数值分析课件：ch03方程组迭代法

1、1第三章线性方程组的数值解法-迭代法Iterative techniques for linear equations2q 直接法得到的解是理论上准确的，但是计算量都是直接法得到的解是理论上准确的，但是计算量都是 n3 n3数量级，存储量为数量级，存储量为n2n2量级，这在量级，这在n n比较小的时候比较小的时候 还比较合适（还比较合适（n400n=1.0e6&nM x= y; y=B*x+f; n=n+1;end17高斯高斯塞德尔塞德尔( (Gauss-Seidel) )迭代法迭代法 q q 研究雅可比迭代法，我们发现在逐个求研究雅可比迭代法，我们发现在逐个求 的分量时，的分量时，

2、当计算到当计算到 的分量时，当计算到的分量时，当计算到 都都 已经求得已经求得. .设想一旦新分量代替旧分量，可能会加速收敛。设想一旦新分量代替旧分量，可能会加速收敛。 例如例如 (1)kX(1)kix(1)(1)11,kkixx(1)( )( )( )13112121311111111(1)(1)( )( )23221213222222222kkkknnkkkknnaaabxxxxaaaaaaabxxxxaaaa 18)(11)(1)(414)(313)(21211)1(1bxaxaxaxaaxknnkkkk )(12)(2)(424)(323)1(12122)1(2bxaxaxaxaaxk

3、nnkkkk )(13)(3)(434)1(232)1(13133)1(3bxaxaxaxaaxknnkkkk )(1)1(11)1(33)1(22)1(11)1(nknnnknknknnnknbxaxaxaxaax Gauss-Seidel迭代法分量形式迭代法分量形式 19Gauss-Seidel迭代的矩阵形式迭代的矩阵形式bLDUxLDxbLDUxLDxbUxxLDbxULDbAxkk1)(1)1(11)()()()()()(作作 A 的另一个分裂：的另一个分裂：()ADLUq 迭代矩阵迭代矩阵 1GBDLU20例子例子1231231231023210152510 xxxxxxxxx(1)

4、( )( )123(1)(1)( )213(1)(1)(1)3121(23)101(215)101(210)5kkkkkkkkkxxxxxxxxx解：解：相应的高斯相应的高斯- -赛德尔迭代公式为赛德尔迭代公式为21取迭代初值取迭代初值(0)(0)(0)(0)123(,)(0,0,0)TTXxxx按此迭代公式进行迭代，计算结果为按此迭代公式进行迭代，计算结果为k( )1kx( )2kx( )3kx01234500.30.88040.98430.99780.999701.561.94451.99231.99891.999902.6842.95392.99382.99912.999922迭代法的收

5、敛性迭代法的收敛性 迭代法的收敛性迭代法的收敛性，是指方程组是指方程组bAx q 从任意初始向量从任意初始向量X X(0)(0)出发，由迭代算法出发，由迭代算法fBxxkk)()1(算出向量序列算出向量序列,)1()()2()1(kkxxxx随着随着k k的增加而趋向于解向量的增加而趋向于解向量X X * *。q 记各次记各次误差向量误差向量)()1(1)0(0kkXXXXXX 23迭代法的收敛性迭代法的收敛性 q 迭代法的收敛性等价于误差向量序列迭代法的收敛性等价于误差向量序列,10k 随着随着k k的增加而的增加而趋向于零趋向于零。q 由由 x(k+1)=Bx(k)+f 及及 x*=Bx*

6、+fk+1 =X(k+1)-X*=B（X(k)-X*） = = B k+1（X(0)-X)=B k+1 0 可推知可推知q x x( (k k) ) 的收敛性的收敛性 B Bk k 0 0 ( (k k ) ) 24迭代法的收敛性定理迭代法的收敛性定理 q 定理定理 (充要条件判别法充要条件判别法)给定方程组给定方程组 X=BX+f则迭代公式则迭代公式(1)( )kkXBXf对任意初始向量对任意初始向量 ，都收敛的充要条件为，都收敛的充要条件为(0)nXR( )1B性质有关。性质有关。的的代矩阵代矩阵的取值无关，而只与迭的取值无关，而只与迭和和与与法收敛与否法收敛与否表明，线性方程组迭代表明，

