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

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

ОбозначенияПравить

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

• $(u,v)=\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{\stackrel{¯<!--\; ¯\; -->}{u}}_i{v}_i$$(u, v) = \sum_{i=1}^n \overline{u}_i v_i$ 
• $[u,v]=\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{u}_i{v}_i$$[u, v] = \sum_{i=1}^n u_i v_i$ 

Алгоритм методаПравить

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

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

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

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

1. ${\mathrm{\rho <!--\; \rho \; -->}}^k=(\stackrel{~<!--\; ~\; -->}{r},r^{k-<!--\; -\; -->1})$$\rho^k = (\tilde{r}, r^{k-1})$ 
2. ${\mathrm{\beta <!--\; \beta \; -->}}^k=\frac{{\mathrm{\rho <!--\; \rho \; -->}}^k}{{\mathrm{\rho <!--\; \rho \; -->}}^{k-<!--\; -\; -->1}}\frac{{\mathrm{\alpha <!--\; \alpha \; -->}}^{k-<!--\; -\; -->1}}{{\mathrm{\omega <!--\; \omega \; -->}}^{k-<!--\; -\; -->1}}$$\beta^k = \frac{\rho^{k}}{\rho^{k-1}} \frac{\alpha^{k-1}}{\omega^{k-1}}$ 
3. $p^k=r^{k-<!--\; -\; -->1}+{\mathrm{\beta <!--\; \beta \; -->}}^k(p^{k-<!--\; -\; -->1}-<!--\; -\; -->{\mathrm{\omega <!--\; \omega \; -->}}^{k-<!--\; -\; -->1}{v}^{k-<!--\; -\; -->1})$$p^{k}=r^{k-1}+\beta ^{k}(p^{k-1}-\omega ^{k-1}v^{k-1})$ 
4. $v^k=A{p}^k$$v^k = A p ^k$ 
5. ${\mathrm{\alpha <!--\; \alpha \; -->}}^k=\frac{{\mathrm{\rho <!--\; \rho \; -->}}^k}{(\stackrel{~<!--\; ~\; -->}{r},v^k)}$$\alpha^k = \frac{\rho^k}{(\tilde{r}, v^k)}$ 
6. $s^k=r^{k-<!--\; -\; -->1}-<!--\; -\; -->{\mathrm{\alpha <!--\; \alpha \; -->}}^k{v}^k$$s^{k}=r^{k-1}-\alpha ^{k}v^{k}$ 
7. $t^k=A{s}^k$$t^k = A s^k$ 
8. ${\mathrm{\omega <!--\; \omega \; -->}}^k=\frac{[t^k,s^k]}{[t^k,t^k]}$$\omega^k = \frac{[t^k, s^k]} {[t^k, t^k]}$ 
9. $x^k=x^{k-<!--\; -\; -->1}+{\mathrm{\omega <!--\; \omega \; -->}}^k{s}^k+{\mathrm{\alpha <!--\; \alpha \; -->}}^k{p}^k$$x^k = x^{k-1} + \omega^k s^k + \alpha^k p^k$ 
10. $r^k=s^k-<!--\; -\; -->{\mathrm{\omega <!--\; \omega \; -->}}^k{t}^k$$r^k = s^k - \omega^k t^k$ 

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

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

См. такжеПравить

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