第三节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 迭代矩阵