“牛顿下降法和梯度下降法在机器学习和自适应滤波中的都很重要，本质上是为了寻找极值点的位置。但是收敛的速度不同。 本文中就两种方法来探究一下，哪种收敛方法速度快“

牛顿下降法的递推公式：

梯度下降算法的递推公式：

解释一

下图是两种方法的图示表示，红色为牛顿下降法，绿色为梯度下降法，从图中直观的感觉是，红色线短，下降速度快。因为牛顿下降法是用二次曲面去拟合当前的局部曲面，而梯度下降法是用平面去拟合当前的局部曲面，一般用二次曲面拟合的更好，所以一般牛顿算法收敛快。

http://img.blog.csdn.net/20160109161858143

关于以上的说法中，梯度下降法是用平面去拟合当前的局部曲面。梯度 f’(x)的方向是函数变大的方向。这里需要解释一下，对于一维情况而言，梯度方向只有正方向和负方向。至于为什么梯度下降算法就是用平面去拟合了，大多数情况下，没有讲的详细。接下来就聊一下为什么。

首先考虑一下这个公式，这是一阶泰勒展式，其实就是用平面去拟合函数的局部曲面。

f(x+Δx)=f(x)+f′(x)∗Δx

我们的目的是使得左边的值变小，那是不是应该使得下面的式子变为负值。

f′(x)∗Δx

这样不就会使得左边的式子变小吗。
但是如何使得上式一定为负值，简单的方法就是：

Δx=−f′(x)

这样上式就变为

f(x+Δx)=f(x)−f′(x)∗f′(x)

现在满足使得下式变小了

f(x+Δx)

---

但是不要忘了以上所有的一切只有在局部成立，也就是说在小范围才成立，那么下式就有很能太大

Δx=−f′(x)

所以加个小的修正的因子，上式就变为：

Δx=−μ∗f′(x)

最终得到公式：

xn+1=xn−μ∗f′(xn)

这就是为什么说梯度下降算法是用平面拟合函数的局部曲面。

---

---

至于说牛顿下降法是用二次曲面去拟合当前的局部曲面，首先考虑一下下式：

f(x+Δx)=f(x)+f′(x)Δx+1/2∗f′′(x)∗Δx2

同样我们希望左式最小，那么将左式看成是△x的函数，当取合适的△x值时，左边的式子达到极小值，此时导数为0。因此对上式进行求导数，得到一下公式：

0=f′(x)+f′′(x)∗Δx

此时可得到公式：

xn+1=xn−f′(xn)/f′′(xn)

所以说牛顿下降法是用二次曲面来拟合函数的局部曲面。

---

综上而言，牛顿下降法利用了函数的更多的信息，能够更好的拟合局部曲面，所以收敛的速度也会加快。

解释二

关于梯度下降算法，其中最重要的就是要确定步长μ，它的值严重的影响了梯度下降算法的表现。

接下来考虑如下公式：

f′(x+Δx)=f′(x)+f′′(x)∗Δx

和

Δx=−μ∗f′(x)

结合两个式子，得到：

f′(x+Δx)=f′(x)−μ∗f′′(x)∗f′(x)

令左边的式子为0，得到：

μ=1/f′′(x)

由此可见牛顿下降法是梯度下降法的最优情况，因此牛顿下降法的收敛的速度必然更快。

牛顿法一篇不错的解释：http://blog.csdn.net/itplus/article/details/21896453

拟牛顿法：http://blog.csdn.net/itplus/article/details/21896619

优劣势对比

牛顿法并没有一定收敛的保证，如果在当前迭代点二阶近似不准确，或者，目标函数在这里本就是线性，二阶导数根本不存在，那么牛顿法一定会ill posed，导致不收敛。可以联想为牛顿法步长J/H在某些方向非常大（因为Hessian在这些方向接近于0的导数）而梯度下降加上line seerch是一定会往正确方向收敛的，但是速度会慢。LM可以理解为：GN二阶近似的好的点，更相信GN给出的步长，GN ill posed以至于无法收敛时相信梯度下降，是一个trade off。

梯度下降法用目标函数的一阶偏导、以负梯度方向作为搜索方向，只考虑目标函数在迭代点的局部性质；

牛顿法同时考虑了目标函数的一、二阶偏导数，考虑了梯度变化趋势，因而能更合适的确定搜索方向加快收敛，但牛顿法也存在以下缺点：
1、对目标函数有严格要求，必须有连续的一、二阶偏导数，海森矩阵必须正定；
2、计算量大，除梯度外，还需计算二阶偏导矩阵及其逆矩阵。

牛顿法要比梯度下降法更具有全局判断能力
梯度法从初始点的领域开始判断，在局部进行下降，然后步步逼近极值，往往是走之字型的。
牛顿法在二阶导数的作用下，从函数的凸性出发，直接搜索怎样到达极值点，也就是说在选择方向时，不仅考虑当前坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。
从收敛速度来看，梯度下降是线性收敛，牛顿法是超线性的，至少二阶收敛