计算方法 第2章 非线性方程数值解法

第二章非线性方程数值解法

本章将讨论非线性方程

=0（2.1）

的数值解法，我们最为熟悉的非线性方程是一元二次方程

ax1+bx+c=O

也是最简单的非线性方程，其解为：

-h+ylb2-4ac

内＞＞=z

，2a

但是对于（2.1）式中一般形式的非线性函数/（幻，很难甚至不可能找到解析形式的解，通常

只能用数值的方法求其近似数值解。

2.1基本概念

定义2.1如果x♦满足/（一）=0,则称/为方程（2.1）的解或根，也称/为函数/（均的

零点或根。

用数值方法求解非线性方程的解，通常需要我们对其解有•个初步的估计，或知道其解

的一个限定区间，因此确定包含解的区间将是我们首先需要解决的问题。

定义2.2若连续函数/（X）在团,以内至少有一个根，则称切力］为有根区间，若在口,例

内恰有一个根，则称为隔根区间。

定理2.1如果函数一㈤在上连续且＜0,则/（X）在（°向内至少有一

个根，如果函数/5）另外满足在［4切上单调连续，则/3）在（凡份内恰有一个根。

寻找隔根区间的通常方法有：图形法，试探法。

例2」求/（x）=/-3x+3=0的有根区间。

解：作出函数＞=/（工）的曲线图形

图2.1例2.1曲线示意图

观察图中的曲线与X轴的交点，可判断在区间（-3,-2）之间方程有一个根。

例2.2求/(x)=X3+X2-3X-3=O的有根区间。

X••,-2-1.75-1.5-1.25-1•••

/（X）・••-1-0.0470.3750.3950••・

在这个表格里我们又发现一个有根区间（-1.75,-1.5）。

从此例中我们可以体会到试探法有可能漏掉某些有根区间，具有•定的局限性。

2.2二分法

二分法也称为对分法，是我们求解很多问题的有效方法，求解非线性方程也有称之为“二

分法”的数值方法。二分法的算法思想非常简单、直观，收敛性也易于理解，以下我们给出

求解非线性方程二分法的算法过程。

设在区间［凡切上连续且f（b）<0,由高等数学的知识可知在区间团，包内

至少有了。）的一个根X*,令［%,%］=［〃/］，取此区间的中点看=色磬■，则

1）如果八%）/（。）<0,区间［。0，勺］内至少有/J）的一个根，令3，仇］=［。0，/］；

2)如果f(x())/3)20，区间［玉),%］内至少有f(%)的一个根,令［%也］=［%0，%］

如此我们将得到一个新的区间［卬,4］,可以断定了(x)在此区间内至少有一个根月新区

间的长度缩小到原长度的一半，反复执行这一过程，我们将得到一个包含/(力根的区间序

列［4,％］」。”々］4?，与］，…4%，々］,…，这个有根区间序列的每个区间有3个的特点

1)均是有根区间,xe［aktbk］；

2)区间包含，

hk1Clk1

3)区间长度减半，bk-ak=~o

二分法算法的收敛性证明正是基于这3个特点，证明如下：

按照以上算法过程，我们可以得到一有根区间序列［出,4］,攵=0,1,2,…，在每个区间

内取其中点构造近似解序列

A=0,12…(2.2)

则有

<—;一(2.3)

2222女+1

\b-a\

limx,一x=limk=0

kfB।kfs2

从而说明所构造的算法是收敛的。

误差估计：

按照(2.3)式，我们可以得到以％作为一的近似解，其误差为

(2.4)

即近似解的误差不超过原区间的I/2人倍。

终止准则：

如果要求近似解的误差达到指定的精度£>0,即要求一丁|<£,根据(2.3)式只要

当前有根区间满足下式即可:

瓦一4」<勿(2.5)

迭代次数：

在给定精度£后就可以确定迭代次数k，也就是说只要迭代々次，其近似解就可以达到

所要求的精度，根据终止潴则(2.5)式，有:

对上述后边的式子两边取对数就可以算出满足精度£所需要的迭代次数。

