Метод Ньютона: быстрая сходимость по касательной

Если бисекция надёжна, но медленна, то метод Ньютона стремителен — он удваивает число верных цифр за шаг.

Метод Ньютона ищет корень, скользя по касательным: от текущей точки он идёт туда, где касательная к графику пересекает ось x.

Идея метода

Стоим в точке x. Проводим касательную к графику (её наклон — производная $f'(x)$). Касательная — прямая, её корень найти легко; принимаем его за следующее приближение:

$$x_{\text{next}} = x - \frac{f(x)}{f'(x)}$$

Повторяем. Если старт близко к корню и функция «приличная», метод сходится поразительно быстро.

       f(x)
        |   /
        |  /  <- касательная в точке x
   ─────+─●──────── x
        | x_next  <- корень касательной = новое приближение

Реализация на чистом Python

Найдём $\sqrt{2}$ как корень $f(x) = x^2 - 2$, у которого $f'(x) = 2x$:

def f(x):
    return x * x - 2

def df(x):
    return 2 * x

x = 1.0                         # стартовое приближение
for step in range(6):
    x = x - f(x) / df(x)        # шаг Ньютона
    print("шаг", step + 1, "->", x)

print("Точно sqrt(2) =", 2 ** 0.5)

Вывод:

шаг 1 -> 1.5
шаг 2 -> 1.4166666666666667
шаг 3 -> 1.4142156862745099
шаг 4 -> 1.4142135623746899
шаг 5 -> 1.4142135623730951
шаг 6 -> 1.414213562373095
Точно sqrt(2) = 1.4142135623730951

Смотрите, как стремительно: уже на 4-м шаге совпали 13 знаков. Это и есть знаменитая квадратичная сходимость — число верных цифр примерно удваивается за итерацию.

А в SciPy — одна строка

from scipy.optimize import newton

root = newton(lambda x: x**2 - 2, x0=1.0, fprime=lambda x: 2*x)
print(root)   # 1.4142135623730951

# производную можно не давать — SciPy оценит её численно (метод секущих)
root2 = newton(lambda x: x**2 - 2, x0=1.0)
print(root2)  # тоже ~1.41421356

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

Откуда берётся квадратичная сходимость? Касательная — это первые два члена ряда Тейлора функции. Отбрасывая остаток (~ ошибка²), мы на каждом шаге «съедаем» квадрат предыдущей погрешности: если ошибка была 0.01, станет ~0.0001, потом ~0.00000001. Отсюда удвоение точных цифр. Но у скорости есть цена: метод требует производную и хороший старт. Если $f'(x)$ близко к нулю (горизонтальная касательная), следующее приближение «улетит» далеко; при неудачном старте метод может зациклиться или разойтись.

Бисекция против Ньютона

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

• Производная около нуля. Деление на крошечное $f'(x)$ выбрасывает приближение в космос.
• Плохой старт. Далеко от корня метод может уйти не туда или зациклиться между двумя точками.
• Нет проверки сходимости. Всегда ставьте лимит итераций и порог по $|f(x)|$, иначе цикл может не закончиться.

Итог

• Метод Ньютона идёт по касательной: $x - f(x)/f'(x)$.
• Квадратичная сходимость — число верных цифр удваивается за шаг.
• Цена скорости: нужны производная и хороший старт; гарантии нет.
• В SciPy — newton (с производной или без, тогда метод секущих).