MathLabs
定理已证明

牛顿法的二次收敛性

命题陈述

设 ff 在根 rr 附近二次连续可微,且 f′(r)≠0f'(r) \ne 0。则存在 rr 的一个邻域,使得若牛顿迭代从该邻域内部出发,迭代序列收敛于 rr,并且对某常数 C=max⁡∣f′′∣2min⁡∣f′∣C=\dfrac{\max|f''|}{2\min|f'|}(最大值与最小值均在该邻域上取)满足 ∣xn+1−r∣≤C ∣xn−r∣2|x_{n+1}-r| \le C\,|x_n-r|^2。

为什么成立?

切线对光滑曲线的逼近非常好,以至于它产生的误差与已走过距离的平方成正比,因此每多正确一位小数,到下一步正确位数大约翻倍。

证明思路

第一步(围绕当前猜测值作泰勒展开)。由于 ff 二次可微,带拉格朗日余项的泰勒定理给出对某个 ξn\xi_n between xnx_n and rr 有 f(r)=f(xn)+f′(xn)(r−xn)+12f′′(ξn)(r−xn)2f(r) = f(x_n) + f'(x_n)(r-x_n) + \tfrac12 f''(\xi_n)(r-x_n)^2。这是精确等式而非近似,因为余项承载了全部二阶误差。

第二步(代入根的条件)。由于 f(r)=0f(r)=0,左边为零,剩下 0=f(xn)+f′(xn)(r−xn)+12f′′(ξn)(r−xn)20 = f(x_n) + f'(x_n)(r-x_n) + \tfrac12 f''(\xi_n)(r-x_n)^2。两边同除以 f′(xn)f'(x_n)(在 rr 附近非零,因为 f′(r)≠0f'(r) \ne 0 且 f′f' 连续),分离出 r−xnr - x_n:0=f(xn)f′(xn)+(r−xn)+f′′(ξn)2f′(xn)(r−xn)20 = \dfrac{f(x_n)}{f'(x_n)} + (r-x_n) + \dfrac{f''(\xi_n)}{2f'(x_n)}(r-x_n)^2。

第三步(识别出牛顿步)。整理得 r−(xn−f(xn)f′(xn))=−f′′(ξn)2f′(xn)(r−xn)2r - \left(x_n - \dfrac{f(x_n)}{f'(x_n)}\right) = -\dfrac{f''(\xi_n)}{2f'(x_n)}(r-x_n)^2。左边括号内恰是牛顿更新 xn+1x_{n+1},故用 en=xn−re_n = x_n - r 可写成 r−xn+1=−f′′(ξn)2f′(xn) en2r - x_{n+1} = -\dfrac{f''(\xi_n)}{2f'(x_n)}\,e_n^2,即 en+1=−f′′(ξn)2f′(xn) en2e_{n+1} = -\dfrac{f''(\xi_n)}{2f'(x_n)}\,e_n^2。

第四步(界定常数)。取绝对值,并用该邻域上的极值 max⁡∣f′′∣\max|f''| 和 1/min⁡∣f′∣1/\min|f'| 分别界定 ∣f′′(ξn)∣|f''(\xi_n)| 与 1/∣f′(xn)∣1/|f'(x_n)|,即得 C=max⁡∣f′′∣2min⁡∣f′∣C=\dfrac{\max|f''|}{2\min|f'|} 下的 ∣xn+1−r∣≤C ∣xn−r∣2|x_{n+1}-r| \le C\,|x_n-r|^2。一旦 C ∣x0−r∣<1C\,|x_0-r| < 1,该递推关系就迫使 ∣xn−r∣|x_n - r| 收缩到 00,从而证明收敛性,而 ∣xn+1−r∣≤C ∣xn−r∣2|x_{n+1}-r| \le C\,|x_n-r|^2 中的平方正是二次收敛速度的体现。

用到此定理的主题

方程的近似解法

分步证明

该定理暂无分步证明。