跳至内容
Topos Uranos
中文 (中国)

牛顿-拉弗森方法

摘要

波尔查诺定理保证：变号的连续函数有根，而二分法每二分一次便多得到一个二进制位，从而确定根的位置。本课研究一种在奏效时快得多的方法：牛顿-拉弗森方法，它用切线代替函数图像，并以切线与横轴的交点作为新的近似值。这样得到的近似值对整数 n≥0n \geq 0 逐个定义，其极限借助自变量趋于无穷大时极限的定义来理解，无需数列理论。本课利用下凸性证明：若导数不为零且函数下凸或上凸，则从适当一侧出发的迭代值逼近根而不越过它，并收敛于它；又利用中值定理证明：可以计算的函数值界定了未知的到根的距离。随后通过数值例子说明正确的位数每迭代一次便翻一番，并说明方法失效的几种情形：导数为零、循环、发散。这些问题不用除法计算立方根与倒数，打破一个循环，研究一个二重根，并求出反正切的收敛与发散之间的确切分界。

学习目标

  1. 计算可导函数的牛顿-拉弗森迭代值，并认出它们就是切线与横轴的交点。
  2. 在导数不为零且函数下凸或上凸时证明迭代值的单调收敛，并从适当的一侧选取初始点。
  3. 用函数值和导数的一个下界来界定近似值到根的距离。
  4. 认识方法失效的几种情形，并在速度与可靠性方面将它与二分法比较。

迭代

设 ff 是一个可导函数，要求它的根 rr，并设 x0x_0 是第一个近似值。在 x0x_0 附近，ff 的图像与它的切线 y=f(x0)+f′(x0)(x−x0)y = f(x_0) + f'(x_0)(x - x_0) 相近，这依据的是关于作为极限的导数的那一课中切线的定义；用关于高阶导数与微分的那一课中的微分来说，增量 f(x0+Δx)−f(x0)f(x_0 + \Delta x) - f(x_0) 与 f′(x0)Δxf'(x_0) \Delta x 相近。若 f′(x0)≠0f'(x_0) \neq 0，切线与横轴只交于一点，自然取这一点为新的近似值：令切线方程等于零即可得到它。从所得的点出发重复这一过程，就是牛顿-拉弗森方法。

定义牛顿-拉弗森迭代值

设 ff 是在区间 II 上可导的函数，x0x_0 是 II 中的一点。从 x0x_0 出发的牛顿-拉弗森迭代值是逐个定义的数，定义式为

xn+1=xn−f(xn)f′(xn)x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}

这里要求 xnx_n 属于 II 且 f′(xn)≠0f'(x_n) \neq 0。若这些条件对每个整数 n≥0n \geq 0 都成立，迭代值便构成一个函数 n↦xnn \mapsto x_n，它定义在非负整数集上，而这个集合没有上界，因此关于自变量趋于无穷大时的极限的那一课中自变量趋于无穷大时极限的定义适用于它。称迭代值收敛于 rr，是指 lim⁡n→∞xn=r\lim_{n \to \infty} x_n = r，也就是

(∀ε>0)(∃M)(∀n≥0)(n>M→∣xn−r∣<ε)(\forall \varepsilon > 0)(\exists M)(\forall n \geq 0)\left(n > M \rightarrow \abs{x_n - r} < \varepsilon\right)

每个迭代值都是 (xn,f(xn))(x_n, f(x_n)) 处的切线与横轴的交点：令 y=0y = 0、x=xn+1x = x_{n+1}，代入方程 y=f(xn)+f′(xn)(x−xn)y = f(x_n) + f'(x_n)(x - x_n) 并解出，就得到定义中的公式。这个方法不像二分法那样要求函数在给定区间上变号，而是要求函数可导，并且导数在方法经过的点处不为零；作为代价，没有什么能事先保证迭代值会逼近某个根。下文给出保证这一点的条件。

例题2 的平方根

对 f(x)=x2−2f(x) = x^2 - 2 应用牛顿-拉弗森方法，初始点为 x0=2x_0 = 2。各步展示前三条切线及其与横轴的交点。

证明

  1. xn+1=xn−xn2−22xn=12(xn+2xn),x1=32x_{n+1} = x_n - \frac{x_n^2 - 2}{2x_n} = \frac{1}{2}\left(x_n + \frac{2}{x_n}\right), \qquad \resaltar{x_1 = \frac{3}{2}}

    导数为 f′(x)=2xf'(x) = 2x，当 x>0x > 0 时它不为零。迭代取如下形式：每个近似值都是前一个近似值与 22 除以前一个近似值所得之商的平均值。从 x0=2x_0 = 2 出发，切线 y=2+4(x−2)y = 2 + 4(x - 2) 与横轴交于 32\frac{3}{2}。

  2. x2=12(32+43)=1712≈1.416667x_2 = \frac{1}{2}\left(\frac{3}{2} + \frac{4}{3}\right) = \resaltar{\frac{17}{12}} \approx 1.416667

    在 (32,14)\left(\frac{3}{2}, \frac{1}{4}\right) 处的切线与横轴的交点离根近得多。

  3. x3=12(1712+2417)=577408≈1.4142157,2≈1.4142136x_3 = \frac{1}{2}\left(\frac{17}{12} + \frac{24}{17}\right) = \resaltar{\frac{577}{408}} \approx 1.4142157, \qquad \sqrt{2} \approx 1.4142136

    第三个迭代值已有五位正确的小数。误差 xn−2x_n - \sqrt{2} 约为 0.590.59、0.0860.086、0.00250.0025 和 0.00000210.0000021：每一个都与前一个的平方同阶。

这个例子中，误差的平方关系是精确的。由迭代公式，对每个 xn>0x_n > 0，得到如下恒等式：

xn+1−2=xn2−22 xn+22xn=(xn−2)22xnx_{n+1} - \sqrt{2} = \frac{x_n^2 - 2\sqrt{2}\,x_n + 2}{2x_n} = \frac{\left(x_n - \sqrt{2}\right)^2}{2x_n}

因此，从第一个起，所有迭代值都大于或等于 2\sqrt{2}；而若 xn≥1x_n \geq 1，后一个误差至多是当前误差平方的一半：第四个迭代值 x4=665 857470 832x_4 = \frac{665\,857}{470\,832} 有十一位正确的小数。把 22 换成任意正数，同样的过程就能计算平方根；它早已出现在亚历山大的希罗于公元 1 世纪所著的测量术中，因此也称为希罗方法。

艾萨克·牛顿于 1669 年在一份以手稿形式流传、1711 年才出版的著作中描述了他求解多项式方程的方法；约瑟夫·拉弗森于 1690 年发表了一个更简单的阐述，托马斯·辛普森则于 1740 年把它作为求解一般方程的迭代方法提出。