非线性方程求根的数值方法04数本林一明1

1、非线性方程求根的数值方法林一明（广西民族大学数计学院04数本1班, 南宁 530006）摘 要: 本文讨论非线性方程的数值解，阐述了二分法、三分法、冒泡法、简单迭代法和牛顿迭代法原理。并对非线性方程的数值例子进行了近似计算，并比较了它们的收敛速度。关键词: 非线性方程；二分法；迭代法；收敛性Numerical Method of the Root for Solving Nonlinear EquationLin Yiming(College of Mathematics and Computer Science,Guangxi University for Nationalities, Na

2、nning 530006)Abstract: In this paper, we study numerical solution of the nonlinear equation, the procedures of dichotomy, rule of thirds, bubble method, the simple iterate method and the Newton iterate method are expounded, And has carried on the approximate calculation to the nonlinear equation, an

3、d compare their convergence rate.Keywords: nonlinear equation；dichotomy；iteration method；convergence0 引 言代数方程求根问题是个古老的数学问题，在19世纪，理论上就证明了n5次一般代数方程不能用代数公式求解，超越方程和工程及科学技术中的许多问题都难以求得精确解，这些方程都归类为非线性方程。因此，需要研究用数值方法求得满足一定代数精度的非线性方程的近似解。当给定非线性方程范围内的某个根，而根的粗略位置已从问题的物理背景或应用其它方法获知，要求取非线性方程精度范围内的根。本文着重讨论非线性方程的数

4、值解法，给出二分法、三分法、冒泡法、简单迭代法和牛顿迭代法的基本原理，并对非线性方程的数值例子进行了近似计算。1 二分法每次把的零点所在小区间收缩一半，使区间的两个端点逐步迫近函数的零点，以求得零点的近似值，这种方法叫做二分法3。设在上连续，假定，取中点，检查的符号，若，则就是方程的一个根；若，记为，为，则得有根区间；若，记为，为，则得有根区间，它的长度为区间的一半。对区间，令，再用同样的方法，可得新的有根区间，如此反复进行下去，其中每一个区间长度都是前一区间长度的一半，有这就是方程的根，而即为方程的近似根，且有估计误差其方法的matlab程序(见附录1)。二分法具有计算简单，易于程序实现的优

5、点。2 三分法三分法是二分法的推广，只是比二分法复杂一些，但求解速度比二分法快。设在上连续，假定，并且对有，取， ，检查,的符号，若,就是方程的一个根，或者,就是方程的一个根。若，记为，为，则得到方程的有根区间；若,记为，为，则得到方程的有根区间；若，记为，为，则得到方程的有根区间；新区间的长度为区间的。如此反复进行下去，其中每一个区间是前一个区间长度的，且有而为方程一个实根的近似值，且它满足关系式: ，这表明方程近似根的绝对误差小于最初区间长度的分之一，三分法Matlab程序实现过程见附录2.3 冒泡法 三分法和二分法其求出方程的近似解的个数比较多后才能得到比较精确的解,冒泡法也是二分法的进

6、一步的推广,求解非线性方程的一种相对简单、容易编程，而且收敛速度比二分法和三分法要快的一种数值算法。冒泡法实现的具体过程如下。定理1 设函数在闭区间上存在二阶连续导数且满足条件：(1)在区间上保号,(2),(3),则冒泡法产生的的唯一解.证明 由条件（1），（2）知，函数f(x)在区间上为单调连续函数，因此在区间a,b上至多有一个根，再有条件（3）在内至少存在一个根，因此，在区间内存在唯一解.冒泡法的基本思想: 设函数在区间上符合定理1的条件，存在唯一的解x,把区间分成10等分，x分别取，, ，然后计算的值，用比较法找出绝对值最小的，并确定，若，则为方程的根，若，记，则得有根区间,方程根的区间

7、长度为原来的，即，再用同样的方法，可得到新的根区间,如此进行下去，其中每一个区间是前一个区间的，有，(k 为常数属于1至9这10个数字中的某一个数)，作为方程的一个实根的近似值，且它满足关系式 (k 为常数属于1至9这10个数字中的某一个数)上式表明方程近似值的绝对误差小于最初区间长度的分之一。Matlab程序的maobao.m函数见附录3。4 简单迭代法迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代法又分为精确迭代和近似迭代。“二分法”和“牛顿迭代法”属于近似迭代法。简单迭代法的基本思想: 设方

