第5章-非线性方程的数值解法课件

第5章非线性方程的数值解法5.1问题背景——人口增长问题设N(t)表示t时刻人口数量，而λ表示人口固定出生率，那么人口满足下列微分方程：(5.1－1)上述方程的解为：(5.1－2)其中N0表示初始人口数量。(5.1－2)式表示的人口指数模型只有当人口是封闭没有迁移时是有效的。如果允许以固定速率迁移，那么微分方程应改为：(5.1－3)第5章非线性方程的数值解法5.1问题背景——人口增长问题1该微分方程的解为：(5.1－4)假设最初人口为1000万，即N0=1000万，第一年有435万人迁入，而在当年末时人口为1564万人，为了确定人口出生率λ，我们必须要求解下面关于λ的方程：(5.1－5)则式（5.1－5）改为：该微分方程的解为：(5.1－4)假设最初人口为1002如图5.1－1所示。方程（5.1－5）表明要求解当年的出生率λ0，使满足很显然，方程(5.1－4)是非线性方程，其解析解求解困难，只能求其近似解。本章讨论的数值计算方法就是当精确解无法通过代数方法获得时用于求该类非线性方程的近似解。一般而言，讨论非线性问题的数值方法，与线性问题相比，无论从理论上还是计算方法上都要复杂的多。非线性方程（5.1－6）的解通常称为方程的根，或称之为函数f(x)的零点。如图5.1－1所示。方程（5.1－5）表明要求解3代数方程如果f(x)是多项式，即则称方程（5.1－6）为代数方程。2.超越方程如果f(x)中含有三角函数，指数函数或其它超越函数，则称方程（5.1－6）为超越方程。例如：(5.1－7)(5.1－8)方程（5.1－7）是一个二次代数方程，它的两个根可以表示为有限形式，即方程（5.1－8）是一个超越方程，一般而言，必须用数值方法求它的解。方程的根可能是实数，也可能是复数，相应的称之为实根和复根。代数方程如果f(x)是多项式，即则称方程（5.1－6）为代43.单根如果对于xk有则称xk为方程f(x)=0的单根。4.重根如果有则称xk为f(x)=0的m+1次重根。对于代数方程，由代数学基本定理可知（实根或复根）的个数与其次数相同，但对于超越方程却复杂的多，如果有解，其解可能有一个或几个，也可能有无穷多个。在大多数情况下，对于高于四次的代数方程及超越方程没有精确的求根公式。其实，在实际应用中并非一定要得到精确的根，只要得到满足一定精度要求的根的近似值就可以了，就象导弹击中飞机一样，击中飞机的各个部位都可以，并非一定要击中飞机的发动机。

下面将介绍几种求解一般非线性方程的常用数值计算方法。3.单根如果对于xk有则称xk为方程f(x)=0的单根。455.2二分法（thebisectionmethod）设f(x)在区间[a,b]上连续，且f(a)f(b)<0，那么根据连续函数的零点定理，方程f(x)=0在(a,b)内至少有一个实根。为简便起见，不妨设f(x)=0在(a,b)内只有一个实根p。二分法基本思想用二分法求实根p的近似值的基本思路就是：逐步将包含有根p的区间二分，通过判断函数值的符号，逐步对半缩小有根区间，直到区间缩小到容许误差范围之内，然后取区间的中点为根p的近似值。具体方法如下：为讨论方便，不妨设如图5.2－1所示。5.2二分法（thebisectionmethod）6Step1:

区间[a,b]的中点，再计算函数值如果正好则表示待求的根就是否则判断Step2:

（即取原来区间的左半部分）；（即取原来区间的右半部）；这样二分的区间[a2,b2]是方程新的有根区间，它被包含在旧的有根区间[a1,b1]即[a,b]之内，而且其长度仅是[a1,b1]的一半。对缩小了的区间[a2,b2]再计算其中点Step3:

（即取区间[a2,b2]的左半部）；这样就把有根p的区间缩小到更小的范围[a3，b3]，再计算其中点的二分以后求得的有根p区间[ak,bk]的中点为如此反复重复上述的计算过程，经过k次这样Step1:区间[a,b]的中点，再计算函数值如果正好7而且（5.2－1）很显然，如果无限二分下去，则有因而零点p（根）为（5.2－2）但在实际计算时，不可能也完全没有必要进行这样的无限计算过程，只要有根区间的长度满足要求的精度即可停止计算，即满足：（5.2－3）则pk就是方程f(x)=0的一个满足给定精度的近似根了。其中ε是预先给定的一个任意小正实数，如10-6，或者满足（5.2－4）则表示pk是方程f(x)=0的一个满足给定精度要求的近似根。而且（5.2－1）很显然，如果无限二分下去，则有因而零点82.二分法算法的源程序（bisection.m）

clear；formatlonga=input(‘a=?’)；b=input(‘b=?’)；tol=input(‘tol=?’)；N=input(‘N=?’)；n=1；fa=f(a)；flag=0；while(n<=N)p=(a+b)./2；fp=f(p)；if(fp==0|(b-a)./2<tol)flag=1；breakendn=n+1；if(fa.*fp>0)a=p；fa=fp；