算法2.1(求解非线性方程的二分法)

0)［初始化］取初始有根区间［4加，计算/(〃),/(〃)，置迭代精度£>0

1)如果取一4<2£,则得近似解X=岁，算法结束

2)取户小

2

3)如果/(x)/(a)<()则〃=x,否则。=x

4)转1)继续迭代。

5)［算法结束］

实际计算时，在已经确定函数值/(a)/S)vO时，仅需要计算其中一个函数值，在每

个迭代过程中，只需要计算/(X)并不需要再次计算/(〃)，以节约计算量。

例2.3求方程/(x)=/-x-1=0在区间［1,1.5］内的一个实根，要求准确到小数点

后两位(即至少有三位有效数)。

解：首先用有效数字与绝对误差关系公式确定精度e

x.-/<-x］01-3=-xl0-2=0.005=£

22

再计算需要迭代的次数

L5-1"人

2x0.005

两边取对数则有k=6,实际计算过程的结果如下：

迭代次数abb-aX於)

11.009001.500000.500001.25000-0.29688

21.250001.500000.2500C1.375000.22461

31.259001.375000.125001.31250-0.05151

41.312501.375000.062501.343750.08261

51.312501.343750.031251.328130.01458

61.312501.328130.015631.32031-0.01871

最后近似解为：x6=1.32031,精确解为：x*=1.32472,估计误差为：0.005,

实际误差为：

,-/|=|1.32031-1.32472|=0.00441<c=0.005

二分法的优点是算法简单，无需任何参考资料就可以编程实现；缺点是收敛速度慢。

2.3迭代法

迭代法也称为简单迭代法、不动点迭代法，是一种对方程根的逐步逼近、逐步精确直到

满足给定精度要求的迭代算法。

1.迭代法的计算过程

首先把非线性方程/(用=0变换为等价的形式x=g(x),称其为迭代函数，然后取

/(%)=0一个初始近似解.”,按如下迭代格式计算近似解序列：

4+1=8(xkXk=0,1,23…(2.6)

如果lim4=x*且g(x)连续,则

x*=limxk=limg(xk)=^(limxk)=g(x*)

由于X=g(x)与f(x)=。是等价的方程，所以/满足/(./)=0,即也是/(X)的解。

注意到将x”代入g(x)其函数值仍为所以也称/为g*)的不动点，而迭代法也称为

不动点迭代法。

例2.4对于方程/(外二/一工一1=0,取/=1・5,比较以下4种迭代格式的计算

结果。

_(M+D

迭代次数加=#1+一%=又-1

“旧Z+I2

11.50C01.5000e+0001.50001.5000e+000

21.35722.3750e+0001.29101.9375e+000

31.33091.2396c+(X)l1.33214.1053c+000

41.32591.9040e+0031.32313.6l48e+001

51.32496.9024e+0091.32512.3635e+004

61.32483.2886e+0291.32466.6012e+012

71.32473.5565c+0881.32471.4383e+038

从这4个迭代函数建立的迭代法的计算结果可以看出，有两个收敛两个发散，也就意味着并

不是所有的迭代函数都是收敛的，以下我们考察迭代法收敛的条件，为此先看一下迭代法的

几何解释。

2.迭代法的几何解释

对于迭代函数g(x)缓慢单调增情况，如图2.2取初始点八,计算玉=g(x0)对应于曲

线y=冢幻上的p()点，从作为自变量的为计算出的占二g(F)，对应于曲线y=g(x)上

的Pi点，如此继续可以得到々，刍，…，可以看出其趋势将是沿左侧逐步逼近其解一。

对于迭代函数g(x)缓慢单调减情况,如图2.3取/可得曲线上Po点，再从Po对应的X,

计算得到曲线上的Pl点，同样可以得到它，当，…，其趋势将是从两侧逐步逼近其解X*。

总之，当g(x)缓慢变化时，无论是缓慢增还是缓慢减,迭代法均是收敛到方程的根/O

再看迭代函数g(R)急速单调增情况，如图2.4取/可得曲线上Po点，再从对应的M

计算得到曲线上的Pi点，同样可以得到工2，与，…，其趋势将向一侧远离其解X*。

图2.4g(x)急速的单调增图2.5g(x)急速的单调减

当迭代函数g(x)急速单调减时，如图2.5取/可得曲线上Po点，再从P。对应的王计

算得到曲线上的Pi点，同样可以得到々，七，…，但趋势将向两侧远离/。

3.迭代法的收敛性

从几何解释可以看出，迭代法是否收敛与迭代函数g(x)在其解附近的变化率有关，亦

即是与迭代函数g(x)的导数绝对值(刈的大小有关，事实确是如此，请看如下定理：

定理2.2(迭代法收敛的充分条件)如果函数以方)在区间［4,加上可微，X€5,例时满足

条件：

1)a<g(x)<b,即点列.切恒成立;

2)|^z(x)|<L<l,即迭代函数变化缓慢。

则以区间［«切上的任意点x0为初始点，迭代格式看”=晨占)产生的序列｛xk｝都收敛到

