【数论】牛顿迭代法
【数论】牛顿迭代法
五次及以上多项式方程没有根式解（就是没有像二次方程那样的万能公式），这个是被伽罗瓦用群论做出的最著名的结论。
但是，没有根式解不意味着方程解不出来，数学家也提供了很多方法，牛顿迭代法就是其中一种。
本文介绍如何用牛顿迭代法（Newton's method for finding roots）求方程的近似解，该方法于 17 世纪由牛顿提出。
具体的任务是，对于在[a,b] 上连续且单调的函数 f(x) ，求方程 f(x)=0 的近似解。
牛顿迭代法
求出根号a的近似值：首先随便猜一个近似值x，然后不断令x等于x和a/x的平均数，迭代个六七次后x的值就已经相当精确了。
例如，我想求根号2等于多少。假如我猜测的结果为4，虽然错的离谱，但你可以看到使用牛顿迭代法后这个值很快就趋近于根号2了：
( 4 + 2/4 ) / 2 = 2.25
( 2.25 + 2/2.25 ) / 2 = 1.56944..
( 1.56944..+ 2/1.56944..) / 2 = 1.42189..
( 1.42189..+ 2/1.42189..) / 2 = 1.41423..
……
对于高维函数，用牛顿法求极值也是这个形式，只不过这里的y'和y''都变成了矩阵和向量。而且你也可以想到，高维函数二阶导有多个，写成矩阵的形式Hessian矩阵：
y'就变成了对所有参数的偏导数组成的向量
然而算的可能非常慢，数也可能很大。简单的解决办法，有一种叫做批迭代的方法，不管是在梯度计算极值还是在牛顿计算极值上都是可行的，就是假设失去大部分点对准确度没有太大的影响，比如说3个在一条直线上的点，去掉一个也没什么关系，最后反正还是会拟合成同一个参数。批迭代就是在众多的点中随机抽取一些，进行迭代计算，再随机抽取一些再进行迭代。迭代的路径可能不完美，但是最终还是会找到我们想要的答案。（有点类似mini-batch）
当然还有其他更帅的解决方法，祝如DFP，BFGS，Broyden。
2. 前置知识---导数
切线是曲线的线性逼近
要讲牛顿迭代法之前我们先说一个关键问题：切线是曲线的线性逼近。
这个是什么意思呢？我们来看一看，下面是 f(x)=x^2 的图像：
我们随便选f(x) 上的一点(A,f(A)) 做它的切线：
我们在A点处放大图像：
上图中，红色的线是f(x) ，黑色的是A点处的切线，可以看出放大之后切线和 f(x)非常接近了。很明显，如果我们进一步放大图像，A点切线就越接近 f(x)。可以自己动手试试：
此处有互动内容，点击此处前往操作。
因为切线是一条直线（也就是线性的），所以我们可以说，A点的切线是f(x) 的线性逼近。离A点距离越近，这种逼近的效果也就越好，也就是说，切线与曲线之间的误差越小。所以我们可以说在A点附近，“切线”。
我们将切线的斜率记作在x处的导数 ，即
对于幂函数 f( x )=x^n，它在
处的导数为
，利用极限的思想即可推导出来。
3.几何直觉
牛顿迭代法又称为牛顿-拉弗森方法，实际上是由牛顿、拉弗森（又是一个被牛顿大名掩盖的家伙）各自独立提出来的。
牛顿-拉弗森方法提出来的思路就是利用切线是曲线的线性逼近这个思想。
牛顿、拉弗森们想啊，切线多简单啊，研究起来多容易啊，既然切线可以近似于曲线，我直接研究切线的根不就成了。
然后他们观察到这么一个事实：
随便找一个曲线上的A点（为什么随便找，根据切线是切点附近的曲线的近似，应该在根点附近找，但是很显然我们现在还不知道根点在哪里），做一个切线，切线的根（就是和x轴的交点）与曲线的根，还有一定的距离。牛顿、拉弗森们想，没关系，我们从这个切线的根出发，做一根垂线，和曲线相交于B点，继续重复刚才的工作：
之前说过，B点比之前A点更接近曲线的根点，牛顿、拉弗森们很兴奋，继续重复刚才的工作：
第四次就已经很接近曲线的根了：
经过多次迭代后会越来越接近曲线的根（下图进行了50次迭代，哪怕经过无数次迭代也只会更接近曲线的根，用数学术语来说就是，迭代收敛了）：
牛顿法搜索动态示例图