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

Метод сопряжённых градиентов - итерационный метод для безусловной оптимизации в многомерном пространстве. Основным достоинством метода является то, что он решает квадратичную задачу оптимизации за конечное число шагов.

Определение

. Два - мерных вектора и называют сопряженными по отношению к матрице (или -сопряженными), если скалярное произведение . Здесь - симметрическая положительно определенная матрица размером .

Предполагается, что квадратичная функция имеет вид:

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

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

Итерация метода сопряженных градиентов состоит в вычислении очередного приближения к точному решению

где

- очередное приближение