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

Question

我目前正在学习一门课程，讲师使用以下代码在 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），程序会陷入无限循环。我使用了 Eclipse 调试器，发现我的代码在某个点之后返回的 t 值接近 234 的平方根，但仍然大于 EPSILON。并且使用更新公式，每次迭代后都会产生相同的 t 值，因此循环会永远卡在那里。有人可以解释为什么程序在使用时失败>= EPSILON但在使用时工作得很>= t * EPSILON好吗？据我了解，鉴于 EPSILON 的值极小，t * EPSILON 最终不应与 EPSILON 相差太大，但在程序中实现时差异很大。

Answer 1

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

我已经使用带有日志断点的 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 * tI 并将日志记录表达式更新为" " + 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以防你选择足够的四舍五入数字（见scale下面的变量）：

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只是克服默认浮点运算中舍入精度不足的一个技巧。

Answer 2

double具有大约 15 位精度（或 1 到 2^52 或 4.5e15）。当您计算t * epsilon您需要 1 与1e15/234可能的比率的误差double时，当您使用时，epsilon您需要 1 与 1 的比率，该比率处于1e15double 精度的极限，除非它是一个精确值并且错误是0. 例如，试试这个256，它可能会起作用，但任何不是精确值的东西都可能不起作用。

对任意端点的简单解决方案是，一旦错误从一次迭代到下一次迭代没有改善，就停止。这将为您提供使用此公式的最准确的解决方案。