牛顿迭代法

牛顿迭代法用于近似求解多项式的零点十分方便，收敛速度也很快，比二分法还快。

牛顿迭代法

牛顿迭代法常用来求解方程的近似根，因为多数的方程没有求根公式，这也是大多数计算机内部的求解根的方法，收敛速度非常快。

牛顿迭代法的思路

对于一般的曲线y=f(x)，通常没有求根公式，无法得到解析解，利用牛顿迭代法需要先对根的位置进行近似估计为x0，然后在x0的领域内将y=f(x)按照泰勒级数展开，并保留前几项，近似为多项式函数y=f1(x)。假设第一步的近似解是x1，那么过曲线f1(x)上点(x1, f1(x1))的切线为y=f1(x1)+f1’(x1)(x-x1)，那么该切线与x轴交点是x=x1-f1(x1)/f1’(x1)，记作x1=x1-f1(x1)/f1’(x1)，同理进行类推，得到了递推公式x(n+1)=x(n)-f1(x(n))/f1’(x(n))，不断迭代下去便能不断逼近真正的零点。

由于进行泰勒展开需要先预先估计零点，有误差，并且泰勒展开本身也有误差，并且最后的根也是近似的，因此实际中感觉还是多项式函数的根比较好用牛顿迭代法，对于多项式函数就不需要进行泰勒展开了。

例题：给定一个非负整数，求它的开方，向下取整。

构造函数y=x^2-a，那么迭代公式x(n+1)=[x(n)+a/x(n)]/2，直接把a当作初值迭代即可。

int mySqrt(in a){
    long x=a;
    // 需要确保x*x不越界，因此需要把x定义为long int
    while(x*x>a){
        x=(x+a/x)/2;
    }
    return x;
}

赏

感谢您的支持:)

支付宝

微信