方程的唯一根X*。

证明：首先证明根的存在性，考虑辅助函数

(p(x)=g(x)-x

可验证0(〃)=以一a20,(p(b)=g(b)-b<0,则存在使0(x")=0,即

x"=g(/)。

再证迭代格式的收敛性，注意到

==|g'e)(Xz-丁)|4也T

其中J是介于&T与/之间的一点。反更利用该式，则有：

xx_xx

\k-*|*|-^\k-2-X*|<•••<|x0-x*|

因此有limz=x"。关于唯一性，可以任取两个解/)，则有

k-^

/一工=|^(x+)-^(x)|=-x)|<l\x-x

因为Lvl,所以只能是丁=元成立。

定理2.3(误差估计)在定理2.2的条件下，有如下误差估计式:

"一/归啥q(2.7)

证明：事实上，第大次迭代之后再经过〃次迭代，应该有

N+P-8IWN+p-/+PT|+辰+pT-％片21+…+民+1一8I

-〃'k+1-々|+L"2kMi-“…+n+]-“

=(*+1。+…+i)Ki-^l=-xk\

I-L

对此式两边取极限，因为有lim/+〃=/所以也就有(2.7)式成立，证毕。

p—g1

例2.5求方程工="、在己』n2]中的根，要求误差不超ICT1(分析所使用迭代格式的

2

敛散性)。

解：容易验证所给区间g,In2]是方程x=er的隔根区间，取迭代函数为g(x)=cf,

迭代格式为

%1=用(々)=""，女=。，1，2,3,1,

验证定理2.1中条件I),任取“£[Lln2],迭代函数的导数短(幻=一e-'<0,则如)单

2

调减，所以

I1-1

-=e/2=g(in2)<g(x)<g(5)=e2=0.60653<0.69315=In2

1

再验证条件2),k'(x)|=/"<”=0.60653=L<1,从而所取迭代格式是收敛的.

按要求误差必须达到卜-x[v1CT4,只要卜7一々|<10-4(1-£)=0.3935xlO^gp

可，因此取终止精度£=10-5,初始点与=0.5,迭代过程结果如下:

k123456

xk0.6065310.5452390.5797030.5600650.5711720.564863

k789101112

xk0.5684380.5664090.5675600.5669070.5672770.567067

k131415161718

xk0.5671860.5671190.5671570.5671350.5671480.567141

精确解为了=0.567143,近似解为8=0.567141、实际误差

-54

|x18-x*|=|0.567141-0.567142|=0.000002=0.2xl0<lO^

显然我们不可能按照例2.5的方法作为迭代终止的准则，以下我们讨论适合编程的迭代

算法的终止准则。

(1)一个明显的规则是对于给定精度£>0,当上人-不［<£时算法终止，遗憾的是在

迭代过程中卜-是不可知的，注意到(2.7)式表示的是近似解与精确解之差和相

邻近似解之差的美系，我们也可以用上N-迎」来作为迭代收敛的判别准则，即

对于给定的精度£>0,当卜什|—不」<£时算法停止。

当然此时的精度£不再是近似解于精确解的误差限，而是一个算法判断收敛的精度

要求。蚁一终止准则不仅用于求解非线性方程的诙代法，几平所有的诙代算法都是

用这一准则来判断迭代算法收敛的。

(2)另一个需要关注的问题是，迭代算法有不收敛的可能，不能够让算法无休止的迭代

下去，所以算法需要规定迭代超过多少次还没有收敛时，判定迭代失败，即要规定

最大的迭代次数，这一原则也适用于其他迭代算法。

至此我们有了算法的迭代过程以及算法的终止准则，下面给出简单迭代法的算法。

算法2.2(求解非线性方程的简单迭代法)

0)［初始化］取初始点与，最大迭代次数N和精度£>0,置&=0;