elseb=pendendif(flag==1)‘P=’，Pelse‘MethodfailedafterNiterations，N=’，Nend2.二分法算法的源程序（bisection.m）clear9说明：程序中函数f(x)应预先自定义，并取函数名存盘。以方程为例，自定义一个名cubicf.m的函数，源程序如下：functiony=cubicf(x)y=x.^3-2*x-5经过上述函数定义以后，将bisection.m源程序中的f(a)改为cubicf(a)，f(p)改为cubicf(p)，那么就可运行bisection.m程序计算方程的根了。3.总结二分法的优点是方法简单，编程容易，且对函数性质要求不高，仅仅要求它连续且在区间两端点的函数值异号即可。其收敛速度与公比为1/2的等比数列相同。但是，二分法只能用于求实函数的实根，不能用于求复根及偶数重根。说明：程序中函数f(x)应预先自定义，并取函数名存盘。以方10例5.1用二分法计算方程（5.1－5）中的人口出生率λ。解：经编程计算，人口出生率为λ＝0.10099887847900。源程序如下(ex51.m)：clear;formatlonga=0;b=1;tol=input('tol=?');N=input('N=?');n=1;fa=popu(a);flag=0;while(n<=N)p=(a+b)./2;fp=popu(p);if(fp==0|(b-a)./2<tol)flag=1;breakendn=n+1;

if(fa.*fp>0)a=p;fa=fp;elseb=p;endif(flag==1)'P=',pelse'MethodfailedafterNiterations,N=',Nendend例5.1用二分法计算方程（5.1－5）中的人口出生率λ。11其中使用的自定义函数（popu.m）为：functiony=popu(x)ifx==0y=-129;elsey=1000*exp(x)+435*(exp(x)-1)./x-1564;end其中使用的自定义函数（popu.m）为：functiony125.3迭代法迭代法是数值计算中的一类重要方法，是求解方程或方程组的一类基本方法。在科学计算和工程实际中经常使用，特别是随着计算机的普遍使用，使迭代法的应用更加广泛。迭代法的基本思路迭代法是一种逐次逼近的方法，其基本思想是使用某个固定公式反复校正根的近似值，从而得到一个近似根序列{xk}，使得该序列的极限就是方程f(x)=0的根。(1)对于非线性方程f(x)=0，用迭代法求根的具体方法是：先将方程改写为便于迭代的等价形式：（5.3－1）式中称为迭代函数。由于（5.3－1）式是隐式方程，其右端含有未知的x，因而不能直接求解，但如果用根的某个猜测值x0代入式（5.3－1）的右端，即可将它转化为显式的计算公式：5.3迭代法迭代法是数值计算中的一类重要方法，是求解13若再取x1作为新的猜测值，又有如此反复计算，其计算公式为（5.3－2）（5.3－2）式被称为迭代公式。如果迭代值xk有限，则称迭代收敛，这时极限值显然就是方程(5.3－1)亦即原方程f(x)=0的根。将方程f(x)=0等价转化为隐式方程，其实质就是求y=x

的交点p，即如果p是f(x)=0的根，即f(p)=0，那么有据此有（5.3－3）（5.3－3）就是根据f(x)构造的依据，从而得到（5.3－1）的等价迭代形式。如果p是y=x

的交点p，那末，p一定是方程f(x)=0的根，反之亦然。由此可知，迭代公式（5.3－2）也称定点迭代公式。若再取x1作为新的猜测值，又有如此反复计算，其计算公式为（5142.线性迭代函数的启示为了使迭代有效，必须保证它的收敛性。一个发散（即不收敛）的迭代过程，即使进行千百次迭代，其结果也毫无可用价值。为了保证迭代过程的收敛性，迭代函数的构造十分关键。以最简单的线性迭代函数为例可以容易验证的迭代才是收敛的，即是保证迭代收敛的线性迭代函数的基本特性（由作图法很容易验证这一特性）。3.压缩映像原理对于迭代函数的一般情形，设p为方程的根，则由微分中值定理有式中是p与xk之间的某一点，即由此可知，如果存在，使得对于任意成立：2.线性迭代函数的启示为了使迭代有效，必须保证它的收15则有（5.3－4）如此反复递推，对迭代误差即迭代收敛。需要指出的是，在上述论证过程中，应当保证一切迭代值xk全落在区间[a,b]内，为此要求对任意综上所述有如下压缩映像原理：定理5.1设在[a,b]上具有连续的一阶导数，且满足以下两个条件：使得对于任意成立（5.3－5）则有（5.3－4）如此反复递推，对迭代误差即迭代收敛。16则迭代过程对任意初值均收敛于方程的根p，且有下列误差公式：（5.3－6）（5.3－7）则迭代过程对任意初值均收敛于方程的根p，且有下列误差公17n=n+1；p0=p；%更新p0endifflag==1‘p=’，p%Theprocedurewassuccessful.else‘ThemethodfailedafterNiterationsN=’，Nend4.定点迭代法源程序（fixedp.m）clear；formatlongp0=input(‘p0=?’)；Tol=input(‘toleranceTol=?’)；N=input(‘maximumnumberofiterationsN=?’)；n=1；flag=0；Whilen<=Np=f(P0)；ifabs(p-p0)<tolflag=1；break；endn=n+1；4.定点迭代法源程序（fixedp.m）clea18例5.2求方程的唯一正根。解：因为f(1)=-1，f(2)=5，所以区间[1,2]含有所求的根。为使用迭代，将所给方程改写为：这时迭代函数在[1,2]上恒有，由定理5.1可知，迭代公式对任意初始值均收敛。取初值x0=1.5，迭代结果如表5.1所示。表5.1迭代结果k012345678xk1.51.357211.330861.325881.324941.324761.324731.324721.32472例5.2求方程的唯一正根。解：因为f(1)=-1，19例5.3用迭代法求解方程的根（已知方程的一个根为解：把方程改写为下列三种等价的迭代形式：对于（1）：

所以用作迭代函数时，无法收敛。对于（2）：

