Русская Википедия:Метод сопряжённых градиентов (для решения СЛАУ)
Метод сопряженных градиентов — численный метод решения систем линейных алгебраических уравнений, является итерационным методом Крыловского типа.
Постановка задачи
Пусть дана система линейных уравнений: <math>Ax = b</math>. Причём матрица системы — это действительная матрица, обладающая следующими свойствами: <math>A = A^T > 0</math>, то есть это симметричная положительно определённая матрица. Тогда процесс решения СЛАУ можно представить как минимизацию следующего функционала:
<math>(Ax,x) - 2(b,x) \rightarrow min</math>
За <math>(\cdot, \cdot)</math> обозначено скалярное произведение. Минимизируя данный функционал, используя подпространства Крылова, получаем алгоритм метода сопряженных градиентов.
Алгоритм
- Подготовка перед итерационным процессом
- Выберем начальное приближение <math>x^0</math>
- <math>r^0 = b - Ax^0</math>
- <math>z^0 = r^0</math>
- <math>k</math>-я итерация метода[1]
- <math>\alpha_k = \frac{(r^{k-1}, r^{k-1})}{(Az^{k-1}, z^{k-1})}</math>
- <math>x^k = x^{k-1} + \alpha_k z^{k-1}</math>
- <math>r^k = r^{k-1} - \alpha_k A z^{k-1}</math>
- <math>\beta_k = \frac{(r^k, r^k)}{(r^{k-1}, r^{k-1})}</math>
- <math>z^k = r^k + \beta_k z^{k-1}</math>
- Критерий остановки
Поскольку минимизируемый функционал квадратичный, то процесс должен дать ответ на <math>n</math>-й итерации, однако при реализации метода на компьютере существует погрешность представления вещественных чисел, в результате чего может потребоваться и больше итераций. Так же оценивать точность можно по относительной невязке <math>\frac{||r^k||}{||b||}</math>, и прекращать итерационный процесс, когда невязка станет меньше заданного числа.
Алгоритм для предобусловленной системы
Пусть предобусловленная система имеет вид: <math> SAQx=Sb </math>, тогда алгоритм метода для такой системы можно записать следующим образом:
- Подготовка перед итерационным процессом
- Выберем начальное приближение <math>x^0</math>
- <math>r^0 = Q(b - SAx^0)</math>
- <math>z^0 = r^0</math>
- <math>\widetilde{x}^0 = Qx^0</math>
- <math>k</math>-я итерация метода
- <math>\alpha_k = \frac{(r^{k-1}, r^{k-1})}{(SAQz^{k-1}, z^{k-1})}</math>
- <math>\widetilde{x}^k = \widetilde{x}^{k-1} + \alpha_k z^{k-1}</math>
- <math>r^k = r^{k-1} - \alpha_k SAQ z^{k-1}</math>
- <math>\beta_k = \frac{(r^k, r^k)}{(r^{k-1}, r^{k-1})}</math>
- <math>z^k = r^k + \beta_k z^{k-1}</math>
- После итерационного процесса
- <math>x^* = Q^{-1} \widetilde{x}^m</math>, где <math>x^*</math> — приближенное решение системы, <math>m</math> — общее число итераций метода.
- Критерий остановки
В данном случае можно использовать те же критерии остановки, что и для обычной системы, только с учётом предобуславливания. Например относительная невязка станет вычисляться как: <math>\frac{||\widetilde{r}^k||}{||Sb||}</math>, однако можно пользоваться и невязкой исходной системы, которая вычисляется следующим образом: <math>\frac{||r^k||}{||b||} = \frac{||Q^{-1}\widetilde{r}^k||}{||b||}</math>
Особенности и обобщения
Как и все методы на подпространствах Крылова, метод сопряженных градиентов от матрицы требует только возможность умножать её на вектор, что приводит к возможности использовать специальные форматы хранения матрицы(такие, как разреженный) и сэкономить память на хранении матрицы.
Метод часто используется для решения конечноэлементых СЛАУ.
У метода есть обобщения: метод бисопряженных градиентов, для работы с несимметричными матрицами. И комплексный метод сопряженных градиентов, где матрица <math>A</math> может содержать комплексные числа, но должна удовлетворять условию: <math>A = A^* > 0</math>, то есть быть самосопряженной-положительно определённой матрицей.
Примечания
