第二章
2.2 解线性方程组的迭代法
数学与统计学院
1 1 1 1 2 2 1 1
2 1 1 2 2 2 2 2
1 1 2 2
( 1 )
nn
nn
n n n n n n
a x a x a x b
a x a x a x b
a x a x a x b
? ? ??
?
? ? ??
?
?
? ? ? ?
?
? ?
,0,
X,.
11
ij nn
T
A X b
A
T
nn
a
,,),,)( x ( bxb b
?
?
??
??
矩 阵 表 示 记 为
这 里 我 们 假 设 A
解线性方程组的两类方法
直接法, 经过有限次运算后可求得方程组精确解
的方法 (不计舍入误差 !)
迭代法：从解的某个近似值出发，通过构造一个
无穷序列去逼近精确解的方法。
迭代法研究的主要问题
1）迭代格式的构造；
2）迭代的收敛性分析；
3）收敛速度分析；
4）复杂性分析；（计算工作量）
5）初始值选择。
迭代格式的构造
把矩阵 A分裂为
则,0,A Q C Q? ? ?
11
()
()
.
A x b Q C x b
I Q C x Q b
x B x g
??
? ? ? ?
? ? ?
? ? ?
迭代过程
B称为迭代矩阵。
给定初值 就得到向量序列
定义：若 称逐次逼近法收敛，
否则，称逐次逼近法不收敛或发散。
1,( 2 )kkx B x g? ??
0,x
01,,,nx x x
*lim,
nn xx?? ?
问题,是否是方程组（ 1）的解？
定理 1：任意给定初始向量,若由迭
代公式（ 2）产生的迭代序列收敛到,
则 是方程组（ 1）的解。
证：
0x
*x
*x
*x
**1l i m l i m ( ),kk
kk x B x g x B x g?? ? ? ?? ? ? ? ?
逐次逼近法收敛的条件
定理 2：对任意初始向量,由（ 2）得到
的迭代序列收敛的充要条件是迭代矩阵
的谱半径
证：
因此
( ) 1,B? ?
0x
**
1
* * 1 *
10( ) ( ),
kk
k
kk
x B x g
x B x g
x x B x x B x x
?
?
?
? ???
??
????
? ? ? ? ? ?
*1
1l i m ( ) 0 l i m 0 ( ) 1,
k
kkkx x B B?
?
?? ? ? ?? ? ? ? ? ?
要检验一个矩阵的谱半径小于 1比较困难，
所以我们希望用别的办法判断是否有
定理 3：若逐次逼近法的迭代矩阵满足,
则逐次逼近法收敛。
Remark:因为矩阵范数,, 都可以
直接用矩阵 的元素计算，因此，用定理 3，
容易判别逐次逼近法的收敛性。
1l i m 0,k
k B
?
?? ?
1B ?
1B FBB?
问题：如何判断可以终止迭代？
定理 4：若迭代矩阵 满足 则
（ 3）
（ 4）
Remark:
1) (4)式给出了一个停止迭代的判别准则。
2) (3）式指出 越小收敛越快。,
1B ?
1
*
1 1 01
k
k
Bx x x x
B
?
? ? ? ??
*
11 1k k k
Bx x x x
B??? ? ??
1B ?
证：
**
1 2 2 1
*
2 2 1
*
11
*
11
( ) ( )
k k k k
k k k
k k k
k k k
x x x x x x
x x x x
B x x B x x
B x x B x x
? ? ? ?
? ? ?
??
??
? ? ? ? ?
? ? ? ?
? ? ? ?
? ? ? ?
1 1 1 0
k
k k k kx x B x x B x x??? ? ? ? ? ?
Jacobi 迭代
11 1 12 2 13 3 1 1
21 122 2 23 3 2 2
31 1 32 233 3 34 4 3 3
1 1 2 2,1 1
+
nn
nn
nn
n n n n nnn n n
ax
a x a x
a x a x a x
a x a x a x a x b
a x a x a x b
a x a x a x b
a x b??
? ? ? ? ? ? ?
?
? ? ? ? ? ? ?
?
?
? ? ? ? ? ??
?
?
?
? ? ? ? ?
?
?
=
Dx Lx Ux
Jacobi迭代
( ),(A x b D x L U x b? ? ? ? ? ?若 | D | 0 )
11( ),x D L U x D b??? ? ? ?
( ) ( ),0,ij ij ij ijL l l a i j e l se l? ? ? ? ?
( ) ( ),0,ij ij ij ijD d d a i j e l se d? ? ? ? ?
()A D L U? ? ?分裂
迭代过程：
若记
111 ( ),kkx D L U x D b??? ? ? ?
1
( 1 ) ( ) ( )
11
1
( ( ) ),
in
k k k
i ij j ij j i
j j iii
x a x a x b
a
?
?
? ? ?
? ? ? ???
( 1 ) ( ) ( )
1
1
( ),
n
k k k
i i ij j i
jii
x b a x x
a
?
?
? ? ??
( ) ( ) ( )
12(,,,),
k k k
knx x x x
??
算法描述
1 输入
2 if,then
2.1 for
2.1.1 s=0,
2.1.2 for
2.1.3
2.1.4 if then
0,,,,.A b x M?
kM?
1,2,,in?
1,2,,jn?
0()ij js s a x??
10( ) ( ) / ( )i i ii ix b s a x? ? ?
01| ( ) ( ) |iixx? ??
01| ( ) ( ) |,iixx ???
( 1 ) ( ) ( )
1
1 ( ),nk k k
i i ij j i
jii
x b a x xa?
?
? ? ??
2.2 k=k+1
2.3 if then
2.3.1
2.3.2 goto 2
else
输出 结束。
else
2.4 输出 迭代次数太大。
3 结束
???
1,xk
10xx?
Gauss-Seidel迭代
假设
| | 0,D ?
1
( 1 ) ( ) ( )
11
1
( ( ) ),
in
k k k
i ij j ij j i
j j iii
x a x a x b
a
?
?
? ? ?
? ? ? ???
Jacobi迭代
1
( 1 ) ( 1 ) ( )
11
1
( ( ) ),
in
k k k
i ij j ij j i
j j iii
x a x a x b
a
?
??
? ? ?
? ? ? ???
1
( 1 ) ( 1 ) ( ) ( )
1
1 ( ),ink k k k
i ij j ij j i i
j j iii
x a x a x b x
a
?
??
??
? ? ? ? ???
A x b? ()A D L U? ? ?
分裂
算法描叙
1 输入
2 if,then
2.1 for
2.1.1 s=0，
2.1.2 for
2.1.3
0,,,,.A b x M?
kM?
1,2,,in?
1,2,,jn?
0()ij js s a x??
0()itx?
00( ) ( ) / ( )i i ii ix b s a x? ? ?
1( 1 ) ( 1 ) ( ) ( )
1
1 ( ),ink k k k
i ij j ij j i i
j j iii
x a x a x b xa ???
??
? ? ? ? ???
2.1.4 if then
2.2 k=k+1
2.3 if,输出结果，结束。
else
2.4 输出迭代次数太大。
3 结束
0| ( ) |,ixt ??? 0| ( ) |ixt? ??
???
Remark:
1) Gauss-Seidel迭代法的计算过程比 Jacobi
迭代法更简单。计算过程中只需用一个
一维数组存放迭代向量。
2) Gauss-Seidel迭代不一定比 Jacobi迭代收
敛快。
例
希望直接对系数矩阵 A研究这俩种迭代收敛
条件。
定理 5 设 A是有正对角元的 n阶对称矩阵，
则 Jacobi迭代收敛 A和 2D-A同为正定
矩阵。
证：记
则
即,
从而有相同的谱半径。
?
?
1 1 2 2(,,,),nnD d ia g a a a?
1
2
1 1 1 1 1 1(,,,),D d i a g a a a?
1 1 1 1
12 2 2 2()
JD I D AD D I D A B
? ? ? ?? ? ? ?
11
22( ) ~ JI D A D B???
由 A的对称性,也对称，
因而特征值全为实数，记为
则 的任一特征值为 。
A, 正定。
故 正定。
11
1122 ()
i i j j i jD A D a a a
?? ???
,(1 ),i in? ??
11
22I D A D??? 1
i??
( ) 1 1 1 1 0 2J i iB? ? ?? ? ? ? ? ? ? ? ? ?
11
222 I D A D???
1 1 1 1
2 2 2 22 ( 2 )D A D I D A D D??? ? ? 2 DA?
?
A正定 正定,特征
值小于 1。
若 2D-A正定,特
征值小于 1,所以 特征值大于－ 1。
?
1122D A D??? 1122I D A D???
1 1 1 1
2 2 2 2( 2 ) ( )I D D A D I D A D? ? ? ?? ? ? ? ?
JB
定理 6 A按行（列）严格对角占优，则
Jacobi迭代收敛。
引理 A按行（列）严格对角占优
（ ）
证 （提示）
?
1.JB ? ? 1 1.JB ?
1,
m a x | |
n ij
J
j j i ii
aB
a? ??? ?
定理 7 A按行严格对角占优，则 Gauss-
Seidel迭代收敛。
证 设 是 任一特征值,x 是相应
特征向量。设
若
则
GSB ?
| | m a x | |,ijxx?
1
1
11
()
| | | | | | | | | | | | | |,
in
j
ii ij ij j
j j ii
D L U x x D x L x U x
x
a a a x
x
? ? ?
??
?
?
? ? ?
? ? ? ? ?
????
| | 1,? ?
1
11
| | | | | |,
in
ii ij ij
j j i
a a a
?
? ? ?
????
?
定理 8 A按列严格对角占优，则 Gauss-
Seidel迭代收敛。
证
设 是 的任一特征值，
x 是相应特征向量。设
1 1 1( ) ( ) ( ( ) ) ( ),D L U D L U D L D L? ? ?? ? ? ? ?
? 1( ( ) )U D L ???
| | m a x | |,ijxx?
1
11
( ),
ni
ii i ji j ji j
j i j
D L x U x a x a x a x??? ? ?
?
? ? ?
? ? ? ? ???