非线性方程求解算法的程序设计及比对课程设计毕业设计.doc

题 目：非线性方程求解算法的程序设计及比对摘要由于五次及其以上代数方程式大多不能用代数公式求解非线性方程的解.或者求解非常复杂。而在工程和科学技术中许多问题常常归结为求解非线性方程式问题.所以需要研究非线性方程的数值解法的问题是非常重要.来适应我们社会的需要.本课题主要介绍非线性方程的数值解法是直接从方程出发，逐步缩小根的存在区间，或逐步将根的近似值精确化，直到满足问题对精度的要求，主要的方法有二分法，迭代法，牛顿法，弦截法等。并写出这几种非线性方程的数值解法的算法和程序及其优缺点和计算条件.关键词 二分法;牛顿迭代法;弦截法法;程序框架图;C语言编程 目录引言1第一章 非线性方程求解算法21.1 二分法21.1.1 二分法的简介21.1.2 二分法的原理21.1.3 二分法的算法31.2 不动点迭代法41.2.1不动点迭代法的简介41.2.2不动点迭代法的几何意义41.2.3不动点迭代法的算法51.3 牛顿迭代法61.3.1牛顿迭代法的简介61.3.2牛顿迭代法的原理61.3.3牛顿迭代法的算法71.4 弦截法81.4.1弦截法的简介81.4.2弦截法的原理81.4.3弦截法的算法9第二章 非线性方程求解的C语言算法对比112.1 C语言求解非线性方程的根112.1.1构造非线性方程迭代公式112.1.2计算迭代公式112.2 C语言算法比较分析14参考文献16附录A17附录B18引言代数方程求根问题是一个古老的数学问题,早在16世纪就得到了三次、四次方程的求根公式.一般(五次及其以上)代数方程式不能用代数公式求解.在工程和科学技术中许多问题常常归结为求解非线性方程式问题.因此,需要研究用数值方法求得满足一定精度的代数方程式的近似解.根的数值方法,其中是连续的称为非线性方程,此类方程除少数情形外,只能求近似解.例如,其根为 像这种方程是可以直接的方法求出解析解.但对于对于多项式方程当时,就不能得到解析解.对于更一般的情况（如超越方程）就更难求得解析解了,更就不存在根的解析表达式,在科学研究和科学计算中常常碰到非线性方程求解问题.非线性方程的解一般不能解析求出.所以数值解法显得非常重要,而数值解法在实际中的实现则更为重要.本课题主要是应用数值解法结合计算机语言来求解非线性方程的解,其中包括的数值解法有二分法、迭代法、牛顿法、弦截法等.主要用的计算机语言C语言、等.正好符合用计算机语言来处理复杂计算量的数学问题,以此来分析几种非线性数值解法的优缺点,计算量的大小.来选出更加适合的计算方法.第一章 非线性方程求解的算法1.1 二分法1.1.1 二分法的简介二分法又称二分区间法,是求解方程的近似根的一种常用的简单方法.设函数在闭区间上连续,且,根据连续函数的性质可知,在内必有实根,称区间为有根区间.为明确起见,假定方程在区间内有惟一实根.二分法的基本思想是: 首先确定有根区间,将区间二等分, 通过判断的符号, 逐步将有根区间缩小, 直至有根区间足够地小, 便可求出满足精度要求的近似根.1.1.2二分法的原理设方程在区间内有根,二分法就是逐步收缩有根区间,最后得出图 1.1 二分法原理图 所求的根,如上图所示,我们可以写出一下内容.(1) 输入有根区间的端点及预先给定的精度；(2) 计算 ；(3) 若,则;否则；(4) 若,则输出方程满足精度要求的根,计算结束；否则转(2).继续执行前面的步骤.开 始 开 始 输 入a,b,(a+b)/2xxb|b-a|eps);Step 7 Output the solution of equation: ; STOP.1.2 不动点迭代法1.2.1 不动点迭代法的简介 迭代法的基本思想是逐次逼近,即首先给出方程的根的一个近似初始值,然后反复使用迭代公式校正这个初始值,逐步精确化,直到满足预先给出的精度要求为止. 首先设法把方程化为下列等价形式(称为迭代函数) (1-1)然后按式(1-1)构造迭代公式 (1-2) 在有根区间上取一点作为方程根的初始近似根,代入式（1-2)右端,求得,再把作为预测值,进一步得到,如此反复进行下去,得到一个近似根的序列如果迭代序列收敛于,则当连续时,便是方程的根. 对预先给定的精度要求,只要某个是满足,即可结束计算并取. 1.2.2 不动点迭代法的几何意义用迭代法求方程在区间内的实根.可以写出一下下几种迭代格式,用Mathematica 画出它们的图形,以此来观察它们的几何意义. y x -2-112-2-11图 1.3 迭代几何图 -112-112图 1.4 迭代几何图-2-11x-2246y图 1.5 迭代几何图1.2.3 不动点迭代法的算法由不动点迭代法程序框架图（见附录A）写出一下迭代算法给定初始近似值 ,求的解.输入: 初始近似值; 容许误差TOL; 最大迭代次数Nmax.输出: 近似解或失败信息.Step 1 Set k = 1;Step 2 While ( k Nmax) ; do steps 3-6 Step 3 Set ; /* 计算 x */ Step 4 If TOL then Output (x); /*成功*/ STOP; Step 5 Set k+; Step 6 Set ; /* 更新 */Step 7 Output (The method failed after Nmax iterations); /*不成功 */ STOP.1.3 牛顿迭代法1.3.1 牛顿迭代法的简介简单的迭代法是用直接的方法从原方程中隐含地解出,从而确定出.而牛顿迭代法是用一种间接而特殊的方法来确定.牛顿迭代法的基本思想是,将非线性方程的求根问题归结为计算一系列线性方程的根. 设是方程的一个近似根,将在附近作一阶泰勒展开,则有,于是方程可近似表示成. 这是一个线性方程式,设,则上式的解为 , 取作为原方程的新的近似根,即令 则称上式为牛顿迭代公式.1.3.2 牛顿迭代法的原理 y y=f(x) Pk Pk+1 Pk+2 x* xk+2 xk+1 xk x 图 1.6 牛顿迭代法程几何意义图从图 1.6可以看出,方程的根是曲线与轴交点的横坐标,设是根的某个近似值,由此来求出过曲线（图 1.7）的横坐标为的点引切线交轴于, 并将其作为新的近似值,重复上述过程,我们可以得到可见一次次用切线方程来求解方程的根,所以亦称为牛顿切线法.开 始输 入x0,N1k N k+1 kx1 x0 YynykN?n输出输出奇异标志结 束输出迭代失败标志 图 1.7 牛顿迭代法程序框架图1.3.3 牛顿迭代法的算法从图 1.7流程图,写出一下牛顿算法,并且用c语言编写运算程序. 用Newton法求方程一个解. 输入 初始值；误差容限TOL；最大迭代次数. 输出 近似解或失败信息.Setp 1 .Setp 2 对 做Setp 3-4 .Setp 3 .Setp 4 若,则输出,停机,否则.Setp 5 输出(Method failed); 停机 在第4步中的迭代终止准则可用 1.4 弦截法1.4.1 弦截法的简介弦截法也称为割线法.如果函数求导困难,则割线较切线更为实用.牛顿迭代法虽然具有收敛速度快的优点,但每迭代一次都要计算导数,比较复杂时,不仅每次计算带来很多不便,而且还可能十分麻烦,如果用不计算导数的迭代方法,往往只有线性收敛的速度.弦截法便是一种不必进行导数运算的求根方法.弦截法在迭代过程中不仅用到前一步处的函数值,而且还使用处的函数值来构造迭代函数,这样能提高迭代的收敛速度.为避免计算函数的导数,使用差商替代牛顿公式中的导数,便得到迭代公式 称为弦截迭代公式,相应的迭代法称为弦截法.1.4.2 弦截法的原理弦截法的几何意义（如图1.8）曲线上两点,的割线来代替曲线,然后用此割线与x轴交点的横座标作为方程的近似根再过P1点和作割线求出,再过P2点和点作割线求出,余此类推,当收敛时可求出满足精度要求的. P1 y=f(x) x0 x2 x3 x1 x* P3 P0 P2图 1.8 弦截法几何意义图开始输 入x0, x1,N1k yx0 x2nynx1 x2 yk+1 kx1 x0x2 x1f(x1)f(x0)f(x2) f(x1)nykN?nyn输出x2输出x2输出奇异标志结 束输出迭代失败标志 图 1.9 弦截法程序框架图1.4.3 弦截法的算法由图 1.9 弦截法的程序框架图,写出如下算法：用弦截法求方程的一个解.输入 初始值,误差容限TOL;最大迭代次数m.输出 近似解,或失败信息.Setp 1 ; ; ; ; Setp 2 对做Setp3,4. Setp 3 . Setp 4 若,则输出,停机. 否则; ; ; ; Setp 5 输出（”Method failed”）; 停机.第二章 非线性方程求解的C语言算法对比2.1 C语言求解非线性方程的根2.1.1 构造非线性方程迭代公式根据上一章的理论知识,本章进行数据计算,首先构造几种非线性方法解法的迭代公式,举下面的非线性方程为例,写出几种算法的迭代格式.并以此来计算它们各自的结果,来为下一小节的算法比较作为例证,所以本节的计算算法的正确与否决定下一节结论的正确与否.所以我们首先用数学软件Mathematica 5来求取方程（2-1）在的根,用来比较我们算法正确与否.用Mathematica 5求解方程的根,得到四个根,取的根 例2.1 方程在中的根 二分法： （2-1）不动点迭代法： （2-2）牛顿迭代法： （2-3）弦截法： （2-4）2.1.2 计算迭代公式 下面用二分法的程序来（程序详见附录B的二分法程序）计算（2-1）式的在的根,误差度在,初始值计算把结果写在表 2-1表 2-1 二分法的计算结果备注11.0000001.5000001.5000000.5000005.0625001. 2. 3.初始值21.0000001.2500001.2500000.2500001.31640631.0000001.1250001.1250000.1250000.00805741.0625001.1250001.0625000.062500-0.53025851.0937501.1250001.0937500.031250-0.27006461.1093751.1250001.1093750.015625-0.13329571.1093751.1250001.1171880.007813-0.06319881.1210941.1250001.1210940.003906-0.02771691.1230471.1250001.1230470.001953-0.009866101.1240231.1250001.1240230.000977-0.000914111.1240231.1245121.1245120.0004880.003569121.1240231.1245121.1242680.0002440.001327131.1240231.1241461.1241460.0001220.000206141.1240841.1241461.1240840.000061-0.000354最后的结果 ：=1.124115 ,由表 2-1二分法的最后结果与比较,我们可以看出与Mathematica 5求得结果在误差范围之内几乎一致,所以此算法是正确的,是可以应用到下一小节,进行算法比较.下面用不动点迭代法的C语言的程序来（程序详见附录B不动点迭代法C语言程序）计算（2-2）式的在的根,误差度在,初始迭代值为,计算把结果写在表 2-2.计算完成后与进行比较,来得出算法的正确与否.表 2-2 不动点迭代的计算结果备注11.2039480.7960521. 2. 3. 初始值21.1319080.07203931.1248870.00702141.1241980.00068951.1241300.000068最后结果: =1.124130 , k=5由表 2-2不动点迭代法的最后结果与比较,我们可以看出与Mathematica 5求得结果在误差范围之内几乎一致,所以此算法是正确的,是可以应用到下一小节,进行算法比较.下面用牛顿迭代法的C语言的程序来（程序详见附录B牛顿迭代法C语言程序）计算（2-3）式的在的根,误差度在,初始迭代值为,计算把结果写在表 2-3.计算完成后与进行比较,来得出算法德正确与否.表 2-3 牛顿迭代的计算结果备注11.51282119.00000039.0000000.4871791. 2. 3. 初始值21.2322855.30224018.9004030.28053631.1349771.11068611.4141620.09730841.1242440.1007579.3880930.01073251.1241230.0011159.1808240.00012161.1241230.0000009.1784960.000000最后结果: =1.124123 , k=6由表 2-3牛顿迭代法的最后结果与比较,我们可以看出与Mathematica 5求得结果在误差范围之内几乎一致,所以此算法是正确的,是可以应用到下一小节,进行算法比较.下面用弦截法的C语言的程序来（程序详见附录B弦截法C语言程序）计算（2-4）式的在的根,误差度在,初始迭代值为,计算把结果写在表 2-4.计算完成后与进行比较,来得出算法的正确与否.表 2-4 弦截法的计算结果备注11.0500000.9500001. 2. 3.初始值 ,21.0804650.03046531.1277450.04728041.1239540.00379151.1241220.000168最后结果: =1.124122 , k=5由表 2-4弦截法迭代法的最后结果与比较,我们可以看出与Mathematica 5求得结果在误差范围之内几乎一致,所以此算法是正确的,是可以应用到下一小节,进行算法比较.2.2 C语言算法比较分析通过上一小节的计算,本节来分析分析几种算法的优缺点,以便以后更好的应用到学习和工作中,做到学以致用,也是这次课题的主旨,活学活用.观察表 2-5的计算结果,可以直观的看出来,牛顿法,弦截法,不动点迭代法的收敛速率差不多,但二分法明显落后前三种收敛速率,所以得到一下结论.1.二分法是电子计算机上一种常用的算法,它的具有简单和易操作的优点,缺点是收敛较慢,且不能求重根. 2.牛顿迭代法牛顿法优点：牛顿迭代法具有至少平方收敛的速度,所以在迭代过程中只要迭代几次就会得到很精确的解.这是牛顿迭代法比简单迭代法优越的地方.特别是当迭代点充分靠近精确解时.牛顿法的缺点：选定的初值要接近方程的解,否则有可能得不到收敛的结果.再者,牛顿迭代法计算量比较大.每次迭代要计算一次导数值,当表达式复杂或无明显表达式时求解困难.对重根收敛速度较慢（线性收敛）.牛顿法是现在最常用的迭代方法.3. 弦截法的收敛阶虽然低于Newton法,但是迭代一次只要计算一次,不需要计算导数值,所以效率高,实际问题中经常使用. 弦截法比牛顿迭代法收敛速度稍慢,但它的计算量比牛顿迭代法小,特别当都函数的导数的计算比较复杂时,弦截法更显示了它的优越性.表 2-5 迭代结果迭代次数二分法不动点迭代法牛顿法弦截法k1.5000001.2039481.5128211.05000011.2500001.1319081.2322851.08046521.1250001.1248871.1349771.12774531.0625001.1241981.1242441.12395441.0937501.1241301.1241231.12412251.1093751.12412361.11718871.12109481.12304791.124023101.124512111.124268121.124146131.124146141.124115 二分法是逐步将含根区间分半,主要用来求实根;迭代法是一种逐次逼近的方法,起着把根的精确值一步一步算出来的作用;牛顿法具有较快的收敛速度,但对初值选取要求较高.弦截法避开了导数的计算,具有超线性的收敛速度,每计算一步,要用到前面两步的信息. 参考文献1 林成森.数值计算方法.北京:科学出版社.2005年2 金聪.熊盛武.数值分析.武汉:武汉理工大学出版社.2003年3 颜晖 .C语言程序设计.北京:高等教育出版社.2008年4 张立科.MATLAB 7.0 应用.北京：人民邮电出版社.2006年5 贾得彬.数值计算方法.北京：水利水电出版社.2007年6 李庆扬,王能超,易大义.数值分析基础.北京：清华大学出版,2008年.7 徐士良.数值方法与计算机实现.北京：清华大学出版社.2006年.附录 A 本附录包含不动点迭代的流程图.开 始 输 入x0,N1k k+1kx1 x0y|x1- x0|?ynkN?n输出近似根x1输出迭代失败标志结 束 附录 B本附录 含二分法,不动点迭代,牛顿法,弦截法的的C语言计算程序.二分法C语言程序#include #define eps 0.0001 /* 容许误差 */double jisuan(double x) return pow(x,4)+2*x*x-x-3 ;main() double a,b,y,x,h,j; int k=0; printf(a=); scanf(%lf,&a); printf(b=); scanf(%lf,&b); if(jisuan(a)*jisuan(b)=0) /* 判断是否符合二分法使用的条件 */ printf(Not bisect of bisect); return; do x=(a+b)/2; k+; j=jisuan(x);/* f(x)的结果 */ if(jisuan(a)*jisuan(x)0) /* 如果f(a)*f(x)eps);/*判断是否达到精度要求,若没有达到,继续循环*/ x=(a+b)/2; /* 取最后的小区间中点作为根的近似值 */ printf(n The zui hou root is x=%lf, k=%dn,x,k);不动点迭代法C语言程序#include #define eps 0.0001 /* 容许误差 */double jisuan(double x) double h ; h=sqrt(sqrt(x+4)-1); return h ; main() double x0,x1,h; int k=0; printf(input 迭代初值 x1: ); scanf(%lf,&x1); do x0=x1; x1=jisuan(x0); k+; h=fabs(x1-x0); printf(n k=%2d , x1=%lf ,h=%lf ,k ,x1,h); while(fabs(x1-x0)eps);/*判断是否达到精度要求,若没有达到,继续循环*/ printf(n最后结果The root is n); printf(x=%lf, k=%dn,x1,k);牛顿迭代法C语言程序#include#includedouble js1(double x) double j; j=pow(x,4)+2*pow(x,2)-x-3; return j; double js2(double c) double j; j=4*