Aitken加速收敛算法

1、2012-2013 (1)专业课程实践论文Aitken加速收敛方法李阳 0818180221 R数学08-2班 曹宏博 0818180220 R数学08-2班、算法理论Aitken加速收敛算法基本原理：对于收敛的迭代过程，只要迭代足够多次，就可以使结果达到任意的精度。 但有时迭代过程收敛缓慢，从而使计算量变得很大，因此，迭代过程的加速是 个重要的过程。设x是跟x*的某个预测值，只迭代公式校正一次x = f (x ),而由微分中0 1 0值定理有：x - X* = f (t) x (x -x*)(其中t介于x*与x之间)。1 0 0假定f (x)改变不大，近似的取某个近似值L，则由x - x*沁

2、L x (x - x*)得1 0到 x* =厶-土红,可以期望按上式右端求得 1-L 1-Lx = xi - x0 XL = x + LX(xi-x0)是比x更好的近似值，将每得到一次改进值21-L 1-L 11-L1算做一步，并用x；和x分别表示第K步的校正值和改进值，则加速迭代计算 k k方案可表述如下:校正:改进:x；k+校正:改进:x；k+1kxk+1,L x （x；- x ）=x +k+1kk+11 - L然而上述加速公式有个缺点，由于其中含有倒数f ；(x)的有关信息L,实际使用不便。仍设已知x*的某个猜测值为x，将校正值x = f (x ),再校正一次，又得0 1 0=仲由于=仲

3、由于x2-x*Lx:-x*各它与式1x* = i-0联立，消去未知L，然后有1-L 1-Lx* = x -(二2 这样构造出的改进公式确定不再含有关于导数的信2 x -2xx + x0 1 2息，但是它需要用2次迭代值进行加工，如果将得到一次改进值作为一步，则 计算公式如下：校正：x二 f (x )k+1k再校正：x = f (x)改进：x 二 x - k+1 Xk+1k+1k+1k+1 k+1 x -2Xx + xk+1k+1 k上述处理过程称为Aitken方法。如下用2个题说明：例题（1）用Aitkn算法通过编程计算x3 - x-1二0在1,2内的近似根，要求精度达到0.0001。例题（2

4、）用Aitken算法通过编程计算x3 -x2-1二0在1,2内的近似根，要求精度达到0.001。二、算法框图三、算法程序(1)题程序：#include#include double s(double t)return (t*t*tT);using namespace std;int main()int i;double x,x0,xl,x2,e;cout请输入迭代初始值x0,和控制精度ex0e;i=0;wh il e(fabs(xO *x0 *xO-xO-l)e)i+; x1=s(x0); x2=s(x1);x0=x2-(x2-x 1)* (x2-xl)/(x2-2 *xl+pow(xl+l)

5、,1.0/3.0); x=x0;cout近似根 x=xendl;cout所需迭代次数 i=iendl; return 0;四、算法实现例1.用Aitken算法通过编程计算X 3 - X-1二0在1,2 内的近似根，要求精度达 到 0.0001。解：运行程序（1）输入X的初始值是1.5以及精度值0.0001 然后按回车。0（2）得到结果近似根x = 1.32472,所需迭代次数为5次。当精度达到0.0001时，程序运行结果如下图：式，经过Ait ken迭代法处理后却获得了相当好的收敛性。例2.用Ait ken算法通过编程计算x 3 - x 2 -1 = 0在1,2内的近似根，要求精度 达到0.001。解：运行程序（1）首先输入x的初始值是1.3，以及精度值0.001按回车。0（2）得到结果近似根x = 1.46557,迭代次数为2次当精度达到0.001时，程序运行结果如下图:c： *C: DocuAent s and Sett ingsAd*inist r