数值计算方法65.ppt

华长生制作 * 第六章 逐次逼近法 6.5 迭代法的加速 6.5 迭代法的加速 无论是解线性方程组的Jacobi迭代法和G—S迭代法 还是解非线性方程Newton系列迭代法 都涉及到收敛速度问题 如何加快迭代法的速度呢？ 也涉及到初值的选取问题 如何改善迭代法的适用范围呢？ 一、线性方程组迭代法的加速 考虑解线性方程组的Gauss-Seidel迭代法 ------(1) 令 因此 ------(2) ------(3) 上式称为逐次超松弛法(SOR迭代法), 由G-S迭代法的矩阵形式 ------(4) ------(5) ----(6) 上式为逐次超松弛法(SOR迭代法)的矩阵形式 令 ----(7) SOR法化为 G-S迭代法 G-S法为SOR法的特例, SOR法为G-S法的加速 例1. 用G-S法和SOR法求下列方程组的解, 要求精度1e-6 解: (1)G-S迭代法 gauss_seidel.m [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.999995 0.999994 1.999995 满足精度的解 迭代次数为71次 (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.000000 1.000000 2.000000 满足精度的解 迭代次数为24次 sor.m SOR法的收敛速度比G-S法要快得多 SOR法都收敛吗？ 1.SOR迭代法收敛的充要条件是 对于SOR迭代法(7),有如下结论 ----(8) (此结论的证明较复杂), 因此有 另外,松弛因子的选取是很困难的,一般采用试算进行 二、非线性方程迭代法的加速 对于迭代法 上式的迭代函数 令 迭代改变量 即 求导并令 ----(9) 得 因此有松弛迭代法: --------(10) 从后面的例子可以看出,加速效果是明显的 甚至一些不收敛的迭代法经过松弛加速后也能收敛 不方便 中值定理 差商近似代替导数 即 于是可以得到迭代格式: 其中 -------(11) 上组公式称为Altken公式或Altken加速 将(11)式综合后可得一个解析式表示的迭代法: ----(12) 上式称为Steffensen迭代法 Altken公式与Steffensen公式是等价的 加速效果也是很明显的 例2中将比较不同加速方法 例2. 对迭代格式 进行加速解方程组 解: x0 = 0.5 x1 = 0.375 x2 = 0.3509115 x3 = 0.3477369 x4 = 0.3473496 x5 = 0.3473028 x6 = 0.3472971 x7 = 0.3472964 (1)直接使用迭代格式 迭代7次,得到满足精度的解 (2)对迭代格式进行松弛加速 x0 = 0.5 x1 = 0.3333333 x2 = 0.3472222 x3 = 0.3472964 x4 = 0.3472964 迭代4次,得到满足精度的解 (3)对迭代格式进行Altken加速(11)式 x0 = 0.5 x1 = 0.3451613 x2 = 0.3472961 x3 = 0.34729