2004-11-10 1
第六章解线性代数方程组的迭代法
§6.1向量和矩阵序列的极限
§6.2 迭代法的基本理论
§6.3 几种常见的迭代法
2004-11-10 2
§6.１向量和矩阵序列的极限一.极限的概念
1.向量序列收敛设是中的向量序列，若有
{ }
)(k
x
v
n
R
向量，使
n
Rx ∈
*
r
定义：
0lim
*)(
=?
∞→
xx
k
k
vv
则称收敛于。记为：{ }
)(k
x
v
*
x
v
*)(
lim xx
k
k
vv
=
∞→
Remark：上面的收敛性实际上和范数的选择无关。
（范数的等价性）
2004-11-10 3
２.矩阵序列收敛设是中的矩阵序列，
若有，使，则称收敛于，记为
{ }
)(k
A
nn
R
×
nn
RA
×
∈
0lim
)(
=?
∞→
AA
k
k
{ }
)(k
A
A
定义：
AA
k
k
=
∞→
)(
lim
Remark：上面的收敛性也和范数的选择无关。
2004-11-10 4
二.序列收敛的等价条件设，
则的充要条件是：
Tk
n
kkk
xxxx ),,,(
)()(
2
)(
1
)(
L
v
=
T
n
xxxx ),,,(
**
2
*
1
*
L
v
=
*)(
lim xx
k
k
vv
=
∞→
1.向量序列收敛的等价定理
*
lim
i
k
i
k
xx
vv
=
∞→
）（
）ni,,2,1 L=（
2004-11-10 5
序列收敛的等价条件（续）
*
k
lim
i
k
i
xx
vv
=
∞→
）（
），（ni,,21 L=
证明：充分性
0maxlim
*)(
1
=?
≤≤∞→
i
k
i
nik
xx
0lim
*)(
=?
∞
∞→
xx
k
k
vv
由范数的等价性，
∞
≤
*)(
2
xxc
k
rr
∞
*)(
1
xxc
k
vv
*)(
xx
k
vv
≤
有
0maxlim
*)(
1
=?
≤≤∞→
i
k
i
nik
xx
*)(
lim xx
k
k
vv
=
∞→
即
2004-11-10 6
序列收敛的等价条件（续）
*)(
lim xx
k
k
vv
=
∞→
0lim
*)(
=?
∞→
xx
k
k
vv
必要性由等价性知：
*)(
1
xxc
k
vv
∞
≤
*)(
xx
k
vv
*)(
2
xxc
k
vv
≤
0lim
*)(
=?
∞
∞→
xx
k
k
vv
有
0maxlim
*)(
1
=?
≤≤∞→
i
k
i
nik
xx
即
*
lim
i
k
i
k
xx
vv
=
∞→
）（
即证毕
2004-11-10 7
序列收敛的等价条件（续）
2.矩阵序列收敛的等价定理设，则的充要条件是
nn
k
ij
k
aA
×
= )(
)(
)(
nnij
aA
×
= )(
AA
k
k
=
∞→
）（
lim
ij
k
ij
k
aa =
∞→
)(
lim
ij
k
ij
k
aa =
∞→
)(
lim
，则，
0maxlim
)(
,1
=?
≤≤∞→
ij
k
ij
njik
aa
证明：充分性
0)(maxlim
1
)(
1
=?
∑
=
≤≤∞→
n
j
ij
k
ij
nik
aa
即
0lim =?
∞
∞→
AA
k
k
）（
故
0lim =?
∞→
AA
k
k
）（
由矩阵范数的等价性，
有
AA
k
k
=
∞→
)(
lim
即
2004-11-10 8
序列收敛的等价条件（续）
0)(maxlim
1
)(
1
=?
∑
=
≤≤∞→
n
j
ij
k
ij
nik
aa即0maxlim
)(
,1
=?
≤≤∞→
ij
k
ij
njik
aa也即
ij
k
ij
k
aa =
∞→
)(
lim
故
①.向量序列、矩阵序列的收敛性等价于按分量、按元素的收敛性。
必要性：由矩阵范数的等价性，有
0lim =?
∞
∞→
AA
k
k
）（
0lim =?
∞→
AA
k
k
）（
AA
k
k
=
∞→
）（
lim即,
Remark
证毕
②.对向量序列和矩阵序列，按范数或者按分量元素收敛，都可以转化为数列的收敛。
2004-11-10 9
三.引理
=
r
J
J
J
J
O
2
1
ii
nn
i
i
i
i
J
×
=
λ
λ
λ
1
1
O
O
，
)2,1( riJ
i
K=
证明：任何矩阵B总相似于它的Jordan标准型，即存在可逆阵P，使其中
JBPP =
1
设，则的充要条件是，
nn
RB
×
∈
1)( <Bρ
0lim =
∞→
k
k
B
其中叫做矩阵B 的谱半径。
）（BB
i
ni
λρ
≤≤
=
1
max)(
称为Jordan块。为B的特征值的重数，.
i
n
nn
r
i
i
=
∑
=1
i
λ
2004-11-10 10
续
1111
)())((
== PPJPJPPJPPJPB
kk
K由，则
1?
= PJPB
0lim0lim =?=
∞→∞→
k
i
k
k
k
JB
），（ri,,21 L=
显然
12
1
= P
J
J
J
PB
k
r
k
k
k
O
=
+
+
k
i
k
ik
k
i
nk
i
n
k
k
ik
k
i
nk
i
n
k
k
ik
k
ik
k
i
k
i
C
CC
CCC
J
ii
ii
λ
λ
λ
λλλ
λλλλ
11
2211
112211
O
MO
L
L
由归纳法可证
2004-11-10 11
续其中，时，
不难看出的充要条件为
0lim =
∞→
k
i
k
J
)1()1(
!
1
+= mkkk
m
C
m
k
L 0=
m
k
C
)1,?
i
nL
,2,1( =m
km>
），（ri,21 L=0lim =
∞→
k
i
k
λ
1)(1 <?< B
i
ρλ
即
1)(0lim
)(
<?=
∞→
BJ
k
i
k
ρ
从而
1)(0lim <?=
∞→
BB
k
k
ρ
故证毕
2004-11-10 12
定理
nk
k
k
k
RxxAA ∈?=?=
∞→∞→
vv
,00
)()(
limlim
证明：必要性是显然的。
T
i
e )0,,0,1,0,,0( LL
v
=
取为第i个单位向量
x
v
充分性
,0
)(
lim
=
∞→
i
k
k
eA
v
则这意味着A
(k)
的第i列元素极限为零。
取i＝1，2，…，n，则充分性得证。
证毕
2004-11-10 13
§6.２迭代法的基本理论迭代法的一般格式为
),,,(
)()1()()1( mkkk
k
k
xxxfx
+
=
v
L
vvv
L,1,+= mmk
因为计算一般要用到前面多步的值故称为多步迭代法。
)1( +k
x
v
)()1()(
,,,
mkkk
xxx
v
L
vv
若 ，即 ， ，称为单步迭代法。
)(
)()1( k
k
k
xfx
vv
=
+
0=m L,1,0=k
k
k
k
k
gxBx
vvv
+=
+ )()1(
L,1,0=k
k
B
若 为线性的，即 , ，
称为单步线性迭代法，称为迭代矩阵。
k
f
k
g
v
k
B
gxBx
kk
vvv
+=
+ )()1(
若 ，与k无关，即 ,k=0,1,…，
称为单步定常线性迭代法，或者叫简单迭代法。本章主要讨论简单迭代。
2004-11-10 14
一.简单迭代法的构造设要求解的线性方程组为，其中为非奇异矩阵，为向量。
bxA
v
v
=
b
v
A
将该方程组等价变形为构造简单迭代格式，。若收敛于确定的向量，则就是方程组的解。此时称简单迭代法
，关于初始向量收敛。
gxBx
vvv
+=
{ }
)(k
x
v
L,1,0=k
gxBx
kk
vvv
+=
+ )()1(
*
x
v
*
x
v
gxBx
kk
vvv
+=
+ )()1(
L,1,0=k
)0(
x
v
2004-11-10 15
简单迭代法的构造（续）
①如果对初始向量，，则称此简单迭
)0(
x
v
*)(
lim xx
k
k
vv
=
∞→
代法关于初始向量收敛。一般谈及收敛，是指
)0(
x
v
对任意，均有.
)0(
x
v *)(
lim xx
k
k
vv
=
∞→
③变形为的方式不唯一。
gxBx
r
vv
+=bxA
v
v
=
②同一个简单迭代法可以关于某一个收敛，而关
)0(
x
v
于另外不收敛。
)0(
x
v
④当收敛时，只要充分大，则可用作为的
k
）（1+k
x
v
*
x
r
近似值。
2004-11-10 16
二.简单迭代法的收敛性和收敛速度
1.收敛的充要条件定理1.简单迭代法，，对任意初始向量都收敛的充要条件是：
)0(
x
v
gxBx
kk
rrr
+=
+ )()1(
L,1,0=k
简单迭代法为.
L
vv
r
,2,1,
)1()(
=+=
kgxBx
kk
)()(
*)0(*)1(*)(
xxBxxBxx
kkk
v
r
L
vvvv
==?=?
故设有唯一解，
*
x
r
gxBx
rr
v
+=
0lim =
∞→
k
k
Ba.
1)( <Bρ
b,迭代矩阵的谱半径
2004-11-10 17
收敛的充要条件（续）
=
0
0
1
0
M
M
r
q
e
作为，
*)0(
xx
vv
证明：
b.必要性：用表示的（i,j）元素，简单迭代对任意初始向量有.设不趋于零，则必有位置（p,q）使不趋于零。取第q
k
ij
b
k
B
)0(
x
v
0)(lim
*)0(
=?
∞→
xxB
k
k
vv
k
B
k
pq
b
个单位向量
a.充分性：，则由
0lim =
∞→
k
k
B
）（
）（）（*0*
xxBxx
kk
vvvv
=?
)0(
x
v
*)(
lim xx
k
k
vv
=
∞→
知对于任意初始向量，,
2004-11-10 18
收敛的充要条件（续）
≠
=
=?
M
M
M
M
M
M
M
LL
M
vv
0
0
0
1
0
0
)(
*)0( k
pq
k
pq
k
bbxxB
则有：
即向量的第q个元素不趋于零，从而与 矛盾。
)(lim
*)0(
0
xxB
k
k
vv
→
0)(lim
*)0(
=?
∞→
xxB
k
k
vv
b.由上节引理可以直接证明。
证毕
2004-11-10 19
收敛的充要条件（续）
Remark
①是判定收敛的根本法则。
1)( <Bρ
②时，有可能存在某个初始向量使简单迭代法收敛。
1)( ≥Bρ
)0(
y
v
2004-11-10 20
2.收敛的充分条件引理：
),2,1(,)( FpBB
p
或∞=≤ρ
对任意矩阵，有
nn
RB
×
∈
特征向量，则。
xxB
vv
λ=
证明：事实上，设λ为B的任一特征值，为相应于的
0≠x
v
λ
显然有向量
n
Ry∈
v
，使得为非零矩阵。
T
yx
vv
用右乘上式，可得
T
y
v TT
yxyxB
vvvv
λ=
由矩阵范数的定义，有
p
T
p
p
T
yxByx
vvvv
≤λ
p
B≤λ
从而有
),2,1(,)( FpBB
p
或∞=≤ρ
即证毕
2004-11-10 21
收敛的充分条件（续）
定理2.设方程组有唯一解，其简单迭
gxBx
vvv
+=
*
x
r
数要求与用到的向量范数相容），则代法为，若（用到的矩阵范gxBx
kk
v
rr
+=
+ )()1(
1<B
a.简单迭代格式关于任意初始向量收敛.
)0(
x
r
)1()(*)(
1
≤?
kkk
xx
B
B
xx
rrr
b.
)0()1(*)(
1
xx
B
B
xx
k
k
rrrr
≤?
c.
2004-11-10 22
收敛的充分条件（续）
证明：
a.由且，故，由迭代收
BB ≤)(ρ
1)( <Bρ
1<B
敛基本定理，简单迭代格式对任意收敛。
)0(
x
r
b.由，相减，得：
gxBx
kk
v
rr
+=
+ )()1(
gxBx
rrr
+=
**
)(
)(*)1(* kk
xxBxx
rrrr
=?
+
故①
)(*)(*)1(*
(
kkk
xxBxxBxx
rrrrrr
≤?=?
+
又由，相减得：
gxBx
kk
v
rr
+=
+ )()1(
gxBx
kk
v
rr
+=
)1()(
)(
)1()()()1(?+
=?
kkkk
xxBxx
rrrr
故②
)1()()1()()()1(
(
+
≤?=?
kkkkkk
xxBxxBxx
rrrrrr
2004-11-10 23
收敛的充分条件（续）
从而)(
)1(*)(*)()1( ++
=?
kkkk
xxxxxx
rrrrrr
)1(*)(* +
≥
kk
xxxx
rrrr
≥
由①
)(*)(*)(*
)1(
kkk
xxBxxBxx
rrrrrr
=
1<B
从而有
)()1(*)(
1
1
kkk
xx
B
xx
rrrr
≤?
+
由②
)1()(
1
≤
kk
xx
B
B
rr
即
*)(
xx
k
rr
)1()(
1
≤
kk
xx
B
B
rr
2004-11-10 24
收敛的充分条件（续）
c.由及②
b
)1()(
1
≤
kk
xx
B
B
rr
)2()1(
2
1
≤
kk
xx
B
B
rr
*)(
xx
k
rr
.
)0()1(
1
xx
B
B
k
rr
L?
≤≤
即
*)(
xx
k
rr
)0()1(
1
xx
B
B
k
rr
≤
证毕
2004-11-10 25
3.收敛速度由定理2可见，若且越小，则收敛到解的速度越快。实际上，可以确切地说，谱半径相对于1来说越小，则的收敛速度越快。
1≤B
B
)(k
x
v
)(Bρ
)(k
x
v
gxBx
vvv
+= **
由和还可得到
gxBx
kk
vvv
+=
)1()(
*)(*)(*)(*
)0()2(2)1()(
xxBxxBxxBxx
kkkk
vv
L
vvvvvv
==?=?=?
**
)0()(
xxBxx
kk
vvvv
≤?
若要求迭代k次后所产生的误差缩小为初始误差的
10
－m
倍，即
*10*
)0()(
xxxx
mk
vvvv
≤?
m
k
B
≤10
则只需
2004-11-10 26
收敛速度（续）
可以证明，，则存在从属于矩阵范数，
使。因而上面的条件可以近似代替为
0>?ε
ερ <? )(BB
mk
B
≤10)(ρ
)(ln
10ln
B
m
k
ρ?
≥
故为了达到所提出的精度，上式给出了大约所需要的迭代次数。当误差压缩量10
－m
确定后，这个次数主要由分母
)(ln Bρη?=
所刻划的。η越大，则迭代次数越少，收敛越快。
一般将η定义为简单迭代法的收敛速度。
2004-11-10 27
三.高斯——塞德尔（Gauss-Seidel）迭代设有简单迭代法,k=0,1,…gxBx
kk
v
rr
+=
+ )()1(
将B分解为
+
=+
=
b
bb
bbb
bb
b
BBB
nn
n
n
nn
MO
L
L
L
OMM
222
11211
21
21
21
0
0
0
gxBxBx
kkk
v
rrr
++=
+ )(
2
)(
1
)1(
则将其修改为k=0,1,…
gxBxBx
kkk
v
rrr
++=
+++ )1(
2
)1(
1
)1(
上式称为由简单迭代法导出的Gauss-Seidel迭代法。
它的分量形式为
i=1,2,……,n
i
n
ij
k
jij
i
j
k
jij
k
i
gxbxbx ++=
∑∑
=
=
++ )(
1
1
)1()1(
2004-11-10 28
1.迭代收敛的充要条件与简单迭代法相应的Gauss-Seidel迭代可化为
gBIxBBIx
kk
v
rr
1
1
)(
2
1
1
)1(
)()(
+
+?=
Gauss-Seidel迭代收敛的充要条件为
1))((
2
1
1
<?
BBIρ
2.迭代收敛的充分条件
①若，则对于任意初始向量,Gauss-
Seidel迭代收敛。
1)(
2
1
1
<?
BBI
)0(
x
r
②若或，，则Gauss-Seidel迭代关于任意的初始向量收敛。
1<
∞
B 1
1
<B
21
BBB +=
)0(
x
r
2004-11-10 29
迭代收敛的充分条件（续）
的分量形式
i
n
ij
k
jij
i
j
k
jij
k
i
gxbxbx ++=
∑∑
=
=
++ )(
1
1
)1()1(
i
n
j
jiji
gxbx +=
∑
=1
**
)()(
*)(
1
1
*)1(*)1(
j
n
ij
k
jij
i
j
j
k
jiji
k
i
xxbxxbxx
∑∑
=
=
++
+?=?
∑∑
=
=
++
+?≤?
n
ij
j
k
jij
i
j
j
k
jiji
k
i
xxbxxbxx
*)(
1
1
*)1(*)1(
记
*)(
1
max
i
k
i
ni
k
xx?=
≤≤
δ ∑
=
=
1
1
i
j
iji
bβ
∑
=
=
n
ij
iji
bγ
证明：
由
+=
++=
++
gxBx
gxBxBx
kkk
rr
v
v
rrr
**
)(
2
)1(
1
)1(
k=0,1,…
1
11
max
<=
∑
=≤≤
∞
n
j
ij
ni
bB
仅以为例。
相减有
2004-11-10 30
迭代收敛的充分条件（续）
有上式对i=1,2,……,n都成立，
ikiki
k
i
xx γδβδ +≤?
+
+
1
*)1(
1
*)1(
00
+
+
=?
ki
k
i
xx δ
故有使0
ii =
00
11 ikikk
γδβδδ +≤
++
有
1+k
δ
0
1
)
1
()
1
(
0
0
0
0
δ
β
γ
δ
β
γ
+
≤≤
≤
k
i
i
k
i
i
L
即其中
0max
*0
1
0
≠?=
≤≤
ii
ni
xxδ
注意：∑
=
∞
<≤=+
n
j
ijii
Bb
1
00
1γβ
即
01
00
>>?
ii
γβ
2004-11-10 31
迭代收敛的充分条件（续）
所以。当k则
1
1
0
0
0
<
≤
i
i
β
γ
∞→
1
0
0
1
+
k
i
i
）（
β
γ
0→
即当k时，则
∞→ 0max
*)1(
1
1
→?=
+
≤≤
+ i
k
i
ni
k
xxδ
*)(
lim
i
k
i
k
xx =
∞→
即故由序列收敛的等价性定理，知
*)(
lim xx
k
k
rr
=
∞→
对任意的都成立。
)0(
x
r
证毕
Remark：当或时，简单迭代法与相应的Gauss-Seidel迭代法同时关于任意初始向量收敛。
1<
∞
B 1
1
<B
2004-11-10 32
§6.3 几种常见的迭代法一.Jacobi迭代法
1.迭代格式设有n 阶方程组
=+++
=+++
=+++
nnnnnn
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
L
L
L
L
2211
22222121
11212111
其中系数矩阵非奇异，且，i=1,2，……，n0≠
ii
a
+=
+=
+=
)(
1
)(
1
)(
1
11,2211
22323121
22
2
11313212
11
1
nnnnnn
nn
n
nn
nn
bxaxaxa
a
x
bxaxaxa
a
x
bxaxaxa
a
x
L
L
L
L
将上式变形为
2004-11-10 33
Jacobi迭代法的迭代格式（续）
建立迭代格式
+=
+=
+=
+
+
+
)(
1
)(
1
)(
1
)(
11,
)(
22
)(
11
)1(
2
)(
2
)(
323
)(
121
22
)1(
2
1
)(
1
)(
313
)(
212
11
)1(
1
n
k
nnn
k
n
k
n
nn
k
n
k
nn
kkk
k
nn
kkk
bxaxaxa
a
x
bxaxaxa
a
x
bxaxaxa
a
x
L
L
L
L
上面的迭代式称为雅可比（Jacobi）迭代格式。
用矩阵形式来表示方程组的迭代法设det(A),且
0≠
0≠
ii
a
+
+
=
00000
00
00
0
0
0
00
00
00000
000
00
00
000
223
11312
21
3231
21
22
11
21
22221
11211
MOOOM
MLO
L
L
LL
OMMM
O
OO
OO
O
L
MOMM
L
L
n
n
nn
nnnnnn
n
n
aa
aaa
aa
aa
a
a
a
a
aaa
aaa
aaa
2004-11-10 34
Jacobi迭代法的迭代格式（续）
bxULD
r
r
=++ )(
记A=D+L+U
xULbxD
r
r
r
)( +?=
bxA
r
r
=
则
bDxULDx
r
rr
11
)(
++?=
雅可比迭代式成为：
bDxULDx
kk
r
rr
1)(1)1(
)(
+
++?=
)(
1
ULDB
J
+?=
bDg
r
r
1
1
=
令
1
)()1(
gxBx
k
J
k
rrr
+=
+
则得
2004-11-10 35
a.充要条件：Jacobi方法关于任意初始向量都收敛的充要条件是
)0(
x
r
1)( <
J
Bρ
2.收敛条件
b.充分条件：
（II）设系数矩阵严格对角占优，
nnij
aA
×
= )(
则Jacobi迭代法关于任意初始向量收敛
)0(
x
r
（I）若则Jacobi方法关于任意初始向量都收敛。
1<
J
B
)0(
x
r
（按行）
,（i=1,2,…,n）
∑
≠=
>
n
jij
ijii
aa
,1
（j=1,2,…,n）(按列)
∑
≠=
>
n
jii
ijjj
aa
,1
即或
2004-11-10 36
Jacobi迭代法的收敛条件（续）
由严格对角占优矩阵的定义有（按行）
i=1,2,……n1
1
,1,11
<==
∑∑∑
≠=≠==
n
ijj
n
ijj
ij
iiii
ij
n
j
ij
a
aa
a
b
即
1<
∞
J
B
证明：
j=1,2,…，n
1
1
,1,11
<==
∑∑∑
≠=≠==
n
jii
n
jii
ij
jjjj
ij
n
i
ij
a
aa
a
b
即
1
1
<
J
B
因此Jacobi迭代法对任意初始向量 收敛。
)0(
x
r
证毕定义：设，若
∑
≠=
≥
n
ijj
ijii
aa
,1
（i=1,2,……n）
nn
ij
RaA
×
∈= )(
且其中至少有一个严格不等式成立，则称A为按行弱对角占优。
2004-11-10 37
Jacobi迭代法的收敛条件（续）
则称A为可约矩阵。
以n阶单位矩阵I
n
的n个列向量为列构成
n阶矩阵称为置换矩阵,是
1，2，……,n的一个排列。
n
eee
r
L
rr
,,,
21
n
jjj,,,
21
L
),,,(
21 jnjj
eeep
r
L
rr
=
=
22
1211
0 A
AA
PAP
T
若可找到置换矩阵P，使A呈
22
1211
0 A
AA
换化为，其中是方阵，则称A为不可约矩阵。
2211
,AA
定义：设，若A不能经过行置换与相应的列置
nn
RA
×
∈
（III）设A为不可约对角占优矩阵，则Jacobi迭代法关于任意初始向量收敛。
)0(
x
r
2004-11-10 38
二.与Jacobi迭代法相应的Gauss-Seidel法
1.迭代格式其迭代式为
+=
+=
+=
+
+++
++
+
)(
1
)(
1
)(
1
)1(
11.
)1(
22
)1(
11
)1(
2
)(
2
)(
323
)1(
121
22
)1(
2
1
)(
1
)(
313
)(
212
11
)1(
1
n
k
nnn
k
n
k
n
nn
k
n
k
nn
kkk
k
nn
kkk
bxaxaxa
a
x
bxaxaxa
a
x
bxaxaxa
a
x
L
L
L
L
矩阵形式为
bxULD
v
v
=++ )(
bxA
r
r
=
xUbxLD
v
r
v
=+ )(
)()1()1( kkk
xUxLbxD
rr
r
r
=
++
)()1(
)(
kk
xUbxLD
r
r
r
=+
+
2004-11-10 39
迭代格式（续）
因,故存在，于是Gauss-Seidel
迭代式为
0≠
ii
a
1
)(
+LD
bLDxULDx
kk
v
v
r
1)(1)1(
)()(
+
+++?=
2
)()1(
gxGx
k
s
k
rrr
+=
+
则得
ULDG
S
1
)(
+?=
2
g
r
bLD
v
1
)(
+=
令
s
G
称为Gauss-Seidel迭代法的迭代矩阵。
Remark1:今后若无特殊说明，凡谈到Gauss-Seidel
迭代法（简称G-S迭代法），均指与Jacobi迭代法相应的Gauss-Seidel迭代法。
Remark2:并不是任何时候Gauss-Seidel迭代法都比
Jacobi迭代法收敛快。甚至也有Jacobi法收敛而
Gauss-Seidel迭代法不收敛的例子。
2004-11-10 40
2.收敛条件
a.充要条件：
收敛的充要条件是：1)( <
s
Bρ
)0(
x
r
G-S法关于任意初始向量都
b.充分条件：
1<
s
B
)0(
x
r
①若则G-S方法关于任意初始向量都收敛。
关于任意初始向量收敛。
②设系数矩阵严格对角占优，则G-S方法
)(
ij
aA=
)0(
x
r
③设A为不可均弱对角占优矩阵，则G-S迭代法关于任意初始向量收敛。
)0(
x
r
④设A为对称正定矩阵，则G-S迭代法关于任意初始向量收敛。
)0(
x
r
2004-11-10 41
三.逐次超松弛迭代法
（SOR法-Successive Over Relaxation）
1.迭代公式将G-S迭代格式
∑
=
+
=
1
1
)1(
(
1
i
j
iji
ii
k
i
ab
a
x）
∑
+=
+
n
ij
k
jij
k
j
xax
1
)()1(
ni,...,2,1=
改写为：
∑∑
=
+
=
+
+=
n
ij
k
jij
k
j
i
j
iji
ii
k
i
k
i
xaxab
a
xx )(
1
)()1(
1
1
)(
)1(
并记
∑∑
=
+
=
+
=
n
ij
k
jij
k
j
i
j
iji
k
i
xaxabr
)()1(
1
1
)1(
ni,...,2,1=
ni,...2,1=
一般地，残量。0
)1(
≠
+k
i
r
2004-11-10 42
逐次超松弛迭代法的迭代格式（续）
∑
=
+
+=
1
1
)(
)1(
(
i
j
iji
ii
k
i
k
i
ab
a
xx
ω
）
∑
=
+
n
ij
k
jij
k
j
xax
)()1(
ni,...2,1=
+?=
+ )()1(
)1(
k
i
k
i
xx ω
∑
=
1
1
i
j
iji
ii
ab
a
（
ω
）
∑
+=
+
n
ij
k
jij
k
j
xax
1
)()1(
矩阵形式:
将迭代格式改写
)()1(
1
)(
1
1
)1()()1(
∑∑
+=
=
++
+?=
n
ij
k
jij
i
j
k
jiji
k
iii
k
iii
xaxabxaxa ωω
由矩阵分解成 A＝D＋L＋U
这就是逐次超松驰迭代法（SOR方法)，称为松驰因子。
ω
SOR方法的计算公式也常写为：
Remark：可见，SOR方法的得到的可以看成是G-S方法的结果与的加权平均。
)1( +k
i
x
)(k
i
x
2004-11-10 43
逐次超松弛迭代法的迭代格式（续）
则相应的矩阵形式为
)()1(
)()1()()1( kkkk
xUxLbxDxD
vvv
r
+?=
++
ωω
v
bxUDxLD
kk
v
r
ωωωω +=+
+ )()1(
))1(()(
v
即
bLDxUDLDx
kk
vv
1)(1)1(
)())1(()(
+
+++= ωωωωω
v
故
gxLx
kk
vvv
+=
+ )()1(
ω
其中
))1(()(
1
UDLDL ωωω
ω
+=
故SOR方法的矩阵形式为
bLDg
r
v
1
)(
+= ωω
ω
L
称为SOR方法的迭代矩阵。
2004-11-10 44
2.SOR方法的收敛性
A.充要条件：SOR法关于任意初始向量都收敛的充要条件是。
1)( <
ω
ρ L
)0(
x
r
SOR方法收敛
Q
证：
B.必要条件：设解的SOR方法关于任意初始向量都收敛，则0 < ω<2。
)0(det,≠= AbxA
v
v
)0(
x
r
设的特征值为ω
L
n
λλλ,...,,
21
1)( <∴
ω
ρ L
n
λλλ,..
21
)det(
ω
L=
由的特征多项式的模与系数的关系知：ω
L
n
λλλ L
21
=)det(
ω
L
)(
ω
ρ L≤
即
2004-11-10 45
SOR方法的收敛性（续）
即
1)()det(
1
<≤
ωω
ρ LL
n
而
))1det(())det((
1
UDLD ωωω+=
)det(
ω
L
))1det(()][det((
1
UDLD ωωω+=
[ ] ))1det((det
1
DD ω=
nn
n
nn
aaaaa,..)1()...(
11
1
2211
ω=
n
)1( ω?=
11)det(
1
<?= ω
ω
n
L
故0＜ω＜2。
即证毕
2004-11-10 46
SOR方法的收敛性（续）
yyL
rr
λ
ω
=
0),...,,(
21
≠=
n
yyyy
r
设为对应的的特征向量，即
λy
r
ω
L
C.充分条件：若A对称正定，且0 <ω<2，则SOR法关于任意初始向量收敛（此时，0 <ω<2对称正定为充要条件）。
)0(
x
r
证：
yyUDLD
rr
λωωω =+
))1(()(
1
即
yLDyUD
rr
)())1(( ωλωω +=
在复空间中考虑内积
n
C )(是复数λ
),)((,))1((( yyLDyyUD
rrrr
ωλωω +=）
即
),(),(
),(),(),(
yyLyyD
yyUyyDyyD
rrrr
rrrrrr
ω
ωω
λ
+
=
2004-11-10 47
SOR方法的收敛性（续）
又记
βα iyyL +=),(
rr
因为
∑
=
>==
n
i
iii
yayyD
1
2
0),( σ
rr
),( yyU
rr
yUy
T
rr
= yLy
TT
rr
= yyL
T
rr
)(=
),( yLy
rr
= ),( yyL
rr
= βα i?=
),(0 yyA
rr
<
),)(( yyULD
rr
++=
所以
)()( βαβασ ii?+++= ασ 2+=
ωβωασ
ωβωαωσσ
i
i
++
+
=
)(
)(
)(
)(
βαωσ
βαωωσσ
λ
i
i
++
=
2004-11-10 48
SOR方法的收敛性（续）
=
2
λ
222
222
)(
)(
βωωασ
βωωαωσσ
++
+
当0＜＜2时，则有
ω
22
)()( ωασαωωσσ +
[ ]σωαωσασω += )(24
0)2)(2( <?+= ωασσω
即，故SOR方法收敛。1<λ
证毕
2004-11-10 49
SOR方法的收敛性（续）
Remark：能使SOR方法收敛最快的松弛因子叫做最佳松弛因子，记为ω
opt
。
对某些特殊类型的矩阵，可以建立SOR方法最佳松弛因子理论。例如，对于具有对称正定，或严格对角占优或弱对角占优且不可约等性质的矩阵A的线性方程组，可以建立最佳松弛因子其中ρ(J)为解Ax＝b的雅可比迭代法的迭代矩阵的谱半径。一般情况下确定ω
opt
并不容易，实际计算时一般都是根据试算的情况确定ω
opt
的一个近似值。
2
))((11
2
J
opt
ρ
ω
+
=
2004-11-10 50
四.数值算例取，用迭代方法求解如下的方程组，使得。
T
x )1,1,1(
0
=
v
5)()1(
10
∞
+
≤?
kk
xx
vv
=+?
=?+
=+
244
3043
2434
32
321
21
xx
xxx
xx
求解
2004-11-10 51
Remark：使用迭代法求解线代数方程组需注意的问题
1.迭代法的收敛性与初始向量的选取无关。但初始向量的选取对迭代的工作量有重大影响。
2.在使用实用误差估计式停止迭代时，
ε<?
+ )()1( kk
xx
要选的恰当。
ε
3.在迭代格式中，若是病态阵，
fxBx
kk
r
rr
+=
+ )()1(
BI?
那么一般迭代法得不到好的结果。
4.如果,则用此判断法比用方便。
1<=qB 1)( <Bρ
5.对某些方程组，有时可适当作些变形，以使得迭代法收敛。
第六章解线性代数方程组的迭代法
§6.1向量和矩阵序列的极限
§6.2 迭代法的基本理论
§6.3 几种常见的迭代法
2004-11-10 2
§6.１向量和矩阵序列的极限一.极限的概念
1.向量序列收敛设是中的向量序列，若有
{ }
)(k
x
v
n
R
向量，使
n
Rx ∈
*
r
定义：
0lim
*)(
=?
∞→
xx
k
k
vv
则称收敛于。记为：{ }
)(k
x
v
*
x
v
*)(
lim xx
k
k
vv
=
∞→
Remark：上面的收敛性实际上和范数的选择无关。
（范数的等价性）
2004-11-10 3
２.矩阵序列收敛设是中的矩阵序列，
若有，使，则称收敛于，记为
{ }
)(k
A
nn
R
×
nn
RA
×
∈
0lim
)(
=?
∞→
AA
k
k
{ }
)(k
A
A
定义：
AA
k
k
=
∞→
)(
lim
Remark：上面的收敛性也和范数的选择无关。
2004-11-10 4
二.序列收敛的等价条件设，
则的充要条件是：
Tk
n
kkk
xxxx ),,,(
)()(
2
)(
1
)(
L
v
=
T
n
xxxx ),,,(
**
2
*
1
*
L
v
=
*)(
lim xx
k
k
vv
=
∞→
1.向量序列收敛的等价定理
*
lim
i
k
i
k
xx
vv
=
∞→
）（
）ni,,2,1 L=（
2004-11-10 5
序列收敛的等价条件（续）
*
k
lim
i
k
i
xx
vv
=
∞→
）（
），（ni,,21 L=
证明：充分性
0maxlim
*)(
1
=?
≤≤∞→
i
k
i
nik
xx
0lim
*)(
=?
∞
∞→
xx
k
k
vv
由范数的等价性，
∞
≤
*)(
2
xxc
k
rr
∞
*)(
1
xxc
k
vv
*)(
xx
k
vv
≤
有
0maxlim
*)(
1
=?
≤≤∞→
i
k
i
nik
xx
*)(
lim xx
k
k
vv
=
∞→
即
2004-11-10 6
序列收敛的等价条件（续）
*)(
lim xx
k
k
vv
=
∞→
0lim
*)(
=?
∞→
xx
k
k
vv
必要性由等价性知：
*)(
1
xxc
k
vv
∞
≤
*)(
xx
k
vv
*)(
2
xxc
k
vv
≤
0lim
*)(
=?
∞
∞→
xx
k
k
vv
有
0maxlim
*)(
1
=?
≤≤∞→
i
k
i
nik
xx
即
*
lim
i
k
i
k
xx
vv
=
∞→
）（
即证毕
2004-11-10 7
序列收敛的等价条件（续）
2.矩阵序列收敛的等价定理设，则的充要条件是
nn
k
ij
k
aA
×
= )(
)(
)(
nnij
aA
×
= )(
AA
k
k
=
∞→
）（
lim
ij
k
ij
k
aa =
∞→
)(
lim
ij
k
ij
k
aa =
∞→
)(
lim
，则，
0maxlim
)(
,1
=?
≤≤∞→
ij
k
ij
njik
aa
证明：充分性
0)(maxlim
1
)(
1
=?
∑
=
≤≤∞→
n
j
ij
k
ij
nik
aa
即
0lim =?
∞
∞→
AA
k
k
）（
故
0lim =?
∞→
AA
k
k
）（
由矩阵范数的等价性，
有
AA
k
k
=
∞→
)(
lim
即
2004-11-10 8
序列收敛的等价条件（续）
0)(maxlim
1
)(
1
=?
∑
=
≤≤∞→
n
j
ij
k
ij
nik
aa即0maxlim
)(
,1
=?
≤≤∞→
ij
k
ij
njik
aa也即
ij
k
ij
k
aa =
∞→
)(
lim
故
①.向量序列、矩阵序列的收敛性等价于按分量、按元素的收敛性。
必要性：由矩阵范数的等价性，有
0lim =?
∞
∞→
AA
k
k
）（
0lim =?
∞→
AA
k
k
）（
AA
k
k
=
∞→
）（
lim即,
Remark
证毕
②.对向量序列和矩阵序列，按范数或者按分量元素收敛，都可以转化为数列的收敛。
2004-11-10 9
三.引理
=
r
J
J
J
J
O
2
1
ii
nn
i
i
i
i
J
×
=
λ
λ
λ
1
1
O
O
，
)2,1( riJ
i
K=
证明：任何矩阵B总相似于它的Jordan标准型，即存在可逆阵P，使其中
JBPP =
1
设，则的充要条件是，
nn
RB
×
∈
1)( <Bρ
0lim =
∞→
k
k
B
其中叫做矩阵B 的谱半径。
）（BB
i
ni
λρ
≤≤
=
1
max)(
称为Jordan块。为B的特征值的重数，.
i
n
nn
r
i
i
=
∑
=1
i
λ
2004-11-10 10
续
1111
)())((
== PPJPJPPJPPJPB
kk
K由，则
1?
= PJPB
0lim0lim =?=
∞→∞→
k
i
k
k
k
JB
），（ri,,21 L=
显然
12
1
= P
J
J
J
PB
k
r
k
k
k
O
=
+
+
k
i
k
ik
k
i
nk
i
n
k
k
ik
k
i
nk
i
n
k
k
ik
k
ik
k
i
k
i
C
CC
CCC
J
ii
ii
λ
λ
λ
λλλ
λλλλ
11
2211
112211
O
MO
L
L
由归纳法可证
2004-11-10 11
续其中，时，
不难看出的充要条件为
0lim =
∞→
k
i
k
J
)1()1(
!
1
+= mkkk
m
C
m
k
L 0=
m
k
C
)1,?
i
nL
,2,1( =m
km>
），（ri,21 L=0lim =
∞→
k
i
k
λ
1)(1 <?< B
i
ρλ
即
1)(0lim
)(
<?=
∞→
BJ
k
i
k
ρ
从而
1)(0lim <?=
∞→
BB
k
k
ρ
故证毕
2004-11-10 12
定理
nk
k
k
k
RxxAA ∈?=?=
∞→∞→
vv
,00
)()(
limlim
证明：必要性是显然的。
T
i
e )0,,0,1,0,,0( LL
v
=
取为第i个单位向量
x
v
充分性
,0
)(
lim
=
∞→
i
k
k
eA
v
则这意味着A
(k)
的第i列元素极限为零。
取i＝1，2，…，n，则充分性得证。
证毕
2004-11-10 13
§6.２迭代法的基本理论迭代法的一般格式为
),,,(
)()1()()1( mkkk
k
k
xxxfx
+
=
v
L
vvv
L,1,+= mmk
因为计算一般要用到前面多步的值故称为多步迭代法。
)1( +k
x
v
)()1()(
,,,
mkkk
xxx
v
L
vv
若 ，即 ， ，称为单步迭代法。
)(
)()1( k
k
k
xfx
vv
=
+
0=m L,1,0=k
k
k
k
k
gxBx
vvv
+=
+ )()1(
L,1,0=k
k
B
若 为线性的，即 , ，
称为单步线性迭代法，称为迭代矩阵。
k
f
k
g
v
k
B
gxBx
kk
vvv
+=
+ )()1(
若 ，与k无关，即 ,k=0,1,…，
称为单步定常线性迭代法，或者叫简单迭代法。本章主要讨论简单迭代。
2004-11-10 14
一.简单迭代法的构造设要求解的线性方程组为，其中为非奇异矩阵，为向量。
bxA
v
v
=
b
v
A
将该方程组等价变形为构造简单迭代格式，。若收敛于确定的向量，则就是方程组的解。此时称简单迭代法
，关于初始向量收敛。
gxBx
vvv
+=
{ }
)(k
x
v
L,1,0=k
gxBx
kk
vvv
+=
+ )()1(
*
x
v
*
x
v
gxBx
kk
vvv
+=
+ )()1(
L,1,0=k
)0(
x
v
2004-11-10 15
简单迭代法的构造（续）
①如果对初始向量，，则称此简单迭
)0(
x
v
*)(
lim xx
k
k
vv
=
∞→
代法关于初始向量收敛。一般谈及收敛，是指
)0(
x
v
对任意，均有.
)0(
x
v *)(
lim xx
k
k
vv
=
∞→
③变形为的方式不唯一。
gxBx
r
vv
+=bxA
v
v
=
②同一个简单迭代法可以关于某一个收敛，而关
)0(
x
v
于另外不收敛。
)0(
x
v
④当收敛时，只要充分大，则可用作为的
k
）（1+k
x
v
*
x
r
近似值。
2004-11-10 16
二.简单迭代法的收敛性和收敛速度
1.收敛的充要条件定理1.简单迭代法，，对任意初始向量都收敛的充要条件是：
)0(
x
v
gxBx
kk
rrr
+=
+ )()1(
L,1,0=k
简单迭代法为.
L
vv
r
,2,1,
)1()(
=+=
kgxBx
kk
)()(
*)0(*)1(*)(
xxBxxBxx
kkk
v
r
L
vvvv
==?=?
故设有唯一解，
*
x
r
gxBx
rr
v
+=
0lim =
∞→
k
k
Ba.
1)( <Bρ
b,迭代矩阵的谱半径
2004-11-10 17
收敛的充要条件（续）
=
0
0
1
0
M
M
r
q
e
作为，
*)0(
xx
vv
证明：
b.必要性：用表示的（i,j）元素，简单迭代对任意初始向量有.设不趋于零，则必有位置（p,q）使不趋于零。取第q
k
ij
b
k
B
)0(
x
v
0)(lim
*)0(
=?
∞→
xxB
k
k
vv
k
B
k
pq
b
个单位向量
a.充分性：，则由
0lim =
∞→
k
k
B
）（
）（）（*0*
xxBxx
kk
vvvv
=?
)0(
x
v
*)(
lim xx
k
k
vv
=
∞→
知对于任意初始向量，,
2004-11-10 18
收敛的充要条件（续）
≠
=
=?
M
M
M
M
M
M
M
LL
M
vv
0
0
0
1
0
0
)(
*)0( k
pq
k
pq
k
bbxxB
则有：
即向量的第q个元素不趋于零，从而与 矛盾。
)(lim
*)0(
0
xxB
k
k
vv
→
0)(lim
*)0(
=?
∞→
xxB
k
k
vv
b.由上节引理可以直接证明。
证毕
2004-11-10 19
收敛的充要条件（续）
Remark
①是判定收敛的根本法则。
1)( <Bρ
②时，有可能存在某个初始向量使简单迭代法收敛。
1)( ≥Bρ
)0(
y
v
2004-11-10 20
2.收敛的充分条件引理：
),2,1(,)( FpBB
p
或∞=≤ρ
对任意矩阵，有
nn
RB
×
∈
特征向量，则。
xxB
vv
λ=
证明：事实上，设λ为B的任一特征值，为相应于的
0≠x
v
λ
显然有向量
n
Ry∈
v
，使得为非零矩阵。
T
yx
vv
用右乘上式，可得
T
y
v TT
yxyxB
vvvv
λ=
由矩阵范数的定义，有
p
T
p
p
T
yxByx
vvvv
≤λ
p
B≤λ
从而有
),2,1(,)( FpBB
p
或∞=≤ρ
即证毕
2004-11-10 21
收敛的充分条件（续）
定理2.设方程组有唯一解，其简单迭
gxBx
vvv
+=
*
x
r
数要求与用到的向量范数相容），则代法为，若（用到的矩阵范gxBx
kk
v
rr
+=
+ )()1(
1<B
a.简单迭代格式关于任意初始向量收敛.
)0(
x
r
)1()(*)(
1
≤?
kkk
xx
B
B
xx
rrr
b.
)0()1(*)(
1
xx
B
B
xx
k
k
rrrr
≤?
c.
2004-11-10 22
收敛的充分条件（续）
证明：
a.由且，故，由迭代收
BB ≤)(ρ
1)( <Bρ
1<B
敛基本定理，简单迭代格式对任意收敛。
)0(
x
r
b.由，相减，得：
gxBx
kk
v
rr
+=
+ )()1(
gxBx
rrr
+=
**
)(
)(*)1(* kk
xxBxx
rrrr
=?
+
故①
)(*)(*)1(*
(
kkk
xxBxxBxx
rrrrrr
≤?=?
+
又由，相减得：
gxBx
kk
v
rr
+=
+ )()1(
gxBx
kk
v
rr
+=
)1()(
)(
)1()()()1(?+
=?
kkkk
xxBxx
rrrr
故②
)1()()1()()()1(
(
+
≤?=?
kkkkkk
xxBxxBxx
rrrrrr
2004-11-10 23
收敛的充分条件（续）
从而)(
)1(*)(*)()1( ++
=?
kkkk
xxxxxx
rrrrrr
)1(*)(* +
≥
kk
xxxx
rrrr
≥
由①
)(*)(*)(*
)1(
kkk
xxBxxBxx
rrrrrr
=
1<B
从而有
)()1(*)(
1
1
kkk
xx
B
xx
rrrr
≤?
+
由②
)1()(
1
≤
kk
xx
B
B
rr
即
*)(
xx
k
rr
)1()(
1
≤
kk
xx
B
B
rr
2004-11-10 24
收敛的充分条件（续）
c.由及②
b
)1()(
1
≤
kk
xx
B
B
rr
)2()1(
2
1
≤
kk
xx
B
B
rr
*)(
xx
k
rr
.
)0()1(
1
xx
B
B
k
rr
L?
≤≤
即
*)(
xx
k
rr
)0()1(
1
xx
B
B
k
rr
≤
证毕
2004-11-10 25
3.收敛速度由定理2可见，若且越小，则收敛到解的速度越快。实际上，可以确切地说，谱半径相对于1来说越小，则的收敛速度越快。
1≤B
B
)(k
x
v
)(Bρ
)(k
x
v
gxBx
vvv
+= **
由和还可得到
gxBx
kk
vvv
+=
)1()(
*)(*)(*)(*
)0()2(2)1()(
xxBxxBxxBxx
kkkk
vv
L
vvvvvv
==?=?=?
**
)0()(
xxBxx
kk
vvvv
≤?
若要求迭代k次后所产生的误差缩小为初始误差的
10
－m
倍，即
*10*
)0()(
xxxx
mk
vvvv
≤?
m
k
B
≤10
则只需
2004-11-10 26
收敛速度（续）
可以证明，，则存在从属于矩阵范数，
使。因而上面的条件可以近似代替为
0>?ε
ερ <? )(BB
mk
B
≤10)(ρ
)(ln
10ln
B
m
k
ρ?
≥
故为了达到所提出的精度，上式给出了大约所需要的迭代次数。当误差压缩量10
－m
确定后，这个次数主要由分母
)(ln Bρη?=
所刻划的。η越大，则迭代次数越少，收敛越快。
一般将η定义为简单迭代法的收敛速度。
2004-11-10 27
三.高斯——塞德尔（Gauss-Seidel）迭代设有简单迭代法,k=0,1,…gxBx
kk
v
rr
+=
+ )()1(
将B分解为
+
=+
=
b
bb
bbb
bb
b
BBB
nn
n
n
nn
MO
L
L
L
OMM
222
11211
21
21
21
0
0
0
gxBxBx
kkk
v
rrr
++=
+ )(
2
)(
1
)1(
则将其修改为k=0,1,…
gxBxBx
kkk
v
rrr
++=
+++ )1(
2
)1(
1
)1(
上式称为由简单迭代法导出的Gauss-Seidel迭代法。
它的分量形式为
i=1,2,……,n
i
n
ij
k
jij
i
j
k
jij
k
i
gxbxbx ++=
∑∑
=
=
++ )(
1
1
)1()1(
2004-11-10 28
1.迭代收敛的充要条件与简单迭代法相应的Gauss-Seidel迭代可化为
gBIxBBIx
kk
v
rr
1
1
)(
2
1
1
)1(
)()(
+
+?=
Gauss-Seidel迭代收敛的充要条件为
1))((
2
1
1
<?
BBIρ
2.迭代收敛的充分条件
①若，则对于任意初始向量,Gauss-
Seidel迭代收敛。
1)(
2
1
1
<?
BBI
)0(
x
r
②若或，，则Gauss-Seidel迭代关于任意的初始向量收敛。
1<
∞
B 1
1
<B
21
BBB +=
)0(
x
r
2004-11-10 29
迭代收敛的充分条件（续）
的分量形式
i
n
ij
k
jij
i
j
k
jij
k
i
gxbxbx ++=
∑∑
=
=
++ )(
1
1
)1()1(
i
n
j
jiji
gxbx +=
∑
=1
**
)()(
*)(
1
1
*)1(*)1(
j
n
ij
k
jij
i
j
j
k
jiji
k
i
xxbxxbxx
∑∑
=
=
++
+?=?
∑∑
=
=
++
+?≤?
n
ij
j
k
jij
i
j
j
k
jiji
k
i
xxbxxbxx
*)(
1
1
*)1(*)1(
记
*)(
1
max
i
k
i
ni
k
xx?=
≤≤
δ ∑
=
=
1
1
i
j
iji
bβ
∑
=
=
n
ij
iji
bγ
证明：
由
+=
++=
++
gxBx
gxBxBx
kkk
rr
v
v
rrr
**
)(
2
)1(
1
)1(
k=0,1,…
1
11
max
<=
∑
=≤≤
∞
n
j
ij
ni
bB
仅以为例。
相减有
2004-11-10 30
迭代收敛的充分条件（续）
有上式对i=1,2,……,n都成立，
ikiki
k
i
xx γδβδ +≤?
+
+
1
*)1(
1
*)1(
00
+
+
=?
ki
k
i
xx δ
故有使0
ii =
00
11 ikikk
γδβδδ +≤
++
有
1+k
δ
0
1
)
1
()
1
(
0
0
0
0
δ
β
γ
δ
β
γ
+
≤≤
≤
k
i
i
k
i
i
L
即其中
0max
*0
1
0
≠?=
≤≤
ii
ni
xxδ
注意：∑
=
∞
<≤=+
n
j
ijii
Bb
1
00
1γβ
即
01
00
>>?
ii
γβ
2004-11-10 31
迭代收敛的充分条件（续）
所以。当k则
1
1
0
0
0
<
≤
i
i
β
γ
∞→
1
0
0
1
+
k
i
i
）（
β
γ
0→
即当k时，则
∞→ 0max
*)1(
1
1
→?=
+
≤≤
+ i
k
i
ni
k
xxδ
*)(
lim
i
k
i
k
xx =
∞→
即故由序列收敛的等价性定理，知
*)(
lim xx
k
k
rr
=
∞→
对任意的都成立。
)0(
x
r
证毕
Remark：当或时，简单迭代法与相应的Gauss-Seidel迭代法同时关于任意初始向量收敛。
1<
∞
B 1
1
<B
2004-11-10 32
§6.3 几种常见的迭代法一.Jacobi迭代法
1.迭代格式设有n 阶方程组
=+++
=+++
=+++
nnnnnn
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
L
L
L
L
2211
22222121
11212111
其中系数矩阵非奇异，且，i=1,2，……，n0≠
ii
a
+=
+=
+=
)(
1
)(
1
)(
1
11,2211
22323121
22
2
11313212
11
1
nnnnnn
nn
n
nn
nn
bxaxaxa
a
x
bxaxaxa
a
x
bxaxaxa
a
x
L
L
L
L
将上式变形为
2004-11-10 33
Jacobi迭代法的迭代格式（续）
建立迭代格式
+=
+=
+=
+
+
+
)(
1
)(
1
)(
1
)(
11,
)(
22
)(
11
)1(
2
)(
2
)(
323
)(
121
22
)1(
2
1
)(
1
)(
313
)(
212
11
)1(
1
n
k
nnn
k
n
k
n
nn
k
n
k
nn
kkk
k
nn
kkk
bxaxaxa
a
x
bxaxaxa
a
x
bxaxaxa
a
x
L
L
L
L
上面的迭代式称为雅可比（Jacobi）迭代格式。
用矩阵形式来表示方程组的迭代法设det(A),且
0≠
0≠
ii
a
+
+
=
00000
00
00
0
0
0
00
00
00000
000
00
00
000
223
11312
21
3231
21
22
11
21
22221
11211
MOOOM
MLO
L
L
LL
OMMM
O
OO
OO
O
L
MOMM
L
L
n
n
nn
nnnnnn
n
n
aa
aaa
aa
aa
a
a
a
a
aaa
aaa
aaa
2004-11-10 34
Jacobi迭代法的迭代格式（续）
bxULD
r
r
=++ )(
记A=D+L+U
xULbxD
r
r
r
)( +?=
bxA
r
r
=
则
bDxULDx
r
rr
11
)(
++?=
雅可比迭代式成为：
bDxULDx
kk
r
rr
1)(1)1(
)(
+
++?=
)(
1
ULDB
J
+?=
bDg
r
r
1
1
=
令
1
)()1(
gxBx
k
J
k
rrr
+=
+
则得
2004-11-10 35
a.充要条件：Jacobi方法关于任意初始向量都收敛的充要条件是
)0(
x
r
1)( <
J
Bρ
2.收敛条件
b.充分条件：
（II）设系数矩阵严格对角占优，
nnij
aA
×
= )(
则Jacobi迭代法关于任意初始向量收敛
)0(
x
r
（I）若则Jacobi方法关于任意初始向量都收敛。
1<
J
B
)0(
x
r
（按行）
,（i=1,2,…,n）
∑
≠=
>
n
jij
ijii
aa
,1
（j=1,2,…,n）(按列)
∑
≠=
>
n
jii
ijjj
aa
,1
即或
2004-11-10 36
Jacobi迭代法的收敛条件（续）
由严格对角占优矩阵的定义有（按行）
i=1,2,……n1
1
,1,11
<==
∑∑∑
≠=≠==
n
ijj
n
ijj
ij
iiii
ij
n
j
ij
a
aa
a
b
即
1<
∞
J
B
证明：
j=1,2,…，n
1
1
,1,11
<==
∑∑∑
≠=≠==
n
jii
n
jii
ij
jjjj
ij
n
i
ij
a
aa
a
b
即
1
1
<
J
B
因此Jacobi迭代法对任意初始向量 收敛。
)0(
x
r
证毕定义：设，若
∑
≠=
≥
n
ijj
ijii
aa
,1
（i=1,2,……n）
nn
ij
RaA
×
∈= )(
且其中至少有一个严格不等式成立，则称A为按行弱对角占优。
2004-11-10 37
Jacobi迭代法的收敛条件（续）
则称A为可约矩阵。
以n阶单位矩阵I
n
的n个列向量为列构成
n阶矩阵称为置换矩阵,是
1，2，……,n的一个排列。
n
eee
r
L
rr
,,,
21
n
jjj,,,
21
L
),,,(
21 jnjj
eeep
r
L
rr
=
=
22
1211
0 A
AA
PAP
T
若可找到置换矩阵P，使A呈
22
1211
0 A
AA
换化为，其中是方阵，则称A为不可约矩阵。
2211
,AA
定义：设，若A不能经过行置换与相应的列置
nn
RA
×
∈
（III）设A为不可约对角占优矩阵，则Jacobi迭代法关于任意初始向量收敛。
)0(
x
r
2004-11-10 38
二.与Jacobi迭代法相应的Gauss-Seidel法
1.迭代格式其迭代式为
+=
+=
+=
+
+++
++
+
)(
1
)(
1
)(
1
)1(
11.
)1(
22
)1(
11
)1(
2
)(
2
)(
323
)1(
121
22
)1(
2
1
)(
1
)(
313
)(
212
11
)1(
1
n
k
nnn
k
n
k
n
nn
k
n
k
nn
kkk
k
nn
kkk
bxaxaxa
a
x
bxaxaxa
a
x
bxaxaxa
a
x
L
L
L
L
矩阵形式为
bxULD
v
v
=++ )(
bxA
r
r
=
xUbxLD
v
r
v
=+ )(
)()1()1( kkk
xUxLbxD
rr
r
r
=
++
)()1(
)(
kk
xUbxLD
r
r
r
=+
+
2004-11-10 39
迭代格式（续）
因,故存在，于是Gauss-Seidel
迭代式为
0≠
ii
a
1
)(
+LD
bLDxULDx
kk
v
v
r
1)(1)1(
)()(
+
+++?=
2
)()1(
gxGx
k
s
k
rrr
+=
+
则得
ULDG
S
1
)(
+?=
2
g
r
bLD
v
1
)(
+=
令
s
G
称为Gauss-Seidel迭代法的迭代矩阵。
Remark1:今后若无特殊说明，凡谈到Gauss-Seidel
迭代法（简称G-S迭代法），均指与Jacobi迭代法相应的Gauss-Seidel迭代法。
Remark2:并不是任何时候Gauss-Seidel迭代法都比
Jacobi迭代法收敛快。甚至也有Jacobi法收敛而
Gauss-Seidel迭代法不收敛的例子。
2004-11-10 40
2.收敛条件
a.充要条件：
收敛的充要条件是：1)( <
s
Bρ
)0(
x
r
G-S法关于任意初始向量都
b.充分条件：
1<
s
B
)0(
x
r
①若则G-S方法关于任意初始向量都收敛。
关于任意初始向量收敛。
②设系数矩阵严格对角占优，则G-S方法
)(
ij
aA=
)0(
x
r
③设A为不可均弱对角占优矩阵，则G-S迭代法关于任意初始向量收敛。
)0(
x
r
④设A为对称正定矩阵，则G-S迭代法关于任意初始向量收敛。
)0(
x
r
2004-11-10 41
三.逐次超松弛迭代法
（SOR法-Successive Over Relaxation）
1.迭代公式将G-S迭代格式
∑
=
+
=
1
1
)1(
(
1
i
j
iji
ii
k
i
ab
a
x）
∑
+=
+
n
ij
k
jij
k
j
xax
1
)()1(
ni,...,2,1=
改写为：
∑∑
=
+
=
+
+=
n
ij
k
jij
k
j
i
j
iji
ii
k
i
k
i
xaxab
a
xx )(
1
)()1(
1
1
)(
)1(
并记
∑∑
=
+
=
+
=
n
ij
k
jij
k
j
i
j
iji
k
i
xaxabr
)()1(
1
1
)1(
ni,...,2,1=
ni,...2,1=
一般地，残量。0
)1(
≠
+k
i
r
2004-11-10 42
逐次超松弛迭代法的迭代格式（续）
∑
=
+
+=
1
1
)(
)1(
(
i
j
iji
ii
k
i
k
i
ab
a
xx
ω
）
∑
=
+
n
ij
k
jij
k
j
xax
)()1(
ni,...2,1=
+?=
+ )()1(
)1(
k
i
k
i
xx ω
∑
=
1
1
i
j
iji
ii
ab
a
（
ω
）
∑
+=
+
n
ij
k
jij
k
j
xax
1
)()1(
矩阵形式:
将迭代格式改写
)()1(
1
)(
1
1
)1()()1(
∑∑
+=
=
++
+?=
n
ij
k
jij
i
j
k
jiji
k
iii
k
iii
xaxabxaxa ωω
由矩阵分解成 A＝D＋L＋U
这就是逐次超松驰迭代法（SOR方法)，称为松驰因子。
ω
SOR方法的计算公式也常写为：
Remark：可见，SOR方法的得到的可以看成是G-S方法的结果与的加权平均。
)1( +k
i
x
)(k
i
x
2004-11-10 43
逐次超松弛迭代法的迭代格式（续）
则相应的矩阵形式为
)()1(
)()1()()1( kkkk
xUxLbxDxD
vvv
r
+?=
++
ωω
v
bxUDxLD
kk
v
r
ωωωω +=+
+ )()1(
))1(()(
v
即
bLDxUDLDx
kk
vv
1)(1)1(
)())1(()(
+
+++= ωωωωω
v
故
gxLx
kk
vvv
+=
+ )()1(
ω
其中
))1(()(
1
UDLDL ωωω
ω
+=
故SOR方法的矩阵形式为
bLDg
r
v
1
)(
+= ωω
ω
L
称为SOR方法的迭代矩阵。
2004-11-10 44
2.SOR方法的收敛性
A.充要条件：SOR法关于任意初始向量都收敛的充要条件是。
1)( <
ω
ρ L
)0(
x
r
SOR方法收敛
Q
证：
B.必要条件：设解的SOR方法关于任意初始向量都收敛，则0 < ω<2。
)0(det,≠= AbxA
v
v
)0(
x
r
设的特征值为ω
L
n
λλλ,...,,
21
1)( <∴
ω
ρ L
n
λλλ,..
21
)det(
ω
L=
由的特征多项式的模与系数的关系知：ω
L
n
λλλ L
21
=)det(
ω
L
)(
ω
ρ L≤
即
2004-11-10 45
SOR方法的收敛性（续）
即
1)()det(
1
<≤
ωω
ρ LL
n
而
))1det(())det((
1
UDLD ωωω+=
)det(
ω
L
))1det(()][det((
1
UDLD ωωω+=
[ ] ))1det((det
1
DD ω=
nn
n
nn
aaaaa,..)1()...(
11
1
2211
ω=
n
)1( ω?=
11)det(
1
<?= ω
ω
n
L
故0＜ω＜2。
即证毕
2004-11-10 46
SOR方法的收敛性（续）
yyL
rr
λ
ω
=
0),...,,(
21
≠=
n
yyyy
r
设为对应的的特征向量，即
λy
r
ω
L
C.充分条件：若A对称正定，且0 <ω<2，则SOR法关于任意初始向量收敛（此时，0 <ω<2对称正定为充要条件）。
)0(
x
r
证：
yyUDLD
rr
λωωω =+
))1(()(
1
即
yLDyUD
rr
)())1(( ωλωω +=
在复空间中考虑内积
n
C )(是复数λ
),)((,))1((( yyLDyyUD
rrrr
ωλωω +=）
即
),(),(
),(),(),(
yyLyyD
yyUyyDyyD
rrrr
rrrrrr
ω
ωω
λ
+
=
2004-11-10 47
SOR方法的收敛性（续）
又记
βα iyyL +=),(
rr
因为
∑
=
>==
n
i
iii
yayyD
1
2
0),( σ
rr
),( yyU
rr
yUy
T
rr
= yLy
TT
rr
= yyL
T
rr
)(=
),( yLy
rr
= ),( yyL
rr
= βα i?=
),(0 yyA
rr
<
),)(( yyULD
rr
++=
所以
)()( βαβασ ii?+++= ασ 2+=
ωβωασ
ωβωαωσσ
i
i
++
+
=
)(
)(
)(
)(
βαωσ
βαωωσσ
λ
i
i
++
=
2004-11-10 48
SOR方法的收敛性（续）
=
2
λ
222
222
)(
)(
βωωασ
βωωαωσσ
++
+
当0＜＜2时，则有
ω
22
)()( ωασαωωσσ +
[ ]σωαωσασω += )(24
0)2)(2( <?+= ωασσω
即，故SOR方法收敛。1<λ
证毕
2004-11-10 49
SOR方法的收敛性（续）
Remark：能使SOR方法收敛最快的松弛因子叫做最佳松弛因子，记为ω
opt
。
对某些特殊类型的矩阵，可以建立SOR方法最佳松弛因子理论。例如，对于具有对称正定，或严格对角占优或弱对角占优且不可约等性质的矩阵A的线性方程组，可以建立最佳松弛因子其中ρ(J)为解Ax＝b的雅可比迭代法的迭代矩阵的谱半径。一般情况下确定ω
opt
并不容易，实际计算时一般都是根据试算的情况确定ω
opt
的一个近似值。
2
))((11
2
J
opt
ρ
ω
+
=
2004-11-10 50
四.数值算例取，用迭代方法求解如下的方程组，使得。
T
x )1,1,1(
0
=
v
5)()1(
10
∞
+
≤?
kk
xx
vv
=+?
=?+
=+
244
3043
2434
32
321
21
xx
xxx
xx
求解
2004-11-10 51
Remark：使用迭代法求解线代数方程组需注意的问题
1.迭代法的收敛性与初始向量的选取无关。但初始向量的选取对迭代的工作量有重大影响。
2.在使用实用误差估计式停止迭代时，
ε<?
+ )()1( kk
xx
要选的恰当。
ε
3.在迭代格式中，若是病态阵，
fxBx
kk
r
rr
+=
+ )()1(
BI?
那么一般迭代法得不到好的结果。
4.如果,则用此判断法比用方便。
1<=qB 1)( <Bρ
5.对某些方程组，有时可适当作些变形，以使得迭代法收敛。
