搜索
数值分析实验——求非线性方程的零点10级数学与应用数学1班20103869郝少强摘要本报告主要介绍了基于求非线性方程零点问题的牛顿法、二分法，简易牛顿法、割线法、Steveson法等数值分析方法的算法原理及实现方法。通过对非线性方程3()310fxxx=−−=分别运用以上五种不同的迭代法进行数值实验，对几种迭代法的运算量，空间存储使用，迭代步数进行了初步分析评价，并对几种迭代法分别适用于求解何种类型的非线性方程进行了简要分析说明A．牛顿法一、算法介绍牛顿法是一种能在许多不同情况下应用的通用过程。特别的，当用它来求实变量实值函数零点时，常常被成为牛顿—拉弗森迭代。由于其收敛是二次的而不是线形或超线性的，所以通常牛顿法对分法和割线法要快。一旦二次收敛变得有效时，即牛顿法序列的值能充分地接近根时，其收敛很快以至于仅仅再需要几个数值即可。不完美的是，牛顿法不能保证总是收敛，所以实际计算中常常将其与其他较慢的方法结合形成一种数值上整体收敛的混合方法。假设我们有一个函数f，其零点由数值计算得出。设r是f的零点，而x是r的一个近似。若''f存在并且连续，则由泰勒定理，得20()()()'()()frfxhfxhfxOh==+=++其中hrx=−，若h较小（即x在r附近），则有理由略去2(Oh）项，并且在余下的方程中求h，其结果是()'()fxhfx−=若x是r的一个近似，则()'()fxxfx−应该是r的一个更好的近似。牛顿从r的一个估计0x开始，然后归纳定义1()(0)'()nnnnfxxxnfx+=−≥二、算法描述用牛顿法求方程f(x)=x^3-3*x-1=0在x0=2附近的根，已知根的准确值为x*=1.87938524…通过牛顿迭代计算方程的根。取初始迭代值为2，精度取510−。MATLAB程序代码如下：f=inline('x^3-3*x-1');df=inline('3*x^2-3');d2f=inline('6*x');a=1;b=2;dlt=0.5*1.0e-8;iff(a)*d2f(a)0x0=a;elsex0=b;endm=min(abs(df(a)),abs(df(b)));k=0;whileabs(f(x0))m*dltk=k+1;x1=x0-f(x0)/df(x0);x0=x1;fprintf('k=%dx=%.5f\n',k,x0);end三、实验结果kx11.8888921.8795431.8793941.8793951.87939四，结果分析牛顿迭代法是二次收敛的，因此用牛顿迭代法求解非线性方程的解，迭代次数较小，能以较小的计算量和较小的空间利用得到相对较精确的数值解。但其缺点为需要所求非线性方程的导函数值，所以适用范围相对较小，只能对一阶可导的方程进行迭代。B．二分法一、算法介绍若f是区间[,]ab的连续函数，且()()0fafb，则f在[,]ab内必有一个零点。因为()()0fafb，所以函数f在区间[,]ab上改变符号，因此它在这个区间内至少存在一个零点。这是中值定理的结论，因此利用区间减半的方法对这一数值计算思想进行实践运算。二、算法描述设函数()fx在区间[,]ab上连续，而且()()0fafb，则()fx在区间[,]ab上至少有一个根。首先确定有限区间：依据零点定理。设],[)(baCxf∈，且0)()(bfaf，则方程0)(=xf在区间),(ba上至少有一个根。如果)('xf在),(ba上恒正或恒负，则此根唯一。令111112,,()aabbhalfab===+若1()()0fafhalf，则1[,]ahalf为有根区间，否则1[,]halfb为有根区间。记新的有根区间为],[22ba，则],[],[2211baba⊃且)(112122abab−=−；对],[22ba重复上述做法得：......],[......],[],[2211⊃⊃⊃⊃nnbababa且)(211ababnnn−=−−，设所求的根为*x，则......2,1],[=∈∗nbaxnn，即......2,1=≤≤∗nbxann，由0)(21lim)(lim1n=−=−−∞→∞→ababnnnn得*limlimxbannnn==∞→∞→，取1()2nnxhalfab∗==+为*x的近似解。MATLAB程序代码如下f=inline('x^3-3*x-1');a=1;b=2;dlt=0.5*1.0e-8;k=1;whileabs(b-a)dltc=(a+b)/2;iff(c)==0break;elseiff(c)*f(b)0a=c;elseb=c;endfprintf('k=%d,x=%.5f\n',k,c);k=k+1;end三、实验结果四、结果分析由实验结果可知，二分法经过多次迭代后，也能达到较好的精度，但当所求问题较为庞大，且对其跟的估计范围较为宽泛时，此方法所需迭代的步数很大，无论计算量和空间储存上都会有很大的开销耗费。C.简易牛顿法一、算法介绍简易牛顿法与牛顿法大致思想相同，都是运用切线和坐标轴相交进行迭代运算，不同的是简易牛顿法在进行迭代运算时只取用了初始值的导函数值，使得算法整体运算量相对较小。二、算法描述在牛顿法程序代码上进行小修改就行，MATLAB代码如下：f=inline('x^3-3*x-1');df=inline('3*x^2-3');d2f=inline('6*x');a=1;b=2;dlt=0.5*1.0e-8;iff(a)*d2f(a)0x0=a;elsex0=b;endm=min(abs(df(a)),abs(df(b)));k=0;h=df(x0);whileabs(f(x0))m*dltk=k+1;x1=x0-f(x0)/h;x0=x1;fprintf('k=%dx=%.5f\n',k,x0);end三、实验结果四、结果分析相比于牛顿法，建议牛顿法拥有较小的计算量，算法只用到初始值的导数值作为分母，但缺点是需要迭代更多步数。综合比较两种迭代算法的话，简易牛顿法适合简单且容易观察出零点大致位置的非线性方程，而牛顿法在更为复杂的问题上仍能以较小的运算量得出令人满意的数值解。D．割线法一、算法介绍我们前面已经知道牛顿迭代法拥有许多良好的性质，比如二次收敛速度很快，迭代次数较少，所用存储空间少，程序编写简单等。但不可否认的是，牛顿法仍然存在缺点，如局部收敛，需要求函数零点导数等。因此为克服存在函数不可导的这一缺点，人们提出了割线法，即111()[]()()nnnnnnnxxxxfxfxfx−+−−=−−因为1nx+得计算要用到nx和1nx−，所以开始时需要指定两个初始点。二、算法描述输入的量：初始值01x、02x，要求的近似根kx的误差限tol，kx的函数值()kfx的误差限ftol，迭代次数的最大值gxmax及其函数fnq(x)输出的量:迭代序列{kx}，迭代k次得到的迭代值kx，相邻两次迭代的偏差piancha=1kkxx−−，以及偏差的相对误差1kkxx−−/kx。MATLAB程序代码如下：function[k,piancha,xdpiancha,xk,yk]=gexian(x01,x02,tol,ftol,gxmax)x(1)=x01;x(2)=x02;fori=2:gxmaxu(i)=fnq(x(i))*(x(i)-x(i-1));v(i)=fnq(x(i))-fnq(x(i-1));x(i+1)=x(i)-u(i)/(v(i));piancha=abs(x(i+1)-x(i));xdpiancha=piancha/(abs(x(i+1))+eps);i=i+1;xk=x(i);yk=fnq(x(i));[(i-2)pianchaxdpianchaxkyk]if(abs(yk)ftol)&((pianchatol)|(xdpianchatol))k=i-2;xk=x(i);yk=fnq(x(i));[(i-2)pianchaxdpianchaxkyk]；return;endendifigxmaxdisp('请注意：迭代次数超过给定的最大值gxmax.')k=i-2;xk=x(i);yk=fnq(x(i));return;end三、实验结果kx11.750021.867831.880641.879451.8794四、结果分析由实验数据分析可知：割线法收敛速度不如牛顿迭代法收敛速度快，但比二分法要快得多，可以达到相对较高的精度。且在其迭代过程中每步只需一次新的函数赋值，又因为此类迭代算法中函数赋值构成了主要的计算量，所以综合比较割线法的运算量要比牛顿法更小些。E．Steffensen法一、算法介绍Steffensen算法是为了克服用牛顿迭代法时存在函数不可导的这一缺点而提出的另一种迭代法，同时也避免了进行割线法迭代时因为两个值之间相差很近时造成的算法误差。其迭代公式为;1()/()nnnnxxfxgx==−其中()[(())()]/()gxfxfxfxfx=+−二、算法描述MATLAB程序代码如下：function[gen,time]=Steff(fun,x0,tol)%如果缺省误差参数，默认为10的-5次方if(nargin==2)tol=1.0e-5;end%设置误差初值time=0;%记迭代次数wucha=0.1;%设置前后两次迭代的误差gen=x0;while(wuchatol)x1=gen;y=subs(fun,x1)+x1;z=subs(fun,y)+y;%加速公式gen=x1-(y-x1)^2/(z-2*y+x1);wucha=abs(gen-x1);time=time+1;%迭代加一次的记录endend;%计算结果四、结果分析由实验结果分析可知，Steffensen迭代算法的收敛速度在一定条件下可以达到二次收敛，相对割线法和二分法收敛速度较快，且其在一定程度上避免了两个值很近时造成的误差，也对牛顿法要求函数导数值这一缺点进行了克服，整体上比较来说是一个计算量较小且有较高精度的迭代算法。