查看“︁牛顿法”︁的源代码

'''牛顿法'''（Newton's method）用函数在当前点的切线预测零点，再到新位置重新计算切线。对于适当光滑的函数，从单根附近开始，这种迭代往往能很快得到精确近似。

== 从二开始求平方根二 ==
令 <math>f(x)=x^2-2</math>。我们知道正根在一和二之间，先取 <math>x_0=2</math>。此时函数值为二，导数 <math>f'(2)=4</math>，所以切线方程为
<math display="block">y=2+4(x-2).</math>
把切线的高度设为零，得到 <math>x=2-2/4=1.5</math>。这比初值二更接近真正的零点，便把它作为下一次近似。

[[File:Gezhi-newton-tangent-theme.svg|frame|center|alt=曲线x平方减二在二二处的切线与横轴相交于一点五，区别于根号二|对 x²−2，在 x₀=2 处用切线预测下一次近似 x₁=3/2；它仍不等于真正的根 √2。]]

图中先沿竖线走到曲线上的 <math>(2,2)</math>，再沿该处切线走到横轴，交点是 <math>1.5</math>。切线与原曲线的零点并不重合，所以这只是一次预测；下一轮要在 <math>x=1.5</math> 处重新作切线。

对一般当前点 <math>x_n</math>，切线写成 <math>y=f(x_n)+f'(x_n)(x-x_n)</math>。若 <math>f'(x_n)\ne0</math>，令 <math>y=0</math> 并解出 <math>x</math>，便得到
<math display="block">x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}.</math>
分子是当前离零有多高，分母是切线斜率，两者之比给出横向修正量。斜率很小时，修正可能很大；斜率为零而函数值非零时，切线平行横轴，这一步没有交点。

== 把切线公式化成可重复计算的步骤 ==
对 <math>f(x)=x^2-2</math>，导数为 <math>2x</math>，公式化简为
<math display="block">x_{n+1}=x_n-\frac{x_n^2-2}{2x_n}=\frac12\left(x_n+\frac2{x_n}\right).</math>
从二开始，前几轮如下。每一轮都将上一行的结果代回这个式子。

<div class="math-table-scroll" role="region" aria-label="从二出发计算平方根二的牛顿迭代" tabindex="0">
{| class="wikitable"
! 编号 !! 精确或近似值 !! 本轮计算
|-
| 0 || 2 || 初值
|-
| 1 || <math>3/2=1.5</math> || <math>(2+2/2)/2</math>
|-
| 2 || <math>17/12\approx1.4166666667</math> || <math>(3/2+4/3)/2</math>
|-
| 3 || <math>577/408\approx1.4142156863</math> || <math>(17/12+24/17)/2</math>
|-
| 4 || 约 1.4142135624 || 再次代入，误差约为 <math>1.6\times10^{-12}</math>
|}
</div>

设 <math>r=\sqrt2</math>。由于 <math>r^2=2</math>，下一步误差可以直接展开：
<math display="block">x_{n+1}-r=\frac{x_n^2+r^2-2x_nr}{2x_n}=\frac{(x_n-r)^2}{2x_n}.</math>
上一步误差被平方了，正是表中精度快速提高的原因。例如误差已经小于百分之一，再平方就达到万分之一的量级，且还要除以约 <math>2\sqrt2</math>。

这个恒等式也证明收敛。对任意正初值，下一步不小于 <math>r</math>；若当前 <math>x_n>r</math>，则 <math>2/x_n<x_n</math>，两者平均值小于 <math>x_n</math>。所以从第一步起，序列在根上方单调下降。其极限 <math>L>0</math> 满足 <math>L=(L+2/L)/2</math>，因此 <math>L^2=2</math>，只能是正根。

还可从当前值得到根区间。若 <math>x_n\ge r</math>，则 <math>2/x_n\le r\le x_n</math>。这对上下界比仅观察小数是否稳定更直接地说明精度。对任何 <math>A>0</math>，同样的证明适用于 <math>x_{n+1}=(x_n+A/x_n)/2</math>。

== 再求一个没有简单根式的方程 ==
考虑 <math>f(x)=x^3-x-1</math>。在 <math>[1,2]</math> 上，端点值异号；导数 <math>3x^2-1>0</math>，所以根唯一。取初值 <math>x_0=1.5</math>，先算
<math display="block">f(1.5)=\frac78,\qquad f'(1.5)=\frac{23}{4}.</math>
修正量为 <math>(7/8)/(23/4)=7/46</math>，所以
<math display="block">x_1=\frac32-\frac7{46}=\frac{31}{23}\approx1.347826087.</math>
下一轮使用新点处的函数与导数：
<math display="block">x_{n+1}=x_n-\frac{x_n^3-x_n-1}{3x_n^2-1}.</math>
依次得到 <math>x_2\approx1.325200399</math>、<math>x_3\approx1.324718174</math>，趋向 <math>1.3247179572</math>。

这个例子还能验证误差。只要近似与根都在 <math>[1,2]</math>，导数至少为二，中值定理给出 <math>|x_n-r|\le|f(x_n)|/2</math>。例如第三步残差约为 <math>9.25\times10^{-7}</math>，位置误差便不超过约 <math>4.63\times10^{-7}</math>。

