Метод бисопряжённых градиентов

Перейти к навигацииПерейти к поиску

Метод бисопряжённых градиентов (англ. Biconjugate gradient method, BiCG) — итерационный численный метод решения СЛАУ крыловского типа. Является обобщением метода сопряжённых градиентов.

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

Пусть дана система линейных алгебраических уравнений вида: . В отличие от МСГ на матрицу не накладывается условие самосопряжённости, то есть возможно, что . Для действительной матрицы это означает, что матрица может быть несимметричной.

Алгоритм для действительных матриц

Подготовка перед итерационным процессом
  1. Выберем начальное приближение
-я итерация метода[1]
Критерий остановки итерационного процесса

Остановка может происходить по числу итераций, по невязке, по отличию приближений и так далее. Поскольку метод является неустойчивым, то при его использовании дополнительно следует ограничивать сверху число итераций.

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

Пусть дана предобусловленная система

Подготовка перед итерационным процессом
  1. Выберем начальное приближение
-я итерация метода
  1. [2]
После итерационного процесса
  1. , где  — приближенное решение системы,  — решение предобусловленной системы на последней итерации.
Критерий остановки итерационного процесса

Остановка может происходить по числу итераций, по невязке, по отличию приближений и так далее. Поскольку метод является неустойчивым, то при его использовании дополнительно следует ограничивать сверху число итераций.

Особенности и модификации метода

BiCG является неустойчивым[1] методом, поэтому для решения реальных задач его используют редко. Чаще используют его модификацию[3] — стабилизированный метод бисопряжённых градиентов.

Примечания

  1. 1 2 Henk A. van der Vorst. Iterative Krylov Methods for Large Linear System. — Cambridge University Press, 2003. — 221 с. — ISBN 9780521818285.
  2. T. Huttunen, M. Malinen, P. Monk. Solving Maxwell’s Equations using Ultra Weak Variational Formulation (англ.). — 2006.