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

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

Обозначения

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

• $(u,v)=\sum _{i=1}^n{\bar{u}}_i{v}_i$
• $[u,v]=\sum _{i=1}^n{u}_i{v}_i$

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

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

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

1. Выберем начальное приближение $x^0$
2. $r^0=b-A{x}^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=A{p}^k$
5. ${\alpha }^k=\frac{{\rho }^k}{(\tilde{r},v^k)}$
6. $s^k=r^{k-1}-{\alpha }^k{v}^k$
7. $t^k=A{s}^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\le k_{max}$) и заданная невязка ($\Vert |r^k||/||b||<\epsilon$), так же остановку метода можно производить, когда величина $|{\omega }^k|$ стала меньше некоторого заранее заданного числа ${\epsilon }_{\omega }$.

См. также

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