牛顿法 · aiwiki.page

牛顿法是一种用于近似求出方程的根的迭代算法，方程通常写作 (f(x)=0)。它从一个初始估计值出发，用局部线性近似代替原函数，再将该近似的根作为下一个估计值。牛顿法是数值分析中的基本方法，也可推广到非线性方程组和数学优化问题。其效果取决于函数本身以及初始点的选择。(math.ubc.ca)

迭代与几何解释

对于可微的一元函数，牛顿迭代公式为

[ x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}, \qquad n=0,1,2,\ldots, ]

前提是导数 (f'(x_n)) 不为零。初始估计值 (x_0) 必须另行给定；公式本身并不能确定适合选取初始点的区域。(personal.math.ubc.ca)

从几何上看，该方法在 ((x_n,f(x_n))) 处作曲线 (y=f(x)) 的切线，其方程为

[ y=f(x_n)+f'(x_n)(x-x_n). ]

令 (y=0)，便得到下一个迭代值。因此，每一步求解的都是线性近似，而非原来的非线性方程。对于非常数的线性函数，这种近似是精确的，只需一步就能求出根。这一构造将微积分与数值求根联系起来。(personal.math.ubc.ca)

例如，将公式应用于多项式 (f(x)=x^2-2)，可得

[ x_{n+1}=\frac12\left(x_n+\frac{2}{x_n}\right). ]

从 (x_0=1) 开始，依次得到的估计值为 (1.5)、约 (1.4166667) 和约 (1.4142157)，逐渐逼近 (\sqrt2)。这些数值说明，一旦估计值接近某个根，精度便可能迅速提高。(personal.math.ubc.ca)

一个标准的局部收敛结论假设：(f) 在根 (r) 附近二阶连续可微，且 (f'(r)\ne0)。这样的根称为单根。如果初始估计值与 (r) 足够接近，牛顿法的收敛速度至少达到二次收敛：新误差的大小不超过前一次误差平方的某个常数倍。(dlmf.nist.gov)

记 (e_n=x_n-r)，则渐近误差关系为

[ e_{n+1} =\frac{f''(r)}{2f'(r)}e_n^2+o(e_n^2). ]

因此，在局部收敛阶段，每次迭代后正确数字的位数往往大致翻倍。如果首项系数为零，收敛还可能更快。这一误差分析可由根附近的泰勒展开推导得到。(dlmf.nist.gov)

对于重数为 (m>1) 的根，普通牛顿迭代通常仅为线性收敛，其渐近误差因子为 (1-1/m)。若已知 (m)，则采用修正后的迭代公式

[ x_{n+1}=x_n-m\frac{f(x_n)}{f'(x_n)} ]

可在适当的光滑性假设下恢复局部二次收敛。(dlmf.nist.gov)

局部收敛并不意味着从任意初始估计值出发都能收敛。某一步可能遇到导数为零的情况，也可能远离预期的根，或进入循环。不同的初始估计值还可能收敛到不同的根。(openstax.org)

一个简单的循环例子是

[ f(x)=x^3-2x+2. ]

从 (x_0=0) 出发，得到 (x_1=1)，随后又得到 (x_2=0)。因此，数列会无限地在这两个点之间交替，而这两个点都不是根。同样，由于导数出现在分母中，过小的导数也可能导致过大的修正量。(openstax.org)

这些局限促使人们采用带有保障机制的方法。二分法等区间括根方法始终保留一个包含根的区间，而混合算法则将这种可靠性与更快的插值步骤或类似牛顿法的步骤结合起来。(docs.scipy.org)

对于 (F:\mathbb R^d\to\mathbb R^d)，牛顿法用雅可比矩阵 (J_F(x)) 代替标量导数，该矩阵的元素是各分量函数的一阶偏导数。在每次迭代中，修正量 (s_n) 满足

[ J_F(x_n)s_n=-F(x_n), \qquad x_{n+1}=x_n+s_n. ]

这样，每一步都将非线性问题化为一个线性方程组。局部二次收敛要求函数具有适当的正则性，且解处的雅可比矩阵非奇异。(dlmf.nist.gov)

对于光滑的目标函数 (g)，牛顿法可用于求解驻点方程 (\nabla g(x)=0)。其迭代利用梯度和海森矩阵：

[ \nabla^2g(x_n)s_n=-\nabla g(x_n). ]

与梯度下降不同，牛顿法利用了二阶曲率信息。当海森矩阵正定时，牛顿方向是下降方向；若不具备这一性质，求解驻点方程并不一定能找到极小值点。(stanford.edu)

阻尼迭代采用 (x_{n+1}=x_n+\alpha_ns_n)，其中步长通过线搜索选取。这可以改善远离解时的迭代表现。计算迭代方向需要求导并求解线性方程组，因此单次迭代的计算成本可能远高于一阶方法。面向大规模问题的变体会利用矩阵结构，或近似求解牛顿方程组。(stanford.edu)

常见的终止条件包括残差足够小、相邻估计值的变化足够小，或达到迭代次数上限。仅凭步长很小并不能保证已经找到根；还必须单独检查残差。(docs.scipy.org)

割线法用前两个估计值计算出的斜率代替导数。它无需显式计算导数，以降低牛顿法的局部收敛速度为代价，换取更低的单次迭代成本。哈雷法还使用二阶导数，可以达到局部三次收敛。(math.ubc.ca)

该方法以艾萨克·牛顿命名，他于1669年描述了一种早期的、基于多项式的计算方法。约瑟夫·拉夫森于1690年对其作出重大改进，托马斯·辛普森又于1740年作出进一步改进。因此，现代基于导数的迭代形式是历史演进的结果，而非对牛顿原始方法的原样照搬。(personal.math.ubc.ca)