中国矿业大学：《数值分析》课程教学课件（讲稿，研究生）第六章 线性方程组的迭代解法

第六章线性方程组的迭代解法S1 基本选代法S2 共轭梯度法83广义极小残差法1

-1- 第六章 线性方程组的迭代解法 §3 广义极小残差法 §2 共轭梯度法 §1 基本迭代法

8x -3x, + 2x, = 20即Ax = b,精确解：x*=(3,2,1)求解> 4x +11x, -x, = 33一个例子6x +3x, +12x, = 36Jacobi选代法5方案1+矩阵形式：Ax= bx; = #(20 + 3x2 -2x,)3（20）-2)0Ax = b x, = (-4x, + x, +33)888x)x,33-41xs =(-6x, -3x, + 36)0↑X22111111(X3)(X3)36-6-3[x(+) = (20 + 3x() -2x()0(12)(1212+) =(33-4x(* +x()建立迭代：[+) =(36-6x() -3x()x= Mx+gk = 0,1,2,...x(k+1) = Mx(k) + g取初值：x(0)=(0,0,0)x() = (xl",x",xg) =(5 / 2,3,3)"x(2) = (x(2),x(2), x(2)) = (3 / 8,20 / 11,5 / 4))x(10)=(3.000032,1.999838,0.9998813)2

-2- Jacobi迭代法 1 2 3 1 2 3 1 2 3 8 3 2 20 4 11 33 6 3 12 36 x x x x x x x x x               求解 即Ax b  ， (3,2,1)T x  精确解：   方 . 案1 ( 1) ( ) ( ) 1 1 2 3 8 ( 1) ( ) ( ) 1 2 1 3 11 ( 1) ( ) ( ) 1 3 1 2 12 (20 3 2 ) (33 4 ) (36 6 3 ) 0,1,2,. k k k k k k k k k x x x x x x x x x k                   建立迭代： 1 1 2 3 8 1 2 1 3 11 1 3 1 2 12 (20 3 2 ) ( 4 33) ( 6 3 36) x x x Ax b x x x x x x                   1 1 2 2 3 3 3 2 20 0 8 8 8 4 1 33 0 11 11 11 6 3 36 0 12 12 12 x x x x x x                                                           x x g M . (0) (0,0,0)T 取初值：x  (1) (1) (1) (1) 1 2 3 ( , , ) (5 / 2,3,3) T T x x x x   (2) (2) (2) (2) 1 2 3 ( , , ) (3 / 8,20 / 11,5 / 4) T T x x x x   (10) (3.000032,1.999838,0.9998813)T x     x x g ( 1) ( ) k k  M 矩阵形式：Ax b  . 一个例子

