Aitken加速收敛算法

2012-2013（1）专业课程实践论文Aitken加速收敛方法李阳0818180221R数学08-2班曹宏博0818180220R数学08-2班一、算法理论Aitken加速收敛算法基本原理：对于收敛的迭代过程，只要迭代足够多次，就可以使结果达到任意的精度。但有时迭代过程收敛缓慢，从而使计算量变得很大，因此，迭代过程的加速是个重要的过程。设0x是跟*x的某个预测值，只迭代公式校正一次)(x01fx,而由微分中值定理有：)x-(x(t)-*0'*1fxx（其中t介于*x与0x之间）。假定xf'改变不大，近似的取某个近似值L，则由)-(-*0*1xxLxx得到LxLLxx-1--101*,可以期望按上式右端求得LxxLxLLxLxx-1--1--1011012是比1x更好的近似值，将每得到一次改进值算做一步，并用kx和kx分别表示第K步的校正值和改进值，则加速迭代计算方案可表述如下：校正：1kxkxf改进：1kxLxxLxkkk-1-11然而上述加速公式有个缺点，由于其中含有倒数xf的有关信息L，实际使用不便。仍设已知*x的某个猜测值为0x，将校正值01xfx,再校正一次，又得12xfx。由于*2-xx*1-Lxx将它与式*xLxLLx-1--101联立，消去未知L，然后有*x21021222---xxxxxx这样构造出的改进公式确定不再含有关于导数的信息，但是它需要用2次迭代值进行加工，如果将得到一次改进值作为一步，则计算公式如下：校正：kkxfx1再校正：11kkxfx改进：kkkkkkkxxxxxxx11211112---上述处理过程称为Aitken方法。如下用2个题说明：例题（1）用Aitken算法通过编程计算01--3xx在[1,2]内的近似根，要求精度达到0001.0。例题（2）用Aitken算法通过编程计算01--23xx在[1，2]内的近似根，要求精度达到001.0。二、算法框图开始定义函数S(t)=t*t*t-1输入迭代初始值x0,控制精度e,循环次数I,i=0fabs(x0*x0*x0-x0-1)ei++;x1=s(x0)；x2=s(x1);x0=x2-(x2-x1)*(x2-x1)/(x2-2*x1+pow((x1+1),1.0/3.是fabs(x0*x0*x0-x0-1)ex=x0;输出近似根x迭代次数e结束否三、算法程序（1）题程序：#includeiostream#includecmathdoubles(doublet){return(t*t*t-1);}usingnamespacestd;intmain(){inti;doublex,x0,x1,x2,e;cout请输入迭代初始值x0,和控制精度eendl;cinx0e;i=0;while(fabs(x0*x0*x0-x0-1)e){i++;x1=s(x0);x2=s(x1);x0=x2-(x2-x1)*(x2-x1)/(x2-2*x1+pow((x1+1),1.0/3.0));}x=x0;cout近似根x=xendl;cout所需迭代次数i=iendl;return0;}四、算法实现例1.用Aitken算法通过编程计算01--3xx在[1,2]内的近似根，要求精度达到0001.0。解：运行程序（1）输入0x的初始值是1.5以及精度值0.0001.然后按回车。（2）得到结果近似根x1.32472，所需迭代次数为5次。当精度达到0.0001时，程序运行结果如下图：Aitken迭代法是将迭代值在迭代一次，此时对于发散的1-31kkxx迭代公式，经过Aitken迭代法处理后却获得了相当好的收敛性。例2.用Aitken算法通过编程计算01--23xx在[1,2]内的近似根，要求精度达到0.001。解：运行程序（1）首先输入0x的初始值是1.3，以及精度值0.001按回车。（2）得到结果近似根x1.46557，迭代次数为2次当精度达到0.001时，程序运行结果如下图：