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

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

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

Пусть дана система линейных алгебраических уравнений вида: $Ax=b$ . В отличие от МСГ на матрицу не накладывается условие самосопряжённости, то есть возможно, что $A\neq A^{*}$ . Для действительной матрицы это означает, что матрица может быть несимметричной.

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

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

Выберем начальное приближение $x^{0}$
$r^{0}=b-Ax^{0}$
$p^{0}=r^{0}$
$z^{0}=r^{0}$
$s^{0}=r^{0}$

$k$ -я итерация метода[1]

$\alpha _{k}={\frac {(p^{k-1},r^{k-1})}{(s^{k-1},Az^{k-1})}}$
$x^{k}=x^{k-1}+\alpha _{k}z^{k-1}$
$r^{k}=r^{k-1}-\alpha _{k}Az^{k-1}$
$p^{k}=p^{k-1}-\alpha _{k}A^{T}s^{k-1}$
$\beta _{k}={\frac {(p^{k},r^{k})}{(p^{k-1},r^{k-1})}}$
$z^{k}=r^{k}+\beta _{k}z^{k-1}$
$s^{k}=p^{k}+\beta _{k}s^{k-1}$

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

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

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

Пусть дана предобусловленная система $M^{-1}AP^{-1}x=M^{-1}b$

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

Выберем начальное приближение $x^{0}$
${\widetilde {x}}^{0}=P^{-1}x^{0}$
$r^{0}=M^{-1}\left(b-A{\widetilde {x}}^{0}\right)$
$p^{0}=r^{0}$
$z^{0}=r^{0}$
$s^{0}=r^{0}$

$k$ -я итерация метода

$\alpha _{k}={\frac {(p^{k-1},r^{k-1})}{(s^{k-1},M^{-1}AP^{-1}z^{k-1})}}$
${\widetilde {x}}^{k}={\widetilde {x}}^{k-1}+\alpha _{k}z^{k-1}$
$r^{k}=r^{k-1}-\alpha _{k}M^{-1}AP^{-1}z^{k-1}$
$p^{k}=p^{k-1}-\alpha _{k}P^{-T}A^{T}M^{-T}s^{k-1}$ [2]
$\beta _{k}={\frac {(p^{k},r^{k})}{(p^{k-1},r^{k-1})}}$
$z^{k}=r^{k}+\beta _{k}z^{k-1}$
$s^{k}=p^{k}+\beta _{k}s^{k-1}$

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

$x^{*}=P{\widetilde {x}}^{m}$ , где $x^{*}$ — приближенное решение системы, ${\widetilde {x}}^{m}$ — решение предобусловленной системы на последней итерации.

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

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

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

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

Примечания

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

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

[2] $P^{-T}=(P^{-1})^{T}$

[uwvf-3] T. Huttunen, M. Malinen, P. Monk. Solving Maxwell’s Equations using Ultra Weak Variational Formulation (англ.). — 2006.

Методы решения СЛАУ
Прямые методы	Матричный метод Метод Гаусса Метод Гаусса — Жордана Метод Крамера LU-разложение Разложение Холецкого Метод прогонки
Итерационные методы	Метод Якоби Метод Гаусса — Зейделя Метод итерации Метод релаксации Метод сопряженных градиентов Метод бисопряжённых градиентов Стабилизированный метод бисопряжённых градиентов
Общее	Обратная матрица Проекционные методы решения СЛАУ Предобуславливание