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

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

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

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

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

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

1. Выберем начальное приближение $x^{0}$
2. $r^{0}=b-Ax^{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},Az^{k-1})}}$
2. $x^{k}=x^{k-1}+\alpha _{k}z^{k-1}$
3. $r^{k}=r^{k-1}-\alpha _{k}Az^{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}AP^{-1}x=M^{-1}b$

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

1. Выберем начальное приближение $x^{0}$
2. ${\widetilde {x}}^{0}=P^{-1}x^{0}$
3. $r^{0}=M^{-1}\left(b-A{\widetilde {x}}^{0}\right)$
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}AP^{-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}M^{-1}AP^{-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{\widetilde {x}}^{m}$, где $x^{*}$ — приближенное решение системы, ${\widetilde {x}}^{m}$ — решение предобусловленной системы на последней итерации.

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

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

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

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