Метод Ньютона: квадратичная сходимость и её цена

Урок про метод Ньютона — самый быстрый классический метод поиска корня: как он устроен, почему так быстр и где предательски расходится.

Метод Ньютона приближает корень, заменяя функцию её касательной в текущей точке и беря за следующее приближение точку пересечения касательной с осью: $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$.

Идея: следуй за касательной

В точке $x_n$ проведём касательную к графику f. Около корня функция почти прямая, поэтому точка, где касательная пересекает ось, — отличное новое приближение. Геометрия даёт формулу: наклон касательной $f'(x_n)$, и она обнуляется при сдвиге $-f(x_n)/f'(x_n)$. Отсюда итерация $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$.

Та самая «вавилонская» формула для корня — это Ньютон для $f(x)=x^2-S$: $x - \frac{x^2-S}{2x} = \frac{x + S/x}{2}$. Не случайно она так быстра.

def ньютон(f, df, x0, eps=1e-14, max_iter=20):
    x = x0
    for n in range(1, max_iter + 1):
        fx = f(x)
        x_new = x - fx / df(x)
        print(f"шаг {n}: x = {x_new:.15f}   f(x) = {f(x_new):+.2e}")
        if abs(x_new - x) < eps:
            return x_new
        x = x_new
    return x

import math
# Корень x^2 - 2 = 0, старт x0 = 1
корень = ньютон(lambda x: x*x - 2, lambda x: 2*x, 1.0)
print(f"\nкорень  = {корень:.15f}")
print(f"sqrt(2) = {math.sqrt(2):.15f}")

Вывод:

шаг 1: x = 1.500000000000000   f(x) = +2.50e-01
шаг 2: x = 1.416666666666667   f(x) = +6.94e-03
шаг 3: x = 1.414215686274510   f(x) = +6.01e-06
шаг 4: x = 1.414213562374690   f(x) = +4.51e-12
шаг 5: x = 1.414213562373095   f(x) = +4.44e-16
шаг 6: x = 1.414213562373095   f(x) = -4.44e-16

корень  = 1.414213562373095
sqrt(2) = 1.414213562373095

Квадратичная сходимость

Посмотрите на показатели степени ошибки: $10^{-1}, 10^{-3}, 10^{-6}, 10^{-12}$ — число верных цифр примерно удваивается с каждым шагом. Это квадратичная сходимость: ошибка нового шага пропорциональна квадрату ошибки предыдущего, $e_{n+1} \approx C \cdot e_n^2$. Пять шагов — и 15 точных знаков. Бисекции на это понадобилось бы полсотни шагов. Вот почему Ньютон — рабочая лошадка везде, где есть производная: от калькуляторов до оптимизаторов нейросетей.

Где Ньютон ломается

За скорость приходится платить хрупкостью. Метод может разойтись или зациклиться:

Производная близка к нулю. Деление на $f'(x_n) \approx 0$ отбрасывает приближение далеко (почти горизонтальная касательная).
Плохой старт. Вдали от корня линейное приближение врёт, и итерация может уйти к другому корню или в бесконечность.
Зацикливание. На некоторых функциях точки прыгают по циклу, не приближаясь.

# f(x) = x^3 - 2x + 2. Старт x0 = 0 загоняет Ньютона в цикл 0 -> 1 -> 0 -> ...
def f(x):  return x**3 - 2*x + 2
def df(x): return 3*x**2 - 2

x = 0.0
for n in range(1, 9):
    x = x - f(x) / df(x)
    print(f"шаг {n}: x = {x:.6f}")

Вывод:

шаг 1: x = 1.000000
шаг 2: x = 0.000000
шаг 3: x = 1.000000
шаг 4: x = 0.000000
шаг 5: x = 1.000000
шаг 6: x = 0.000000
шаг 7: x = 1.000000
шаг 8: x = 0.000000

Метод честно застрял в цикле $0 \to 1 \to 0 \to 1$ и никогда не найдёт настоящий корень (он около $-1.77$). Это не редкость, а типичная опасность Ньютона при неудачном старте.

Как работает под капотом

Квадратичная сходимость выводится из ряда Тейлора: разложив f около корня $r$ и подставив в формулу Ньютона, получаем $e_{n+1} = \frac{f''(r)}{2f'(r)} \cdot e_n^2 + \ldots$ — ошибка квадратична, если $f'(r) \ne 0$ (простой корень) и старт достаточно близок. У кратного корня ($f'(r)=0$) сходимость падает до линейной. На практике Ньютон комбинируют с бисекцией (метод Брента): пока приближения «послушны» — Ньютон, как только улетают за отрезок — страховочный шаг бисекции. Так получают и скорость, и надёжность.

Частые ошибки

Запуск без защиты от $f'(x) \approx 0$. Проверяйте знаменатель; при близком к нулю наклоне делайте шаг бисекции.
Слишком далёкий старт. Грубо локализуйте корень (хоть бисекцией) и стартуйте рядом.
Нет лимита итераций. Без max_iter зацикливание или расходимость подвесят программу.

Итоги

Ньютон: $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$ — следование за касательной.
Квадратичная сходимость у простого корня: число верных цифр удваивается за шаг.
Требует производной и хорошего старта; без них расходится, зацикливается или делит на ~0.
Надёжный вариант — гибрид с бисекцией (метод Брента): скорость Ньютона плюс гарантия бисекции.