《SOR法及加速》PPT课件.ppt

第六章线性方程组迭代法,迭代法的加速,数值分析,2,迭代法的加速,无论是解线性方程组的Jacobi迭代法和GS迭代法,还是解非线性方程Newton系列迭代法,都涉及到收敛速度问题,如何加快迭代法的速度呢？,也涉及到初值的选取问题,如何改善迭代法的适用范围呢？,3,由G-S迭代法的矩阵形式,加速,加速法主要思想,4,-(5),两边同时乘D,5,-(6),上式为逐次超松弛法(SOR迭代法)的矩阵形式,令,-(7),6,SOR法化为,G-S迭代法,G-S法为SOR法的特例,SOR法为G-S法的加速,例1.,用G-S法和SOR法求下列方程组的解,要求精度1e-6,7,解:,(1)G-S迭代法,8,x,k=gauss_seidel(a,b,1,1,1,1e-6)1110.75000000.37500001.50000000.56250000.53125001.54166670.65104170.59635421.61458330.70182290.65820311.6727431.0.99999330.99999231.99999260.99999430.99999351.99999370.99999520.99999441.9999946k=71,x=0.9999950.9999941.999995,满足精度的解,迭代次数为71次,9,(1)SOR迭代法,1110.63750000.01218751.31990630.20042700.37175721.31228050.65503350.53401191.69228480.70584680.77334011.7771932.0.99999900.99999761.99999910.99999840.99999931.99999890.99999980.99999941.99999980.99999960.99999981.9999997k=24,x=1.0000001.0000002.000000,满足精度的解,迭代次数为24次,SOR法的收敛速度比G-S法要快得多,10,SOR法都收敛吗？,1.SOR迭代法收敛的充要条件是,对于SOR迭代法(7),有如下结论,-(8),(此结论的证明较复杂),因此有,另外,松弛因子的选取是很困难的,一般采用试算进行,11,二、非线性方程迭代法的加速,对于迭代法,上式的迭代函数,令,迭代改变量,即,求导并令,-(9),12,得,因此有松弛迭代法:,-(10),从后面的例子可以看出,加速效果是明显的,甚至一些不收敛的迭代法经过松弛加速后也能收敛,13,不方便,中值定理,差商近似代替导数,即,14,于是可以得到迭代格式:,其中,-(11),上组公式称为Altken公式或Altken加速,15,将(11)式综合后可得一个解析式表示的迭代法:,-(12),上式称为Steffensen迭代法,Altken公式与Steffensen公式是等价的,加速效果也是很明显的,例2中将比较不同加速方法,16,例2.,对迭代格式,进行加速解方程组,解:,x0=0.5x1=0.375x2=0.3509115x3=0.3477369x4=0.3473496x5=0.3473028x6=0.3472971x7=0.3472964,(1)直接使用迭代格式,迭代7次,得到满足精度的解,17,(2)对迭代格式进行松弛加速,x0=0.5x1=0.3333333x2=0.3472222x3=0.3472964x4=0.3472964,迭代4次,得到满足精度的解,18,(3)对迭代格式进行Altken加速(11)式,x0=0.5x1=0.3451613x2=0.3472961x3=0.3472964,迭代3次,得到满足精度的解,从以上3种结果可见,迭代法加速技术效果比较明显,迭代格式,显然不收敛,19,x0=1.5x1=1.5350706x2=1.5321124x3=1.5320889x4=1.5320889,迭代4次,得到满足精度的解,对迭代格式进行松弛加速,x=1.5x=1.5333333x=1.5320906x=1.5320889x=1.5320889,迭代4次,得到满足精度的解,对迭代格式进行Altken加速,可见加速技术可能将不收敛的迭代法加速为收敛,