第7章 非线性方程的数值求法

第七章非线性方程与方程组的数值解法1.二分法2.迭代法及其收敛性3.埃特金（Aitken）加速法4.牛顿迭代法(切线法)5.弦截法2023/2/11

引言在科学研究和工程设计中,经常会遇到的一大类问题是非线性方程

f(x)=0(7.1)

的求根问题，其中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)=0的m重根(m>1)当且仅当2023/2/12记笔记

当f(x)不是x的线性函数时，称对应的函数方程为非线性方程。如果f(x)是多项式函数，则称为代数方程，否则称为超越方程（三角方程，指数、对数方程等）。一般称n次多项式构成的方程为n次代数方程,当n＞1时,方程显然是非线性的一般稍微复杂的3次以上的代数方程或超越方程,很难甚至无法求得精确解。本章将介绍常用的求解非线性方程的近似根的几种数值解法2023/2/13记笔记

通常方程根的数值解法大致分为三个步骤进行①

判定根的存在性。即方程有没有根？如果有根，有几个根？②确定根的分布范围。即将每一个根用区间隔离开来，这个过程实际上是获得方程各根的初始近似值。③根的精确化。将根的初始近似值按某种方法逐步精确化，直到满足预先要求的精度为止2023/2/147.1二分法

二分法又称二分区间法,是求解方程(7.1)的近似根的一种常用的简单方法。设函数f(x)在闭区间[a,b]上连续,且f(a)f(b)<0,根据连续函数的性质可知,f(x)=0在(a,b)内必有实根,称区间[a,b]为有根区间。为明确起见,假定方程f(x)=0在区间[a,b]内有惟一实根x*。二分法基本思想:首先确定有根区间,将区间二等分,判断f(x)的符号,逐步将有根区间缩小,直至有根区间足够地小,便可求出满足精度要求的近似根。2023/2/157.1.1确定有根区间的方法为了确定根的初值，首先必须圈定根所在的范围，称为圈定根或根的隔离。在上述基础上，采取适当的数值方法确定具有一定精度要求的初值。对于代数方程，其根的个数（实或复的）与其次数相同。至于超越方程，其根可能是一个、几个或无解，并没有什么固定的圈根方法求方程根的问题，就几何上讲,是求曲线

y=f(x)与

x轴交点的横坐标。2023/2/16

由高等数学知识知,设f(x)在区间[a,b]上连续,如果f(a)·f

(b)<0,则在[a,b]中至少有一个实根。如果f(x)在[a,b]上还是单调的，则仅有一个实根。记笔记由此可大体确定根所在子区间，方法有：(1)画图法(2)逐步搜索法y=f(x)abyx2023/2/17(1)画图法画出y=f(x)的略图，从而看出曲线与x轴交点的大致位置。也可将f(x)=0分解为1(x)=2(x)的形式，1(x)

与2(x)两曲线交点的横坐标所在的子区间即为含根区间。 例如xlnx-1=0

可以改写为lnx=1/x

画出对数曲线y=lnx,与双曲线y=1/x,它们交点的横坐标位于区间[2,3]内2023/2/18(1)画图法023yx2023/2/19对于某些看不清根的函数，可以扩大一下曲线y0xy=f(x)y=kf(x)(1)画图法记笔记2023/2/110y0xABa1b1a2b2(2)逐步搜索法(2)搜索法

对于给定的f(x),设有根区间为[A,B],从x0=A出发,以步长h=(B-A)/n(n是正整数),在[A,B]内取定节点:xi=x0＋ih(i=0,1,2,…,n),从左至右检查f(xi)的符号,如发现xi与端点x0的函数值异号,则得到一个缩小的有根子区间［xi-1,xi］。2023/2/111例1方程f(x)=x3-x-1=0

确定其有根区间解：用试凑的方法，不难发现

f(0)<0f(2)>0

在区间（0，2）内至少有一个实根设从x=0出发,取h=0.5为步长向右进行根的搜索,列表如下xf(x)00.51.01.52

–––++可以看出，在[1.0,1.5]内必有一根2023/2/112用逐步搜索法进行实根隔离的关键是选取步长h

要选择适当h，使之既能把根隔离开来，工作量又不太大。

为获取指定精度要求的初值,可在以上隔离根的基础上采用对分法继续缩小该含根子区间

二分法可以看作是搜索法的一种改进。2023/2/113①取有根区间[a,b]之中点,将它分为两半,分点,这样就可缩小有根区间7.1.2

二分法求根过程

设方程f(x)=0在区间[a,b]内有根,二分法就是逐步收缩有根区间，最后得出所求的根。具体过程如下