所以用作迭代函数也无法收敛。对于（3）：

所以可用其作迭代函数。以x0=3为初值，迭代结果如下：例5.3用迭代法求解方程的根（已知方程的一个根为解：把方程20经过2次迭代即可达到3位有效数字精度。若将f(x)=0改为所以用为迭代函数时也收敛，结果如下：由以上计算结果可知，两种迭代函数都可收敛，但收敛速度却不相同，前者很快收敛，而后者却收敛较慢，因此，构造出合适的迭代函数十分重要。5.迭代过程的收敛速度一种迭代法要具有实用价值，不仅需要肯定它是收敛的，而且还要求它收敛快。所谓收敛速度是指在接近收敛时迭代误差的下降速度。具体而言就是，如果迭代误差时成立：则称迭代过程是p阶收敛的。当p=1时称线性收敛；p=2时称平方收敛经过2次迭代即可达到3位有效数字精度。若将f(x)=0改为21定理5.2设的根p邻近有连续的二阶导数，且时迭代过程为线性收敛；而当时为平方收敛。定理5.2设的根p邻近有连续的二阶导数，且时迭代过程225.4迭代过程的加速收敛方法迭代公式的加工对于收敛的迭代过程，只要迭代足够多次，就可以使迭代结果达到任意精度，但有时迭代过程收敛较慢，从而大大增加了计算量，因此，迭代过程的加速是个重要的研究课题。设xk是根p的某个近似值，用迭代公式校正一次得在所考虑的范围内变化不大，其估值为L，则由微分中值定理有(5.4－1)从而得这表明，如果将迭代值与xk加权平均，可望所得到的5.4迭代过程的加速收敛方法迭代公式的加工对于收敛的23是比更好的近似根。其加速计算过程是：迭代：加工：它们合并为：(5.4－2)例5.4用迭代法和加速迭代法求方程附近的一个根p，要求精度为10-5。解：设迭代函数为所以迭代方程是收敛的。(1)使用非加速迭代时，经过18次迭代即得到满足精度要求的根0.567141（准确值为0.56713）是比更好的近似根。其加速计算过程是：迭代：加工：24结果如表5.2所示。k01234567xk0.5000000.6065310.5452390.5797030.5600650.5711720.5648630.568438k89101112131415xk0.5664090.5675600.5669070.5672770.5670670.5671860.5671190.567157k161718xk0.5671350.5671480.567141(2)使用加速迭代公式(5.4－2)时，故取L=-0.6，此时加速迭代公式为：计算结果如下：即只要迭代3次即可得到满足精度要求的结果，显然加速的效果显著的。结果如表5.2所示。k01234567xk0.5000000252.埃特金算法上述加速方案的缺点是，由于其中含有导数的有关信息而不便于实际应用。同样假定在所考虑的范围内变化不大，其估值为L，将迭代值再迭代一次，即得到由微分中值定理得利用式(5.4－1)：联立消去L得从而得若以上式右端得出的结果作为新的改进值，那末这样构造出的加速公式不再含有关于导数的信息2.埃特金算法上述加速方案的缺点是，由于其中含26但是，它需要两次迭代值进行加工，具体算法如下：迭代：再迭代：加工：(5.4－3)上述方法称之为埃特金（Aitken）加速方法。3.埃特金加速算法的源程序(aitken.m)clear；formatlongx0=input(‘x0=?’)；N=input(‘N=?’)；Tol=input(‘Tol=?’)；n=1；flag=0；Whilen<=Nx1=φ(x0)；x2=φ(x1)；x2=x2－(x2－x1).^2./(x2-2*x1+x0)；ifabs(x2-x0)<Tolflag=1；breakendn=n+1；x0=x2；endifflag==1‘x2=’,x,’Theprocedurewassuccessful’else‘ThemethodfailedafterNiterations,N=’,Nend但是，它需要两次迭代值进行加工，具体算法如下：迭代：再275.5牛顿迭代法牛顿迭代法是求解非线性方程f(x)=0的一种重要和常用的迭代方法，其基本思想是将非线性函数f(x)=0逐步线性化，从而将非线性方程f(x)=0近似地转化为线性方程的求解。牛顿迭代公式的导出对于方程f(x)=0设已知它的近似根为xk，则函数f(x)=0在点xk处作泰勒展开：取其前两项近似代替f(x)（称为f(x)的线性化），即用线性方程(5.5－1)来近似方程f(x)=0。很显然，方程(5.5－1)是线性方程，它的求根是很容易的。5.5牛顿迭代法牛顿迭代法是求解非线性方程f28则用线性方程(5.5－1)的根作为非线性方程f(x)=0的新近似根，记为xk+1，则有牛顿迭代公式：(5.5－2)这就是著名的牛顿迭代公式，相应的迭代函数是：(5.5－3)如果p是方程f(x)=0的一个单根，即f(p)=0，由此可见，在单根p的附近，对于任意的初值x0，由收敛性定理5.1可知，由迭代公式(5.5－2)得到的迭代序列都收敛于根p，而且收敛的速度很快（由定理5.2知）。则用线性方程(5.5－1)的根作为非线性方程f(x)=0的29牛顿法有明显的几何意义。方程f(x)=0的根p在几何上表示曲线y=f(x)与x轴的交点p。当求得p的近似值xk以后，过曲线y=f(x)上的对应点(xk

，f(xk))作f(x)的切线，其切线方程为：则该切线与x轴的交点横坐标正好是这就是牛顿迭代公式(5.5－2)的计算结果xk+1。继续取点(xk+1

，f(xk+1))，再作曲线y=f(x)的切线与x轴相交，又可得xk+2，…，由图5.5－1可知，只要初值x取得充分靠近根p，序列{xk}就会很快收敛于p。正因为牛顿法有这一明显的几何意义，所以牛顿法也常称之为切线法。牛顿法有明显的几何意义。方程f(x)=0的根p302.牛顿法的收敛性对于方程f(x)=0，如果f(x)在根p邻近具有连续的二阶导数，且p是f(x)=0的一个单根，则在跟p的附近，对于任意的初始值x0，由牛顿迭代法产生的序列{xk}收敛于p，所以牛顿法具有局部收敛性，并且可进一步证明牛顿迭代法在单根p附近是平方收敛的，即具有二阶收敛速度。但是，如果p是f(x)=0的重根时，则可证明牛顿法仅有线性收敛速度，且重数越高收敛越慢。牛顿迭代法对初值x0的选取要求比较高，即x0必须充分靠近p才能保证局部收敛。为了保证牛顿法具有非局部收敛性，下面不加证明地给出一个判断牛顿非局部收敛的充分定理：2.牛顿法的收敛性对于方程f(x)=0，如果f31定理5.3设函数f(x)在区间[a，b]上存在二阶导数，且满足下列条件：在[a，b]上不为零；在[a，b]上不变号；(4)在[a，b]上任意选取满足条件的初始近似值x0。则有牛顿法产生的序列{xk}单调收敛于方程f(x)=0在[a,b]上的唯一根3牛顿迭代法源程序（newtoniter.m）clear；formatlongx0=input(‘x0=?’)；N=input(‘N=?’)；TOL=input(‘TOL=?’)；k=1；flag=0；Whilen<=Nfdot=f’(x0)；定理5.3设函数f(x)在区间[a，b]上存在二阶导数，32iffdot==0flag=0；breakendx1=x0－f(x0)./fdot；ifabs(x1－x0)<tolflag=1；breakendifn==Nflag=2；breakendn=n+1；x0=x1；endifflag==0‘Thisequationhasnosolution’；elseifflag==1‘p=’，x1else‘ThismethodfailedafterNiterations,N=’，Nendiffdot==0ifflag==033例5.5用牛顿法求解非线性方程解：牛顿迭代公式为：所以方程在[0，1]内有解。取初始值x=0.5，计算结果如下：与例5.4相比可知，牛顿迭代法的收敛速度与加速迭代法一样快。例5.5用牛顿法求解非线性方程解：牛顿迭代公式为：所以34例5.6用牛顿迭代法（5.5－2）式计算的近似值。解的精确值为2.4494897。则方程的解就是的近似值。所以方程在[2，3]内有解。牛顿迭代公式如下：取初值x0=2.5，计算结果如下：例5.6用牛顿迭代法（5.5－2）式计算的近似值。35由牛顿法的收敛性定理5.3可知，牛顿法对初始值的选取要求是很高的。一般而言，牛顿法只有局部收敛性。当初始值取得离根p太远时，迭代将发散，而一旦xk进入收敛域内，牛顿法就有平方收敛的速度。为了扬长避短，扩大初始值x0的选择范围，下面介绍牛顿法的一种改进方法—牛顿下山法。4.牛顿下山法将牛顿迭代公式（5.5－2）修改为：（5.5－4）其中，λ是一个参数，且称为下山因子。适当选取下山因子可以使单调性条件（5.5－5）成立。由牛顿法的收敛性定理5.3可知，牛顿法对初始值的36下山因子λ的选择是个逐步探索的过程，从λ=1开始反复将因子λ的值减半进行计算，一旦单调性条件（5.5－5）成立，则称“下山成功”；否则，如果在上述过程中找不到使条件（5.5－5）成立的下山因子λ，则称“下山失败”，这时需要另选初值x0重新计算。例5.7已知非线性方程的一个根为p=1.32472。若取初值x0

