东南大学_数值分析_第二章_牛顿迭代法

东南大学《数值分析》上机练习——算法与程序设计实验报告第二章非线性方程的解法——牛顿迭代法****（学号）****（姓名）算法与程序题目见教材P56上机题目20。一、算法原理根据题目的要求，是关于用牛顿迭代法法求解方程()0fx的通用算法。该法是一种通过斜率迭代的算法，其速度比二分法和简单迭代法都要快。其简单原理如下：设2[,],[,],fCabpab且存在数满足()0()0,fpfp。如果则存在一个数00,[,],ppp对任意初始值使得由如下定义的迭代序列0{}kkp收敛到p：1111()(),1,2,()kkkkkfppgppkfp其中(1)对于函数3()/3=0fxxx，则其递推规则是31212,1,2,3-3kkkppkp其中(2)定义序列0{}kkp，则序列0{}kkp收敛到x，也可表示为limkxpx。现简要证明：对于3'2()/3()-1fxxxfxx，得，写出牛顿迭代公式32()/3()()-1fxxxgxxxfxx(3)该公式可化简为322()33xgxx(4)二、流程图题目要求于用牛顿迭代法法求解方程()0fx的通用算法。其计算过程主要第二章非线性方程的解法用到迭代()()()fxgxxfx，图流程图1所示。输入各参数k=1迭代1111()(),1,2,()kkkkkfppgppkfp其中计算各误差误差在允许范围之内TFbreakk=k+1kmaxN输出图1题1关于牛顿迭代法的算法流程图三、计算代码核心代码1)p1=……;2)if(errdelta)|(relerrdelta)|(abs(y)epsilon),break;3)ifkmaxN,goto1完整代码程序1：Newton.m%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Description:牛顿迭代法%Author:panyunqiang%Versoin:1.0%Date:2012-9-21%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%function[p0,err,k,y]=Newton(p0,delta,epsilon,maxN)%input-p0istheinitialapproximationtoazerooff%-deltaisthetoleranceforp0%-epsilonisthetoleranceforthefunctionvaluesy%-maxNisthemaxiumnumberofiterations%output-p0istheNewtonapproximationtoazero%-erristheerrorestimateforp0东南大学《数值分析》上机练习——算法与程序设计实验报告%-kisthenumberofiterations%-yisthefunctionvaluef(p0)fork=1:maxN%%递归p1=2*p0^3/(3*p0^2-3);%%计算误差err=abs(p1-p0);relerr=2*err/(abs(p1)+delta);p0=p1;%%当前求出的根的函数值y=p0^3/3-p0;%%判断if(errdelta)|(relerrdelta)|(abs(y)epsilon)break;endend程序2：Newton_Step.m%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%Description:寻找题目中关于牛顿迭代法收敛的尽可能大的delta%搜索步进为step=10^(-6),即精确到小数点后六位%Author:panyunqiang%Versoin:1.0%Date:2012-9-21%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%formatlongstep=10^(-6);delta=10^-8;epsilon=10^-8;maxN=1000;ps=0.6;[p0,err,k,y]=Newton(ps,delta,epsilon,maxN);while((abs(p0)=epsilon)&(p0~=NaN))ps=ps+step;[p0,err,k,y]=Newton(ps,delta,epsilon,maxN);endps-step四、计算结果及分析a)运行程序Newton_Step.m，获得Newton局部收敛于2=0x的初始值的范围=0.774596，六位有效数字。通过改变程序Newton_Step.m中的搜索步进step，可以获得不同的精度。b)运行程序Newton.m,输出结果如下：第二章非线性方程的解法1、输入0(-,1)x时p0=newton(-2,10^(-12),10^(-12),1000)p0=-1.732050807568877%收敛到根-32、输入0(-1,-)x时p0=newton(-0.85,10^(-12),10^(-12),1000)p0=1.732050807568877%收敛到根33、输入0(-,)x时p0=newton(-0.001,10^(-12),10^(-12),1000)p0=-1.975314567913087e-028%收敛到根04、输入0(,1)x时p0=newton(0.85,10^(-12),10^(-12),1000)p0=-1.732050807568877%收敛到根-35、输入0(1,+)x时p0=newton(2,10^(-12),10^(-12),1000)p0=1.732050807568877%收敛到根3从上面的结果可知，牛顿迭代法具有非常高的收敛速度（程序newton.m运行迭代次数k很小），进一步还会发现每次迭代后的精确位数大致都会翻倍，即具有二阶收敛性。同时，可以看出，当0(-,1)(-,)(1,+)x时，程序会收敛到0x所属区间的那个根；而当0(-1,-)(,1)x，则不会收敛到0x所属区间的那个根。可以画出函数图像观察迭代过程，如图2所示。其中0(-1,-)x，为初始值，经过一次迭代后得到x1，三次迭代后就接近准确值*3=3x了。事实上，我们通过matlab仿真观察每次迭代的结果，如下表所示，也能看出Newton迭代法收敛迅速，且与图2所示的切线基本符合一致。表1Newton迭代收敛情况迭代次数012345nx-0.8551.5491561.7705251.7332701.7320521.732051东南大学《数值分析》上机练习——算法与程序设计实验报告-2-1.5-1-0.500.511.522.5-0.8-0.6-0.4-0.200.20.40.60.8f(x)=x3/3-xxyf(x)x3*=1.732x2*=0x1*=-1.732x2初始值x0x1x3=x3*图2Newton法迭代过程五、结论此次题目主要涉及牛顿迭代法。通过题目，我们可以看出，牛顿迭代法的效率是很高的。但该法的其中一个苛刻条件是二阶可导且一阶导数不能为0。有以下几个缺陷：1，有可能所得的序列左右来回飘移，不会收敛。2，序列会趋于重复或基本重复，造成循环。3，还有可能发生离散振荡序列。当根的阶数大于1时，迭代的速度会变慢，此时有一种更好的方法求解，即牛顿-拉夫森迭代的加速收敛法。而哈利法则是其另一种途径。