8、程有根，把方程化为等价方程因而有.选定s的初始近似值x0，用递推公式 （k=0,1,2,） （4.1）产生序列，在一定条件下，序列收敛于. 在收敛的情况下，当足够大时就可取作为方程的近似根。迭代公式（1）被称为求解方程f(x)=0的简单迭代法，其中称为迭代函数。因，故s是迭代函数的不动点。简单迭代法（4.1）又称为不动点迭代法.由迭代过程所产生的数列并不是都收敛于某一个数,与其迭代方程的撷取有关.定理2 设函数，在内可导，且满足两个条件：（1） 当时，（2） 当时，其中L为一常数。则有如下两个结论：1.当方程在区间上有唯一的根s;2.对任取的,简单的迭代法（4.1）产生的序列,且收敛于 s;证

9、明 (1)令,则，并由条件（1）可知若上面两个不等式中有一个等号成立，则方程（4.1）有根或 ;若两个都是严格不等式，则根据连续函数的介值定理，必存在,使,即方程（4.1）有根,今设有两个不同的使，,则由微分中值定理以及条件（2），有其中在与之间，因而，上式出现的矛盾证实.(2) 因，由条件（1）可知，又由条件（2）得其中在与s之间，因而，因，故有.收敛性定义：设序列收敛于s，并且，如果存在常数和常数,使得极限成立，或者使得当（某个正整数）时，成立，则称序列收敛于具有阶收敛速度，简称是阶收敛的。常数称为渐近收敛常数，也称为收敛因子。显然，大小反映了序列收敛的快慢程度， 越大收敛越快, =1时，

10、又序列是线性收敛的，此时必有0<c<=1; =2时,又称序列是平方收敛的;对于的情况,序列统称是超线性收敛的. 具体的matlab程序实现过程见附录4.5 Newton法牛顿法是牛顿在17世纪提出的一种求解方程，多数方程不存在求根公式，从而求精确根非常困难，甚至不可能，从而寻找方程的近似根就显得特别重要。用简单迭代法求方程(4.1)的根s，十分重要的问题构造迭代函数.为了使收敛速度的阶高一些,就尽可能使在处有更多阶导数等于零.现在令,为待定函数，但，则方程(4.1)与方程有共同的根s.现用条件确定. 由知，h(x)必须满足. 显然，取就具备这个条件，并且也满足.于是，被确定为它满足

11、. 由此得出下面的特殊的简单迭代法 (5.1)上式所表示的迭代法称为Newton(牛顿)法.定理34 设函数在闭区间上存在二阶连续导数且满足条件：(1) 在区间上保号,(2) , ,(3) ,(4) 设且,则牛顿迭代格式(5.1)产生的迭代序列收敛于方程的唯一解.下面对本定理的条件做些说明.(i)由条件（1）,（2）知，函数在区间上为单调连续函数，因此在区间上至多有一个根，再有条件（3）在内至少存在一个根，因此，在区间内存在唯一解.对于条件(1)和条件(3)仅可能产生下列四种情形:(1) ;(2)(3) ;(4) ;上述四种情形的几何图形如图所示.(ii)对于第一种情形,由于在区间上单调增加,

12、且由条件(4)知,所以,当时有，即满足条件(4)的必要条件是.(iii)证明对任意初值，由迭代公式(5.1)求出的逐次近似值都属于,且产生的序列单调增加。事实上，设表示曲线经过点的切线，由于在区间内,所以曲线上凸,切线必在曲线的上方，因此，从而有另外，设，由于是经过的切线，且单调增加，又有综合上面两种情形，可得连续函数满足,因此,在区间内存在一点使，即上式表明，由式(5.1)产生的序列单调增加且有上界，由极限存在的单调收敛准则知序列的极限存在，不妨设为，即.再对递推公式(5.1)两边取极限，可得由于，从而得，因此，也是的根，再由第一步知，方程仅有唯一的根，因此.6 数值算例以下的例子是各种方法

13、对同一方程的数值求法解的列表.例1. (解的误差数度为0.0001)(二分法,三分法,冒泡法取区间2,5,简单迭代法和牛顿法的初值取) 方法迭代次数n二分法三分法冒泡法迭代法牛顿法1.2.3.4.5.6.7.8.9.10.11.12.3.52.753.1253.31253.21883.17193.14843.13673.14263.14553.1473.146243.66673.22223.18523.13583.1443.14683.14633.23.143.1523.14723.1462122.69312.99073.09553.133.1413.14453.14573.1463.1461

