吉林大学：《计算方法》课程电子教案（PPT课件）第五章 解线性代数方程组的迭代法 5.3 SOR迭代法

第三节SOR迭代法 SOR迭代格式 二SOR迭代法的收敛性

第三节 SOR 迭代法 一、 SOR 迭代格式 二 SOR 迭代法的收敛性

SOR 迭代格式 SOR是Succesive Over Re laxation (逐次超松弛) 的缩写。SOR迭代法是解大型稀疏矩阵方程组的有效 方法之一。它可以看作是Gass-Seidel迭代法的加 速，Gauss--Seidel迭代法是SOR迭代的一种特殊形式

一、 SOR 迭代格式 SOR 是 ( 逐次超松弛 ) 的缩写。 SOR 迭代法是解大型稀疏矩阵方程组的有效 方法之一。它可以看作是 Gauss Seidel − 迭 代 法 的加 迭代法是 迭代的一种特殊形式。 Succesive Over R laxation e 速， Gauss Seidel − SOR

将方程组AX=b写成 anx +ax2++a+ax+amxn =b, (i=1,2,…,n) 则有 →anx,=b-(ax1+a2x2+…+a-x -(ax4l++anxn） aux =ax;+(b-anx-ax2-.-a-xi- -anx-ai-ainxn) →x=x+6-8,-a--8X aixi-ai-ainxn) 其Gauss--Seidel迭代格式可写为(a,≠0)：

将方程组 AX b = 写成 1 1 2 2 , 1 1 , ( 1, 2, , ) i i i i i ii i in n i a x a x a x a x a x b i n + + + + + = − − = ( 0) 其 Gauss Seidel − 迭 代 格 式 可写为 aii  ： 1 1 2 2 , 1 1 , 1 1 1 ( ) i i i i i i i i ii ii i i i i in n x x b a x a x a x a a x a x a x − − + +  = + − − − − − − − − ( ) ( ) 1 1 2 2 , 1 1 , 1 1 1 1 2 2 , 1 1 , 1 1 ( ) ii i i i i i i i i i i in n ii i ii i i i i i i i ii i i i i in n a x b a x a x a x a x a x a x a x b a x a x a x a x a x a x − − + + − − + +  = − + + + − + +  = + − − − − − − − − 则有

x=x+(6-a (k+1 -a-ix-ax--anx） 0 (3.) 若记 9=6-a"-之》 i=1,2,…,n 则(3.1)式可写为 x+=x0 +二 (3.2) d

若记 1 ( ) ( 1) ( ) 1 ( ), i n k k k i i ij j ij j j j i r b a x a x − + = = = − −   i n =1, 2, , ( ) ( 1) ( ) ( 1) ( 1) ( ) ( ) 1 1 , 1, 1 k k k k k k 1 i i i i i i i ii i in n ii x x b a x a x a x a x a + + + = + − − − − − − − − (3.1) 1 ( ) ( 1) ( ) 1 1 i n k k k i i ij j ij j j j i ii x b a x a x a − + = =   = + − −       则 (3.1) 式可写为 ( 1) ( ) ( ) k k k 1 i i i ii x x r a + = + (3.2)

由此可以看出，Gauss--Seidel迭代法的第k+1 步，相当于在第k步的基础上每一个分量增加 一个修正量。”。现在，为了获得更快的收敛 效果，在修正项的前面乘以一个参数0，便得到 逐次超松弛迭代格式 x=x+0,i=1,2.,n (3.3)

由此可以看出， Gauss Seidel − 迭代法的第 k +1 1 ( ) k i ii r 一个修正量 a 。现在，为了获得更快的收敛 步 ，相当于在第 k 步的基础上每一个分量增加 效果，在修正项的前面乘以一个参数  ，便得到 逐次超松弛迭代格式 (3.3) ( 1) ( ) ( ) , 1,2, , k k k i i i ii x x r i n a +  = + =

称o为松驰因子，称01的迭代过程(3.3)为超松弛方法，此法 可以加速Gauss-Seidel迭代方法的收。o=1的迭 代过程(3.3)就是Gauss-Seidel迭代公式。 由迭代格式(3.3) -g”,-含"a 有 -x”-m-ax-立

称 为松弛因子，称 的 迭 代 过 程 为低松弛方法，对于一些方程组，用 迭代 法得不到收敛解或不收敛，但用低松弛方法却是收敛 的 。称 的迭代过程 为超 松 弛 方法, 此法  (3.3) Gauss Seidel − 可以加速 迭 代 方 法 的收敛。 的迭 代过程 就是 迭代公式。  1 (3.3) Gauss Seidel − Gauss Seidel −  =1 (3.3) 0 1    ( ) 1 1 ( ) ( 1) ( ) 1 1 i n k k k k i i i ij j ij j j j i ii x x b a x a x a − + + = =   = + − −       由迭代格式（3.3） 有 ( ) ( ) 1 1 ( ) ( 1) ( ) 1 1 i n k k k k k i i i i ij j ij j j j i ii x x x b a x a x a   − + + = = +   = − + − −      

即有 i=1,2,…,n SOR迭代法常以这种形式进行计算。 格式(3.4)的矩阵形式为 X()=(1-@)X+@D-i(b+LX()+UX() (3.5)

格式（3.4）的矩阵形式为 ( ) ( ) ( ) ( 1) 1 ( ) (1 ) , k k k k X X D b LX UX   + − = − + + + (3.5) SOR迭代法常以这种形式进行计算。 ( ) 1 1 ( ) ( 1) ( ) 1 1 (1 ) , i n k k k k i i i ij j ij j ii j j i x x b a x a x a   − + + = = +   = − + − −       i n =1, 2, , (3.4) 即有

其中 0 0 0 D 02 L= 0 0 0 U= n-1.n 0 0 显然，A=D-L-U

其中 11 22 0 , 0 nn a a D a     =         21 1 , 1 0 0 n n n 0 a L a a −       =       12 1 1, 0 0 0 0 n n n a a U a −     =         显然， A D L U = − −

二SOR迭代法的收敛性 由(3.5)式有 Dx=(1-0)Dx+b+Lx+Ux 即 DX-@LX()=(1-@)DX()+oUx()+@b 于是有 (D-@L)x()=[(1-@)D+@U]X()+@b x)=(D-@L)-[(1-@)D+@U]X*+@(D-@L)-b

二 SOR 迭代法的收敛性 由 (3.5) 式有 ( ) ( ) ( ) ( ) ( ) 1 1 1 k k k k DX DX b LX UX   + + = − + + + 即 ( ) ( ) ( ) 1 1 ( ) ( ) 1 k k k k DX LX DX UX b     + + − = − + + ( ) ( ) ( ) ( ) ( ) ( ) 1 1 1 1 ( ) [ 1 ] ( ) [ 1 ] ( ) k k k k D L X D U X b X D L D U X D L b          + + − − − = − + +  = − − + + − 于是有

记 B。=(D-oL)[1-o)D+oU] F。=o(D-oL)'b (3.6) 则有 X()=Bx()+F (3.7 其中，称B。为SOR迭代矩阵

记 ( ) ( ) ( ) 1 1 B D L D U [ 1 ] F D L b        − −   = − − +   = −  (3.6) 则有 (k k 1) ( ) X B X F   + = + (3.7) 其中，称 B 为 SOR 迭代矩阵