1)当&<N时循环执行下列步骤

1.1)计算与+1=或以)；

1.2)如果,川一看|<£,则停止计算，乙.可作为方程的近似解；

1.3)令4=4+1,继续执行下一次循环。

2)［算法结束］

前述的定理2.2给出的迭代法收敛的充分条件不便于验证，使用起来有一定的局限性，

现在再给出一个局部收敛条件，较之于定理2.2更易使用。

定义2.3设/是方程x=g(x)的根，如果存在5>0和/的一个邻域，一5,x"+6］,

当取/£次*-6,/+5|时，迭代格式二双4)收敛于方程的根丁，则称迭代函数

g(x)在方程的根X*处有局部收敛性。

定理2.4(局部收敛条件)设迭代函数g(x)在方程x=g(x)的根/附近的一个邻域有

连续的一阶导数且卜'(刈＜1,则迭代格式看”二g“)在/附近具有局部收敛性。

证明留做习题。

4.迭代加速

一般的迭代法收敛速度太慢，我们考虑如何提高其收敛速度的方法。

取方程的初始近似解小，令凡=g(%)，在迭代格式收敛的情况下，一般凡是比与

更好的近似解。设/是方程的精确解，由中值定理有

-/=g（Xo）-g（X*）=g'©（x（）-X”）

记g'e)=L,则有

），07*XL（x0一丁）

从该式解得

・1LL/、

\—L1—L\-L

以此作为近似解得

L/、

为=—7(丫。一/。)

1—L

根据这•思想我们得到一•般迭代格式的加速公式：

%二g（s）

1,DJ2…（2.8）

Z+i="一；~7（九一五）

1-L

考虑用此加速迭代公式计算例2.5中的方程，取初始点与=0.54=8'(%)=145,

计算结果为：

k01234

xk0.5000000.5663110.5671230.5671430.567143

迭代3次即超过一般迭代法18次的迭代精度。

斯蒂芬森(Steffensen)加速

对于上述加速的方法，最大的问题是要估计双工)的导数，这是很困难的甚至是不可能

做到的，以下我们考虑用两次迭代的信息估计出A=g'4)的值。

取初始点”0,计算%=g(%),Zo=g(%)，仍记L=g'C),则有

)，0-xI

=L(XQ-x

解此联立方程，消去L得

)'0-/〜/一/

Z07*

最后得新的近似解为

*()'o-*0)~

X«xo----------------=X］

^0-2>0+20

此公式就是著名的斯蒂芬森加速公式，并由此得到斯蒂芬森加速迭代格式:

%=g(z)

z«=g(”)=0,1,2,...(2.9)

(%一占)2

%=z-

占-2)JZ«

Stcffcnscn迭代法一个更为重要的优点是只要短(外W1算法就是收敛的，用此加速迭代

公式求解例2.5的结果为：

k0123

0.50000()0.5676240.5671430.567143

两次已经得到很好的近似解占=0567143,远优于简单迭代法的18次迭代。

算法2.3(求解非线性方程的斯蒂芬森(Steffensen)加速算法)

0)［初始化］取初始点餐,最大迭代次数N,给定精度£>(),置女=0；

