《计算方法》第三章（3-4）迭代法

第四节迭代法 问题的提出 1.直接方法(以 Gauss消去法为代表)的缺陷: 对于低阶或中等阶数(n≤100)的线性方程组十分有 效,但当n较大时,特别是由某些微分方程经离散 后得到的线性方程组,由于舍入误差的积累以及计 算机的存贮困难,直接方法变得无能为力 2.解决方法:(利用迭代方法) 迭代方法:把线性方程组的数值求解问题,化为 个迭代序列来实现,类似于非线性方程迭代法的思 想 具体做法 ①Ax=bx=Mx+g ②取任意初始向量x构成迭代序列: (k+1 1)=Mx)+g k=0.1. (*1) 若x)→x'(k→∞),则有 X M欢x+g (*2) 即x为Ax=b的解 迭代矩阵:矩阵M.(*2)也称为迭代格式

第四节 迭代法 一、 问题的提出 1. 直接方法（以 Gauss 消去法为代表）的缺陷： 对于低阶或中等阶数 (n  100) 的线性方程组十分有 效，但当 n 较大时，特别是由某些微分方程经离散 后得到的线性方程组，由于舍入误差的积累以及计 算机的存贮困难，直接方法变得无能为力. 2. 解决方法：（利用迭代方法） 迭代方法：把线性方程组的数值求解问题，化为一 个迭代序列来实现，类似于非线性方程迭代法的思 想. 具体做法 ① Ax = b  x Mx g = + ② 取任意初始向量 (0) x 构成迭代序列： ( 1) ( ) k k x Mx g + = + ， k = 0,1,  (*1) 若 ( ) ( ) * x → x k →  k ，则有 * * x Mx g = + . (*2) 即 * x 为 Ax = b 的解. 迭代矩阵:矩阵 M . (*2)也称为迭代格式

若序列{xn}的极限存在,则称此迭代过程收敛,否 则称为发散 常用的迭代方法 ● Jacobi迭代方法 1. Jacobi迭代方法的具体形式 设有n阶线性方程组 Guixi+a 12 x+∴+a1x In n c21X1+c22x2+ t a2n anx1+anx2+.+annen=bn ≠0(i=0,1,2,…n) 3x3 a1nxn+b) II x +b2) Ca. Ix mn-n- +bn) 建立迭代格式:

若序列 { }n x 的极限存在，则称此迭代过程收敛，否 则称为发散. 二．常用的迭代方法 ⚫Jacobi 迭代方法 1. Jacobi 迭代方法的具体形式 设有 n 阶线性方程组 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 n n n n n n nn n n a x a x a x b a x a x a x b a x a x a x b  + + + =   + + + =     + + + = 0 ii a  ( 0,1, 2, ) i n =  1 12 2 13 3 1 1 11 2 21 1 23 3 2 2 22 1 1 1 1 1 ( ) 1 ( ) 1 ( ) n n n n n n ni i nn n n nn x a x a x a x b a x a x a x a x b a x a x a x a x b a − −  = − − − − +     = − − − − +     = − − − − − +   建立迭代格式：

(k+1) (k) 12 aInm)+b1) antm+b2) 22 (k+1 xm +bm) 或缩写为: (k+1) (k) (k) +b) 用此迭代格式求解的方法叫雅可比( Jacobi)迭代 法,又称简单迭代格式。 分解A=(an)为 A=D-L-U 其中 0 0-a1 0 L= n-1,n n n d=diag(au, a 2

( 1) ( ) ( ) ( ) 1 2 3 12 13 1 1 11 ( 1) ( ) ( ) ( ) 2 1 3 21 23 2 2 22 ( 1) ( ) ( ) ( ) 1 1 1 ( ) 1 ( ) 1 ( ) k k k k n n k k k k n n k k k k n n ni i nn n n nn x a x a x a x b a x a x a x a x b a x a x a x a x b a + + + − −  = − − − − +     = − − − − +     = − − − − − +   或缩写为： 1 ( 1) ( ) ( ) 1 1 1 ( ) i n k k k i ij j ij j i ii j j i x a x a x b a − + = = + = − − +   ( 1, , ) i n = 用此迭代格式求解的方法叫雅可比（Jacobi）迭代 法，又称简单迭代格式。 分解 ( ) A = aij 为 A = D− L −U 其中             − − − = − 0 0 0 0 1 , 1 21 n n n a a a L                 − − − = − 0 0 0 0 1, 12 1 n n n a a a U     ( , , , ) D = diag a11 a22  ann

变形Ax=b分>Dx=Lx+Ux+b →x=D(Lx+Ux+b) 故雅可比迭代格式可写成矩阵形式: (+=D(L+U)x)+D-b 迭代矩阵 0 12 M=D(L+U)=a22 22 2 0 nn 2. Gauss- seidle迭代方法的具体形式 (k+1) (k) (k) 122 133 +b) (k) +b2 (k+1) (amx(+l 即在计算新分量xk+1)时,利用了新值xk+1)

