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

1

Метод сопряженных градиентов – один из эффективных методов; он позволяет уменьшить число шагов блок-схемы градиентного спуска.

Этот метод связан с понятием

сопряженного направления.

2

Векторы , (k,j = 1, …, n) называются сопряженными

относительно симметричной матрицы

А, если

Причем, если матрица А полностью определена и векторы попарно сопряжены относительно А, то – линейно независимы.

3

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

минимизации квадратичной функции за n

и меньше число шагов (где n – число переменных).

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

4

Алгоритм метода

1.Составляем grad ).

2.Выбираем точку . Находим grad f() при

Составим уравнение:

,

Аналогично методу наискорейшего спуска из уравнения находим и получаем координаты {x11 ; x12} точки

5

3. Координаты всех последующих точек вычисляем по другим формулам:

,

где

6

Здесь – вектор, задающий новые направления поиска.

Величину h1 находим, исследовав

на экстремум функцию Далее процедура повторяется.

7

!!! Основные формулы

Для нахождения min функции f(x1,x2,…,xn):

,	(1)
где

(2)

)

8

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

Чтобы с этим бороться, метод сопряженных градиентов время от времени обновляют, т. е. полагают .

9

Номер k называется моментом обновления.

На практике в качестве момента обновления берут ,

где n – размерность рассматриваемого пространства.

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

10