第二章、解线性方程组的迭代法
直接法, 经过有限次运算后可求得方程组精确解的方
法 (不计舍入误差 !)
迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。（一般有限步内得不到精确解）
直接法比较适用于中小型方程组。对高阶方程组，
既使系数矩阵是稀疏的，但在运算中很难保持稀疏性，
因而有存储量大，程序复杂等不足。
迭代法则能保持矩阵的稀疏性，具有计算简单，编
制程序容易的优点，并在许多情况下收敛较快。故能有
效地解一些高阶方程组。
§ 1.迭代法概述
迭代法的基本思想是构造一串收敛到解的序列，即建立一种
从已有近似解计算新的近似解的规则。由不同的计算规则得到不
同的迭代法，本章介绍单步定常线性迭代法。
1
( 0 )
( 1 ) ( )
( ) ( )
( ) (,,)
,
( k= 0,1,2,)
{}
T
ij n n n
n
n
kk
kk
Ax b
A a b b b
x M x g
M n g R
xR
x M x g
x k x
Ax b
?
?
?
??
??
?
?
??
?
L
L
对线性方程组
其中 非奇异矩阵，
构造其形如
的同解方程组，其中 为 阶方阵,。
任取初始向量 代入迭代公式
产生向量序列,当 充分大时，以 作为
方程组 的近似解，这就是求解线
M
性方程组
的单步定常线性迭代法。 称为迭代矩阵。
()
()
()
()
()
(
{ }
l im 0
{}
l im
{ }
l im
k n n
k
k
k
k
k
n k n
i
k
x R x R
xx
xx
xx
R x R x
x
??
??
??
?
??
?
?
定义：设 为 中的向量序列，,如果
其中 为向量范数，则称序列 收敛于,记为
定理,中的向量序列 收敛于 中的向量 当且仅当
)
( ) ( ) ( ) ( )
1 2 1 2
( ) ( )
( ) ( ) ( )
1
()
( 1,2,,)
(,,,),(,,,)
{ } l im 0
1 0 m a x
l im = 0 ( 1,2,,)
k
i
k k k k T T
nn
kk
k
k k k
i i j j
jn
k
ii
k
x i n
x x x x x x x x
x x x x
i n x x x x x x
x x i n
??
?
??
??
??
??
??
? ? ? ? ? ? ? ?
??
L
LL
L
其中 。
证：由定义,收敛于 即
而对任意,有
由极限存在准则得
即
()
l im ( 1,2,,)
k
ii
k
x x i n
??
?? L
()
()
()
()
( ) ( )
()
{ }
l i m 0
{}
l i m
{ } ( ) ( 1,2,),(
{}
k
k
k
k
k
k
kk
ij ij
k
A n A n
AA
AA
AA
A a k A a n
AA
??
??
??
?
?
? ? ?L
定义：设 为 阶方阵序列,为 阶方阵，如果
其中 为矩阵范数，则称序列 收敛于矩阵,记为
定理：设 ) 均为 阶方阵，
则矩阵序列 收敛于矩阵 的充
()
( 1 ) ( ) ( )
( 1 ) ( )
l i m (,1,2,,)
{ },
l i m l i m [ ]
k
ij ij
k
k k k
kk
kk
a a i j n
x Mx g x x
x x Mx g Mx g
xA
??
?
?
? ? ? ?
??
??
? ? ? ? ?
L
要条件为
证明略。
定理表明，向量序列和矩阵序列的收敛可以归结为对应
分量或对应元素序列的收敛。
若按 产生的向量序列 收敛于向量
则有
即 是方程组 xb ? 的解。
§ 2.雅可比 (Jacobi)迭代法
1 1 1 1 2 2 1 n 1
2 1 1 2 2 2 2 n 2
n 1 1 n 1 2 n n
0 ( 1,2,,),
n
n
nn
ii
in
a x a x a x b
a x a x a x b
a x a x a x b
a
? ? ? ??
?
? ? ? ??
?
?
?
? ? ? ?
?
??
L
L
LL
L
L若系数矩阵非奇异即 则有
1 1 2 2 1 3 3 1
1
2 2 1 1 2 3 3 2
2
n 1 1 2 2 3 3
nn
nn
n n n
n
gx b x b x b x
gx b x b x b x
x b x b x b x
? ? ? ? ?
? ? ? ? ?
? ? ? ? ? ?
L
L
LL
L
,(,,1,2,,),( 1,2,,),
ij i
ij i
ii ii
a b
b i j i j n g i n
aa
g
?
?
?
?
?
?
?
??
? ? ? ? ? ?LL其中
12 13 1 1 1 1
21 23 2 1 2 2
1 2 3 1
( 0 ) ( 1 ) 1 0 ( 1 )
( 2 ) ( )
( 1 )
0
0
0
,
{}
nn
nn
n n n nn n
k
k
b b b b g
b b b b g
Bg
b b b b g
x B x g
x x x B x g x
xx
x B x
?
?
?
?
? ? ? ?
? ? ? ?
? ? ? ?
??
? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ?
??
? ? ?
?
?
L
L
L L M
L
L
（ ） （ ）
若记
则方程组可简记为
选初值向量 代入,代入
，如此继续下去，就产生一个向量序列
满足
()
( 0,1,2,)
k
gk
J ac ob i
?? L
此过程所给出的迭代法称为 迭代法，又称简单
迭代法。
矩阵简化记法
1
1
1
100
010
001
0
0
0
21
221
112
21
221
112
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
??
?
?
?
??
?
?
bb
bb
bb
bb
bb
bb
nn
n
n
nn
n
n
B
AD I -
aaa
aaa
aaa
a
a
a
I
nn
1
nnn2n1
2n2221
1n1211
1
1
22
1
11
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
??
?
?
?
1
12
1 1 1 2 2 2
(,,,)
(,,,)
T
T
n
n n n
g g gg
bDb a b a b a ?
?
??
L
L
同样
收敛与解 1
*
**
n 0 1 2
{ }
B g
nn
k
J a c o b i B gxx
xx
xx
?
? ? ?
?
??
L
（ ） （ ）
（）
迭代,，，
若收敛,则
* 1 1
1 * 1
*
( ),,
I B x g B I D A g D b
D A x D b
A x b
??
??
? ? ? ? ?
??
??
即
故如果序列收敛,则收敛到解,B 称迭代矩阵,
1 2 3
1 2 3
1 2 3
1
10 2 72
10 2 83
5 42
1
00
10
1 0 0 10 1 2 0 0.1 0.2
1
0 1 0 0 0 1 10 2 0.1 0 0.2
10
0 0 1 1 1 5 0.2 0.2 0
1
00
5
x x x
J ac obi x x x
x x x
B I D A
?
? ? ??
?
? ? ? ?
?
?
? ? ? ?
?
??
??
??
??? ? ? ? ? ?
??
? ? ? ? ? ???
? ? ? ? ?
? ? ? ? ? ???
? ? ? ? ? ?????
? ? ? ? ? ?
??
??
??
例：用 迭代法求解
解：
1
( 0 ) ( 0 )
( 2 ) ( 1 ) ( 9 )
( 7.2,8.3,8.4)
( 0,0,0),( 7.2,8.3,8.4)
( 9.71,10.70,11.5 ) ( 10.9994,11.9994,12.999 2)
( 11,12,13 ),
T
TT
T
T
g D b
x Bx g
x Bx g x
x
?
??
? ? ? ?
? ? ? ?
?
L
(1)
取 代入迭代式，得x
精确解为
Jacobi迭代法的计算过程如下,
( 0 ) ( 0 ) ( 0 ) ( 0 )
1 1 2
( 0 )
1
( 0 )
( 0 )
1,( ),(,,),,(,,,),
,.
2,1.
3,1,2,,( ) /
4.,,5
5.,1,( 1,2,,),3
ij n n
n
i i ij j ii
j
ji
ii
A a b b b n x x x x
N
k
i n x b a x a
x x x
k N k k x x i n
?
?
?
?
? ? ?
?
? ? ?
??
? ? ? ? ?
?
LL
L
L
输入 维数
最大容许迭代次数
置
对
若 输出 停机；否则转 。
若 置 转 ；
否则，输出失败信息，停机。
( ) ( 1
,
kk
M x x
? ）
评价：公式简单，每迭代一次只需计算一次矩阵和向量
的乘法，不改变 的稀疏性，需两组工作单元，存 。
§ 3,高斯 — 塞德尔（ Gauss-Seidel)迭代法
( 1 ) ( )
( 1 ) ( ) ( ) ( )
1 12 2 13 3 1
1
( 1 ) ( ) ( ) ( )
2 21 1 23 3 2
2
( 0,1,2,)
kk
k k k k
nn
k k k k
nn
x B x g k
gx b x b x b x
gx b x b x b x
?
?
?
? ? ?
? ? ? ? ?
? ? ? ? ?
L
L
L
LL
迭代公式 用方程组表示为
( 1 ) ( ) ( ) ( )
1 1 2 2,1 1
( ) ( 1 )
k k k k
n n n n n n
n
kk
J ac obi
xx
gx b x b x b x
?
??
?
?
?
?
?
?
?
?
? ? ? ? ?
?
?
L
因此，在 迭代法的计算过程中，需同时保留两个
近似解向量 和 。若把迭代公式改写成
( 1 ) ( ) ( ) ( )
1 12 2 13 3 1
1
( 1 ) ( 1 ) ( ) ( )
2 21 1 23 3 2
2
( 1 ) ( 1 )
1 1 2
k k k k
nn
k k k k
nn
kk
n n n
gx b x b x b x
gx b x b x b x
x b x
?
??
??
? ? ? ? ?
? ? ? ? ?
??
L
L
LL
( 1 ) ( 1 )
2,1 1
( 0 ) ( )
,{ },
kk
n n n
n
k
n
xx
G auss Se ide l
J ac obi
gb x b x
??
??
?
?
?
?
?
?
?
? ? ?
?
?
?
L
这样，在整个计算过程中，只需用 个单元存储近似
解分量。而且通常认为，近似解可能比老近似解更接
近精确解，因此，可望这种迭代会更有效。
选取初始向量 用上式迭代产生近似解序列
这种方法叫 迭代法。
评价：与 相比，只需一组工作单元存放近似解。
° °
° °
° °
° °
° ° °
( 1 ) ( )
12 1
2,21
12
( 1 ) ( )
1
( 1 ) 1 ( ) 1
00
00
U
0
0
( )
1,( )
( ) ( )
kk
n
n
nn
kk
kk
L x U x g
L
I L x U x g
I L I L
x I L U x I L g
bb
bb
bb
?
?
?
? ? ?
? ? ?
????
????
????
??
????
????
?? ??
?? ??
? ? ?
? ? ?
? ? ? ?
L
MO
O
L
(k+1)
用矩阵表示为 x
其中,
移项可得
因为 故 存在，上式可改写为
° °
°
° °
1 2 1 3 1
21 2 3 2
3 1 3 2
1
1 2 1
11
1 1 1
( 1 ) 1 (
0 0 0 0
0 0
0 00
,
()
( )
n
n
nn
n n n n
kk
A
a a a
a aa
LUaa
a
a a a
L D L U D U
I L D D D L D D L
x I L U x
?
?
??
? ? ?
??
? ? ??? ??
?? ??
? ??
?? ??
?? ??????
?? ??
?
?? ??
?? ??
? ? ?
????
??
? ? ? ? ? ?
??
L L
L
OM M O O M
M M O O O
L L
如果用矩阵 来表示，记
则
由
°
)1
( 1 ) 1 ( ) 1
1
()
( ) ( )
( )
kk
I L g
x D L Ux D L b
M D L U Gau ss Se i de l
?
? ? ?
?
??
? ? ? ? ?
? ? ?式中矩阵 为 迭代法的迭代矩阵。
1 2 3
1 2 3
1 2 3
( 0 )
1 ( 0 ) ( 0 )
1 2 3 1
1 ( 1 ) ( 0 )
2 1 3 2
1
3
10 2 72
10 2 83
5 42
( 0,0,0),
11
( 2 ) 72 7.2 00 0
10 10
11
( 2 ) ( 7.2 00 0 83 ) 9.0 20 0
10 10
T
x x x
Gau ss Se i de l x x x
x x x
x
x x x b
x x x b
x
? ? ??
?
? ? ? ? ?
?
?
? ? ? ?
?
?
? ? ? ? ? ?
? ? ? ? ? ?
?
（）
（）
（）
例：用 迭代法求解
解：仍取 代入迭代式，得
( 1 ) ( 1 )
1 2 3
( 5 )
11
( ) 7.2 00 0 9.0 20 0 42 ) 11,64 40
55
( 10,99 89,11,99 93,12,99 96 )
( 11,12,13 ),
T
x x b
x
x
? ? ? ? ? ?
?
?
L
（
如此继续下去，
精确解为
G au se se ide l
J ac ob i
G au se se ide l J ac ob i
G au se se ide l
J ac ob i J ac ob i
G au se se ide l
J ac ob i
?
?
?
?
上例计算结果表明,迭代
法比 迭代法效果好。事实上，对有
些问题 迭代法确实比
迭代法收敛得快，但也有 迭
代比 迭代收敛得慢，甚至还有
迭代收敛,迭代发散的情形。
评价：与 相比，只需一组工作单
元存放近似解。
Gauss-Seidel迭代法的计算过程如下,
( 0 ) ( 0 ) ( 0 ) ( 0 )
1 1 2
( 0 )
1 1 1 11
2
1
( 0 )
11
1,( ),(,,),,(,,,),
,.
2,1.
3,( ) /
( ) / ( 2,,1 )
(
ij n n
n
jj
j
in
i i ij j ij j ii
j j i
nn
A a b b b n x x x x
N
k
x b a x a
x b a x a x a i n
x b a
?
?
?
? ? ?
? ? ?
?
??
? ? ? ? ?
??
?
??
LL
L
输入 维数
最大容许迭代次数
置
计算
1
1
( 0 )
( 0 )
)/
4.,,5
5.,1,( 1,2,,),3
n
nj j nn
j
ii
xa
x x x
k N k k x x i n
?
?
?
??
? ? ? ? ?
?
L
若 输出 停机；否则转 。
若 置 转 ；
否则，输出失败信息，停机。
§ 4.松弛法
( 1 ) ( ) ( 1 )
12
1
( 1 ) ( ) ( )
11
1
( 1 ) ( ) ( )
11
(,,,),
1
( )
T k k k
n
in
k k k
i ij j ij j i i
j j i
in
k k k
i ij j ij j i
j j iii
G auss Se ide l
x x x x x x x
G auss Se ide l
x b x b x g x
b a x a x x
a
??
?
?
? ? ?
?
?
? ? ?
?
? ? ? ? ? ? ?
?
? ? ? ? ?
? ? ? ?
??
??
L
为 迭代法加速。
记 其中 由
迭代公式得到。于是有
()
( 1 ) ( )
( 1,2,,)
k
kk
in
x G auss Se ide l k
x
x x x
?
?
??
? ? ?
L
可以把 看作 迭代的修正项，即第 次
近似解 以此项修正后得到新的近似解
( 1 ) ( )
( 1 )
1
( 1 ) ( )
11
( 1 ) ( )
(
kk
kk
i i i
in
k k k
i i ij j ij j
j j i
ii
x
x x x
x x x
x b a x a x
a
i
?
?
?
?
?
?
?
?
?
? ? ?
?
? ? ?
? ? ?
? ? ? ? ?
?
??
松弛法是将 乘上一个参数因子 作为修正项而
得到新的近似解，具体公式为
即
1,2,,)
11
1
n
A x b
G auss
Se ide l
? ? ?
?
?
? ? ?
?
L
按上式计算 的近似解序列的方法称为松弛法，
称为松弛因子。当 时称为低松弛； 是
迭代； 时称为超松弛法。
( 1 ) ( )
( ) 1 ( 1 ) 1 ( ) 1 ( )
( ) 1 ( 1 ) 1 ( ) 1
1 1 1 1
( 1 ) 1
( )
( 1 )
1,( )
( ) [ ( 1
kk
k k k k
k k k
k
x x x
x D L x D U x D b x
x D L x D U x D b
I D L I D L D L
x D L
?
?
? ? ? ?
? ? ?
??
?
? ? ? ?
? ? ? ?
? ? ?
??
? ? ?
? ? ? ? ?
? ? ? ? ?
? ? ? ?
? ? ?
－
松弛法迭代公式的矩阵表示：
因为 故（ ）与 存在，
有
( ) 1
1
) ] ( )
( ) [ ( 1 ) ]
,
k
D U x D L b
M D L D U
? ? ?
? ? ?
?
?
? ? ?
? ? ? ?
松弛法的迭代矩阵为
松弛因子的选取对收敛速度影响极大但目前尚无可
供实用的计算最佳松弛因子的方法。通常是根据系数矩
阵的性质及实际经验，通过试算来确定松弛因子。
( 0 )
12
1 2 3
23
1
( 1 ) ( 1 ) ( )
11
( 1 ) ( ) ( )
1 1 2
( 1 ) ( )
22
1.4,( 1,1,1 ),
21
2 0
2 1.8
( 1 ) ( )
0.4 0.7 ( 1 )
0.4
T
in
k k k k
i i i ij j ij j
j j i
ii
k k k
kk
x
xx
x x x
xx
x x b a x a x
a
x x x
xx
?
?
?
?
??
? ? ?
?
?
??
???
?
? ? ? ?
?
?
? ? ?
?
? ? ? ? ?
? ? ? ?
? ? ?
??
例：取 用超松弛法解方程组
解：由
( 1 ) ( )
13
( 1 ) ( ) ( 1 )
3 3 2
( 0 )
( 9 )
0.7 ( ) ( 0,1,2,)
0.4 0.7 ( 1.8 )
( 1,1,1 )
( 1.200,1.3996,1.6001 ) ( 1.2,1.4,1.6)
kk
k k k
T
TT
x x k
x x x
x
xx
?
??
?
?
? ? ?
?
?
? ? ? ?
?
??
??
L
将 代入上式开始迭代，
精确解
松弛法 计算过程如下,
( 0 ) ( 0 ) ( 0 ) ( 0 )
1 1 2
( 0 ) ( 0 )
1 1 1 1 11
2
1
( 0 ) ( 0 )
11
1,( ),(,,),,(,,,),
,.
2,1.
3,( 1 ) ( ) /
( 1 ) ( ) /
ij n n
n
jj
j
in
i i i ij j ij j ii
j j i
A a b b b n x x x x
N
k
x x b a x a
x x b a x a x a
??
??
??
?
?
? ? ?
? ? ?
?
? ? ? ?
? ? ? ? ?
?
??
LL输入 维数
最大容许迭代次数,参数
置
计算
1
( 0 )
1
( 0 )
( 0 )
( 2,,1 )
( 1 ) ( ) /
4.,,5
5.,1,( 1,2,,),3
n
n n n nj j nn
j
ii
in
x x b a x a
x x x
k N k k x x i n
??
?
?
?
??
? ? ? ?
??
? ? ? ? ?
?
L
L
若 输出 停机；否则转 。
若 置 转 ；
否则，输出失败信息，停机。
§ 5.迭代法的收敛条件
一、矩阵的谱半径
1
12
12
( 1,2,,)
( ) m a x { }
(,,,)
(,,,) ( 1,2,),( ) [ (
i
i
in
n
k
k k k k
n
A n i n A
A
A
A
A A A A
kA
?
??
? ? ?
? ? ? ? ?
??
?
?
?
??
L
L
L
LL
迭代法的收敛与迭代矩阵的特征值有关。
定义：设 为 阶方阵,为 的特
征值，称特征值的最大值为矩阵 的谱半径，记为
称为矩阵 的谱。
由特征值的定义知，矩阵 的谱是
因而 )]
k
A
,,
,( )
:,
,
( ),
,,,
ii
i i i i i i
ii
i
An
AA
Au
u u Au A u
uA
AA
An
?
?
??
?
??
?
?
?
? ? ?
?
?
定理设 为任意 阶方阵 为任意由向量范数诱导
出的矩阵范数则
证对 的任一特征值 及相应的特征向量 都有
因为 为非零向量于是有
由 的任意性即得 证毕
定理设 为任意 阶方阵则对任意正数 存在一种
矩阵
2
,( )
,,
( ) ( )
AA
n
A A A A A
??
??
? ? ?
?
??
范数 使得
证明略。
对任意 阶方阵一般不存在矩阵范数 使得
。但若 为对称矩阵，则有 。
l im 0 ( ) 1
l im 0
l im 0 ( )
0 ( ) [ ( ) ]
l im [ ( ) ] 0 ( ) 1
1
( ) 1
k
k
k
k
k
k
k k k
k
k
A n A A
A
A A A
A A A
AA
A
?
?
??
??
??
??
??
??
??
??
?
??
? ? ? ?
?
?
??
定理：设 为 阶方阵，则 的充要条件为 。
证：必要性,若
由矩阵收敛的定义知 又因
由极限存在的准则，有 ＝ 所以 。
充分性。若,取
()
0,
2
1 ( )
( ) 1
2
,l im l im 0 l im 0.
kk
k k k
k k k
A
A
AA
A A A A A
?
?
??
? ? ? ? ? ?
?
?
?
? ? ? ?
? ? ? ? ? ?
由上一定理
知，存在一种矩阵范数,使得
而
二、迭代法的收敛条件
( 0 )
( 1 ) ( )
()
* ( ) *
* * *
()
( 0,1,2,)
{ } ( ) 1,
,,,l im
kk
k
k
k
k
xg
x M x g k
xM
n x x x
x x M x g
x
?
?
??
? ? ?
?
?
??
L
定理：对任意初始向量 和右端项,由迭代格式
产生的向量序列 收敛的充要条件是
证必要性 设存在 维向量 使得
则 满足
由迭代公式有
* ( 1 ) *
( 1 ) * 2 ( 2 ) * ( 0 ) *
( 0 ) * ( ) *
( 0 )
( ) ( ) ( )
l im ( ) l im ( ) 0
,l im 0
( ) 1,
k
k k k
kk
kk
k
k
x M x g M x g
M x x M x x M x x
M x x x x
x n M
M?
?
??
? ? ? ?
??
? ? ? ? ?
? ? ? ? ? ?
? ? ? ?
?
??
于是有
因为 为任意 维向量因此上式成立必须
由上一定理
* * *
( ) * ( 1 ) * ( 0 ) *
( 0 )
( ) *
, ( ) 1,1,
0,,
,,
l i m 0
( ) ( )
,,
l i m ( ) l i m
k
k
k k k
k
kk
MM
I M n g I M x g
x x M x g
M
x x M x x M x x
x
x x M
??
??
?
? ? ? ?
??
? ? ? ?
??
?
? ? ? ? ?
??
充分性若 则 不是 的特征值因而有
于是对任意 维向量 方程组
有唯一解记为 即
并且
又因为
所以对任意初始向量 都有
( 0 ) *
( 1 ) ( ) ( )
( 0 )
( 1 ) ( )
()
( ) = 0
{ },
1 1,
( 0,1,2,)
{ },
k
k k k
kk
k
xx
x M x g x
x g M
x M x g k
x
?
?
?
??
?
? ? ? L
即由迭代公式 产生的向量序列 收敛
推论 对任意初始向量 和右端项,若 由迭代
格式
产生的向量序列 收敛
12
12
1
1
1 1 2 2
2 0 2
,,,
d e t ( ) [ ( )]
d e t ( ) 1
d e t ( ) ( ) ( 1 )
1
( )
( 1
n
n
n
nn
M
MM
M
M D L D U
DL
a a a
?
? ? ?
? ? ? ?
? ? ?
?
?
?
?
??
??
?
? ? ? ?
??
?
L
L
L
推论 松弛法收敛的必要条件是 。
证：设松弛法的迭代矩阵 由特征值 。
因为
由定理，松弛法收敛必有
又因为
1 1 2 2
) ( 1 )
d e t ( ) ( 1 ) 1 0 2
n
nn
n
D U a a a
M
??
??
? ? ?
? ? ? ? ? ? ?
L
。
迭代法收敛与否只决定于迭代矩阵的谱半径，与初始向
量及右端项无关。对同一方程组，由于不同的迭代法迭代
矩阵不同，可能出现有的方法收敛，有的方法发散的情形。
1 2 3
1 2 3
1 2 3
2 2 1
2
2 2 3
1
1 2 2 1 0 0
1 1 1 0 1 0
2 2 1 0 0 1
0 0 0
1 0 0
2 2 0
x x x
x x x
x x x
AD
L
? ? ??
?
? ? ?
?
?
? ? ?
?
?? ? ? ?
? ? ? ?
??
? ? ? ?
? ? ? ?
? ? ? ?
??
??
??
?
? ??
??
例：对方程组
讨论Jac obi 迭代法与Gau ss- Sei del 迭代法的收敛性。
解：求迭代矩阵判别其谱半径是否小于 。
0 2 2
0 0 1
0 0 0
U
???
??
??
? ? ?
? ? ?
??
1
3
1 2 3
Ja c ob i
0 2 2
1 0 1
2 2 0
22
1 1 0
22
0,( ) 0 1,
Ja c ob i
B I D A
IB
B
?
? ? ?
?
? ? ? ?
?
???
??
? ? ? ? ?
??
????
??
?
? ? ? ?
? ? ? ? ?
迭代法的迭代矩阵为
其特征方程为
因此有 于是
所以 迭代法收敛。
1
1
2
1
G a uss- S e i de l
1 0 0 1 0 0
1 1 0 ( ) 1 1 0
2 2 1 0 2 1
1 0 0 0 2 2 0 2 2
( ) 1 1 0 0 0 1 0 2 3
0 2 1 0 0 0 0 0 2
22
0 2 3 ( 2 ) 0
0 0 2
0,
D L D L
M D L U
IM
?
? ? ? ?
?
?
?
?
? ? ? ?
? ? ? ?
? ? ? ? ? ?
? ? ? ?
? ? ? ??
? ? ? ?
??? ? ? ? ? ?
? ? ? ? ? ?
? ? ? ? ? ? ?
? ? ? ? ? ?
? ? ? ? ? ??
? ? ? ? ? ?
?
? ? ? ? ? ?
?
?
迭代，由
特征方程
特征值为
23
2,( ) 2 1,M? ? ?? ? ? ?故 所以迭代发散。
0 2
1
12
1,
1,1
B
M
?
?
?
?
??
?
?
?
上例说明了 确实只是松弛法收敛的
必要条件，而非充要条件，因为Gau ss- Sei del
迭代记为 的情形。
判断定理虽然给出了判别迭代收敛的充要条
件，但要求逆矩阵和特征值。推论 与 仅分别
给出了收敛的充分与必要条件，许多情形下不
能起作用。如上例，两个方法均有
由推论 无法判别收敛性。
对一些特殊的系数矩阵可给出几个常用的判
别收敛条件
1
11 12
11 22
22
( ) ( 1,2,,)
,
0
1 1 0
1 1
n
ij ii ij
j
ji
n A a a a i n
iA
iA
A
AA
A A A A
A
A
?
?
? ? ?
??
?
??
??
?
?
L定义：若 阶方阵 满足
且至少有一个 值，使上式中不等号严格成立，则称 为弱
对角占优阵。若对所有，上式不等号均严格成立，则称
为严格对角占优阵。
定义：如果矩阵 不能通过行的互换和相应的列互换成
为形式 其中, 为方阵，则称 为不可约。
例：
13
2 1 0
0 0 1 1
0 1 2 0 1 1
PI T
P A P
?
? ? ? ?
? ? ? ?
???? ?
? ? ? ?
? ? ? ?
? ? ? ?
,
1.
Ja c ob i G a uss- S e ide l
2,0 1,
3.
02
10 1 2 2 1 0
1 10 2 1 2 1
1 1 5 0 1 2
A x b
A
A
A
AB
A
?
?
?
??
??
? ? ?? ? ? ?
? ? ? ?
? ? ? ? ? ?
? ? ? ?
? ? ? ?? ? ?
? ? ? ?
设有线性方程组 下列结论成立：
若 为严格对角占优阵或不可约弱对角占优阵，则
迭代法和 迭代法均收敛。
若 为严格对角占优阵,则松弛法收敛。
若 为对称正定阵，则松弛法收敛的充要条件为
。
上两例中：
为严格对角占优
B
?
阵，故Ja co bi 与Ga us s- Se id el 迭
代均收敛。 为非严格对角占优阵，但为对称正定
阵,=1,4 故松弛法收敛。
-1
11
1
22
11
,1
22
11
1
22
3 ( 0 2)
1
11
0
22
11
- 0
22
11
0
22
Ax b A
AA
A
B I D A
?
??
??
??
??
??
??
??
??
??
??
??
??
??
?
?
?
? ? ? ?
?
?
?
??
?
?
例,讨论用三种迭代法求解的收敛性。
解：因 为对称且其各阶主子式皆大于零，故 为对称正定矩
阵。由判别条件,G aus s-S eid el迭 代法与松弛法
均收敛。 不是弱对角占优阵，故不能用条件 判断。
Jacobi 迭代法的迭代矩阵为
?
?
?
?
?
?
?
?
3
2
1 2 3
11
22
1 1 3 1
2 2 4 4
11
22
1
( ) ( 1 ) 0
2
1
,1,( ) 1
2
IB
B
Jaco b i
?
? ? ? ?
?
??
? ? ? ?
? ? ? ? ?
? ? ? ?
? ? ? ? ?
?
其特征方程
得 因而
迭代法不收敛。
3 10
,
94
10 10
00
33
,
9 15
00
42
30 15
( ),( )
22
Ax b A
J ac obi Gaus s Se i de l
BM
BM??
???
??
??
?
??
?
? ? ? ?
?
? ? ? ?
??? ? ? ?
? ? ? ?
?
? ? ? ?
? ? ? ?
??
改变方程组中方程的次序，即将系数矩阵作行
交换，会改变迭代法的收敛性。
例：
与 迭代的迭代矩阵分别为
谱半径分别是 。均不收敛。
''
'
' ' '
,
3 1 0 9 4
9 4 3 1 0
A x b
A x b
AA
A A x b
J a c o b i G a u ss S e id e l
?
?
??? ? ? ?
? ? ?
? ? ? ?
??
? ? ? ?
?
?
若交换方程的次序，得 的同解方程组
为严格对角占优阵，因而对方程组 用
与 迭代求解均收敛。
三、误差估计
? ?
( 1 ) ( )
( ) *
( ) * ( 1 ) ( 0 )
1*
*1
( ) * ( 1 ) * ( 0 ) *
,1,
,
1
( ) 1,0,
)
)
( ) ( )
kk
k
k
k
k k k
x Mx g M
xx
M
x x x x
M
M M I M
I M x Mx g x
x I M g
x x M x x M x x
?
?
?
?
?
? ? ?
? ? ?
?
? ? ? ?
? ? ?
??
? ? ? ? ?
定理：设有迭代格式 若
收敛于 则有误差估计式
证：因 故 于是
( 存在，方程组 有唯一解,
且 ( 。从而有
( 0 ) 1
1 ( 0 )
1 ( 0 ) 1
[ ) ]
) [ ) ]
) [ ]
k
k
k
M x I M g
M I M I M x g
M I M x x
?
?
?
? ? ?
? ? ? ?
? ? ?
（）
(
((
(
( ) * 1 ( 0 ) 1
1
11
11
1
1
( ) *
)
) )
) )
) )
)
1
)
1
1
k
k
k
k
x x M I M x x
I M I M I
I M I M I M
I M I M I M
I M I M
IM
M
M
xx
?
?
??
??
?
?
? ? ? ?
? ? ?
? ? ? ? ?
? ? ? ?
? ? ?
??
?
??
?
（）
取范数 (
又因为 ( (
((
取范数 ( (
(
移项得 (
代入得
( 1 ) ( 0 )
xx
M
? 。
( ) * ( 1 ) ( 0 )
( 1 ) ( 0 )
( 0 ) ( 1 )
4(
1
:
( 1 )
ln
ln
0 0.1 0.2 0 7.2
0.1 0 0.2,0,8.3
0.2 0.2 0 0 8.4
10,0.4,
k
k
M
x x x x
M
k
M
xx
k
M
M x x
Mx
?
?
?
?
? ? ?
?
?
?
?
? ? ? ? ? ?
? ? ? ? ? ?
? ? ?
? ? ? ? ? ?
? ? ? ? ? ?
? ? ? ? ? ?
??
－
由误差估计式
根据事先给定的精度,可估计出迭代的次数
例：若
则有
1 ) ( 0 )
8.4
12.93 2,13
x
k
?
??
?? 即需要迭代 次才能满足精度。
? ?
( 1 ) ( )
( ) *
( ) * ( ) ( 1 )
( ) * ( 1 ) * ( 1 ) 1
1 ( 1 ) ( 1 ) 1 ( 1 ) ( )
( ) * 1 ( 1 )
,1,
,
1
( ) [ ) ]
) [ ] ) ( )
)
kk
k
k k k
k k k
k k k k
kk
x Mx g M
xx
M
x x x x
M
x x M x x M x I M g
M I M x Mx g M I M x x
x x M I M x
?
?
? ? ?
? ? ? ? ?
??
? ? ?
? ? ?
?
? ? ? ? ? ?
? ? ? ? ? ? ?
? ? ? ? ?
定理：设有迭代格式 若
收敛于 则有误差估计式
证：因 (
((
(
()
( ) ( 1 )
( ) ( 1 )
,
1
1
k
kk
kk
x
M
xx
M
M x x ?
?
?
??
?
??当 不太接近 时，可用 作为停机准则。
直接法, 经过有限次运算后可求得方程组精确解的方
法 (不计舍入误差 !)
迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。（一般有限步内得不到精确解）
直接法比较适用于中小型方程组。对高阶方程组，
既使系数矩阵是稀疏的，但在运算中很难保持稀疏性，
因而有存储量大，程序复杂等不足。
迭代法则能保持矩阵的稀疏性，具有计算简单，编
制程序容易的优点，并在许多情况下收敛较快。故能有
效地解一些高阶方程组。
§ 1.迭代法概述
迭代法的基本思想是构造一串收敛到解的序列，即建立一种
从已有近似解计算新的近似解的规则。由不同的计算规则得到不
同的迭代法，本章介绍单步定常线性迭代法。
1
( 0 )
( 1 ) ( )
( ) ( )
( ) (,,)
,
( k= 0,1,2,)
{}
T
ij n n n
n
n
kk
kk
Ax b
A a b b b
x M x g
M n g R
xR
x M x g
x k x
Ax b
?
?
?
??
??
?
?
??
?
L
L
对线性方程组
其中 非奇异矩阵，
构造其形如
的同解方程组，其中 为 阶方阵,。
任取初始向量 代入迭代公式
产生向量序列,当 充分大时，以 作为
方程组 的近似解，这就是求解线
M
性方程组
的单步定常线性迭代法。 称为迭代矩阵。
()
()
()
()
()
(
{ }
l im 0
{}
l im
{ }
l im
k n n
k
k
k
k
k
n k n
i
k
x R x R
xx
xx
xx
R x R x
x
??
??
??
?
??
?
?
定义：设 为 中的向量序列，,如果
其中 为向量范数，则称序列 收敛于,记为
定理,中的向量序列 收敛于 中的向量 当且仅当
)
( ) ( ) ( ) ( )
1 2 1 2
( ) ( )
( ) ( ) ( )
1
()
( 1,2,,)
(,,,),(,,,)
{ } l im 0
1 0 m a x
l im = 0 ( 1,2,,)
k
i
k k k k T T
nn
kk
k
k k k
i i j j
jn
k
ii
k
x i n
x x x x x x x x
x x x x
i n x x x x x x
x x i n
??
?
??
??
??
??
??
? ? ? ? ? ? ? ?
??
L
LL
L
其中 。
证：由定义,收敛于 即
而对任意,有
由极限存在准则得
即
()
l im ( 1,2,,)
k
ii
k
x x i n
??
?? L
()
()
()
()
( ) ( )
()
{ }
l i m 0
{}
l i m
{ } ( ) ( 1,2,),(
{}
k
k
k
k
k
k
kk
ij ij
k
A n A n
AA
AA
AA
A a k A a n
AA
??
??
??
?
?
? ? ?L
定义：设 为 阶方阵序列,为 阶方阵，如果
其中 为矩阵范数，则称序列 收敛于矩阵,记为
定理：设 ) 均为 阶方阵，
则矩阵序列 收敛于矩阵 的充
()
( 1 ) ( ) ( )
( 1 ) ( )
l i m (,1,2,,)
{ },
l i m l i m [ ]
k
ij ij
k
k k k
kk
kk
a a i j n
x Mx g x x
x x Mx g Mx g
xA
??
?
?
? ? ? ?
??
??
? ? ? ? ?
L
要条件为
证明略。
定理表明，向量序列和矩阵序列的收敛可以归结为对应
分量或对应元素序列的收敛。
若按 产生的向量序列 收敛于向量
则有
即 是方程组 xb ? 的解。
§ 2.雅可比 (Jacobi)迭代法
1 1 1 1 2 2 1 n 1
2 1 1 2 2 2 2 n 2
n 1 1 n 1 2 n n
0 ( 1,2,,),
n
n
nn
ii
in
a x a x a x b
a x a x a x b
a x a x a x b
a
? ? ? ??
?
? ? ? ??
?
?
?
? ? ? ?
?
??
L
L
LL
L
L若系数矩阵非奇异即 则有
1 1 2 2 1 3 3 1
1
2 2 1 1 2 3 3 2
2
n 1 1 2 2 3 3
nn
nn
n n n
n
gx b x b x b x
gx b x b x b x
x b x b x b x
? ? ? ? ?
? ? ? ? ?
? ? ? ? ? ?
L
L
LL
L
,(,,1,2,,),( 1,2,,),
ij i
ij i
ii ii
a b
b i j i j n g i n
aa
g
?
?
?
?
?
?
?
??
? ? ? ? ? ?LL其中
12 13 1 1 1 1
21 23 2 1 2 2
1 2 3 1
( 0 ) ( 1 ) 1 0 ( 1 )
( 2 ) ( )
( 1 )
0
0
0
,
{}
nn
nn
n n n nn n
k
k
b b b b g
b b b b g
Bg
b b b b g
x B x g
x x x B x g x
xx
x B x
?
?
?
?
? ? ? ?
? ? ? ?
? ? ? ?
??
? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ?
??
? ? ?
?
?
L
L
L L M
L
L
（ ） （ ）
若记
则方程组可简记为
选初值向量 代入,代入
，如此继续下去，就产生一个向量序列
满足
()
( 0,1,2,)
k
gk
J ac ob i
?? L
此过程所给出的迭代法称为 迭代法，又称简单
迭代法。
矩阵简化记法
1
1
1
100
010
001
0
0
0
21
221
112
21
221
112
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
??
?
?
?
??
?
?
bb
bb
bb
bb
bb
bb
nn
n
n
nn
n
n
B
AD I -
aaa
aaa
aaa
a
a
a
I
nn
1
nnn2n1
2n2221
1n1211
1
1
22
1
11
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
??
?
?
?
1
12
1 1 1 2 2 2
(,,,)
(,,,)
T
T
n
n n n
g g gg
bDb a b a b a ?
?
??
L
L
同样
收敛与解 1
*
**
n 0 1 2
{ }
B g
nn
k
J a c o b i B gxx
xx
xx
?
? ? ?
?
??
L
（ ） （ ）
（）
迭代,，，
若收敛,则
* 1 1
1 * 1
*
( ),,
I B x g B I D A g D b
D A x D b
A x b
??
??
? ? ? ? ?
??
??
即
故如果序列收敛,则收敛到解,B 称迭代矩阵,
1 2 3
1 2 3
1 2 3
1
10 2 72
10 2 83
5 42
1
00
10
1 0 0 10 1 2 0 0.1 0.2
1
0 1 0 0 0 1 10 2 0.1 0 0.2
10
0 0 1 1 1 5 0.2 0.2 0
1
00
5
x x x
J ac obi x x x
x x x
B I D A
?
? ? ??
?
? ? ? ?
?
?
? ? ? ?
?
??
??
??
??? ? ? ? ? ?
??
? ? ? ? ? ???
? ? ? ? ?
? ? ? ? ? ???
? ? ? ? ? ?????
? ? ? ? ? ?
??
??
??
例：用 迭代法求解
解：
1
( 0 ) ( 0 )
( 2 ) ( 1 ) ( 9 )
( 7.2,8.3,8.4)
( 0,0,0),( 7.2,8.3,8.4)
( 9.71,10.70,11.5 ) ( 10.9994,11.9994,12.999 2)
( 11,12,13 ),
T
TT
T
T
g D b
x Bx g
x Bx g x
x
?
??
? ? ? ?
? ? ? ?
?
L
(1)
取 代入迭代式，得x
精确解为
Jacobi迭代法的计算过程如下,
( 0 ) ( 0 ) ( 0 ) ( 0 )
1 1 2
( 0 )
1
( 0 )
( 0 )
1,( ),(,,),,(,,,),
,.
2,1.
3,1,2,,( ) /
4.,,5
5.,1,( 1,2,,),3
ij n n
n
i i ij j ii
j
ji
ii
A a b b b n x x x x
N
k
i n x b a x a
x x x
k N k k x x i n
?
?
?
?
? ? ?
?
? ? ?
??
? ? ? ? ?
?
LL
L
L
输入 维数
最大容许迭代次数
置
对
若 输出 停机；否则转 。
若 置 转 ；
否则，输出失败信息，停机。
( ) ( 1
,
kk
M x x
? ）
评价：公式简单，每迭代一次只需计算一次矩阵和向量
的乘法，不改变 的稀疏性，需两组工作单元，存 。
§ 3,高斯 — 塞德尔（ Gauss-Seidel)迭代法
( 1 ) ( )
( 1 ) ( ) ( ) ( )
1 12 2 13 3 1
1
( 1 ) ( ) ( ) ( )
2 21 1 23 3 2
2
( 0,1,2,)
kk
k k k k
nn
k k k k
nn
x B x g k
gx b x b x b x
gx b x b x b x
?
?
?
? ? ?
? ? ? ? ?
? ? ? ? ?
L
L
L
LL
迭代公式 用方程组表示为
( 1 ) ( ) ( ) ( )
1 1 2 2,1 1
( ) ( 1 )
k k k k
n n n n n n
n
kk
J ac obi
xx
gx b x b x b x
?
??
?
?
?
?
?
?
?
?
? ? ? ? ?
?
?
L
因此，在 迭代法的计算过程中，需同时保留两个
近似解向量 和 。若把迭代公式改写成
( 1 ) ( ) ( ) ( )
1 12 2 13 3 1
1
( 1 ) ( 1 ) ( ) ( )
2 21 1 23 3 2
2
( 1 ) ( 1 )
1 1 2
k k k k
nn
k k k k
nn
kk
n n n
gx b x b x b x
gx b x b x b x
x b x
?
??
??
? ? ? ? ?
? ? ? ? ?
??
L
L
LL
( 1 ) ( 1 )
2,1 1
( 0 ) ( )
,{ },
kk
n n n
n
k
n
xx
G auss Se ide l
J ac obi
gb x b x
??
??
?
?
?
?
?
?
?
? ? ?
?
?
?
L
这样，在整个计算过程中，只需用 个单元存储近似
解分量。而且通常认为，近似解可能比老近似解更接
近精确解，因此，可望这种迭代会更有效。
选取初始向量 用上式迭代产生近似解序列
这种方法叫 迭代法。
评价：与 相比，只需一组工作单元存放近似解。
° °
° °
° °
° °
° ° °
( 1 ) ( )
12 1
2,21
12
( 1 ) ( )
1
( 1 ) 1 ( ) 1
00
00
U
0
0
( )
1,( )
( ) ( )
kk
n
n
nn
kk
kk
L x U x g
L
I L x U x g
I L I L
x I L U x I L g
bb
bb
bb
?
?
?
? ? ?
? ? ?
????
????
????
??
????
????
?? ??
?? ??
? ? ?
? ? ?
? ? ? ?
L
MO
O
L
(k+1)
用矩阵表示为 x
其中,
移项可得
因为 故 存在，上式可改写为
° °
°
° °
1 2 1 3 1
21 2 3 2
3 1 3 2
1
1 2 1
11
1 1 1
( 1 ) 1 (
0 0 0 0
0 0
0 00
,
()
( )
n
n
nn
n n n n
kk
A
a a a
a aa
LUaa
a
a a a
L D L U D U
I L D D D L D D L
x I L U x
?
?
??
? ? ?
??
? ? ??? ??
?? ??
? ??
?? ??
?? ??????
?? ??
?
?? ??
?? ??
? ? ?
????
??
? ? ? ? ? ?
??
L L
L
OM M O O M
M M O O O
L L
如果用矩阵 来表示，记
则
由
°
)1
( 1 ) 1 ( ) 1
1
()
( ) ( )
( )
kk
I L g
x D L Ux D L b
M D L U Gau ss Se i de l
?
? ? ?
?
??
? ? ? ? ?
? ? ?式中矩阵 为 迭代法的迭代矩阵。
1 2 3
1 2 3
1 2 3
( 0 )
1 ( 0 ) ( 0 )
1 2 3 1
1 ( 1 ) ( 0 )
2 1 3 2
1
3
10 2 72
10 2 83
5 42
( 0,0,0),
11
( 2 ) 72 7.2 00 0
10 10
11
( 2 ) ( 7.2 00 0 83 ) 9.0 20 0
10 10
T
x x x
Gau ss Se i de l x x x
x x x
x
x x x b
x x x b
x
? ? ??
?
? ? ? ? ?
?
?
? ? ? ?
?
?
? ? ? ? ? ?
? ? ? ? ? ?
?
（）
（）
（）
例：用 迭代法求解
解：仍取 代入迭代式，得
( 1 ) ( 1 )
1 2 3
( 5 )
11
( ) 7.2 00 0 9.0 20 0 42 ) 11,64 40
55
( 10,99 89,11,99 93,12,99 96 )
( 11,12,13 ),
T
x x b
x
x
? ? ? ? ? ?
?
?
L
（
如此继续下去，
精确解为
G au se se ide l
J ac ob i
G au se se ide l J ac ob i
G au se se ide l
J ac ob i J ac ob i
G au se se ide l
J ac ob i
?
?
?
?
上例计算结果表明,迭代
法比 迭代法效果好。事实上，对有
些问题 迭代法确实比
迭代法收敛得快，但也有 迭
代比 迭代收敛得慢，甚至还有
迭代收敛,迭代发散的情形。
评价：与 相比，只需一组工作单
元存放近似解。
Gauss-Seidel迭代法的计算过程如下,
( 0 ) ( 0 ) ( 0 ) ( 0 )
1 1 2
( 0 )
1 1 1 11
2
1
( 0 )
11
1,( ),(,,),,(,,,),
,.
2,1.
3,( ) /
( ) / ( 2,,1 )
(
ij n n
n
jj
j
in
i i ij j ij j ii
j j i
nn
A a b b b n x x x x
N
k
x b a x a
x b a x a x a i n
x b a
?
?
?
? ? ?
? ? ?
?
??
? ? ? ? ?
??
?
??
LL
L
输入 维数
最大容许迭代次数
置
计算
1
1
( 0 )
( 0 )
)/
4.,,5
5.,1,( 1,2,,),3
n
nj j nn
j
ii
xa
x x x
k N k k x x i n
?
?
?
??
? ? ? ? ?
?
L
若 输出 停机；否则转 。
若 置 转 ；
否则，输出失败信息，停机。
§ 4.松弛法
( 1 ) ( ) ( 1 )
12
1
( 1 ) ( ) ( )
11
1
( 1 ) ( ) ( )
11
(,,,),
1
( )
T k k k
n
in
k k k
i ij j ij j i i
j j i
in
k k k
i ij j ij j i
j j iii
G auss Se ide l
x x x x x x x
G auss Se ide l
x b x b x g x
b a x a x x
a
??
?
?
? ? ?
?
?
? ? ?
?
? ? ? ? ? ? ?
?
? ? ? ? ?
? ? ? ?
??
??
L
为 迭代法加速。
记 其中 由
迭代公式得到。于是有
()
( 1 ) ( )
( 1,2,,)
k
kk
in
x G auss Se ide l k
x
x x x
?
?
??
? ? ?
L
可以把 看作 迭代的修正项，即第 次
近似解 以此项修正后得到新的近似解
( 1 ) ( )
( 1 )
1
( 1 ) ( )
11
( 1 ) ( )
(
kk
kk
i i i
in
k k k
i i ij j ij j
j j i
ii
x
x x x
x x x
x b a x a x
a
i
?
?
?
?
?
?
?
?
?
? ? ?
?
? ? ?
? ? ?
? ? ? ? ?
?
??
松弛法是将 乘上一个参数因子 作为修正项而
得到新的近似解，具体公式为
即
1,2,,)
11
1
n
A x b
G auss
Se ide l
? ? ?
?
?
? ? ?
?
L
按上式计算 的近似解序列的方法称为松弛法，
称为松弛因子。当 时称为低松弛； 是
迭代； 时称为超松弛法。
( 1 ) ( )
( ) 1 ( 1 ) 1 ( ) 1 ( )
( ) 1 ( 1 ) 1 ( ) 1
1 1 1 1
( 1 ) 1
( )
( 1 )
1,( )
( ) [ ( 1
kk
k k k k
k k k
k
x x x
x D L x D U x D b x
x D L x D U x D b
I D L I D L D L
x D L
?
?
? ? ? ?
? ? ?
??
?
? ? ? ?
? ? ? ?
? ? ?
??
? ? ?
? ? ? ? ?
? ? ? ? ?
? ? ? ?
? ? ?
－
松弛法迭代公式的矩阵表示：
因为 故（ ）与 存在，
有
( ) 1
1
) ] ( )
( ) [ ( 1 ) ]
,
k
D U x D L b
M D L D U
? ? ?
? ? ?
?
?
? ? ?
? ? ? ?
松弛法的迭代矩阵为
松弛因子的选取对收敛速度影响极大但目前尚无可
供实用的计算最佳松弛因子的方法。通常是根据系数矩
阵的性质及实际经验，通过试算来确定松弛因子。
( 0 )
12
1 2 3
23
1
( 1 ) ( 1 ) ( )
11
( 1 ) ( ) ( )
1 1 2
( 1 ) ( )
22
1.4,( 1,1,1 ),
21
2 0
2 1.8
( 1 ) ( )
0.4 0.7 ( 1 )
0.4
T
in
k k k k
i i i ij j ij j
j j i
ii
k k k
kk
x
xx
x x x
xx
x x b a x a x
a
x x x
xx
?
?
?
?
??
? ? ?
?
?
??
???
?
? ? ? ?
?
?
? ? ?
?
? ? ? ? ?
? ? ? ?
? ? ?
??
例：取 用超松弛法解方程组
解：由
( 1 ) ( )
13
( 1 ) ( ) ( 1 )
3 3 2
( 0 )
( 9 )
0.7 ( ) ( 0,1,2,)
0.4 0.7 ( 1.8 )
( 1,1,1 )
( 1.200,1.3996,1.6001 ) ( 1.2,1.4,1.6)
kk
k k k
T
TT
x x k
x x x
x
xx
?
??
?
?
? ? ?
?
?
? ? ? ?
?
??
??
L
将 代入上式开始迭代，
精确解
松弛法 计算过程如下,
( 0 ) ( 0 ) ( 0 ) ( 0 )
1 1 2
( 0 ) ( 0 )
1 1 1 1 11
2
1
( 0 ) ( 0 )
11
1,( ),(,,),,(,,,),
,.
2,1.
3,( 1 ) ( ) /
( 1 ) ( ) /
ij n n
n
jj
j
in
i i i ij j ij j ii
j j i
A a b b b n x x x x
N
k
x x b a x a
x x b a x a x a
??
??
??
?
?
? ? ?
? ? ?
?
? ? ? ?
? ? ? ? ?
?
??
LL输入 维数
最大容许迭代次数,参数
置
计算
1
( 0 )
1
( 0 )
( 0 )
( 2,,1 )
( 1 ) ( ) /
4.,,5
5.,1,( 1,2,,),3
n
n n n nj j nn
j
ii
in
x x b a x a
x x x
k N k k x x i n
??
?
?
?
??
? ? ? ?
??
? ? ? ? ?
?
L
L
若 输出 停机；否则转 。
若 置 转 ；
否则，输出失败信息，停机。
§ 5.迭代法的收敛条件
一、矩阵的谱半径
1
12
12
( 1,2,,)
( ) m a x { }
(,,,)
(,,,) ( 1,2,),( ) [ (
i
i
in
n
k
k k k k
n
A n i n A
A
A
A
A A A A
kA
?
??
? ? ?
? ? ? ? ?
??
?
?
?
??
L
L
L
LL
迭代法的收敛与迭代矩阵的特征值有关。
定义：设 为 阶方阵,为 的特
征值，称特征值的最大值为矩阵 的谱半径，记为
称为矩阵 的谱。
由特征值的定义知，矩阵 的谱是
因而 )]
k
A
,,
,( )
:,
,
( ),
,,,
ii
i i i i i i
ii
i
An
AA
Au
u u Au A u
uA
AA
An
?
?
??
?
??
?
?
?
? ? ?
?
?
定理设 为任意 阶方阵 为任意由向量范数诱导
出的矩阵范数则
证对 的任一特征值 及相应的特征向量 都有
因为 为非零向量于是有
由 的任意性即得 证毕
定理设 为任意 阶方阵则对任意正数 存在一种
矩阵
2
,( )
,,
( ) ( )
AA
n
A A A A A
??
??
? ? ?
?
??
范数 使得
证明略。
对任意 阶方阵一般不存在矩阵范数 使得
。但若 为对称矩阵，则有 。
l im 0 ( ) 1
l im 0
l im 0 ( )
0 ( ) [ ( ) ]
l im [ ( ) ] 0 ( ) 1
1
( ) 1
k
k
k
k
k
k
k k k
k
k
A n A A
A
A A A
A A A
AA
A
?
?
??
??
??
??
??
??
??
??
?
??
? ? ? ?
?
?
??
定理：设 为 阶方阵，则 的充要条件为 。
证：必要性,若
由矩阵收敛的定义知 又因
由极限存在的准则，有 ＝ 所以 。
充分性。若,取
()
0,
2
1 ( )
( ) 1
2
,l im l im 0 l im 0.
kk
k k k
k k k
A
A
AA
A A A A A
?
?
??
? ? ? ? ? ?
?
?
?
? ? ? ?
? ? ? ? ? ?
由上一定理
知，存在一种矩阵范数,使得
而
二、迭代法的收敛条件
( 0 )
( 1 ) ( )
()
* ( ) *
* * *
()
( 0,1,2,)
{ } ( ) 1,
,,,l im
kk
k
k
k
k
xg
x M x g k
xM
n x x x
x x M x g
x
?
?
??
? ? ?
?
?
??
L
定理：对任意初始向量 和右端项,由迭代格式
产生的向量序列 收敛的充要条件是
证必要性 设存在 维向量 使得
则 满足
由迭代公式有
* ( 1 ) *
( 1 ) * 2 ( 2 ) * ( 0 ) *
( 0 ) * ( ) *
( 0 )
( ) ( ) ( )
l im ( ) l im ( ) 0
,l im 0
( ) 1,
k
k k k
kk
kk
k
k
x M x g M x g
M x x M x x M x x
M x x x x
x n M
M?
?
??
? ? ? ?
??
? ? ? ? ?
? ? ? ? ? ?
? ? ? ?
?
??
于是有
因为 为任意 维向量因此上式成立必须
由上一定理
* * *
( ) * ( 1 ) * ( 0 ) *
( 0 )
( ) *
, ( ) 1,1,
0,,
,,
l i m 0
( ) ( )
,,
l i m ( ) l i m
k
k
k k k
k
kk
MM
I M n g I M x g
x x M x g
M
x x M x x M x x
x
x x M
??
??
?
? ? ? ?
??
? ? ? ?
??
?
? ? ? ? ?
??
充分性若 则 不是 的特征值因而有
于是对任意 维向量 方程组
有唯一解记为 即
并且
又因为
所以对任意初始向量 都有
( 0 ) *
( 1 ) ( ) ( )
( 0 )
( 1 ) ( )
()
( ) = 0
{ },
1 1,
( 0,1,2,)
{ },
k
k k k
kk
k
xx
x M x g x
x g M
x M x g k
x
?
?
?
??
?
? ? ? L
即由迭代公式 产生的向量序列 收敛
推论 对任意初始向量 和右端项,若 由迭代
格式
产生的向量序列 收敛
12
12
1
1
1 1 2 2
2 0 2
,,,
d e t ( ) [ ( )]
d e t ( ) 1
d e t ( ) ( ) ( 1 )
1
( )
( 1
n
n
n
nn
M
MM
M
M D L D U
DL
a a a
?
? ? ?
? ? ? ?
? ? ?
?
?
?
?
??
??
?
? ? ? ?
??
?
L
L
L
推论 松弛法收敛的必要条件是 。
证：设松弛法的迭代矩阵 由特征值 。
因为
由定理，松弛法收敛必有
又因为
1 1 2 2
) ( 1 )
d e t ( ) ( 1 ) 1 0 2
n
nn
n
D U a a a
M
??
??
? ? ?
? ? ? ? ? ? ?
L
。
迭代法收敛与否只决定于迭代矩阵的谱半径，与初始向
量及右端项无关。对同一方程组，由于不同的迭代法迭代
矩阵不同，可能出现有的方法收敛，有的方法发散的情形。
1 2 3
1 2 3
1 2 3
2 2 1
2
2 2 3
1
1 2 2 1 0 0
1 1 1 0 1 0
2 2 1 0 0 1
0 0 0
1 0 0
2 2 0
x x x
x x x
x x x
AD
L
? ? ??
?
? ? ?
?
?
? ? ?
?
?? ? ? ?
? ? ? ?
??
? ? ? ?
? ? ? ?
? ? ? ?
??
??
??
?
? ??
??
例：对方程组
讨论Jac obi 迭代法与Gau ss- Sei del 迭代法的收敛性。
解：求迭代矩阵判别其谱半径是否小于 。
0 2 2
0 0 1
0 0 0
U
???
??
??
? ? ?
? ? ?
??
1
3
1 2 3
Ja c ob i
0 2 2
1 0 1
2 2 0
22
1 1 0
22
0,( ) 0 1,
Ja c ob i
B I D A
IB
B
?
? ? ?
?
? ? ? ?
?
???
??
? ? ? ? ?
??
????
??
?
? ? ? ?
? ? ? ? ?
迭代法的迭代矩阵为
其特征方程为
因此有 于是
所以 迭代法收敛。
1
1
2
1
G a uss- S e i de l
1 0 0 1 0 0
1 1 0 ( ) 1 1 0
2 2 1 0 2 1
1 0 0 0 2 2 0 2 2
( ) 1 1 0 0 0 1 0 2 3
0 2 1 0 0 0 0 0 2
22
0 2 3 ( 2 ) 0
0 0 2
0,
D L D L
M D L U
IM
?
? ? ? ?
?
?
?
?
? ? ? ?
? ? ? ?
? ? ? ? ? ?
? ? ? ?
? ? ? ??
? ? ? ?
??? ? ? ? ? ?
? ? ? ? ? ?
? ? ? ? ? ? ?
? ? ? ? ? ?
? ? ? ? ? ??
? ? ? ? ? ?
?
? ? ? ? ? ?
?
?
迭代，由
特征方程
特征值为
23
2,( ) 2 1,M? ? ?? ? ? ?故 所以迭代发散。
0 2
1
12
1,
1,1
B
M
?
?
?
?
??
?
?
?
上例说明了 确实只是松弛法收敛的
必要条件，而非充要条件，因为Gau ss- Sei del
迭代记为 的情形。
判断定理虽然给出了判别迭代收敛的充要条
件，但要求逆矩阵和特征值。推论 与 仅分别
给出了收敛的充分与必要条件，许多情形下不
能起作用。如上例，两个方法均有
由推论 无法判别收敛性。
对一些特殊的系数矩阵可给出几个常用的判
别收敛条件
1
11 12
11 22
22
( ) ( 1,2,,)
,
0
1 1 0
1 1
n
ij ii ij
j
ji
n A a a a i n
iA
iA
A
AA
A A A A
A
A
?
?
? ? ?
??
?
??
??
?
?
L定义：若 阶方阵 满足
且至少有一个 值，使上式中不等号严格成立，则称 为弱
对角占优阵。若对所有，上式不等号均严格成立，则称
为严格对角占优阵。
定义：如果矩阵 不能通过行的互换和相应的列互换成
为形式 其中, 为方阵，则称 为不可约。
例：
13
2 1 0
0 0 1 1
0 1 2 0 1 1
PI T
P A P
?
? ? ? ?
? ? ? ?
???? ?
? ? ? ?
? ? ? ?
? ? ? ?
,
1.
Ja c ob i G a uss- S e ide l
2,0 1,
3.
02
10 1 2 2 1 0
1 10 2 1 2 1
1 1 5 0 1 2
A x b
A
A
A
AB
A
?
?
?
??
??
? ? ?? ? ? ?
? ? ? ?
? ? ? ? ? ?
? ? ? ?
? ? ? ?? ? ?
? ? ? ?
设有线性方程组 下列结论成立：
若 为严格对角占优阵或不可约弱对角占优阵，则
迭代法和 迭代法均收敛。
若 为严格对角占优阵,则松弛法收敛。
若 为对称正定阵，则松弛法收敛的充要条件为
。
上两例中：
为严格对角占优
B
?
阵，故Ja co bi 与Ga us s- Se id el 迭
代均收敛。 为非严格对角占优阵，但为对称正定
阵,=1,4 故松弛法收敛。
-1
11
1
22
11
,1
22
11
1
22
3 ( 0 2)
1
11
0
22
11
- 0
22
11
0
22
Ax b A
AA
A
B I D A
?
??
??
??
??
??
??
??
??
??
??
??
??
??
?
?
?
? ? ? ?
?
?
?
??
?
?
例,讨论用三种迭代法求解的收敛性。
解：因 为对称且其各阶主子式皆大于零，故 为对称正定矩
阵。由判别条件,G aus s-S eid el迭 代法与松弛法
均收敛。 不是弱对角占优阵，故不能用条件 判断。
Jacobi 迭代法的迭代矩阵为
?
?
?
?
?
?
?
?
3
2
1 2 3
11
22
1 1 3 1
2 2 4 4
11
22
1
( ) ( 1 ) 0
2
1
,1,( ) 1
2
IB
B
Jaco b i
?
? ? ? ?
?
??
? ? ? ?
? ? ? ? ?
? ? ? ?
? ? ? ? ?
?
其特征方程
得 因而
迭代法不收敛。
3 10
,
94
10 10
00
33
,
9 15
00
42
30 15
( ),( )
22
Ax b A
J ac obi Gaus s Se i de l
BM
BM??
???
??
??
?
??
?
? ? ? ?
?
? ? ? ?
??? ? ? ?
? ? ? ?
?
? ? ? ?
? ? ? ?
??
改变方程组中方程的次序，即将系数矩阵作行
交换，会改变迭代法的收敛性。
例：
与 迭代的迭代矩阵分别为
谱半径分别是 。均不收敛。
''
'
' ' '
,
3 1 0 9 4
9 4 3 1 0
A x b
A x b
AA
A A x b
J a c o b i G a u ss S e id e l
?
?
??? ? ? ?
? ? ?
? ? ? ?
??
? ? ? ?
?
?
若交换方程的次序，得 的同解方程组
为严格对角占优阵，因而对方程组 用
与 迭代求解均收敛。
三、误差估计
? ?
( 1 ) ( )
( ) *
( ) * ( 1 ) ( 0 )
1*
*1
( ) * ( 1 ) * ( 0 ) *
,1,
,
1
( ) 1,0,
)
)
( ) ( )
kk
k
k
k
k k k
x Mx g M
xx
M
x x x x
M
M M I M
I M x Mx g x
x I M g
x x M x x M x x
?
?
?
?
?
? ? ?
? ? ?
?
? ? ? ?
? ? ?
??
? ? ? ? ?
定理：设有迭代格式 若
收敛于 则有误差估计式
证：因 故 于是
( 存在，方程组 有唯一解,
且 ( 。从而有
( 0 ) 1
1 ( 0 )
1 ( 0 ) 1
[ ) ]
) [ ) ]
) [ ]
k
k
k
M x I M g
M I M I M x g
M I M x x
?
?
?
? ? ?
? ? ? ?
? ? ?
（）
(
((
(
( ) * 1 ( 0 ) 1
1
11
11
1
1
( ) *
)
) )
) )
) )
)
1
)
1
1
k
k
k
k
x x M I M x x
I M I M I
I M I M I M
I M I M I M
I M I M
IM
M
M
xx
?
?
??
??
?
?
? ? ? ?
? ? ?
? ? ? ? ?
? ? ? ?
? ? ?
??
?
??
?
（）
取范数 (
又因为 ( (
((
取范数 ( (
(
移项得 (
代入得
( 1 ) ( 0 )
xx
M
? 。
( ) * ( 1 ) ( 0 )
( 1 ) ( 0 )
( 0 ) ( 1 )
4(
1
:
( 1 )
ln
ln
0 0.1 0.2 0 7.2
0.1 0 0.2,0,8.3
0.2 0.2 0 0 8.4
10,0.4,
k
k
M
x x x x
M
k
M
xx
k
M
M x x
Mx
?
?
?
?
? ? ?
?
?
?
?
? ? ? ? ? ?
? ? ? ? ? ?
? ? ?
? ? ? ? ? ?
? ? ? ? ? ?
? ? ? ? ? ?
??
－
由误差估计式
根据事先给定的精度,可估计出迭代的次数
例：若
则有
1 ) ( 0 )
8.4
12.93 2,13
x
k
?
??
?? 即需要迭代 次才能满足精度。
? ?
( 1 ) ( )
( ) *
( ) * ( ) ( 1 )
( ) * ( 1 ) * ( 1 ) 1
1 ( 1 ) ( 1 ) 1 ( 1 ) ( )
( ) * 1 ( 1 )
,1,
,
1
( ) [ ) ]
) [ ] ) ( )
)
kk
k
k k k
k k k
k k k k
kk
x Mx g M
xx
M
x x x x
M
x x M x x M x I M g
M I M x Mx g M I M x x
x x M I M x
?
?
? ? ?
? ? ? ? ?
??
? ? ?
? ? ?
?
? ? ? ? ? ?
? ? ? ? ? ? ?
? ? ? ? ?
定理：设有迭代格式 若
收敛于 则有误差估计式
证：因 (
((
(
()
( ) ( 1 )
( ) ( 1 )
,
1
1
k
kk
kk
x
M
xx
M
M x x ?
?
?
??
?
??当 不太接近 时，可用 作为停机准则。