=0.6，用牛顿法计算得到的第一次近似值为x1=17.9，反而比x0=0.6更偏离了根p。若改用牛顿下山法：计算，仍取x0

=0.6，从λ=1开始逐次搜索，当搜索到下山因子由牛顿下山公式（5.5－4）得到的计算值下山因子λ的选择是个逐步探索的过程，从λ=1开始37已满足条件（5.5－5），即因而牛顿下山法修正了原来x1=17.9的严重偏差，使迭代收敛。计算结果如表5.3所示：k01234λ11/32111xk0.61.140631.366811.326281.32472由例5.7的分析可以知道，如果初值x0的选取偏离根p太远，从而使迭代计算的值x1偏离根p更远，那末就可采用牛顿下山法，逐次将下山因子减半，重新计算x1的值，即已满足条件（5.5－5），即因而牛顿下山法修正了原来x1=38并判断单调性条件是否成立。若条件仍不成立，再将λ减半，重新计算x1，直到单调性条件成立为止，这样即可将第一次迭代计算的值x1出现的偏差得到修正，使之进入根p的收敛区域之内，以后的迭代过程，下山因子λ恒定为1。并判断单调性条件是否成立。若条件仍不成立，再将λ减半，重395.6弦截法牛顿法的突出优点是收敛速度快，但也有明显的缺点，这就是需要提供导数值f’(xk)。如果函数f(x)=0比较复杂，致使导数的计算困难，那末用牛顿法公式是很不方便的。1.为了避开导数的计算，可以改用差商来代替牛顿公式（5.5－2）中的导数，从而得到下列的离散形式：（5.6－1）这个公式是根据f(x)=0的等价形式：（5.6－2）5.6弦截法牛顿法的突出优点是收敛速度快，但也有明显40建立的迭代公式，迭代函数为：（5.6－3）迭代公式（5.6－1）的几何解释如图5.6－1所示，曲线y=f(x)上横坐标为xk的点记为pk，则差商表示弦线的斜率，由公式（5.6－1）计算得到的xk+1，实际上就是弦线与x轴的交点，因而这种方法称为弦截法。图5.6－1弦截法示意图建立的迭代公式，迭代函数为：（5.6－3）迭代公式（5.6412.弦截法的收敛性为提高收敛速度，改用差商（5.5－2）中的导数f’(xk)，从而导出下列的迭代公式：来代替牛顿公式（5.6－4）这种迭代法称为快速弦截法

