数值分析第三章 非线性方程的数值解法数学与统计学院简介（ Introduction）
我们知道在实际应用中有许多非线性方程的例子，例如
（ 1）在光的衍射理论（ the theory of
diffraction of light)中,我们需要求 x-tanx=0的根
（ 2）在行星轨道（ planetary orbits） 的计算中,对任意的 a和 b,我们需要求 x-asinx=b的根
（ 3） 在数学中，需要求 n次多项式 xn + a1 xn-
1+...+an-1 x + an＝ 0的根求 f(x)=0的根
§ 3.1 对分区间法
(Bisection Method )
原理,若 f(x)?C[a,b],且 f (a) · f (b) <
0,则 f(x) 在 (a,b) 上必有一根。
a
b
x1
x2
a1
b
x*
1
2
停机条件（ termination condition ）,
11 εxx kk 2)( εxf?或误差 分析：
第 1步产生的
21
bax 有误差
21
abx*||x
第 k 步产生的 xk 有误差
kk
abx*||x
2
对于给定的精度?,可估计二分法所需的步数 k,
2ln
lnln
2
εabkεab
k
例 1 用二分法求在 (1,2)内的根，要求绝对误差不超过解,
f(1)=-5<0 有根区间 中点
f(2)=14>0 -(1,2)+
f(1.25)<0 (1.25,1.5)
f(1.375)>0 (1.25,1.375)
f(1.313)<0 (1.313,1.375)
f(1.344)<0 (1.344,1.375)
f(1.360)<0 (1.360,1.375)
f(1.368)>0 (1.360,1.368)
0104 23 xx
210
2
1
f(1.5)>0 (1,1.5)
nx
1,51?x
3 6 4.1
3 6 8.1
3 6 0.1
3 4 4.1
3 1 3.1
3 7 5.1
25.1
8
7
6
5
4
3
2
x
x
x
x
x
x
x
12
例 2，求方程 f(x)= x 3 –e-x =0的一个实 根 。
因为 f(0)<0,f(1)>0。 故 f(x)在 (0,1)内有根用二分法解之,(a,b） =（ 0,1)’计算结果如表：
k a bk xk f(xk)符号
0 0 1 0.5000 －
1 0.5000 － 0.7500 －
2 0.7500 － 0.8750 ＋
3 － 0.8750 0.8125 ＋
4 － 0.8125 0.7812 ＋
5 － 0.7812 0.7656 －
6 0.7656 － 0.7734 ＋
7 － 0.7734 0.7695 －
8 0.7695 － 0.7714 －
9 0.7714 － 0.7724 －
10 0.7724 － 0.7729 ＋
取 x10=0.7729,误差为 | x* -x10|<=1/211 。
Remark1,求奇数个根
Find solutions to the equation
on the intervals [0,4],Use the bisection
method to compute a solution with an
accuracy of 10－ 7,Determine the number
of iterations to use.,
[0,1],[1.5,2.5] and [3,4]，
利用前面的公式可计算迭代次数为 k=23,
Remark2:要区别根与奇异点
Consider f(x) = tan(x) on the interval
(0,3).Use the 20 iterations of the
bisection method and see what happens.
Explain the results that you obtained.
（ 如下图）
Remark3:二分发不能用来求重根
f (x) = 0 x = g (x)
等价变换
f (x) 的根 g (x) 的不动点
§ 3.2 单个方程的迭代法
f(x)=0化为等价方程
x=g(x)的方式是不唯一的,有的收敛,有的发散
For example,2x3-x-1=0
321xx(1) 如果将原方程化为等价方程由此可见，这种迭代格式是发散的取初值
00?x
3102 1 1xx
3212 1 3xx
3322 1 55xx
31 21kkxx则 迭 代 格 式 为,
3 2 1 xx
(2) 如果将原方程化为等价方程
00?x
2
103
1
xx 3
2
1? 7937.0?
3 12 2 1 xx 3 2
7937.1? 9644.0?
仍取初值依此类推,得
x3 = 0.9940
x4 = 0.9990
x5 = 0.9998
x6 = 1.0000
x7 = 1.0000
已经收敛,故原方程的解为 x = 1.0000
同样的方程
不同的迭代格式有不同的结果什么形式的迭代法能够收敛呢?
收敛性分析定义 2 若存在常数?(0≤?<1),使得对一切 x1,x2∈ ［ a,b］,
|g(x1)-g(x2)|≤? |x1-x2|,(5)
则称 g(x)是［ a,b］ 上的一个压缩映射,
称为压缩系数考虑方程 x = g(x),g(x)?C[a,b],若
( I ) 当 x?[a,b] 时,g(x)?[a,b]；
( II )在［ a,b］ 上成立不等式,|g(x1)-g(x2)|≤? |x1-x2| 。
则（ 1） g在［ a,b］ 上存在惟一不动点 x*
（ 2）任取 x0?[a,b],由 xk+1 = g(xk) 得到的序列 {xk}（?［ a,b】）
收敛于 x*。
（ 3） k次迭代所得到的近似不动点 xk与精确不动点 x*有 有误差估计式：
定理 3.2.1
*
11k k kx x x x
*
101
k
kx x x x
§ 3 Fixed-Point Iteration
证明,① g(x) 在 [a,b]上存在不动点？
② 不动点唯一？
③ 当 k时,xk 收敛到 x*？
|x*-x′|=|g(x *)-g(x′)|≤? |x*-x′|,
因 0≤?<1，故必有 x′=x *
若有 x′∈ ［ a,b］,满足 g(x′)=x′,
|xk-x*|=|g(xk-1)-g(x*)|≤? |x k-1-x*|
≤?2|xk-2-x*| ≤ … ≤?k|x0-x*|?0,
令 G(x)=g(x)-x,x∈ ［ a,b］,由条件①知
G(a)=g(a)-a≥0,G(b)=g(b) -b≤0.
由条件②知 G(x)在［ a,b］ 上连续，又由介值定理知存在 x*∈ ［ a,b］,使 G(x*)=0,即 x*=g(x*).
§ 3 Fixed-Point Iteration
可用 来控制收敛精度
|| 1 kk xx
越小，收敛越快
(4) |xk-x*|=|g(xk-1)-g(x*)|≤? |x k-1-x*|
≤? （ |xk-xk-1|+|xk-x*|）,
故有 |xk-x*| ≤?/(1-?)|xk-xk-1|.
这就证明了估计式 (6),
(5) |xk-xk-1| = |g(xk-1)-g(xk-2)|
≤? |x k-1-xk-2|≤ … ≤? k-1|x1-x0|
联系估计式 (6)
|xk-x*| ≤?k-1/(1-?)|x1-x0|.
即估计式 (7)成立
Remark：
定理条件非必要条件，而且定理 3.2.1中的压缩条件不好验证，一般来讲,
若知道迭代函数 g(x)∈C 1『 a,b］,并且满足 |g′(x)|≤? ≤1,对任意的 x∈ ［ a,b］,
则 g（ x)是［ a,b］ 上的压缩映射例题
已知方程 2x-7-lgx＝ 0,求方程的含根区间，考查用迭代法解此方程的收敛性。
在这里我们考查在区间 [3.5,4]的迭代法的收敛性
很容易验证,f(3.5)<0,f(4)>0
将方程变形成等价形式,x＝ (lgx+7)/2
( l g ( ) 7 )
11
()
2 l n 1 0
x
gx
x
1
g(x)=
2
3,5 4m a x | ( ) | 0,0 6 3 1x gx
由定理 3.2.1知，迭代格式 xk+1＝ (lgxk+7)/2
在 [3.5,4]内收敛局部收敛性定理定理 3.2.2 设 x*为 g的不动点,g(x)与 g′(x)
在包含 x*的某邻域 U(x*) (即开区间 )内连续，
且 |g′(x *)|<1,则存在?>0，当 x0∈ ［ x* -
,x*+?］ 时，迭代法 (3)产生的序列
{xk}? ［ x* -?,x*+?］ 且收敛于 x*.
证明略（作为练习） We don’t know x*,how do we
estimate the
inequality？
举例用一般迭代法求 x3-x-1=0的正实根 x*
3x = x + 1将 方 程 改 写 成,
3x) = x+ 1则 迭 代 函 数 为,g(
2
3
1x ) =
3 x + 1
g(
（ ）
容易得到,g′(x) 在包含 x*的某邻域 U(x*) 内连续，且 |g′(x *)|<1
*3
kx = x + 1 xk+1因 此 迭 代 格 式 在 附 件 收 敛例题用一般迭代法求方程 x-lnx＝ 2在区间（ 2,?）
内的根，要求 |xk-xk-1|/|xk|<=10-8
解：令 f(x)=x-lnx-2
f(2)<0,f(4)>0,故方程在（ 2,4）内至少有一个根
1f ( x ) = 1 0,2
x x又 － （,）
f ( x ) = 0 2,
2
*
*
因 此 方 程 在 （,） 内 仅 有 一 个 根 x
且 x （,）
将方程化为等价方程,x＝ 2＋ lnx
1g ( x ) 2 l n x ( x ) |= | | 0,5 1,2 4
x
x＝ ＋,|g （,）
因此,? x0?（ 2,?）,xk+1＝ 2＋ lnxk产生的序列? xk?收敛于 X*
取初值 x0＝ 3.0,计算结果如下：
7 3.146143611
8 3.146177452
9 3.146188209
10 3.146191628
11 3.146192714
12 3.146193060
13 3.146193169
14 3.146193204
k xi
0 3.000000000
1 3.098612289
2 3.130954362
3 3.141337866
4 3.144648781
5 3.145702209
6 3.146037143
另一种迭代格式：
1
( 1 l n )
1
kk
k
k
xx
x
x?
0 3.000000000
1 3.147918433
2 3.146193441
3 3.146193221
程序演示由此可见，对同一个非线性方程的迭代格式，在收敛的情形下，有的收敛快，有的收敛慢。
定义 1.,设 序列 {xk}收敛于 x*,若存在 p≥ 1和正数 c，
使得成立则称 {xk}为 p 阶收敛的特别,
p = 1,要求 c<1,称线性收敛 ;
1<p<2,称超线性收敛
p=2,称平方收敛。
*
1
*
l i m
k
pk
k
xx
C
xx
迭代法的收敛阶 (收敛速度 )
定理 3.2.3
设 x*为 g的不动点,p≥2 为正整数,g在 x*的某邻域Ｕ (x*)内 p阶连续可微，且
g′( x*)=g″( x*)=… =g (p-1)(x*)=0,而
g(p)(x*)≠0,
则存在?>0，当 x0∈ ［ x* -?,x*+?］
(x0≠x *)时，由迭代法 (3)产生的序列｛ xk｝
以 p阶收敛速度收敛于 x*.
Prove:
(1)由 g′( x*)=0?必存在?>0，当 x0∈ ［ x* -?,
x*+?］? U(x)时，由迭代格式 (3)产生的序列 {xk}收敛于 x*,并有 xk∈ ［ x* -?,x*+?］
(2)由泰勒公式有 xk+1=g(xk)=g(x* ）＋ g′(x*)(x k-
x*)+… +g (p-1) (x*)(xk-x*) p-1/(p-1)! +
g (p)(x*+?(xk-x*))(xk-x*) p /p!,0<?<1.
利用 g在 x*的各阶导数条件及 g(x*)=x*,上式可改写成
( ) * *
**
1
( ( )
()
!
p
pk
kk
g x x x
x x x x
p
(11)
(3)由于 g在 x*处 p阶连续可微且 g(p)(x*)≠0,知必存在 x*的某邻域Ｕ (x*),当 x∈U(x *)时，有 g (p) (x)≠0.
由于 x*+?(xk-x*) ∈ ［ x* -?,x*+?］?U(x*),故
g (p)(x*+?(xk-x*)) ≠0,k=0,1,2,…,
可见，当初值 x0≠x *时，由 (11)式可推出诸 xk≠x *
于是由 (11)式有
* ( ) * *
1
*
( ( )
!
p
k k
p
k
xx g x x x
pxx
上式令 k→∞ 取极限,
* ( ) *
1
*
()
l im 0
!
p
k
pk
k
xx gx
pxx
即 {xk}有 p阶收敛速度,
作业（ homework)
P159,第二题
P160,第三题
我们知道在实际应用中有许多非线性方程的例子，例如
（ 1）在光的衍射理论（ the theory of
diffraction of light)中,我们需要求 x-tanx=0的根
（ 2）在行星轨道（ planetary orbits） 的计算中,对任意的 a和 b,我们需要求 x-asinx=b的根
（ 3） 在数学中，需要求 n次多项式 xn + a1 xn-
1+...+an-1 x + an＝ 0的根求 f(x)=0的根
§ 3.1 对分区间法
(Bisection Method )
原理,若 f(x)?C[a,b],且 f (a) · f (b) <
0,则 f(x) 在 (a,b) 上必有一根。
a
b
x1
x2
a1
b
x*
1
2
停机条件（ termination condition ）,
11 εxx kk 2)( εxf?或误差 分析：
第 1步产生的
21
bax 有误差
21
abx*||x
第 k 步产生的 xk 有误差
kk
abx*||x
2
对于给定的精度?,可估计二分法所需的步数 k,
2ln
lnln
2
εabkεab
k
例 1 用二分法求在 (1,2)内的根，要求绝对误差不超过解,
f(1)=-5<0 有根区间 中点
f(2)=14>0 -(1,2)+
f(1.25)<0 (1.25,1.5)
f(1.375)>0 (1.25,1.375)
f(1.313)<0 (1.313,1.375)
f(1.344)<0 (1.344,1.375)
f(1.360)<0 (1.360,1.375)
f(1.368)>0 (1.360,1.368)
0104 23 xx
210
2
1
f(1.5)>0 (1,1.5)
nx
1,51?x
3 6 4.1
3 6 8.1
3 6 0.1
3 4 4.1
3 1 3.1
3 7 5.1
25.1
8
7
6
5
4
3
2
x
x
x
x
x
x
x
12
例 2，求方程 f(x)= x 3 –e-x =0的一个实 根 。
因为 f(0)<0,f(1)>0。 故 f(x)在 (0,1)内有根用二分法解之,(a,b） =（ 0,1)’计算结果如表：
k a bk xk f(xk)符号
0 0 1 0.5000 －
1 0.5000 － 0.7500 －
2 0.7500 － 0.8750 ＋
3 － 0.8750 0.8125 ＋
4 － 0.8125 0.7812 ＋
5 － 0.7812 0.7656 －
6 0.7656 － 0.7734 ＋
7 － 0.7734 0.7695 －
8 0.7695 － 0.7714 －
9 0.7714 － 0.7724 －
10 0.7724 － 0.7729 ＋
取 x10=0.7729,误差为 | x* -x10|<=1/211 。
Remark1,求奇数个根
Find solutions to the equation
on the intervals [0,4],Use the bisection
method to compute a solution with an
accuracy of 10－ 7,Determine the number
of iterations to use.,
[0,1],[1.5,2.5] and [3,4]，
利用前面的公式可计算迭代次数为 k=23,
Remark2:要区别根与奇异点
Consider f(x) = tan(x) on the interval
(0,3).Use the 20 iterations of the
bisection method and see what happens.
Explain the results that you obtained.
（ 如下图）
Remark3:二分发不能用来求重根
f (x) = 0 x = g (x)
等价变换
f (x) 的根 g (x) 的不动点
§ 3.2 单个方程的迭代法
f(x)=0化为等价方程
x=g(x)的方式是不唯一的,有的收敛,有的发散
For example,2x3-x-1=0
321xx(1) 如果将原方程化为等价方程由此可见，这种迭代格式是发散的取初值
00?x
3102 1 1xx
3212 1 3xx
3322 1 55xx
31 21kkxx则 迭 代 格 式 为,
3 2 1 xx
(2) 如果将原方程化为等价方程
00?x
2
103
1
xx 3
2
1? 7937.0?
3 12 2 1 xx 3 2
7937.1? 9644.0?
仍取初值依此类推,得
x3 = 0.9940
x4 = 0.9990
x5 = 0.9998
x6 = 1.0000
x7 = 1.0000
已经收敛,故原方程的解为 x = 1.0000
同样的方程
不同的迭代格式有不同的结果什么形式的迭代法能够收敛呢?
收敛性分析定义 2 若存在常数?(0≤?<1),使得对一切 x1,x2∈ ［ a,b］,
|g(x1)-g(x2)|≤? |x1-x2|,(5)
则称 g(x)是［ a,b］ 上的一个压缩映射,
称为压缩系数考虑方程 x = g(x),g(x)?C[a,b],若
( I ) 当 x?[a,b] 时,g(x)?[a,b]；
( II )在［ a,b］ 上成立不等式,|g(x1)-g(x2)|≤? |x1-x2| 。
则（ 1） g在［ a,b］ 上存在惟一不动点 x*
（ 2）任取 x0?[a,b],由 xk+1 = g(xk) 得到的序列 {xk}（?［ a,b】）
收敛于 x*。
（ 3） k次迭代所得到的近似不动点 xk与精确不动点 x*有 有误差估计式：
定理 3.2.1
*
11k k kx x x x
*
101
k
kx x x x
§ 3 Fixed-Point Iteration
证明,① g(x) 在 [a,b]上存在不动点？
② 不动点唯一？
③ 当 k时,xk 收敛到 x*？
|x*-x′|=|g(x *)-g(x′)|≤? |x*-x′|,
因 0≤?<1，故必有 x′=x *
若有 x′∈ ［ a,b］,满足 g(x′)=x′,
|xk-x*|=|g(xk-1)-g(x*)|≤? |x k-1-x*|
≤?2|xk-2-x*| ≤ … ≤?k|x0-x*|?0,
令 G(x)=g(x)-x,x∈ ［ a,b］,由条件①知
G(a)=g(a)-a≥0,G(b)=g(b) -b≤0.
由条件②知 G(x)在［ a,b］ 上连续，又由介值定理知存在 x*∈ ［ a,b］,使 G(x*)=0,即 x*=g(x*).
§ 3 Fixed-Point Iteration
可用 来控制收敛精度
|| 1 kk xx
越小，收敛越快
(4) |xk-x*|=|g(xk-1)-g(x*)|≤? |x k-1-x*|
≤? （ |xk-xk-1|+|xk-x*|）,
故有 |xk-x*| ≤?/(1-?)|xk-xk-1|.
这就证明了估计式 (6),
(5) |xk-xk-1| = |g(xk-1)-g(xk-2)|
≤? |x k-1-xk-2|≤ … ≤? k-1|x1-x0|
联系估计式 (6)
|xk-x*| ≤?k-1/(1-?)|x1-x0|.
即估计式 (7)成立
Remark：
定理条件非必要条件，而且定理 3.2.1中的压缩条件不好验证，一般来讲,
若知道迭代函数 g(x)∈C 1『 a,b］,并且满足 |g′(x)|≤? ≤1,对任意的 x∈ ［ a,b］,
则 g（ x)是［ a,b］ 上的压缩映射例题
已知方程 2x-7-lgx＝ 0,求方程的含根区间，考查用迭代法解此方程的收敛性。
在这里我们考查在区间 [3.5,4]的迭代法的收敛性
很容易验证,f(3.5)<0,f(4)>0
将方程变形成等价形式,x＝ (lgx+7)/2
( l g ( ) 7 )
11
()
2 l n 1 0
x
gx
x
1
g(x)=
2
3,5 4m a x | ( ) | 0,0 6 3 1x gx
由定理 3.2.1知，迭代格式 xk+1＝ (lgxk+7)/2
在 [3.5,4]内收敛局部收敛性定理定理 3.2.2 设 x*为 g的不动点,g(x)与 g′(x)
在包含 x*的某邻域 U(x*) (即开区间 )内连续，
且 |g′(x *)|<1,则存在?>0，当 x0∈ ［ x* -
,x*+?］ 时，迭代法 (3)产生的序列
{xk}? ［ x* -?,x*+?］ 且收敛于 x*.
证明略（作为练习） We don’t know x*,how do we
estimate the
inequality？
举例用一般迭代法求 x3-x-1=0的正实根 x*
3x = x + 1将 方 程 改 写 成,
3x) = x+ 1则 迭 代 函 数 为,g(
2
3
1x ) =
3 x + 1
g(
（ ）
容易得到,g′(x) 在包含 x*的某邻域 U(x*) 内连续，且 |g′(x *)|<1
*3
kx = x + 1 xk+1因 此 迭 代 格 式 在 附 件 收 敛例题用一般迭代法求方程 x-lnx＝ 2在区间（ 2,?）
内的根，要求 |xk-xk-1|/|xk|<=10-8
解：令 f(x)=x-lnx-2
f(2)<0,f(4)>0,故方程在（ 2,4）内至少有一个根
1f ( x ) = 1 0,2
x x又 － （,）
f ( x ) = 0 2,
2
*
*
因 此 方 程 在 （,） 内 仅 有 一 个 根 x
且 x （,）
将方程化为等价方程,x＝ 2＋ lnx
1g ( x ) 2 l n x ( x ) |= | | 0,5 1,2 4
x
x＝ ＋,|g （,）
因此,? x0?（ 2,?）,xk+1＝ 2＋ lnxk产生的序列? xk?收敛于 X*
取初值 x0＝ 3.0,计算结果如下：
7 3.146143611
8 3.146177452
9 3.146188209
10 3.146191628
11 3.146192714
12 3.146193060
13 3.146193169
14 3.146193204
k xi
0 3.000000000
1 3.098612289
2 3.130954362
3 3.141337866
4 3.144648781
5 3.145702209
6 3.146037143
另一种迭代格式：
1
( 1 l n )
1
kk
k
k
xx
x
x?
0 3.000000000
1 3.147918433
2 3.146193441
3 3.146193221
程序演示由此可见，对同一个非线性方程的迭代格式，在收敛的情形下，有的收敛快，有的收敛慢。
定义 1.,设 序列 {xk}收敛于 x*,若存在 p≥ 1和正数 c，
使得成立则称 {xk}为 p 阶收敛的特别,
p = 1,要求 c<1,称线性收敛 ;
1<p<2,称超线性收敛
p=2,称平方收敛。
*
1
*
l i m
k
pk
k
xx
C
xx
迭代法的收敛阶 (收敛速度 )
定理 3.2.3
设 x*为 g的不动点,p≥2 为正整数,g在 x*的某邻域Ｕ (x*)内 p阶连续可微，且
g′( x*)=g″( x*)=… =g (p-1)(x*)=0,而
g(p)(x*)≠0,
则存在?>0，当 x0∈ ［ x* -?,x*+?］
(x0≠x *)时，由迭代法 (3)产生的序列｛ xk｝
以 p阶收敛速度收敛于 x*.
Prove:
(1)由 g′( x*)=0?必存在?>0，当 x0∈ ［ x* -?,
x*+?］? U(x)时，由迭代格式 (3)产生的序列 {xk}收敛于 x*,并有 xk∈ ［ x* -?,x*+?］
(2)由泰勒公式有 xk+1=g(xk)=g(x* ）＋ g′(x*)(x k-
x*)+… +g (p-1) (x*)(xk-x*) p-1/(p-1)! +
g (p)(x*+?(xk-x*))(xk-x*) p /p!,0<?<1.
利用 g在 x*的各阶导数条件及 g(x*)=x*,上式可改写成
( ) * *
**
1
( ( )
()
!
p
pk
kk
g x x x
x x x x
p
(11)
(3)由于 g在 x*处 p阶连续可微且 g(p)(x*)≠0,知必存在 x*的某邻域Ｕ (x*),当 x∈U(x *)时，有 g (p) (x)≠0.
由于 x*+?(xk-x*) ∈ ［ x* -?,x*+?］?U(x*),故
g (p)(x*+?(xk-x*)) ≠0,k=0,1,2,…,
可见，当初值 x0≠x *时，由 (11)式可推出诸 xk≠x *
于是由 (11)式有
* ( ) * *
1
*
( ( )
!
p
k k
p
k
xx g x x x
pxx
上式令 k→∞ 取极限,
* ( ) *
1
*
()
l im 0
!
p
k
pk
k
xx gx
pxx
即 {xk}有 p阶收敛速度,
作业（ homework)
P159,第二题
P160,第三题
