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

Сравнение методов градиентного спуска(зеленый) и метода сопряженных градиентов для [math]\displaystyle{ n=2 }[/math]

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

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

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

[math]\displaystyle{ (Ax,x) - 2(b,x) \rightarrow min }[/math]

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

Алгоритм

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

1. Выберем начальное приближение [math]\displaystyle{ x^0 }[/math]
2. [math]\displaystyle{ r^0 = b - Ax^0 }[/math]
3. [math]\displaystyle{ z^0 = r^0 }[/math]

[math]\displaystyle{ k }[/math]-я итерация метода

1. [math]\displaystyle{ \alpha_k = \frac{(r^{k-1}, r^{k-1})}{(Az^{k-1}, z^{k-1})} }[/math]
2. [math]\displaystyle{ x^k = x^{k-1} + \alpha_k z^{k-1} }[/math]
3. [math]\displaystyle{ r^k = r^{k-1} - \alpha_k A z^{k-1} }[/math]
4. [math]\displaystyle{ \beta_k = \frac{(r^k, r^k)}{(r^{k-1}, r^{k-1})} }[/math]
5. [math]\displaystyle{ z^k = r^k + \beta_k z^{k-1} }[/math]

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

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

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

Пусть предобусловленная система имеет вид: [math]\displaystyle{ SAQx=Sb }[/math], тогда алгоритм метода для такой системы можно записать следующим образом:

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

1. Выберем начальное приближение [math]\displaystyle{ x^0 }[/math]
2. [math]\displaystyle{ r^0 = Q(b - SAx^0) }[/math]
3. [math]\displaystyle{ z^0 = r^0 }[/math]
4. [math]\displaystyle{ \widetilde{x}^0 = Qx^0 }[/math]

[math]\displaystyle{ k }[/math]-я итерация метода

1. [math]\displaystyle{ \alpha_k = \frac{(r^{k-1}, r^{k-1})}{(SAQz^{k-1}, z^{k-1})} }[/math]
2. [math]\displaystyle{ \widetilde{x}^k = \widetilde{x}^{k-1} + \alpha_k z^{k-1} }[/math]
3. [math]\displaystyle{ r^k = r^{k-1} - \alpha_k SAQ z^{k-1} }[/math]
4. [math]\displaystyle{ \beta_k = \frac{(r^k, r^k)}{(r^{k-1}, r^{k-1})} }[/math]
5. [math]\displaystyle{ z^k = r^k + \beta_k z^{k-1} }[/math]

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

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

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

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

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

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