数值分析非线性方程求解（五种方法）.docx

数值分析实验分析牛顿法、割线法、对分法、Steffensen法、简易牛顿法解线性方程组的性质聂隐愚20103959摘要本报告介绍了牛顿法、割线法、对分法、Steffensen法、简易牛顿法五种算法原理及设计，检验了使用Matlab实现的对非齐次线性方程求根的程序，验证了五种算法的不同性能。本文在使用牛顿法求非齐次线性方程零点中，通过误差分析，得出其收敛是二次的，比对分法与割线法要快，这就保证在求零点时，需要更少的步数就能得出在精度范围内的结果，其收敛快（二次），稳定性好，且算法简单，但是值得指出的是牛顿法是一种局部收敛算法，且不能存在。对于割线法，同样通过误差分析得出，可知其收敛是超线性的，但比牛顿法要慢，较对分法快；同时在割线法中本文指出，其每次迭代只需要一次函数赋值，而牛顿法需两次，而对于割线法中的两步，其收敛性要比牛顿二次收敛好的多，因此在函数赋值上割线法工作量较少，且避免求导，但是需要给出两个较好的初始值，且越小会导致失真。对于对分法，其收敛是一次的，且算法简单且只要存在根就总是收敛的，但是由于一次收敛所以收敛速度较前三种方法慢。对于steffensen法，当出现不能用，或者计算导数比求函数更加复杂时使用，且具有与牛顿法同样的二阶收敛速度。对于简易牛顿法，是对牛顿法的一种改造，以时间效率来换空间效率的方式减少了对各个函数点的导数计算，从一定程度上节省了空间，但收敛阶数低于牛顿法，通常较牛顿法慢。一 牛顿法的性质1.1原理描述：设已知方程的近似根，则在附近可用一阶泰勒多项式近似代替。因此，方程可近似表示为。用满足方程的近似表示根差异不大。 设，由于满足，解得 重复这以过程，得到迭代格式。1.2算法描述 迭代公式：，初值设为，最大迭代次数为n，迭代次数为i（i=0），最终结果设为c，要求精度为e；Step1. Step2. 若，重复第一个步骤 若，break，则零点为二 割线法的性质2.1原理描述我们知道，牛顿迭代是由下式定义：，牛顿法的一个缺点是它需要求零点的函数导数，为了克服这一缺点，给出采用差商：代替牛顿迭代中的，得到割线法的迭代公式： 2.2算法描述初始值为x1,x0,精度为e，步骤记录为i（i=0）；Step1. Step2. 若，重复第一个步骤 若，break，则零点为三 对分法的性质3.1算法描述设是区间a,b上的连续函数，且 ，则a和b之间有一个零点，当，计算，且检查是否，检查零点在a,c之间还是c,b之间，若在a,c之间则把c换成b在新的区间上重复上面的步骤，若在c,b则把c换成a继续上面步骤。i为迭代步骤（i=0），初始点为x(0),x(1)，精度要求为eStep1.x(i+2)=（x(i)+x(i+1)）/2，若abs(f(x(i+2)e，则停止运算，输出零点为x(i+2)Step2.若f(i)f(i+2)0，令x(i+2)=x(i+1)，否则令x(i+2)=x(i)；Step3.重复第一步与第二步直到达到精度。四 Steffensen法4.1原理描述Steffensen法的原理与割线法类似，为了克服牛顿法中求导这一缺点，使用g(x)代替，其中g(x)如下：；因此迭代函数为：4.2算法描述迭代步数为i（i=0），精度要求为eStep1.计算Step2.若norm(x(i+1)-x(i)e，i=i+1，重复上述步骤，直到达到精度。五 简易牛顿法5.1原理描述简易牛顿法，是在牛顿法的基础上，对初始点只求一次导数，然后每次利用代替中的,这样处理后减少了牛顿的计算量,降低了空间上对各个迭代点导数的存储,但同样降低了运算速率.5.2算法描述初值设为x0，i为迭代步数，精度为eStep1. Step2.若,迭代结束，若，转至下一步Step3. ，继续迭代前两步，直至达到精度。六 计算机配置1. 处理器Inter(R) Core(TM) i3 CPU M350 2.27GHz 2.27GHz2. 安装内存（RAM）：4.00GB（3.87GB可用）3. 系统类型 Windows7 64位操作系统4. Matlab版本 Matlab 7.12.0（R2011a）七 案例分析参数设置：精度：最大迭代次数：30 函数选取：，如下图：图7-1 函数图形初值选取：五种方法的第一个初值点均选相同点，对于牛顿法，简易牛顿法，Steffensen法，只需要一个初值点。而对分法，割线法需要两初值点的情况下，我们根据函数图象可以设置一个合适的初值点，由于某些算法带有局部性，本文在此考虑比较各个算法在区间2,3上寻找零点的优越性。八 输出结果本文通过比较各个算法的迭代步数，迭代精度，运算时间，来评判各个算法的优越性，并描绘出计算方程过程中的几何图像。求区间2,3上零点的各个迭代法数据如下表：表8-1 五种迭代法的计算结果近似值初始值迭代次数计算时间误差对分法2.414213657379152,3210.0162100.0000009536743164割线法2.414213562404042.5,350.0077570.0000002950466231牛顿法2.41421356237358350.0423370.0000006729811206简易牛顿法2.414214635204923240.0187100.0000007152234747Steffensen法2.41421356237313110.0068830.00000000581783688注：由于迭代时间每次不同，且首次运行会比较慢，在这里取迭代时间为取第一次后的十次结果均值近似值取15位有效数字，误差取十位有效数字8.1对分法的迭代过程迭代步骤迭代值误差13.0-22.51.032.50.542.50.2552.43750.12562.43750.062572.4218750.0312582.4218750.01562592.417968750.0078125102.4160156250.00390625112.41503906250.001953125122.414550781250.0009765625132.4143066406250.00048828125142.4143066406250.00024414062152.414245605468750.00012207031162.4142150878906250.000061035156172.4142150878906250.000030517578182.4142150878906250.000015258789192.4142150878906250.0000076293945202.4142150878906250.0000038146973212.414214134216308593750.0000019073486222.41421318054199218750.00000095367432得到迭代过程图如下：图8-1 对分法迭代过程图图8-2 对分法迭代误差图8.2简易牛顿法的迭代过程迭代步骤迭代值误差13.00.422.60.089632.51040.04248878442.46791121551360.02271788452.445193331754560.01280206762.43239126494070.007411870872.424979394172810.00435563182.420623763138210.002581539992.418042223195740.0015376891102.416504534118570.00091861667112.415585917446120.00054974133122.415036176117130.00032933265132.414706843467170.00019741568142.414509427782960.00011838331152.41439104447790.000071006207162.414320038271140.000042595169172.414277443101870.000025554023182.414251889079020.000015331306192.414236557773430.0000091983845202.414227359388950.0000055188871212.414221840501840.0000033112806222.414218529221270.0000019867497232.414216542471530.0000011920431242.414215350428390.00000071522347迭代过程如下：图8-3 简易牛顿法迭代示意图图8-4简易牛顿法迭代过程图图8-5简易牛顿法迭代误差图8.3割线法迭代过程：迭代步骤迭代值误差值13.00.05172413793103448279974559964600222.50.03124199163160890080348508490715232.4482758620689655172413884378550.002721428129028424791613360866904342.4170338704373561328510177768250.00009858485766534030858565529342740852.4143124423083279772583864541960.000000295046623133288221652037464082图8-6割线法迭代图形图8-7 割线法迭代过程图图8-8 割线法迭代误差图8.4 Steffensen法的迭代过程迭代步骤迭代值误差13.00.080000000000000 22.919999999999999928945726423990.084776216185672 32.83522378381432815785956336185340.088934581244894 42.74628920256943453992448667122520.091140639574765 52.65514856299466961431221534439830.088731705383704 62.5664168576109656072503639734350.077196631102685 72.48922022650828100864828229532580.052246496830380 82.43697372967790126807585693313740.020248154247633 92.4167255754302678916189961455530.002478889485957 102.41424668594431057755400615860710.000033117753378 112.41421356819093269052700634347270.000000005817837 图8-9 Steffensen迭代过程图图8-10Steffensen迭代误差图8.5牛顿法迭代过程迭代步骤迭代点迭代误差13.000000000000000.39999999999999900000022.599999999999990.15774647887323900000032.442253521126760.02724288438280800000042.415010636743950.00079640138925629500052.414214235354690.000000672981120608540图8-11牛顿法迭代过程示意图图8-12 牛顿法迭代过程图图8-13 牛顿法迭代误差图九结果分析9.1根据结果，从迭代步骤方面来看，牛顿法与割线法是迭代需要次数最少（仅有五次）就能达到要求的精度，收敛速度很快（二次），但从时间花费与误差值来看，割线法优于牛顿法（牛顿法计算最慢）。迭代步骤需要最多的为简易牛顿法，根据原理我们也可以知道牛顿法的速度较慢，但是此算法的改进在于节省空间。9.2从计算时间上看，最优的为Steffensen法，且误差比割线法还小（最小），但迭代次数为11步，收敛速度中等。因此Steffensen法最为精确，计算最为快速。9.3从误差大小来看，Steffensen法最精确，且计算时间最少，迭代步数为中等。综上，我们可以发现，Steffensen法在总体上计算最优。十附录所用代码：清单：1. function函数有：fun3（x）函数，代表，详见附录中fun3.m2. M文件有：Steffensen算法代码：见附录Steffensen代码.m对分法算法代码：见附录对分法（代码）.m割线法算法代码：见附录割线法代码.m简易牛顿法算法代码：见附录EasyNewton.m牛顿法算法代码：见附录牛顿法（代码）.m1. fun3(x)函数：function y=fun3(x)y=x3-3*x2+x+1;end2. Steffensen代码.m： clear;clc;x(1)=3;eps=0.000001;tic;for i=1:20; f(i)=x(i)-fun3(x(i)*fun3(x(i)/(fun3(x(i)+fun3(x(i)-fun3(x(i); if norm(f(i)-x(i)eps conj=1; break; end x(i+1)=f(i); endtoc;answer=vpa(f(end),15)e=vpa(abs(f-x),10)ix=vpa(x,8)3. 对分法（代码）.m： clear;clc;x(1)=3;x(2)=2;r=0.000001;tic;for i=1:30 d(i)=x(i)-x(i+1); if(abs(fun3(x(i)r|abs(fun3(x(i+1)r) if(abs(fun3(x(i)sign(fun3(x(i+1) m=(x(i)+x(i+1)/2; if(abs(fun3(m)r) z0=m; return elseif(sign(fun3(m)=sign(fun3(x(i+1) x(i+1)=x(i); x(i+2)=m; else x(i+2)=x(i+1); x(i+1)=m; end else m=(x(i)+x(i+1)/2; if(abs(fun3(m)r) z0=m; return; elseif(sign(fun3(m)=sign(fun3(x(i+1) x(i+1)=x(i); x(i+2)=m; else x(i+2)=x(i+1); x(i+1)=m; end endendtoc;answer=vpa(z0,15)e=vpa(abs(x(end)-x(end-1),10)4. 割线法代码.m clearclcx(1)=3;x(2)=2.5;eps=0.000001;tic;for i=1:30 f(i+2)=x