Метод сопряжённых градиентов (СЛАУ) (Bymk; vkhjx'~uud] ijg;nyumkf (VLGR))
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/bf/Conjugate_gradient_illustration.svg/220px-Conjugate_gradient_illustration.svg.png)
Метод сопряженных градиентов — численный метод решения систем линейных алгебраических уравнений, является итерационным методом Крыловского типа.
Постановка задачи
[править | править код]Пусть дана система линейных уравнений: . Причём матрица системы — это действительная матрица, обладающая следующими свойствами: , то есть это симметричная положительно определённая матрица. Тогда процесс решения СЛАУ можно представить как минимизацию следующего функционала:
За обозначено скалярное произведение. Минимизируя данный функционал, используя подпространства Крылова, получаем алгоритм метода сопряженных градиентов.
Алгоритм
[править | править код]- Подготовка перед итерационным процессом
- Выберем начальное приближение
- -я итерация метода[1]
- Критерий остановки
Поскольку минимизируемый функционал квадратичный, то процесс должен дать ответ на -й итерации, однако при реализации метода на компьютере существует погрешность представления вещественных чисел, в результате чего может потребоваться и больше итераций. Так же оценивать точность можно по относительной невязке , и прекращать итерационный процесс, когда невязка станет меньше заданного числа.
Алгоритм для предобусловленной системы
[править | править код]Пусть предобусловленная система имеет вид: , тогда алгоритм метода для такой системы можно записать следующим образом:
- Подготовка перед итерационным процессом
- Выберем начальное приближение
- -я итерация метода
- После итерационного процесса
- , где — приближенное решение системы, — общее число итераций метода.
- Критерий остановки
В данном случае можно использовать те же критерии остановки, что и для обычной системы, только с учётом предобуславливания. Например относительная невязка станет вычисляться как: , однако можно пользоваться и невязкой исходной системы, которая вычисляется следующим образом:
Особенности и обобщения
[править | править код]Как и все методы на подпространствах Крылова, метод сопряженных градиентов от матрицы требует только возможность умножать её на вектор, что приводит к возможности использовать специальные форматы хранения матрицы(такие, как разреженный) и сэкономить память на хранении матрицы.
Метод часто используется для решения конечноэлементых СЛАУ.
У метода есть обобщения: метод бисопряженных градиентов, для работы с несимметричными матрицами. И комплексный метод сопряженных градиентов, где матрица может содержать комплексные числа, но должна удовлетворять условию: , то есть быть самосопряженной-положительно определённой матрицей.
Примечания
[править | править код]- ↑ Henk A. van der Vorst. Iterative Krylov Methods for Large Linear System. — Cambridge University Press, 2003. — 221 с. — ISBN 9780521818285.