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

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

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

Образуем квадратичный функционал вида:

Ф(X) = (AX,X)-2(B,X)+C, (18)

где CÎR₁ - const;

(*,*) – скалярное произведение в пространстве R_n.

Задача решения нормальной системы и задача минимизации функционала (18) эквивалентны.

Пусть X^* - точное решение системы , тогда:

Ф(X^*) = Ф(X). (19)

Рассмотрим метод сопряженных градиентов. Введем следующие обозначения:

X⁽⁰⁾, …, X^(k) – приближения к точному решению X^*;

r⁽⁰⁾, …, r^(k) – невязки на каждом шаге, играющие роль антиградиента функции Ф(X);

p^(k) – направление минимизации функционала Ф(X) в точке X^(k);

a_k – коэффициент, обеспечивающий минимум Ф(X) в направлении p^(k);

b_k – коэффициент при p^(k) в формуле для вычисления p^(k+1),

обеспечивающий А – сопряженность векторов p^(k) и p^(k+1) (т. е. p^(k) ортогональны всем предыдущим невязкам r^(k-1));

q^(k) – вспомогательный вектор.

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

Шаг 1.

Задаём X⁽⁰⁾ – начальное приближение;

e>0 – погрешность решения;

r⁽⁰⁾=B-AX⁽⁰⁾ – невязка на начальном приближении;

p⁽⁰⁾= r⁽⁰⁾ – направление минимизации на нулевом шаге.

Шаг 2.

Вычисляем вектор q^(k)=Ap^(k), k – номер итерации;

вычисляем пошаговый множитель ;

вычисляем следующее приближение X^(k+1)=X^(k)+a_kp^(k);

вычисляем невязку на шаге (k+1): r^(k+1)=r^(k)+a_kq^(k).

Шаг 3.

Если || r^(k+1) ||£ e, то итерационный процесс останавливается и выводится решение X^(k+1);

иначе

вычисляем скаляр ;

вычисляем новое направление минимизации вектор

p^(k+1)=r^(k+1)-b_kp^(k);

полагаем k = k + 1, переходим к Шагу 2.