第六章第三节逐次超松弛迭代法

1§3逐次超松弛迭代法（SOR方法）Byalex2一般说来，Jacobi迭代法收敛太慢，在实践中很少使用．在Jacobi迭代法收敛很慢的情况下，Gauss-Seidel迭代法也并不明显快一些．因此，欲对Gauss-Seidel迭代法作简单的修改，以提高其收敛速度．假设方程组bAx的系数矩阵TniinnijbbbniaaA,,),,,1(0,1．我们用下面的迭代格式来建立解方程组bAx的遥次超松弛迭代法(SOR方法)11)1(1)()((1~ijkjnijijkjijiiikixaxabax(3.1))~()1()()1()(kikikikixxxxni,,2,1这里，引入一个中间量)(~kix和一个加速收敛的参数(限于实数)，称。为松弛因子)(kix可以看作是)1(kix和)(~kix的加权平均．当1时(3．1)就是Gauss-Seidel迭代法．1时，(3．1)称为逐次超松弛迭代法；1时，(3．1)称为逐次低松弛迭代法．通常，统称为逐次超松弛迭代法，或简称为SOR迭代法．3我们把(3．1)式中的中间)(~kix消去，则有)1(11)1(1)()()1()(~kiijkjnijijkjijiiikixxaxabax2,1,,,2,1kni(3．2)上式的矩阵表示形式是111)1()(kkkkxbDUxLxx(3．3)或者bDLIxTxkk111)((3．4)其中))1(()(1UILITw(3．5)它是SOR方法的迭代矩阵．特别，若取1，则ULIT11)(是Gauss-Seidel迭代法的迭代矩阵．若将矩阵A分裂成0),)1((1)(1DUDDLDA按§1所述的建立相容迭代法的方法，立即可得SOR方法．因此，SOR方法与方程组bAx是完全相容的．4例1方程组341085121045432143214324321xxxxxxxxxxxxxxxx有唯一解4,3,2,1x．我们应用Gauss-Seidel迭代法和SOR方法（取2,1来解这个方程组．Gauss—Seidel迭代公式为)4(51)1(4)1(3)1(2)(1kkkkxxxx)12(101)1(4)1(3)(1)(2kkkkxxxx)8(51)1(4)(2)(1)(3kkkkxxxx)34(101)(3)(2)(1)(4kkkkxxxx,2,1k5取初始向量Tx0,0,0,00，迭代六次得结果见表6．1．从表6.1得到3610022.1xx应用SOR方法(取O＝1．2)的迭代公式为96.024.024.024.02.0)1(4)1(3)1(2)1(1)(1kkkkkxxxxx44.112.012.02.012.0)1(4)1(3)1(2)(1)(2kkkkkxxxxx92.124.02.024.024.0)1(4)1(3)(2)(1)(3kkkkkxxxxx08.42.012.012.012.0)1(4)(3)(2)(1)(4kkkkkxxxxx2,1k取初始得量Tx0,0,0,00，迭代六次得结果见表6.2．图表6.1图表6.26从表6．2得到461056.5xx算法6．3应用SOR方法解方程组bAx输人方程组的阶数n；A的元素),,1,(njiaij；b的分量),,1(nibi；初始向量0x的分量),,1(0nixi；参数；容限TOL；最大迭代次数m输出近似解nxxx,,21或迭代次数超过m的信息．step1对nk,,1做step2—4．step2对ni,,2,11110()1(ijnijojijjijiiixaxabxxstep3若TOLxx0，则输出),,(1nxx；停机．step4对ni,,2,1iixx0step5输出(‘Maximunnumberofiterationsexceeded，)；停机．73．2SOR方法的收敛性现在，我们来讨论逐次超松弛迭代法的收敛性问题．定理1设方程组bAx的系数矩阵A的主对角元素niaij,,1,0，则SOR方法收敛的充分必要条件为1)(T其中T是SOR方法的迭代矩阵．定理2设方程组bAx的系数矩阵A的主对角元素niaij,,1,0，则SOR方法的迭代矩阵了。的谱半径大于等于1，即1)(T且SOR方法收敛的必要条件是20(3．6)证明由(3．5)式，有nUIUILIT)1())1det(())1det(())det(()det(18从1)(T而，迭代矩阵了-的所有特征值之积等于n)1(．因此有1)(T据定理1，若SOR方法收敛，则1)(T，因此11．由于。取实数，故有20定理2说明，若要SOR方法收敛，必须选取松弛因子，使)2,0(．但当)2,0(时，未必对任何线性方程组，SOR方法都收敛．定理3若线性方程组bAx的系数矩阵A是对称正定的，则20当时，SOR方法收敛．证明设是SOR方法的迭代矩阵))1(()(1UILITw的任意一个特征值，x为与其相应的特征向量，则有等式xxUILI))1(()(1或xLIxUI)())1((用DxH左乘上式两端得DLxxDxDUxxDxHHHH)1(，其中),,(11nnaadiagD,Hx表示x的共轭转置．记iDLxxqDxxHH,，由(2．8)式9有DUDLDA又因假设A是对称正定的，因此TDLDU)(iDLxxxDLxDUxxHHTHH)()(0q从而有02)(qxDUDLDxAxxHH于是iqiqq2222222)()(qqq由假设20，有0)2)(2()()(22qqqqq，因此12从而1)(T．故SOR方法收敛．10当1时，SOR方法就是Gauss—Seidel迭代法．因此，若且是对称正定矩阵，则Gauss—Seidel迭代法亦收敛．例2容易验证例1的线性方程组的系数矩阵是对称正定的．因此，对于解这个方程组，Gauss~Seidel迭代法收敛，并且取2.1时，SOR方法亦收敛．3．3相容次序、性质A和最佳松弛因子我们从例1看到，SOR方法收敛得快慢与松驰因子。的选择有关．松弛因子选择得好，会加快SOR方法的收敛速度．这一段，我们将对一类特殊的矩阵(在偏微分方程数值解法中常遇到的)，简要地叙述最佳松弛因子如何选取的问题．定义1给定一个n阶矩阵ijaA，对ji，若或0jia，则说ji,是有联系的．定义2给定一个n阶矩阵ijaA，记自然数集合nW,,2,1．若存在W的t个互不相交的子集t使得(1)tkkWW1(2)对kWi，若ji,有联系，则当ij时，1kWj；当ij时，1kWj，则说A是具有相容次序的矩阵．11注意：若矩阵ijaA具有相容次序，则属于同一子集的元素之间没有联系，即若kWji,，则,0ija，且0jia．例34001041001411004A取三个互不相交子集，}1{1W，}4,2{2W,}3{3W．容易验证它们满足定义2中的条件（1）和(2)．例如，01,2,4,01,2,01,121221421,21aWiWaWaWi32313,01,1WaW因此矩阵A具有相容次序．定义3给定一个n阶矩阵ijaA，记nW,,2,1．若存在W的两个不相交的子集21,SS使得(1);21WSS(2)若ji,有联系，则ji,分别属于这两个子集，则称矩阵A具有性质A12注意：定义3中1S或2S可以是空集．若有一个是空集，则矩阵A必为对角阵．从定义3还可看到，若矩阵A具有性质A，则属于同一子集的元素之间没有联系，即若1,Sji：或2,Sji，则0ija或0jia就例3，取3,11S，4,22S，易知它们满足定义3中的条件(1)和(2)．因此例1的矩阵A具有性质A．例4考虑),(yx平面的区域G内的Dirichlet问题：;),(,02222Gyxyuxu),(,),(yxyxfu(3．7)此处为区域G的边界G，如图6.1所示．图6.113我们在),(yx平面上作两组平行直线,2,1,0,,00jijhyyihxx(3.8)),(00yx是平面),(yx上的任意一点，通常取),(00yx为坐标原点，)0(h称为步长．这样，整个平面就被这两组平行直线构成的正方形网格所覆盖，所讨论的区域G+P可被有限个正方形网格所覆盖．两组平行直线的交点称为网格结点．我们只考虑属于G+F的结点．若一结点的所有四个相邻结点都属于G，则称此结点为内部结点；若一结点的四个相邻结点中至少有一个不属于G，则称此结点边界结点．在每一个内部结点上，我们用二阶中心差代替问题(3．7)中的二阶导数),(222)(),(),(2),(iiyxiiiiiixuhyhxuyxuyhxu),(222)(),(),(2),(iiyxiiiiiixuhhyxuyxuhyxu则有142),(22),(22),(4),(),(),(),()()(hyxuhyxuhyxuyhxuyhxuyuxujijijiiiiiyxyxjiji用iju表示),(jiyxu的近似值，便得到与问题(3.7)的微分方程相应的方程041,1,,1,1jijijijiijuuuuu(3.9)对G内的每一个内部结点都建立这样的方程，便可得到一个线性方程组．对所考虑的区域G，我们采用步长1h的正方形网格，按图6.2所示的内部结点编号次序列方程．于是，由(3.9)式便得到方程组图6.215040404040404111302221221231232224042315141404221413120221131211012012111uuuuuuuuuuuuuuuuuuuuuuuuuuuuuu由于边界结点上问题(3．7)的解的值已知为(3.10)5,,1,0),0,(0iifui5,4,3),2,(2iifui,3,2,1,0),3,(3iifui,2,1),,0(ijfuij),1,5(51fu因此方程组(3．10)可写成16)2,0()3,1(4)2,3(4)1,5()2,4()0,4(4)2,3()0,3(4)0,2(4)0,1()1,0(4122211122221413141312122312111122111ffuuufuuufffuuffuuufuuuuffuuu(3.11)或写成)2,0()3,1()3,2()2,3()1,5()2,4()0,4()2,3()0,3()0,2()0,1()1,0(410001140010004100001410