Условие цикла при расчете квадратного корня методом Ньютона-Рафсона

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.

Я использовал отладчик 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 * 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, если выберете достаточное количество округляемых цифр (см. Ниже переменную 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 до 1e15, которое находится в пределахточность double, если это не точное значение и ошибка 0.например, попробуйте это для 256, и это может сработать, но все, что не является точным значением, вероятно, не сработает.

Простое решение для произвольной конечной точки - остановить, как только ошибка не улучшится содна итерация к следующей.Это даст вам наиболее точное решение с использованием этой формулы.