牛顿迭代法求解开方问题

五次及以上多项式方程没有根式解（就是没有像二次方程那样的万能公式），这个是被伽罗瓦用群论做出的最著名的结论。

没有根式解不意味着方程解不出来，数学家也提供了很多方法，牛顿迭代法就是其中一种。

资源来源于 LeetCode69——Sqrt(x)。题目描述如下所示：

题目要求实现库函数 sqrt()，并返回整数，实际上是降低了迭代次数，减少了计算量。解决该问题的一个较优也是很经典的方法就是牛顿迭代法。

牛顿迭代法

牛顿迭代法，又称切线法，由牛顿首次提出。其算法详细过程如下图所示：

以方程 x2=n 为例，令 f(x)=x2−n，也就是相当于求解 f(x)=0 的解。首先随便找一个初始值 x0，如果 x0 不是解，做一个经过 (x0,f(x0)) 这个点的切线,与轴的交点为 x1。同理，如果 x1 不是解，做一个经过(x1,f(x1)) 这个点的切线，与轴的交点为 x2。 以此类推……以这样的方式得到的会无限趋近于 f(x)=0 的解。

判断是否是的解有两种方法：1. 直接计算的值判断f(x)是否为0；2. 判断前后两个解和是否无限接近。

经过这个点 (xi,f(xi)) 的切线方程为 f(x)=f(xi)+f′(xi)(x−xi)，
其中，f′(xi) 为 f(xi) 的导数，本题中导数为 2x。令切线方程等于0（纵轴截距取0），即可求出：

xi+1=xi−f(xi)f′(xi)

带入 f(x)=x2−n，继续化简：

xi+1=xi−x2i−n2xi=xi−xi2+n2xi=xi2+n2xi

基于上述迭代公式，可以给出了一个求平方根的算法。事实上，这也的确是很多语言中内置的开平方函数的实现方法。牛顿迭代法也同样适用于求解其他多次方程的解。

下面给出本题的C++代码示例：

int mySqrt(int x) {
    long resutSqrt = x;
    while (resutSqrt * resutSqrt > x) {
        resutSqrt = (resutSqrt + x/resutSqrt) / 2;   // 此处应该把分母2提到最后项，不然两次除以2后相加会有偏差
    }
    return (int)resutSqrt;
}

非常简短，且效率较高，这也是数学分析给算法设计带来的便利。