отрицательно определенная квадратичная форма может иметь вид

Рис. 3. Траектория движения в точку минимума при использовании метода сопряженных градиентов

В данном случае каждое новое направление движения ортогонально предыдущему. Не существует ли более разумного способа выбора нового направления движения? Существует, и он называется метод сопряженных направлений. А метод сопряженных градиентов как раз относится к группе методов сопряженных направлений. На рисунке 3 изображена траектория движения в точку минимума при использовании метода сопряженных градиентов.

Рис. 2. Траектория движения в точку минимума методом наискорейшего спуска.

процесс повторяется до достижения точки минимума.

в точке, где функция перестает уменьшаться, опять вычисляется градиент, и спуск продолжается в новом направлении;

в начальной точке x(0) вычисляется градиент, и движение осуществляется в направлении антиградиента до тех пор, пока уменьшается целевая функция;

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

То есть, если матрица А положительно-определенная, то вместо того, чтобы решать систему уравнений 1, можно найти минимум ее квадратичной функции. Причем, метод сопряженных градиентов сделает это за n или менее шагов, где n размерность неизвестного вектора x. Так как любая гладкая функция в окрестностях точки своего минимума хорошо аппроксимируется квадратичной, этот же метод можно применить для минимизации и неквадратичных функций. При этом метод перестает быть конечным, а становится итеративным.

Рис. 1. Квадратичные формы для положительно-определенной матрицы, отрицательно-определенной матрицы, положительно-неопределенной матрицы, неопределенной матрицы.

На рисунке 1 изображено как выглядят квадратичные формы соответственно для положительно-определенной матрицы (а), отрицательно-определенной матрицы (b), положительно-неопределенной матрицы (с), неопределенной матрицы (d).

Наличие такой связи между матрицей линейного преобразования A и скалярной функцией f(x) дает возможность проиллюстрировать некоторые формулы линейной алгебры интуитивно понятными рисунками. Например, матрица А называется положительно-определенной, если для любого ненулевого вектора x справедливо следующее:

Квадратичная форма это просто скаляр, квадратичная функция некого вектора x следующего вида:

где x неизвестный вектор, b известный вектор, а A известная, квадратная, симметричная, положительно определенная матрица. Решение этой системы эквивалентно нахождению минимума соответствующей квадратичной формы.

Первоначально метод сопряженных градиентов был разработан для решения систем линейных алгебраических уравнений вида:

Скалярное произведение двух векторов записывается xTy и представляет сумму скаляров: . Заметим, что xTy = yTx. Если x и y ортогональны, то xTy = 0. В общем, выражения, которые преобразуются к матрице 1х1, такие как xTy и xTAx, рассматриваются как скалярные величины.

Несколько слов об обозначениях, используемых далее.

Термин "метод сопряженных градиентов" один из примеров того, как бессмысленные словосочетания, став привычными, воспринимаются сами собой разумеющимися и не вызывают никакого недоумения. Дело в том, что, за исключением частного и не представляющего практического интереса случая, градиенты не являются сопряженными, а сопряженные направления не имеют ничего общего с градиентами. Название метода отражает тот факт, что данный метод отыскания безусловного экстремума сочетает в себе понятия градиента целевой функции и сопряженных направлений.

Автор: Николай Некипелов

Метод сопряженных градиентов математический аппарат

Николай Некипелов Метод сопряженных градиентов математический аппарат