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

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

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

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

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

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

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

${\displaystyle k}$-я итерация метода^[1]

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

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

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

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

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

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

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

${\displaystyle k}$-я итерация метода

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

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

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

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

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

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

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

Примечания

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