《计算方法》课件第2章

第2章非线性方程求根2.1引言2.2二分法2.3迭代法2.4牛顿迭代法与弦割法 2.1引言

科学研究及生产实践中的许多问题常归结为求解非线性方程f(x)=0根的问题，对求解非线性方程的方法进行研究具有重要的实用价值。根据数学相关理论可知,方程通常分为代数方程和超越方程。代数方程即为多项式方程，如x3+4x2－10=0，而超越方程不仅要对未知数和一些常数施行有限次代数运算，而且还要施行有限次指数、对数、三角函数等运算，如e－x－sinx=0。对于代数方程的求解，理论上已经证明,当次数大于等于5时无精确的求根公式，而对于一般的超越方程更没有求根公式可以利用。在实际问题中，求方程的根时，不一定要得到根的准确值，而只需求得满足一定精度的近似值即可，因此本章将介绍求解非线性方程的近似根的方法，并只讨论近似根为实根的情况。求解方程的近似根包括两个步骤：第一步是求根的隔离区间，第二步是根的精确化。求根的隔离区间，即确定根所在的区间，使方程在这个小区间内有且只有一个根，这一过程称为根的隔离，而且所求根的隔离区间越小越好。根的精确化是在已知一个根的近似值后，用某种方法把此近似值精确化，使其满足给定的精度要求。下面介绍求根的隔离区间的描图法与逐步搜索法，而根的精确化将在以后各节中进行介绍。

(1)描图法获得根的隔离区间。根据方程f(x)=0，画出曲线y=f(x)的简图，观察曲线y=f(x)与x轴的交点的大致位置，从而确定根的隔离区间；或将方程等价变换为y1(x)=y2(x)，画出曲线y1(x)和y2(x)的简图，从两条曲线交点横坐标位置确定根的隔离区间。

例2－1用描图法求方程3x－1－cosx=0的根的隔离区间。

解将方程等价变换为3x－1=cosx

令y1(x)=3x－1，y2(x)=cosx，作出该两条曲线的图形如图2.1所示。从图中可以看出,y1(x)和y2(x)曲线交点的横坐标在［1/3，1］内，［1/3,1］即为所求方程根的隔离区间。图2.1

y1(x)=3x-1和y2(x)=cosx的图形(2)逐步搜索法获得根的隔离区间。根据连续函数的界值定理，设f(x)在区间［a，b］内连续，若f(a)和f(b)异号，则方程f(x)=0在［a，b］内至少有一个根。据此，先确定方程f(x)=0的所有实根所在的大致区间，设为［a，b］，再按照选定的步长h=(b-a)/n(n为正整数)，取点xk=a+kh(k=0，1，…，n)，逐次计算函数值f(xk)，依据函数值的异号及实根的个数即可确定根的隔离区间。

例2－2利用逐步搜索法确定方程x3－x－1=0的一个根的隔离区间。

解根据已知方程，令f(x)=x3－x－1则可得f(0)<0，f(2)>0，因此,在区间［0，2］之间至少有一个实根。取步长h=(2-0)/4=0.5，即n=4，则取点xk=a+kh(k=0，1，2，3，4)，逐次计算函数值f(xk)便可得其符号，见表2.1。表2.1例2－2的计算结果

根据表2.1的计算结果可知,方程在区间［1.0，1.5］内必有一实根，且在该区间内，f′(x)>0，表明方程x3－x－1=0在区间［1.0，1.5］内有唯一实根，所以可取［1.0，1.5］为方程的一个根的隔离区间。需要说明的是,利用逐步搜索法得到的方程根的隔离区间长度与步长h有关，且随着步长的减小，根的隔离区间长度也减小。这意味着步长h如果取的足够小，则可得到任意精度的近似根，即可获得方程的根。然而，单用逐步搜索法计算方程的根不是一个好的方法，因为当要求计算精度很高时，步长较小，搜索的步数增多，计算量增大；可以将逐步搜索法与其他方法，如二分法等联合使用来计算方程的根。 2.2二分法