2023/2/114②对压缩了的有根区间施行同样的手法,即取中点,将区间再分为两半,然后再确定有根区间,其长度是的二分之一③如此反复下去,若不出现,即可得出一系列有根区间序列：上述每个区间都是前一个区间的一半,因此的长度

当k→∞时趋于零,这些区间最终收敛于一点x*即为所求的根。2023/2/115

每次二分后,取有根区间的中点作为根的近似值，得到一个近似根的序列该序列以根x*为极限只要二分足够多次(即k足够大),便有这里ε为给定精度,由于,则2023/2/116当给定精度ε＞0后,要想成立,只要取k满足即可，亦即当:

时,做到第k+1次二分,计算得到的就是满足精度要求的近似根。在程序中通常用相邻的与的差的绝对值或与的差的绝对值是否小于ε来决定二分区间的次数。

2023/2/117

二分法算法实现2023/2/118例２求方程f(x)=x3-x-1=0

在区间[1.0,1.5]内的一个实根,使误差不超过0.5×10-2。P215例３证明方程在区间[2,3]内有一个根,使用二分法求误差不超过0.5×10-3的根要二分多少次？证明令且f(x)在[2,3]上连续,故方程f(x)=0在[2,3]内至少有一个根。又当时时，,故f(x)在[2,3]上是单调递增函数,从而f(x)在[2,3]上有且仅有一根。

给定误差限＝0.5×10-3,使用二分法时2023/2/119误差限为只要取k满足

即可，亦即二分法的优点是不管有根区间多大,总能求出满足精度要求的根,且对函数f(x)的要求不高,只要连续即可,计算亦简单;它的局限性是只能用于求函数的实根,不能用于求复根及偶重根,它的收敛速度与比值为的等比级数相同。所以需二分10次便可达到要求。2023/2/1207.2不动点迭代法及其收敛性

一般的非线性方程,没有通常所说的求根公式求其精确解,需要设计近似求解方法.迭代法---是一种逐次逼近的方法,用某个固定公式反复校正根的近似值,使之逐步精确化，最后得到满足精度要求的结果。为求解非线性方程f(x)=0的根，先将其写成便于迭代的等价方程7.2.1迭代法的基本思想2023/2/1212023/2/122再将代入式的右端,得到,依此类推,得到一个数列…，其一般表示式(5.4)称为求解非线性方程的迭代公式。

(5.4)2023/2/123如果由迭代格式产生的序列收敛,即

则

实际计算中当然不可能也没必要无穷多步地做下去,对预先给定的精度要求ε，只要某个k满足即可结束计算并取2023/2/124例4用迭代法求方程在x=1.5附近的一个根。相应地可得到两个迭代公式如果取初始值，用上述两个迭代公式分别迭代，计算结果将方程改写成如下两种等价形式

注意：迭代函数的构造方法是多种多样的。2023/2/125kxk012345671.51.357211.330861.325881.324941.324761.324731.32472迭代公式是否收敛是选择迭代公式的关键！2023/2/126(a)(b)7.2.2迭代法的几何意义

通常将方程f(x)=0化为与它同解的方程的方法不止一种,有的收敛,有的不收敛,这取决于的性态,方程的求根问题在几何上就是确定曲线y=与直线y=x的交点P*的横坐标(图7-2所示)

2023/2/127图7-2迭代法的几何意义

2023/2/128对方程f(x)=0可以构造不同的迭代公式,但迭代公式并非总是收敛。那么,当迭代函数满足什么条件时，相应的迭代公式才收敛呢？即使迭代收敛时，我们也不可能迭代无穷多次，而是迭代有限次后就停止，这就需要估计迭代值的误差，以便适时终止迭代.

7.2.3迭代法收敛的条件2023/2/129定理1设函数在[a,b]上具有连续的一阶导数,且满足

（1）对所有的x∈[a,b]有

（2）则方程在[a,b]上的解存在且唯一，且对任意的∈[a,b]，迭代过程均收敛于。并有误差估计式：

①

②

2023/2/130证:构造函数,由条件(1)对任意的x∈[a,b]

[a,b]由零点定理知,假设有两个解由微分中值定理有由条件(2)存在唯一2023/2/131按迭代过程,有

由于L<1,所以有,可见L越小,收敛越快，且与无关。2023/2/132即

①

得证。

即

②

得证。

证(2)

再证误差估计式2023/2/133定理1

对任意的∈[a,b]，迭代过程均收敛于。且有①

②

通过①式控制近似值的误差

2023/2/1347.2.4迭代法的算法框图2023/2/135例5

对方程,构造收敛的迭代格式,求其最小正根,计算过程保留4位小数。解容易判断[1,2]是方程的有根区间,且在此区间内仅有一根。将原方程改写成以下两种等价形式:①迭代公式不满足迭代收敛条件!2023/2/136例5

