第四节迭代法 问题的提出 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 迭代格式：