牛顿-拉夫森(Newton-Raphson)迭代法

牛顿迭代法也称为牛顿-拉夫森(Newton-Raphson)迭代法，它是数值分析中最重要的方法之一，它不仅适用于方程或方程组的求解，还常用于微分方程和积分方程求解。 3.4.1 牛顿迭代法

用迭代法解非线性方程时，如何构造迭代函数是非常重要的，那么怎样构造的迭代函数才能保证迭代法收敛呢？牛顿迭代法就是常用的方法之一，其迭代格式的来源大概有以下几种方式：

2f(x)C[a,b]，对f(x)在点x0[a,b]作泰勒展开： 1设

f''()(xx0)2f(x)f(x0)f'(x0)(xx0)2!

f(x)f(x0)f'(x0)(xx0)。

略去二次项，得到f(x)的线性近似式：

f'(x0)0)，

由此得到方程f(x)0的近似根(假定

即可构造出迭代格式(假定

xx0f(x0)f'(x0)

f'(xk)0)：

xk1xkf(xk)f'(xk) 公式(3.4.1)

这就是牛顿迭代公式，若得到的序列{

xk}收敛于，则就是非线性方程的根。

2 牛顿迭代法也称为牛顿切线法，这是由于f(x)的线

性化近似函数l(x)＝

f(x0)f'(x0)(xx0)是曲线y＝

f(x)过点(x0,f(x0))的切线而得名的，求f(x)的零点代之

以求l(x)的零点，即切线l(x)与x轴交点的横坐标，如右图所示，这就是牛顿切线法的几何解释。实际上，牛顿迭代法

也可以从几何意义上推出。利用牛顿迭代公式，由

xk得到xk1，从几何图形上看，就是过点

(xk,f(xk))作函数f(x)的切线lk，切线lk与x轴的交点就是xk1，所以有

f(xk)f'(xk)xkxk1，整理后也能得出牛顿迭代公式： f(xk)f'(xk)。

3 要保证迭代法收敛，不管非线性方程f(x)0的形式如何，总可以构造：

x(x)xk(x)f(x) (k(x)0)

作为方程求解的迭代函数。因为：'(x)1k'(x)f(x)k(x)f'(x)

xk1xk而且

'(x)在根附近越小，其局部收敛速度越快，故可令：'()0

若f'()0(即根不是f(x)0的重根)，则由'()0得：

k()1f'()，

f(xk)1xk1xkf'(xk)。 f'(x)，则也可以得出迭代公式：因此可令

4 迭代法的基本思想是将方程f(x)0改写成等价的迭代形式x(x)，但随之而来的

k(x)问题却是迭代公式不一定收敛，或者收敛的速度较慢。运用前述加速技巧，对于简单迭代过程

xn1xnf(xn)，其加速公式具有形式：

xn1(xn)xnxn1(xn1xn)x(xn) 11，其中n1xn1xnf(xn)L

记L1，上面两式可以合并写成：

f(x)L。 这种迭代公式称作简单的牛顿公式，其相应的迭代函数是：

需要注意的是，由于L是'(x)的估计值，若取(x)xf(x)，则'(x)实际上便是

(x)xf'(x)的估计值。假设f'(x)0，则可以用f'(x)代替上式中的L，就可得到牛顿法的迭代

xn1xn公式：

牛顿迭代法实质上是一种线性化方法，其基本思想是将非线性方程逐步归结为某种线性方程来求解。

3.4.2 牛顿迭代法的收敛性

f(xn)f'(xn)。

f(x)f'(x)而获得的不动点迭代格式。这样就可以应用牛顿迭代公式可以看成是由

不动点迭代的收敛原则，只须证明在根附近的迭代函数是一个压缩映象。由于：

(x)x[f'(x)]2f(x)f\"(x)f(x)f\"(x)'(x)1[f'(x)]2[f'(x)]2，

这里的根是单根，即f()0且f'()0，于是：

'()f()f\"()02[f'()]。

那么由'(x)的连续性可知，存在一个邻域(,)，对这个邻域内的一切x，有：

'(x)q，其中O＜q＜1，因此(x)为区间(,)上的一个压缩映象，于是有以下

结论：

2f(x)C[a,b]，x*是f(x)0的精确解，且f'(x*)0，则存在x* 定理 3.4.1 设

x(x*,x*)，迭代序列{xn}收敛于

的邻域(x*,x*)，对于任何迭代初值0x*。

牛顿迭代法具有较高的收敛速度，它的收敛阶数为p＝2；而牛顿迭代法的局部收敛性较

强，只有初值充分地接近x*，才能确保迭代序列的收敛性。为了放宽对局部收敛性的限制，必须再增加条件建立以下收敛的充分条件。

2f(x)C[a,b]，且满足：在区间[a,b]上， 定理 3.4.2 设

⑴ f(a)f(b)0；⑵ f'(x)0；

x[a,b]，满足条件：f(x0)f\"(x0)0

⑶ f\"(x)不变号；⑷ 0则牛顿迭代序列n，单调地收敛于方程f(x)0的唯一解x*。

由条件⑴至条件⑷可归结为四种情形： ① f(a)0，f(b)0，f'(x)0，f\"(x)0；

② f(a)0，f(b)0，f'(x)0，f\"(x)0； ③ f(a)0，f(b)0，f'(x)0，f\"(x)0；

④ f(a)0，f(b)0，f'(x)0，f\"(x)0。

对定理的几何意义作如下说明：条件⑴保证了根的存在性；条件⑵表明函数单调变化，在区间[a,b]内有惟一的根；条件⑶表示函数图形在区间[a,b]上的凹向不变。条件⑶和条件⑷一起保证了每一次迭代值都界于区间[a,b]内。

{x}

在不满足上述收敛充分条件时，有可能导致迭代值远离所求根的情况或死循环的情况(如下图所示)。

【例3.4.1】对于给定的正数a，用牛顿法建立求平方根的收敛迭代公式。 解 令f(x)xa，(x＞0)，则f(x)0的正根就是a。

2xna1axn1xn(xn)2xn2xn， 公式(3.4.2) 用牛顿法求解的迭代公式是：

由于当x＞0时，f'(x)2x＞0，f''(x)2＞0，故由收敛定理可知，对于任意满足条

2xa的初始近似值，由选代公式所产生的序列必定收敛于平方根a。公式(3.4.2)是件0计算平方根的准确而有效的计算方法。

3.4.3 牛顿迭代法的变形

用牛顿法解方程，虽然在单根附近具有较快的收敛速度，但它有个明显的缺点，就是每次都要计算导数f'(x)，当f(x)比较复杂时，计算f'(x)可能很困难。下面介绍两种克服这种困难的方法，另外还介绍一种扩大牛顿迭代法初值选择范围的方法，它们统称为变形的牛顿迭代法。

1 简化牛顿法

f'(x0)代

为避免频繁地计算导数值f'(x)，可将它取为固定值，比如在牛顿迭代公式中用

替

f'(xn)，即在迭代过程中始终保持分母不变，则有简化牛顿迭代公式(或固定斜率切线xn1xnf(xn)f'(x0) 公式(3.4.3)

法)：

其几何意义如下图所示，这时除第一次迭代仍为曲线的切线外，其余皆为该切线的平行线。简化牛顿法避免了每次计算导数值。

更一般地，若取

f'(xn)L,则迭代公式成为：

xn1xnf(xn)L，称为推广的简化切线法。这时L值应

f'(x)1L

满足下式：

'(x)10满足上式的L为：

切线法是收敛的。该迭代形式在参数法里也曾得到过。

2 由牛顿法的收敛性定理知，牛顿法对初始值的选取要求是很高的。一般地说，牛顿法只有局部收敛性。当初始值取得离根太远时，迭代将不收敛，而一旦初始值进入收敛域内，牛顿

f'(x)2L，可见当L与f'(x)同号且满足上述不等式时，推广的简化

法就有平方收敛的速度，为了扬长避短，扩大初始值选取的范围，下面介绍牛顿法的一种改进——牛顿下山法。

xn1xn将牛顿法的迭代公式修改为：其中，是一个参数，的选取应使

f(xn)f'(xn) 公式(3.4.3)

f(xn1)＜

f(xn)成立，当

f(xn1)＜1或

xn1xn＜

2，就停止迭代，且取x*xn1，其中1，2为事先给定的精度，1称为残量精确度，2为根的误差限；否则再减，继续迭代。按上述迭代过程计算，实际上得到了一个以零为下界的严格单调下降的函数值序列，这个方法就称为牛顿下山法。称为下山因子，要求满足0＜

1，称为下山因子下界，为了方便，一般开始时可简单地取1，然后逐步分半

112，且使f(xn1)＜f(xn)成立。

减小，即可选取1，2，2，…，

牛顿下山法计算步骤可归纳如下： ⑴ 选取初始近似值⑶ 计算⑷ 计算① 若

x0；⑵ 取下山因子1；

f(xn)f'(xn)

xn1，

xn1xnf(xn1)，并比较f(xn1)与f(xn)的大小，分以下两种情况：

＜

f(xn1)f(xn)，则当

xn1xn＜2时，则就取x*xn1，计算过程结束；当

xn1xn②若则，若

＞2时，则把xn1作为新的xn值，并重复回到⑶。

f(xn1)f(xn)且f(xn1)＜1，就取x*xn，计算过程结束；否

，则当

f(xn1)1xn1xn1，而

时，则把

加上一个适当选定的小正数，即取

作为

n11时，则将下山因子缩小一半，并，且新的n值，并转向⑶重复计算；当

转向⑶重复计算。

牛顿下山法不但放宽了初值的选取，且有时对某一初值，虽然用牛顿法不收敛，但用牛顿下山法却有可能收敛。一般来说，牛顿下山法不再有平方收敛速度，它的优点在于可能将原来收敛域以外的初始值，经过几次迭代后拉入收敛域内。

xf(x)x例如，已知方程f(x)xx1＝0的一个根为x*1.32472，若取初值0＝0.6，用牛x顿法计算得到的第一次近似值x117.9反而比0更偏离根。若改用牛顿下山法，当取下山因

子

3125时，可得x11.14063，修正后的迭代序列收敛。（沈建华P138）（史万明P48）

3.4.4 弦截法

1 单点弦截法

f(xn)f(x0)xnx0为避免牛顿迭代法中导数的计算，可用平均变化率：

来近似代替

f'(xn)，于是得到如下迭代公式：

f(xn)xf(xn)xnf(x0)(xnx0)0f(xn)f(x0)f(xn)f(x0) 公式(3.4.4)

称为单点弦截法。单点弦截法具有明显的几何意义，它

xn1xnx0，y0)与点B(xn，yn)的直线，代替

