Метод сопряжённых градиентов (СЛАУ)

Сравнение методов градиентного спуска(зеленый) и метода сопряженных градиентов для $n=2$

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

Постановка задачи

Пусть дана система линейных уравнений: $Ax=b$. Причём матрица системы — это действительная матрица, обладающая следующими свойствами: $A=A^T>0$, то есть это симметричная положительно определённая матрица. Тогда процесс решения СЛАУ можно представить как минимизацию следующего функционала:

$(Ax,x)-2(b,x)\to min$

За $(\cdot ,\cdot )$ обозначено скалярное произведение. Минимизируя данный функционал, используя подпространства Крылова, получаем алгоритм метода сопряженных градиентов.

Алгоритм

Подготовка перед итерационным процессом

1. Выберем начальное приближение $x^0$
2. $r^0=b-A{x}^0$
3. $z^0=r^0$

$k$-я итерация метода

1. ${\alpha }_k=\frac{(r^{k-1},r^{k-1})}{(A{z}^{k-1},z^{k-1})}$
2. $x^k=x^{k-1}+{\alpha }_k{z}^{k-1}$
3. $r^k=r^{k-1}-{\alpha }_{k}A{z}^{k-1}$
4. ${\beta }_k=\frac{(r^k,r^k)}{(r^{k-1},r^{k-1})}$
5. $z^k=r^k+{\beta }_k{z}^{k-1}$

Критерий остановки

Поскольку минимизируемый функционал квадратичный, то процесс должен дать ответ на $n$-й итерации, однако при реализации метода на компьютере существует погрешность представления вещественных чисел, в результате чего может потребоваться и больше итераций. Так же оценивать точность можно по относительной невязке $\frac{||r^k||}{||b||}$, и прекращать итерационный процесс, когда невязка станет меньше заданного числа.

Алгоритм для предобусловленной системы

Пусть предобусловленная система имеет вид: $SAQx=Sb$, тогда алгоритм метода для такой системы можно записать следующим образом:

Подготовка перед итерационным процессом

1. Выберем начальное приближение $x^0$
2. $r^0=Q(b-SA{x}^0)$
3. $z^0=r^0$
4. ${\tilde{x}}^0=Q{x}^0$

$k$-я итерация метода

1. ${\alpha }_k=\frac{(r^{k-1},r^{k-1})}{(SAQ{z}^{k-1},z^{k-1})}$
2. ${\tilde{x}}^k={\tilde{x}}^{k-1}+{\alpha }_k{z}^{k-1}$
3. $r^k=r^{k-1}-{\alpha }_{k}SAQ{z}^{k-1}$
4. ${\beta }_k=\frac{(r^k,r^k)}{(r^{k-1},r^{k-1})}$
5. $z^k=r^k+{\beta }_k{z}^{k-1}$

После итерационного процесса

1. $x^{*}=Q^{-1}{\tilde{x}}^m$, где $x^{*}$ — приближенное решение системы, $m$ — общее число итераций метода.

Критерий остановки

В данном случае можно использовать те же критерии остановки, что и для обычной системы, только с учётом предобуславливания. Например относительная невязка станет вычисляться как: $\frac{||{\tilde{r}}^k||}{||Sb||}$, однако можно пользоваться и невязкой исходной системы, которая вычисляется следующим образом: $\frac{||r^k||}{||b||}=\frac{||Q^{-1}{\tilde{r}}^k||}{||b||}$

Особенности и обобщения

Как и все методы на подпространствах Крылова, метод сопряженных градиентов от матрицы требует только возможность умножать её на вектор, что приводит к возможности использовать специальные форматы хранения матрицы(такие, как разреженный) и сэкономить память на хранении матрицы.
Метод часто используется для решения конечноэлементых СЛАУ.
У метода есть обобщения: метод бисопряженных градиентов, для работы с несимметричными матрицами. И комплексный метод сопряженных градиентов, где матрица $A$ может содержать комплексные числа, но должна удовлетворять условию: $A=A^{*}>0$, то есть быть самосопряженной-положительно определённой матрицей.