牛顿法为什么是二阶的
牛顿法为什么是二阶的
牛顿法是数值分析中一种重要的算法，广泛应用于求解方程的根和最优化问题。本文将深入探讨牛顿法为什么被称为二阶算法，通过详细的数学推导和直观的对比分析，帮助读者理解这一算法的核心原理。
牛顿法的基本应用场景
牛顿法主要应用于以下两个场景：
- 求方程的根
- 求解最优化问题
以求解方程 (f(x) = 0) 为例。首先，选择一个接近函数 (f(x)) 零点的初始值 (x_0)，计算相应的函数值 (f(x_0)) 和切线斜率 (f'(x_0))。然后，计算穿过点 ((x_0, f(x_0))) 且斜率为 (f'(x_0)) 的直线与 (x) 轴的交点的 (x) 坐标，即求解如下方程：
[f(x_1) - f(x_0) = f'(x_0) \cdot (x_1 - x_0)]
通常，(x_1) 会比 (x_0) 更接近方程 (f(x) = 0) 的解。因此，我们可以利用 (x_1) 开始下一轮迭代。迭代公式可化简为：
[x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}]
已经证明，如果 (f') 是连续的，并且待求的零点 (x) 是孤立的，那么在零点 (x) 周围存在一个区域，只要初始值 (x_0) 位于这个邻近区域内，那么牛顿法必定收敛。并且，如果 (f'(x) \neq 0)，那么牛顿法将具有平方收敛的性能。粗略地说，这意味着每迭代一次，牛顿法结果的有效数字将增加一倍。
由于牛顿法是基于当前位置的切线来确定下一次的位置，所以牛顿法又被很形象地称为是"切线法"。牛顿法的搜索路径（二维情况）如下图所示：
牛顿法与梯度下降法的效率对比
从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。（牛顿法目光更加长远，所以少走弯路；相对而言，梯度下降法只考虑了局部的最优，没有全局思想。）
根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。
注：红色的牛顿法的迭代路径，绿色的是梯度下降法的迭代路径。
牛顿法的优缺点总结
优点：二阶收敛，收敛速度快；
缺点：牛顿法是一种迭代算法，每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂。
当我们将牛顿法用作优化算法的时候，它就是二阶的。假设我们有一个凸优化问题：
[\min_x f(x)]
也就是说我们要找一个 (x) 来最小化 (f(x))。对于凸优化问题，(f(x)) 的最小值点就是 (f(x)) 的极值点，也就是导数为0的点。那么我们上面的优化问题就转换为了如下的求根问题：
[f'(x) = 0]
利用牛顿法求解上面的式子，我们先选取初始点 (x_0)，然后进行如下迭代：
[x_{n+1} = x_n - \frac{f'(x_n)}{f''(x_n)}]
直到 (|x_{n+1} - x_n| < \epsilon)
综上，牛顿法求根是一阶算法，我们将优化问题转为求根问题需要一阶导数，所以用牛顿法进行最优化是二阶算法。