快速弦截法也称两步法，这是因为在计算xk+1时，要用到前面两步的信息xk-1和xk，因此在使用快速弦截法时，在计算之前必须预先提供两初始值x0和x1。2.弦截法的收敛性为提高收敛速度，改用差商（5.5－2）中42例5.8用快速弦截法求解非线性方程解：所以方程取初值用快速弦截法求得的结果如下：很显然，快速弦截法的收敛速度是很快的，与牛顿下山法(例5.7)和加速迭代法（例5.4）的收敛速度相当。例5.9编程计算下列方程（见（5.1－1）式）的根λ。解：因为所以方程f(x)=0在[0，1]内有解。例5.8用快速弦截法求解非线性方程解：所以方程取初值43采用快速弦截法计算，程序如下：(1)f(λ)函数定义（population2.m）functiony=popu(x)n=length(x)；forj=1:n

ifx(j)==0y(j)=-129；

elsey(j)=1000*exp(x(j))+435*(exp(x(j))-1)./x(j)-1564；

endend采用快速弦截法计算，程序如下：(1)f(λ)函数定义（p44（2）求方程f(λ)=0的解的源程序（secant.m）clear；formatlongx0=input('x0=?')；x1=input('x1=?')；N=input('N=?')；Tol=input('Tol=?')；n=2;flag=0；y0=population2(x0)；y1=population2(x1)；whilen<=Nx=x1-y1.*(x1-x0)./(y1-y0)；ifabs(x-x1)<Tolflag=1；breakend

n=n+1；x0=x1；x1=x；y0=y1；y1=population2(x1)；endifflag==0'ThemethodfailedafterNiterations，N='，Nelse'x='，xend取初值精度Tol＝10-6时，经六次迭代计算，计算结果为：λ＝0.1009979。（2）求方程f(λ)=0的解的源程序（secant.m45第5章非线性方程的数值解法5.1问题背景——人口增长问题设N(t)表示t时刻人口数量，而λ表示人口固定出生率，那么人口满足下列微分方程：(5.1－1)上述方程的解为：(5.1－2)其中N0表示初始人口数量。(5.1－2)式表示的人口指数模型只有当人口是封闭没有迁移时是有效的。如果允许以固定速率迁移，那么微分方程应改为：(5.1－3)第5章非线性方程的数值解法5.1问题背景——人口增长问题46该微分方程的解为：(5.1－4)假设最初人口为1000万，即N0=1000万，第一年有435万人迁入，而在当年末时人口为1564万人，为了确定人口出生率λ，我们必须要求解下面关于λ的方程：(5.1－5)则式（5.1－5）改为：该微分方程的解为：(5.1－4)假设最初人口为10047如图5.1－1所示。方程（5.1－5）表明要求解当年的出生率λ0，使满足很显然，方程(5.1－4)是非线性方程，其解析解求解困难，只能求其近似解。本章讨论的数值计算方法就是当精确解无法通过代数方法获得时用于求该类非线性方程的近似解。一般而言，讨论非线性问题的数值方法，与线性问题相比，无论从理论上还是计算方法上都要复杂的多。非线性方程（5.1－6）的解通常称为方程的根，或称之为函数f(x)的零点。如图5.1－1所示。方程（5.1－5）表明要求解48代数方程如果f(x)是多项式，即则称方程（5.1－6）为代数方程。2.超越方程如果f(x)中含有三角函数，指数函数或其它超越函数，则称方程（5.1－6）为超越方程。例如：(5.1－7)(5.1－8)方程（5.1－7）是一个二次代数方程，它的两个根可以表示为有限形式，即方程（5.1－8）是一个超越方程，一般而言，必须用数值方法求它的解。方程的根可能是实数，也可能是复数，相应的称之为实根和复根。代数方程如果f(x)是多项式，即则称方程（5.1－6）为代493.单根如果对于xk有则称xk为方程f(x)=0的单根。4.重根如果有则称xk为f(x)=0的m+1次重根。对于代数方程，由代数学基本定理可知（实根或复根）的个数与其次数相同，但对于超越方程却复杂的多，如果有解，其解可能有一个或几个，也可能有无穷多个。在大多数情况下，对于高于四次的代数方程及超越方程没有精确的求根公式。其实，在实际应用中并非一定要得到精确的根，只要得到满足一定精度要求的根的近似值就可以了，就象导弹击中飞机一样，击中飞机的各个部位都可以，并非一定要击中飞机的发动机。

下面将介绍几种求解一般非线性方程的常用数值计算方法。3.单根如果对于xk有则称xk为方程f(x)=0的单根。4505.2二分法（thebisectionmethod）设f(x)在区间[a,b]上连续，且f(a)f(b)<0，那么根据连续函数的零点定理，方程f(x)=0在(a,b)内至少有一个实根。为简便起见，不妨设f(x)=0在(a,b)内只有一个实根p。二分法基本思想用二分法求实根p的近似值的基本思路就是：逐步将包含有根p的区间二分，通过判断函数值的符号，逐步对半缩小有根区间，直到区间缩小到容许误差范围之内，然后取区间的中点为根p的近似值。具体方法如下：为讨论方便，不妨设如图5.2－1所示。5.2二分法（thebisectionmethod）51Step1:

