第三章 线性方程组的迭代解法

由表３-３和表３-４可见，达到同样的精度Gauss-Seidel迭代法 要72步，而取ω=1.45的SOR法只要25步，可见当松弛因子选择 适当时，SOR法有明显加速收敛作用，它常用于求解大型线性 方程组。
9
结束
3.3
迭代法的一般形式的收敛条件
x( k 1) Bx( k ) f
3.3.1 一般迭代过程
x( k 1) Bs x( k ) f s
其中
Bs (D L)1U , f s (D L)1b
6
结束
3.2.3 SOR迭代法
SOR迭代法也称为逐次超松弛法，它可看成Gauss-Seidel迭代法 的加速， Gauss-Seidel迭代法是SOR迭代法的特例. 将Gauss-Seidel迭代法的(3.9)式 n bi 1 i 1 ( k 1) ( k 1) (k ) xi aij x j aij x j 改写为 aii aii j 1 j i 1 i 1 n 1 ( k 1) (k ) ( k 1) (k ) bi aij x j xi xi aij x j aii j 1 j i 记 则
x2
x3
0
0
可见它对这一方程组比Jacobi迭代法收敛快一些。
Gauss-Seidel迭代法的公式如下： i 1 n i 1,2, n b 1 ( k 1) ( k 1) (k ) i xi aij x j aij x j k 0,1,2, (3.9) aii aii j 1 j i 1 Gauss-Seidel迭代法的矩阵迭代形式： （推导）
(k ) (k ) x1( k 1) 0.2 x 2 0.1x3 0.3 ( k 1) ( k 1) (k ) 0.1x3 1.5 x 2 0.2 x1 x ( k 1) 0.2 x ( k 1) 0.4 x ( k 1) 2 1 2 3
ri
(k )
x
( k 1) i
x
(k ) i
1 aii
i 1 n ( k 1) (k ) aij x j bi aij x j j 1 j i i 1 n ( k 1) (k ) aij x j bi aij x j j 1 j i
从(3.13)式不难推出SOR法的矩阵迭代形式：
x( k 1) B x( k ) f
其中
B (D L)1[(1 )D U ],
f (D L)1b
今后可以看到，必须取0<ω<2，当ω=1时,就是Gauss-Seidel迭代法 .当ω取得适当时，对Gauss-Seidel迭代法有加速效果. 8 结束
这种迭代形式称为Jacobi迭代法(雅可比迭代法)，也称简单迭 代法. Jacobi迭代法的矩阵迭代形式: (推导)
x( k 1) BJ x( k ) f J
其中
BJ D1 ( L U ),
f J D1b
4
结束
3.2.2 Gauss-Seidel 迭代法
( k 1) x 在Jacobi迭代法的迭代形式(3.6)中，可以看出，在计算 2
的收敛条件.
定理3.1 对任意初始向量x(0)和 f, 由上式产生的迭代序列x(k)收 敛的充要条件是ρ(B) < 1. 证: 1)必要性： x(k)收敛于 x*, 有x*=Bx*+f 成立, 记 k= x(k)- x* 有 k+1= x(k+1)- x* = Bx(k)+ f - Bx* - f = B(x(k) - x*)= Bk 有 k+1= Bk= B2k-1=…= Bk+10, 这里0= x(0)- x*,
(k ) i

aij x
j i

