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

Этот метод позволяет получить сопряженные направления для квадратично функции f(x) с использованием ее производных.

В этом методе используется итерационный процесс:

х=х+р, k=0,1,…, хЄЕ, p=-f(х) (1)

в которой величина шага находится из условия исчерпывающего спуска по направлению р. После вычисления очередной точки х, k=0,1,… новое направление поиска рнаходится по формуле:

р=-f(х)+р, k=0,1,… (2)

Где коэффициенты выбираются так, чтобы при min-ии квадратичной функции f(x) с положительно определенной матрицей А получалась последовательность А-ортогональных векторов р, р,…

Из условия <Ар, р>=0 имеет

=- (3)

Напомним, что для квадратичной функции шаг исчерпывающего спуска по направлению рравен:

=- (4)

Можно показать, что процесс (1)-(4) min-ии квадратичной функции с положительно определенной симметричной функцией с положительно определенной симметричной матрицей А дает точки х,-,хи векторы р,-,ртакие, что если f(х)0 при 0i<k<n-1, то векторы р,-,р А-ортогональны, а f(х),…, f(х) взаимно ортогональны.

Опишем алгоритм сопряженных градиентов:

ШАГ 0:

Задать параметр точности >0, выбрать хЄЕ, найти f(х).

ШАГ1:

Положить k=0, р=-f(х).

ШАГ2:

Решить задачу одномерной min-ии -f(х+р)→min, >0, т.е. найти =.

ШАГ3:

Положить х= х+ри вычислить f(х). Проверить условие достижения точности: ||f(х)||<.

Если оно выполняется, то положить х=х, f(х)=f(х) и закончить поиск, иначе – перейти к шагу 4.

ШАГ4:

Проверить условие k+1=n. Если оно выполняется, то положить х=х, f(х)=f(х) и перейти к шагу 1, иначе – перейти к шагу 5.

ШАГ5:

Вычислить коэффициент =||f(х)||/||f(х)||и найти новое направление поиска р=-f(х)+р. Положить k=k+1 и перейти к шагу 2.

Дата добавления: 2014-01-07