java - 使用 Newton-Raphson 方法计算平方根的 While 循环条件

Question

我目前正在学习一门类(class)，讲师使用以下代码在 Java 中实现平方根功能 -

public class Sqrt { 
    public static void main(String[] args) { 

        // read in the command-line argument
        double c = Double.parseDouble(args[0]);
        double epsilon = 1.0e-15;  // relative error tolerance
        double t = c;              // estimate of the square root of c

        // repeatedly apply Newton update step until desired precision is achieved
        while (Math.abs(t - c/t) > epsilon*t) {
            t = (c/t + t) / 2.0;
        }

        // print out the estimate of the square root of c
        System.out.println(t);
    }

}

但是，如果我将 while 循环条件稍微更改为 while (Math.abs(t - (c/t)) >= epsilon) 而不是 while (Math.abs( t - (c/t)) >= t * epsilon)，对于某些输入(例如 234.0.0.t)，程序陷入无限循环。

我使用 Eclipse 调试器，发现我的代码在某个点之后返回一个接近 234 平方根的 t 值，但仍然大于 EPSILON。并且使用更新公式，每次迭代后都会产生相同的 t 值，因此循环会永远卡在那里。

有人可以解释为什么程序在使用 >= EPSILON 时失败，但在使用 >= t * EPSILON 时工作得很好吗？根据我的理解，考虑到 EPSILON 的值极小，t * EPSILON 最终应该不会与 EPSILON 相差太大，但在程序中实现时差别却很大。

Answer 1

您实际上可以使用调试器来查看数字的进展情况，以及为什么当 epsilon 未乘以 t 时，234 的平方根会导致无休止的循环。

我使用带有日志记录断点的 IntelliJ 来查看数字的进展情况以及为什么会发生无休止的循环:

首先，我在日志断点中使用了这个表达式:

" " + Math.abs(t - c/t) + " " + epsilon

对于此代码:

private static void calcRoot(String arg) {
    // read in the command-line argument
    double c = Double.parseDouble(arg);
    double epsilon = 1.0e-15;  // relative error tolerance
    double t = c;              // estimate of the square root of c

    // repeatedly apply Newton update step until desired precision is achieved
    while (Math.abs(t - c/t) > epsilon ) {
        t = (c/t + t) / 2.0;
    }

    // print out the estimate of the square root of c
    System.out.println(t);
}

这是证明 epsilon 实际上小于 Math.abs(t - c/t) 的结果，而这个 Math.abs(t - c/t) 停止前进:

 233.0 1.0E-15
 115.50851063829788 1.0E-15
 55.82914775415816 1.0E-15
 24.47988606961853 1.0E-15
 7.647106514310517 1.0E-15
 0.927185521197492 1.0E-15
 0.014043197832668497 1.0E-15
 3.2230278765865705E-6 1.0E-15
 1.723066134218243E-13 1.0E-15
 1.7763568394002505E-15 1.0E-15
 1.7763568394002505E-15 1.0E-15
 1.7763568394002505E-15 1.0E-15
 1.7763568394002505E-15 1.0E-15
 1.7763568394002505E-15 1.0E-15
 1.7763568394002505E-15 1.0E-15
 1.7763568394002505E-15 1.0E-15
 ...

如果我随后使用 epsilon * t I 并将日志表达式更新为 ""+ Math.abs(t - c/t) + ""+ epsilon * t 我可以看到完全不同的控制台输出:

 233.0 2.34E-13
 115.50851063829788 1.175E-13
 55.82914775415816 5.974574468085106E-14
 24.47988606961853 3.1831170803771985E-14
 7.647106514310517 1.959122776896272E-14
 0.927185521197492 1.5767674511807463E-14
 0.014043197832668497 1.5304081751208715E-14
 3.2230278765865705E-6 1.529706015229238E-14
 1.723066134218243E-13 1.5297058540778443E-14

更新

如果您对 BigDecimal 类尝试相同的操作，您将能够计算 234 的平方根，以防您选择足够的舍入数字(请参阅比例变量如下):

private static void calcRootBig(String arg) {
    // read in the command-line argument
    BigDecimal c = new BigDecimal(arg);
    BigDecimal epsilon = new BigDecimal(1.0e-15);  // relative error tolerance
    BigDecimal t = new BigDecimal(c.toString());              // estimate of the square root of c
    BigDecimal two = new BigDecimal("2.0");

    // repeatedly apply Newton update step until desired precision is achieved
    int scale = 10;
    while (t.subtract(c.divide(t, scale, RoundingMode.CEILING)).abs().compareTo(epsilon) > 0) {
        t = c.divide(t, scale, RoundingMode.CEILING).add(t).divide(two, scale, RoundingMode.CEILING);
    }

    // print out the estimate of the square root of c
    System.out.println(t);
}

但是，如果您只选择 3 作为舍入比例，您将再次陷入无休止的循环。

所以看来是浮点除法的精度实际上导致了您的情况的无限循环。 epsilon * t 的乘法只是克服默认浮点运算中舍入精度不足的一个技巧。