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

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

Обозначения

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

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

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

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

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

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

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

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

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

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

См. также

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