(3.12 ) (3.13)
改写为
x
( k 1) i
i 1 n ( k 1) (k ) （1 ）x bi aij x j aij x j aii j 1 j i 1
称此公式为SOR法 (逐次超松弛法).
3.2 几种常用的迭代法公式 3.2.1 Jacobi迭代法
10 x1 2 x 2 x 3 3 例1 2 x1 10 x 2 x 3 15 x 2 x 5 x 10 1 2 3
从以上三个方程中分别解出x1, x2, x3
x1 0.2 x2 0.1x3 0.3 0.1x3 1.5 x2 0.2 x1 x 0.2 x 0.4 x 2 1 2 3
定理3.2 若 ||B|| =q<1，则由迭代格式x(k+1)=Bx(k)+f 和任意初始 向量x(0)产生的迭代序列x(k)收敛于准确解x*. 本定理是迭代法收敛的充分条件，它只能判别收敛的情况，当 ||B|| ≥1时,不能断定迭代不收敛.但由于||B||,特别是||B|| 1和||B|| ∞ 的计算比较容易，也不失为一种判别收敛的方法。 同时当||B|| <1时可以用来估计迭代的次数，或用来设置退出 计算的条件. 这时有定理3.3和定理3.4 定理3.3 若||B|| =q<1，则迭代格式x(k+1) =Bx(k)+f产生的向量序 k 列 {x(k)}中 q || x ( k ) x * || || x ( 0) x (1) || (3.17) 1 q 利用此定理可以在只计算出x(1)时，就估计迭代次数k，但估 计偏保守，次数偏大. 称为事前误差估计. 12 结束
对任意的 x(0) , 0= x(0)- x* 也是任意的, 因此要有 Bk+100 (k ), 必须有Bk0 (k ) 由上章定理2.8, 必有 (B) <1 .
10 结束
2)充分性：
设 (B) <1 ,则1不是B的特征值, 有| I- B | 0, 于是 ( I- B ) x = f 有唯一解 , 记为x* , 即有 x*=Bx*+f 成立, 则 k+1= B(x(k) - x*)= Bk 仍成立, k+1= B k+10 仍成立,
(k ) ( k 1) 时，要使用 x1 .但此时 x1 已计算出来.看来此时可提前使 (k ) ( k 1) 代替 用 x1 ，一般地，计算 x1
xi( k 1) (n≥i≥2)时，使
用x
( k 1) p
(k ) x 代替 p (i >p≥1)，这样可能收敛会快一些，这就
形成一种新的迭代法，称为Gauss-Seidel迭代法。 例2 用 Gauss-Seidel 迭代法计算例1并作比较. 解 迭代公式为：
1 10 4 2 . 2 2 3 0 .2 0 .1 0 1 解：1）就A1讨论 BJ D ( L U ) 0.2 0 0.1. 0 .2 0 .4 0 10 A1 2 1 4 A2 2 1 2 1 1 , 5 2
由上章定理2.8, 由 (B) <1 , 可得 Bk+1 0 (k ) 成立,
因此 k+1 0 (k ) 成立, 也即是 x(k) x* (k )
•定理3.1是迭代法收敛的基本定理，它不但能判别收敛，也能 判别不收敛的情况.但由于ρ(B)的计算往往比解方程组本身更困 难，所以本定理在理论上的意义大于在实用上的意义. •从上面的定理可以看到,迭代法的收敛与否与B的性态有关， 而与初始向量x(0)和右端向量 f 无关. 由于ρ(B)难于计算，而由定理2.7有ρ(B) ≤||B|| ，||B||<1时, 必 有 ρ(B) <1，于是得到： 11 结束
(k=0,1,2, ) 结束
任取一初始向量，例如 x(0)=(0,0,0)T ，得到迭代序列 {x(k)} (k=0,1,2,)，列表如下表3-1。
k
x1 x2 x3
0
0 0 0
1
2
3
4
5
6
7
8
0.3000 0.8000 0.9180 0.9716 0.9804 0.9962 0.9985 0.9998 1.5000 1.7600 1.9260 1.9700 1.9897 1.9961 1.9986 1.9998 2.0000 2.6600 2.9540 2.9540 2.9823 2.9938 2.9977 2.9997
例3 用Gauss-Seidel迭代法和取ω=1.45的SOR法计算下列方程 组的解，当 max| xi( k 1) xi( k ) | 107 时退出迭代，初值取x(0)=(1,1,1)T 。
4 x1 2 x2 x3 0 2 x1 4 x2 2 x3 2 x 2 x 3x 3 1) ri ( k ) xi( k )
1 aii
7
结束
(k ) 为加快收敛，在增量 ri
前加一个因子
i 1 ( k 1) j n
(0 2), 得
(k ) j
x
( k 1) i
x
(k ) i

bi aij x aii j 1
按下式进行迭代 (k ) (k ) x1( k 1) 0.2 x2 0.1x3 0.3 ( k 1) (k ) (k ) x 0 . 2 x 0 . 1 x 2 1 3 1.5 x ( k 1) 0.2 x ( k ) 0.4 x ( k ) 2 1 2 3 2
定理3.4 若||B|| =q<1 ，则x(k)的第k次近似值的近似程度有如下 q 估计式： || x ( k 1) x * || || x ( k 1) x ( k ) || (3.18)