(
x
)
n
lim
n
x
n
若
{x
}
n
收敛，即
lim xn x*，则：
n
x* (x*) f (x*) 0
迭代过程的几何表示
x (x) :
y x 交点即真根。
y (x)
yx
y
Q1
Q2
P* P2
O x* x2
P1
x1
y (x)
P0
x0
x
例：求方程 f (x) x3 x 1 0 在x0 1.5附近的根x*. 解：（1） 将方程改写为 x 3 x 1
第十章 方程求根
求解非线性方程
f (x) 0 f 是非线性函数，
例：代数方程
a x a x a x a f (x) n
n1 L
0, n 1。
n
n1
1
0
例: 超越方程
f (x) ex sin x 0
§1. 非线性方程实根的对分法(二分法)
设 f (x) 在[a,b] 上连续且 [a,b] 有且仅有一个根又
xn1 (xn ) (n 0,1,L )
均收敛于x*，并有
x* xn
Ln 1 L
x1 x0
收敛充分性定理(一、2)
证：由条件（2）知(x)在[a, b]上连续。 令 (x) x (x),则 (x)在[a,b]上连续，且
(a) a (a) 0, (b) b (b) 0 故存在 [a,b]，使得（） 0,即 （）, 所以方程x (x)在[a,b]内有根。
可先用二分法或经验确定迭代初值x0 0.5，再按牛
顿公式进行迭代。
Newton法具有收敛快，稳定性好，精度高等优点，是求 解非线性方程的有效方法之一。但它每次迭代均需计算函 数值与导数值，故计算量较大。而且当导数值提供有困难 时， Newton法无法进行。
牛顿法应用举例
对于给定正数C，应用牛顿法解二次方程 x2 C 0
依此类推，得
xn x* Ln x0 x*
因 0 L 1, 所以
lim
n
xn
x*
即对任意初值x0 [a, b], 迭代序列xn均收
敛到有
xk 1 xk (xk ) ( xk 1) L xk xk 1
L Lk x1 x0
收敛充分性定理(一、4)
依次产生迭代格式，称 Newton 法：
x x x f ( )
n1
n
n
f ' (xn),
n 0, 1, 2,
Newton 法的几何解释
当 x0 在取后（在真根 附近），过 x0, f (x0)
作 f (x) 的切线，则切线方程：
y
f (x0)
f
'
(x0)(x x0)
(0，f(0))
改进
x%k1 ( xk )
xk1 ( x%k1)
xk 1
xk 1
(xk 1 x%k 1)2 xk 1 2x%k 1 xk
§3. Newton 法
非线性问题的最简单解法是线性近似.
将非线性方程线性化，以线性方程的解逐步逼
近非线性方程的解，这就是Newton法的基本思 想
f ( x ) 0 在真根附近 x 点展开成 Taylor 级数：
由此建立迭代公式 xk1 3 xk 1 (k 0,1, 2L )
k0 1
2L 7
8
xk 1.5 1.35721 1.33086 L 1.32472 1.32472 迭代收敛。
（2） 若将方程改写为 x x3 1
建立迭代公式 k0
xk1 xk3 1.
1
2L
xk 1.5 2.375 12.39 L 迭代不收敛。
于是，对任意正整数n, p,有
x x x x x x x x
L
n p
n
n p
n p1
n p1
n p2
n1
n
L x x L x x L x x n p1 n p2 L n
1
0
1
0
1
0
L L L x x n( p1 p2 L 1)
1
0
1 Lp
1 L
Ln
x1
x0
令p ,得
x x x x* Ln
3),
若
f
ai
2
bi
0，则得到根
x ai bi . 2
二分法的收敛性
f (x)
二分法产生一个有根区间：
[a, b]
[a1,b1] L
[a
,
n
b
]
n
[a
,
n
b
]
n
区间长度：
a1 a x*
b1
x0
b
b a b a 1 ( ) L
n
n2
n 1
n 1
a b 当n 足够大时，取近似值
1
2n
n 1 L 1 0
收敛充分性定理(二、1)
定理. 设函数 (x)在区间[a, b]上满足条件 （1）对任意x [a, b]，都有a (x) b;
(2)存在常数0 L 1, 使得对一切x [a, b],都有
'(x) L
则方程x (x)在[a, b]内有唯一的根x*,且对任何
初值x0 [a, b], 迭代序列
取。如果当 x [a, b]时 ' (x) 0,则该迭代过程只
可能是线性收敛。
对牛顿公式
xk 1 xk
f (xk ) f ' (xk )
其迭代函数为
(x)
x
f (x) f '(x)
由于
'(x)
f (x) f '' (x)
f
'
2
( x)
假定x*是f (x)的一个单根，即f (x* ) 0, f ' (x*) 0,则
n
n p
n p1
n p1
n p2
n1
n
（L L x x x x
p1 p2 L 1） 1
n1
n 1 L n1
n
令p ,得
x x x x * 1
n 1 L n1 n
x x 可通过检查 来判断迭代过程应否终止。
n1
n
例：用简单迭代法求方程 f (x) x2 x 1 0 的根。
解：因 f (1.5) 0.25 0,
f (2) 1 0
[1.5, 2] 为有根区间。
（1）x x 1 1(x) 因 1.5 1.5 1 1(x) 2 1 2
且
1' (x) 2
1 1 1 x 1 2 2.5 3.162
(2)
x 1 1 x
2(x)
因
1.5
1
1 2
2
(
x)
1
1 1.5
2
且
' 2
(
x)
1 x2
1 1.52
则称该迭代过程是p阶收敛的。 p 1为线性收敛，p 1为超线性收敛， p 2为平方收敛。
定理：对于迭代过程xk1 (xk ),如果 ( p) (x)在所
求根x*的邻近连续，并且
' (x*) "(x*) L ( p1) (x*) 0; p (x*) 0
则该迭代过程在点x*邻近是p阶收敛的。
xn1 (xn ) (n 0,1, 2,L )
收敛于x* .
收敛充分性定理(三、2)
证：因 ' (x)在O(x*, *)内连续，且 ' (x) 1,故存 在正数L 1, *, 使得对x [x* , x* ]，有
'(x) L 1 另一方面，由 (x*) x*, 又有
(x) x* (x) (x*) L x x* 即 (x) [x* , x* ]。由上面定理知，迭代序列 xn1 (xn )收敛于x*。
xn1 ( xn ) (n 0,1,L )
均收敛于x*，并有
x* xn
Ln 1 L
x1 x0
收敛充分性定理(二、2)
证：设x, y为[a,b]上任意两点，由微分中值
定理，在x, y之间至少存在一点，使得 (x) ( y) '( )(x y)
(x) ( y) '( )(x y)
f(x) f( x0 ) (x- x0 ) f ' ( x0 )
xx0 2
f ('' x0 )
2!
取线性部分近似代替
f(x) 0 : f(x ) f ' (x )xx 0
0
0
0
解出x作为近似根x ： 1 x1 x0 f( x0 ) f (' x0 ) ( f (' x0 ) 0)
实际用迭代法计算时，先用对分区间法求较好的初值， 然后再进行迭代。
迭代法加速（埃特金方法）（1）
设x0是根x*的某个预测值，通过两次迭代校正
有
x1 ( x0 )
x2 ( x1)
由微分中值定理，有
x1 x* (x0 ) (x* ) ' (1)(x0 x* ) x2 x* (x1) (x* ) ' (2 )(x1 x* ) 假定 ' (x)改变不大，近似地取某个近似值L,
1 2.25
根据定理，任取x0 [1.5, 2],由这两种等价方程所构造的 简单迭代方法都收敛，且第一种所产生的迭代序列收敛较快。
收敛充分性定理(三、1)
定理：如果函数 (x)在x*的一邻域O(x*, *) 内连续可微，x*为方程x (x)的根，且 ' (x) 1,则存在正数 , *,使得对任意 x0 [x* , x* ], 迭代序列