非线性方程(论文).doc

非线性方程根的数值求法（二）非线性方程根的数值求法（二）摘要在科学研究和工程设计中, 经常会遇到的一大类问题是非线性方程 f(x)=0 的求根问题，其中f(x)为非线性函数。方程f(x)=0的根, 亦称为函数f(x)的零点。如果f(x)可以分解成 ,其中m为正整数且 ,则称x*是f(x)的m重零点,或称方程f(x)=0的m重根。当m=1时称x*为单根。若f(x)存在m阶导数,则是方程f(x)的m重根(m1)当且仅当。当f(x)不是x的线性函数时，称对应的函数方程为非线性方程。如果f(x)是多项式函数，则称为代数方程，否则称为超越方程（三角方程，指数、对数方程等）。一般称n次多项式构成的方程为n次代数方程,当n1时,方程显然是非线性的。一般稍微复杂的3次以上的代数方程或超越方程,很难甚至无法求得精确解。此论文将介绍常用的求解非线性方程的近似根的几种数值解法 。关键词：非线性方程；数值解法；近似根 THE NUMERICAL METHOD OF NONLINEAR EQUATION (TWO)ABSTRACTIn scientific research and engineering design, a large class of problems often encountered is a nonlinear equationF (x) =0The root problem, where f (x) is a nonlinear function.The equation f (x) =0 root, also known as a function of F (x) zero.If f (x) can be decomposed into, where m is a positive integer and, then x* is called f (x) m zeros, or equation f (x) m =0. When m=1 x* is called single. If f (x) m derivative, is the equation f (x) m roots (m1) if and only if.When f (x) is not a linear function of X, function equation is a nonlinear equation. If f (x) is a polynomial function, is called algebraic equations, otherwise known as the transcendental equation (trigonometric equation, exponential, logarithmic equation). The general said the N polynomial equation for n algebraic equation, when n 1, the equation is nonlinear. Generally slightly complicated algebraic equation 3 times above or beyond the equation, it is difficult or even impossible to obtain the exact solution. This paper will introduce some approximate numerical solution of the nonlinear equations root of.Key words: nonlinear equation; numerical solution; approximate root目 录 1 题目内容.1 1.1 题目的复述12 问题分析.22.1问题的分析. .23 算法描述.33.1 简单迭代法.33.1.1 简单迭代法的原理.33.1.2 简单迭代法的几何解析.33.1.3 简单迭代法的收敛依据.33.1.4 简单迭代法收敛的条件.33.1.5 简单迭代法的局部收敛性.43.1.6 简单迭代法的收敛阶.43.2 牛顿迭代法43.2.1 牛顿迭代法原理.43.2.2 牛顿迭代法的几何解析.53.2.3 牛顿迭代法的收敛性.53.2.4 牛顿迭代法的收敛速度.53.2.5 迭代过程的加速.63.3 弦割法64 简短源程序及有关运行结果.8参考文献.16附录.171 题目内容1.1 题目的复述（1）用简单迭代法求下列方程的根，要求有6位有效数字， 改变初值的选取，对出现的情况进行总结分析；构造收敛速度尽可能高的迭代法，并求根。（2）用牛顿法求下列方程的根，要求有6位有效数字，x=ctgx；改变初值的选取，对出现的情况进行总结分析；若要求方程的最小正根和在 附近的根，初值应如何选取？ 并讨论初值的变化对收敛的影响。（3）探讨用其它方法来求（1）和（2）中的非线性方程的根（如二分法、弦割法、抛物线法等）。（4）上面计算结果精度可达10位以上有效数字吗？说明实现过程，并举例。3 问题分析2.1问题的分析我们都会解一元一次方程和一元二次方程，三次以上方程就不会解了。事实上，三次和四次方程的求根公式很复杂，五次以上代数方程一般无求根公式，超越方程也只能求近似解。考察形式如下的方程：该方程是隐式的，也不能直接得出它的根，只能通过迭代法求出它的近似解。如果给出根的某个猜测值x0，将它代入方程式中，即可求得x1=g(x0)。然后又可以取x1为猜测值，代入方程式中，如此反复迭代。如果按以下公式：，k=0,1,2,确定的数列xk有极限x*=limkxk,则称方程迭代过程收敛。这时迭代值x*显然是方程的根。本次课题是用迭代法求非线性方程根。首先我们要理解迭代法求解非线性方程根的基本算法，确定迭代格式，如（1）中方程，构造迭代格式为：xk+1=33xk。然后按题目要求，将相关求非线性方程迭代算法用c+语言实现编程，在程序运行中输入初始值，求出方程根。最后用多种迭代法分别用不同的初始值进行求方程根，对得到的收敛速度和求根结果进行总结分析。3 算法描述3.1简单迭代法3.1.1 简单迭代法的原理简单迭代法的基本思想是：设方程（1）有解，把方程改写为等价形式（2）选定的初始值x0进行迭代：（3）得迭代序列。当k 足够大时，用xk作为f(x) = 0的近似解。这样求解方程f(x)=0根近似值的方法称为简单迭代函数，g(x)称为迭代函数；（3）式称为迭代格式。3.1.2 简单迭代法的几何解析求方程的根，在几何上就是求直线y=x与曲线y=g(x)交点的横坐标。3.1.3简单迭代法的收敛依据定理 若 ，则 （设连续）（即根）。3.1.4 简单迭代法收敛的条件定理1（充分条件）若g (x)满足如下条件（1） x1, x2I, $q (0, 1) 使得| g (x2)g (x1)| q |x2 x1| （Lipschitz条件）；（2） ，则（1）存在唯一点使；（2），由（3）式得xk且。（3）。注（1）条件（1）可改为，；（2）可以近似代替。3.1.5 简单迭代法的局部收敛性若，使对都收敛，则称上迭代是局部收敛的。定理2 若在根的某个邻域内有连续导数，且，则上迭代有局部收敛性。3.1.6 简单迭代法的收敛阶定义 设某迭代有局部收敛性，记ek=sxk0, k=0, 1, , 如果存在正实数r和c使成立，则称该迭代是r阶收敛的。r=1时又称有线性收敛速度；r=2称平方收敛。定理3 设I = a, b，s = g(s) I，g (k) (s)=0, k=1, 2, m1, g (m) (s) 0，则对任何x0 I (x0 s)，由迭代法产生的序列xk以m阶敛速收敛于s。3.2牛顿迭代法3.2.1牛顿迭代法原理设已知方程的近似根,则在附近可用一阶泰勒多项式近似代替.因此, 方程可近似地表示为.用表示的根,它与的根差异不大.设,由于满足解得重复这一过程,得到迭代格式这就是著名的牛顿迭代公式,它相应的不动点方程为.3.2.2牛顿迭代法的几何解析在处作曲线的切线，切线方程为。令，可得切线与轴的交点坐标，这就是牛顿法的迭代公式。因此，牛顿法又称“切线法”。3.2.3牛顿迭代法的收敛性计算可得,设是的单根,有,则,故在附近,有.根据不动点原理知牛顿迭代法收敛.3.2.4牛顿迭代法的收敛速度定理(牛顿法收敛定理) 设在区间上有二阶连续导数,且满足,在上不变号, 在上不等于0,令有.则对任意,牛顿迭代格式收敛于在中的唯一实根,并且:(1) (2)(3) ,牛顿迭代法为2阶收敛.3.2.5迭代过程的加速对不动点方程,它导出的迭代过程有可能发散,也可能收敛得非常缓慢.这时,我们有没有办法改进不动点方程,让迭代过程收敛得快一些呢?(1)一个简单的方法 注意到和都是不动点方程,他们的加权平均也是不动点方程,而且与有完全相同的不动点.适当选取的值,可以使发散的迭代过程变得收敛,使收敛慢的迭代过程变得收敛迅速.(2)加速的原因 在下面的实验中我们可以看到,在不动点附近的导数值在很大程度上决定了迭代过程的收敛性.的绝对值越小,收敛性越好.因此,选择使得.计算得到理想的值为,相应可计算出.(3) 的选取 于理想的值为,当变换不大时可以取近似计算.(4)回到牛顿迭代法的讨论 为求解方程,可以使用不动点方程,相应的迭代函数为.对进行加速,所以,牛顿迭代法是对基本迭代格式进行加速的结果.3.3 弦割法为了避免计算导数，在牛顿迭代公式中，用差商fxn-fxn-1xn-xn-1代替导数fxn，得：xn+1=xn-fxnfxn-fxn-1（xn-xn-1）（n=0,1,2，）该迭代格式被称为弦割法。从几何上看，式xn+1=xn-fxnfxn-fxn-1（xn-xn-1）实际上是由曲线上两点（xn-1，fxn-1）和（xn，fxn）确定割线，该割线与 x 轴交点的横坐标即为xn+1，故弦割法又称为割线法。弦割法和牛顿迭代法都是线性化方法 ， 牛顿迭代法在计算xn+1时只用到前一步的值 xn，而弦割法用到前面两步的结果xn和xn-1，因此使用弦割法必须先给出两个初始值x0，x1。4 简短源程序及有关运行结果（1）用简单迭代法求下列方程的根，要求有6位有效数字，改变初值的选取，对出现的情况进行总结分析；构造收敛速度尽可能高的迭代法，并求根。该题的相关简短源程序如下：int main()double x,y,m; static int k=1;cout-使用简单迭代法求解方程根-endl;coutx;cout迭代过程及次数如下:endl;doy=pow(3.0*x,1.0/3.0);m=fabs(y-x); x=y;coutk+ setprecision(15)x1e-6); -k;cout方程迭代次数为：kendl最后方程的根为（保六位有效数字）：setprecision(6)xendl;return 0;当用户输入初始值x：1.7时，运行结果如下：-使用简单迭代法求解方程根-请输入x的初始值：1.7迭代过程及次数如下:1 1.721300620726322 1.72845997268993 1.730853034498634 1.731651457809925 1.731917680750586 1.732006430825827 1.732036015194868 1.73204587676359 1.7320491639655310 1.7320502597009211 1.73205062494621方程迭代次数为：11最后方程的根为（保六位有效数字）：1.73205当用户输入初始值x：0.5时，运行结果如下：-使用简单迭代法求解方程根-请输入x的初始值：0.5迭代过程及次数如下:1 1.144714242553332 1.508711197669533 1.654153428718194 1.705685724599995 1.723217473799126 1.729101343263787 1.731067094209068 1.731722841018549 1.731941478484610 1.7320143637739811 1.7320386595520412 1.7320467582204713 1.7320494577850214 1.73205035764081方程迭代次数为：14最后方程的根为（保六位有效数字）：1.73205分析总结：由以上的1.7和0.5的初始值改变选取，得知改变初始值的选取，简单迭代法求得方程的根是一样的。但是不同初始值的选取，迭代次数是有区别的，初始值取1.7要比初始值0.5的迭代次数要少，也就是收敛迭代要快些。可见，迭代收敛速度对初值极为敏感，我应注意对初值的选取，这对我们的迭代结果非常重要。为了加快迭代收敛速度，我们构造收敛速度更快些的牛顿迭代法，相应的简短源程序如下：int main()double x,y,m; static int k=1;cout-从简单迭代改用牛顿迭代-endl;coutx;cout迭代过程及次数如下:endl;doy=(x*x+3)/(2*x);m=fabs(y-x); x=y;coutk+ setprecision(15)x1e-6); -k;cout方程迭代次数为：kendl最后方程的根为（保六位有效数字）：setprecision(6)xendl;return 0;当用户输入初始值x：1.7时，运行结果如下：-从简单迭代改用牛顿迭代-请输入x的初始值：1.7迭代过程及次数如下:1 1.732352941176472 1.732050833915913 1.73205080756888方程迭代次数为：3最后方程的根为（保六位有效数字）：1.73205当用户输入初始值x：0.5时，运行结果如下：-从简单迭代改用牛顿迭代-请输入x的初始值：0.5迭代过程及次数如下:1 3.252 2.086538461538463 1.762163239985824 1.732308093206635 1.732050826675156 1.73205080756888方程迭代次数为：6最后方程的根为（保六位有效数字）：1.73205（2）用牛顿法求下列方程的根，要求有6位有效数字，x=ctgx；改变初值的选取，对出现的情况进行总结分析；若要求方程的最小正根和在附近的根，初值应如何选取？ 并讨论初值的变化对收敛的影响。该题的相关简短源程序如下：int main()double x,y,m; static int k=1;cout-牛顿迭代法-endl;coutx;cout迭代过程及次数如下:endl;doy=x-(x-1/tan(x)/(1+1/(sin(x)*sin(x);m=fabs(y-x); x=y;coutk+ setprecision(15)x1e-6); -k;cout方程迭代次数为：kendl最后方程的根为（保六位有效数字）：setprecision(6)xendl;return 0;当用户输入初始值x：2时，运行结果如下：-牛顿迭代法-请输入x的初始值：2迭代过程及次数如下:1 0.8876611517807192 0.8599410133749193 0.8603335047698944 0.860333589019376方程迭代次数为：4最后方程的根为（保六位有效数字）：0.860334当用户输入初始值x：99.999时，运行结果如下：-牛顿迭代法-请输入x的初始值：99.999迭代过程及次数如下:1 79.18830275030992 58.37492441904083 30.02376561238314 15.16383411639745 11.60969388477696 6.678111057138157 6.126380405811888 5.82995850284259 4.5616888465366410 2.3819018284389311 1.2769161363882612 0.81111199239969313 0.8589164274799114 0.86033248954980615 0.86033358901871916 0.86033358901938方程迭代次数为：16最后方程的根为（保六位有效数字）：0.860334当用户输入初始值x：100时，运行结果如下：-牛顿迭代法-请输入x的初始值：100迭代过程及次数如下:1 79.24455826733552 56.1657067166953 48.98009936526134 25.36015096094885 24.34247719974696 15.84360615686877 15.69066513187038 15.66868244437539 15.605375565850410 15.342602594027411 13.309851108231712 9.4697191905524213 9.49543477657814 9.518416085549215 9.528207446085216 9.5293224294615117 9.5293344040099718 9.52933440536196方程迭代次数为：18最后方程的根为（保六位有效数字）：9.52933当用户输入初始值x:100.01时，运行结果如下：-牛顿迭代法-请输入x的初始值：100.01迭代过程及次数如下:1 79.80805917956892 41.90645661586943 23.97081696827374 12.8158821725195 12.30487916296916 11.29993282469237 5.765928260206258 4.287666079502779 2.547876791859410 1.5873611512118811 0.78550743758189212 0.8569425226310113 0.86032727627411614 0.86033358899760715 0.86033358901938方程迭代次数为：15最后方程的根为（保六位有效数字）：0.860334分析总结：通过对初始值的改变选取，我们可以得到方程的多个根，如上，我们取了初始值分别为2、99.999、100和100.01，可得到方程的两个根：0.860334和9.52933。同时，由不同初始值的选取得到的结果说明，初始值的选取不同，不但能得到不同的方程根，而且还影响了迭代收敛速度的快慢。经过多次的初始值选取，得出方程最小的正根为：0.860334，x=100附近的根为：9.52933。由上我们同时也得出，如果初始值越接近方程根，则方程的迭代速度越快。所以选取初始值时，我们可以先猜测方程根的大概值作为初始值，这样的初始值更接近方程根，可以使方程迭代收敛速度更快。当然由式子可得到除了x=0之外的初始值，都可使方程迭代收敛。（3）探讨用其它方法来求（1）和（2）中的非线性方程的根（如二分法、弦割法、抛物线法等）。该题的相关简短源程序如下：int main()double y,m,g1,g2,x0,x1; static int k=1;cout-用弦割法求解(1)中的方程根-endl;coutx0x1;cout迭代过程及次数如下:endl;dog1=x0*x0-3; g2=x1*x1-3;y=x1-g2*(x1-x0)/(g2-g1);m=fabs(y-x0); x0=x1;x1=y;coutk+ setprecision(15)x11e-6); -k;cout方程迭代次数为：kendl最后方程的根为（保六位有效数字）：setprecision(6)x1endl;return 0;当用户输入初始值x0和x1:1.7 1.8时，运行结果如下：-用弦割法求解(1)中的方程根-请输入两个初始值x0和x1：1.7 1.8迭代过程及次数如下:1 1.731428571428572 1.732038834951463 1.732050809719844 1.732050807568875 1.73205080756888方程迭代次数为：5最后方程的根为（保六位有效数字）：1.73205int main()double y,m,g1,g2,x0,x1; static int k=1;cout-用弦割法求解(2)中的方程根-endl;coutx0x1;cout迭代过程及次数如下:endl;dog1=x0-1/tan(x0); g2=x1-1/tan(x1);y=x1-g2*(x1-x0)/(g2-g1);m=fabs(y-x0); x0=x1;x1=y;coutk+ setprecision(15)x11e-6); -k;cout方程迭代次数为：kendl最后方程的根为（保六位有效数字）：setprecision(6)x1endl;return 0;当用户输入初始值x0和x1:15 33时，运行结果如下：-用弦割法求解(2)中的方程根-请输入两个初始值x0和x1：15 33迭代过程及次数如下:1 -2.276784133986472 0.7776074592979283 1.02913770695734 0.8675912204944225 0.8597410085336056 0.8603359278379287 0.8603335897769198 0.8603335890193799 0.86033358901938方程迭代次数为：9最后方程的根为（保六位有效数字）：0.860334（4）上面计算结果精度可达10位以上有效数字吗？说明实现过程，并举例。可以，我们随便改变任一题中的代码最后输出行中setprecision(6)函数，只要将其中的数字6改成数字10，即可输出10位有效数字的结果。我们将(1)题中的代码改成十位有效数字输出结果，如下：int main()double x,y,m; static int k=1;cout-使用简单迭代法求解方程根-endl;coutx;cout迭代过程及次数如下:endl;doy=pow(3.0*x,1.0/3.0);m=fabs(y-x); x=y;coutk+ setprecision(15)x1e-6); -k;cout方程迭代次数为：kendl最后方程的根为（保十位有效数字）：setprecision(10)xendl;return 0;当用户输入初始值x：1.7时，运行结果如下：-使用简单迭代法求解方程根-请输入x的初始值：1.7迭代过程及次数如下:1 1.721300620726322 1.72845997268993 1.730853034498634 1.731651457809925 1.731917680750586 1.732006430825827 1.732036015194868 1.73204587676359 1.7320491639655310 1.7320502597009211 1.73205062494621方程迭代次数为：11最后方程的根为（保十位有效数字）：1.732050625参考文献1 严蔚敏 吴伟民数据结构(C语言版)M.北京：清华大学出版社，1997.42 李庆扬，王能超，易大义.数值分析M.武汉.华中科技大学出版社，2006.7.3 清华大学、北京大学计算方法编写组。计算方法M。北京。科学出版社，19804 孙淑霞，肖阳春，魏琴等.C/C+程序设计教程（第2版）。北京：电子工业出版社，2007.035 谭浩强。C+程序设计。北京：清华大学出版社，2004,06附件源程序及有关运行结果：（1）简单迭代源程序：#include#include#include using namespace std;int main()double x,y,m; static int k=1;cout-使用简单迭代法求解方程根-endl;coutx;cout迭代过程及次数如下:endl;doy=pow(3.0*x,1.0/3.0);m=fabs(y-x); x=y;coutk+ setprecision(15)x1e-6); -k;cout方程迭代次数为：kendl最后方程的根为（保六位有效数字）：setprecision(6)xendl;return 0;改用牛顿迭代源程序：#include#include#include using namespace std;int main()double x,y,m; static int k=1;cout-从简单迭代改用牛顿迭代-endl;coutx;cout迭代过程及次数如下:endl;doy=(x*x+3)/(2*x);m=fabs(y-x); x=y;coutk+ setprecision(15)x1e-6); -k;cout方程迭代次数为：kendl最后方程的根为（保六位有效数字）：setprecision(6)xendl;return 0;（2）#include#include#include using namespace std;int main()double x,y,m; stati