第六章线性方程组的迭代解法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
3SOR选迭代法x(+) =(b,-2ag(+)-2ag)(i=1,2,.",n)i==i+1↑x(+) =X+(b,-2ax(+)-2ag().(i =1,2,...,n)a:x(+) = , +0(b,-Za,x+)-2ag/),二(i=1,2,",n)令：-其中，の为松弛因子；の=1，G-S迭代法；の>1，超松驰迭代法；の<1，低松弛迭代法。小-6
- 6 - 3 SOR迭 代 法 1 ( 1) ( 1) ( ) 1 1 1 ( ) ( 1,2, , ) i n k k k i i ij j ij j j i i i j x b a x a x i n a 1 ( 1) ( 1) ( ) 1 1 ( ) ( 1,2, , ) i n k k k i i i ij j ij j j j i ii x x b a x a x i n a 1 ( 1) ( 1) ( ) 1 1 ( ) ( 1,2, , ) i n k k k i i i ij j ij j j j i ii x x b a x a x i n a 令 ： 其中，为松弛因子； 1 G-S ， 迭代法； 1，超松弛迭代法； 1，低松弛迭代法
二迭代法的矩阵形式对Ax=b，将A进行分解：0an0-ain-0112-a13..00a22-a21123-2n0A=0D-L-Ua3331-a32-3n:0aun-a,-an2-.3则Ax =b 台(D- L-U)x=b Dx =b+(L+U)x x = D-'(b+(L+U)xJacobi选代法2 G-S迭代法(+1) = D-'(b+ Lx(k+1) + Ux()x(k+1) = D-'(b+(L+ U)x()= D-'b+ D-'(L+ U)x(k)=→(D- L)x(k+1) =(b+Ux(k)=x(+1) =(D- L)-'(b+ Ux(k))= D-'b + D-'(D - A)x(k)= x(k+1) =(D- L)'Ux(k) +(D- L)-" b=(E - D-'A)x(k) + D-'bx(k+1) = x(k) +D-'(b+ Lx(+1) + Ux(k) - Dx(k)SOR迭代法3= x(k+I) =(D-L)-'[(1-0)D+ wU]x(k) + 0(D-OL)-"b
- 7 - 1 x D b L U x ( ) 二 迭代法的矩阵形式 对Ax b A ，将 进行分解： 11 12 13 1 22 21 23 2 33 31 32 3 1 2 3 0 0 . 0 0 . 0 0 . . . 0 0 nnn nn n n n a a a a a a a a A a a a a a a a a D L U 则 Ax b ( ) D L U x b Dx b L U x ( ) 1 Jacobi迭代法 ( 1) 1 ( ) ( ) k k x D b L U x 1 1 ( ) ( ) k D b D L U x 1 1 ( ) ( ) k D b D D A x 1 ( ) 1 ( ) k E D A x D b 2 G-S迭代法 ( 1) 1 ( 1) ( ) k k k x D b Lx Ux ( 1) ( ) ( ) k k D L x b Ux ( 1) 1 ( ) ( ) k k x D L b Ux ( 1) 1 ( ) 1 ( ) ( ) k k x D L Ux D L b 3 SOR迭代法 ( 1) ( ) 1 ( 1) ( ) ( ) k k k k k x x D b Lx Ux Dx ( 1) 1 ( ) 1 ( ) (1 ) ( ) k k x D L D U x D L b
综上可见，三种迭代法可统一为xk+1 = Mxk + g其中，M为迭代矩阵：M,=(E-D-A);MG-s =(D- L)-'U;MsoR =(D-wL)-"[(1 -)D+ wU]迭代法的矩阵形式8-
- 8 - 综上可见，三种迭代法可统一 为： x x g k k 1 M 其 中，M 为 迭代 矩 阵: 1 M ( ); J E D A 1 M ( ) ; G-S D L U 1 M ( ) (1 ) ; SOR D L D U -迭代 法 的 矩 阵 形 式
三迭代法的收敛性1基本概念1）向量序列极限设x() -(x,x*",.,x()" e R" (k = 0,1, .,x* -(x,x2,x)" e R",若 lim x(k)=x,(i=1,,n)，则称向量序列x收敛于x，记作：lim x=xk-→+0k→+0o2）选代法的收敛性设x(k)是由迭代公式xk+1=Mx+g生成的向量序列，若limx(k)存在：k->+00则称迭代法收敛，否则发散，且收敛时有x=limx(k)。k-→+003）定理(补充)limx=x"台limx-x*J=0，其中·为向量任一范数。k-→+00lim x* = x 台 lim / x(k) -x(" = 0,(i = 1,,n)k-→+00k>t范数的等价性台 lim max |x(k) - x(" [= 0k→+00台 lim x*-x*m=0lim Ilx-x=0-9.k-→>+00
- 9 - 三 迭代 法 的 收 敛 性 1 基 本 概 念 1 ） 向 量 序 列 极 限 ( ) ( ) ( ) ( ) * * * 1 2 1 2 ( ) * * * , , , ( 0,1, ), , , , lim ( 1, , ) lim . T T k k k k n n n n k k k i i k k x x x x R k x x x x R x x i n x x x x 设 ， 若 ，则称向量序列 收敛于 ，记作： ( ) 1 ( ) * ( ) M lim lim k k k ki k k k x x x g x x x 设 是由迭代公式 生成的向量序列，若 存在， 则称迭代法收敛，否则发散，且收敛时有 。 2）迭代法的收敛性 3 ( ) ）定理 补充 * * lim lim || || 0 || || k k k k x x x x ，其中 为 向量任一范数。 * lim k k x x * lim || || 0 k k x x ( ) (*) lim max | | 0 k i i k i x x * lim || || 0 k k x x ( ) (*) lim | | 0,( 1, , ) k i i k x x i n 范数的等价性
2判别条件1）收敛基本定理【充要条件,P131-Th1.1】x(k+1) = Mx(k) + g对任意初值收敛 p(M)=maxa,[1, 选代发散!-10-
-10- 2 判别条件 1 P131 Th1.1 ）收敛基本定理【充要条件, - 】 ( 1) ( ) M ( ) max 1 k k i x x g M 对任意初值收敛 。 ( 1) ( ) 0 2 5 1 3 0 5 k k x x 例 判断迭代格式 的收敛性。 解 0 2 M 3 0 迭代矩阵 f E ( ) | M | 1 2 6, 61 2 (M) max(| |,| |) 6 1, 迭代发散！ 2 3 2 6 0