Объяснение примера метода Ньютона на Java

Question

http://introcs.cs.princeton.edu/java/13flow/Sqrt.java.html:

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

        // read in the command-line argument
        double c = Double.parseDouble(args[0]);
        double epsilon = 1e-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);
    }

}

Дело в том ... Я прекрасно понимаю, как работает сама программа.У меня проблема с уравнением f (x) = x ^ 2 - c и как это связано с кодом выше.Мол, зачем делить его на х так, чтобы х (х - с / х)?Кажется, что в некоторых из этих примеров отсутствует математическое объяснение.Другими словами, я ищу объяснение с простой математической точки зрения, а не столько кода.

Answer 1

Вам дано c, и вы хотите решить

t = sqrt(c)

или, что эквивалентно,

c = t^2

или еще раз,

c - t^2 = 0.

I 'назовем вышеприведенное уравнение f(t) = 0 (без упоминания c, так как это заданная константа).Метод Ньютона перебирает пробные значения t, которые я обозначу t_i, t_{i+1}, ....

Расширение Тейлора до 1-го порядка:

f(t_i + dt_i) = f(t_i) + dt_i * f'(t_i) + ...

Так что, если вы не совсемf(t_i) = 0, вы добавляете dt_i таким образом, что

f(t_i + dt_i) nearly = 0 = f(t_i) + dt_i * f'(t_i) + ...

То есть dt_i = -f(t_i) / f'(t_i), то есть f(t_i + -f(t_i) / f'(t_i)) ближе к нулю, чем f(t_i).

Если вы сделаетепроизводные от f(t) = c - t^2, вы увидите, что уравнение в коде t_{i+1} = (c / t_i + t_i) / 2 - это просто итерационная формула t_{i+1} = t_i + dt_i с оценкой dt_i, приведенной выше.

Это итерационный метод, поэтому он недать точное решение.Вам нужно решить, когда вы хотите остановиться (достаточная точность), иначе алгоритм будет работать вечно.Вот почему вы проверяете f(t_i) < threshold вместо истинного f(t_i) = 0.В их случае они выбрали threshold = epsilon * t^2;Я думаю, что умножение на t^2 было использовано, потому что, если вы использовали фиксированную константу в качестве порога, вы можете столкнуться с проблемами числовой точности (то есть, если вы играете с триллионами, вы никогда не сможете получить фиксированную точность 10^{-10} из-законечная точность представления с плавающей точкой.)

Answer 2

Хорошо, я сделаю это (см. Встроенные комментарии):

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

        // read in the command-line argument (i.e. this is the value that we want
        // square root from.)
        double c = Double.parseDouble(args[0]); 

        // Since the the square root of non-squares are irrational, we need some
        // error tolerance.  In other words, if the answer is less than epsilon wrong
        // we'll take it.  
        double epsilon = 1e-15;    // relative error tolerance

        // t is our first guess (c / 2.0 works well too - in fact it tends to be
        // better.)
        double t = c;              // estimate of the square root of c

        // repeatedly apply Newton update step until desired precision is achieved
        // The condition here is rather elegant and optimized... to see why it works,
        // simply break it up.  The absolute is there to cater for negative values, but
        // for c >= 0:
        //   | c - c/t | > epsilon * t
        //   t * ( t - c / t ) > epsilon
        //   tt - c = > epsilon)
        while (Math.abs(t - c/t) > epsilon*t) {
            // Improve the guess by applying Newton's genius :-)
            // Take the original number, divide by the guess add t and take the
            // average.
            t = ( c / t + t) / 2.0;
        }

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

}

Answer 3

На основе кода в комментарии Javadoc уже объяснено следующее:

 *  Computes the square root of a nonnegative number c using
 *  Newton's method:
 *     - initialize t = c
 *     - replace t with the average of c/t and t
 *     - repeat until desired accuracy reached

Answer 4

ejlab.net jelmar

Я полагаю, что вышеупомянутый код взят из книги Р. Седжвика «Введение в программирование на Java», стр. 62. В книге он пытается сказать, что вы можете использовать f(x)=x^2-c как особый случай, чтобы найти квадрат корень любого положительного числа. Итак, как это работает:

Состояния метода Ньютона X(n+1)=X(n)-(F(X(n))/F'(X(n))). Предположим, что в F(X)=X^2-C, где C=2, так как мы ищем квадратный корень из 2 (если вы хотите найти квадратный корень из 36, тогда C=36 и т. Д.). Тогда первая производная функции F(X) равна F'(X)=2X. Применяя метод Ньютона, мы получаем

X(n+1)=X(n)-((X^2-C)/(2X))

для X(0)=2 получаем n=1, X(1)=2-(2^2-2)/(2*2)> X(1)=1.5; n=2 X(2)=1.5 -(1.5^2-2)/(2*1.5)> X(2)=1.41666667 и так далее ...