第二章 非线性方程求根

本章主要讨论单变量非线性方程：

f(x)0 (2.1)

的求根问题，xR,f(x)C[a,b].

 问题：

（1）“根在哪里”，即确定根所在的区间，进行根的隔离。 （2）“根的求法”，通过数值方法，近似求解，并保证精度要求。

若f(x)C[a,b]且f(a)f(b)0,根据闭区间上连续函数性质可知f(x)0在(a,b)内至少有一个实根，这时称

[a,b]为方程(2.1)的有根区间，通常可通过逐次搜索法求得方程

(2.1)的有根区间。

32 例 求f(x)x11.1x38.8x41.770的有根区间。

解 根据有根区间定义，对f(x)0的根进行搜索计算，结果如下:

x f(x)的符号 0 - 1 - 2 + 3 + 4 - 5 - 6 + 由此可知方程的有根区间为：[1,2],[3,4],[5,6]。

 根的近似求解：将区间[a,b]分成若干小的子区间，由零点定理确定根所在的子区间，并根据精度要求，不断细分直到满足精度要求。最简单的方法就是二分法。

1

§1 二分法

二分法是方程求解的一个简单而可靠的方法。 设f(x)C[a,b]且f(a)f(b)0,根据连续函数性质可

*知f(x)0在(a,b)内至少有一个实根x。

 二分法：考察有根区间a,b]，取中点x0(ab)/2，将它分为两半。假设中点x0不是f(x)的零点，然后进行根的搜索，

*即检查f(x0)与f(a)是否同号，如果同号，说明所求的根x*在x0的右侧，这时令a1x0,b1b;否则x必在x0的左侧，

令a1a,b1x0(如图)。 不管出现哪一种情况，新的有根区间[a1,b1]的长度仅为[a,b]的一半，对压缩了的有限区间

[a1,b1]再分为两半，然后通过根

的搜索判定所求的根在x1的哪一侧，从而又确定一个新的有根区间

[a2,b2]，其长度是[a1,b1]的一半，如此反复二分下去，即可

得出一系列的有根区间：

[a,b][a1,b1][a2,b2][ak,bk]

其中区间每个区间都是前一个区间的一半，因此[ak,bk]的长度：

bkak(ba)/2k当k时趋于零，就是说，如果二分过程无限地继续下去，这些区间最终必收缩于一点x，该点

就是所求的根。

2

*每次二分后，取有根区间[an,bn]的中点xn(anbn)/2作为根的近似值，则在二分过程中可以获得一个近似根的序列

x0,x1,x2,,该序列必以根x*为极限。

*由x[an,bn]，可得

11 xxn(bnan)n1(ba) (2.2)

22只要足够多次(即n充分大)，使得

*1 n1(ba)

2banln/ln2即，就有 

x*xn

这里为预定的精度。

注：在实际计算中，若|f(xn)|很小：|f(xn)|（为给定的误差限），则xn就可作为近似根。 例1 见教材p.14 .

3 例 求方程f(x)xx10在区间[1.0, 1.5]内的一个

实根，要求准确到小数点后的第2位。

*a1.0,b1.5,f(a)0,f(b)0x解 由知(a,b)；

取[a,b]的中点x01.25,将区间二等分，由于f(x0)0，

f(x0)f(b)0，故所求的根x*必在x0右侧，这时应令

a1x01.25, b1b1.5，得x*(a1,b1)；

如此反复二分下去，按误差估计(2.2)式，只要二分6次(n6)，

3

*xx60.005（x6(a6b6)/2）便能达到预定的精度 。

二分法的计算结果如下表：

表 计算结果

k 0 1 2 3 4 5 6 ak 1.0 1.25 1.25 1.3125 1.3125 1.3125 1.3203 bk 1.5 1.5 1.375 1.375 1.3438 1.3281 1.3281 xk 1.25 1.375 1.3125 1.3438 1.3281 1.3203 1.3242 f(xk)符号 - + - + + - -  二分法程序框图见教材图2-2（p.15）。

 二分法的优点是算法简单，且总是收敛的，缺点是事先要确定有根区间，且收敛较慢，且不能用于求复根或偶数重根，故一般不单独将其用于求根，只用其求根的一个较好的近似值。

§2 迭代法

迭代法是一种逐次逼近的方法。

2.1 不动点迭代法（简单迭代法）

将方程(2.1)（即f(x)0）改写成等价的形式： 𝑥

=𝑔(𝑥) (2.3)

4

***∗∗xxf(x)0若满足，则𝑥=𝑔(𝑥)，反之亦然。称

为函数𝑔(𝑥)的一个不动点。

选择一个初始近似值x0，将它代入(2.3)右端，即可求得： 𝑥1

=𝑔(𝑥0)

=𝑔(𝑥𝑘), 𝑘=0,1,2,⋯ (2.4)

可以如此反复迭代计算： 𝑥𝑘+1

称 𝑔(𝑥) 为迭代函数。

如果对x0[a,b]，由(2.4)得到的迭代序列

xk有极限：

limxkx*

k则称迭代法(2.4)收敛，且 𝑥∗

=𝑔(𝑥∗) 为 𝑔(𝑥)的不动点，称(2.4)

为不动点迭代法。若迭代序列发散，则称迭代法发散。  不动点迭代法基本思想：将隐式方程f(x)0化为显式的计算公式 𝑥=𝑔(𝑥)，然后通过迭代，求方程的近似根。  迭代法几何意义：方程𝑥

=𝑔(𝑥)的求根问题在xy平面上

*yx就是要确定曲线 𝑥=𝑔(𝑥) 与直线的交点P。

*x 对于的某个近似值

x0，在曲线𝑦=𝑔(𝑥)上

可确定一点P0，它以x0为横坐标，而纵坐标等于

