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

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

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

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

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

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

1. Выберем начальное приближение $x^0$
2. $r^0=b-A{x}^0$
3. $p^0=r^0$
4. $z^0=r^0$
5. $s^0=r^0$

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

1. ${\alpha }_k=\frac{(p^{k-1},r^{k-1})}{(s^{k-1},A{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. $p^k=p^{k-1}-{\alpha }_k{A}^T{s}^{k-1}$
5. ${\beta }_k=\frac{(p^k,r^k)}{(p^{k-1},r^{k-1})}$
6. $z^k=r^k+{\beta }_k{z}^{k-1}$
7. $s^k=p^k+{\beta }_k{s}^{k-1}$

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

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

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

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

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

1. Выберем начальное приближение $x^0$
2. ${\tilde{x}}^0=P^{-1}{x}^0$
3. $r^0=M^{-1}(b-A{\tilde{x}}^0)$
4. $p^0=r^0$
5. $z^0=r^0$
6. $s^0=r^0$

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

1. ${\alpha }_k=\frac{(p^{k-1},r^{k-1})}{(s^{k-1},M^{-1}A{P}^{-1}{z}^{k-1})}$
2. ${\tilde{x}}^k={\tilde{x}}^{k-1}+{\alpha }_k{z}^{k-1}$
3. $r^k=r^{k-1}-{\alpha }_k{M}^{-1}A{P}^{-1}{z}^{k-1}$
4. $p^k=p^{k-1}-{\alpha }_k{P}^{-T}{A}^T{M}^{-T}{s}^{k-1}$
5. ${\beta }_k=\frac{(p^k,r^k)}{(p^{k-1},r^{k-1})}$
6. $z^k=r^k+{\beta }_k{z}^{k-1}$
7. $s^k=p^k+{\beta }_k{s}^{k-1}$

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

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

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

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

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

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