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

创作时间:

作者:

@小白创作中心

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

引用

CSDN

https://m.blog.csdn.net/gghhb12/article/details/139881390

牛顿迭代法是一种高效的数值分析方法，广泛应用于求解方程的近似根。本文通过一个面试场景引入主题，详细介绍了牛顿迭代法的原理及其在求解整数近似平方根和立方根中的应用，并进一步探讨了其在机器学习优化中的重要作用。

情景再现

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

一、什么是牛顿迭代法

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

给出一个初始点
，则在该点的切线为：
沿着切线方向，与横轴相交，也即令
则求的：
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点更接近曲线的根点，牛顿、拉弗森们很兴奋，继续重复刚才的工作：

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