牛顿法¶
最速下降法只用一阶导数，最坏情形只有线性收敛。牛顿法同时使用一阶与二阶导数：每步用二次函数贴合目标函数，直接跳到二次模型的极小点。代价是每步更贵、且只在极小点附近可靠——本页的主线就是"快"与"脆"这两面，以及为补"脆"而生的两个修正（阻尼步长、Levenberg–Marquardt）。
核心结论速览
| 结论 | 内容 |
|---|---|
| 牛顿迭代公式 | \(\boldsymbol{x}^{(k+1)} = \boldsymbol{x}^{(k)} - \boldsymbol{F}(\boldsymbol{x}^{(k)})^{-1} \boldsymbol{g}^{(k)}\)，\(\boldsymbol{g}^{(k)} = \nabla f(\boldsymbol{x}^{(k)})\) |
| 二次型目标 | 任意初始点一步收敛（阶数 \(\infty\)） |
| 局部收敛性 | \(f \in \mathcal{C}^3\)、\(\nabla f(\boldsymbol{x}^*) = \boldsymbol{0}\)、\(\boldsymbol{F}(\boldsymbol{x}^*)\) 可逆 \(\Rightarrow\) 初始点足够近时至少二阶收敛 |
| 下降方向 | \(\boldsymbol{F}(\boldsymbol{x}^{(k)}) \succ 0\) 且 \(\boldsymbol{g}^{(k)} \ne \boldsymbol{0}\) 时，牛顿方向是下降方向 → 加一维搜索得阻尼牛顿法 |
| 黑塞不正定的补救 | Levenberg–Marquardt 修正：\(\big( \boldsymbol{F}(\boldsymbol{x}^{(k)}) + \mu_k \boldsymbol{I} \big)^{-1}\)，\(\mu_k\) 足够大即正定 |
| 非线性最小二乘 | \(\boldsymbol{F} = 2(\boldsymbol{J}^\top \boldsymbol{J} + \boldsymbol{S})\)；忽略 \(\boldsymbol{S}\) → 高斯–牛顿法；再加 \(\mu_k \boldsymbol{I}\) → L–M 方法 |
思想：用二次模型代替目标函数¶
设 \(f \in \mathcal{C}^2\)。在当前点 \(\boldsymbol{x}^{(k)}\) 处作二阶泰勒展开、丢掉高阶项，得到与 \(f\) 在该点一、二阶导数完全相同的二次型近似：
对 \(q\) 用内点 FONC：\(\nabla q(\boldsymbol{x}) = \boldsymbol{g}^{(k)} + \boldsymbol{F}(\boldsymbol{x}^{(k)})(\boldsymbol{x} - \boldsymbol{x}^{(k)}) = \boldsymbol{0}\)。当 \(\boldsymbol{F}(\boldsymbol{x}^{(k)}) \succ 0\) 时 \(q\) 的极小点即为下一个迭代点：
这是一维牛顿法 \(x^{(k+1)} = x^{(k)} - f'(x^{(k)}) / f''(x^{(k)})\) 的多维版本：除法变成乘黑塞矩阵的逆。
实现注记：实际计算不求逆矩阵，而是分两步——先解 \(n\) 维线性方程组 \(\boldsymbol{F}(\boldsymbol{x}^{(k)})\, \boldsymbol{d}^{(k)} = -\boldsymbol{g}^{(k)}\) 得牛顿方向 \(\boldsymbol{d}^{(k)}\)，再更新 \(\boldsymbol{x}^{(k+1)} = \boldsymbol{x}^{(k)} + \boldsymbol{d}^{(k)}\)。每步的主要代价就是这个方程组（一般 \(O(n^3)\)）。
求根版本：牛顿法同样适用于解多元方程 \(\boldsymbol{g}(\boldsymbol{x}) = \boldsymbol{0}\)（\(\boldsymbol{g}: \mathbb{R}^n \to \mathbb{R}^n\)），此时公式中的 \(\boldsymbol{F}(\boldsymbol{x})\) 换成 \(\boldsymbol{g}\) 的雅可比矩阵 \(\big[ \partial g_i / \partial x_j \big]\)。
例：牛顿法求解 Powell 函数
用牛顿法极小化 Powell 函数（经典测试函数）：
初始点 \(\boldsymbol{x}^{(0)} = (3, -1, 0, 1)^\top\)。
解答
求出梯度与黑塞矩阵（略），每步解 \(\boldsymbol{F} \boldsymbol{d} = -\boldsymbol{g}\) 后更新：
| \(k\) | \(\boldsymbol{x}^{(k)}\) | \(f(\boldsymbol{x}^{(k)})\) |
|---|---|---|
| 0 | \((3, -1, 0, 1)^\top\) | \(215\) |
| 1 | \((1.5873, -0.1587, 0.2540, 0.2540)^\top\) | \(31.8\) |
| 2 | \((1.0582, -0.1058, 0.1694, 0.1694)^\top\) | \(6.28\) |
| 3 | \((0.7037, -0.0704, 0.1121, 0.1111)^\top\) | \(1.24\) |
函数值快速下降，迭代点稳步逼近极小点 \(\boldsymbol{0}\)（该函数在原点处黑塞矩阵奇异，是有名的"难缠"测试题，牛顿法依然表现良好）。
收敛性分析¶
二次型目标：一步命中¶
对 \(f(\boldsymbol{x}) = \frac{1}{2} \boldsymbol{x}^\top \boldsymbol{Q} \boldsymbol{x} - \boldsymbol{x}^\top \boldsymbol{b}\)（\(\boldsymbol{Q} = \boldsymbol{Q}^\top \succ 0\)），有 \(\boldsymbol{g}(\boldsymbol{x}) = \boldsymbol{Q}\boldsymbol{x} - \boldsymbol{b}\)、\(\boldsymbol{F} \equiv \boldsymbol{Q}\)，于是
任意初始点一步收敛——二次模型就是目标函数本身，跳一次就到底。这与最速下降法在条件数大时的锯齿形成鲜明对比。
一般目标：局部二阶收敛¶
定理（牛顿法的局部二阶收敛）
设 \(f \in \mathcal{C}^3\)，\(\boldsymbol{x}^*\) 满足 \(\nabla f(\boldsymbol{x}^*) = \boldsymbol{0}\) 且 \(\boldsymbol{F}(\boldsymbol{x}^*)\) 可逆。则对所有与 \(\boldsymbol{x}^*\) 足够接近的初始点 \(\boldsymbol{x}^{(0)}\)，牛顿法有定义且收敛到 \(\boldsymbol{x}^*\)，收敛阶数至少为 2。
证明
对 \(\nabla f\) 在 \(\boldsymbol{x}^{(0)}\) 处泰勒展开（\(f \in \mathcal{C}^3\) 故余项 \(O(\lVert \cdot \rVert^2)\)）：在 \(\boldsymbol{x}^*\) 的 \(\varepsilon\)-邻域内存在 \(c_1, c_2 > 0\) 使
（后者由 \(\boldsymbol{F}(\boldsymbol{x}^*)\) 可逆与矩阵逆的连续性保证）。利用 \(\nabla f(\boldsymbol{x}^*) = \boldsymbol{0}\) 改写第一式，再从牛顿迭代式两端减 \(\boldsymbol{x}^*\) 取范数：
取 \(\lVert \boldsymbol{x}^{(0)} - \boldsymbol{x}^* \rVert \le \alpha / (c_1 c_2)\)（\(\alpha \in (0,1)\)），则 \(\lVert \boldsymbol{x}^{(1)} - \boldsymbol{x}^* \rVert \le \alpha \lVert \boldsymbol{x}^{(0)} - \boldsymbol{x}^* \rVert\)，误差每步至少缩到 \(\alpha\) 倍，归纳得 \(\boldsymbol{x}^{(k)} \to \boldsymbol{x}^*\)；同时 \(\lVert \boldsymbol{x}^{(k+1)} - \boldsymbol{x}^* \rVert \le c_1 c_2 \lVert \boldsymbol{x}^{(k)} - \boldsymbol{x}^* \rVert^2 = O\big( \lVert \boldsymbol{x}^{(k)} - \boldsymbol{x}^* \rVert^2 \big)\)，收敛阶至少为 2。\(\blacksquare\)
二阶收敛的直观感受：误差的有效数字每步翻倍——这是牛顿法"快"的一面。
易错点：牛顿法找的是驻点，不挑极小极大
定理中没有要求 \(\boldsymbol{x}^*\) 是极小点——只要 \(\nabla f(\boldsymbol{x}^*) = \boldsymbol{0}\) 且黑塞可逆，从合适的初始点出发牛顿法照样收敛过去，哪怕 \(\boldsymbol{x}^*\) 是局部极大点或鞍点。牛顿法本质是在解方程 \(\nabla f = \boldsymbol{0}\)，对解的"身份"一视同仁，收敛后仍需用二阶条件验明正身。
"脆"的一面（远离极小点时）：
- 可能不收敛，甚至中途黑塞矩阵奇异、方法直接失效；
- \(\boldsymbol{F}(\boldsymbol{x}^{(k)})\) 不正定时，牛顿方向未必是下降方向（二次模型开口不对，跳向鞍点/极大点一侧）；
- 即使 \(\boldsymbol{F}(\boldsymbol{x}^{(k)}) \succ 0\)，整步跳跃也可能跳过头，出现 \(f(\boldsymbol{x}^{(k+1)}) \ge f(\boldsymbol{x}^{(k)})\)。
下面两节的修正分别解决"跳过头"和"方向不对"。
下降性与阻尼牛顿法¶
定理（牛顿方向是下降方向）
若 \(\boldsymbol{F}(\boldsymbol{x}^{(k)}) \succ 0\) 且 \(\boldsymbol{g}^{(k)} \ne \boldsymbol{0}\)，则牛顿方向 \(\boldsymbol{d}^{(k)} = -\boldsymbol{F}(\boldsymbol{x}^{(k)})^{-1} \boldsymbol{g}^{(k)}\) 是下降方向：存在 \(\bar{\alpha} > 0\) 使得对所有 \(\alpha \in (0, \bar{\alpha})\)，\(f(\boldsymbol{x}^{(k)} + \alpha \boldsymbol{d}^{(k)}) < f(\boldsymbol{x}^{(k)})\)。
证明
令 \(\phi(\alpha) = f(\boldsymbol{x}^{(k)} + \alpha \boldsymbol{d}^{(k)})\)，链式法则：
（正定矩阵的逆仍正定）。初始斜率为负，故小步长内函数值必下降。\(\blacksquare\)
于是把"整步跳"改成"沿牛顿方向做一维搜索"，得到阻尼牛顿法（修正牛顿法）：
只要 \(\boldsymbol{g}^{(k)} \ne \boldsymbol{0}\)（且黑塞正定），阻尼牛顿法保证 \(f(\boldsymbol{x}^{(k+1)}) < f(\boldsymbol{x}^{(k)})\)。它解决了"跳过头"，但黑塞不正定的问题仍在——交给下一节。
Levenberg–Marquardt 修正¶
思路非常干净：把黑塞矩阵沿对角线抬高。设对称矩阵 \(\boldsymbol{F}\) 的特征值为 \(\lambda_1, \dots, \lambda_n\)（实数、可正可负），则 \(\boldsymbol{G} = \boldsymbol{F} + \mu \boldsymbol{I}\)（\(\mu \ge 0\)）与 \(\boldsymbol{F}\) 有相同的特征向量，特征值整体平移为
只要 \(\mu\) 足够大（超过 \(-\lambda_{\min}\)），\(\boldsymbol{G}\) 必正定。由此得 Levenberg–Marquardt（L–M）修正：
修正后的方向必为下降方向；再配上一维搜索步长 \(\alpha_k\) 即可严格保证下降特性。
L–M 是牛顿法与梯度法之间的连续插值
- \(\mu_k \to 0\)：退化为纯牛顿法（快但脆）；
- \(\mu_k \to \infty\)：\((\boldsymbol{F} + \mu_k \boldsymbol{I})^{-1} \approx \frac{1}{\mu_k} \boldsymbol{I}\)，表现为小步长梯度法（稳但慢）。
实践策略：\(\mu_k\) 从小取起、逐渐增大，直到该步出现下降（\(f(\boldsymbol{x}^{(k+1)}) < f(\boldsymbol{x}^{(k)})\)）为止——状态好时当牛顿法用，状态差时自动退守梯度法。
牛顿法在非线性最小二乘中的应用¶
一类极常见的问题：给定函数 \(r_i: \mathbb{R}^n \to \mathbb{R}\)（\(i = 1, \dots, m\)），求
称为非线性最小二乘问题，\(r_i\) 通常是"第 \(i\) 个数据点的拟合残差"。
例：正弦曲线拟合
在时刻 \(t_1, \dots, t_m\) 测得数据 \(y_1, \dots, y_m\)，想用正弦函数 \(y = A \sin(\omega t + \phi)\) 拟合。以 \(\boldsymbol{x} = (A, \omega, \phi)^\top\) 为决策变量，最小化误差平方和
即取残差 \(r_i(\boldsymbol{x}) = y_i - A \sin(\omega t_i + \phi)\) 的非线性最小二乘问题。
记 \(\boldsymbol{r} = (r_1, \dots, r_m)^\top\)，目标 \(f(\boldsymbol{x}) = \boldsymbol{r}(\boldsymbol{x})^\top \boldsymbol{r}(\boldsymbol{x})\)，\(\boldsymbol{J}(\boldsymbol{x}) = D\boldsymbol{r}(\boldsymbol{x})\) 为残差的 \(m \times n\) 雅可比矩阵。求导得
其中 \(\boldsymbol{S}(\boldsymbol{x})\) 的 \((j, k)\) 元为 \(\sum_{i=1}^m \frac{\partial^2 r_i}{\partial x_k \partial x_j}(\boldsymbol{x})\, r_i(\boldsymbol{x})\)，包含残差的二阶导数。代入牛顿迭代式（系数 2 恰好约掉）：
高斯–牛顿法
\(\boldsymbol{S}\) 的元素带着残差因子 \(r_i\)，拟合良好时都很小，实践中常直接忽略，得到高斯–牛顿法：
最大好处：完全不需要计算二阶导数，只用残差的雅可比矩阵。
例：正弦拟合的雅可比矩阵与结果
续上例（\(m = 21\) 个数据点），\(\boldsymbol{J}(\boldsymbol{x})\) 是 \(21 \times 3\) 矩阵，第 \(i\) 行为
给定数据后迭代求解，得最佳拟合参数 \(A = 2.01\)，\(\omega = 0.992\)，\(\phi = 0.541\)。
高斯–牛顿法的隐患是 \(\boldsymbol{J}^\top \boldsymbol{J}\) 可能不正定（或病态），解决办法仍是 L–M 修正：
事实上 Levenberg–Marquardt 修正最初就是为非线性最小二乘问题提出的，上式常直接称为 Levenberg–Marquardt 方法；\(\mu_k \boldsymbol{I}\) 也可以理解为对被忽略的 \(\boldsymbol{S}(\boldsymbol{x})\) 的一种粗略近似——这是同一公式的两种解读。
速查表¶
梯度方法 vs 牛顿家族：
| 方法 | 每步信息与代价 | 收敛性 | 适用场景 |
|---|---|---|---|
| 最速下降法 | 梯度；便宜 | 全局收敛，线性（受条件数制约） | 远离极小点的"开荒"阶段 |
| 纯牛顿法 | 梯度 + 黑塞 + 解 \(n\) 维方程组 | 局部至少二阶；远处可能发散/不降 | 已接近极小点的"冲刺"阶段 |
| 阻尼牛顿法 | 牛顿 + 一维搜索 | \(\boldsymbol{F} \succ 0\) 时保证下降 | 修"跳过头" |
| L–M 修正 | \((\boldsymbol{F} + \mu_k \boldsymbol{I})^{-1}\) | 方向必下降；在牛顿与梯度法间插值 | 修"黑塞不正定" |
| 高斯–牛顿 / L–M 方法 | 只需残差雅可比 \(\boldsymbol{J}\) | 近似牛顿 | 非线性最小二乘（曲线拟合） |
关键公式：
| 公式 | 内容 |
|---|---|
| 牛顿迭代 | \(\boldsymbol{x}^{(k+1)} = \boldsymbol{x}^{(k)} - \boldsymbol{F}^{-1} \boldsymbol{g}\)（实现上解 \(\boldsymbol{F}\boldsymbol{d} = -\boldsymbol{g}\)） |
| 局部二阶收敛 | \(\lVert \boldsymbol{x}^{(k+1)} - \boldsymbol{x}^* \rVert \le c_1 c_2 \lVert \boldsymbol{x}^{(k)} - \boldsymbol{x}^* \rVert^2\) |
| 最小二乘梯度 | \(\nabla f = 2 \boldsymbol{J}^\top \boldsymbol{r}\) |
| 最小二乘黑塞 | \(\boldsymbol{F} = 2(\boldsymbol{J}^\top \boldsymbol{J} + \boldsymbol{S})\)，高斯–牛顿即丢掉 \(\boldsymbol{S}\) |
易错点：
- 牛顿法收敛的对象是驻点：可能是极小点、极大点或鞍点，收敛后必须用二阶条件复核；
- 二次型目标一步收敛的前提是 \(\boldsymbol{Q} \succ 0\)；一般函数只有局部二阶收敛，初始点远时一切免谈；
- \(\boldsymbol{F} \succ 0\) 只保证牛顿方向下降，整步仍可能令函数值上升——下降保证来自阻尼（一维搜索）；
- L–M 中 \(\mu\) 的作用记两头：\(\mu \to 0\) 是牛顿法，\(\mu \to \infty\) 是小步长梯度法；
- 高斯–牛顿法"不用二阶导数"的代价是丢掉 \(\boldsymbol{S}\)，残差大或强非线性时近似变差、可能不收敛，此时靠 L–M 的 \(\mu_k \boldsymbol{I}\) 兜底。