跳到正文
格致开物MATHWIKI
数学百科/知识地图

牛顿法

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

从二开始求平方根二

令 f(x)=x2−2。我们知道正根在一和二之间，先取 x0=2。此时函数值为二，导数 f′(2)=4，所以切线方程为 y=2+4(x−2). 把切线的高度设为零，得到 x=2−2/4=1.5。这比初值二更接近真正的零点，便把它作为下一次近似。

曲线x平方减二在二二处的切线与横轴相交于一点五，区别于根号二
对 x²−2，在 x₀=2 处用切线预测下一次近似 x₁=3/2；它仍不等于真正的根 √2。

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

牛顿法的切线迭代

在当前点作切线，观察它与横轴的交点怎样成为下一次近似。

静态配图与完整推导见本节正文；交互演示需浏览器启用 JavaScript。

对一般当前点 xn，切线写成 y=f(xn)+f′(xn)(x−xn)。若 f′(xn)≠0，令 y=0 并解出 x，便得到 xn+1=xn−f(xn)f′(xn). 分子是当前离零有多高，分母是切线斜率，两者之比给出横向修正量。斜率很小时，修正可能很大；斜率为零而函数值非零时，切线平行横轴，这一步没有交点。

把切线公式化成可重复计算的步骤

对 f(x)=x2−2，导数为 2x，公式化简为 xn+1=xn−xn2−22xn=12(xn+2xn). 从二开始，前几轮如下。每一轮都将上一行的结果代回这个式子。

编号 精确或近似值 本轮计算
0 2 初值
1 3/2=1.5 (2+2/2)/2
2 17/12≈1.4166666667 (3/2+4/3)/2
3 577/408≈1.4142156863 (17/12+24/17)/2
4 约 1.4142135624 再次代入，误差约为 1.6×10−12

设 r=2。由于 r2=2，下一步误差可以直接展开： xn+1−r=xn2+r2−2xnr2xn=(xn−r)22xn. 上一步误差被平方了，正是表中精度快速提高的原因。例如误差已经小于百分之一，再平方就达到万分之一的量级，且还要除以约 22。

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

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

再求一个没有简单根式的方程

考虑 f(x)=x3−x−1。在 [1,2] 上，端点值异号；导数 3x2−1>0，所以根唯一。取初值 x0=1.5，先算 f(1.5)=78,f′(1.5)=234. 修正量为 (7/8)/(23/4)=7/46，所以 x1=32−746=3123≈1.347826087. 下一轮使用新点处的函数与导数： xn+1=xn−xn3−xn−13xn2−1. 依次得到 x2≈1.325200399、x3≈1.324718174，趋向 1.3247179572。

这个例子还能验证误差。只要近似与根都在 [1,2]，导数至少为二，中值定理给出 |xn−r|≤|f(xn)|/2。例如第三步残差约为 9.25×10−7，位置误差便不超过约 4.63×10−7。

一般函数的二次收敛条件

平方根例子的误差恒等式，对一般函数变为泰勒余项估计。设 f(r)=0、f′(r)≠0，这样的根称为单根；假定 f 在附近二次连续可微。将根处的函数值在当前点展开： 0=f(xn)+f′(xn)(r−xn)+12f″(ξn)(r−xn)2, 其中 ξn 位于当前点与根之间。移项并除以 f′(xn)，把前两项组成牛顿更新，得到 xn+1−r=f″(ξn)2f′(xn)(xn−r)2. 若邻域内 |f′|≥μ>0、|f″|≤M，则误差满足 |en+1|≤C|en|2，其中 en=xn−r、C=M/(2μ)。

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

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

哪些情形会改变这一过程

重根会减慢速度。 对 f(x)=(x−r)m，其中整数 m>1，代入迭代式可得 xn+1−r=(1−1m)(xn−r). 误差只按固定比例缩小。例如平方重根每轮减半，因为根处导数为零，已经不满足单根条件。若重数 m 已知，使用 xn+1=xn−mf(xn)/f′(xn) 可补偿这一因素。

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

陡直的穿越也可能发散。 对 f(x)=x3，从非零点开始，f/f′=3x，所以 xn+1=−2xn，绝对值逐轮翻倍。函数在根处不满足前面导数的条件。

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

停止、保护与推广

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

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

多元方程 F(x)=0 中，切线改为局部线性系统： JF(xn)sn=−F(xn),xn+1=xn+sn. 雅可比矩阵 JF 收集各输出对各输入的偏导数，sn 是待求修正。计算时解这个线性系统即可，不必显式求逆矩阵。在优化中对梯度应用此方法，求得的是驻点，还需检查它是最小值、最大值还是鞍点。

历史

牛顿 1669 年的工作研究方程近似求根，拉夫逊于 1690 年发表了改进的计算形式，辛普森于 1740 年发展以导数表达的一般迭代及推广。现代公式汇集了这些发展；平方根的特殊迭代还有更早的计算渊源。CLP：Newton's Method；MacTutor：Thomas Simpson

参考资料与知识联系

检索自“https://gezhi.wiki/index.php?title=牛顿法&oldid=1854”