𝑔(𝑥0)=𝑥1。过P0引平行x轴的直线，设此直线交

5

yx于点Q1，然后过Q1再作平行于y轴的直线，它与曲线

𝑦=𝑔(𝑥)的交点记作P1，则点P1的横坐标为x1，纵坐标则等

于𝑔(𝑥1)线𝑦

=𝑥2。按图7-2中箭头所示的路径继续做下去，在曲

=𝑔(𝑥)上得到点列P1,P2，…，其横坐标分别为由

*P𝑥𝑘+1=𝑔(𝑥𝑘)求得。如果点列k趋向于点P，则相应的迭

*xx代值k收敛到所求的根。

例2 求方程：

fxx3x10

*x1.5x在0附近的根。

解 将上述方程改写成下列形式：

3xx1

据此建立迭代公式

3x1, k0,x1,2, k1k表2-2 计算结果

k 0 1 2 3 4 xk 1.5 1.35721 1.33086 1.32588 1.32494 k 5 6 7 8 xk 1.32476 1.32473 1.32472 1.32472 我们看到，如果仅取6位数字，那么结果x7与x8完全相同，这时可以认为x7实际上已满足方程，即为所求的根。

6

应当指出，迭代法的效果并不是总能令人满意的。譬如，设方程的另一种等价形式：𝑥建立迭代公式 𝑥𝑘+1

3=𝑥𝑘−1

=𝑥3−1

迭代初值仍取 𝑥0

=1.5，则有 𝑥1=2.375,𝑥2=12.39,⋯，

𝑥𝑘 会越来越大，不可能趋于某个极限，这种不收敛的迭代过程

称作是发散的。

上例表明原方程化为(2.3)的形式不同，有的收敛，有的发散，而只有收敛的迭代过程(2.4)才有意义。

例 用迭代法求方程 𝑓(𝑥)的根。

解 方程在x3.5附近有根。构造如下三个迭代函数：

=𝑥−𝑥1/3−2=0

𝑔1(𝑥)=𝑥1/3+2

𝑔2(𝑥)=(𝑥−2)3 𝑔3(𝑥)=

6+2𝑥1/33−𝑥−2/3 下表是初始值x03时，分别用三个迭代函数得到的迭代序列。

表 迭代结果

k 0 1

𝑥𝑘=𝑔1(𝑥𝑘−1) 3 3.4422495703 𝑥𝑘=𝑔2(𝑥𝑘−1) 3 1 𝑥𝑘=𝑔3(𝑥𝑘−1) 3 3.522931 7

2 3 4 5 6 7 8 9 10 11 3.50974493 3.5197243050 3.5211412691 3.5213453678 3.5213747615 3.52137946 3.5213796042 3.5213796920 3.5213797047 3.5213797065 -1 -27 -243 -1.45107e+013 -3.05539e+039 -2.85233e+118 -Inf -Inf -Inf -Inf 3.5213801474 3.5213797068 3.5213797068 可知，𝑔1(𝑥),𝑔3(𝑥) 收敛，但 𝑔3(𝑥) 比 𝑔1(𝑥) 快很多；而𝑔2(𝑥)是发散的。

下面讨论 𝑔(𝑥)不动点的存在性及迭代法(2.4)的收敛性。

2.3 迭代法收敛的充分条件

 压缩映照：在区间[a,b]上定义的函数 𝑔(𝑥)，若存在常数

L, 0L1，使得 x,y[a,b]，都有

|𝑔(𝑥)−𝑔(𝑦)|

≤𝐿|𝑥−𝑦|

则称映照 𝑔(𝑥)在区间[a,b]上是压缩的。

 不动点的存在唯一性及误差分析

定理1 设 𝑔(𝑥)∈𝐶[𝑎,𝑏] 满足以下两个条件： （1）对任意 𝑥∈[𝑎,𝑏]，有 𝑔(𝑥)∈[𝑎,𝑏]；

（2）存在常数L, 0L1，使对任意x,y[a,b]，有

8

|𝑔(𝑥)−𝑔(𝑦)|则

≤𝐿|𝑥−𝑦|

*[a,b]x（1） 𝑥=𝑔(𝑥)在上存在唯一实根;

（2） 对任意初值 𝑥0

∈[𝑎,𝑏]，由 𝑥𝑘+1=𝑔(𝑥𝑘) 得到的

迭代序列xk收剑到 𝑥=𝑔(𝑥) 在[𝑎,𝑏]的唯一实根

x*，并有误差估计： |𝑥−𝑥𝑘|≤

|𝑥∗

∗

11−𝐿𝐿𝑘

|𝑥𝑘+1−𝑥𝑘| (2.5)

−𝑥𝑘|≤1−𝐿|𝑥1−𝑥0| (2.6)

=𝑔(𝑥)−𝑥

证明 先证不动点存在性。定义函数： 𝜑(𝑥)

显然 𝜑(𝑥)∈𝐶[𝑎,𝑏] 。因 𝑎≤𝑔(𝑥)≤𝑏，有

𝜑(𝑎)=𝑔(𝑎)−𝑎≥0， 𝜑(𝑏)=𝑔(𝑏)−𝑏≤0

*xa,b，使 𝜑(𝑥∗)=0，即由连续函数性质可知存在

𝑥∗=

*∗x𝑔(𝑥)，即为 𝑔(𝑥)的不动点。

**xx再证唯一性。设1及2[a,b]是 𝑔(𝑥) 的两个不同的不

动点，则由压缩映射条件2，得

