第七章 方程求根 1
1 1 0
( ) 0
( ) 0,1
,
( ) si n 0
nn
nn
x
fx
f
f x n
f x x
a x a x a x a
e
?
?
?
? ? ? ? ? ? ?
? ? ?
L
求解非线性方程
是非线性函数，
例：代数方程
。
例 超越方程
( ) [,] [,]
( ) ( ) 0
( ) 0,( ) 0
f x a b a b
f a f b
f a f b
??
??
设 在 上连续且 有且仅有一个根又
。则可用对分法：
不妨设
.,
2
2
0
2
,
2
0
2
,1
1111 aa
ba
bbb
ba
a
ba
f
ba
x
ba
f
?
?
??
?
?
?
?
?
?
?
?
?
?
? ??
??
?
?
?
?
?
?
?
? ?
反之，令
，否则：若输出根若）
?],,[]b,a[),ba 2211 1 2 ）的计算，并产生区间重复对
.
2
0
2
),3 baxbaf iiii
?
????
?
?
??
?
? ?
则得到根，若
§ 1,非线性方程实根的对分法 (二分法 )
二分法的收敛性
11 [,] [,] [,]nnab a b a b? ? ?L
二分法产生一个有根区间：
11
[,]
11
( ) ( )
2 2
nn
nn n n n
ba
ab
b a b a??? ? ? ? ? ?L
区间长度：
，足够大时，取近似值当
2
bax nnnn
?
?
1
2
nn
ba
x x ?
?
?
? ? ?误差：
计算简便，容易估计误差，但收敛较慢。
a x* x0 b
()fx
a1 b1
§ 2,迭代法
连续。且改写方程,)(0)( ?? xxxf ???
}{ xxx nnn )( 1,得到序列建立迭代格式,???
1
{ } ( 0
)(l im l im l im
n
nn n
n n n
fxx
xxx ???
? ? ? ? ? ?
?
??
?? ??
??
则 若 收敛必收敛到 ） 的根：
*
* * *
{ }
( ) ( ) 0
l imnn
n
x
x x f x
xx
?
??
?
? ? ?
若 收敛，即,则：
迭代过程的几何表示
()yx??
yx?
O x* x2 x1 x0 x
y
0P
1Q
1P
2P
*P
2Q
()
()
yx
xx
xy
?
?
??
?? ?
??
交点即为真根
3*
0
3
3
1
k
( ) 1 0 1.5,
1 1
1 ( 0,1,2 )
k 0 1 2 7 8
x 1.5 1.3 57 21 1.3 30 86 1.3 24
kk
f x x x x x
xx
x x k
?
? ? ? ? ?
??
? ? ? L
L
L
例：求方程 在 附近的根
解：（ ） 将方程改写为
由此建立迭代公式
3
3
1
k
72 1.3 24 72
2 1
1.
k 0 1 2
x 1.5 2.3 75 12,39
kk
xx
xx
?
??
??
L
L
迭代收敛。
（ ） 若将方程改写为
建立迭代公式
迭代不收敛。
*
1
*
,( ) [,]
1 [,] ( ) ;
( 2) 0 1,,[,],
( ) ( )
( ) [,],
[,],
( ) ( 0,1,)
nn
x a b
x a b a x b
L x y a b
x y L x y
x x a b x
ab
x x n
x
?
?
??
?
?
?
? ? ?
? ? ?
? ? ?
?
?
?? L
0
定理 设函数 在区间 上满足条件
（ ）对任意,都有
存在常数 使得对一切 都有
则方程 在 内有唯一的根 且对任何
初值x 迭代序列
均收敛于,并有
*
10
x
1
n
n
L
x x x
L
? ? ?
?
收敛充分性定理 (一,1)
2 ( ) [,]
( ) ( ),( ) [,]
( ) ( ) 0,( ) ( ) 0
[,] 0,
( ) [,]
x a b
x x x x a b
a a a b b b
ab
x x a b
?
? ? ?
? ? ? ?
? ? ? ? ? ?
?
??
? ? ? ? ? ?
? ? ?
?
证：由条件（ ）知 在 上连续。
令 则 在 上连续，且
故存在,使得 （ ） 即 （ ）,
所以方程 在 内有根。
**
12
* * * * * * * *
1 2 1 2 1 2 1 2
( ) [,],
2
( ) ( )
x x a b x x
x x x x L x x x x
?
??
??
? ? ? ? ? ? ?
假设方程 在 内有两个根
由条件（ ），有
导出矛盾，唯一性得证。
收敛充分性定理 (一,2)
? ?
0
* * *
11
**
0
*
0
*
1 1 1
1
[,],
( ) ( )
0 < 1,l i m
x [,],
( ) ( )
n n n
n
n
n
n
n
k k k k k k
k
x a b
x x x x L x x
x x L x x
L x x
a b x
x
k
x x x x L x x
Lx
??
??
??
??
? ? ?
?
? ? ? ? ?
? ? ?
??
?
? ? ? ? ?
? ? ?L
对任意 由迭代公式有
依此类推，得
因 所以
即对任意初值 迭代序列 均收
敛到方程的根 。
类似地，对任意正整数,有
0
x
收敛充分性定理 (一,3)
1 1 2 1
12
1 0 1 0 1 0
12
10
10
*
10
,,
( 1 )
1
1
,
1
n p n n p n p n p n p n n
n p n p n
n p p
p
n
n
n
np
L
p
L
x
L
x x x x x x x x
x x x x x xL L L
xxL L L
L
xxL
x x x
? ? ? ? ? ? ? ? ?
? ? ? ?
??
? ? ? ? ? ? ? ?
? ? ? ? ? ? ?
? ? ? ? ?
?
??
?
??
? ? ?
?
L
L
L
于是，对任意正整数 有
令得
收敛充分性定理 (一,4)
收敛充分性定理 (二,1)
'
*
1
*
*
,( ) [,]
1 [,] ( ) ;
( 2) 0 1,[,],
( )
( ) [,],
[,],
( ) ( 0,1,)
x
nn
x a b
x a b a x b
L x a b
xL
x x a b x
ab
x x n
x
?
?
?
?
?
?
? ? ?
? ? ?
?
?
?
??
?
L
0
定理 设函数 在区间 上满足条件
（ ）对任意,都有
存在常数 使得对一切 都有
则方程 在 内有唯一的根 且对任何
初值x 迭代序列
均收敛于,并有
10
1
n
n
L
x x x
L
??
?
收敛充分性定理 (二,2)
'
'
'
,[,]
,
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
( ) ( )
( ) 2
x y a b
xy
x y x y
x y x y
x y L x y
x
?
? ? ? ?
? ? ? ?
??
?
? ? ?
? ? ? ?
? ? ? ?
证：设 为 上任意两点，由微分中
值定理，在 之间至少存在一点,使得
即 满足上一定理的条件（ ），故结论成
立。
*
10
'
x
1
()
( ) [,]
n
n
L
x x x L
L
x
x a b
?
?
? ? ?
?
误差估计式 表明，常数 越小，
简单迭代法收敛越快。因而构造迭代函数 的原则
是使 在有根区间 上有尽可能小的上界。
1 1 2 1
1 2
11
1
1
1
1
1
1
*
,
1
n p n n p n p n p n p n n
p p
n n n n
n n n
nn
p
L
p
L
x x x x x x x x
L x x x xL
x x xx
xx
? ? ? ? ? ? ? ? ?
? ?
??
?
?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ?
?
? ? ? ? ?
?
?
L
L
对任意正整数 有
）
令得
可通过检查 来判断迭代过程应否终止。
（
2
11
'
1
2
( ) 1 0
( 1,5 ) 0,2 5 0,( 2 ) 1 0
[ 1.5,2]
1 1 ( ) 1,5 1,5 1 ( ) 2 1 2
1 1 1
()
3,1 6 22 1 2 2,5
1
( 2 ) 1 ( )
f x x x
ff
x x x x
x
x
xx
x
??
?
?
? ? ? ?
? ? ? ? ?
?
? ? ? ? ? ? ? ? ?
? ? ?
?
? ? ?
例：用简单迭代法求方程 的根。
解：因
为有根区间。
（ ） 因
且
2
'
2
22
0
11
1,5 1 ( ) 1 2
2 1,5
1 1 1
( )
1,5 2,2 5
[ 1,5,2 ],
x
x
x
x
?
?
? ? ? ? ? ?
? ? ? ?
?
因
且
根据定理，任取 由这两种等价方程所构造的
简单迭代方法都收敛，且第一种所产生的迭代序列收敛较快。
收敛充分性定理 (三,1)
* * *
*
'*
**
0
1
*
( ) (,)
()
( ) 1,,,
[,],
( ) ( 0,1,2,)
.
nn
x x O x
x x x
x
x x x
x x n
x
??
?
? ? ? ?
??
?
?
?
??
? ? ?
?? L
定理：如果函数 在 的一邻域
内连续可微,为方程 的根，且
则存在正数 使得对任意
迭代序列
收敛于
' * * '
* * *
'
**
* * *
**
*
1
( ) (,) ( ) 1,
1,,[,]
( ) 1
( ),
( ) ( ) ( )
( ) [,]
()
nn
x O x x
L x x x
xL
xx
x x x x L x x
x x x
x x x
? ? ?
? ? ? ?
?
?
? ? ? ?
? ? ?
?
?
?
? ? ? ? ? ?
??
?
? ? ? ? ? ?
? ? ?
?
证：因 在 内连续，且 故存
在正数 使得对,有
另一方面，由 又有
即 。由上面定理知，迭代序列
收敛于 。
收敛充分性定理 (三,2)
实际用迭代法计算时，先用对分区间法求较好的初值，
然后再进行迭代。
迭代法加速（埃特金方法）（ 1）
*
0
1 0 2 1
* * ' *
1 0 1 0
* * ' *
2 1 2 1
'
* * * *
1 0 2 1
*
1
2
( ) ( )
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
( ),
( ) ( )
xx
x x x x
x x x x x x
x x x x x x
xL
x x L x x x x L x x
xx
xx
??
? ? ? ?
? ? ? ?
?
??
? ? ? ? ?
? ? ? ? ?
? ? ? ? ? ?
?
?
?
设 是根 的某个预测值，通过两次迭代校正
有
由微分中值定理，有
假定 改变不大，近似地取某个近似值
则由
* 2
*0 21
2
**
1 0 1 2
()
2
xx xx
xx
x x x x x
? ?
? ? ? ?
? ? ?
此种加速需用两次迭代值进行加工。
迭代法的加速（埃特金方法）（ 2）
%
%
%
%
1
11
2
11
1
1
11
( )
( )
()
2
k
k
kk
kk
k
k
kk
k
xx
xx
xx
xx
x x x
?
?
?
??
??
?
?
??
?
?
?
??
??
如果将一次改进值作为一步，
则计算公式如下：
校正
再校正
改进
? ?
0
2
0
0 0 0
( ) 0
0 2
''
'
f x x T ay lor
()
f( x ) f( ) ( x - ) ( )
!
f x
xfx x x x
?
? ? ? ?? L
在真根附近 点展开成 级数：
§ 3,Newton 法
非线性问题的最简单解法是线性近似,
将非线性方程线性化，以线性方程的解逐步逼
近非线性方程的解，这就是 Newton法的基本思想
1
0 0 0 0
( 0 )
''
xx
f( ) ( ) ( )ffx x x x x? ? ?
解出 作为近似根,
?,2,1,0 ),()(
N e w t o n
'
1
???
?
nf xfxxx
nnnn
法：依次产生迭代格式，称
? ? 00
000
???? xx)(xf ')f ( x:f ( x )
取线性部分近似代替
Newton 法的几何解释
1
'
1
x ( 0 )
'
0 0 0( ) ( )
y x
fx fx x x
?
? ?
与 轴交点 为第二个近似根,
? ?
0 0 0
'
0 0 0
,( )
( )
( ) ( ) ( )
f
fx
y f x
x x x
fx x x
?
? ? ?
当 在取定后（在真根 附近），过
作 的切线，则切线方程：
?
?
0
?
1
ξ
( ?
0
,f( ?
0
))
'
0 0 0 ( ) ( ) ( )y f xfx x x? ? ?
1
**
1
()
()
( 0
11
2
kk
kk
k
p
k
xx
x x x e x x
k
e
CC
e
p
pp
p
?
?
?
?
?
? ? ?
??
??
??
?
定义：设迭代过程 收敛于方程
的根,如 果迭代误差
当 时成立下列渐进关系式
为常数）
则称该迭代过程是 阶收敛的。
为线性收敛,为超线性收敛，
为平方收敛。
迭代法收敛速度定义
()
1
*
' * " * ( 1 ) * ( ) *
*
( ),( )
( ) ( ) ( ) 0 ; ( ) 0
p
kk
pp
x x x
x
x x x x
xp
??
? ? ? ?
?
?
?
? ? ? ? ?L
定理：对于迭代过程 如果 在所
求根 的邻近连续，并且
则该迭代过程在点 邻近是 阶收敛的。
'*
1
*
()
**
( ) ( ) *
** 1
1
( ) 0 1,( )
()
()
( ) ( ) ( )
!
( ) ( )
()
!!
kk
k
p
p
kk
pp
p k
kk p
k
x x x
xx
x x x x
p
e x
x x x x
p e p
??
?
??
??
? ? ?
?
?
?
? ? ?
? ? ?
? ? ? ? ? ?
证：由于 故 具有局部收敛性。
将 在根 处展开，由条件有
'
1
'
'
2
' ''
''
'
2
''
( )
[,] ( ) 0,
()
()
()
( )
()
( ) ( ) ( )
( ) ( )
( ) 1
( ) (
k
kk
k
x
x a b x
fx
xx
fx
fx
xx
fx
f x f x f x
f x f x
x
f x f
?
?
?
?
?
??
??
??
?? ?
??
? ? ?
??
??
迭代过程的收敛速度依赖于迭代函数 的选
取。如果当 时 则该迭代过程只
可能是线性收敛。
对牛顿公式
其迭代函数为
由于
2
* * ' *
' * *
)
( ) ( ) 0,( ) 0,
( ) 0,
x
x f x f x f x
xx?
??
??
??
?
假定 是 的一个单根，即 则
由上式知 由上述定理知，牛顿法在根 的
邻近至少是平方收敛的。
'
'
1
0
1 0.
( ) 1,( ) ( 1 )
()
( )
( ) 1
1
0.5
k
x
xx
x
x
k
kk
k
xe
f x x e f x e x
f x x e
x x x
f x x
xe
xx
x
x
?
?
?
?
??
? ? ? ?
?
? ? ? ?
?
?
??
?
?
例：用牛顿法解方程
解：
牛顿法迭代函数为
牛顿公式为
可先用二分法或经验确定迭代初值,再按牛
顿公式进行迭代。
Newton法具有收敛快，稳定性好，精度高等优点，是求
解非线性方程的有效方法之一。但它每次迭代均需计算函
数值与导数值，故计算量较大。而且当导数值提供有困难
时,Newton法无法进行。
牛顿法应用举例
2
1
0
1
( ),
2kk k
C x C
C
C x x
x?
??
??
对于给定正数,应用牛顿法解二次方程
即导出求开方值 的计算程序
0
2
2'
1
2
22
1
22
2
1
0
1
( ),( ) 2,( ),
22
1
( 2 2 )
22
11
( 2 ) ( )
22
1
( )
2
k
k k k
kk
k
k k k k k
kk
k k k
kk
kk
k
x
xC C
f x x C f x x x x x
xx
xC
x C x C x x C x C
xx
x x C C x C
xx
x C x C
x
?
?
?
?
?
? ? ? ? ? ? ?
?
? ? ? ? ? ? ? ?
? ? ? ? ?
? ? ?
现证此迭代公式对于初值 都是收敛的。由迭代公式得
同理
22
11
2
1
1
2
0
0
20
0
2
2
11
( ),( )
22
,
,
2,
1
k
k
k
k
k k k k
kk
kk
kk
k
k
k
k
k
x C x C x C x C
xx
x C x C
x C x C
x C x C
x C x C
x C x C
qq
x C x C
q
x C C
q
??
?
?
? ? ? ? ? ?
??
??
? ? ?
??
??
??
??
??
??
??
??
??
??
??
??
? ? ?
??
? ? ?
?
L
由
记
0
0,1,
k
x q k x C? ? ? ? ?对任意 总有,故当 时，
§ 4.弦截法与抛物线法
1
'
1
1
1
1
( ),( ),
()
,,,( ) 0
( ),( ),,( ),
( ),( ) 0 ( ) 0
kk
k
k k k r
k k k r
rr
k
k
f x f x
fx
x x x f x
f x f x f x
p x p x f x
x
x
?
?
?
??
??
?
?
??
?
L
L
L
＋
基本思想：利用一些函数值 来
回避导数值 的计算。
设 是 的一组近似根，利用
函数值 构造插值多项式
并适当选取 的一个根作为 的
新的近似根,这就确定了一个迭代过程，记迭
代函数为,
1
(,,,),
1 2
k k k r
x x x
rr
??
??
L
当 时为弦截法，当 时为抛物线法。
一、弦截法
11
11
1
1
1
1
11
1
1
,( ) 0 ( ),( )
( ) ( ) 0
( ) 0,
( ) ( )
( ) ( ) ( )
()
( ),
( ) ( )
()
k k k k
k
kk
kk
kk
k
k k k k
kk
k
kk
x x f x f x f x
p x p x
f x x
f x f x
p x f x x x
xx
fx
x x x x
f x f x
fx
xx
f
??
?
?
?
??
?
?
?
?
?
?
? ? ?
?
? ? ? ?
?
??
设 是 的近似根，利用
构造一次插值多项式,并用 的根作为
的新的近似根
由
此迭代公式可看作牛顿公式
'
' 1
1
()
( ) ( )
()
k
kk
kk
x
f x f x
fx
xx
?
?
?
?
中的导数
用差商 取代的结果。
弦截法的几何表示
x0 X x* x1 x2 x3
Y
P0
P2
P1
11
0 1 1
,.
,
k k k
k
k
x x x
x x x
x
??
?
弦截法在求 时要用到前面两步的结果
需两个初值,而牛顿切线法在计算 时，只
用到前一步 的值。
弦截法收敛性定理
**
'
01
11
1
*
( ),
( ) 0,
,,
()
( ),
( ) ( )
15
1, 6 1 8,
2
k
k k k k
kk
f x x x x
x f x
xx
fx
x x x x
f x f x
px
?
??
?
? ? ?
? ? ?
? ? ?
? ? ?
?
?
??
定理：假设 在根 的邻域 内
具有二阶连续导数，且对任意 有 又
初值 那么当邻域 充分小时，弦截法
将按阶 收敛到根
证明：（略）
二、抛物线法
12
22
1
( ) 0,,,
( ),( )
,
,.
k k k
k
f x x x x
p x p x
x
??
?
?设已知方程 的三个近似根 以这三
点为节点构造二次插值多项式 并适当选取 的
一个零点 作为新的近似根 这样确定的迭代过程称抛
物线法 也称密勒法
()fx
2()Px
*x
1kx? k
x1kx? 2kx?
抛物线法计算公式
21
1 2 1
12
1 1 2 1
2
2
( ) ( ) [,] ( )
+ [,,] ( ) ( ),
[,,]
[,] + [,,] ( )
()
( ) ( )
k k k k
k k k k k
k k k k
k k k k k k k k
kk
kk
p x f x f x x x x
f x x x x x x x
a f x x x
b f x x f x x x x x
c f x
p x a x x
?
? ? ?
??
? ? ? ?
? ? ?
??
??
?
??
?
?
?
?
? ? ? ?
插值多项式
令
2
2
*
21
1
2
()
4 2
2
4
,,,,
,.
2 sgn ( )
4
k k k
k k k k
k
kk
k
k k k k
k k k k
kk
kk
kk
k k k k
b x x c
b b a c c
x x x
a
b b a c
x x x x x
x x x
cb
xx
b b a c
??
?
??
? ? ?
? ? ? ? ?
??
?
??
??
在 三个近似根中假定 更接近根 故新的近
似根应在 邻近 即 较小于是抛物线计算公式为
*
*
0 1 2
*
*
,( )
,,,,
( ) 0
1,8 4
f x x
x x x x
x f x
x
?
可以证明如果 在其零点 邻近三阶连
续可微 且初值 充分接近 则抛物线法
是收敛的。特别地，若 是方程 的单根，
收敛解为 。
另一方面，在收敛性的证明中虽然要求初
始值充分接近根,但实际计算表明，抛物线
法对初值要求并不苛刻，在初值不太好的情况
下常常也能收敛。缺点是程序较复杂，并在计
算实根的过程中，也常常需要采用复数计算，
增加
( ) 0fx ?
了工作量。因此，抛物线法适用于当初值
不太好时求方程 的复根的情况。
§ 5.代数方程的牛顿法
0
1
0 1 1
0 0 0
12
0 1 2 1
00
( )
( ) 0
( )
( )
( ) ( ) ( ) ( ) ( ),
( );
nn
nn
nn
nn
fx
fx
fx
f x a x a x a x a
x x f x f x x x p x
p x b x b x b x b
ab
?
?
??
??
?
? ? ? ? ?
? ? ? ?
? ? ? ? ?
?
L
L
如果 是多项式，可针对多项式的特性，建立求解
代数方程 的有效解法。
计算函数值 的秦九韶法：
多项式
以 为除式，有
令 代入并与上式
比较同次幂的系数得
00
0 1 0 1
0 0 1 0;
,1 1 ;,1 ;
( ) ( ),
i i i i i i
n n n
ba
a b x b i n b a x b i n
a f x x b f x b
??
?
???
??
? ? ? ? ? ? ? ? ? ?
??
??
? ? ?
??
'
0
"
' 0
0 0 0 0
()
10
0 0 0
'
0
'
00
2
0
( ),
( )
()
( ) ( ) ( ) [ ( ) ( )
2!
()
( ) ] ( ) ( ) ( ),
!
( ) ( ) ( )
( ) ( ) ( ) ( ),
()
n
n
n
fx
fx
fx
f x f x x x f x x x
fx
x x f x x x p x
n
f x p x x x
p x f x x x q x
q x c x c
?
?
? ? ? ? ? ?
? ? ? ? ?
?
? ? ?
??
L
用秦九韶算法求
的台劳展开式,
由此可知，导数 又可看作 用因式
相除得出的余式。令
其中
3
1 3 2
00
01
'
01
,;
,1 1 ;
( ),
n
nn
i i i
n
x c x c
cb
c b x c i n
f x c
?
??
?
?
? ? ?
??
?
? ? ? ? ? ?
?
?
?
?
L
1
0 1 1
1
'
'
00
1
00
1
'
1
( ) 0
()
()
( ) ( );
,1 ;
( ),;
,1 1 ;
( ),
nn
nn
k
kk
k
kk
i i k i
kn
i i k i
kn
f x a x a x a x a
fx
xx
fx
f x f x
ba
b a x b i n
f x b
cb
c b x c i n
f x c
?
?
?
?
?
?
? ? ? ? ? ?
??
??
?
? ? ? ?
?
?
?
?
??
?
? ? ? ? ?
?
?
?
?
L
代数方程的牛顿法：
对
用牛顿公式
其中函数值 与导数值 均可方便求出：
1 1 0
( ) 0
( ) 0,1
,
( ) si n 0
nn
nn
x
fx
f
f x n
f x x
a x a x a x a
e
?
?
?
? ? ? ? ? ? ?
? ? ?
L
求解非线性方程
是非线性函数，
例：代数方程
。
例 超越方程
( ) [,] [,]
( ) ( ) 0
( ) 0,( ) 0
f x a b a b
f a f b
f a f b
??
??
设 在 上连续且 有且仅有一个根又
。则可用对分法：
不妨设
.,
2
2
0
2
,
2
0
2
,1
1111 aa
ba
bbb
ba
a
ba
f
ba
x
ba
f
?
?
??
?
?
?
?
?
?
?
?
?
?
? ??
??
?
?
?
?
?
?
?
? ?
反之，令
，否则：若输出根若）
?],,[]b,a[),ba 2211 1 2 ）的计算，并产生区间重复对
.
2
0
2
),3 baxbaf iiii
?
????
?
?
??
?
? ?
则得到根，若
§ 1,非线性方程实根的对分法 (二分法 )
二分法的收敛性
11 [,] [,] [,]nnab a b a b? ? ?L
二分法产生一个有根区间：
11
[,]
11
( ) ( )
2 2
nn
nn n n n
ba
ab
b a b a??? ? ? ? ? ?L
区间长度：
，足够大时，取近似值当
2
bax nnnn
?
?
1
2
nn
ba
x x ?
?
?
? ? ?误差：
计算简便，容易估计误差，但收敛较慢。
a x* x0 b
()fx
a1 b1
§ 2,迭代法
连续。且改写方程,)(0)( ?? xxxf ???
}{ xxx nnn )( 1,得到序列建立迭代格式,???
1
{ } ( 0
)(l im l im l im
n
nn n
n n n
fxx
xxx ???
? ? ? ? ? ?
?
??
?? ??
??
则 若 收敛必收敛到 ） 的根：
*
* * *
{ }
( ) ( ) 0
l imnn
n
x
x x f x
xx
?
??
?
? ? ?
若 收敛，即,则：
迭代过程的几何表示
()yx??
yx?
O x* x2 x1 x0 x
y
0P
1Q
1P
2P
*P
2Q
()
()
yx
xx
xy
?
?
??
?? ?
??
交点即为真根
3*
0
3
3
1
k
( ) 1 0 1.5,
1 1
1 ( 0,1,2 )
k 0 1 2 7 8
x 1.5 1.3 57 21 1.3 30 86 1.3 24
kk
f x x x x x
xx
x x k
?
? ? ? ? ?
??
? ? ? L
L
L
例：求方程 在 附近的根
解：（ ） 将方程改写为
由此建立迭代公式
3
3
1
k
72 1.3 24 72
2 1
1.
k 0 1 2
x 1.5 2.3 75 12,39
kk
xx
xx
?
??
??
L
L
迭代收敛。
（ ） 若将方程改写为
建立迭代公式
迭代不收敛。
*
1
*
,( ) [,]
1 [,] ( ) ;
( 2) 0 1,,[,],
( ) ( )
( ) [,],
[,],
( ) ( 0,1,)
nn
x a b
x a b a x b
L x y a b
x y L x y
x x a b x
ab
x x n
x
?
?
??
?
?
?
? ? ?
? ? ?
? ? ?
?
?
?? L
0
定理 设函数 在区间 上满足条件
（ ）对任意,都有
存在常数 使得对一切 都有
则方程 在 内有唯一的根 且对任何
初值x 迭代序列
均收敛于,并有
*
10
x
1
n
n
L
x x x
L
? ? ?
?
收敛充分性定理 (一,1)
2 ( ) [,]
( ) ( ),( ) [,]
( ) ( ) 0,( ) ( ) 0
[,] 0,
( ) [,]
x a b
x x x x a b
a a a b b b
ab
x x a b
?
? ? ?
? ? ? ?
? ? ? ? ? ?
?
??
? ? ? ? ? ?
? ? ?
?
证：由条件（ ）知 在 上连续。
令 则 在 上连续，且
故存在,使得 （ ） 即 （ ）,
所以方程 在 内有根。
**
12
* * * * * * * *
1 2 1 2 1 2 1 2
( ) [,],
2
( ) ( )
x x a b x x
x x x x L x x x x
?
??
??
? ? ? ? ? ? ?
假设方程 在 内有两个根
由条件（ ），有
导出矛盾，唯一性得证。
收敛充分性定理 (一,2)
? ?
0
* * *
11
**
0
*
0
*
1 1 1
1
[,],
( ) ( )
0 < 1,l i m
x [,],
( ) ( )
n n n
n
n
n
n
n
k k k k k k
k
x a b
x x x x L x x
x x L x x
L x x
a b x
x
k
x x x x L x x
Lx
??
??
??
??
? ? ?
?
? ? ? ? ?
? ? ?
??
?
? ? ? ? ?
? ? ?L
对任意 由迭代公式有
依此类推，得
因 所以
即对任意初值 迭代序列 均收
敛到方程的根 。
类似地，对任意正整数,有
0
x
收敛充分性定理 (一,3)
1 1 2 1
12
1 0 1 0 1 0
12
10
10
*
10
,,
( 1 )
1
1
,
1
n p n n p n p n p n p n n
n p n p n
n p p
p
n
n
n
np
L
p
L
x
L
x x x x x x x x
x x x x x xL L L
xxL L L
L
xxL
x x x
? ? ? ? ? ? ? ? ?
? ? ? ?
??
? ? ? ? ? ? ? ?
? ? ? ? ? ? ?
? ? ? ? ?
?
??
?
??
? ? ?
?
L
L
L
于是，对任意正整数 有
令得
收敛充分性定理 (一,4)
收敛充分性定理 (二,1)
'
*
1
*
*
,( ) [,]
1 [,] ( ) ;
( 2) 0 1,[,],
( )
( ) [,],
[,],
( ) ( 0,1,)
x
nn
x a b
x a b a x b
L x a b
xL
x x a b x
ab
x x n
x
?
?
?
?
?
?
? ? ?
? ? ?
?
?
?
??
?
L
0
定理 设函数 在区间 上满足条件
（ ）对任意,都有
存在常数 使得对一切 都有
则方程 在 内有唯一的根 且对任何
初值x 迭代序列
均收敛于,并有
10
1
n
n
L
x x x
L
??
?
收敛充分性定理 (二,2)
'
'
'
,[,]
,
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
( ) ( )
( ) 2
x y a b
xy
x y x y
x y x y
x y L x y
x
?
? ? ? ?
? ? ? ?
??
?
? ? ?
? ? ? ?
? ? ? ?
证：设 为 上任意两点，由微分中
值定理，在 之间至少存在一点,使得
即 满足上一定理的条件（ ），故结论成
立。
*
10
'
x
1
()
( ) [,]
n
n
L
x x x L
L
x
x a b
?
?
? ? ?
?
误差估计式 表明，常数 越小，
简单迭代法收敛越快。因而构造迭代函数 的原则
是使 在有根区间 上有尽可能小的上界。
1 1 2 1
1 2
11
1
1
1
1
1
1
*
,
1
n p n n p n p n p n p n n
p p
n n n n
n n n
nn
p
L
p
L
x x x x x x x x
L x x x xL
x x xx
xx
? ? ? ? ? ? ? ? ?
? ?
??
?
?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ?
?
? ? ? ? ?
?
?
L
L
对任意正整数 有
）
令得
可通过检查 来判断迭代过程应否终止。
（
2
11
'
1
2
( ) 1 0
( 1,5 ) 0,2 5 0,( 2 ) 1 0
[ 1.5,2]
1 1 ( ) 1,5 1,5 1 ( ) 2 1 2
1 1 1
()
3,1 6 22 1 2 2,5
1
( 2 ) 1 ( )
f x x x
ff
x x x x
x
x
xx
x
??
?
?
? ? ? ?
? ? ? ? ?
?
? ? ? ? ? ? ? ? ?
? ? ?
?
? ? ?
例：用简单迭代法求方程 的根。
解：因
为有根区间。
（ ） 因
且
2
'
2
22
0
11
1,5 1 ( ) 1 2
2 1,5
1 1 1
( )
1,5 2,2 5
[ 1,5,2 ],
x
x
x
x
?
?
? ? ? ? ? ?
? ? ? ?
?
因
且
根据定理，任取 由这两种等价方程所构造的
简单迭代方法都收敛，且第一种所产生的迭代序列收敛较快。
收敛充分性定理 (三,1)
* * *
*
'*
**
0
1
*
( ) (,)
()
( ) 1,,,
[,],
( ) ( 0,1,2,)
.
nn
x x O x
x x x
x
x x x
x x n
x
??
?
? ? ? ?
??
?
?
?
??
? ? ?
?? L
定理：如果函数 在 的一邻域
内连续可微,为方程 的根，且
则存在正数 使得对任意
迭代序列
收敛于
' * * '
* * *
'
**
* * *
**
*
1
( ) (,) ( ) 1,
1,,[,]
( ) 1
( ),
( ) ( ) ( )
( ) [,]
()
nn
x O x x
L x x x
xL
xx
x x x x L x x
x x x
x x x
? ? ?
? ? ? ?
?
?
? ? ? ?
? ? ?
?
?
?
? ? ? ? ? ?
??
?
? ? ? ? ? ?
? ? ?
?
证：因 在 内连续，且 故存
在正数 使得对,有
另一方面，由 又有
即 。由上面定理知，迭代序列
收敛于 。
收敛充分性定理 (三,2)
实际用迭代法计算时，先用对分区间法求较好的初值，
然后再进行迭代。
迭代法加速（埃特金方法）（ 1）
*
0
1 0 2 1
* * ' *
1 0 1 0
* * ' *
2 1 2 1
'
* * * *
1 0 2 1
*
1
2
( ) ( )
( ) ( ) ( ) ( )
( ) ( ) ( ) ( )
( ),
( ) ( )
xx
x x x x
x x x x x x
x x x x x x
xL
x x L x x x x L x x
xx
xx
??
? ? ? ?
? ? ? ?
?
??
? ? ? ? ?
? ? ? ? ?
? ? ? ? ? ?
?
?
?
设 是根 的某个预测值，通过两次迭代校正
有
由微分中值定理，有
假定 改变不大，近似地取某个近似值
则由
* 2
*0 21
2
**
1 0 1 2
()
2
xx xx
xx
x x x x x
? ?
? ? ? ?
? ? ?
此种加速需用两次迭代值进行加工。
迭代法的加速（埃特金方法）（ 2）
%
%
%
%
1
11
2
11
1
1
11
( )
( )
()
2
k
k
kk
kk
k
k
kk
k
xx
xx
xx
xx
x x x
?
?
?
??
??
?
?
??
?
?
?
??
??
如果将一次改进值作为一步，
则计算公式如下：
校正
再校正
改进
? ?
0
2
0
0 0 0
( ) 0
0 2
''
'
f x x T ay lor
()
f( x ) f( ) ( x - ) ( )
!
f x
xfx x x x
?
? ? ? ?? L
在真根附近 点展开成 级数：
§ 3,Newton 法
非线性问题的最简单解法是线性近似,
将非线性方程线性化，以线性方程的解逐步逼
近非线性方程的解，这就是 Newton法的基本思想
1
0 0 0 0
( 0 )
''
xx
f( ) ( ) ( )ffx x x x x? ? ?
解出 作为近似根,
?,2,1,0 ),()(
N e w t o n
'
1
???
?
nf xfxxx
nnnn
法：依次产生迭代格式，称
? ? 00
000
???? xx)(xf ')f ( x:f ( x )
取线性部分近似代替
Newton 法的几何解释
1
'
1
x ( 0 )
'
0 0 0( ) ( )
y x
fx fx x x
?
? ?
与 轴交点 为第二个近似根,
? ?
0 0 0
'
0 0 0
,( )
( )
( ) ( ) ( )
f
fx
y f x
x x x
fx x x
?
? ? ?
当 在取定后（在真根 附近），过
作 的切线，则切线方程：
?
?
0
?
1
ξ
( ?
0
,f( ?
0
))
'
0 0 0 ( ) ( ) ( )y f xfx x x? ? ?
1
**
1
()
()
( 0
11
2
kk
kk
k
p
k
xx
x x x e x x
k
e
CC
e
p
pp
p
?
?
?
?
?
? ? ?
??
??
??
?
定义：设迭代过程 收敛于方程
的根,如 果迭代误差
当 时成立下列渐进关系式
为常数）
则称该迭代过程是 阶收敛的。
为线性收敛,为超线性收敛，
为平方收敛。
迭代法收敛速度定义
()
1
*
' * " * ( 1 ) * ( ) *
*
( ),( )
( ) ( ) ( ) 0 ; ( ) 0
p
kk
pp
x x x
x
x x x x
xp
??
? ? ? ?
?
?
?
? ? ? ? ?L
定理：对于迭代过程 如果 在所
求根 的邻近连续，并且
则该迭代过程在点 邻近是 阶收敛的。
'*
1
*
()
**
( ) ( ) *
** 1
1
( ) 0 1,( )
()
()
( ) ( ) ( )
!
( ) ( )
()
!!
kk
k
p
p
kk
pp
p k
kk p
k
x x x
xx
x x x x
p
e x
x x x x
p e p
??
?
??
??
? ? ?
?
?
?
? ? ?
? ? ?
? ? ? ? ? ?
证：由于 故 具有局部收敛性。
将 在根 处展开，由条件有
'
1
'
'
2
' ''
''
'
2
''
( )
[,] ( ) 0,
()
()
()
( )
()
( ) ( ) ( )
( ) ( )
( ) 1
( ) (
k
kk
k
x
x a b x
fx
xx
fx
fx
xx
fx
f x f x f x
f x f x
x
f x f
?
?
?
?
?
??
??
??
?? ?
??
? ? ?
??
??
迭代过程的收敛速度依赖于迭代函数 的选
取。如果当 时 则该迭代过程只
可能是线性收敛。
对牛顿公式
其迭代函数为
由于
2
* * ' *
' * *
)
( ) ( ) 0,( ) 0,
( ) 0,
x
x f x f x f x
xx?
??
??
??
?
假定 是 的一个单根，即 则
由上式知 由上述定理知，牛顿法在根 的
邻近至少是平方收敛的。
'
'
1
0
1 0.
( ) 1,( ) ( 1 )
()
( )
( ) 1
1
0.5
k
x
xx
x
x
k
kk
k
xe
f x x e f x e x
f x x e
x x x
f x x
xe
xx
x
x
?
?
?
?
??
? ? ? ?
?
? ? ? ?
?
?
??
?
?
例：用牛顿法解方程
解：
牛顿法迭代函数为
牛顿公式为
可先用二分法或经验确定迭代初值,再按牛
顿公式进行迭代。
Newton法具有收敛快，稳定性好，精度高等优点，是求
解非线性方程的有效方法之一。但它每次迭代均需计算函
数值与导数值，故计算量较大。而且当导数值提供有困难
时,Newton法无法进行。
牛顿法应用举例
2
1
0
1
( ),
2kk k
C x C
C
C x x
x?
??
??
对于给定正数,应用牛顿法解二次方程
即导出求开方值 的计算程序
0
2
2'
1
2
22
1
22
2
1
0
1
( ),( ) 2,( ),
22
1
( 2 2 )
22
11
( 2 ) ( )
22
1
( )
2
k
k k k
kk
k
k k k k k
kk
k k k
kk
kk
k
x
xC C
f x x C f x x x x x
xx
xC
x C x C x x C x C
xx
x x C C x C
xx
x C x C
x
?
?
?
?
?
? ? ? ? ? ? ?
?
? ? ? ? ? ? ? ?
? ? ? ? ?
? ? ?
现证此迭代公式对于初值 都是收敛的。由迭代公式得
同理
22
11
2
1
1
2
0
0
20
0
2
2
11
( ),( )
22
,
,
2,
1
k
k
k
k
k k k k
kk
kk
kk
k
k
k
k
k
x C x C x C x C
xx
x C x C
x C x C
x C x C
x C x C
x C x C
x C x C
q
x C C
q
??
?
?
? ? ? ? ? ?
??
??
? ? ?
??
??
??
??
??
??
??
??
??
??
??
??
? ? ?
??
? ? ?
?
L
由
记
0
0,1,
k
x q k x C? ? ? ? ?对任意 总有,故当 时，
§ 4.弦截法与抛物线法
1
'
1
1
1
1
( ),( ),
()
,,,( ) 0
( ),( ),,( ),
( ),( ) 0 ( ) 0
kk
k
k k k r
k k k r
rr
k
k
f x f x
fx
x x x f x
f x f x f x
p x p x f x
x
x
?
?
?
??
??
?
?
??
?
L
L
L
＋
基本思想：利用一些函数值 来
回避导数值 的计算。
设 是 的一组近似根，利用
函数值 构造插值多项式
并适当选取 的一个根作为 的
新的近似根,这就确定了一个迭代过程，记迭
代函数为,
1
(,,,),
1 2
k k k r
x x x
rr
??
??
L
当 时为弦截法，当 时为抛物线法。
一、弦截法
11
11
1
1
1
1
11
1
1
,( ) 0 ( ),( )
( ) ( ) 0
( ) 0,
( ) ( )
( ) ( ) ( )
()
( ),
( ) ( )
()
k k k k
k
kk
kk
kk
k
k k k k
kk
k
kk
x x f x f x f x
p x p x
f x x
f x f x
p x f x x x
xx
fx
x x x x
f x f x
fx
xx
f
??
?
?
?
??
?
?
?
?
?
?
? ? ?
?
? ? ? ?
?
??
设 是 的近似根，利用
构造一次插值多项式,并用 的根作为
的新的近似根
由
此迭代公式可看作牛顿公式
'
' 1
1
()
( ) ( )
()
k
kk
kk
x
f x f x
fx
xx
?
?
?
?
中的导数
用差商 取代的结果。
弦截法的几何表示
x0 X x* x1 x2 x3
Y
P0
P2
P1
11
0 1 1
,.
,
k k k
k
k
x x x
x x x
x
??
?
弦截法在求 时要用到前面两步的结果
需两个初值,而牛顿切线法在计算 时，只
用到前一步 的值。
弦截法收敛性定理
**
'
01
11
1
*
( ),
( ) 0,
,,
()
( ),
( ) ( )
15
1, 6 1 8,
2
k
k k k k
kk
f x x x x
x f x
xx
fx
x x x x
f x f x
px
?
??
?
? ? ?
? ? ?
? ? ?
? ? ?
?
?
??
定理：假设 在根 的邻域 内
具有二阶连续导数，且对任意 有 又
初值 那么当邻域 充分小时，弦截法
将按阶 收敛到根
证明：（略）
二、抛物线法
12
22
1
( ) 0,,,
( ),( )
,
,.
k k k
k
f x x x x
p x p x
x
??
?
?设已知方程 的三个近似根 以这三
点为节点构造二次插值多项式 并适当选取 的
一个零点 作为新的近似根 这样确定的迭代过程称抛
物线法 也称密勒法
()fx
2()Px
*x
1kx? k
x1kx? 2kx?
抛物线法计算公式
21
1 2 1
12
1 1 2 1
2
2
( ) ( ) [,] ( )
+ [,,] ( ) ( ),
[,,]
[,] + [,,] ( )
()
( ) ( )
k k k k
k k k k k
k k k k
k k k k k k k k
kk
kk
p x f x f x x x x
f x x x x x x x
a f x x x
b f x x f x x x x x
c f x
p x a x x
?
? ? ?
??
? ? ? ?
? ? ?
??
??
?
??
?
?
?
?
? ? ? ?
插值多项式
令
2
2
*
21
1
2
()
4 2
2
4
,,,,
,.
2 sgn ( )
4
k k k
k k k k
k
kk
k
k k k k
k k k k
kk
kk
kk
k k k k
b x x c
b b a c c
x x x
a
b b a c
x x x x x
x x x
cb
xx
b b a c
??
?
??
? ? ?
? ? ? ? ?
??
?
??
??
在 三个近似根中假定 更接近根 故新的近
似根应在 邻近 即 较小于是抛物线计算公式为
*
*
0 1 2
*
*
,( )
,,,,
( ) 0
1,8 4
f x x
x x x x
x f x
x
?
可以证明如果 在其零点 邻近三阶连
续可微 且初值 充分接近 则抛物线法
是收敛的。特别地，若 是方程 的单根，
收敛解为 。
另一方面，在收敛性的证明中虽然要求初
始值充分接近根,但实际计算表明，抛物线
法对初值要求并不苛刻，在初值不太好的情况
下常常也能收敛。缺点是程序较复杂，并在计
算实根的过程中，也常常需要采用复数计算，
增加
( ) 0fx ?
了工作量。因此，抛物线法适用于当初值
不太好时求方程 的复根的情况。
§ 5.代数方程的牛顿法
0
1
0 1 1
0 0 0
12
0 1 2 1
00
( )
( ) 0
( )
( )
( ) ( ) ( ) ( ) ( ),
( );
nn
nn
nn
nn
fx
fx
fx
f x a x a x a x a
x x f x f x x x p x
p x b x b x b x b
ab
?
?
??
??
?
? ? ? ? ?
? ? ? ?
? ? ? ? ?
?
L
L
如果 是多项式，可针对多项式的特性，建立求解
代数方程 的有效解法。
计算函数值 的秦九韶法：
多项式
以 为除式，有
令 代入并与上式
比较同次幂的系数得
00
0 1 0 1
0 0 1 0;
,1 1 ;,1 ;
( ) ( ),
i i i i i i
n n n
ba
a b x b i n b a x b i n
a f x x b f x b
??
?
???
??
? ? ? ? ? ? ? ? ? ?
??
??
? ? ?
??
'
0
"
' 0
0 0 0 0
()
10
0 0 0
'
0
'
00
2
0
( ),
( )
()
( ) ( ) ( ) [ ( ) ( )
2!
()
( ) ] ( ) ( ) ( ),
!
( ) ( ) ( )
( ) ( ) ( ) ( ),
()
n
n
n
fx
fx
fx
f x f x x x f x x x
fx
x x f x x x p x
n
f x p x x x
p x f x x x q x
q x c x c
?
?
? ? ? ? ? ?
? ? ? ? ?
?
? ? ?
??
L
用秦九韶算法求
的台劳展开式,
由此可知，导数 又可看作 用因式
相除得出的余式。令
其中
3
1 3 2
00
01
'
01
,;
,1 1 ;
( ),
n
nn
i i i
n
x c x c
cb
c b x c i n
f x c
?
??
?
?
? ? ?
??
?
? ? ? ? ? ?
?
?
?
?
L
1
0 1 1
1
'
'
00
1
00
1
'
1
( ) 0
()
()
( ) ( );
,1 ;
( ),;
,1 1 ;
( ),
nn
nn
k
kk
k
kk
i i k i
kn
i i k i
kn
f x a x a x a x a
fx
xx
fx
f x f x
ba
b a x b i n
f x b
cb
c b x c i n
f x c
?
?
?
?
?
?
? ? ? ? ? ?
??
??
?
? ? ? ?
?
?
?
?
??
?
? ? ? ? ?
?
?
?
?
L
代数方程的牛顿法：
对
用牛顿公式
其中函数值 与导数值 均可方便求出：