== 一般函数为什么会有二次收敛 ==
平方根例子的误差恒等式，对一般函数变为泰勒余项估计。设 <math>f(r)=0</math>、<math>f'(r)\ne0</math>，这样的根称为单根；假定 <math>f</math> 在附近二次连续可微。将根处的函数值在当前点展开：
<math display="block">0=f(x_n)+f'(x_n)(r-x_n)+\frac12f''(\xi_n)(r-x_n)^2,</math>
其中 <math>\xi_n</math> 位于当前点与根之间。移项并除以 <math>f'(x_n)</math>，把前两项组成牛顿更新，得到
<math display="block">x_{n+1}-r=\frac{f''(\xi_n)}{2f'(x_n)}(x_n-r)^2.</math>
若邻域内 <math>|f'|\ge\mu>0</math>、<math>|f''|\le M</math>，则误差满足 <math>|e_{n+1}|\le C|e_n|^2</math>，其中 <math>e_n=x_n-r</math>、<math>C=M/(2\mu)</math>。

为保证能一直使用这个界，可以选一个半径 <math>\rho>0</math>，使上述导数界在该邻域内成立，并令 <math>C\rho\le1/2</math>。只要 <math>|e_0|<\rho</math>，便有 <math>|e_1|\le|e_0|/2<\rho</math>；逐步重复，后续点始终留在邻域中并趋向根。这说明“初值足够近”具体承担了什么任务。[https://fncbook.com/newton/ FNC：Newton's method]

误差足够小时，这种平方关系称为局部二次收敛。若二阶导数在根处也消失，还可能更快；线性函数的切线就是函数本身，一步即可求根。浮点计算达到表示精度后，小数不会继续按这个理想规律改善。

== 哪些情形会改变这一过程 ==
'''重根会减慢速度。''' 对 <math>f(x)=(x-r)^m</math>，其中整数 <math>m>1</math>，代入迭代式可得
<math display="block">x_{n+1}-r=\left(1-\frac1m\right)(x_n-r).</math>
误差只按固定比例缩小。例如平方重根每轮减半，因为根处导数为零，已经不满足单根条件。若重数 <math>m</math> 已知，使用 <math>x_{n+1}=x_n-mf(x_n)/f'(x_n)</math> 可补偿这一因素。

'''光滑函数也可能让迭代循环。''' 取 <math>f(x)=x^3-2x+2</math>，从零出发，<math>f(0)=2,f'(0)=-2</math>，下一步到一；而 <math>f(1)=1,f'(1)=1</math>，下一步又回到零。于是出现 <math>0\to1\to0</math> 的永久循环。多项式光滑且有实根，初值却没有进入所需的局部收敛区域。

'''陡直的穿越也可能发散。''' 对 <math>f(x)=\sqrt[3]x</math>，从非零点开始，<math>f/f'=3x</math>，所以 <math>x_{n+1}=-2x_n</math>，绝对值逐轮翻倍。函数在根处不满足前面导数的条件。

还有直接无法计算的步骤：求 <math>x^3-1=0</math> 却从零开始，导数就是零；带对数的函数还可能被一步带到非正输入。遇到这些情况应改变初值、缩短步长或使用区间保护。

== 停止、保护与推广 ==
小残差不必意味着小位置误差：将函数整体乘一个极小常数，根与牛顿修正都不变，残差却能变得很小。相邻两次值相同也可能只是浮点停滞。因此可同时记录步长与残差，并在有条件时提供导数下界或根区间作为误差证据。最大迭代次数是计算限制，达到它不等于达到精度。

保护牛顿法的一种办法是保留[[二分法]]的异号区间。先尝试牛顿候选点；若离开区间、导数太小或区间缩减不足，就改用中点。接受点后按符号更新端点。为了继承二分的可靠性，需要规定何时必须缩短区间，而不只检查候选点有没有落在里面。

多元方程 <math>F(x)=0</math> 中，切线改为局部线性系统：
<math display="block">J_F(x_n)s_n=-F(x_n),\qquad x_{n+1}=x_n+s_n.</math>
雅可比矩阵 <math>J_F</math> 收集各输出对各输入的偏导数，<math>s_n</math> 是待求修正。计算时解这个线性系统即可，不必显式求逆矩阵。在[[优化]]中对梯度应用此方法，求得的是驻点，还需检查它是最小值、最大值还是鞍点。

== 历史 ==
牛顿 1669 年的工作研究方程近似求根，拉夫逊于 1690 年发表了改进的计算形式，辛普森于 1740 年发展以导数表达的一般迭代及推广。现代公式汇集了这些发展；平方根的特殊迭代还有更早的计算渊源。[https://clp.math.uky.edu/clp1/sec_C_1.html CLP：Newton's Method]；[https://mathshistory.st-andrews.ac.uk/Biographies/Simpson/ MacTutor：Thomas Simpson]

== 参考资料与知识联系 ==
* Tobin A. Driscoll、Richard J. Braun，[https://fncbook.com/newton/ Fundamentals of Numerical Computation，Newton's method]：局部线性化与收敛分析。
* CLP Calculus，[https://clp.math.uky.edu/clp1/sec_C_1.html Newton's Method]，大学课程公开镜像：几何推导及历史注释。
* MacTutor，University of St Andrews，[https://mathshistory.st-andrews.ac.uk/Biographies/Simpson/ Thomas Simpson]：现代公式形成背景。
* 前置：[[导数]]、[[极限]]；比较：[[二分法]]；推广：[[矩阵]]、[[优化]]、[[最小二乘法]]。
[[分类:数值分析]]