Как понять метод Ньютона для квадратного корня в Java?

public static double sqrt(double c)
{
    if (c < 0) return Double.NaN;
    double t = c;                          // line 1
    double err = 1e-15;                    // line 2
    while (Math.abs(t - c/t) > err * t)    // line 3
        t = (c/t + t) / 2.0;           // line 4
    return t;
}

Q1: Меня смущает переменная t в строке 1 и строке 4: поскольку t = c, то c/t = 1, что означает строка 4?

Q2: В строке 3, какова цель проверки?

Я искал "метод Ньютона" и получил несколько объяснений, но так и не смог понять. Могу ли я запросить прямое объяснение здесь?


java newtons-method
person Nick    schedule 23.05.2014    source источник
comment
Отлаживайте код шаг за шагом и наблюдайте за переменными и/или их значениями.   -  person assylias    schedule 23.05.2014

Ответы (2)


arrow_upward
3
arrow_downward

Q1: Обратите внимание, что t меняется с каждой итерацией цикла, поэтому, хотя изначально c/t==1, после этого этого не произойдет.

Q2: Мы хотим, чтобы цикл продолжался до тех пор, пока мы не получим ответ «достаточно близко», как определено err.

person Scott Hunter    schedule 23.05.2014

arrow_upward
2
arrow_downward

Метод Ньютона используется для аппроксимации корней вещественных функций. См. здесь.

Когда вы вычисляете корень для двойного значения, вы на самом деле пытаетесь решить для F(x) = X^2 - C, где C - это двойное значение, и вы пытаетесь найти x, который делает уравнение равным нулю.

Теперь Newton's Method аппроксимирует это серией предположений. С каждым предположением (поскольку эта функция имеет соответствующие свойства) мы приближаемся к квадратному корню. Инкрементное приближение фактически вычисляет касательную к графику при каждом предположении (t), а затем выбирает его в качестве предположения в этой точке и приближается по шагам (c/t + t)/2. В какой-то момент мы подходим очень близко, и мы не хотим, чтобы функция работала вечно, поэтому у нас есть строка 3, чтобы проверить, что наша следующая оценка имеет определенное расстояние от текущего приближения. Если следующее приближение ближе, чем err*t, мы не будем продолжать. Мы достаточно близко.

person Farhad Alizadeh Noori    schedule 23.05.2014