对方程,构造收敛的迭代格式,求其最小正根,计算过程保留4位小数。此时迭代公式满足迭代收敛条件。

②2023/2/137例5

对方程,构造收敛的迭代格式,求其最小正根,计算过程保留4位小数。解将原方程改写成以下形式。

2023/2/138例6设,要使迭代过程局部收敛到,求的取值范围。解：由在根邻域具有局部收敛性的时条件

2023/2/139例7已知方程在内有根,且在上满足,利用构造一个迭代函数,使局部收敛于。故迭代公式局部收敛解：2023/2/1407.2.6迭代法的收敛速度

一种迭代法具有实用价值，首先要求它是①收敛的，其次还要求它②收敛较快。

则称序列是p阶收敛的,c

称渐近误差常数。特别地,p=1时称为线性收敛,p=2时称为平方收敛。1<p<2时称为超线性收敛。

定义2.2设迭代过程收敛于的根,记迭代误差若存在常数p（p≥1）和c(c>0)，使

2023/2/141

数

p

的大小反映了迭代法收敛的速度的快慢，p越大，则收敛的速度越快，故迭代法的收敛阶是对迭代法收敛速度的一种度量。

定义2.2设迭代过程收敛于的根,记迭代误差若存在常数p（p≥1）和c(c>0)，使p——收敛阶2023/2/142定理4设迭代过程，若在所求根的邻域连续且则迭代过程在的邻域p

阶收敛。证:由迭代公式及根据已知条件得2023/2/143例8已知迭代公式收敛于证明该迭代公式平方收敛。根据定理7.3可知，迭代公式平方收敛。将代入，为了使迭代过程收敛或提高收敛的速度,可设法①提高初值的精度以减少迭代的次数②提高收敛的阶数p证:迭代公式相应的迭代函数为2023/2/144（1）加权法其中

可见,是比更好的近似根7.3迭代过程的加速*

又根据中值定理有设是根的某个近似值,用迭代公式校正一次得2023/2/145在龙贝格(Romberg)算法中我们已使用过此技术

根据积分区间分成n等份和2n等份时的梯形公式误差估计式(4.8)可得

如果用对进行修正，将更接近积分真值,因此可得到具有更好效果的近似公式。2023/2/146作为中间值并记为：化简并写成：修正为：迭代一次，计算一次在上述迭代公式中，要事先估计L的值。2023/2/147例9用加权法加速技术求方程在0.5附近的一个根。仍取,逐次计算得=0.56658…=0.56714。迭代4次便可得到精度的结果,而不用加速技术需迭代18次,效果显著。取L=-0.6，建立如下迭代公式解：因为在附近2023/2/148（2）埃特金（Aitken）方法

在加权法中,估计L的值有时不太方便。假设在求得以后,先求出由于求根区间变化不大,用某个定值L近似2023/2/149将迭代值再迭代一次,得新的迭代值将上述两个方程联立消去常数L化简可得同理记2023/2/150这样得到公式称为埃特金（Aitken）加速公式计算一次迭代加速迭代两次2023/2/151例10用埃特金方法求方程在初值附近的一个根,精度要求，

取迭代格式所以迭代格式收敛。2023/2/152例10用埃特金方法求方程在初值附近的一个根,精度要求，

取迭代格式解埃特金方法迭代格式为只迭代二次就得到满足精度要求的解。2023/2/153控制递推公式中误差的传播

对于一个数学问题的求解往往有多种数值方法在选择数值方法时，要注意:所用的数值方法不应将计算过程中难以避免的误差放大的较快，造成计算结果完全失真。例

计算积分并估计误差解容易得到递推公式2023/2/154则递推公式前进式2023/2/155于是

计算时的误差被扩大了倍,显然算法不稳定。

若有误差且与精确值的误差为，则误差的递推规律为

2023/2/156准确的理论递推式实际运算的递推式如果将递推公式变换一种形式从而有后退式2023/2/157即于是有则这个算法的误差传递规律为

即每计算一步的误差的绝对值是上一步的十分之一，误差的传播逐步缩小，得到很好的控制，这个算法是数值稳定的2023/2/158用迭代法可逐步精确方程根的近似值，但必须要找到的等价方程,如果选得不合适,不仅影响收敛速度,而且有可能造成迭代格式发散。能否通过一定的程序找到一个迭代函数,使之满足结构简单,收敛速度快,又不存在发散的问题。这就是本节要介绍的牛顿迭代法。7.4

牛顿迭代法

2023/2/159牛顿迭代法是一种重要和常用的迭代法,它的基本思想是将非线性函数f(x)逐步线性化,从而将非线性方程f(x)=0近似地转化为线性方程求解。7.4.1牛顿迭代法的基本思想

2023/2/1607.4.2牛顿迭代法的几何解释