区间[a,b]的中点，再计算函数值如果正好则表示待求的根就是否则判断Step2:

（即取原来区间的左半部分）；（即取原来区间的右半部）；这样二分的区间[a2,b2]是方程新的有根区间，它被包含在旧的有根区间[a1,b1]即[a,b]之内，而且其长度仅是[a1,b1]的一半。对缩小了的区间[a2,b2]再计算其中点Step3:

（即取区间[a2,b2]的左半部）；这样就把有根p的区间缩小到更小的范围[a3，b3]，再计算其中点的二分以后求得的有根p区间[ak,bk]的中点为如此反复重复上述的计算过程，经过k次这样Step1:区间[a,b]的中点，再计算函数值如果正好52而且（5.2－1）很显然，如果无限二分下去，则有因而零点p（根）为（5.2－2）但在实际计算时，不可能也完全没有必要进行这样的无限计算过程，只要有根区间的长度满足要求的精度即可停止计算，即满足：（5.2－3）则pk就是方程f(x)=0的一个满足给定精度的近似根了。其中ε是预先给定的一个任意小正实数，如10-6，或者满足（5.2－4）则表示pk是方程f(x)=0的一个满足给定精度要求的近似根。而且（5.2－1）很显然，如果无限二分下去，则有因而零点532.二分法算法的源程序（bisection.m）

clear；formatlonga=input(‘a=?’)；b=input(‘b=?’)；tol=input(‘tol=?’)；N=input(‘N=?’)；n=1；fa=f(a)；flag=0；while(n<=N)p=(a+b)./2；fp=f(p)；if(fp==0|(b-a)./2<tol)flag=1；breakendn=n+1；if(fa.*fp>0)a=p；fa=fp；

elseb=pendendif(flag==1)‘P=’，Pelse‘MethodfailedafterNiterations，N=’，Nend2.二分法算法的源程序（bisection.m）clear54说明：程序中函数f(x)应预先自定义，并取函数名存盘。以方程为例，自定义一个名cubicf.m的函数，源程序如下：functiony=cubicf(x)y=x.^3-2*x-5经过上述函数定义以后，将bisection.m源程序中的f(a)改为cubicf(a)，f(p)改为cubicf(p)，那么就可运行bisection.m程序计算方程的根了。3.总结二分法的优点是方法简单，编程容易，且对函数性质要求不高，仅仅要求它连续且在区间两端点的函数值异号即可。其收敛速度与公比为1/2的等比数列相同。但是，二分法只能用于求实函数的实根，不能用于求复根及偶数重根。说明：程序中函数f(x)应预先自定义，并取函数名存盘。以方55例5.1用二分法计算方程（5.1－5）中的人口出生率λ。解：经编程计算，人口出生率为λ＝0.10099887847900。源程序如下(ex51.m)：clear;formatlonga=0;b=1;tol=input('tol=?');N=input('N=?');n=1;fa=popu(a);flag=0;while(n<=N)p=(a+b)./2;fp=popu(p);if(fp==0|(b-a)./2<tol)flag=1;breakendn=n+1;

if(fa.*fp>0)a=p;fa=fp;elseb=p;endif(flag==1)'P=',pelse'MethodfailedafterNiterations,N=',Nendend例5.1用二分法计算方程（5.1－5）中的人口出生率λ。56其中使用的自定义函数（popu.m）为：functiony=popu(x)ifx==0y=-129;elsey=1000*exp(x)+435*(exp(x)-1)./x-1564;end其中使用的自定义函数（popu.m）为：functiony575.3迭代法迭代法是数值计算中的一类重要方法，是求解方程或方程组的一类基本方法。在科学计算和工程实际中经常使用，特别是随着计算机的普遍使用，使迭代法的应用更加广泛。迭代法的基本思路迭代法是一种逐次逼近的方法，其基本思想是使用某个固定公式反复校正根的近似值，从而得到一个近似根序列{xk}，使得该序列的极限就是方程f(x)=0的根。(1)对于非线性方程f(x)=0，用迭代法求根的具体方法是：先将方程改写为便于迭代的等价形式：（5.3－1）式中称为迭代函数。由于（5.3－1）式是隐式方程，其右端含有未知的x，因而不能直接求解，但如果用根的某个猜测值x0代入式（5.3－1）的右端，即可将它转化为显式的计算公式：5.3迭代法迭代法是数值计算中的一类重要方法，是求解58若再取x1作为新的猜测值，又有如此反复计算，其计算公式为（5.3－2）（5.3－2）式被称为迭代公式。如果迭代值xk有限，则称迭代收敛，这时极限值显然就是方程(5.3－1)亦即原方程f(x)=0的根。将方程f(x)=0等价转化为隐式方程，其实质就是求y=x

的交点p，即如果p是f(x)=0的根，即f(p)=0，那么有据此有（5.3－3）（5.3－3）就是根据f(x)构造的依据，从而得到（5.3－1）的等价迭代形式。如果p是y=x