变形 Ax = b  Dx = Lx +Ux +b 1 x D Lx Ux b ( )  = + + − 故雅可比迭代格式可写成矩阵形式： ( 1) 1 ( ) 1 ( ) k k x D L U x D b + − − = + + 迭代矩阵 12 1 11 11 21 2 1 22 22 1 2 0 0 ( ) 0 n n J n n nn nn a a a a a a M D L U a a a a a a −   − −       − −   = + =         − −   2. Gauss—Seidle 迭代方法的具体形式 ( 1) ( ) ( ) ( ) 1 2 3 12 13 1 1 11 ( 1) ( 1) ( ) ( ) 2 1 3 21 23 2 2 22 ( 1) ( 1) ( 1) ( 1) 1 1 1 ( ) 1 ( ) 1 ( ) k k k k n n k k k k n n k k k k n n ni i nn n n nn x a x a x a x b a x a x a x a x b a x a x a x a x b a + + + + + + + − −  = − − − − +     = − − − − +     = − − − − − +   即在计算新分量 ( 1) k x i + 时，利用了新值 ( 1) k x j +

j=1,2,…,i-1,上面这种迭代法称为 Gauss Seidel迭代方法。 E (k+1) (k) 或缩写为: lI 故 Gauss- seide迭代的矩阵形式为: x(+)=D1(Lx4)+b)+Db (k+1) D Tr(k) +d b →Dx(k+1 (+1)=Ux)+b →(D-D)x+)=U()+b →x4+)=(D-D)b)+(D-D)b 称MG=(D-D)U为Gaus- seidel法的迭代 矩阵。 513 241‖x 例:求 4611八x 的 Jacobi迭代格式 和 Gauss- Seidel迭代格式。 解: Jacobi迭代格式:

j i = − 1, 2, , 1 ， 上 面 这 种 迭 代 法 称 为 Gauss — Seidel 迭代方法。 或缩写为： [ ] 1 1 ( ) 1 1 ( 1) ( 1)  = + − = + + = − − n j i k i j j i j k i i j j i i k i b a x a x a x 故 Gauss—Seidel 迭代的矩阵形式为： ( 1) 1 ( 1) ( ) 1 ( ) k k k x D Lx Ux D b + − + − = + + ( 1) 1 ( 1) 1 ( ) 1 k k k x D Lx D Ux D b  − = + + − + − − ( 1) ( 1) ( ) k k k Dx Lx Ux b  − = + + + ( 1) ( ) ( ) k k D L x Ux b  − = + + ( 1) 1 ( ) 1 ( ) ( ) k k x D L Ux D L b  = − + − + − − 称 1 ( ) M D L U G − = − 为 Gauss—Seidel 法的迭代 矩阵。 例：求           =                    − 3 2 1 4 6 11 2 4 1 5 1 3 3 2 1 x x x 的 Jacobi 迭代格式 和 Gauss-Seidel 迭代格式。 解：Jacobi 迭代格式：

