使用 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，它可能会起作用，但任何不是精确值的东西都可能不起作用。对任意端点的简单解决方案是，一旦错误从一次迭代到下一次迭代没有改善，就停止。这将为您提供使用此公式的最准确的解决方案。