x(k+1) =(20 +3x(k) -2x(k)+1)=(33-4x(* +x(0)Gauss-Seidel迭代法方案2[+1) =(36-6x(*) -3x(0)x =$(20 +3x -2xg)= x(0) = (0,0,0),x() = (2.5,3,3)Ax = b x, =(33 -4x, +x,)x, =(36-6x, -3x,)x(10)=(3.00003,1.99983,0.99988)x(k+1) =(20 + 3x(k) =2x(*)Xix(+1) = (33 -4x(*) + x(*)=3x2[rg+1) =(36-6x() ~3x()把已有的结果用上。期待能有更好结果！x(k+1) = (20 +3x(k) -2x(*)x(++1) = (33- 4x(+1) + x(*)建立迭代：x(k+1) = (36 -6x(k+1) - 3x(+)取初值：x(0)=(0,0,0)3

-3- Gauss-Seidel迭代法 ( 1) ( ) ( ) 1 1 2 3 8 ( 1) ( ) ( ) 1 2 1 3 11 ( 1) ( ) ( ) 1 3 1 2 12 (0) (1) (10) (20 3 2 ) (33 4 ) (36 6 3 ) (0,0,0) , (2.5,3,3) . . (3.00003,1.99983,0.99988) k k k k k k k k k T T T x x x x x x x x x x x x                      ( 1) ( ) ( ) 1 1 2 3 8 ( 1) ( ) ( ) 1 2 1 3 11 ( 1) ( ) ( ) 1 3 1 2 12 (20 3 2 ) (33 4 ) (36 6 3 ) k k k k k k k k k x x x x x x x x x                   1 1 2 3 8 1 2 1 3 11 1 3 1 2 12 (20 3 2 ) (33 4 ) (36 6 3 ) x x x Ax b x x x x x x                 (0) (0,0,0)T 取初值：x  建立迭代： ( 1) ( ) ( ) 1 1 2 3 8 ( 1) ( ) 1 2 1 3 11 ( 1) ( 1) 1 ( 1) ( 1) 3 1 2 12 (20 3 2 ) (33 4 ) (36 6 3 ) k k k k k k k k k x x x x x x x x x                     把已有的结果用上, 期待能有更好结果!  方 . 案2

图方案3SOR选代法将G-S选代等价变形：[x(++) =(20 +3x(k) -2x(*)++)=+(3-4x(+) +)x+) =古(36-6x(+) -3x(+)X3[x(++1) = x(*) +(20 -8x() +3x(*) -2x*)x(++1) = x(*) ++(33-4x(+1) -11x(*) + x()心x,x(++1) = x(*) +(36-6x(k+1) -3x(+1) -12x)X3记作：x(k+1) = x(k) +Ax(k) (i=1,2,3,4)x(k+1) = x(*) + 0.Ax(*) (i=1,2,3,4)建立迭代：0(k+1)(k)(20 -8x(k) +3x(k) -2x(k))V8即:0-(k+1)-(k)(33 -4x(+) -11x(* +x(*)3X=3-(k+1)-(k)(36-6x(+) -3x(+1) -12x(*)X3X3a12

-4- SOR迭代法 记作： 将G-S迭代等价变形：  方 . 案3 ( 1) ( ) ( ) 1 1 2 3 8 ( 1) ( ) 1 2 1 3 11 ( 1) ( 1) 1 ( 1) ( 1) 3 1 2 12 (20 3 2 ) (33 4 ) (36 6 3 ) k k k k k k k k k x x x x x x x x x                     ( 1) ( 1) ( ) ( ) 1 1 ( ) ( ) 1 1 ( ) ( ) 2 2 8 2 3 ( 1) ( ) 1 2 1 3 11 ( 1) ( 1) 1 3 ( 1 12 1 2 ( ) ( ) ) 3 3 (20 3 2 ) (33 8 11 1 4 ) (3 ) 6 6 3 2 k k k k k k k k k k k k k k k x x x x x x x x x x x x x x x                            ( 1) ( ) ( ) ( 1,2,3,4) k k k i i i x x x i   建立迭代：      ( 1) ( ) ( ) ( 1,2,3,4) k k k i i i x x x i           即： ( 1) ( ) ( ( ) 1 1 1 3 ) 2 ( ) (20 3 2 ) 8 8 k k k k k x x x x x        ( 1) ( 1) ( ) 2 1 3 ( ) ( ) 2 2 (33 4 ) 11 11 k k k k k x x x x x         ( 1) ( 1) ( 1) 3 1 ) 2 3 ( ( ) 3 (36 6 3 ) 12 12 k k k k k x x x x x         

aux,+a2x,+...+ai.x.=b一常用迭代法a21x+a22x+..+anx,=b1Jacobi迭代法anx,+anx+.+amx,=b假设a，≠0，则从第i个方程中解出x,：ax, +aizx,+..+aix,+...+anx,=bx(k+1)(b -(a2x(k) +.+ anx(*)b, -(ax, +..+anx.))x,ar-(k+1)2 -(a2x(*) +.+a2nx(*)x22 -(a2i +..+a2nxn)a22a22-(k+1)+ -(ax(*) +..+ann-x())b. -(anx, +...+an.n-ixn-)711or.x(+) =(b, -agx),or. x, =(b, -Zagx)(i=1,2,.-,n)(i=1,2, .-,n)一G-S迭代法2x(+) =(b,-2a,x(+) -2 ag()(i=1,2,..",n)Ciai=

- 5 - 一 常 用 迭 代 法 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 i 假设a i x  ，则从第 个方程中解出 1 1 12 2 1   11 1 ( ) n n x b a x a x a     2 2 21 1 2   22 1 ( ) n n x b a x a x a      1 1 , 1 1  1 ( ) n n n n n n nn x b a x a x a         ( 1) ( ) ( ) 1 1 12 2 1 11 1 ( ) k k k n n x b a x a x a        ( 1) ( ) ( ) 2 2 21 1 2 1 22 1 ( ) k k k n x b a x a x a        ( 1) ( ) ( ) 1 1 , 1 1 1 ( ) k k k n n n n n n nn x b a x a x a          1 1 ( ) ( 1,2, , ) n i i ij j j ii j i x b a x i n  a       ( 1) ( ) 1 1 ( ) ( 1,2, , ) n k k i i ij j j ii j i x b a x i n a        i i ii i in n i 1 1 2 2 a x a x a x a x b        or .  or. 1 Jacobi 迭 代 法 2 G-S 迭 代 法 1 ( 1) ( ) 1 1 ( 1) 1 ( ) ( 1,2, , ) i n k k i i ij j ij j j j i k ii x b a x a x i n a             