Метод Ньютона

Единственные требования, накладываемые на функцию $f$ — что у неё есть хотя бы один корень и что она непрерывна и дифференцируема на интервале поиска.

#Описание алгоритма

Алгоритм начинает с какого-то изначального приближения $x_0$ и затем итеративно строит лучшее решение, строя касательную к графику в точке $x = x_i$ и присваивая в качестве следующего приближения $x_{i+1}$ координату пересечения касательной с осью $x$. Интуиция в том, что если функция $f$ «хорошая», и $x_i$ уже достаточно близок к корню, то $x_{i+1}$ будет ещё ближе.

Чтобы получить точку пересечения для $x_i$, нужно приравнять уравнение касательной к нулю:

Метод Ньютона крайне важен в вычислительной математике: в большинстве случаев именно он используется для нахождения численных решений уравнений.

#Поиск квадратных корней

В качестве конкретного примера рассмотрим задачу нахождения квадратных корней, которую можно переформулировать как решение следующего уравнения:

Если нам нужно посчитать корень с некоторой заданной точностью $\epsilon$, можно на каждой итерации делать соответствующую проверку:

const double eps = 1e-9;

double sqrt(double n) {
    double x = 1;
    while (abs(x * x - n) > eps)
        x = (x + n / x) / 2;
    return x;
}

Алгоритм успешно сходится к правильному ответу для многих функций, однако это происходит надежно и доказуемо только для определенного множества функций (например, выпуклых). Другой вопрос — как быстра эта сходимость, если она происходит.

#Скорость сходимости

Запустим метод Ньютона для поиска квадратного корня $2$, начиная с $x_0 = 1$, и посмотрим, сколько первых цифр оказались правильными после каждой итерации:

1.0000000000000000000000000000000000000000000000000000000000000
1.5000000000000000000000000000000000000000000000000000000000000
1.4166666666666666666666666666666666666666666666666666666666675
1.4142156862745098039215686274509803921568627450980392156862745
1.4142135623746899106262955788901349101165596221157440445849057
1.4142135623730950488016896235025302436149819257761974284982890
1.4142135623730950488016887242096980785696718753772340015610125
1.4142135623730950488016887242096980785696718753769480731766796

Можно заметить, что число корректных цифр примерно удваивается после каждой итерации. Такая прекрасная скорость сходимости не просто совпадение.

Чтобы оценить скорость сходимости численно, рассмотрим небольшую относительную ошибку $\delta_i$ на $i$-ой итерации и посмотрим, насколько меньше станет ошибка $\delta_{i+1}$ на следующей итерации.

Здесь мы разложили $(1 + \delta_i)^{-1}$ в ряд Тейлора в точке $0$, используя предположение что ошибка $d_i$ мала: так как последовательность $x_i$ сходится к $x$, то $d_i \ll 1$ для достаточно больших $n$.

Наконец, выражая $\delta_{i+1}$, получаем

что означает, что относительная ошибка примерно возводится в квадрат и делится пополам на каждой итерации, когда мы уже близки к решению. Так как логарифм $(- \log_{10} \delta_i)$ примерно равен числу правильных значимых цифр числа $x_i$, возведение ошибки в квадрат соответствует удвоению значимых цифр ответа, что мы и наблюдали ранее.

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