方程f(x)=0的根x*是曲线y=f(x)与x轴交点的横坐标,设xk是根x*的某个近似值,过曲线y=f(x)的横坐标为xk的点Pk=(xk,f(xk))引切线交x轴于xk+1,并将其作为x*新的近似值,重复上述过程,一次次用切线方程的根近似方程f(x)=0的根,所以亦称为牛顿切线法。2023/2/161忽略高次项,用其线性部分作为函数f(x)的近似，

对于方程f(x)=0，设其近似根为xk，函数f(x)可在xk的附近作泰勒展开2023/2/162将右端取为,即是比更接近于的近似值

这就是著名的牛顿迭代公式2023/2/1637.4.3

牛顿迭代法的收敛性证:牛顿迭代公式对应的迭代函数为从而定理2.4设x*是方程f(x)=0的单根，且

f(x)在x*的某个邻域内有连续的二阶导数,则牛顿法在x*附近局部收敛,且至少二阶收敛。∵

x*是方程f(x)=0的单根，所以,牛顿迭代法在

x*附近局部收敛。2023/2/164证至少二阶收敛,方法12023/2/165则称序列是p阶收敛的,c

称渐近误差常数。特别地,p=1时称为线性收敛,p=2时称为平方收敛。1<p<2时称为超线性收敛。

定义2.2设迭代过程收敛于的根,记迭代误差若存在常数p（p≥1）和c(c>0)，使

证法2：用泰勒公式2023/2/166证法2：用泰勒公式2023/2/167所以证毕2023/2/168解：牛顿迭代公式2023/2/169证收敛：证法2：2023/2/170解：证毕2023/2/171切线法(Newton)的使用条件2023/2/172yx0B=x0f´´(x)>0xn+1X*ayx0Bf´´(x)>0a=x0yx0B=x0f´´(x)<0ayx0Bf´´(x)<0a=x02023/2/173yx10x0X*0x0X*x2不满足迭代条件时，可能导致迭代值远离根的情况而找不到根或死循环的情况2023/2/1747.4.4牛顿迭代法的算法实现2023/2/175例11用牛顿迭代法求方程的根,ε=10-4.

取x0=0.5,逐次计算得

x1=0.57102,x2=0.56716，

x3=0.56714解：因建立迭代公式2023/2/1767.4.5牛顿下山法

将牛顿迭代法与下山法结合起来使用,即在下山法保证函数值下降的前提下,用牛顿迭代法加快收敛速度。把这一算法称为牛顿下山法。即满足这项要求的算法称下山法。其中λ(0<λ<1)为下山因子通常,牛顿迭代法的收敛性依赖于初始值x0的选取,如果x0偏离所求的根x*比较远,则牛顿法可能发散。为了防止迭代发散,我们对牛顿迭代法的迭代过程再附加一项要求,即具有单调性2023/2/177

下山因子的选择是个逐步探索的过程，设从λ=1开始反复将λ减半进行试算,即逐次取λ为从中挑选下山因子，直至找到其中某个λ使单调性条件成立，则称“下山成功”，否则“下山失败”，这时需另选初值重算。2023/2/178牛顿法可用于求方程重根2023/2/179迭代格式收敛且为线性收敛2023/2/180可将迭代公式改为：2023/2/181得(4.14)式平方收敛。2023/2/1822023/2/183kxk(1)(2)(3)0123x0x1x2x31.51.4583333331.4366071431.4254976191.51.4166666671.4142156861.4142135621.51.4117647061.4142114381.414213562(2),(3)都是二阶方法的精度均达到(1)是一阶方法精度要达到需迭代30次。2023/2/184§7.5弦截法牛顿迭代法虽然具有收敛速度快的优点，但每迭代一次都要计算导数,当f(x)比较复杂时,不仅每次计算导数带来很多不便，而且还可能十分麻烦，如果用不计算导数的迭代方法，往往只有线性收敛的速度。本节介绍的弦截法便是一种不需求导的求根方法。弦截法在迭代过程中不仅用到前一步处的函数值，而且还使用处的函数值来构造迭代函数，称为多点迭代法，能够提高迭代的收敛速度。2023/2/185

7.5.1弦截法的基本思想

为避免计算函数的导数，使用差商

替代牛顿公式中的导数,便得到迭代公式

称为弦截迭代公式，相应的迭代法称为弦截法。2023/2/186弦截法也称割线法,其几何意义是用过曲线上两点、的割线来代替曲线,用割线与x轴交点的横座标作为方程的近似根再过P1点和点作割线求出,再过P2点和点作割线求出,余此类推，当收敛时可求出满足精度要求的7.5.2弦截法几何意义2023/2/187可以证明，弦截法具有超线性收敛，收敛的阶约为1.618，它与前面介绍的一