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

В отличие от метода наискорейшего спуска, где спуск часто производится по тем же направлениям, которые использовались ранее, в методе сопряженных градиентов спуск производится по сопряженным направлениям без их повторного использования. Данный метод позволяет минимизировать квадратичную функцию за шагов (если не учитывать ошибки округления) [4].

Множество векторов — направлений спуска называются сопряженными по отношению к матрице (или — ортогональными), если.

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

Каждое направление спуска вычисляется как линейная комбинация направления наискорейшего спуска и направления спуска на предыдущем шаге:

где находится из условия сопряженности :

В итоге получили алгоритм метода сопряженных градиентов:

Аналогично методу наискорейшего спуска, вычислительная сложность определяется умножением вектора на матрицу. Временная сложность метода сопряженных градиентов:. Пространственная сложность:

Максимальное количество итераций необходимое для достижения условия (3.1.1.5)[8]: