计算方法-迭代法讲义

a2n a22
a(n1)n
a (n1)(n1)
0
常数向量：
b ' [b1 / a11 , b2 / a22 ,L , bn / ann ]T
4
雅可比迭代法的分量形式：
a11 x1 a12 x2 a1n xn b1
a21
x1
a22 x2
a2n xn
b2
an1 x1 an2 x2 ann xn bn
4x1 2x2 8x3 24 9x3 24 4x1 2x2 x3
15
1 3 / 4 2 / 4
B
4
/
9
2 / 9
1/ 9
4 / 9 2 / 9 1 / 9
5
b
'
33
/
9
24 / 9
|| B || 2.25, || B ||1 1.89, || B ||2 1.37 , (B) 0.85
什么时候收敛？收敛速度如何？
1
如果收敛，设：
lim X (k) X * lim || X (k) X * || 0
k
k
则： X * BX * b ' 就是原方程组的解。
X (k1) X * BX (k) BX *
B(X (k) X * ) B X (k) X *
所以，当 B q 1 时，迭代收敛。且有： || X (k ) X * || 1 || X (k1) X (k ) || 1 q
X (k 1) BJ X (k ) b '
其中：
当||BJ||<1时，雅可 比迭代收敛。
3
计算时用到的Jacobi迭代矩阵：
0
a12 a11
a1(n1) a11
BJ
a21
a22
0
a2(n1)
a22
0
an1
ann
an2 ann
an(n1) ann
a1n a11
5 3
x2( k
1)
x(k 1) 1
2
5 2
x(0 1
x2(0
) )
0 0
8
➢ 雅可比方法与高斯-赛德尔方法的比较 • 收敛与否？ • 收敛快慢？
当 A 的主对角线元素全为正，其它元素都≤0时， G-S方法与J方法同收敛或否，且G-S收敛快。
当 A 的元素全为正时，G-S方法优于J方法。
可以试验一下一般情况下两种算法的比较，参见 GSvsJ.m和JvsGS.m两个程序。
SOR迭 代( 1.3545)， 17次 ， (B) 0.452847
BSOR (D L)1[(1 )D U ] I (D L)1 A
定理9： 若系数矩阵的主对角元素全不为0，则 0<<2 是松弛法收敛的必要条件。
定理10：若A对称正定， 0<<2 ，则对任意初 值，SOR方法收敛。
定理8 Bk 0, k 的充要条件是：
(B) 1
且 (B) 越小，收敛越快。
10
定理5 若迭代公式 X(k+1) = BX(k)＋b’ 的迭代矩阵 B 的某个算子范数 || B || = q < 1，则： （1）对任意的初始向量 X(0), 该迭代收敛于原方 程的唯一解 X*；
（2）
||
X*
(bi
a x( k1) ij j
aij
x
(k j
)
)
/
aii
j 1
j i 1
i 1
n
x(k) i
(bi
a x( k1) ij j
aij
x
( j
k
)
)
/
aii
j 1
ji
x~i(k )
19
计算新的近似值，得到SOR方法：
x( k1) i
x~i(k )
(1 ) xi(k )
i 1
n
计算 xi(k1) 时,
x(k 1) j
(
j
i)的值已经算出
所以迭代公式可以修改成：
X (k1) D1LX(k1) D1UX (k) D1b
或写成分量形式
i1
n
x(k1) i
(bi
aij
x
( j
k 1)
aij x(jk) ) / aii
j 1
j i 1
7
把矩阵A 记为 A = D – L – U ，则方程组等价为 (D – L)X = ＵＸ＋b ， 从而有： Ｘ = (D – L)-1 UX + (D – L)-1b
9
4.3 迭代法收敛条件与误差估计 矩阵 A 的谱半径：
( A)
max ( A)
max |
1in
i
|
定理4 矩阵 A 的谱半径不超过它的任意一种算子 范数 ||A||，即有：
( A) || A || A Rnn成立。
定理 迭代公式 X(k+1) = BX(k)＋b’ 的解收敛的充 要条件是： Bk 0, k 。
X (k)
||
1 1q
||
X (k1)
X (k)
||
（3） || X * X (k) || qk || X (1) X (0) || 1q
11
定理6 若方程组 AX=b 的系数矩阵 A 按行严格
对角占优，或则，按列严格对角占优，即：
n
| aii | | aij | i 1,2, , n
j 1 ji
17
4.4 逐次超松弛迭代法
AX = b AX = b 记A=D–L–U
(D – L – U)X = b DX - LX = UX + b DX - LX = (1- )DX + UX + b (D - L)X = [(1- )D + U]X + b X= (D - L)-1[(1- )D+U]X+ (D - L)-1b 得到逐次超松弛迭代（SOR）公式：
1 1 2 (B0 )
0.034532 0.38795 0.25863 B 0.012991 0.18048 0.19134
0.014502 0.15400 0.049762
2.5863 b' 2.1306
1.2147
|| B || 0.6811, || B ||1 0.7224,
X(k+1)= (D-L)-1[(1- )D+U]X(k) + (D-L)-1b 迭代矩阵 B= (D-L)-1[(1- )D+U]
18
其中 是松弛因子，当 >1 时为超松弛，当 <1 时为低松弛，当 =1 时即为高斯-赛德尔迭代法。
SOR方法的分量形式： 由G-S迭代有
i 1
n
x(k1) i
（精度要求）
得到满足要求的近似解。
例子：p.55(p.52)例8 ，10-3的精度，迭代10 次。
3x1x12xx22
5 5
x( 1
k
1)
x(k) 2 3
5 3
x2( k
1)
x(k) 1
2
5 2
x(0 1
x2(0
) )
0 0
6
4.2、高斯-赛德尔迭代法 雅可比方法中
X (k1) D1(L U) X (k) D1b
3 / 11 21/ 176 61/ 176
15 / 4
b'
27 /11
135 / 176
|| B || 23 / 16 1.4375, || B ||1 131/ 88 1.49,
|| B ||2 1.23, (B) 0.71
收敛，迭代次数45。
21
取
2
1.03453 ，则迭代矩阵：
迭代矩阵 BG = (D – L)-1 U，b’= (D – L)-1b
高斯赛德尔迭代矩阵BG一般不容易计算，所以实际使用 时采用分量形式的算法，参见程序 GaussSeidelit2.m
例子：p.55(p.52)例8 ，10-3的精度，迭代6 次。
3x1x12xx22
5 5
x(k 1) 1
x(k) 2 3
25
作业： （5）第三章p.73(p.69)第10题；
上机作业： （4）p.182(p.154)第7题。
26
|| B || 0.62875, || B ||1 0.648065375,
|| B ||2 0.52151, (B) 0.1285
收敛，迭代次数 7。
(B0) 0.36 (BGS ) 0.13
23
p.65(p.62)例11：
4 2 4
2 17 10
4 10 X 9
10
或
n
| ajj | | aij | j 1,2, , n
i1 i j
则雅可比迭代法与高斯-赛德尔迭代法都收敛到原 方程的唯一解 X*。
12
定理7 若方程组 AX=b 的系数矩阵 A 对称正定， 则高斯-赛德尔迭代法收敛。
证明提要：A = D – L – U U = LT
迭代矩阵 B = (D – L)-1U 只要证明 (B)<1
（4）Gauss-Seidel迭代法
0 B 0
0
3/8 3 / 22 27 / 176
1/ 4 2 / 11
7
/
88
2.5
b'
2.0909
1.22727
|| B || 0.625, || B ||1 0.66, || B ||2 0.53, (B) 0.13
收敛，迭代次数8。
x(k) i
(bi
a x( k1) ij j
aij
x
( j
k
)
)
/
aii
j 1
ji
不同的 的值会影响SOR迭代的收敛性、收敛 速度。
20
例（7）SOR迭代法
8 3 2 A 4 11 1
6 3 12
取 =1.5，则迭代矩阵：
1 / 2 9 / 16
3 / 8
B 3 /11 71/ 88 15 / 44
收敛，迭代次数82 (精度10-5)。
16
（3）Jacobi迭代法
0
3/ 8 2 / 8
B 4 /11 0 1/11
6 /12 3/12 0
5/ 2
b'
3
3
|| B || 0.75, || B ||1 0.86, || B ||2 0.68, (B) 0.36
收敛，迭代次数14 。
|| B || 20, || B ||1 17, || B ||2 14.4, (B) 13
不收敛。
14
（2）简单构造迭代法-2
8x1 3x2 2x3 20 4x1 11x2 x3 33 6x1 3x2 12x3 36
2
3
4x1 20 4x1 3x2 2x3
9x2 33 4x1 2x2 x3
3
7
2
精 确 解X *
1
1
G S迭代, 75次， (B) 0.877
SOR迭代( 1.46)， 20次， (B) 0.524
又例：
2 1 1
1 3 1
1 1X 2
10
3
7
31/ 3
精 确 解X
*
6
Fra Baidu bibliotek
14 / 3
G S迭 代, 50次 ， (B) 0.7743
|| B ||2 0.5560, (B) 0.153
收敛，迭代次数 8。
(B0 ) 0.36 (BGS ) 0.13
22
取 0.99 ，则迭代矩阵：
0.01 B 0.0036
0.37125 0.12365
0.2475 0.1791
0.004059 0.153165375 0.8818525
§4、迭代法 解 AX = b 等价形式： X = BX + b’ 得到迭代公式： X(k+1)=B X(k)＋b’ 从而由某个初值 X(0)开始逐次计算得到序列 {X(k)}。 B 称为迭代矩阵。 例如，简单迭代法：
X = X-AX+b = (I-A)X + b = BX + b 得到迭代矩阵 B = I-A , b’= b 。
a11 x1 b1 a1 j x j
j 1
a22 x2 b2 a2 j x j
j2
ann xn
bn
anj x j
jn
5
若全部的 aii 0 , i 1,2, , n 则得到迭代公式：
x ( k 1) i
(bi
aij
x
( j
k
)
)
/
aii
i 1,2, , n
ji
当
X (k 1) X (k )
2
4.1、雅可比（Jacobi）迭代法
把矩阵A 记为 A = D – L – U ，则方程组等价为
DX = (Ｌ＋Ｕ)Ｘ＋b ，
若 det(D)0, 则有：
Ｘ = D-1(L + U)X + D-1b
得到雅可比迭代矩阵：
BJ = D-1(L + U)，b’= D-1b 从而，得到雅可比迭代公式：
注意：这里的对角 矩阵的D-1是非常 容易计算的。
举例：
8 4
x1 x1
3x2 2x3 11x2 x3
20 33
6 x1 3 x2 12x3 36
精确解
3 2 1
13
（1）简单迭代法
8 3 2 7 3 2 B I A I 4 11 1 4 10 1
6 3 12 6 3 11 20 b' 33 36