第章方程的近似解法

第二章 方程求根

在许多实际问题中，常常会遇到方程f(x)=0求解的问题。当f(x)为一次多项式时，f(x)=0称为线性方程，否则称为非线性方程。对于非线性方程，由于f(x)的多样性，求其根尚无一般的解析方法可以使用，因此研究非线性方程的数值解法是十分必要的。

本章主要介绍求非线性方程根的一些常用方法。它们是增值寻根法、二分法、迭代法、牛顿法及割线法。这些方法均是知道根的初始近似值后，进一步把根精确化，直到达到所要求的 精度为止。也即求非线性方程根的数值方法。 第一节 第一节 增值寻根法与二分法 2.1.1 增值寻根法

设非线性方程f(x)=0的根为*

x ，增值寻根法的基本思想是，从初始值0x 开始，按规定 的一个初始步长h 来增值。令 1n x +=n x +h(n=0,1,2，…)，同时计算f(1n x +)。 在增值的计算过程中可能遇到三种情形：

(1) f(1n x +)=0，此时1n x +即为方 程的根*

x 。

(2) f(n x )和f(1n x +)同符号。这说明区间［n x , 1n x +］内无根。

(3) f(n x )和f(1n x +)异号， 即有

f(n x )·f(1n x +)＜0

此时当f(x)在区间［n x , 1n x +］上连续时，方程f(x)=0在［n x , 1n x +］ 一定有根。也即我们用增值寻根法找到了方程根的存在区间，n x 或1n x +均可以视为根的近似值。下一步就是设法在该区间内寻找根 *

x 更精确的近似值，为此再用增值

寻根法 把n x 作为新的初始近似值，同时把步长缩小，例如选新步长

1100h h =

，这 样会得到区间长度更小的有根区间，从而也得到使 f(x) 更接近于零的n x ，作为*x 更 精确的近似值，若精度不够，可重复使用增值寻根法，直到有根区间的长度｜1n x +-n x ｜＜ε(ε为所要求的精度)为止。此时f(n x )或f(1n x +)就可近似认为是零。n x 或1n x +就是满足精度的方程的近似根（如图2-1）.

2—1

例1 用增值寻根法求方程 f(x)=32

4x x +-10=0的有根区间。 解 取0x =-4，h=1，则计算结果如下表2-1：

所以f(x)=0的有根区间为(1，2).再取=1，h=0.1，计算结果如表2-2：

所以 f(x)=0 更进一步的有根区间为(1.3，1.4)

2.1.2 二分法

设f(x)在区间［a,b ］上连续，且f(a)·f(b)＜0，则由连续函数性质知，方程f(x)=0在(a ,b)内至少有一实根，为以下讨论方便，设(a,b)内仅有唯一实

根*

x 。

二分法的基本思想 就是逐步对分区间［a,b ］，通过判断两端点函数值乘积的符号，进一步缩小有根区间，将有根区间的长度缩小到充分小，从而求出满足

精度的根*

x 的近似值，如图。 2-2

具体做法 如下 ：

用区间 ［a,b ］的中点12a b x +=

平分区间，并计算f(1x )，同时记(1a ,1b )=(a,b)，

如果恰好有f(1x )=0，则我们已经找到方程的根*

x = 1x 。如若不然，f(1x )≠0，如果f(1a )·f(1x )＜0，则记(2a ,2b )=(1a , 1x ),如果f(1x )· f(1b )＜0，则记

(2a ,2b )=(1x , 1b )，在后两种情形区间(2a 2b ,)为新的有根区 间。它包含在旧的有根区间(1a ,1b )内，其区间长度是原区间的一半。对区间(2a ，2b )施行同样的办法。即平分区间，求中点判断函数值乘积的符号，得到新的有根区间(3

a ,3

b )，它包含在区间(2a 2b ,)内，其区间长度是(2a ,2b )的21，(1a ,1b )的41

。如此重复n 次，如果还没有找到方程的精确根*

