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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Сравнение методов градиентного спуска(красный) и метода сопряженных градиентов для n=2

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

Постановка задачи[править | править вики-текст]

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

(Ax,x) + 2(b,x) \rightarrow min

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

Алгоритм[править | править вики-текст]

Подготовка перед итерационным процессом
  1. Выберем начальное приближение x^0
  2. r^0 = b - Ax^0
  3. z^0 = r^0
k-я итерация метода[1]
  1. \alpha_k = \frac{(r^{k-1}, r^{k-1})}{(Az^{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 - SAx^0)
  3. z^0 = r^0
  4. \widetilde{x}^0 = Qx^0
k-я итерация метода
  1. \alpha_k = \frac{(r^{k-1}, r^{k-1})}{(SAQz^{k-1}, z^{k-1})}
  2. \widetilde{x}^k = \widetilde{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} \widetilde{x}^m, где x^* — приближенное решение системы, m — общее число итераций метода.
Критерий останова

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

Особенности и обобщения[править | править вики-текст]

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

Примечания[править | править вики-текст]

  1. Henk A. van der Vorst Iterative Krylov Methods for Large Linear System. — Cambridge University Press, 2003. — 221 с. — ISBN 9780521818285.