数值分析知识内容 (17).pdf
2.4 迭代收敛的加速方法 2.4.1 埃特金加速法 加快收敛速度，减少计算量，是数值计算的重要课题，埃特金(Aitken)方法是一种有效的加速方法.埃特金加速方法可用于加快一已知收敛序列kx的收敛速度，其方法是通过收敛较慢的已知序列kx构造一个更快收敛的序列kx.设kx是一个线性收敛的序列，收敛于方程)(xx的根x.第一次校正：设0 x是根x的某个预测值，迭代公式可使0 x校正为)(01xx.由微分中值定理,有)()()(001xxxxxx，其中介于x与0 x之间.由于在较小的有根区间内，)(x的变化不大，取Lx)(，则有)(01xxLxx.（2.14）第二次校正：对1x值再校正一次，得)(12xx.由于)(12xxLxx，将其与(2.14)式联立，消去L，有 xxxxxxxx1021.解出x，得到 012201001221202)(2xxxxxxxxxxxxx.一次埃特金加速：对于初始近似值0 x，首先计算)(01xx，再计算)(12xx，然后，可用上式右端作为x的新近似值，记作1x，这就是一次埃特金加速过程.埃特金加速算法：对于更一般的情形，由kx计算21,kkxx,然后作一次加速 kkkkkkkxxxxxxx122112)(，（2.15）由此得到埃特金加速迭代公式：,1,0,2)()()(12211121kxxxxxxxxxxxkkkkkkkkkkk.（2.16）可以证明，0lim*1xxxxkkk，（2.17）它表明序列kx的收敛速度比kx的收敛速度快.【注】当迭代过程收敛很慢时，一般可用埃特金法加速，但有时埃特金法加速可能失败，例如当)(x起伏很大、初值0 x与根x有较大的距离时，埃特金加速就可能失败.2.4.2 斯蒂芬森迭代法 埃特金方法不管原序列kx是怎样产生的，对kx进行加速计算，得到序列kx，如果把埃特金加速技巧与不动点迭代结合，则可得到如下的斯蒂芬森迭代法(Steffensens Method)：)(kkxy，)(kkyz，kkkkkkkxyzxyxx2)(21（,1,0k）.(2.18)实际上公式（2.18）是将不动点迭代法计算两步合并成一步得到的，可将它写成另一种不动点迭代)(1kkxx（,1,0k），(2.19)其中 xxxxxxx)(2)()()(2.(2.20)对不动点迭代（2.19）有以下局部收敛性定理.【定理 6】若*x为（2.20）定义的迭代函数)(x的不动点，则*x为)(x的不动点.反之，若*x为)(x的不动点，设)(x 存在，1)(*x，则*x是)(x的不动点，且斯蒂芬森迭代法（2.18）是 2 阶收敛的.例 9 用斯蒂芬森迭代法求解方程01)(3xxxf.解 例 6 中已指出迭代131kkxx是发散的.现在利用斯蒂芬森迭代计算，仍取1)(3 xx，计算结果见表 2-6.表 2-6 例 9 迭代值 k kx ky kz 0 1.5 2.37500 12.3966 1 1.41629 1.84092 5.23888 2 1.35565 1.49140 2.31728 3 1.32895 1.34710 1.44435 4 1.32480 1.32518 1.32714 5 1.32472 计算表明它是收敛的，这说明即使原不动点迭代法不收敛，用斯蒂芬森迭代法仍可能收敛.至于原来已收敛的不动点迭代法，由定理 6 可知它可达到 2 阶收敛.更进一步还可知若原迭代法为p阶收敛，则斯蒂芬森迭代法为1p阶收敛.例 10 用斯蒂芬森迭代法求方程01)(xxexf在5.0 x附近的一个根.解 方程的精确解为*x=0.56714392.在例 7 中，迭代过程),1,0(1kexkxk，取初值0 x0.5，迭代计算到18x=0.5671407，且5*18104.0 xx.利用斯蒂芬森迭代计算，结果见表 2-7.由表 2-7 可知，经过 2 次迭代，18x=0.56714331，7*2102.0 xx，加速效果较好.表 2-7 例 10 迭代值 k kx ky kz 0 0.5 0.60653066 0.54523921 1 0.56762388 0.56687079 0.56729786 2 0.56714331 斯蒂芬森迭代法的 MATLAB 程序：steffensen.mfunction xstar,index,it=steffensen(phi,x,ep,it_max)%steffensen 加速方法，其中%phi(x)为迭代函数，x 为初始点；%ep 为精度，缺省值为 1e-5,%当x(k)-x(k-1)=it_max,失败；%it为迭代次数 if nargin4 it_max=100;end if nargin3 ep=1e-5;end index=0;k=1;while k=it_max x1=x;y=feval(phi,x),z=feval(phi,y),x=x-(y-x)2/(z-2*y+x)if abs(x-x1)=ep index=1;break;end k=k+1;end xstar=x;it=k;例7迭代函数的函数名为phi.m function f=phi(x)f=exp(-x);调用斯蒂芬森迭代法函数 steffensensteffensen.m 求方程的根 xstar,index,it=steffensen(phi,0.5,1exstar,index,it=steffensen(phi,0.5,1e-5)5)得到方程的根 xstarxstar=0.5671=0.5671,indexindex=1=1,itit=3=3 运行结果表明迭代成功，达到精度要求.迭代终止条件为：前后两次迭代结果之差是否满足精度，共迭代计算 3 次；对比例 7，利用不动点迭代计算了 18 次；显然 SteffSteffensenensen 方法收敛更快.