x ，此时我们得到方程的有根区间序列： (1a ,1b )，(2a ,2b )，…,(n n b a ,)，… 它满足 (1a ,1b ) ?(,

2b ) ?…?(n n b a ,) … f(n a )f(n b )<0 n b -n a =1

11122---=-n n a

b a b ,n=1,2,… n-1 当n 充分大时，(n n b a ,)的长度缩小到充分小，此时 它的中点n

x 与*

x 夹在n a 与n b 之间，它们的距离也充分小，且序列｛n x ｝满足 ：

n n n n a

b a b x x 22*-=-<

-上式表明 n n x lim ∞→=*x (2) 即 序 列｛n

x ｝以等比数列的收敛速度收敛于*x 。同时也表明序列｛n x ｝是*

x 的一个 近似

值序列。因此对任意给定的精度<0，总存在n ， 使ξ

<-<-n n a

b x x 2*此时,我们可以取n x 作为*

x 的近似值，即可满足 精度 。

例2 用二分法求方程 f(x)=1042

3-+x x =0 在［1，2］内的一个实根，且

要求满足精度 3

*1021

-?<-x x n

迭代11次，近似根 11x =1.364746094即 为所求，其误差

3

1111*1021

000488281.02-?<=-<-a b x x n 这种方法的优点是简单，对 f(x)

只要求连续。它的收敛速度与 比值为21

的等比级数相同，它的局限性是只能用于求实根，不能用于求 复根及偶数重根。

迭代法的基本思想

由函数方程f(x)=0，构造一个等价方程：x=)(x ?(1) 从某个近似根0x 出发，令)(1n n x x ?=+， n=0,1,2，… (2) 可得到序列｛n x ｝，若｛n x ｝收敛，即

lim n x =*x 只要)(x ?连续，有 )

()lim (lim

lim 1n n x x x n n n n ∞

→∞

→+∞

→==??也即

)(**x x ?= 从而可知*x 是方程(1)的根，也就是f(x)=0的根。此时｛n x ｝就是

方程(1)的一个近似解序列，n 越大，n x 的近似程度就越好。若｛n x ｝发散，则迭代 法失败。

例1用迭代法求方程f(x)=2

34x x +-10=0在［1,2 ］内的一个近似根，取初始近似值5.10=x .

解原方程的等价方 程可以有以下不同形式：

(1)1042

3+--=x x x x (2)

x x x 410-=

(3)3

1021x x -= (4)

x x +=410 对应的迭代公式有： (1)

104231+--=+n n n n x x x x (2 ) n n

n x x x 410

1-=

+

(3) 311021n

n x x -=+ (4) n

n x x +=+4101取5.10=x ，列表计算如表2-2。 与

上节二分法比较，(3)、(4)都得到较好的结果 ，而用二分法达到同样的精度，需要迭代27次，同时也看出迭代函数构造不同，收敛速度也不尽相同，迭代函数构造不当(如(1)，(2))，序列｛n x ｝就不收敛。

二 迭代法的几何意义

以上可以看到迭代法可能收敛，也可能不收敛。一般来说从f(x)=0，构造)(x ?不止一种，有的收敛，有的不收敛，这取决于的性)(x ?态。方程x=的)(x ?根，在几何上就是直线 y=x 与曲线y=)(x ?交点的横坐标*

x ,如图2-3所示。

（a ） （b ）

（c ） （d ）

图2-3中(1)、(2)收敛，(3)、(4)发散。 三 迭代法收敛的条件

定义1 如果在根*

x 的某个邻域B=}

