数值分析：6.4超松弛迭代法.ppt

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第六章 线性方程组迭代解法,Numerical Value Analysis,6.4,超松弛迭代法,(SOR),6.4,超松弛,迭代法,(,SOR),一、,SOR,法迭代公式,例,3.6,用,SOR,法求解线性方程组,二、,SOR,法的收敛性,SOR,法收敛与收敛速度有关定理,SOR,法分类与现状,SOR,（,Successive Over-Relaxation,）,法，即超松弛迭代法，是目前解大型线性方程组的一种最常用的方法，是,Gauss-Seidel,迭代法的一种加速方法。,一、,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),返回引用,把,式（,1,）,代入,式（,2,）,可以综合写成：,即得超松弛法或逐次超松弛迭代法（,Successive Over-Relaxation Method,），简称,SOR,法。,或可表示成增量的形式：,其中，,参数,叫做松弛因子；,若,=1,，,它就是,Gauss-Seidel,迭代法。,返回引用,令,A=D-L-U,SOR,法,(2),式可写成：,再整理成：,于是可导出,SOR,法的矩阵形式：,其中，迭代矩阵和,f,为,:,例,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,迭代法,：,返回引用,迭代结果见表,3.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.62231453.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,迭代法若要精确到七位小数，,Gauss-Seidel,迭代法需要,34,次迭代；,而用,SOR,迭代法,(,=1.25),，,只需要,14,次迭代。,可见，若选好参数,，,SOR,迭代法收敛速度会很快。,返回节,二、,SOR,法的收敛性,为了利用,第,3,节的收敛定理,，要先给出,SOR,法的矩阵表达式。,令,A=D-L-U,SOR,法,(2),式可写成：,再整理成：,于是可导出,SOR,法的矩阵形式：,其中，迭代矩阵和,f,为,:,由,定理,6.1,及,定理,6.2,直接得知：,SOR,法收敛的充要条件是,(B,)1,。,SOR,法收敛的充分条件是,|,B,|1,。,前面我们看到，,SOR,法收敛与否或收敛速度都与松弛因子,有关，关于,的范围，有如下定理。,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,的推论。,定理,6.7,设,A,是对称正定的三对角矩阵，则,(,B,G,)=,(,B,J,),2,1,时，称为,超松弛算法,，当,1,时，称为,超松弛算法,；,当,1,时，称为,亚松弛算法,。,目前还没有自动选择因子的一般方法，实际计算中，通常取（,0,2,）区间内几个不同的,值进行试算，通过比较后，确定比较理想的松弛因子,。,例,3.7,讨论,例,3.6,用,SOR,法的,取值。,解,系数矩阵,由式（,3,-,24,）得,根据,定理,6.,7,，有,(,B,G,)=,(B,J,),2,=0.625,，,(,B,opt,)=,opt,1=0.24,可见采用,SOR,方法比,Jacobi,迭代法和,Gauss-Seidel,迭代法快得多。,返回章,返回节,1,Jacobi,迭代法、,Gauss-Seidel,迭代法和,SOR,法,（,1,）计算分量形式、矩阵形式以及它们的迭,代矩阵表示；,(2),线性方程组的系数矩阵为某些特殊情形下，,Jacobi,迭代法、,Gauss-Seidel,迭代法和,SOR,法的收敛性的重要结论。,本章学习要点,返回章,应用数值分析,：,例题,6.3.1,、,6.3.5,；,习题,6.1,、,6.3,、,6.4,、,6.8,、,6.9,、,6.11,、,6.14,、,6.18,See you later!,