5x1+x2+3x 由原方程{2x1+4x2+x3=2 4x1+6x2+11x3=3 2=(2-2x1-x3) 4 (3-4x1-6x2) (k+1) 3x (k) 2 →{x2 (k+1) (2-2 4 r,(3-4x1 (k)_6x Gauss- Seidel迭代格式: 2 →{x2=(2-2x1-x3) 原方程组为 x (3-4x1-6x2)

由原方程 1 2 3 1 2 3 1 2 3 5 3 1 2 4 2 4 6 11 3 x x x x x x x x x  − + + =   + + =   + + =          = − − = − − = − − −  (3 4 6 ) 11 1 (2 2 ) 4 1 (1 3 ) 5 1 3 1 2 2 1 3 1 2 3 x x x x x x x x x          = − − = − − = − − −  + + + (3 4 6 ) 11 1 (2 2 ) 4 1 (1 3 ) 5 1 ( ) 2 ( ) 1 ( 1) 3 ( ) 3 ( ) 1 ( 1) 2 ( ) 3 ( ) 2 ( 1) 1 k k k k k k k k k x x x x x x x x x Gauss-Seidel 迭代格式： 原方程组为          = − − = − − = − − −  (3 4 6 ) 11 1 (2 2 ) 4 1 (1 3 ) 5 1 3 1 2 2 1 3 1 2 3 x x x x x x x x x

(k+1) X 3x (k+1) (2-2x1 (k+1) 4 (k+1) (3-4x1-6x2) 、序列{x6}收敛的条件 定理6:Wx0∈R",常向量g,迭代过程 x{k+)=M()+g收敛台p(M)<1.p(M)为矩 阵M的谱半径P(M)=max4|<1,为矩阵M l≤i<n 的特征值。 例:设方程组Ax=b的系数矩阵A为 A=(3413/4 3/43/41 判别雅可比迭代与高斯-塞德尔迭代是否收敛。 0-3/4-3/4 解:①M=D(L+U)=-3/40-3/4 40 求M的特征值:

         = − − = − − = − − −  + + + + + + (3 4 6 ) 11 1 (2 2 ) 4 1 (1 3 ) 5 1 ( 1) 2 ( 1) 1 ( 1) 3 ( ) 3 ( 1) 1 ( 1) 2 ( ) 3 ( ) 2 ( 1) 1 k k k k k k k k k x x x x x x x x x 二、序列 { } (k ) x 收敛的条件 定 理 6 ： n x  R (0) ， 常向量 g ， 迭 代 过 程 ( 1) ( ) k k x Mx g + = + 收敛  ( ) 1 M  . ( ) M 为矩 阵 M 的谱半径. 1 ( ) max 1 i i n   M   =  ， i 为矩阵 M 的特征值。 例：设方程组 Ax b = 的系数矩阵 A 为 1 3 4 3 4 3 4 1 3 4 3 4 3 4 1 A     =       判别雅可比迭代与高斯-塞德尔迭代是否收敛。 解：① 1 0 3 4 3 4 ( ) 3 4 0 3 4 3 4 3 4 0 M D L U J −   − −   = + = − −       − − 求 M J 的特征值：

λ3/43/4 A/-M/=3443/4=232320 27 16 3y43/4 49 =-1,I-M132 0 121 A=-2,|-M 1,雅可比迭代 不收敛。 ②MG=(D-L)U 0 0 1-01 3/43/4 03/41-3/4 →)01|-3/4 01|-316-3/41

3 3 4 3 4 27 27 3 4 3 4 0 16 32 3 4 3 4 J I M       − = = − + =  = −1 ， 49 0 32 J I M− =   = −2 ， 121 0 32 J I M− = −  故  有一值于 ( 2, 1) − − 中， ( ) 1  M J  ，雅可比迭代 不收敛。 ② 1 ( ) M D L U G − = − 1 1 0 3 4 3 4 3 4 1 0 3 4 3 4 3 4 1 0 −     − −     = −             1 1 1 1 3 4 1 1 0 1 3 4 1 3 4 3 4 1 1 0 3 4 1 3 4 1         → −         −     1 1 0 1 3 4 1 0 0 1 3 16 3 4 1     → −     − −  

即|3/41 3/16-3/4 0-3/4-3/ 3/16-3/41 0 3/4-3/4 09/16-3/16 09/6445/64 A-M=02-9/163/6=0 0-9/642-45/64 解得:2(228127 +-,)=0 6464 不1=0,223=0.633±0.1461 P(MG)=max ai< l≤i<3 高斯-塞德尔迭代收敛 注:由于对 Gauss- Seidel迭代法而言,其特征矩

即 1 1 1 3 4 1 3 4 1 3 4 3 4 1 3 16 3 4 1 −         = −             − − 1 0 3 4 3 4 3 4 1 0 3 4 3 16 3 4 1 0 MG    − −    = − −          − − 0 3 4 3 4 0 9 16 3 16 0 9 64 45 64   − −   = −       3 4 3 4 0 9 16 3 16 0 0 9 64 45 64 G I M     − = − = − − 解得： 2 81 27 ( ) 0 64 64    − + = 1 2,3   = =  0, 0.633 0.146i  1 3 ( ) max 1 G i i   M   =  高斯-塞德尔迭代收敛。 注：由于对 Gauss-Seidel 迭代法而言，其特征矩

阵必须求出(D-L)2。以下介绍一种等价的求其特征 值的方法。 I2I-MG=(D-L)n(D-L)-(D-L)UI (D-L) 2(D-l)-Ul 考虑到,前一个矩阵的行列式不会为0(在本章开 始就已经假设A≠0),那么只需第二个行列式为0 即可。即:|A(D-L)-U=0而该方程无须求(D-L) 也能求出矩阵M的特征值 (D-L)-U=0 即 12 22 0 定理7若迭代矩阵M的某种范数M‖-=q<1,则 迭代方法x+)=M)+g,k=01有如下误 差估计 ≤ x q

阵必须求出 1 ( ) − D − L 。以下介绍一种等价的求其特征 值的方法。 |( ) | | ( ) | | | |( ) ( ) ( ) | 1 1 1 D L D L U I MG D L D L D L U = −  − − − = − − − − − − −    考虑到，前一个矩阵的行列式不会为 0（在本章开 始就已经假设 | A| 0 ），那么只需第二个行列式为 0 即可。即： | (D − L) −U |= 0.而该方程无须求 1 ( ) − D − L ， 也能求出矩阵 MG 的特征值. | (D − L) −U |= 0 即 11 12 1 21 22 2 1 2 0 n n n n nn a a a a a a a a a       = 定理 7 若迭代矩阵 M 的某种范数 M q = 1 ，则 迭代方法 ( 1) ( ) k k x Mx g + = + ， k = 0,1,  有如下误 差估计 * ( ) ( ) ( 1) 1 − − − −  k k k x x q q x x