∗∗|∗)∗)∗∗∗∗|𝑥1−𝑥2=|𝑔(𝑥1−𝑔(𝑥2|≤𝐿|𝑥1−𝑥2|<|𝑥1−𝑥2|

矛盾。故 𝑔(𝑥) 的不动点只能是唯一的。

误差估计：由条件（2）得

|𝑥𝑘−𝑥∗|=|𝑔(𝑥𝑘−1)−𝑔(𝑥∗)|≤𝐿|𝑥𝑘−1−𝑥∗|≤⋯≤𝐿𝑘|𝑥0−𝑥∗|

*xx因0L1，故当k时，序列k收剑到。

又

9

|𝑥𝑘+1−𝑥𝑘|=|𝑔(𝑥𝑘)−𝑔(𝑥𝑘−1)|≤𝐿|𝑥𝑘−𝑥𝑘−1|≤𝐿𝑘|𝑥1−𝑥0| 于是，对任意正整数p，有

xkpxkxkpxkp1xkp1xkp2xk1xk (Lkp1Lkp2Lk)|x1x0|Lk |x1x0|1L*limxxkp令p，注意到，即得式(2.6)。

p（|xk1xk||x*xk||x*xk1||x*xk|L|x*xk|(1L)|x*xk|）  注：在实际迭代计算过程中，有时由于L估计的困难性，所以，由（2.5）估计式：

1xk1xk |xxk|1L*知，只要相邻两次计算结果的偏差近似值xk具有足够精度。

xk1xk足够小，即可保证

 由Lagrange中值定理可知，如果 𝑔(𝑥)意x[a,b]，有 |𝑔′(𝑥)|则对x,y[a,b]，有

∈𝐶1[𝑎,𝑏]，且对任

≤𝐿<1

|𝑔(𝑥)−𝑔(𝑦)|=|𝑔′(𝜉)(𝑥−𝑦)|≤𝐿|𝑥−𝑦|,𝜉∈(𝑎,𝑏) 表明定理中的条件（2）可用 𝑔′(𝑥) 的性质代替。 在例2中，

3

fxx3x10

13

2−3当 𝑔(𝑥)=√𝑥+1 时，对任意 𝑥∈[1,2]，有 |𝑔𝑥)|=|(𝑥+1)|≤()≜𝐿≈0.21<1

34

10

′(

11

13又因为1≤√2≤𝑔(𝑥)≤√3≤2，所以迭代法是收敛的。

而当 𝑔(𝑥)=𝑥3−1时，对任意 𝑥∈[1,2]，有

33

|𝑔′(𝑥)|=|3𝑥2|≥3>1,不满足定理条件。

 注：一般情况下，𝐿越小，收敛速度越快。

 局部收敛性

定理1中给出的迭代序列 {𝑥𝑘}对于任何初始值 𝑥0∈[𝑎,𝑏]都收敛，这种收敛性通常称为全局收敛性（整体收敛性）。有时不易检验，实际应用时通常只在不动点 𝑥∗ 的邻近考察其收敛性，即局部收敛性：

𝑔(𝑥)有不动点𝑥∗，如果存在𝑥∗的某个邻域𝑆={𝑥||𝑥−𝑥∗|≤𝛿}，对任意𝑥0∈𝑆，迭代(2.4)产生的序列{𝑥𝑘}∈𝑆，且收敛到 𝑥∗，则称迭代法(2.4)局部收敛。

定理2 设 𝑥∗ 为 𝑔(𝑥)的不动点，𝑔′(𝑥)在 𝑥∗ 的某个邻域连续，且 |𝑔′(𝑥)|<1，则迭代法(2.4)局部收敛。

证明 由连续函数的性质，存在L和 𝑥∗ 的某个领域

𝑆={𝑥||𝑥−𝑥∗|≤𝛿}=[ 𝑥∗−𝛿,𝑥∗+𝛿]，对任意 𝑥∈𝑆，成立：

|𝑔′(𝑥)|≤𝐿<1 又

|𝑔(𝑥)−𝑥∗|=|𝑔(𝑥)−𝑔(𝑥∗)|≤𝐿|𝑥−𝑥∗|≤|𝑥−𝑥∗|

知，对任意 𝑥∈𝑆，总有 𝑔(𝑥)∈𝑆.

于是由定理1知，对任意 𝑥0∈𝑆，迭代序列 {𝑥𝑘}∈𝑆，且收

11

敛到 𝑥∗。

例3 方程 𝑥=𝑒−𝑥 有唯一实根 𝑥∗∈(0,1)，试分析迭代

过程 𝑥𝑘+1=𝑒−𝑥𝑘 （𝑘=0,1,2,⋯)的收敛性。

解 𝑔(𝑥)=𝑒−𝑥,𝑔′(𝑥)=−𝑒−𝑥，对任意 𝑥∈(0,1)，有

|𝑔′(𝑥)|=|𝑒−𝑥|<𝑒0=1

由定理2知，迭代法 𝑥𝑘+1=𝑒−𝑥𝑘 在 𝑥∗ 附近局部收敛，只要取好的初值 𝑥0（充分接近 𝑥∗），则迭代法收敛。

§3 牛顿迭代法与弦割法

牛顿（Newton）迭代法是求解非线性方程（组）的重要方法之一。

3.1 牛顿迭代公式及其几何意义

 牛顿法实质上是一种线性化方法，其基本思想：将非线性方程f(x)0逐步归结为某种线性方程求解。

对于单根和重根，收敛速度不同。 设f(x)可表示成𝑓(𝑥)

=(𝑥−𝑥∗)𝑚𝑞(𝑥)，且𝑞(𝑥∗)≠0，

**则称x为方程f(x)0的m重根，当m1时，称x为方程

f(x)0的单根。

由Taylor公式，得：

*x 设f(x)C[a,b]，则f(x)在内的点具有𝑚重根的充要

m条件是：

f(x*)f(x*)f(m1)(x*)0, f(m)(x*)0

12

 单根情形

1****f(x)C(x,x)f(x)0x设，，即为方程

f(x)0的单根。

设已知方程f(x)0有近似根xk（f(xk)0），将函数

f(x)在点xk展开，有

f(x)f(xk)f(xk)(xxk) 于是方程f(x)0可近似地表示为 f(xk)f(xk)xxk0 记其根为xk1，则xk1的计算公式为： 𝑥𝑘+1

=𝑥𝑘−

𝑓(𝑥𝑘)

,𝑓′(𝑥𝑘)

𝑘=0,1,⋯ (2.8)

——牛顿迭代法

*f(x)0x 牛顿法的几何解释：方程的根可解释为曲线

yf(x)与x轴的交点的横坐标（下图所示）。

*xx 设k是根的某个近似值，过曲线yf(x)上横坐标xk 13

的点Pk引切线，并将该切线与x轴的交点的横坐标xk1作为

x*的新的近似值。注意到切线方程为

yf(xk)f(xk)xxk

这样求得的值xk1就是牛顿法(2.8)的计算结果。所以，牛顿法

亦称切线法。

3.2 牛顿迭代法收敛的充分条件

 牛顿迭代法的收敛性，可直接由定理2得到：

定理3 设 𝑓(𝑥) 在其零点 𝑥∗的某邻域 𝑆={𝑥||𝑥−𝑥∗|≤𝛿}

内有二阶连续导数，且𝑓′(𝑥∗)≠0（即 𝑥∗为单根），则牛顿迭代法在 𝑥∗ 附近具有局部收敛性。

证明 牛顿迭代法的迭代函数为： 𝑔(𝑥)有：𝑔

′(

=𝑥−𝑓′(𝑥) (2.9)

[𝑓′(𝑥)]2−𝑓(𝑥)𝑓′′(𝑥)

[𝑓′(𝑥)]2𝑓(𝑥)

𝑥)=1−

*=

𝑓(𝑥)𝑓′′(𝑥)[𝑓′(𝑥)]2 **f(x)f(x)0, f(x)0， 假定x是的一个单根，即

则由上式知𝑔′(𝑥∗)

=0，于是由定理2得，牛顿迭代法在 𝑥∗ 附

近具有局部收敛性。

定理4 对方程 𝑓(𝑥)=0，若存在区间 [𝑎,𝑏]，使 （1） 𝑓′′(𝑥)在 [𝑎,𝑏]上连续； （2） 𝑓(𝑎)𝑓(𝑏)

<0；

′

（3） 对任意 𝑥∈[𝑎,𝑏]，都有 𝑓(𝑥)（4） 𝑓′′(𝑥)在 [𝑎,𝑏]上保号。

≠0；

14

则当初值 𝑥0根 𝑥∗。

∈[𝑎,𝑏]且𝑓(𝑥0)𝑓′′(𝑥0)>0 时，牛顿迭代法（2.8）

产生的迭代序列 {𝑥𝑘}收敛于方程 𝑓(𝑥)=0在 [𝑎,𝑏]上的唯一实

（几何意义见教材p.24，图2-7） 例4 用牛顿迭代法方程 𝑥确到 |𝑥𝑘+1−𝑥𝑘|<10

−5

−𝑐𝑜𝑠𝑥=0 的实根，要求准

∈[0,𝜋]，

2.

解 方程 𝑥−𝑐𝑜𝑠𝑥=0存在唯一实根 𝑥∗

𝑓(𝑥)=𝑥−𝑐𝑜𝑠𝑥 在 [0,𝜋] 上满足定理4的条件。

2取 𝑥0

=1，有𝑓(𝑥0)𝑓′′(𝑥0)>0，则相应的牛顿迭代法：

𝑥𝑘−𝑐𝑜𝑠𝑥𝑘

𝑥𝑘+1=𝑥𝑘− ,𝑘=0,1,⋯

1+𝑠𝑖𝑛𝑥𝑘

表2-3

收敛，计算可得 𝑥4=0.739085 满足精度要求，参见表2-3.

𝑥𝑘 1 0.7503 0.739113 𝑘 0 1 2 𝑘 3 4 𝑥𝑘 0.739086 0.739085  牛顿迭代法的计算步骤：

（1）选定初始近似值x0，计算f0f(x0)，f0'f(x0) （2）迭代。按公式：

x1x0f0/f0

f(x1)。

迭代一次，得新的近似值x1，计算f1f(x1)，f1（3）控制。如果x1满足||1或|f1|2，则终止迭代，以x1作为所求的根；否则转（4）。此处1，2是允许误差，而

15

|x1x0| , 当 |x1|C 时|x1x0|

|x|, 当 |x1|C 时1其中C是取绝对误差或相对误差的控制常数，一般可取C=1。

（4）修正。如果迭代次数达到预先指定的次数

N，或者

f0，则方法失败；否则以x1,f1,f1代替x0,f0,f0转

（2）继续迭代。

注：牛顿法的优点是收敛快，缺点一是每步迭代要计算

f(xk)及f(xk)，计算量较大且有时f(xk)计算较困难，缺点

二是初始近似x0只在根x附近才能保证收敛，如x0给的不

*合适可能不收敛。为克服这两个缺点，通常可用下述方法。

（1）简化牛顿法，也称平行弦法，其迭代公式为：

xk1xkCf(xk), C0, k0,1, 迭代函数为： 𝑔(𝑥)

=𝑥−𝐶𝑓(𝑥)。

=|1−𝐶𝑓(𝑥)|<1，即取0Cf(x)2，

1

′

若 |𝑔′(𝑥)|

*x在根附近成立，则迭代法局部收

敛。若取𝐶

=𝑓′(𝑥)，则称为简化

0

牛顿法，其几何意义是用平行弦与

x轴交点作为x*的近似。

16

（2）牛顿下山法。牛顿法收敛性依赖初值x0的选取。如

*x果0偏离所求根x较远，则牛顿法可能发散。例如，用牛顿法

求解方程：

xx10

3*x 此方程在x1.5附近的一个根。取迭代初值x01.5，

用牛顿法公式

计算得： x1xk13xkxk1xk23xk1

1.34783, x21.32520, x31.32472

迭代3次得到的结果x3有6位有效数字。 但是，如果改用x0迭代一次得x1*0.6作为迭代初值，则依牛顿法公式

17.9，这个结果反而比x00.6更偏离了所求

的根x1.32472。

 为了防止迭代发散，对迭代过程附加一项要求，即具有单调性：

|f(xk1)||f(xk)| 满足这项要求的算法称下山法。

将牛顿法与下山法结合起来使用，即在下山法保证函数值稳定下降的前提下，用牛顿法加快收敛速度。  牛顿下山法：将牛顿法的计算结果： 𝑥̅𝑘+1

=𝑥𝑘−𝑓′(𝑥)

𝑘

17

𝑓(𝑥𝑘)

与前一步的近似值 𝑥𝑘适当加权平均作为新的改进值： 𝑥𝑘+1

=𝜆𝑥̅𝑘+1+(1−𝜆)𝑥𝑘=𝑥𝑘−𝜆𝑓′(𝑥) 𝑘

𝑓(𝑥𝑘)

选择下山因子 𝜆 时从 𝜆=1 开始，逐次将 𝜆 减半进行试算，直到能使下降条件满足为止。

若用此法解上述方程，当x00.6时，由牛顿迭代法求得

x117.9，它不满足条件下降条件，通过逐次取半进行试算，

1当时可求得x11.140625。此时f(x1)0.6563，

32而f(x0)1.384，显然|f(x1)||f(x0)|。由x1计算x2，x3时1，均能使下降条件成立。计算结果如下：

x21.36181, f(x2)0.1866

x31.32628, f(x3)0.00667

x41.32472, f(x4)0.0000086

x4即为x*的近似。一般情况只要能使下降条件成立，则可得到

limf(xk)0，从而使xk收敛。

k

3.3 弦割法（割线法）

 建立在插值原理基础上，利用已求函数f(xk),f(xk1),来

回避导数值f(xk)的计算。

设xk,xk1是f(x)0的近似根，利用f(xk),f(xk1)构造一次插值多项式p1(x)，并用p1(x)0的根作为f(x)0的新

18

的近似根xk1。由

f(xk)f(xk1)(xxk) p1(x)f(xk)xkxk1因此有（令p1(xk1)0）：

f(xk) xk1xkf(x)f(x)(xkxk1) 𝑘=1,2,⋯ (2.10)

kk1，

—— 弦割法（割线法，Secant method） 弦割法：牛顿法𝑥𝑘+1

=𝑥𝑘−

𝑓(𝑥𝑘)

中的导数′()𝑓𝑥𝑘

f(xk)用

f(xk)f(xk1)差商取代的结果。 xkxk1 弦割法的几何意义：

如图所示，曲线yf(x)上 横坐标 𝑥𝑘、𝑥𝑘−1的点分别记为Pk、

Pk1，则弦线PkPk1的斜率等差商

值

𝑓(𝑥𝑘)−𝑓(𝑥𝑘−1)𝑥𝑘−𝑥𝑘−1

( =𝑓′(𝜉) )，其方程是：

f(xk)f(xk1)(xxk) yf(xk)xkxk1因此，按(2.10)求得的xk1实际上是弦线PkPk1与x轴交点的横坐标。因此称这种算法为弦割法。

弦割法与牛顿法都是线性化方法，但两者有本质的区别。牛顿法在计算 𝑥𝑘+1时只用到前一步的值 𝑥𝑘，而弦割法在求 𝑥𝑘+1

19

时要用到前面两步的结果 𝑥𝑘、𝑥𝑘−1，因此使用这种方法给出两个开始值 𝑥0、𝑥1。弦割法避免了求导数，但收敛速度不如牛顿法。

例5 用弦割法求方程 𝑓(𝑥)=𝑥3−𝑥−1=0在区间[1,1.5]内的一个根。 （参见教材p.26） 例 用弦割法解方程

fxxe10

x x10.6作为开始值，解 设x00.5 、用弦割法求得的结

果见下表，比较上例牛顿法的计算结果可以看出，弦割法的收敛速度也是相当快的。

𝑘 0 1 2

𝑥𝑘 0.5 0.6 0.56532 𝑘 3 4 𝑥𝑘 0.56709 0.56714 §4 非线性方程组牛顿迭代法求根

非线性方程组牛顿迭代法设计思想：单个方程的推广，即先线性化，然后求解。

考虑方程组

f1x1,,xn0 fnx1,xn0

(*)

20

其中f1,f2,,fn均为(x1,,xn)的多元函数。若用向量记号记

Xx1,,xnRn，F(f1,,fn)T，可以写成

T

F(X)0

当n2，且fi(i1,,n)中至少有一个是自变量

xi(i1,,n)的非线性函数时，则称方程组为非线性方程组。

非线性方程组求根问题是非线性方程（即n1）求根的直接推广，实际上只要把单变量函数f(x)看成函数F(X)，则

可将单变量方程求根方法推广到方程组(*)。

kkkTX(x,,x若已给出方程(*)的一个近似根1n)，将

(k)函数F(X)的分量fi(x) (i1,,n)在X用多元函数泰勒

展开，并取线性部分，则可表示为

(k)(k)(k)F(X)F(X)F(X)(XX)

令上式右端为零，得到线性方程组

(k)(k)(k)F(X)(XX)F(X) （**）

其中F(X)为f1,f2,,fn的nn阶的雅可比（Jacobi）矩阵：

f1f1x x 21f2f2(f1,f2,,fn) F(X)x1x2(x1,x2,,xn)  

fn fn x1x2(k1)X求解线性方程组（**），并记解为，则得

f1xnf2xn fnxn21

(k1)(k)(k)1(k)XXF(X)F(X), k0,1, (***)

——解非线性方程组(**)的牛顿迭代法。 二元非线性方程组的情况见教材p.27。

定理5 设 𝐹(𝑋)的定义域 𝐷⊂𝑅𝑛, 𝑋∗∈𝐷满足 𝐹(𝑋∗)=0，在 𝑋∗的开邻域 𝑆0⊂𝐷上 𝐹′(𝑋)存在且连续，𝐹′(𝑋∗)非奇异，则牛顿法生成的序列 {𝑋(𝑘)}在闭域 𝑆⊂𝑆0上超线性收敛于 𝑋∗，若还存在常数 𝐿>0，使 ‖𝐹′(𝑋)−𝐹′(𝑋∗)‖≤𝐿∙‖𝑋−𝑋∗‖,∀𝑋∈𝑆，则{𝑋(𝑘)} 至少平方收敛。 例 求解方程组

f1x1,x2 x1 2x230 fx,x2x2 x250

12212(0)Tx(1.5, 1.0)给定初值，用牛顿法求解。

解 先求雅可比矩阵

14x F(X)1211F(X)，2x22x28x122x24x11由牛顿法(***)，得

X(k1)X(k)1(k)(k)2x28x12x2(k) 2x1(k)2x2(k)3(k)(k)2(k)214x12(x1)(x2)5(k)(k)(k)(k)(k1)x1x22(x1)23x25(k)x1x1(k)(k)x24x1(k)2(k)2(k)(k)(k)即 (k1)(x)2(x)4xx12x5 (k)21121x2(k)(k)x22x8x21 22

(0)T由x(1.5, 1.0)，逐次迭代得到

Tx1.488095, 0.755952

Tx(3)1.488034, 0.755983 (2)

§5 迭代法的收敛阶与加速收敛方法

先看一个例子。

*2x3。 x30 例 用不同方法求方程的根2f(x)x3，可改写为各种不同的等价形式 解 方程

𝑥=𝑔(𝑥) ，其不动点为x （1）xk12*3。构造不同的迭代法如下：

xkxk3， 𝑔1(𝑥)=𝑥2+𝑥−3，

33xk，𝑔2(𝑥)=𝑥

′(∗)=−𝑥2,𝑔2𝑥=−1

3

′()′(∗)′

𝑔1𝑥=2𝑥+1,𝑔1𝑥=𝑔1(√3)=2√3+1>1

（2）

xk1′() 𝑔2𝑥

（3）xk1′() 𝑔3𝑥

12xkxk3，𝑔(𝑥)=𝑥−1(𝑥2−3)， 344

=1−2𝑥,

1

′(∗)𝑔3𝑥

=1−

√32

≈0.314<1

（4）

xk11313xk，𝑔4(𝑥)=(𝑥+)， 2x2𝑥k′(∗)′=2(1−𝑥2),𝑔4𝑥=𝑔4(√3)=0 1

3

′() 𝑔4𝑥

取 𝑥0=2，对上述4种迭代法，计算三步所得的结果如下表：

23

表 计算结果

𝑘 𝑥𝑘 迭代法(1) 迭代法(2) 迭代法(3) 迭代法(4) 0 𝑥0 1 𝑥1 2 𝑥2 3 𝑥3   2 3 9 87  2 1.5 2 1.5  2 1.75 1.734475 1.732361  2 1.75 1.732143 1.732051  注意到：31.7320508，从计算结果看到迭代法(1)及(2)均不收敛，且它们均不满足定理2中的局部收敛条件；迭代法(3)和(4)均满足局部收敛条件，且迭代法(4)比(3)收敛快，其中在

′(∗)迭代法(4)中𝑔4𝑥

=0。为了衡量迭代法(2.4)收敛速度的快慢

=𝑔(𝑥𝑘) 收敛于方程 𝑥=𝑔(𝑥) 的

给出以下定义。

定义 设迭代法 𝑥𝑘+1

根 𝑥∗，若存在常数 𝑝 (𝑝≥1) 和 𝑐 (𝑐>0) ，使得

lim𝑘→∞

|𝑥∗−𝑥𝑘+1||𝑥∗−𝑥

𝑘

|𝑝=𝑐

则称该迭代过程是 𝒑阶收敛的。特别地，𝒑=𝟏（𝟎<𝒄<𝟏）时称线性收敛，𝒑>𝟏时称超线性收敛，𝒑=𝟐时称平方收敛。  迭代法的收敛速度依赖于迭代函数 𝑔(𝑥) 的选取

定理6 设 𝑥∗ 是方程 𝑥=𝑔(𝑥) 的根，

𝑔(𝑥),𝑔′(𝑥),⋯,𝑔(𝑝)(𝑥) 在 𝑥∗ 的邻近连续，且

𝑔′(𝑥∗)=𝑔′′(𝑥∗)=⋯=𝑔(𝑝−1)(𝑥∗)=0, 𝑔(𝑝)(𝑥∗)≠0

则迭代法 𝑥𝑘+1

′

=𝑔(𝑥𝑘) 在 𝑥∗邻近是 𝒑阶收敛的。特别地

当 0<|𝑔(𝑥∗)|<1 时，迭代法是线性收敛的 ；

24

当 𝑔′(𝑥∗)=0, 𝑔′′(𝑥∗)≠0 时，迭代法是平方收敛的。 证明 由 𝑔′(𝑥∗)=0，根据定理2，可知迭代法 𝑥𝑘+1

=

𝑔(𝑥𝑘)具有局部收敛性。

将 𝑔(𝑥𝑘) 在根 𝑥∗处泰勒展开，则有 𝑔(𝑥𝑘)=𝑔(𝑥

∗)

𝑔(𝑝)(𝜉)𝑝!

+

(𝑥𝑘−𝑥∗)𝑝 (在xk与x之间)

* 注意到 𝑔(𝑥𝑘)=𝑥𝑘+1, 𝑥𝑘+1−𝑥∗=

𝑔(𝑝)(𝜉)𝑝!

𝑔(𝑥∗)=𝑥∗，由上式得

𝑔(𝑝)(𝑥∗)

𝑝!

(𝑥𝑘−𝑥∗)𝑝→(𝑥𝑘−𝑥∗)𝑝

即迭代过程 𝑥𝑘+1

=𝑔(𝑥𝑘) 在 𝑥∗ 邻近是 𝒑阶收敛的。

 注：在上例中，迭代法（3）中的𝑔′(𝑥∗)≠0，故它只是线性收敛，而迭代法（4）（牛顿迭代法）中的𝑔′(𝑥∗)=0，

𝑔𝑥

′′(∗)

=

2√3≠0，由定理6知 𝒑=𝟐，即该迭代法是2阶收

敛的。

又在前例中，𝑔1(𝑥)=𝑥

′()𝑔1𝑥=

′′()𝑔3𝑥=2

fxxx20

+2，𝑔2(𝑥)=(𝑥−2)，𝑔3(𝑥)=

′() ，𝑔3𝑥=𝑥1/3(3𝑥2/3−1)2 22(𝑥−𝑥1/3−2)

3

131/3

6+2𝑥1/33−𝑥−2/3 13√𝑥3221

𝑥1/3(3𝑥2/3−1)(1−3𝑥−2/3)−(𝑥−𝑥1/3−2)(𝑥1/3(3𝑥2/3−1))′

𝑥2/3(3𝑥2/3−1)4 *′(∗)x3.52，故 0<𝑔′1(𝑥∗)<1，𝑔3𝑥=0,𝑔′′(𝑥∗)≠0，其中

知以 𝑔1(𝑥)为迭代函数的迭代法是线性收敛的，以 𝑔3(𝑥)为迭代函数的迭代法（牛顿迭代法）是平方收敛的。而

′(∗)𝑔2𝑥=3|𝑥∗−2|2≈6.9312>1，是发散的。

25

例6 分析简单迭代法与牛顿迭代法的收敛速度。 解 简单迭代法：

由：𝑥∗−𝑥𝑘+1=𝑔(𝑥∗)−𝑔(𝑥𝑘)=𝑔′(𝜁𝑘)(𝑥∗−𝑥𝑘)

得：

|𝑥∗−𝑥𝑘+1|′()|′(∗)|lim=lim𝑔𝜁=|𝑔𝑥| 𝑘∗𝑘→∞|𝑥−𝑥𝑘|𝑘→∞

所以，当 𝟎<|𝒈′(𝒙∗)|<𝟏 时，简单迭代法线性收敛。 牛顿迭代法：（1）单根情形：

由 𝑔(𝑥)

=𝑥−𝑓′(𝑥)， 知：

𝑓(𝑥)

′()]2′′()′′()[()()𝑓𝑥−𝑓𝑥𝑓𝑥𝑓𝑥𝑓𝑥′()𝑔𝑥=1−= ′2′2[𝑓(𝑥)][𝑓(𝑥)]***f(x)f(x)0, f(x)0，则由x 是的一个单根，即

上式知

𝑔𝑥

′(∗)

=0，𝑔𝑥

′′(∗)

=

𝑓′′(𝑥∗)𝑓′(𝑥∗)

*x于是由定理6得，牛顿迭代法在零点的邻近是平方收敛的。

lim𝑘→∞

𝑥𝑘+1−𝑥∗(𝑥𝑘−𝑥∗)2=

𝑔′′(𝑥∗)2!

=

𝑓′′(𝑥∗)2𝑓′(𝑥∗)

（2）重根情形： 设𝑓(𝑥)

=(𝑥−𝑥∗)𝑚𝑞(𝑥)，整数m2，𝑞(𝑥∗)≠0，

𝑓(𝑥)

*则x为方程f(x)0的m重根，只要f(xk)0仍可用牛顿

迭代法计算，此时迭代函数𝑔(𝑥)

=𝑥−𝑓′(𝑥)的导数为：

26

𝑔𝑥

′(∗)

=

𝑓(𝑥)𝑓′′(𝑥)[𝑓′(𝑥)]2|

𝑥=𝑥∗

=1−𝑚≠0, |𝑔′(𝑥∗)|<1

1

**f(x)xx所以，当为𝑓(𝑥)=0的𝑚 (𝑚≥2)重零点，在其零点

的某邻域内有二阶连续导数，则牛顿法局部线性收敛。

为使迭代法仍保持二次收敛，须对牛顿迭代法进行修正。  若已知重根数m：取𝑔(𝑥)=𝑥−𝑚则迭代法：

𝑓(𝑥)𝑓′(𝑥)

，可得：𝑔′(𝑥∗)=0，

mf(xk) xk1xkf(x), k0,1,

k是局部二次收敛的。  若重根数m未知：

令𝐹(𝑥)

=𝑓′(𝑥)

𝑓(𝑥)

*x，若是f(x)0的m重根，则

𝐹(𝑥)

*=𝑚𝑞(𝑥)+(𝑥−𝑥∗)𝑞′(𝑥) 𝐹(𝑥)

𝐹′(𝑥)

𝑓(𝑥)𝑓′(𝑥)

(𝑥−𝑥∗)𝑞(𝑥)

得x是 𝐹(𝑥)=0的单根，对它用牛顿法，其迭代函数为： 𝑔(𝑥)

=𝑥−

=𝑥−[𝑓′(𝑥)]2−𝑓(𝑥)𝑓′′(𝑥)

从而可构造迭代法

f(xk)f(xk) xk1xk[f(x)]2f(x)f(x), k0,1,

kkk是二阶收敛的。

*42x2是二重根，用上x4x40 例 方程的根

述三种方法求根。

27

解 先求出三种方法的迭代公式： （1）牛顿迭代法：

xk12xk2xk4xk 2xk2xk2xk

（2）重根数已知： xk12xk2 （3）重根数未知： xk1xk2xk2

取初值x01.5，计算结果如下表。

表 三种方法数值结果

k 1 2 3 xk x1 x2 x3 方法（1） 1.458333333 1.436607143 1.425497619 方法（2） 1.416666667 1.412156860 1.414213562 方法（3） 1.4117706 1.414211380 1.414213562 计算三步，方法（2）及（3）均达到10位有效数字，而牛顿法（1）只有线性收敛，要达到同样精度需迭代30次。

 迭代加速方法

1. 艾特肯（Aitken）加速方法

*x对于收敛于的不动点迭代算法 𝑥𝑘+1=𝑔(𝑥𝑘) *xx 设k是根的某个近似值，用迭代公式校正一次得

𝑥𝑘+1

=𝑔(𝑥𝑘)

由微分中值定理，有

𝑥𝑘+1−𝑥∗=𝑔(𝑥𝑘)−𝑔(𝑥∗)=𝑔′(𝜁)(𝑥𝑘−𝑥∗)

28

*xx其中𝜁介于k与之间。

假定𝑔′(𝑥)改变不大，近似地取某个近似值L，则有

**xxLxx k1k （*） ，将它与（*）式联立，

若将校正值𝑥𝑘+1 𝑥𝑘+2

=𝑔(𝑥𝑘)，再校正一次，又得

=𝑔(𝑥𝑘+1)

**xxLxx 由于 k2k1消去未知的L，有

𝑥∗−𝑥𝑘+1𝑥∗−𝑥

𝑘

≈

𝑥∗−𝑥𝑘+2𝑥∗−𝑥𝑘+1

2 （2.11）

由此推知

2xxx(xx)*kk2k1k1kxxk xk22xk1xkxk22xk1xk

在计算了xk1及xk2之后，可用上式右端作为x的新近似。记

* 𝑥̃𝑘

=𝑥𝑘−𝑥

(𝑥𝑘+1−𝑥𝑘)2

𝑘+2−2𝑥𝑘+1+𝑥𝑘

（**）

式(**)称为艾特肯(Aitken)加速方法。 2. 斯蒂芬森（Steffensen）方法

把艾特肯加速技巧与不动点迭代结合，可得如下的迭代法：

𝑥𝑘+1{

𝑦𝑘=𝑔(𝑥𝑘)𝑧𝑘=𝑔(𝑦𝑘)

(𝑦𝑘−𝑥𝑘)

=𝑥𝑘−𝑧−2𝑦+𝑥𝑘𝑘𝑘

2 (𝑘

=0,1,2,⋯) (2.12)

——斯蒂芬森（Steffensen）迭代法

（教材上称为艾特肯算法 ）

29

 注：(2.12)是将不动点迭代法计算两步合并成一步得到的，可将它写成另一种不动点迭代 𝑥𝑘+1其中 𝑔(𝑥)

=𝑔(𝑥𝑘) (𝑘=0,1,2,⋯) =𝑥−

(𝑔(𝑥)−𝑥)2

𝑔(𝑔(𝑥))−2𝑔(𝑥)+𝑥

3f(x)xx10。 例 用斯蒂芬森方法求解方程

解 前面已经指出迭代 （2.12）计算，取𝑔(𝑥)

𝑘 0 1 2 3 4 5 xk1x1是发散的，现用

3k=𝑥3−1，计算结果如下表。 𝑥𝑘 𝑦𝑘 𝑧𝑘 2.37500 1.84092 1.49140 1.34710 1.32518 12.3965 5.23888 2.31728 1.44435 1.32714 1.5 1.41629 1.35565 1.325 1.32480 1.32472 计算表明：它是收敛的，这说明即使迭代法 𝑥𝑘+1=𝑔(𝑥𝑘)不收

敛，用斯蒂芬森迭代法(2.12)仍可能收敛。若 𝒙𝒌+𝟏=𝒈(𝒙𝒌)线性收敛，则艾特肯算法(2.12)达到2阶收敛。更进一步还可知若

𝒙𝒌+𝟏=𝒈(𝒙𝒌)为p阶收敛，则(2.12)为p1阶收敛。

例 求方程3xe0的[3,4]中的解。 解 由方程得e 𝑥

2xx3x2,两边取对数得：

=𝑙𝑛3𝑥2=2𝑙𝑛𝑥+𝑙𝑛3≜𝑔(𝑥)

30

构造迭代法： xk1 由于𝑔

′(

2lnxkln3

2

𝑥)=𝑥,max3≤𝑥≤4|𝑔′(𝑥)|<1，当x[3,4]，

可知此迭代法是收敛的。若取x03.5，迭代16次，得：

x163.73307，有六位有效数字。

若用斯蒂芬森迭代法(2.12)进行加速，计算结果如下表所示： 𝑘 0 1 2 𝑥𝑘 3.5 3.73444 3.73307 𝑦𝑘 3.60414 3.73381 𝑧𝑘 3.66202 3.73347 这里计算2步（相当于一般迭代法的4步）结果与x16相同，说明用艾特肯算法(2.12)的收敛速度比一般迭代法快得多。

例7 用迭代法求方程𝑓(𝑥)

=𝑥−2−𝑥=0在[0,1]内根

𝑥∗的近似值，精确到 |𝑥𝑘+1−𝑥𝑘|<10−4.

（见教材p.30）

31