第 6章 解线性方程组的迭代法
直接法得到的解是理论上准确的，但是我们可以看得出，它们的计算量都是 n3
数量级，存储量为 n2量级，这在 n比较小的时候还比较合适（ n<400），但是对于现
在的很多实际问题，往往要我们求解很大的 n的矩阵，而且这些矩阵往往是系数矩阵
就是这些矩阵含有大量的 0元素。对于这类的矩阵，在用直接法时就会耗费大量的时
间和存储单元。因此我们有必要引入一类新的方法：迭代法。
迭代法具有的特点是速度快。与非线性方程的迭代方法一样，需要我们构造一
个等价的方程，从而构造一个收敛序列，序列的极限值就是方程组的根
对方程组 bAx ? 做等价变换 gGxx ??
bMNxMxNxbMxbxNMbAx 11)( ?? ??????????
如：令 NMA ??,则
则，我们可以构造序列 gxGx kk ??? )()1(
若 *)( xx k ? bAxgxGx ????? ** *
同时：
*)(** )()()1( xxGGxGxxx kkk ??????
*)( )0(1 xxG k ??? ??
0?? kG所以，序列收敛 与初值的选取无关
定义 6.1：（收敛矩阵） 0?kG
定理,矩阵 G为收敛矩阵，当且仅当 G的谱半径 <11)( 0 ??? GG
k ?
由
GG ?)(?
知，若有某种范数
1?pG
则，迭代收敛
6.1 Jacobi迭代
?
?
?
?
?
???
???
nnnnn
nn
bxaxa
bxaxa
?
?
?
11
11111
?
?
?
?
?
??
?
?
?
?
???
?
?
????
?
?
???
?
?
?
??
)(
1
)(
1
)(
1
11 11
21323121
22
2
11212
11
1
nnnnn
nn
n
nn
nn
bxaxa
a
x
bxaxaxa
a
x
bxaxa
a
x
?
?
?
?
?
?
?
?
?
??
?
?
?
?
???
?
?
????
?
?
???
?
?
?
??
?
?
?
)(
1
)(
1
)(
1
)(
11
)(
11
)1(
2
)(
1
)(
323
)(
121
22
)1(
2
1
)(
1
)(
212
11
)1(
1
n
k
nnn
k
n
nn
k
n
k
nn
kkk
k
nn
kk
bxaxa
a
x
bxaxaxa
a
x
bxaxa
a
x
?
?
?
?
格式很简单：
)(1
1
)(
1
1
)()1(
i
n
ij
k
jij
i
j
k
jij
ii
k
i bxaxaax ??
?? ??
??
?
?
?
Jacobi迭代算法
1、输入系数矩阵 A和向量 b，和误差控制 eps
2,x1={0,0,…..,0},x2={1,1,…..,1} // 赋初值
3,while( ||A*x2-b||>eps) {
x1=x2;
for(i=0;i<n;i++) {
x2[i]=0;
for(j=0;j<i;j++) {
x2[i] += A[i][j]*x1[j]
}
for(j=i+1;j<n;j++) {
x2[i] += A[i][j]*x1[j]
}
x2[i]=-(x2[i]-b[i])/A[i][i]
}
}
4、输出解 x2
? 迭代矩阵
ULDA ???记
?
?
?
?
?
?
?
?
?
?
?
nna
a
D
0
011
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
?
0
0
0
00
11
21
nnn
aa
a
L
?
???
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
?
?
00
0
0
0
1
112
nn
n
a
aa
U ?
??
?
易知,Jacobi迭代有
bxULD ??? )(
bxULDx ??? )(
bDxULDx 11 )( ?? ???
bDgADIULDG 111,)( ??? ??????
? 收敛条件
迭代格式收敛的充要条件是 G的谱半径 <1。对于 Jacobi迭代，我们有一些保证收敛
的充分条件
定理：若 A满足下列条件之一，则 Jacobi迭代收敛。
① A为行对角占优阵
② A为列对角占优阵
③ A满足
?
?
?
ij
ijii aa
?
?
?
ji
ijjj aa
1??
? ji ii
ij
a
a
证明：
)(1 ULDG ?? ?
ii
ij
ij
ij ii
ij
i
aaaaG ???? ??
??
? 1m a x
1m a x1 ?? ?
? ji ii
ij
i a
aG
② A为列对角占优阵，则 AT为行对角占优阵，有
1)( 1 ?? ? TADI?
1)()( 11 ????? ?? TADIADI ?? ＃证毕
?
?
?
?
?
??
?
?
?
?
???
?
?
????
?
?
???
?
?
?
?
??
??
??
?
)(
1
)(
1
)(
1
)1(
11
)1(
11
)1(
2
)(
1
)(
323
)1(
121
22
)1(
2
1
)(
1
)(
212
11
)1(
1
n
k
nnn
k
n
nn
k
n
k
nn
kkk
k
nn
kk
bxaxa
a
x
bxaxaxa
a
x
bxaxa
a
x
?
?
?
?
6.2 Gauss－ Seidel迭代
)(1
1
)(1
1
)1()1(
i
n
ij
k
jij
i
j
k
jij
ii
k
i bxaxaax ??
?? ??
??
?
?
??
在 Jacobi迭代中，使用最新计算出的分量值
Gauss-Siedel迭代算法
1、输入系数矩阵 A和向量 b，和误差控制 eps
2,x2={1,1,…..,1} // 赋初值
3,while( ||A*x2-b||>eps) {
for(i=0;i<n;i++) {
for(j=0;j<i;j++) {
x2[i] += A[i][j]*x2[j]
}
for(j=i+1;j<n;j++) {
x2[i] += A[i][j]*x2[j]
}
x2[i]=-(x2[i]-b[i])/A[i][i]
}
}
4、输出解 x2
? 迭代矩阵
)( )()1(1)1( bUxLxDx kkk ??? ???
bDUxDxLDI kk 1)(1)1(1 )( ???? ???
bDLDIUxDLDIx kk 111)(111)1( )()( ??????? ????
bLDUxLDx kk 1)(1)1( )()( ??? ????
bLDgULDG 11 )(,)( ?? ?????
是否是原来的方程的解？
A=(D-L)-U
? 收敛条件
迭代格式收敛的充要条件是 G的谱半径 <1。我们看一些充分条件
定理：若 A满足下列条件之一，则 Jacobi迭代收敛。
① A为行或列对角占优阵
② A对称正定阵
证明,设 G的特征多项式为 )(?
sP
，则
ULDLDULDIGIP s ?????????? ?? )()()()( 11 ????
ULDA ??? 为对角占优阵，则 1?? 时 ULD ?? )(? 为对角占优阵
0)( ???? ULD?
即 0)( ??
sP
1 ?? ? 即 1)( ?G?
＃证毕
注,二种方法都存在 收敛性问题 。
有例子表明,Gauss-Seidel法收敛时,Jacobi法可能
不收敛；而 Jacobi法收敛时,Gauss-Seidel法也可能
不收敛。
( 0 )
1 8 0 7
1 0 9,8,( 0,0,0) '
9 1 1 7
A b x
?? ? ? ?
? ? ? ?? ? ? ?
? ? ? ?
? ? ? ???? ? ? ?
1、预处理
9 1 1 7
1 8 0,7
1 0 9 8
Ab
??? ? ? ?
? ? ? ?? ? ?
? ? ? ?
? ? ? ??? ? ? ?
2、格式
( 1 ) ( ) ( )
1 2 3
( 1 ) ( 1 )
11
( 1 ) ( 1 )
11
1 / 9( 7 )
1 / 8 ( 7 )
1 / 9( 8 )
k k k
kk
kk
x x x
xx
xx
?
??
??
? ? ? ?
?
???
? ??
?
( 1 )
( 2 )
( 3 )
( 4 )
( 0, 7 7 7 8,0, 9 7 2 2,0, 9 7 5 3 ) '
( 0, 9 9 4 2,0, 9 9 9 3,0, 9 9 9 4 ) '
( 0, 9 9 9 9,0, 9 9 9 9,0, 9 9 9 9 ) '
( 1, 0 0 0 0,1, 0 0 0 0,1, 0 0 0 0 ) '
x
x
x
x
?
?
?
?
3、结果
1
0 1 / 2 1 / 2
( ) 1 0 1
1 / 2 1 / 2 0
B D L U?
???
??? ? ? ? ?
??
1,Jacobi迭代
2 1 1
1 1 1
1 1 2
A
???
???
?????
特征值为
3 5 0
4IB? ? ?? ? ? ? 1 2,3
50,
2 i??? ? ?
1
0 1 / 2 1 / 2
( ) 0 1 / 2 1 / 2
0 0 1 / 2
B D L U?
???
??? ? ? ? ?
???
2,Gauss－ Siedel迭代
1 2,3
10,
2??? ? ?
6.3 松弛迭代
记
)()1()( kkk xxx ??? ?
则
)()()1( kkk xxx ????
可以看作在前一步上加一个修正量。若在修正量前乘以一个因子 ?,有
)()()1( kkk xxx ???? ?
)( )()1(1)1( bUxLxDx kkk ??? ???对 Gauss－ Seidel迭代格式
)( )()1()()1( kkkk xxxx ??? ?? ?
)( )(1)(1)1(1)()1( kkkkk xbDUxDLxDxx ????? ????? ?
)()1( 1)(1)1(1)()1( bDUxDLxDxx kkkk ????? ????? ??
?
?
?
?
?
??
?
?
?
?
???
?
???
???????
???
?
???
??
?
?
?
)(
1
)1(
)()1(
)(
1
)1(
)(
11
)(
11
)()1(
2
)(
1
)(
323
)(
121
22
)(
2
)1(
2
1
)(
1
)(
212
11
)(
1
)1(
1
n
k
nnn
k
n
nn
k
n
k
n
k
nn
kkkk
k
nn
kkk
bxaxa
a
xx
bxaxaxa
a
xx
bxaxa
a
xx
?
?
?
?
??
?
?
??
写成分量形式，有
松弛迭代算法
1、输入系数矩阵 A、向量 b和松弛因子 omega，和误差控制 eps
2,x2={1,1,…..,1} // 赋初值
3,while( ||A*x2-b||>eps) {
for(i=0;i<n;i++) {
temp-0
for(j=0;j<i;j++) {
temp += A[i][j]*x2[j]
}
for(j=i+1;j<n;j++) {
temp += A[i][j]*x2[j]
}
temp = -(x2[i]-b[i])/A[i][i]
x2[i] = (1-omega)*x2[i]+omega*temp
}
}
4、输出解 x2
)()1( 1)(1)1(1)()1( bDUxDLxDxx kkkk ????? ????? ??
? 迭代矩阵
bDxUDIxLDI kk 1)(1)1(1 ))1(()( ???? ????? ????
bDLDIxUDILDIx kk 111)(111)1( )())1(()( ??????? ?????? ?????
bDLDIg
UDILDIG
111
111
)(
))1(()(
???
???
??
?????
??
???
定理,松弛迭代收敛 20 ??? ?
定理,A对称正定，则松弛迭代收敛 20 ??? ?
是否是原来的方程的解？
SOR方法收敛的快慢与松弛因子 ?的选择有密切关系,
但是如何选取最佳松弛因子,即选取 ?=?*,使 ?(￡?)达到最
小,是一个尚未很好解决的问题,实际上可采用试算的方法
来确定较好的松弛因子,经验上可取 1.4<?<1.6.
定理 若 SOR方法收敛,则 0<?<2.
证 设 SOR方法收敛,则 ?(￡?)<1,所以
|det(￡?)| =|?1?2… ?n|<1
而
det(￡?) =det[(D-?L)-1 ((1-?)D+?U)]
=det[(E-?D-1L)-1 ]det[(1-?)E+?D-1U)]
=(1-?)n
于是
|1-?|<1,或 0<?<2
定理 设 A是对称正定 矩阵,则解方程组 Ax=b的 SOR
方法,当 0<?<2时收敛,
证 设 ?是 ￡?的任一特征值,y是对应的特征向量,则
[(1-?)D+?U]y=? (D-?L)y
于是
(1-?)(Dy,y)+?(Uy,y)=?[(Dy,y)-?(Ly,y)]
)()(
)())(1(
yL y,yD y,
yU y,yD y,
?
???
?
???
由于 A=D-L-U是对称正定的,所以 D是正定矩阵,且 L=UT,
若记 (Ly,y)=?+i?,则有
(Dy,y)=?>0
(Uy,y)=(y,Ly)=(Ly,y) =?-i?
0<(Ay,y)=(Dy,y)-(Ly,y)-(Uy,y) =?-2?
所以
)(
)()1(
????
??????
i
i
??
????
222
222
2
)(
)(||
?????
????????
??
????
当 0<?<2时,有
(?-??+??)2-(?-??)2= (2??-??)(2?-??)
= ?? (2?-?)(2-?)<0
所以 |?|2<1,因此 ?(￡?)<1,即 S0R方法收敛,
可得 ?=2?/?
设 ?是 B的任一特征值,y是对应的特征向量,则
(L+U)y=?Dy
于是
(Ly,y)+(Uy,y)=?(Dy,y)
当 A对称正定时,即 2?-?<0时,|?|<1? 2?+?>0
而 ((2D-A)y,y)=(Dy,y)+(Ly,y)+(Uy,y) =?+2?
即,当 A对称正定时,Jacobi迭代法收敛 ?2D-A正定,