牛顿迭代法求平方根

Author Avatar
Brian Lee 7月 21, 2018
  • 在其它设备中阅读本文章

Sedgewick的《Algorithm》第一章有一段使用牛顿迭代法计算平方根的代码,开始没理解代码的意思,上网查阅资料后搞清楚了原理,并整理了自己的思路。

思路

要求 $c$ 的平方根 $x$ ,首先设函数 $y=x^2-c$ ,当 $y=0$ 时,$x$ 的值便为 $c$ 的平方根。

函数

如图所示,$x_{n+1}$ 为 $c$ 的平方根,而我们通过 $(x_n,f(x_n))$ 来求得 $x_{n+1}$ 的值。

知道 $y=x^2-c$ 的斜率为:

$f^`(x)=\frac{f(x_n)}{x_n-x_{n+1}}$

因为 $f(x_n)=x_{n}^{2}-c$ ,$f^`(x_n)=2x_n$ ,所以得:

$x_{n+1}=\frac{1}{2}(x_n+\frac{c}{x_n})$

通过上述步骤便得到了 $x_{n+1}$ 的表达式,可见我们可以通过迭代得到 $x_{n+1}$ 的值。

给定 $x_n$ 的初始值为 $c$ 。

而停止迭代的条件为:

$x_{n+1}^{2}-c=0$

即:

$x_{n+1}-\frac{c}{x_{n+1}}<x_{n+1}\times err(err为一个极小误差值)$

最后求得的 $x_{n+1}$ 的值便为平方根。

代码

public static double sqr(double c) {
        if (c < 0) {
            return Double.NaN;
        }
        double err = 1e-15;
        double x = c;
        while (Math.abs(x - c / x) > err * x) {
            x = (c / x + x) / 2.0;
        }
        return x;
    }

源代码地址

https://github.com/XutongLi/Algorithm-Learn/blob/master/src/S1_foundation/S1_1_6_1_NewtonMethod/NewtonMethodSqrt.java

本博客采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处!
本文链接:http://brianleelxt.top/2018/07/21/newton_sqrt/