简介

牛顿迭代法（Newton’s method）又称为牛顿-拉夫逊（拉弗森）方法（Newton-Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。

联系知识

泰勒公式:泰勒公式是一个用函数在某点的信息描述其附近取值的公式。如果函数足够平滑的话，在已知函数在某一点的各阶导数值的情况之下，泰勒公式可以用这些导数值做系数构建一个多项式来近似函数在这一点的邻域中的值。

公式 = f(x)=f(x0)+f'(x0)*(x-x0)+f''(x0)/2!*(x-x0)^2+...+f(n)(x0)/n!*(x-x0)^n

f(n)(x.)是f(x.)的n阶导数

具体内容

其采用一阶泰勒展开，f(x) = 0,求 x = ?

简单例子

求x平方根？

令 $$y_0=x$$
则 $$y_{n+1}=y_n-\frac{f(y_n)}{f’(y_n)}=y_n-\frac{y_n2-x}{2y_n}=\frac{y_n2+x}{2y_n}=\frac{y_n+\frac{x}{y_n}}{2}$$

求三次方根？

代码实现

Java实现开平方的牛顿迭代法. 求c(c>0)的算术平方根就是求 $$f(x) = x^2-c$$ 的正根,
得迭代公式: $$x_{n+1}=\frac{1}{2}(x_n+\frac{c}{x_n})$$
代码中取初始值 c , 误差控制在 $$ 1*10^{-15} $$

class Solution{
    public static double sqrt(double c) {
        if (c < 0) return Double.NaN;
        double e = 1e-15;
        double x = c;
        double y = (x + c / x) / 2;
        while (Math.abs(x - y) > e) {
            x = y;
            y = (x + c / x) / 2;
        }
        return x;
    }
}