《科学计算与数学建模第6章 回归问题-线性方程组求解的迭代法-6.4 超松弛代法-2017-02》由会员分享，可在线阅读，更多相关《科学计算与数学建模第6章 回归问题-线性方程组求解的迭代法-6.4 超松弛代法-2017-02（14页珍藏版）》请在金锄头文库上搜索。
1、,6.4 超松弛迭代法,6.4.1 超松弛迭代法的构造,逐次超松弛迭代法（Successive Over Relaxation Method， 简称为SOR法）是Gauss-Seidel迭代法的一种加速方法。,对方程 Ax b，其中,为非奇异矩阵，且 aii 0.(i 1,2,n) ，,ARnn,，现给出基于 G-S 迭代法的计算第 i 分量,的,（预估校正）方法：,将系数矩阵分解为 ADLU。 设已知第 k 次迭代向量 x( k ) 及第 k 1 次迭代向量 xk 1 的分量,j,x(k1) ( j 1,2,i 1),x,(k1) i,( k 1),先用Gauss-Seidel迭代法求出辅助
2、（预测）量 xi ：,(k 1),xi,1,ij j,(k 1),(b ,i1 i j1,(k ),ij j,a x,a x ,n ji1,) ( i 1, 2, n),再取,ai 为 与,的某种平均值（即加权平均值）,进行校正，即,x,( k 1),i,x,( k 1),(k),i i,x,(k ),(k ) ),(k ) i,i,i,x,(k 1),(k 1),(k 1) i,(1)x,xi x,(xi x,由上两式可得求解 Ax b的逐次超松弛迭代公式,i,ij j,ij j,a x(k ) ),aii,x(k ),j 1 j i,x(k 1) x(k ) i i,(b ,a x(k 1
3、) ,i1 ,n ,(x(k ) , x(k ) ,x(k ) ), (i 1, 2, n, k 0.1, 2,) 1 2 n,其中称为松弛因子，上式也可写为,j,i,i,i,ij j,ij,ii,a,j 1 j i,x(k 1) x(k ) i i,x,x ,(b ,a x(k 1) ,i1 ,n ,a x(k ) ), ( i 1, 2, n, k 0,1, 2,),显然1时，求解 Ax b的SOR法即为Gauss-Seidel迭代法； 当1 时，称为低松弛法，当 1时，称为超松弛法。,SOR法中每迭代一次，主要计算量是计算一次矩阵,与向量乘法。迭代算时，可用,来控制迭代终止。,(k ),
4、i,i,(k 1),p max xi max x i 1i n,x,3,1 x1 1, ,1 x2 1,1 x ,1，其精确解为 ,4 1 1 1 4 1 例 用SOR法解方程组 1 1 4 1 1 1,4 x4 1,x*,1, ,1,1。 ,1,解 取 x(0),1,1,1 2,3 4,2,2 1,2 3 4,3,3 1 2 3 4,4,4 1,2 3 4,4,4,4,4,x(k ),4x(k ) x(k ),x(k ) x(k ) ),x(k1),(1, , ,x(k1),x(k ) (1x(k1) 4x(k ) x(k ) x(k ) ),0，则SOR迭代公式为：,x(k ) (1x(k
5、1) x(k1) 4x(k ) x(k ) ),x(k ) (1x(k1) x(k1) x(k1) 4x(k ) ),x(k1),x(k1),取 1.3，第11次迭代结果为：,x(11) (0.99999646,1.00000310,0.99999953,0.99999912)T,2,2,(11) x(11) x*,0.46105,对松弛因子取其它值，满足误差,xk x*,105,的迭代次数如右表，由此可见，松弛因子选择 得好，会使SOR迭代的收敛大大加速。本例中 的1.3 是否是最佳的松弛因子？,6.4.2 SOR迭代的矩阵形式及其收敛性 将SOR迭代公式 可改写为：,ii i,( k 1)
6、 ( k ),ii i,a x (1)a x,i, b,ij j,a x,( k 1),i1 ,( k ),ij j,a x,j 1 j i1,n , i 1, 2, n,(b Lx( k 1) Ux( k ) ) (1)Dx( k ),Dx（k 1),由 A D L U，则,。 0,i 1,2,n； L 为,即（D L)x(k 1) (1)D U )x(k ) b 由于对任意的，（D L）均为非奇异阵（设 aii 下三角阵，其对角线元素为0），则,x( k 1),(D L)1 (1 )D U x( k ) (D L)1 b,因此，若 aii,0,i 1,2,n，则SOR迭代公式为：,x( k
7、 1), L x( k ) f,其中 L,(D L)1 (1 )D U , f (D L)1 b 。,L称为SOR迭代法的迭代矩阵。由迭代法收敛基本定理可 得SOR迭代收敛定理。,定理6.4.1 对 Ax=b，且 aii,0,i 1,2,n，则用SOR迭代法解,方程组收敛的充要条件是：(L) 1 。,。,对于方程组 Ax=b（aii,0, i 1, 2, n），如何选取超松弛,因子才能使SOR迭代法收敛？应选择*使,*,（L ）min（L ）,n,det(L) 12 n (L),1 det(L) n (L) 1,det(L ) det( DL)1)det(1)DU) (1)n,11,0 2,定
8、理6.4.2 (必要条件) 方程组 Ax=b，且 aii 0,i 1,2,n， 若SOR迭代法收敛，则 0 2 。 证：若SOR迭代法收敛，则 （L）1 （ L）= max(1，2，n ) 1,那么若选取 0 2，SOR迭代法是否一定收敛呢？事实上， 此条件只必要不充分。,定理6.4.3 (充分条件) 若A为对称正定矩阵，且 0 2 ,则解 Ax=b （aii,0,i 1,2,n）的SOR迭代法必收敛。,T, 1, 2 n,L y y, y (y y ,y ) 0,1,(1)D U y (D L)y,(D L) (1)D U)y y (1)DUy, y(DL)y, y,证：设 y 为对应 的
9、L特征向量，即,Dy, yDy, yUy, y,Dy, yLy, y,而,2,i1,0,n Dy, y aii yi,设Ly, yi，由于 A AT 则 U LT 。,-(Uy, y)(y,Ly)(Ly, y)i,从而,0(Ay, y) ( DLU)y, y) 2,当 02 有：2 2 220 从而可知 1，故SOR收敛。,i,因此， ,() i, ,2,2 2,2, ,从而， ,()2 22,？,如何对非线性方程组构造迭代解法？,6.4 超松弛迭代法,弹幕问题：,a.,1. 用SOR迭代法解方程 Ax b 时，只要松弛因子 0 2， 则相应的SOR迭代法就收敛吗？(不是),2. 方程组 Ax b满足 用条件时，可以构造SOR 迭代公式。(c),A 0 ；,L 0 ；,c. aii,0,i 1,2,n；,b. d. 0 2 。,
