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

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。52.(k)例1判断迭代格式x(k+1)的收敛性。3020解·迭代矩阵M=032-2=22-6=0:. f(a)=aE-M)元-3.. 2 = ~6,2, = -/6:: p(M)= max(I a, Il,I a, I) = /6 >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