x曲线求取与横轴交点作为近似值n1的方法，以后再过

是用联结点A((

x0，y0)与(xn1，yn1)两点，作直线求取与横轴的

x交点作为n2，等等。其中(0，0)是一个固定点，

称为不动点，另一点则不断更换，故名单点弦截法。可以证明，单点弦截法具有收敛的阶r＝1，即具有线性收敛速度。

2 双点弦截法

若把单点弦截法中的不动点(法的迭代公式：

xyx0，y0)改为变动点(xn1，yn1)，则得到下面的双点弦截

xn1xnf(xn)xf(xn)xnf(xn1)(xnxn1)n1f(xn)f(xn1)f(xn)f(xn1) 公式(3.4.5)

用弦截法求根的近似值，在几何上相当于过点(弦，然后用弦与x轴的交点的横坐标

xk1，f(xk1))，和点(xk，f(xk))作

xk1时，不仅用到点xk上xk1及其函数值，这就

xk1作为x*的新的近似值。由于在双点弦截法中，构造

的迭代公式在计算新的近似值

k，而且还用到点的函数值

有可能提高迭代法的收敛速度。

f(x)与牛顿法一样，如果函数yf(x)在其根x*附近具有直到二阶的连续导数，且f'(x)0，则弦截法具有局部收敛性，即当初始近似值充分接近于x*时，按双点弦截法迭代公式得到的迭代序列收敛于根x*。可以证明弦截法具有超线性收速度，且收敛阶数为P＝

1.618。双点弦截法迭代公式与前面介绍的单点迭代法有明显的不同，就是在计算到前两步的计算结果n、n1，所以在使用迭代公式前，必须先给出两个初始值此，这种迭代法也称两步法，而单点迭代法称为一步法。

xn1时要用

xxx0、x1，因