14、7.09393.44483.15183.15183.1462例 2. (解的误差数度为0.0001)(二分法,三分法,冒泡法取区间0,1,简单迭代法和牛顿法的初值取) 方法迭代次数n二分法三分法冒泡法迭代法牛顿法1.2.3.4.5.6.7.8.9.10.11.12.13.14.0.50.250.3750.31250.343750.359380.351560.347660.34570.346680.347170.347410.347290.347350.666670.555560.407410.358020.353910.348420.347970.347360.34730.30.340.348

15、0.34720.347360.34730.50.3750.350910.347740.347350.34730.333330.347220.3473从以上两个图表来看:三分法，冒泡法是二分法的推广，这三种方法都比较直观，都是计算方程的解x的误差为0.0001，由上可知:冒泡法的计算的速度比较快。冒泡法、简单迭代法、牛顿迭代法计算的速度相对于另外两种方法来说都比较快，并且牛顿法是最快的。在例2中虽然在-2到0间有解，但当其迭代函数为时用简单迭代法求解中如果初值取0的时候，是得不到解的，其运行结果为: k x f(x)1 0 13 1.2392+0.6143i -2.2175+0.75519i4

16、1.4571+0.2933i -0.65373+0.96299i5 1.5105+0.12886i -0.16029+0.49332i6 1.5249+0.055442i -0.043026+0.22025i7 1.5294+0.023705i -0.013525+0.09521i8 1.531+0.010114i -0.004876+0.040776i9 1.5316+0.0043112i -0.0019155+0.017407i10 1.5319+0.0018371i -0.00078658+0.0074222i11 1.532+0.00078273i -0.00032975+0.0031

17、631i12 1.5321+0.00033348i -0.00013951+0.0013478i13 1.5321+0.00014207i -5.9258e-005+0.00057422i14 1.5321+6.0526e-005i -2.5213e-005+0.00024464i15 1.5321+2.5785e-005i -1.0736e-005+0.00010422i16 1.5321+1.0985e-005i -4.5725e-006+4.4401e-005i所以用简单迭代法求方程的数值解时，注意迭代函数的选取是很重要的。参考文献1 王沫然. MATLAB与科学计算(第2版)M. 北京

18、: 电子工业出版社,2004.2 万福永,戴浩晖,潘建瑜. 数学实验教程(Matlab版)M. 北京: 科学出版社, 2006.3 朱方生,李大美,李素贞. 计算方法M. 武汉: 武汉大学出版社, 2006.4 颜庆津. 数值分析(第三版) M. 北京: 航空航天大学出版社, 2006.注1: 以下的fun函数是例题函数注2: 简单迭代法和牛顿迭法是以例1为例子编写的程序，例2要修改程序里面的函数,其它的方法只改fun函数就可以运行了.附录1二分法的matlab程序:function erfen(a,b,esp)if feval('fun',a)*feval('fun&

19、#39;,b)<0; n=1; while abs(b-a)>esp; c=a+(b-a)/2; if feval('fun',a)*feval('fun',c)<0; b=c; disp(num2str(n),' ',num2str(c); elseif feval('fun',c)*feval('fun',b)<0; a=c; disp(num2str(n),' ',num2str(c); end if feval('fun',a)*feval('

20、fun',c)=0; disp(num2str(n),' ',num2str(c); break; end n=n+1; end end附录2三分法的matlab程序:function sanfen(a,b,esp)if feval('fun',a)*feval('fun',b)<0; n=0; while abs(b-a)>esp; n=n+1; if feval('fun',a)*feval('fun',b)<0; s=a:(b-a)/3:b; if feval('fun

21、9;,s(2)*feval('fun',s(3)<0; a=s(2);b=s(3); x0=(s(3)+s(2)/2; elseif feval('fun',a)*feval('fun',s(2)<0; b=s(2); x0=(a+s(2)/2; elseif feval('fun',s(2)=0; x0=s(2); break elseif feval('fun',s(3)=0; x0=s(3); break else a=s(3);x0=(s(3)+b)/2; end disp(num2str(n)

22、,' ',num2str(s(3); else break; end endend附录3冒泡法matlab 程序:function maobao(a,b,esp)if feval('fun',a)*feval('fun',b)<0; n=1; while abs(b-a)>esp; if feval('fun',a)*feval('fun',b)<0; s=a:(b-a)/10:b; a0=abs(feval('fun',s(2); k=2; for i=3:10; if abs(feval('fun',s(i)<a0; a0=abs(feval('fun',s(i); k=i; end end n=n+1; a=s(k-1); b=s(k+1); n s(k) elseif feval('fun',a)=0; disp(n,a) break elseif feval('fun',b)=0; d