Ньютон: учитываем кривизну

Метод Ньютона строит в каждой точке параболу-приближение и сразу прыгает в её вершину — отсюда фантастическая скорость.

Метод Ньютона минимизирует функцию по правилу $x_{k+1}=x_k-[\nabla^2 f(x_k)]^{-1}\nabla f(x_k)$, используя кривизну (гессиан), а не только наклон.

Идея: парабола вместо прямой

Градиентный спуск видит только наклон и потому шагает «вслепую» на $\alpha$. Метод Ньютона использует и кривизну: он приближает функцию вблизи $x_k$ квадратичной моделью (парабола/чаша) по формуле Тейлора и прыгает прямо в её вершину. Для квадратичной функции это попадание в минимум за один шаг.

Минимум квадратичной модели $f(x_k)+\nabla f^\top p+\tfrac12 p^\top\nabla^2 f\,p$ достигается там, где её градиент нулевой: $\nabla^2 f\,p+\nabla f=0$, откуда шаг $p=-[\nabla^2 f]^{-1}\nabla f$. Это и есть формула Ньютона:

$$x_{k+1}=x_k-[\nabla^2 f(x_k)]^{-1}\,\nabla f(x_k).$$

Одномерный случай

В 1D гессиан — это просто $f''$, и формула упрощается:

$$x_{k+1}=x_k-\frac{f'(x_k)}{f''(x_k)}.$$

Это тот же ньютоновский поиск корня, но применённый к уравнению $f'(x)=0$. Минимизировать $f$ = найти корень её производной.

Реализация 1D и квадратичная сходимость

Минимизируем $f(x)=x^4-3x^3+2$. Производные: $f'=4x^3-9x^2$, $f''=12x^2-18x$. Минимум там, где $f'=0$, $x\ne0$: $x=9/4=2.25$.

def fp(x):   # f'(x)
    return 4 * x ** 3 - 9 * x ** 2

def fpp(x):  # f''(x)
    return 12 * x ** 2 - 18 * x

x = 3.0
for k in range(1, 7):
    x = x - fp(x) / fpp(x)
    err = abs(x - 2.25)
    print(f"шаг {k}: x={x:.10f}  ошибка={err:.2e}")

Вывод:

шаг 1: x=2.5000000000  ошибка=2.50e-01
шаг 2: x=2.2916666667  ошибка=4.17e-02
шаг 3: x=2.2514619883  ошибка=1.46e-03
шаг 4: x=2.2500018962  ошибка=1.90e-06
шаг 5: x=2.2500000000  ошибка=3.20e-12
шаг 6: x=2.2500000000  ошибка=4.44e-16

Посмотрите на ошибку: $0.25\to 0.04\to 0.001\to 10^{-6}\to 10^{-13}$. Число верных цифр примерно удваивается каждый шаг — это квадратичная сходимость. Градиентному спуску на такую точность понадобились бы десятки-сотни итераций.

Многомерный пример

В $n$ измерениях нужно решить систему $\nabla^2 f\,p=-\nabla f$. Для $2\times2$ обратим гессиан вручную (формула $2\times2$).

def grad(v):
    x, y = v
    return [2 * x + y, x + 2 * y]          # f = x^2 + xy + y^2

def solve2(H, b):                          # решаем H p = b для 2x2
    a, bb, c, d = H[0][0], H[0][1], H[1][0], H[1][1]
    det = a * d - bb * c
    return [(d * b[0] - bb * b[1]) / det, (-c * b[0] + a * b[1]) / det]

H = [[2, 1], [1, 2]]                        # гессиан постоянен (квадратичная f)
x = [4.0, -3.0]
g = grad(x)
p = solve2(H, [-g[0], -g[1]])
x = [x[0] + p[0], x[1] + p[1]]
print("После 1 шага Ньютона: x =", [round(c, 6) for c in x])
print("Градиент в новой точке:", grad(x))

Вывод:

После 1 шага Ньютона: x = [0.0, 0.0]
Градиент в новой точке: [0.0, 0.0]

Для квадратичной функции Ньютон попал в минимум $(0,0)$ за один шаг из любой стартовой точки — никаких оврагов, никакой осцилляции. Гессиан «знает» форму чаши целиком.

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

Сила Ньютона — в инвариантности к масштабу: умножение гессианом «выпрямляет» овраги, поэтому метод не страдает от большого числа обусловленности. Но есть три «но». Первое: гессиан стоит $O(n^2)$ памяти и $O(n^3)$ на решение системы — для больших $n$ запретительно. Второе: вдали от минимума гессиан может быть незнакоопределён, и шаг Ньютона укажет в сторону роста — нужна страховка (демпфирование, line search, сдвиг гессиана). Третье: нужны вторые производные, которых часто нет. Эти проблемы решают квазиньютоновские методы.

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

Чистый Ньютон вдали от минимума. Без line search или демпфирования он может разойтись, если гессиан плохой.
Делить на $f''$ около перегиба. При $f''\approx 0$ шаг $f'/f''$ взрывается.
Применять к огромным $n$. $O(n^3)$ убивает; там нужны BFGS или градиентные методы.

Итоги

Ньютон: $x_{k+1}=x_k-[\nabla^2 f]^{-1}\nabla f$ — прыжок в вершину квадратичной модели.
Квадратичная сходимость: число верных цифр удваивается за шаг; на квадратичной функции — один шаг.
Цена: $O(n^2)$ память, $O(n^3)$ решение, нужен знакоопределённый гессиан и страховка вдали от минимума.