1)当左<N时循环执行下列步骤

1.1)按(2.9)式计算然，z*,x“|；

1.2)若卜人句―8|<£,则停止计算，与3为方程的近似解。

1.3)令k=k+\,继续执行下一次循环

2)［算法结束］

我们用迭代格式(2.9)重新计算例2.4的/(幻=/-工-1=0,取同样的初始点

x0=1.5,计算结果为:

占+1=1+」~（X：+X—1）

迭代次数Z+i=暇-1Z+I=2

VXk

01.5000001.5000001.5000001.500000

11.3248991.4162931.3253721.389383

21.3247181.3556501.3247181.335411

31.3247181.3289491.324718L325044

41.3248041.324718

51.3247181.324718

61.324718

5.收敛速度

在此之前讲述的几个算法，我们看到不同的迭代公式收敛速度差别很大，为了度量算法

的收敛速度，我们引入收敛“阶”的概念。所谓一个算法的收敛速度，其本质是迭代过程中的

近似解与精确解的误差收敛于0的速度，而算法的收敛阶越高收敛速度越快。

定义2.4设limx,=/,如果存在常数〃之0,c之0,使得

上T0O

lim一"Lc(2.10)

AfX*P

Xk-x

则称序列kJ为P阶收敛或称收敛的阶是p。显然阶越高收敛越快！

P=\时称为线性收敛，一般迭代法是线性收敛；

P=2时称为平方收敛，Steffensen加速法是平方收敛；

p=l且(-0称为超线性收敛,

定理2.5(判断收敛阶定理)设g(x)在非线性方程工=g(x)的根/处有连续的〃阶导

数而且满足

g'，)=g"(x")=…=g8)(『)=o,g""(x*)W0

则迭代格式s+l=g(s)是〃阶收敛。

证明：因为g'(J)=0,由定理2.3可知，迭代格式在x*附近局部收敛，将g(x)在x*

处Taylor展开，则有

<p-,)

g(s)=g(j)+;;g'(♦)(Z7*)+…+-gu*)(xk-/尸

1!(pT)!

=g，)+Lg5©(/一/)'

其中〈介于占和X*之间，此式可改写成：

%7*二以々)-武/)=4."@(4一/)

根据此式可得到

lim国=1=而贮4=吐贮工。

口々_/『》〃！〃！

从而证得迭代格式S+i=g(占)是〃阶收敛的。

可以验证，对于例2.5中的迭代格式g(5)=ef,由于g，(/)=«"。0,因而是线

性收敛的：而对于Steffensen加速公式，可以验证是二阶收敛。

2.4牛顿(Newton)法

求解非线性方程的Newton法也是一种迭代法，而且是最著名的一种迭代法，也被认为

是最为有效的迭代法之一，其收敛阶可达二阶，而算法的推导过程也非常简单。

1.Newton法迭代公式及收敛性

考虑已得到非线性方程/(x)=0的解X*的一个近似值占，将函数/5)在9处Taylor

展开并忽略二阶以上的高阶项得到一个近似的线性方程：

fM«f(xk)+f'(xk)(x-xk)=0

以此线性方程的解作为原方程新的近似解5小

/Ux)

有理由认为与+1将是比4更好的近似解，反复执行此过程可得如下迭代格式:

XA+I=xkD,k=0,1,2,-••(2.11)

f(a)

