10.4 牛顿迭代法
一 牛顿法及其收敛性
牛顿法是一种线性化方法，其基本思想是将非线性方 程 f ( x) 0逐步归结为某种线性方程来求解. 设已知方程 f ( x) 0 有近似根 xk（假定 f ( xk ) 0)， 将函数 f ( x) 在点 xk 展开，有
f ( x) f ( xk ) f ( xk )( x xk ),
x
表7 5 计算结果 k 0 1 2 3 xk 0.5 0.57102 0.56716 0.56714
5
二 牛顿法应用举例 对于给定的正数 C，应用牛顿法解二次方程
x 2 C 0,
可导出求开方值 C 的计算程序
xk 1 1 C ( xk ). 2 xk
（3.5）
这种迭代公式对于任意初值 x0 0 都是收敛的. 事实上，对（3.5）式施行配方手续，易知
10
在（3.7）中取C
1 ，则称为简化牛顿法，这 f ( x0 )
类方法计算量省，但只有线性收敛，其几何意义是用平行 弦与 x 轴交点作为 x *的近似. 如图7-4所示.
图7-4
11
（2）
牛顿下山法.
牛顿法收敛性依赖初值 x0的选取. 如果x0 偏离所求根 x* 较远，则牛顿法可能发散.
xk 1 xk 1 1 C ( xk 2 xk C 1 ( xk 2 xk C )2 ; C )2 .
6
以上两式相除得
xk 1 xk 1 xk C x C k C . C
2
据此反复递推有
xk 1 xk 1 x0 C x C 0 C C .
14
x1 17.9，它不满足条件（3.10）.
通过 逐次取半进行试算，当 1 / 32时可求得 x1 1.140625 . 此时有 f ( x1 ) 0.656643 ，而 f ( x0 ) 1.384 显然 f ( x1 ) f ( x0 ) . 由 x1 计算 x2 , x3 , 时 1 , 成立. 计算结果如下 ：
f ( xk ) f xk 1 p1 ( x) f ( xk ) ( x xk ). xk xk 1
（5.1）
21
因此有
xk 1 f ( xk ) xk ( xk xk 1 ). f ( xk ) f ( xk 1 )
（5.2）
（5.2）可以看做牛顿公式
k
15
四 重根情形 设 f ( x) ( x x*)m ( x)，整数 m 2, ( x*) 0 ，则 x *为方程 f ( x) 0 的 m 重根，此时有
f ( x*) f ( x*) f
( m 1)
( x*) 0, f
m
( x*) 0.
从而可构造迭代法
xk 1 xk f ( xk ) f ( xk ) [ f ( xk )]2 f ( xk ) f ( xk ) ( k 0,1, ),
（3.14） 它是二阶收敛的. 例7.3.3 方程x 4 4 x 2 4 0 的根 x* 用上述三种方法求根. 解 先求出三种方法的迭代公式：
于是方程 f ( x) 0 可近似地表示为
f ( xk ) f ( xk )( x xk ) 0.
（1）
这是个线性方程，记其根为 xk 1 ，则 xk 1的计算公式为
1
xk 1 xk
f ( xk ) f ( xk )
( k 0,1, ),
（2）
这就是牛顿(Newton)法. 牛顿法的几何解释. 方程 f ( x) 0 的根 x * 可解释为曲线 y f ( x) 与 x 轴 的交点的横坐标（图7-3). 设 xk 是根 x *的某个近似值， 过曲线 y f ( x) 上横坐标为 xk 的点 Pk 引切线，并将该切线与 x 轴的交点的横坐标 xk 1 作为 x * 的新的近似值.
.
用迭代法
f ( xk ) f ( xk ) (k 0,1, )
xk 1 xk m
（3.13）
求 m重根，则具有2阶收敛，但要知道 x *的重数 m .
构造求重根的迭代法，还可令 ( x) f ( x) / f ( x) ， 若 x* 是 f ( x) 0 的 m重根，则
例如，用牛顿法求方程
x 3 x 1 0.
（3.8）
在 x 1.5 附近的一个根 x *. 设取迭代初值 x0 1.5，用牛顿法公式
xk 1
3 xk xk 1 xk 2 3 xk 1
（3.9）
x3 1.32472.
计算得
x1 1.34783, x2 1.32520,
xk 1 xk f ( xk ) f ( xk ) xk xk 1
（3.11）
其中 (0 1) 称为下山因子，（3.11）即为
xk 1 f ( xk ) xk f ( xk ) ( k 0,1, ),
（择下山因子时从 1 开始，逐次将 减半进行试 算，直到能使下降条件（3.10）成立为止. 若用此法解方程（3.8），当 x0 0.6 时由（3.9）求得
由于
g ( x)
f ( x) f ( x) . 2 [ f ( x)]
假定 x *是 f ( x) 的一个单根，即 f ( x*) 0, f ( x*) 0 ， 则由上式知 g ( x*) 0 ，于是依据可以断定， 牛顿法在根 x * 的邻近至少是平方收敛的.
3
又因
ek 1 ekp
例7.3.1 解
用牛顿法解方程
xex 1 0.
（3.4）
这里牛顿公式为
xk 1 xk e x k xk , 1 xk
取迭代初值 x0 0.5 ，迭代结果列于表7-5中.
4
所给方程（3.4）实际上是方程 x e 的等价形式. 若 用不动点迭代到同一精度要迭代28次，可见牛顿法的收敛速 度是很快的.
2k
（3.6）
记
q x0 x0 C , C
整理（3.6）式，得
7
xk
C 2 C
q2
k
1 q
2k
.
对任意 x0 0，总有 q 1，故由上式推知，当 k 时 xk C ，即迭代过程恒收敛. 例7.3.2 求 115. 解 取初值 x0 10，对 C 115 按（3.5）式迭代3次 便得到精度为 10 6 的结果 （见表7-6). 由于公式（3.5）对任意 初值 x0 0 均收敛，并且收 敛的速度很快，因此可取确定 的初值如 x0 1 编成通用程序.
x2 1.36181, x3 1.32628, x4 1.32472,
均能使条件（3.10）
f ( x2 ) 0.1866; f ( x3 ) 0.00667; f ( x4 ) 0.0000086.
x4 即为 x *的近似. 一般情况只要能使条件（3.10）成立， 则可得到 lim f ( xk ) 0 ，从而使 {xk } 收敛.
xk 1
2 xk 2 xk . 4 xk
2 是二重根，
（1） 牛顿法
18
（2） 用（3.13）式
xk 1
2 xk 2 xk . 2 xk 2 xk ( x k 2) xk . 2 xk 2
（3） 用（3.14）式 xk 1
取初值 x0 1.5，计算结果如表7-7.
迭代3次得到的结果 x3 有6位有效数字.
12
但如果改用 x0 0.6 作为迭代初值，则依牛顿法公式 （3.9）迭代一次得
x1 17.9.
这个结果反而比 x0 0.6 更偏离了所求的根 x* 0.32472 . 为了防止迭代发散，对迭代过程再附加一项要求，即 具有单调性：
f ( xk 1 ) f ( xk ) .
表7 6 计算结果 k 0 1 2 3 4 xk 10 10.750000 10.723837 10.723805 10.723805
8
三 简化牛顿法与牛顿下山法
牛顿法的优点 收敛快，
牛顿法的缺点 每步迭代要计算 f ( x ) 及 f ( x ) ，计算量较大 k k 且有时 f ( xk ) 计算较困难， 二是初始近似 附近才能保证收敛， x0只在根x * 一
表7 7 三种方法数值结果 k 1 2 3 xk x1 x2 x3 方法（ 1 ） 1.458333333 1.436607143 1.425497619 方法（2） 1.416666667 1.414215686 1.414213562 方法（3 ） 1.411764706 1.414211438 1.414213562
如 x0 给的不合适可能不收敛.
9
为克服这两个缺点，通常可用下述方法. （1） 简化牛顿法，也称平行弦法.
xk 1 xk Cf ( xk )
其迭代公式为 （3.7）
C 0,1 ,.
迭代函数 ( x) x Cf ( x). 若在根 x * 附近成立 ( x) 1 Cf ( x) 1 ，即取 0 Cf ( x) 2，则迭代法（3.7）局部收敛.
满足这项要求的算法称下山法.
（3.10）
将牛顿法与下山法结合起来使用，即在下山法保证函 数值稳定下降的前提下，用牛顿法加快收敛速度. 将牛顿法的计算结果
13
xk 1 xk
f ( xk ) f ( xk )
与前一步的近似值 xk 适当加权平均作为新的改进值
xk 1 xk 1 (1 ) xk ,
只要 f ( xk ) 0仍可用牛顿法（3.2）计算，此时迭代函数
g ( x) x f ( x) f ( x)