Математика / Начала анализа

Метод тяжёлого шарика: инерционный шаг для квадратичной цели

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

Опубликовано: 28 октября 2026 г.Обновлено: 28 октября 2026 г.

Математический анализ Алгебра Страницы с задачами и решениями Есть историческая справка

Формула

x_{k+1}=x_k-\alpha\nabla f(x_k)+\beta(x_k-x_{k-1})

Схема Затухающие перелёты через минимум

Последовательность для α=1/2, β=1/4: 1;0,5;0,125;−0,03125;−0,0546875;−0,033203125.

Обозначения

$xₖ,xₖ₋₁$: два последовательных вектора, безразмерная
$α$: положительный градиентный шаг, безразмерная
$β$: коэффициент инерции, безразмерная
$λ$: собственное значение положительно определённой матрицы цели, безразмерная
$r$: корень характеристического уравнения ошибки, безразмерная

Условия применения

Основные утверждения ниже относятся к f(x)=xᵀAx/2−bᵀx, где A=Aᵀ≻0 и все координаты безразмерны. Для постоянных 0≤β<1 достаточно 0<αλ<2(1+β) для каждого собственного значения λ. Начальные две точки задаются явно.

Ограничения

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

Подробное объяснение

Обычный градиентный шаг использует только текущую производную. Добавка β(xₖ−xₖ₋₁) переносит часть уже набранного движения. При одинаковом направлении нескольких поправок они складываются; если градиент меняет знак, сохранённая инерция способна вызвать перелёт через минимум.

Для квадратичной цели ошибка eₖ=xₖ−x* удовлетворяет eₖ₊₁=(I−αA+βI)eₖ−βeₖ₋₁. В собственном направлении A с числом λ это скалярная рекурсия eₖ₊₁=(1−αλ+β)eₖ−βeₖ₋₁. Её характеристический многочлен r²−(1−αλ+β)r+β определяет затухание.

Оба корня должны иметь модуль меньше 1. При 0≤β<1 это эквивалентно положительности αλ и условию αλ<2(1+β). Неравенство следует проверять для всего спектра, а не одной удобной координаты. Комплексные корни означают затухающие колебания, если их модуль меньше 1.

Часто задают x₋₁=x₀, чтобы начальная инерция была нулевой. Это соглашение не является обязательной частью метода и должно быть указано в расчёте. Сравнивать алгоритмы по первым двум шагам без одинаковой инициализации некорректно: начальный запас движения способен изменить всю траекторию.

Как пользоваться формулой

Задайте две начальные точки и проверьте, равны ли они; их разность задаёт начальное инерционное перемещение в первом шаге.
Вычислите градиент в xₖ, отдельно найдите градиентную поправку и β(xₖ−xₖ₋₁), после чего сложите их с текущей точкой.
Для квадратичной модели проверьте характеристические корни на крайних собственных значениях или условие 0<αλ<2(1+β).
Сохраняйте старое xₖ перед переходом; оценивайте норму ошибки или градиента, учитывая возможное немонотонное изменение цели.

Историческая справка

Работа Б. Т. Поляка «О некоторых способах ускорения сходимости итерационных методов» опубликована в 1964 году в «Журнале вычислительной математики и математической физики», том 4, номер 5. Она является первичным источником инерционного подхода, известного как метод тяжёлого шарика.

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

Современная литература по ускоренным методам отдельно подчёркивает ограничения квадратичного спектрального анализа. Обсуждение Wilson, Recht и Jordan показывает, почему выводы для квадратичной цели не переносятся автоматически на общий выпуклый случай. Отдельные варианты momentum имеют разные точки вычисления градиента и разные гарантии.

Историческая линия формулы

Инерционная схема тяжёлого шарика связывается с работой Б. Т. Поляка 1964 года. Здесь разобрана постоянная двухшаговая итерация на квадратичной цели; её нельзя отождествлять со всеми современными методами momentum или с ускорением Нестерова.

Пример

Возьмём f(x)=x²/2, x₋₁=x₀=1, α=1/2, β=1/4. Первый шаг: x₁=1−0,5·1+0=0,5. Второй: x₂=0,5−0,5·0,5+0,25(0,5−1)=0,125. Третий: x₃=0,125−0,0625+0,25(0,125−0,5)=−0,03125. Метод перелетел через нуль, но модуль ошибки мал. Характеристический многочлен r²−0,75r+0,25 имеет отрицательный дискриминант−0,4375; модуль каждого комплексного корня равен√0,25=0,5. Следовательно, траектория затухает с колебаниями. Это проверка данной квадратичной модели; она не доказывает ту же скорость для произвольной нелинейной цели.

Частая ошибка

Не прибавляйте предыдущую точку вместо предыдущего перемещения. Не обновляйте xₖ до вычисления разности с xₖ₋₁. Не путайте тяжёлый шарик с методом Нестерова, где производная берётся в другой точке. Сходимость ошибки и монотонное уменьшение функции — разные свойства; одно не заменяет другое.

Практика

Задачи с решением

Нулевая инерция

Условие. Для f=x², x₀=2, β=0 и α=1/4 найдите два шага.

Решение. ∇f=2x. x₁=2−(1/4)·4=1; x₂=1−(1/4)·2=1/2. При β=0 вторая начальная точка не влияет.

Ответ. x₁=1, x₂=0,5.

Неустойчивый шаг

Условие. λ=4, α=1, β=1/4. Проверьте условие и корни.

Решение. αλ=4>2(1+1/4)=2,5. Многочлен r²+2,75r+0,25 имеет корни(−11±√105)/8, примерно−0,0941 и−2,6559.

Ответ. Один корень по модулю>1: общая сходимость не гарантирована.

Дополнительные источники

https://www.mathnet.ru/php/archive.phtml?jrnid=zvmmf&option_lang=rus&paperid=7713&wshow=paper
https://jmlr.org/papers/volume22/20-195/20-195.pdf

Связанные формулы

Математика

Градиентный спуск с постоянным шагом: условие убывания

$x_{k+1}=x_k-\alpha\nabla f(x_k),\quad 0<\alpha<2/L,\quad f(x_{k+1})\le f(x_k)-\alpha(1-L\alpha/2)\|\nabla f(x_k)\|^2$

Постоянный шаг градиентного спуска смещает точку против градиента. При липшицевом градиенте известная граница шага обеспечивает уменьшение функции и объясняет, почему слишком крупный шаг вызывает расходимость.

Математика

Метод Ньютона для минимума: шаг через матрицу Гессе

$H_k d_k=-g_k,\qquad x_{k+1}=x_k+\alpha_k d_k$

Метод Ньютона выбирает шаг по квадратичной модели целевой функции: матрица Гессе учитывает кривизну, а градиент задаёт линейную часть. Решение системы даёт направление, но длину шага иногда приходится уменьшать.

Математика

Покоординатный спуск для выпуклой квадратичной функции

$x_i^{+}=x_i-\frac{(Ax-b)_i}{A_{ii}},\quad f(x)=\tfrac12x^TAx-b^Tx$

Покоординатный спуск минимизирует функцию по одной переменной при фиксированных остальных. Для положительно определённой квадратичной цели точное обновление получается делением компоненты градиента на диагональ матрицы.