二分法的基本思想是取隔离区间的中点作为方程的近似根，通过计算区间的中点、中点函数值及区间端点函数值，判断它们的符号，逐步对半缩小有根区间，直至将有根区间缩小到满足根的精度要求，从而得到方程的近似根。下面介绍二分法的具体计算过程。它们的关系为并且，其中每一个区间都是前一个区间长度的一半，从而［an，bn］的长度为(2.1)当n→∞，这些区间将收敛于一点，该点即为所求方程的根。在实际应用中，无法也没必要去完成无穷的运算，只要能够获得满足预定精度的近似值即可。若令区间［ak，bk］的中点xk=(ak+bk)/2为方程的根x*的近似值，则根据二分法的计算过程可以得到一个序列：x0，x1，x2，…，xk，由此可得(2.2)此即为以xk作为方程的近似根时的误差。如果预定精度为ε，则只要(2.3)xk即可作为方程的近似根。据此给出二分法的具体步骤如下：(1)计算f(x)在区间［a，b］端点的函数值f(a)，f(b);表2.2例2－3的计算结果

从表2.2可以看出，当计算到k=7时，得到方程的近似根x7=1.364，其误差为0.004,小于要求的误差0.005，此即为满足要求的方程的近似根。

根据二分法的计算过程可知，每一步计算得到区间的中点都需要判断其误差是否满足要求，如果满足要求则停止计算，否则继续。这种情况下不知道需要计算的具体步数,那么是否能够事先计算出需要的步数，然后直接计算到具体的步数从而得到满足误差的根呢？回答是肯定的，推导二分法计算步数公式的过程如下：设第k步计算得到的方程的根x*的近似值为xk，可知其绝对误差 ，若要求的误差为ε，则有另外，根据式(2.1)有所以有，即对上式两边取对数可得，即(2.4)

例2－4根据例2－3的方程及其要求的精度，计算二分法的计算步数。

解根据题意知a=1，b=2，ε=0.5×10－2，将其代入式(2.4)得则k取7，即二分法对分的次数为7时即可满足精度要求，这也与例2－3的计算结果相同。二分法计算过程简单，程序容易实现，可在大范围内求根，但该方法收敛较慢(仅与一个以1/2为比值的等比级数相同)，且不能求重根和复根，一般用于求根的初始近似值。

2.3迭代法

2.3.1迭代法的概念及其过程

迭代法是一种逐步求精的方法，是解代数方程、超越方程、方程组、微分方程等的一种基本而重要的方法。迭代法采用的是逐次逼近的方法，首先给定一个粗糙的初始值，然后用一个迭代公式反复校正这个初始值，直到满足预先给定的精度要求为止。下面介绍迭代法的具体计算过程。(2.5)由此得(2.6)式(2.6)即为迭代公式，也称迭代格式。其中,函数φ(x)称为迭代函数。 将初始值x0代入迭代公式(2.6)可得逐步代入式(2.6)迭代可得

例2－5用迭代法求方程2x3－x－1=0在0附近的根。

解

(1)根据方程将其等价变换为x=2x3－1，得迭代公式：xk+1=2x3k－1,取x0=0，代入迭代公式进行计算，其迭代过程如下：…

(2)根据方程将其等价变换为，得迭代公式： ,取x0=0，代入迭代公式进行计算，其迭代过程如下：

从计算结果可以看出，根据该迭代公式得到的数列{xn}]收敛到1.0000，则方程的根为1.0000。

在例2－5中，同样的方程，不同的迭代公式，得到了不同的结果。也就是说,迭代函数φ(x)不同，相应的数列{xn}收敛情况不同，可能收敛也可能不收敛，若收敛则称迭代公式收敛(迭代收敛)，否则称迭代公式发散(迭代发散)。而对于方程f(x)=0，如何选择迭代函数，使由其得到的迭代公式是收敛的呢？下面讨论迭代法的收敛性。2.3.2迭代法的收敛性定理

定理2.1设方程f(x)=0的等价形式为x=φ(x)，其中φ(x)在区间［a，b］上具有连续的一阶导数，假设迭代函数满足下列两项条件：

条件1:对任意x∈［a，b］总有φ(x)∈［a，b］；

条件2:存在正常数L<1，使对任意x∈［a，b］有φ′(x)≤L。则有

结论1:方程f(x)=0在区间［a，b］内有唯一根x*；