的交点p，那末，p一定是方程f(x)=0的根，反之亦然。由此可知，迭代公式（5.3－2）也称定点迭代公式。若再取x1作为新的猜测值，又有如此反复计算，其计算公式为（5592.线性迭代函数的启示为了使迭代有效，必须保证它的收敛性。一个发散（即不收敛）的迭代过程，即使进行千百次迭代，其结果也毫无可用价值。为了保证迭代过程的收敛性，迭代函数的构造十分关键。以最简单的线性迭代函数为例可以容易验证的迭代才是收敛的，即是保证迭代收敛的线性迭代函数的基本特性（由作图法很容易验证这一特性）。3.压缩映像原理对于迭代函数的一般情形，设p为方程的根，则由微分中值定理有式中是p与xk之间的某一点，即由此可知，如果存在，使得对于任意成立：2.线性迭代函数的启示为了使迭代有效，必须保证它的收60则有（5.3－4）如此反复递推，对迭代误差即迭代收敛。需要指出的是，在上述论证过程中，应当保证一切迭代值xk全落在区间[a,b]内，为此要求对任意综上所述有如下压缩映像原理：定理5.1设在[a,b]上具有连续的一阶导数，且满足以下两个条件：使得对于任意成立（5.3－5）则有（5.3－4）如此反复递推，对迭代误差即迭代收敛。61则迭代过程对任意初值均收敛于方程的根p，且有下列误差公式：（5.3－6）（5.3－7）则迭代过程对任意初值均收敛于方程的根p，且有下列误差公62n=n+1；p0=p；%更新p0endifflag==1‘p=’，p%Theprocedurewassuccessful.else‘ThemethodfailedafterNiterationsN=’，Nend4.定点迭代法源程序（fixedp.m）clear；formatlongp0=input(‘p0=?’)；Tol=input(‘toleranceTol=?’)；N=input(‘maximumnumberofiterationsN=?’)；n=1；flag=0；Whilen<=Np=f(P0)；ifabs(p-p0)<tolflag=1；break；endn=n+1；4.定点迭代法源程序（fixedp.m）clea63例5.2求方程的唯一正根。解：因为f(1)=-1，f(2)=5，所以区间[1,2]含有所求的根。为使用迭代，将所给方程改写为：这时迭代函数在[1,2]上恒有，由定理5.1可知，迭代公式对任意初始值均收敛。取初值x0=1.5，迭代结果如表5.1所示。表5.1迭代结果k012345678xk1.51.357211.330861.325881.324941.324761.324731.324721.32472例5.2求方程的唯一正根。解：因为f(1)=-1，64例5.3用迭代法求解方程的根（已知方程的一个根为解：把方程改写为下列三种等价的迭代形式：对于（1）：

所以用作迭代函数时，无法收敛。对于（2）：

所以用作迭代函数也无法收敛。对于（3）：

