Стабилизированный метод бисопряжённых градиентов

Стабилизированный метод бисопряжённых градиентов (англ. Biconjugate gradient stabilized method, BiCGStab) — итерационный метод решения СЛАУ крыловского типа. Разработан Ван дэр Ворстом (англ.) для решения систем с несимметричными матрицами. Сходится быстрее, чем обычный метод бисопряженных градиентов, который является неустойчивым^[1], и поэтому применяется чаще^[2].

Обозначения

Для комплексных СЛАУ, в методе используются два вида скалярных произведений, в случае действительных матрицы и правой части они совпадают.

• ${\displaystyle (u,v)=\sum _{i=1}^{n}{\overline {u}}_{i}v_{i}}$
• ${\displaystyle [u,v]=\sum _{i=1}^{n}u_{i}v_{i}}$

Алгоритм метода

Для решения СЛАУ вида ${\displaystyle Ax=b}$, где ${\displaystyle A}$ — комплексная матрица, стабилизированным методом бисопряжённых градиентов может использоваться следующий алгоритм^[1][3]:

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

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

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

1. ${\displaystyle \rho ^{k}=({\tilde {r}},r^{k-1})}$
2. ${\displaystyle \beta ^{k}={\frac {\rho ^{k}}{\rho ^{k-1}}}{\frac {\alpha ^{k-1}}{\omega ^{k-1}}}}$
3. ${\displaystyle p^{k}=r^{k-1}+\beta ^{k}(p^{k-1}-\omega ^{k-1}v^{k-1})}$
4. ${\displaystyle v^{k}=Ap^{k}}$
5. ${\displaystyle \alpha ^{k}={\frac {\rho ^{k}}{({\tilde {r}},v^{k})}}}$
6. ${\displaystyle s^{k}=r^{k-1}-\alpha ^{k}v^{k}}$
7. ${\displaystyle t^{k}=As^{k}}$
8. ${\displaystyle \omega ^{k}={\frac {[t^{k},s^{k}]}{[t^{k},t^{k}]}}}$
9. ${\displaystyle x^{k}=x^{k-1}+\omega ^{k}s^{k}+\alpha ^{k}p^{k}}$
10. ${\displaystyle r^{k}=s^{k}-\omega ^{k}t^{k}}$

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

Кроме традиционных критериев остановки, как число итераций (${\displaystyle k\leq k_{max}}$) и заданная невязка (${\displaystyle \||r^{k}||/||b||<\varepsilon }$), так же остановку метода можно производить, когда величина ${\displaystyle |\omega ^{k}|}$ стала меньше некоторого заранее заданного числа ${\displaystyle \varepsilon _{\omega }}$.

См. также

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

Примечания

1. 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.
3. A. Formmer, V. Hannemann, B. Nokel, Th. Lippert, K. Schilling. Accelerating Wilson Fermion Matrix Invesion by Means of the Stibilized Biconjugate Cgadient Agorithm (англ.). — 1994.