|{*δ≤-x x x 0x ∈B ，迭代过程)(1n n x x ?=+，n=0,1,2，…收敛，则 称迭代过程在*x 附近局部收敛。

定理1 设*x =?(*x )，在*

x 的某个邻域B 内)(x ?'连续，并且｜)(x ?'｜≤q<1，

则对任何 0x ∈B ，由迭代公式)(1n n x x ?=+决定的迭代序列｛n x ｝收敛于*

x 。

且｜n x -*x ｜≤0

11x x q q n

--(3)

｜n x -*x ｜≤n

n x x q --+111

(4)

证：由拉格朗日中值定理，存在∈ξB ，使

))(()()(*1*1*x x x x x x n n n -'=-=---ξ??? 由已知 ｜)(ξ?'｜≤q ,从而得

｜n x -*x ｜≤q ｜--1n x *x ｜≤…≤n q ｜0x - *x ｜

所以

=

∞

→n x n lim *x 这样我们就证明了｛n x ｝收敛于 *x 。

再由拉格朗日中值定理，存在 B ∈'ξ ，使

n n x x -+1=)()(1--n n x x ??=)(ξ?''(n n x x -+1)所以 ｜n n x x -+1｜≤q ｜1--n n x x ｜≤…≤q n

｜01x x -｜ (5)

又由于 ｜n p n x x -+｜=｜(1-++-p n p n x x )+(21-+-+-p n p n x x ) +…+(n n x x -+1)｜ ≤｜1-++-p n p n x x ｜+｜21-+-+-p n p n x x ｜+…+｜n n x x -+1｜

所以｜n p n x x -+｜≤(q 1-p +q 2

-p +…+q+1)｜n n x x -+1｜=q q p

--11｜n n x x -+1｜

令p →+∞,有 ｜*

x -n x ｜≤q -11

｜n n x x -+1 ｜

也即｜n x -*

x ｜≤q -11

｜n n x x -+1 ｜ 这样(4)式得证。

再由(5)得｜n x -*

x ｜≤ q q n

-1｜01x x -｜ 这样(3)式也得证。

这个定理是一个很实用的收敛定理。一方面它可以判定我们所构造的迭代函数)(x ?是否收敛。另一方面(3)式还可以估计迭代次数。但结果偏保守，次数也偏大，实际中很少用。通常由(4)式，当 ｜n n x x -+1｜<ξ(ξ为给定精度)时，

认为｜*x -n x ｜<ξ n x 就是*

x 满足精度的一个近似解了。

定理2〖HTSS 〗对于方程 x=)(x ?,如果满足 (1)对任意x ∈［ a,b ］，有)(x ?∈［a,b ］ (2)对任意x ∈［a,b ］，有｜?'(x) ｜≤q<1 则对任意x 0∈ ［a,b ］，

迭代x 1+n =(x n )所决定的序列｛x n ｝收敛于x=?(x)的根x *

，且( 3)、(4)式也都成立。证明与定理1相仿，故略去。以上两定理中的条件要严格验证都较 困

难，实用时常用以下不严格的标准。 有根区间［a,b ］较小，对某一x 0∈［a,b ］,｜ ?'(x 0) ｜明显小于1，由?'(x)连续性知在的x 0某领域内｜?'(x)｜也小于1，则迭 代收敛。

例2 考察例1中四种迭代法在根附近的收敛情况，取根的近 似 值为x 0=5.1。

解 (1) )(x ?1042

3+--=x x x

=')(x ?x x 8312-- ≈')5.1(?17.75>1不收敛

(2) )(x ? x x 410-= =')(x ?)410()410(21221

--?--x x x ≈')5.1(? 5.128>1不收敛〖ZK 〗〗 (3) )(x ? 31021x -= =')(x ?2

1

3

2)10(43---x x

≈')5.1(?0.656<1 收敛

(4) )(x ?

x +=

410

=')(x ?221

)4(1)410(5x x +?+-- ≈')5.1(?0.122<1收敛) 上例说明)(0x ?'值越小，收敛速度就越快。

四 迭代法的收敛速度 用迭代法求方程的近似根，我们不仅要构造适当的)(x ?要求它收敛，而且还需要知道它的收敛速度。关于收敛速度，有如下定义：

定义2 设序列｛x n ｝收敛于*x ，令 ξ= *

x - x n ，若存在某实数p ≥1 及正