第六章 线性方程组迭代法,迭代法的加速,数值分析,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) 1 1 1 0.7500000 0.3750000 1.5000000 0.5625000 0.5312500 1.5416667 0.6510417 0.5963542 1.6145833 0.7018229 0.6582031 1.6727431. 0.9999933 0.9999923 1.9999926 0.9999943 0.9999935 1.9999937 0.9999952 0.9999944 1.9999946 k = 71,x=0.9999950.9999941.999995,满足精度的解,迭代次数为71次,9,(1)SOR迭代法,1 1 1 0.6375000 0.0121875 1.3199063 0.2004270 0.3717572 1.3122805 0.6550335 0.5340119 1.6922848 0.7058468 0.7733401 1.7771932. 0.9999990 0.9999976 1.9999991 0.9999984 0.9999993 1.9999989 0.9999998 0.9999994 1.9999998 0.9999996 0.9999998 1.9999997 k = 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加速,可见加速技术可能将不收敛的迭代法加速为收敛,