所以可用其作迭代函数。以x0=3为初值，迭代结果如下：例5.3用迭代法求解方程的根（已知方程的一个根为解：把方程65经过2次迭代即可达到3位有效数字精度。若将f(x)=0改为所以用为迭代函数时也收敛，结果如下：由以上计算结果可知，两种迭代函数都可收敛，但收敛速度却不相同，前者很快收敛，而后者却收敛较慢，因此，构造出合适的迭代函数十分重要。5.迭代过程的收敛速度一种迭代法要具有实用价值，不仅需要肯定它是收敛的，而且还要求它收敛快。所谓收敛速度是指在接近收敛时迭代误差的下降速度。具体而言就是，如果迭代误差时成立：则称迭代过程是p阶收敛的。当p=1时称线性收敛；p=2时称平方收敛经过2次迭代即可达到3位有效数字精度。若将f(x)=0改为66定理5.2设的根p邻近有连续的二阶导数，且时迭代过程为线性收敛；而当时为平方收敛。定理5.2设的根p邻近有连续的二阶导数，且时迭代过程675.4迭代过程的加速收敛方法迭代公式的加工对于收敛的迭代过程，只要迭代足够多次，就可以使迭代结果达到任意精度，但有时迭代过程收敛较慢，从而大大增加了计算量，因此，迭代过程的加速是个重要的研究课题。设xk是根p的某个近似值，用迭代公式校正一次得在所考虑的范围内变化不大，其估值为L，则由微分中值定理有(5.4－1)从而得这表明，如果将迭代值与xk加权平均，可望所得到的5.4迭代过程的加速收敛方法迭代公式的加工对于收敛的68是比更好的近似根。其加速计算过程是：迭代：加工：它们合并为：(5.4－2)例5.4用迭代法和加速迭代法求方程附近的一个根p，要求精度为10-5。解：设迭代函数为所以迭代方程是收敛的。(1)使用非加速迭代时，经过18次迭代即得到满足精度要求的根0.567141（准确值为0.56713）是比更好的近似根。其加速计算过程是：迭代：加工：69结果如表5.2所示。k01234567xk0.5000000.6065310.5452390.5797030.5600650.5711720.5648630.568438k89101112131415xk0.5664090.5675600.5669070.5672770.5670670.5671860.5671190.567157k161718xk0.5671350.5671480.567141(2)使用加速迭代公式(5.4－2)时，故取L=-0.6，此时加速迭代公式为：计算结果如下：即只要迭代3次即可得到满足精度要求的结果，显然加速的效果显著的。结果如表5.2所示。k01234567xk0.5000000702.埃特金算法上述加速方案的缺点是，由于其中含有导数的有关信息而不便于实际应用。同样假定在所考虑的范围内变化不大，其估值为L，将迭代值再迭代一次，即得到由微分中值定理得利用式(5.4－1)：联立消去L得从而得若以上式右端得出的结果作为新的改进值，那末这样构造出的加速公式不再含有关于导数的信息2.埃特金算法上述加速方案的缺点是，由于其中含71但是，它需要两次迭代值进行加工，具体算法如下：迭代：再迭代：加工：(5.4－3)上述方法称之为埃特金（Aitken）加速方法。3.埃特金加速算法的源程序(aitken.m)clear；formatlongx0=input(‘x0=?’)；N=input(‘N=?’)；Tol=input(‘Tol=?’)；n=1；flag=0；Whilen<=Nx1=φ(x0)；x2=φ(x1)；x2=x2－(x2－x1).^2./(x2-2*x1+x0)；ifabs(x2-x0)<Tolflag=1；breakendn=n+1；x0=x2；endifflag==1‘x2=’,x,’Theprocedurewassuccessful’else‘ThemethodfailedafterNiterations,N=’,Nend但是，它需要两次迭代值进行加工，具体算法如下：迭代：再725.5牛顿迭代法牛顿迭代法是求解非线性方程f(x)=0的一种重要和常用的迭代方法，其基本思想是将非线性函数f(x)=0逐步线性化，从而将非线性方程f(x)=0近似地转化为线性方程的求解。牛顿迭代公式的导出对于方程f(x)=0设已知它的近似根为xk，则函数f(x)=0在点xk处作泰勒展开：取其前两项近似代替f(x)（称为f(x)的线性化），即用线性方程(5.5－1)来近似方程f(x)=0。很显然，方程(5.5－1)是线性方程，它的求根是很容易的。5.5牛顿迭代法牛顿迭代法是求解非线性方程f73则用线性方程(5.5－1)的根作为非线性方程f(x)=0的新近似根，记为xk+1，则有牛顿迭代公式：(5.5－2)这就是著名的牛顿迭代公式，相应的迭代函数是：(5.5－3)如果p是方程f(x)=0的一个单根，即f(p)=0，由此可见，在单根p的附近，对于任意的初值x0，由收敛性定理5.1可知，由迭代公式(5.5－2)得到的迭代序列都收敛于根p，而且收敛的速度很快（由定理5.2知）。则用线性方程(5.5－1)的根作为非线性方程f(x)=0的74牛顿法有明显的几何意义。方程f(x)=0的根p在几何上表示曲线y=f(x)与x轴的交点p。当求得p的近似值xk以后，过曲线y=f(x)上的对应点(xk

，f(xk))作f(x)的切线，其切线方程为：则该切线与x轴的交点横坐标正好是这就是牛顿迭代公式(5.5－2)的计算结果xk+1。继续取点(xk+1

，f(xk+1))，再作曲线y=f(x)的切线与x轴相交，又可得xk+2，…，由图5.5－1可知，只要初值x取得充分靠近根p，序列{xk}就会很快收敛于p。正因为牛顿法有这一明显的几何意义，所以牛顿法也常称之为切线法。牛顿法有明显的几何意义。方程f(x)=0的根p752.牛顿法的收敛性对于方程f(x)=0，如果f(x)在根p邻近具有连续的二阶导数，且p是f(x)=0的一个单根，则在跟p的附近，对于任意的初始值x0，由牛顿迭代法产生的序列{xk}收敛于p，所以牛顿法具有局部收敛性，并且可进一步证明牛顿迭代法在单根p附近是平方收敛的，即具有二阶收敛速度。但是，如果p是f(x)=0的重根时，则可证明牛顿法仅有线性收敛速度，且重数越高收敛越慢。牛顿迭代法对初值x0的选取要求比较高，即x0必须充分靠近p才能保证局部收敛。为了保证牛顿法具有非局部收敛性，下面不加证明地给出一个判断牛顿非局部收敛的充分定理：2.牛顿法的收敛性对于方程f(x)=0，如果f76定理5.3设函数f(x)在区间[a，b]上存在二阶导数，且满足下列条件：在[a，b]上不为零；在[a，b]上不变号；(4)在[a，b]上任意选取满足条件的初始近似值x0。则有牛顿法产生的序列{xk}单调收敛于方程f(x)=0在[a,b]上的唯一根3牛顿迭代法源程序（newtoniter.m）clear；formatlongx0=input(‘x0=?’)；N=input(‘N=?’)；TOL=input(‘TOL=?’)；k=1；flag=0；Whilen<=Nfdot=f’(x0)；定理5.3设函数f(x)在区间[a，b]上存在二阶导数，77iffdot==0flag=0；breakendx1=x0－f(x0)./fdot；ifabs(x1－x0)<tolflag=1；breakendifn==Nflag=2；breakendn=n+1；x0=x1；endifflag==0‘Thisequationhasnosolution’；elseifflag==1‘p=’，x1else‘ThismethodfailedafterNiterations,N=’，Nendiffdot==0ifflag==078例5.5用牛顿法求解非线性方程解：牛顿迭代公式为：所以方程在[0，1]内有解。取初始值x=0.5，计算结果如下：与例5.4相比可知，牛顿迭代法的收敛速度与加速迭代法一样快。例5.5用牛顿法求解非线性方程解：牛顿迭代公式为：所以79例5.6用牛顿迭代法（5.5－2）式计算的近似值。解的精确值为2.4494897。则方程的解就是的近似值。所以方程在[2，3]内有解。牛顿迭代公式如下：取初值x0=2.5，计算结果如下：例5.6用牛顿迭代法（5.5－2）式计算的近似值。80由牛顿法的收敛性定理5.3可知，牛顿法对初始值的选取要求是很高的。一般而言，牛顿法只有局部收敛性。当初始值取得离根p太远时，迭代将发散，而一旦xk进入收敛域内，牛顿法就有平方收敛的速