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

вопрос создан в Thu, May 2, 2019 12:00 AM

В настоящее время я прохожу курс, где инструктор использовал следующий код для реализации функции квадратного корня в 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, но разница, когда он реализован в программе, огромна.

    
1
  1. Использование = с double (или любого другого типа float в этом отношении) чревато опасностями, поскольку некоторые числа с плавающей запятой могут неожиданно совпадать.
    2019-05-02 14: 58: 02Z
2 ответа                              2                         

double имеет около 15 цифр точности (или от 1 до 2 ^ 52 или 4.5e15). Когда вы вычисляете t * epsilon вокруг вас, требуя погрешности от 1 до 1e15/234, которая возможна с double, когда вы используете epsilon, вам требуется соотношение от 1 до 1e15, если только это значение не является двойным с точностью, равной точному с точностью до предела точности, равной двум точным с точностью до предела точности, равной точному с точностью до двукратного значения, не превышающего точности с точностью, равной двойной точности ошибка 0. напр. попробуйте это для 256, и это может сработать, но все, что не является точным значением, вероятно, не сработает.

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

    
0
2019-05-03 08: 24: 31Z
  1. Не могли бы вы уточнить, как были получены эти соотношения или цифры точности? Я имею в виду, я не понимаю, как вы получили эти отношения 1 to 1e15 или 1 to 254e15.
    2019-05-03 00: 36: 17Z
  2. Вы указываете epsilon = 1e-15, поэтому разница между t и c / t может составлять t * epsilon, что имеет соотношение (t - c/t) / (t * epsilon) или 625050000000000000000000000000000000000016 /234, что является меньшим отношением.
    2019-05-03 08: 22: 56Z
  3. @ Ratus Хороший вопрос о числах, соотношение было выключено. +1
    2019-05-03 08: 25: 03Z
  4. Это объяснение полностью имеет смысл. Проблема действительно достигла пределов двойной точности. Я могу использовать предыдущий код (для ввода 234), изменив t на (t - c/t) / epsilon, но, конечно, по мере того, как число ввода увеличивается, eps необходимо изменить еще раз. Таким образом, использование 1e-14 - это действительно умный способ сохранить хороший чек.
    2019-05-03 09: 36: 43Z

На самом деле вы можете использовать отладчик, чтобы увидеть, как прогрессируют числа и почему, например, квадратный корень из 234 вызывает бесконечный цикл, когда eps не умножается на t * epsilon.

Я использовал IntelliJ с точкой останова регистрации, чтобы увидеть, как прогрессируют числа и почему происходит бесконечный цикл:

 введите описание изображения здесь

Сначала я использовал это выражение в точке прерывания ведения журнала:

epsilon

для этого кода:

t

и это результат, доказывающий, что

" " + 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) I и обновлю выражение ведения журнала на

 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

Обновление

Если вы попробуете то же самое с классом " " + 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

Тем не менее, если вы выберете только 3 для шкалы округления, вы снова попадете в бесконечный цикл.

Итак, похоже, что именно точность деления с плавающей запятой фактически вызывает бесконечный цикл в вашем случае. Умножение scale - всего лишь хитрость, позволяющая преодолеть отсутствие точности округления в операциях с плавающей запятой по умолчанию.

    
1
2019-05-03 07: 24: 17Z
  1. Это не отвечает на мой вопрос. Это показывает только то, что я уже пробовал и упоминал в вопросе.
    2019-05-03 01: 49: 17Z
  2. @ Ратус, вы правы. Пожалуйста, проверьте мое обновление с использованием
    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);
    }
    
    .
    2019-05-03 07: 25: 13Z
epsilon * t
источник размещен Вот