7、线性方程组迭代定理定理 1 . 3 )0(BfXq 25q 迭代法的收敛性定理迭代法的收敛性定理 定理定理 ( (充分条件判别法充分条件判别法) )给定方程组给定方程组 X=BX+f如果如果 ，则迭代公式，则迭代公式1B 1. 对任意初始向量对任意初始向量 收敛。收敛。(0)nXR(1)( )kkXBXf2. 有如下估计有如下估计( )*( )(1)1,2,3,1kkkBXXXXkB26证明证明 111*( *)( *)kkkkkxxB xxB xxxx111| *| | |(| *| |)kkkkx xBx xxx11| *|1 |kkkBxxxxB27注注 q 由于此估计式，在实际计算中，

8、用 | | X X (k+1) - (k+1) - X X (k) | (k) | 作为迭代终止条件是合理的。 q ( )(1)(0)*1kkBXXXXB进一步可以推知：由于( (B B) ) B B11，B越小，说明(B) 越小，序列 X (k)收敛越快。28收敛速度收敛速度下面我们给出收敛速度的概念下面我们给出收敛速度的概念： 定义定义 R R( (B B)= -)= -lnln( (B B) )，称为迭代法的渐进，称为迭代法的渐进 收敛速度。收敛速度。q 由于由于Gauss-Seidel迭代法逐次用计算出来的新迭代法逐次用计算出来的新值代替旧值，所以在收敛的条件下，它要比值代替旧值，所以

9、在收敛的条件下，它要比Jacobi迭代法收敛速度快。迭代法收敛速度快。29Jacobi Jacobi 和和Gauss-SeidelGauss-Seidel的收敛性的收敛性1.() 1 ()1 ;JGAXbJacobi SeidelBB解解线线性性方方程程组组的的迭迭代代法法收收敛敛的的充充要要条条件件是是2. 1 1 JGAXbJacobi SeidelBB解解线线性性方方程程组组的的迭迭代代法法收收敛敛的的充充分分条条件件是是。 ULDBULDBGJ11, 其中其中301311211111123221222222313233333331230000nnJnnnnnnnnnnaaaaaaaaa

10、aaaBaaaaaaaaaaaa注注 31525110101021011020JB对于前面的例子由迭代矩阵的特征方程由迭代矩阵的特征方程05211102121012311717,51010 因而雅可比迭代公式是收敛的。因而雅可比迭代公式是收敛的。32注注 的特征值。因而可由此式求解等价于因此由于因为：可避开求逆矩阵的特征值法迭代阵求BULDBILDULDLDULDLDLDBILDULDB0)(det(0)det(0)det()(det()det()()()det()det()()( S-G 11111133直接用矩阵直接用矩阵A A判定敛散性判定敛散性q q 定义定义 如果矩阵如果矩阵A A满

11、足条件满足条件(1,2, )(2)iiijj iaain则称则称A A是是严格对角占优阵严格对角占优阵(strictly diagonally dominant (strictly diagonally dominant matrix)matrix)；342100110114100141001410014BAA为按行按列为按行按列严格严格对角占优阵；对角占优阵；B为按行对角为按行对角占优阵。占优阵。实例实例(Example)(Example)35定理定理1 1 若若A A为为严格对角占优阵严格对角占优阵，则，则J Jacobiacobi 迭代法迭代法和和 G-SG-S迭代法迭代法收敛。收敛。

12、定理定理2 2 若若A A为为对称正定阵对称正定阵，则，则G-SG-S迭代法收敛迭代法收敛。 相关定理相关定理q q 36定理1的证明证 首先证明首先证明JacobiJacobi 迭代的收敛性。由迭代的收敛性。由nnnJnnnnnnnnJabababfaaaaaaaaaaaaULDB22211121222222111111121,000)(易求ijnjiiijniJaaB,11max 由严格对角占优定义，得由严格对角占优定义，得 B BJ J 1, = detdet( ( ( (D-LD-L)-)-U U)=0 )=0 38 我们通过我们通过A A的严格对角占优性质去证明的严格对角占优性质去证

13、明detdet( ( ( (D-D-L L)-)-U U)=0)=0的根的根 有性质有性质 | | |1 |1。用。用反证法反证法：假设：假设| | |1 |1，且由于，且由于A A的严格对角占优性质，有的严格对角占优性质，有 niaaaanijijijijnijjijii, 2 , 1,111, 1nnnnaaaaaaaaaULD21112221111111)(39是严格对角占优阵，所以它是非奇异的，即det(D-L)-U) 0与特征值满足det(D-L)-U) =0 矛盾。故 | |1即(BG) 11 时，称为时，称为超松弛算法超松弛算法，当，当11 时，时，称为称为亚松弛算法亚松弛算法。

14、 目前，还没有自动选择因子的一般方法，实目前，还没有自动选择因子的一般方法，实际计算中，通常取（际计算中，通常取（0 0，2 2）区间内几个不同的）区间内几个不同的值进行试算，通过比较后，确定比较理想的松弛值进行试算，通过比较后，确定比较理想的松弛因子因子。 46例例 用用SORSOR法求解线性方程组法求解线性方程组 243024410143034321xxx 取=1 ，即Gauss-Seidel迭代： 625. 05 . 725. 075. 0675. 0)1(2)1(3)(3)1(1)1(2)(2)1(1kkkkkkkxxxxxxx 取=1.25 ，即SOR迭代法： 5 . 725. 03

15、125. 075. 93125. 025. 09375. 05 . 79375. 025. 0)(3)1(2)1(3)(3)(2)1(1)1(2)(2)(1)1(1kkkkkkkkkkxxxxxxxxxx47例例 迭代结果见表3.3。 表3.3 Gauss-Seidel迭代法与SOR迭代法比较 Gauss-Seidel迭代法SOR迭代法(=1.25)kx1x2x3x1x2x301.00000001.00000001.00000001.00000001.00000001.000000015.25000003.1825000-5.04687506.31250003.9195313-6.650146

16、523.14062503.8828125-5.02929692.62231453.9585266-4.600423833.08789063.9267587-5.01831053.13330274.0402646-5.096686343.05493163.9542236-5.01144102.95705124.0074838-4.973489753.03433233.9713898-5.00715263.00372114.0029250-5.005713563.02145773.9821186-5.00447032.99632764.0009262-4.998282273.01341103.98

17、88241-5.00279403.00004984.0002586-5.000348648 迭代法若要精确到七位小数，迭代法若要精确到七位小数，u Gauss-SeidelGauss-Seidel迭代法需要迭代法需要3434次迭代；次迭代；u 而用而用SORSOR迭代法迭代法( (=1.25)=1.25)，只需要，只需要1414次迭代。次迭代。 可见，若选好参数可见，若选好参数，SORSOR迭代法收敛速度会迭代法收敛速度会很快。很快。q 49SOR迭代的矩阵形式：迭代的矩阵形式：inijkjijijkjijiikikibxaxaaxx)(11)1()()1(X(k+1) =(1-)X(k)+D

18、-1(b+LX(k+1)+UX(k)DX(k+1) =(1-)DX(k)+(b+LX(k+1)+UX(k)）(D-L)X（k+1） =(1-)D+U X(k)+b解得解得 X(k+1)=(D-L)-1(1-)D+UX(k)+(D-L)-1b 记记 B=(D-L)-1 (1-)D+U 称为称为SORSOR法迭代矩阵法迭代矩阵。 50SOR迭代法的收敛性迭代法的收敛性q (1)SOR法收敛的充要条件是法收敛的充要条件是(B)1。(2) SOR法收敛的充分条件是法收敛的充分条件是 | B|1。 q 解线性方程组，解线性方程组，SORSOR法收敛的必要条件是法收敛的必要条件是 |1-|1-| 1 | 1 ，即，即 00 2 2。 q 设设A AR Rn n n n对称正定，且对称正定，且 0022，则，则SORSOR法对任意法对任意的初始向量都收敛。的初始向量都收敛。 51注注q 通过比较后，确定比