欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛顿迭代法求解开方问题

程序员文章站 2024-02-27 19:43:33
...

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

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

资源来源于 LeetCode69——Sqrt(x)。题目描述如下所示:
牛顿迭代法求解开方问题

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

牛顿迭代法

牛顿迭代法,又称切线法,由牛顿首次提出。其算法详细过程如下图所示:
牛顿迭代法求解开方问题

以方程 x2=n 为例,令 f(x)=x2n,也就是相当于求解 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)(xxi)
其中,f(xi)f(xi) 的导数,本题中导数为 2x。令切线方程等于0(纵轴截距取0),即可求出:

xi+1=xif(xi)f(xi)

带入 f(x)=x2n,继续化简:
xi+1=xix2in2xi=xixi2+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;
}

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