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

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

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

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

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

Та самая «вавилонская» формула для корня — это Ньютон для f(x)=x²−S: x − (x²−S)/(2x) = (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} ≈ C·e_n². Пять шагов — и 15 точных знаков. Бисекции на это понадобилось бы полсотни шагов. Вот почему Ньютон — рабочая лошадка везде, где есть производная: от калькуляторов до оптимизаторов нейросетей.

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

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

Производная близка к нулю. Деление на f'(x_n) ≈ 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 → 1 → 0 → 1 и никогда не найдёт настоящий корень (он около −1.77). Это не редкость, а типичная опасность Ньютона при неудачном старте.

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

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

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

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

Итоги

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