,n
二、 Gauss-Seidel迭代法
在J迭代公式中，计算
( k 1) x1( k 1) , x2 ,
) xi( k 1时，利用已经算出来的新的
k 1) , xi( 1 值，从而得到G-S迭代法。
G-S迭代法是J迭代法的一种改进
G-S迭代法的分量形式：
bi aij x
j 1 i 1 ( k 1) j
(k ) 3
10 (k ) (k ) ( 5 2 x1 3 x3 ) ( k 1) x2 ( 10) (k ) (k ) (14 x1 3 x2 ) ( k 1) x3 10
x
( k 1) 1
x
x
( k 1) 1
( k 1) 2


( 10) ( k 1) ( k 1) (14 x1 3 x2 ) ( k 1) x3 10 T Jacobi迭代法 取初值 x (0 0 0)
1 2
1 2
AD 是对称正定的。 对 x R ( 0)
x Ax y D AD y 0
T T

1 2

2 D A D (2 I D AD ) D
而矩阵 2 I D
1 2 1 2

1 2

1 2
1 2
同理可证
AD 是对称正定的
2D A 0
充分性 因为 A 正定，所以 D
ji
|a
j 1 jm
n
mj
|
对 k J ，有 由此可知，当
akk akj
jk
xj xk
xk x j
时，akj
0
否则与弱对角占优矛盾！ 但对于 k J , 所以
jJ
都有
xk x j
与不可约矛盾
akj 0 k J , j J
Th6.9 如果 A (aij )nn 为严格对角占优或为不可约
第六章 线性代数方程组的迭代解法
/*Iterative Method for Solving Linear Algebraic Systems*/
求解 A x b, A R
迭代法
nn
det( A) 0
从一个初始向量出发,按照一定的递推 格式,产生逼近方程组的近似解序列。
与解f (x)=0 的不动点迭代相似 ， 将方程组 A x b 思 等价改写成 x B x f 形式，从而建立迭代格式 路 ( k 1) (k ) (k ) (0) { x } x B x f ，从 x 出发，生成迭代序列 迭代法是一种逐次逼近的方法,与直接法比较, 具有: 程序简单,存储量小的优点。特别适用于求解系数 矩阵为大型稀疏矩阵 /* sparse matrices */ 的方程组。
的G-S法收敛，而J法不一定收敛。
例2：判定用J法和G-S法求解下列方程组的收敛性：
det( D L U ) 0
1
矛盾！
如果 A 为严格对角占优矩阵，易证
B 1 其中B 为J法的迭代矩阵
Th6.10 如果 A 是对称矩阵，且有正的对角元，则
求解方程组 Ax b的J法收敛的充要条件是矩阵 A
和 2D 证明： 记D
1 2
A 均为正定的，其中 D diag(a11 ,
B 1 Gauss-Seidel迭代法收敛的充分条件是 G 1
如例1：利用J和G-S迭代法求解方程组
10 3
1

2 10 3
x1 x2

14 5
3
10 x3
14
10 3
系数矩阵 A
2 10 3
1
1,2 0.05 0.384i 3 10 3 0.1
0
1
Jacobi迭代矩阵
aii 0, i 1, 2, , n ，且 A 非奇异。
自己看
Th6.8 如果 A (aij )nn 不可约且弱对角占优，则
aii 0, i 1, 2, , n ，且 A 非奇异。 证明：首先证明 aii 0, i 1, 2, , n 设 k , akk 0
A 是弱对角占优， 由条件：
如果 aii
相应的迭代格式
x( k 1) Bx( k ) f ; k 0,1, 2,
上述方法称为Jacobi迭代法，简称J法或简单迭代法
分量形式：
x
( k 1) i

bi aij x
j 1
i 1
(k ) j

j i 1
a
n
ij
x
(k ) j
a ii
; i 1, 2,

x
( k 1) i

j i 1
a
n
ij
x
(k ) j
a ii
; i 1, 2,
,n
例1：利用Jacobi和Gauss-Seidel迭代法求解方程组
10 3
1
1
2 10 3
解：
Jacobi 迭 代 格 式
x1 x2

14 5
3

10 x3
(14 3 x
(k ) 2
14
x )
(14 3 x
(k ) 2
x )
(k ) 3
G-S
似 解
1.0002507)
0.9999541)
0.9999981)
Gauss-Seidel迭代法 取初值 计 算 结 果
要求 精度
x (0 0 0)
T
迭代 方 程 组 的 近 次数 0.001 5 (0.9997916 0.9998479 0.0001 7 (0.9999929 0.9999949 0.00001 8 (1.0000013 1.0000009
0
是可约的
2
r1 r3
1 1
c1 c3
2

1 1
1 1
2
1
0
0

0
0
1
1 1 0
0 1 1
若系数矩阵是可约的，则可通过行与列重排化为 （*）式，从而可以将方程组简化为低阶方程组。
Def 6 （补充:可约矩阵的等价定义）
A R
子集 J
n n
是可约矩阵，当且仅当存在一个下标的非空
计 算 结 果
迭代 方 程 组 的 近 次数 0.001 9 (1.0002507 1.0000694 0.0001 10 (0.9999541 1.0001253 0.00001 14 (0.9999981 1.0000020 要求 精度
迭 代 格 式
10 ( k 1) (k ) ( 5 2 x1 3 x3 )
G 1 227
500
B

2
5
1 0 2 0.04914 3 0.18314
Def 5
设 A (aij ) Rnn满足 否则称 A 为不可约的
n
aii aij
j 1 ji
i 1, 2,
ij
, n称 A 为严格对角占优矩阵 , n 且至少有一个严格
如果 aii
( k 1) 1 1 ( k 1) (k ) 1
似 解
1.0000664) 1.0000022) 0.9999996)
G-S迭代法的迭代矩阵：
由迭代公式
x
D Lx
1 1
D Ux
(k )
f
1
x
( k 1)
( I D L) D Ux
( I D L) f ( D L) U
§2 Jacobi和Gauss-Seidel迭代法
一、 Jacobi迭代法
设方程组 Ax b; A (aij )nn , b (bi )1n ;det( A) 0
D LU 其中 D diag(a11 , a22 , , ann )
0
将系数矩阵分裂为：A
L a31 a32 0
1 2
, ann )
D D
其中 D
1
1 2
diag( a11 , a22 ,
1 2 1 2
, ann )
1 2 1 2
迭代矩阵
B I D A D ( I D AD ) D
D AD
、 I
1 2
1 2
矩阵 B 和I
1 2相似，故有相同的特征值；且
D AD
a
j 1 ji
n
i 1, 2,
不等式成立，则称 A为弱对角占优矩阵。
Def 6
T
设 A R
n n
，如果能找到排列阵 P ，使得
A11 () P AP 0
A12 其中 A11与 A22均为方 A22 阵，称 A为可约的
1 1 0
例如： 矩阵 A 1
0
1
1
迭代矩阵 G ( I D1 L)1 D1U
三、 Jacobi和Gauss-Seidel迭代法的收敛性
Th6.6
Jacobi迭代法收敛的充要条件是 ( B ) 1
Gauss-Seidel迭代法收敛的充要条件是 (G ) 1
推论1：Jacobi迭代法收敛的充分条件是
akj 0; j 1, 2, , n
与 A不可约矛盾！
交换 A 的第k、n行与k、n列，则矩阵 A 变为
A11 P AP 0
T
A12 0
其次证明 A是非奇异的
则存在非零向量
设 det( A) 0
x ( x1 , x2 ,
且令