6.4超松弛迭代法

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第六章 线性方程组迭代解法,Numerical Analysis,6.4 超松弛迭代法(SOR),1, 6.4,超松弛,迭代法(,SOR),一、,SOR,法迭代公式,例6.6 用SOR法求解线性方程组,二、SOR法的收敛性,SOR法收敛与收敛速度有关定理,SOR法分类与现状,SOR,（,Successive Over-Relaxation,）法，即,超松弛迭代法,，是目前解大型线性方程组的一种,最常用的方法,，是,Gauss-Seidel,迭代法,的一种,加速方法,。,2,一、,SOR,法迭代公式,设线性方程组,AX,=,b,其中,A,非奇异，且,a,ii, 0,（,i,=1,2,n,） 。,如果已经得到第,k,次迭代量,x,(k),及第,k+,1次迭代量,x,(k+1),的前,i,-1个 分量,（,x,1,(,k,+1),x,2,(,k,+1),x,i,-1,(,k,+1),)，,在计算,x,i,(,k,+1),时，先用,Gauss-Seidel,迭代法,得到,(,1,),选择参数，取,(2),返回引用,3,把 式（1）代入式（,2,）即得,SOR,法,其中，,参数,叫做松弛因子；,若,=1,，它就是,Gauss-Seidel,迭代法。,返回引用,4,例6.6 用,SOR,法求解线性方程组,解,方程组的精确解为,x,=(3,4,-5),T,，,为了进行比较,，,利用同一初值,x,(0),=(1,1,1),T,，,分别取,=1 (,即,Gauss-Seidel,迭代法,),和,=1.25,两组算式同时求解方程组。,取,=1,，即,Gauss-Seidel,迭代,：,取,=1.25,，即,SOR,迭代法,：,返回引用,5,迭代结果见表,6.3,。,表,6.3,Gauss-Seidel,迭代法与,SOR,迭代法比较,Gauss-Seidel,迭代法,SOR,迭代法(,=1.25),k,x,1,x,2,x,3,x,1,x,2,x,3,0,1.0000000,1.0000000,1.0000000,1.0000000,1.0000000,1.0000000,1,5.2500000,3.1825000,-5.0468750,6.3125000,3.9195313,-6.6501465,2,3.1406250,3.8828125,-5.0292969,2.6223145,3.9585266,-4.6004238,3,3.0878906,3.9267587,-5.0183105,3.1333027,4.0402646,-5.0966863,4,3.0549316,3.9542236,-5.0114410,2.9570512,4.0074838,-4.9734897,5,3.0343323,3.9713898,-5.0071526,3.0037211,4.0029250,-5.0057135,6,3.0214577,3.9821186,-5.0044703,2.9963276,4.0009262,-4.9982822,7,3.0134110,3.9888241,-5.0027940,3.0000498,4.0002586,-5.0003486,6,迭代法若要精确到七位小数，,Gauss-Seidel,迭代法需要,34,次迭代；,而用,SOR,迭代法,(,=1.25),，,只需要,14,次迭代。,可见，若选好参数,，,SOR,迭代法收敛速度会很快。,返回节,7,二、,SOR,法的收敛性,为了利用第3节的收敛定理，要先给出,SOR,法的矩阵表达式。由式（2）,以及,Gauss-Seidel,迭代法的矩阵表达形式，可以看出,X,(,k,+1),=(1-,),X,(,k,),+,D,-1,(,b,+,LX,(,k,+1),+,UX,(,k,),),DX,(,k,+1),=(1-,),DX,(,k,),+,(,b,+,LX,(,k,+1),+,UX,(,k,),）,(,D,-,L,),X,（,k,+1）,=(1-,),D,+,U,X,(,k,),+,b,解得,X,(,k,+1),=(,D,-,L,),-1,(1-,),D,+,U,X,(,k,),+,(,D,-,L,),-1,b,(3),记,B,=(,D,-,L,),-1,(1-,),D,+,U, 称为,SOR,法迭代矩阵。,8,由定理,6.1,及定理,6.2,直接得知：,SOR,法收敛的充要条件是,(,B,)1,。,SOR,法收敛的充分条件是,|,B,|1,。,前面我们看到，,SOR,法收敛与否或收敛速度都与松弛因子,有关，关于,的范围，有如下定理。,9,SOR,法收敛与收敛速度有关定理,定理6.5 设,A,R,n,n,，满足,a,ii,0 (,i,=1,2,n,),则有,(,B,) |1-,| 。,推论 解线性方程组，,SOR,法收敛的必要条件是,|1-,| 1 ，即 0,2。,定理,6.6,设,A,R,n,n,对称正定，且,0,2,，则,SOR,法对任意,的初始向量,都收敛。,由于定理,6.4,只是定理,6.6,的特殊情况，故定理,6.4,可以看作定理,6.6,的推论。,10,定理,6.7,设,A,是对称正定的三对角矩阵，则,(,B,G,) =,(,B,J,),2,1,时，称为,超松弛算法,；,当,1,时，称为,亚松弛算法,。,目前还没有自动选择因子的一般方法，实际计算中，通常取（,0,2,）区间内几个不同的,值进行试算，通过比较后，确定比较理想的松弛因子,。,12,例6.7 讨论例6.6用,SOR,法的,取值。,解,系数矩阵,由式（,4,）得,根据定理6. 7，有,(,B,G,) =,(B,J,),2,=0.625，,(,B,opt,)= ,opt, 1 = 0.24 ,可见采用,SOR,方法比,Jacobi,迭代法和,Gauss-Seidel,迭代法快得多。,返回章,返回节,13,1,Jacobi,迭代法、,Gauss-Seidel,迭代法（和,SOR,法,简介）,（1）计算公式分量形式、矩阵形式以及它们的迭,代矩阵表示；,(2)线性方程组的系数矩阵为某些特殊情形下，,Jacobi,迭代法、,Gauss-Seidel,迭代法的收敛性,的重要结论。,本章学习要点,返回章,14,2,迭代法收敛性的判定定理和收敛速度,(1)迭代法收敛的充要条件；,(2)从迭代矩阵的范数判别迭代法的收敛性,及其证明；,(3)线性方程组的系数矩阵为严格对角占优阵，则,Jacobi,迭代法、,Gauss-Seidel,迭代法对任意初始向量均收敛。,本章学习要点,返回章,15,习题 6.3、6.6、6.9-6.12、,6.14、6.17、6.22,See you next chapter!,16,