大部分的数值计算方法都是迭代法，这让人感到，解析解的世界是理想的，迭代解的世界才是现实的。如果要我当上帝，我一定选择迭代算法来创造这个世界。这就是数值计算给我的感受。

牛顿迭代法是数值计算中非常重要的基础算法。本文分析一下。

对于一个非常复杂的非线性函数，

以一维情况为例。我们想求其最小值（相当于求$-f(x)$​​的最大值），如果全局只有一个极值点，那么只需要求到$f’(x) = 0$​的根即可。但是由于$f(x)$​本身就是个非常复杂的函数，其导数也会很复杂，因此求根也不容易。为此我们考虑使用更简单的函数$h(x)$​来逼近复杂的非线性函数$f(x)$​。这个$h(x)$​​的构造最简便而又不过于简单的做法是使用二阶泰勒展开，即在点$x_n$​处展开有，

直观上就是使用抛物线来逼近$f(x)$， 于是我们可以使用$h’(x) =0$求根来替代$f’(x) = 0$求根，有

于是解得$x$，

如此迭代下去，可以逼近$f(x)$的最小值，这就是牛顿法的迭代公式。令$\alpha = \frac{1}{f’’(x)}$，有

这里的$\alpha$可以理解为步速因子，即以多大的速度更新$x_n$，牛顿法则是使用$f’’(x)$的倒数来控制步速于。是我们把它改为常数也可以，

这！不就是梯度下降算法吗？是的！

转载请包括本文地址：https://allenwind.github.io/blog/6156
更多文章请参考：https://allenwind.github.io/blog/archives/