结论2:迭代公式xk+1=φ(xk)(k=0，1，2,…)对于任意的初始值x0∈［a，b］均收敛于方程的根x*；

结论3:

(2)证明结论2。根据迭代公式xk+1=φ(xk)(k=0，1，2,…)有根据拉格朗日中值定理有其中ξk为(xk－1，x*)内的一点,所以有则利用条件2有即(k=1，2，3,…)递推可得即由于L<1，故对上式两端取极限可得即

也就是说迭代数列收敛，且迭代公式xk+1=φ(xk)收敛于方程的根。

(3)证明结论3。因为而根据结论2的证明有所以由此可得而根据条件2可得所以结论3得证。定理的结论3给出了误差的估计方式，只要前后两次迭代值的偏差|xk－xk－1|足够小，就可以保证迭代误差|x*－xk|有足够的精度，因此常常通过|xk－xk－1|来判断是否满足迭代精度，即若预先要求的误差限为ε，只要|xk－xk－1|≤ε就停止迭代,得到满足误差要求的近似根xk。

此外 ，满足定理2.1的条件2。所以迭代公式收敛。

例2－7用迭代法求方程ex+10x－2=0在区间(0，0.2)上的近似解，要求精确到小数点后6位。

解根据题目，迭代函数有如下两种构造形式：计算其一阶导数得则根据定理2.1可知,采用能够获得方程的根，即迭代公式为取初始值x0=0，代入迭代公式计算可得而，不满足精度要求，继续迭代，计算结果如表2.3所示。表2.3例2－7的计算结果+代入已知条件可得由此得两边取极限有则根据定义2.2可知,迭代公式φ(x)为p阶收敛的。 2.4牛顿迭代法与弦割法

2.4.1牛顿迭代法

1.牛顿迭代公式

设xk是方程f(x)=0的一个近似根，把f(x)在xk处进行泰勒展开可得取前两项，即其线性部分作为f(x)的近似:(2.8)设f′(xk)≠0，则由式(2.8)可得令其左端的x为xk+1，则有(k=0，1，…)式(2.9)即为牛顿迭代公式。由该式可得到相应的迭代函数为(2.9)(2.10)

例2－8用牛顿迭代法求方程x=e－x在x=0.5附近的根。

解将方程变换为xex－1=0，即f(x)=xex－1，则根据牛顿迭代公式有整理后得取初始值x0=0.5，并代入以上迭代公式进行计算，结果如表2.4所示。从表2.4中可以看出，应用牛顿迭代法迭代3次，可得到较高的精度0.2×10－4。表2.4例2－8的计算结果

2.牛顿迭代法的几何意义

设方程f(x)=0，取x的一个初始值x0，则可得曲线y=f(x)上的一个点(x0，f(x0))，曲线上过该点的切线方程为令y=0，则得到该切线与x轴交点的横坐标此值即为根据牛顿迭代公式及初始值x0得到的值x1。图2.2牛顿迭代法的几何意义

3.牛顿迭代法的收敛性

对牛顿迭代法中的迭代函数求导数有(2.11)(2.12)设x*是方程f(x)=0的单根，则有f(x)=(x－x*)g(x)，且g(x*)≠0。则有则于是有(2.13)(2.14)通常情况下，φ″(x*)≠0，则根据定理2.3可知,牛顿迭代法至少是二阶局部收敛的，且根据定理2.3的证明有(2.15)2.4.2近似牛顿迭代法与弦割法

1.近似牛顿迭代法

牛顿迭代公式需要计算每个迭代点的导数f′(xk)，如果用x0的导数近似代替f′(xk)，则牛顿迭代公式变成(2.16)此即为近似牛顿迭代公式，也称为简化的牛顿迭代法。近似牛顿迭代公式只需要计算一次导数，减少了计算量，但精度比牛顿迭代法稍低。

2.弦割法

用数值导数代替牛顿迭代公式中迭代点的导数f′(xk)的计算，即将其代入牛顿迭代公式可得(k=1,2,…)(2.17)此即为弦割法的迭代公式。从该公式可以看出,弦割法需要两个初始值才能进行迭代计算。图2.3弦割法的几何意义

图2.3中的曲线y=f(x)由方程f(x)=0得到，该