牛顿迭代法（求解整数的近似平方根）

 情景再现

面试官：给你一个整数怎样最快求解他的近似平方根？
小白：可以用while循环呀！
面试官：有没有更好的方法？
小白：可以从这个数的左右两边开始迭代。
面试官：除了这个呢，还有吗？
小白：暂时想不到了。
面试官：嗯嗯好的
..........................
HR: 回去等通知吧

一、什么是牛顿迭代法 

假设有函数：𝑓(𝑥)=0，要想求出其根，则可以：

1: 给出一个初始点 ，则在该点的切线为：

2: 沿着切线方向，与横轴相交，也即令 则求的：

3:更新  ，令

4:按照1-3步骤迭代下去，直到精度满足要求

上述算法的第1、2步，其实也就是函数𝑓(𝑥)在处的泰勒展开取前两项：

上述泰勒展开式，取前两项并使之等于0，则有：,可以得到步骤2中的迭代公式。

容易得出，点的切线方程为，要求，即相当于求的解

二、解决求根问题

对于求解一个整数的近似平方根这个问题，我们可以简单做一个转换，使得问题变成一个方程：。对于方程，n是已知待求平方根的整数，x为我们姚求解的目标，此时，我们的目的就变成求解的根

function getSqrt(n) {  
	let x0 = 1;
	let x1 = 0;
	while(true){
		x1 = x0 - (x0*x0 - n)/(2*x0)
		if(Math.abs(x1-x0) < 1e-10){
			break;
		}
		x0 = x1;
	}
	return x1;
}

我们给定初始值为1，这里需要注意的是，我们给的初始值不能是方程的极值点，否则利用牛顿迭代法则无法继续优化下去；

设定了迭代结束条件：，当满足该条件时，说明求解的精度已经很高了，此时的迭代结果即可作为近似根了。

拓展一下：

给出了使用牛顿迭代法求解给定整数近似平方根的方法，我们同样可以用于处理其他问题，如求解给定整数立方根..n次方根、给定任意方程，求其近似解等问题。

下面给出求解立方根的解法，与求解平方根十分相似，唯一不同之处就在于目标迭代公式稍微发生一点变化：

while(true){
        x1 = x0 - (x0*x0*x0 - n)/(3*x0*2)
        if(Math.abs(x1-x0) < 1e-20){
            break;
        }
        x0 = x1;
 }

三、机器学习 

    机器学习的本质是建立优化模型，通过优化方法，不断迭代参数向量，找到使目标函数最优的参数向量，最终建立模型。但是在机器学习的参数优化过程中，很多函数是非常复杂的，不能直接求出。五次及以上多项式方程没有根式解，这个是被伽罗瓦用群论做出的最著名的结论，工作生活中还是有诸多类似求解高次方程的真实需求（比如行星的轨道计算，往往就是涉及到很复杂的高次方程）没有根式解不意味着方程解不出来，我们必须转向一些近似解法，通常用到的优化方法：梯度下降方法、牛顿法、拟牛顿法等，这些优化方法的本质就是在更新参数。

    牛顿迭代法又称为牛顿-拉弗森方法，实际上是由牛顿、拉弗森各自独立提出来的。牛顿-拉弗森方法提出来的思路就是利用切线是曲线的线性逼近这个思想，如下图所示：

随便找一个曲线上的A点（为什么随便找，根据切线是切点附近的曲线的近似，应该在根点附近找，但是很显然我们现在还不知道根点在哪里），做一个切线，切线的根（就是和x轴的交点）与曲线的根，还有一定的距离。牛顿、拉弗森们想，没关系，我们从这个切线的根出发，做一根垂线，和曲线相交于B点，继续重复刚才的工作：

 之前说过，B点比之前A点更接近曲线的根点，牛顿、拉弗森们很兴奋，继续重复刚才的工作：

第四次就已经很接近曲线的根了：

经过多次迭代后会越来越接近曲线的根（下图进行了50次迭代，哪怕经过无数次迭代也只会更接近曲线的根，用数学术语来说就是，迭代收敛了）：