2004-11-10 1
第六章解线性代数方程组的迭代法
§6.1向量和矩阵序列的极限
§6.2 迭代法的基本理论
§6.3 几种常见的迭代法
2004-11-10 2
§6.1向量和矩阵序列的极限一.极限的概念
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
2.矩阵序列收敛设是中的矩阵序列,
若有,使,则称收敛于,记为
{ }
)(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.2迭代法的基本理论迭代法的一般格式为
),,,(
)()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


=
=
n
ij
iji

证明:

+=
++=
++
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

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

)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.对某些方程组,有时可适当作些变形,以使得迭代法收敛。