Математика / Численное решение линейных систем
Наискорейший спуск для линейной системы: точный шаг
Наискорейший спуск для симметричной положительно определённой системы выбирает длину шага по текущей невязке. Шаг минимизирует квадратичную энергию вдоль направления спуска.
Формула
Минимум параболы приходится на s=5/17. Удвоенный шаг возвращает энергию к исходному уровню.
Обозначения
- $A$
- симметричная положительно определённая матрица, —
- $b$
- вектор правой части, —
- $xₖ$
- текущее приближение, —
- $rₖ$
- невязка b−Axₖ, —
- $k$
- номер итерации, —
Условия применения
Матрица вещественная, симметричная и положительно определённая. При ненулевой невязке rᵀAr строго положительно. Если r=0, решение уже найдено и вычислять коэффициент шага не нужно.
Ограничения
При большом отношении крайних собственных чисел даже точный выбор шага вдоль невязки оставляет медленную сходимость. Для несимметричной матрицы вывод через градиент квадратичной энергии неприменим: градиент использовал бы симметричную часть.
Подробное объяснение
Систему Ax=b можно понимать как задачу о минимуме функции F(x)=xᵀAx/2−bᵀx. Её градиент Ax−b обращается в ноль в решении. Положительная определённость даёт единственный минимум и превращает линии уровня в эллипсоиды вокруг него.
При движении из x вдоль r функция приращения равна −s·rᵀr+s²·rᵀAr/2. Линейный член отвечает за начальное падение энергии, а квадратный останавливает это падение. Приравняв производную по s к нулю, получаем положительный шаг из формулы.
Новая невязка равна r−sAr. Её скалярное произведение со старой равно нулю именно при выбранном шаге. Это не означает, что следующая итерация продолжит работу в новом независимом подпространстве: соседние направления ортогональны в обычной метрике, а не в метрике A.
На вытянутом эллипсе направление градиента может смотреть почти поперёк длинной оси. Последовательные шаги пересекают узкую долину и медленно продвигаются вдоль неё. Если же текущая невязка совпала с собственным направлением A, шаг равен обратному собственному числу и устраняет эту невязку целиком.
Как пользоваться формулой
- Вычислите b−Axₖ в исходных координатах. При нулевой невязке завершите расчёт без деления.
- Один раз умножьте A на текущую невязку, чтобы получить вектор Arₖ для знаменателя и обновления.
- Разделите квадрат евклидовой нормы rₖ на скалярное произведение rₖᵀArₖ, сохраняя точность до конца шага.
- Прибавьте к текущему приближению вектор αₖrₖ и проверьте результат прямым умножением A на новое приближение.
Историческая справка
В статье Хестенеса и Штифеля 1952 года о сопряжённых градиентах решение системы с положительно определённой матрицей связано с минимумом квадратичной формы. Это позволяет сравнивать способы выбора направления независимо от представления системы отдельными строками. При движении только вдоль остатка минимум на прямой даёт формулу одного шага наискорейшего спуска.
В учебном тексте Джонатана Шевчука 1994 года этот шаг разобран до перехода к сопряжённым направлениям. На линиях уровня видно, откуда берётся зигзаг и почему локально лучший шаг может оказаться частью медленной последовательности. Запись через скалярные произведения переносит тот же вывод с рисунка в плоскости на систему произвольной размерности.
Историческая линия формулы
Одномерная минимизация квадратичной формы определяет коэффициент шага; отдельного автора этой алгебраической записи указывать не требуется. Хестенес и Штифель дают контекст перехода к сопряжённым направлениям, а Шевчук подробно выводит шаг спуска для линейной системы.
Пример
Решаем систему с A=diag(1,4), b=(1,2) и x₀=(0,0). Найдём первый точный шаг вдоль невязки и проверим условие оптимальности на этой прямой. Невязка r₀=(1,2), а Ar₀=(1,8). Числитель равен 1²+2²=5, знаменатель 1·1+2·8=17. Поэтому α₀=5/17 и x₁=(5/17,10/17). Прямое умножение даёт Ax₁=(5/17,40/17), откуда r₁=(12/17,−6/17). Проверка: (1,2)·(12/17,−6/17)=0. Энергия в начале равна нулю, а после шага равна −25/34. Все числа в этой абстрактной системе без физических единиц; знак энергии отражает выбранный ноль, а не ошибку.
Частая ошибка
Не подставляйте Ax−b в ту же формулу со знаком плюс: получится подъём. Знаменатель rᵀAr не равен квадрату нормы Ar; с последним строят другой критерий. Наконец, проверяйте невязку отдельно: падение энергии показывает продвижение к минимуму, но малый шаг сам по себе не удостоверяет точное решение.
Практика
Задачи с решением
Вторая итерация
Условие. В примере сделайте ещё один шаг с точным выбором коэффициента.
Решение. У r₁=(12,−6)/17 квадрат нормы равен 180/289, а r₁ᵀAr₁=288/289. Шаг 5/8, поэтому прибавляем к x₁ вектор (15/34,−15/68).
Ответ. x₂=(25/34,25/68).
Остаток на собственной оси
Условие. У A=diag(2,5), b=(0,10), x₀=0 найдите x₁.
Решение. r₀=(0,10), Ar₀=(0,50). Берём α=100/500=1/5 и умножаем на r₀. Подстановка во второе уравнение даёт 5·2=10.
Ответ. x₁=(0,2), невязка нулевая.
Дополнительные источники
- https://nvlpubs.nist.gov/nistpubs/jres/049/jresv49n6p409_A1b.pdf
- https://ics.uci.edu/~smyth/courses/cs274/readings/optimization/shewchuk.pdf
Связанные формулы
Математика
Метод сопряжённых градиентов для системы Ax=b
Сопряжённые градиенты решают симметричную положительно определённую систему, сохраняя полезную часть прежнего направления. На каждом шаге достаточно умножения матрицы на вектор.
Математика
GMRES(1): шаг с минимальной евклидовой невязкой
GMRES с перезапуском после одного шага выбирает поправку вдоль текущей невязки так, чтобы минимизировать норму нового остатка. Формулу можно применять и к несимметричной матрице.
Математика
Метод Ричардсона: стационарная итерация для Ax=b
Метод Ричардсона прибавляет к текущему приближению невязку, умноженную на параметр τ. Для симметричной положительно определённой матрицы разумный τ превращает эту простую формулу в сходящуюся стационарную итерацию.