称(2.11试为Newton迭代格•式c

如果把g(x)=x-/*，则Newton法也是迭代法的一种形式，其导数为

/WTW

(广。)『

如果/是/(幻=0的一个单根,则有f(x*)=o,4(丁)工0,进而g'(x*)=0,也就

存在x•的邻域氏/+加，使

|g(x)|vl,xw［x*

根据定理2.4和定理2.5可知Newton法有局部收敛性且至少是二阶收敛，因此有如下结论。

定理2.6(Newton法收敛性)如果x"是f(x)=。的一个单根，则Newton法有局部收

敛性且至少是二阶收敛的。

算法2.4(求解非线性方程的Newton法)

0)［初始化］取初始点与，最大迭代次数N和精度£>0,置&=0;

1)当〃VN时循环执行以下各步骤

1

1.1)计算Xi=4-I)'):

1.2)若氏讨一占卜£,则停止计算，々用为方程的近似解；

1.3)令A=攵+1,继续执行下一次循环

2)［算法结束］

3

例2.6试用Newton法求解方程f(x)=x-x-1=0,取初始点x0=1.50

解：先计算导数/J)=3/一1,迭代函数双©二4一华1,得迭代格式

/W

迭代结果为

k01234

xk1.5000001.3478261.3252CX)1.3247181.324718

2.Newton法的几何意义

如图所示的是Newton法迭代的收敛过程。

图2.6Newton法的几何意义

Newton法在求解非线性方程/（x）=0的迭代过程中，首先取近似解与可得到曲线

），=/（x）上的点（/，/（%）），过此点作曲线的切线，而切线与X轴有一个交点修，同样

对应曲线上的一个新点（3,/（再）），过此点再作曲线的切线，此切线与X轴又有一个交点々，

如图，如此反匆执行此过程，迭代点列将收敛到方程/（©=0的解X"。

3.Newton下山法

关于Newton法的收敛性我们仅证明了局部收敛性，当初试点选择不好时，迭代有可能

存在不收敛的危险，事实也确是如此。

对例2.6的方程/"）二/一X-1=0用Newton法，取初始点X。=0.58迭代3次，迭

代点列为：

k0123

xk0.580000151.111304100.74235567.163809

为了解决Newton法的此类问题，通常采用所谓的Newton下山法，策略就是在Newton

迭代公式中增加一个参数。…称为Newton下山迭代公式：

加二3如(2.12)

参数由称为下山因子，其目的是保证使

(2.13)

成立，之所以称为卜.山因子，是因为当迭代点S处的函数值太大(上山)时，使用此

因子能够使其值减小(下II)。一般是先取。《=1,如果不满足(2.13)式则参数减半，反复

检查直到满足(2.13)式，如果参数处已经很小仍然不满足Q.13)式，则必须换一个新的初始

点与。使用Newton下山法重新计算，迭代结果为:

k012345

40.5800001.1680131.3537841.3254751.3247181.324718

4.重根情况的Newton法

在前述的有关Newton法收敛性与收敛阶的证明分析中，前提是假设/是/(x)=0的

一个单根，对于重根情况容易证明Newion法仅是线性收敛的，可以用如下方法提高Newlon

法的收敛速度。

设/是方程的，〃重根，定义迭代函数：

f(x)

g(x)=x-m(2.14)

fXx)

可以证明(2.14)式定义的迭代格式将是二阶收敛的，遗憾的是求解非线性方程时往往事先并

不知道其根是否为重根，因此迭代格式(2.14)基本无实用价值。另一方面我们知道Steffensen

加速公式是二阶收敛的，对丁•重根情况还可以考虑用Steffensen加速公式对Newlon法进行

加速能够提高收敛速度，试看下述例子。

例2.7取初始点七)=1.5,用Newton法、(2.14)式、Steffensen加速公式求解

/U)=U+1)U-1)2=O

解：⑴用Newton法:

(xk+1)(,^-1)~

%=看

迭代17次，结果如下:

k012345

xk1.500001.272731.144081.074381.037851.01910

k678910II

1.009591.004811.002411.001201.000601.00030

k121314151617

xkl.(X)0I51.000081.000041.000021.0()0011.0(X)00

(2)利用(2.14)式

(X*+1)(看一

%1=八-2—y—--------------

3x；-2x「l

迭代3次，结果如下：

k0123

1.500001.045451.000501.00000

(3)利用Steffensen加速公式迭代2次，结果如下:

k012

xk1.500000.995571.00000

例2.8导出计算十(4>0)的Newton迭代格式，使其即无开方又无除法运算。

I2

解：令f(x)=a一一f\x)=—,则Newton法的迭代函数为

厂x

1

a--F