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

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

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

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

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

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

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

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

1. ${\mathrm{\alpha <!--\; \alpha \; -->}}_k=\frac{(p^{k-<!--\; -\; -->1},r^{k-<!--\; -\; -->1})}{(s^{k-<!--\; -\; -->1},A{z}^{k-<!--\; -\; -->1})}$$\alpha_k = \frac{(p^{k-1}, r^{k-1})}{(s^{k-1}, Az^{k-1})}$ 
2. $x^k=x^{k-<!--\; -\; -->1}+{\mathrm{\alpha <!--\; \alpha \; -->}}_k{z}^{k-<!--\; -\; -->1}$$x^k = x^{k-1} +\alpha_k z^{k-1}$ 
3. $r^k=r^{k-<!--\; -\; -->1}-<!--\; -\; -->{\mathrm{\alpha <!--\; \alpha \; -->}}_{k}A{z}^{k-<!--\; -\; -->1}$$r^{k} = r^{k-1} - \alpha_k Az^{k-1}$ 
4. $p^k=p^{k-<!--\; -\; -->1}-<!--\; -\; -->{\mathrm{\alpha <!--\; \alpha \; -->}}_k{A}^T{s}^{k-<!--\; -\; -->1}$$p^k = p^{k-1} - \alpha_k A^T s^{k-1}$ 
5. ${\mathrm{\beta <!--\; \beta \; -->}}_k=\frac{(p^k,r^k)}{(p^{k-<!--\; -\; -->1},r^{k-<!--\; -\; -->1})}$$\beta_k = \frac{(p^k, r^k)}{(p^{k-1}, r^{k-1})}$ 
6. $z^k=r^k+{\mathrm{\beta <!--\; \beta \; -->}}_k{z}^{k-<!--\; -\; -->1}$$z^k = r^k + \beta_k z^{k-1}$ 
7. $s^k=p^k+{\mathrm{\beta <!--\; \beta \; -->}}_k{s}^{k-<!--\; -\; -->1}$$s^k = p^k + \beta_k s^{k-1}$ 

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

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

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

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

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

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

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

1. ${\mathrm{\alpha <!--\; \alpha \; -->}}_k=\frac{(p^{k-<!--\; -\; -->1},r^{k-<!--\; -\; -->1})}{(s^{k-<!--\; -\; -->1},M^{-<!--\; -\; -->1}A{P}^{-<!--\; -\; -->1}{z}^{k-<!--\; -\; -->1})}$$\alpha_k = \frac{(p^{k-1}, r^{k-1})}{(s^{k-1}, M^{-1}AP^{-1}z^{k-1})}$ 
2. ${\stackrel{~<!--\; ~\; -->}{x}}^k={\stackrel{~<!--\; ~\; -->}{x}}^{k-<!--\; -\; -->1}+{\mathrm{\alpha <!--\; \alpha \; -->}}_k{z}^{k-<!--\; -\; -->1}$$\widetilde{x}^k = \widetilde{x}^{k-1} +\alpha_k z^{k-1}$ 
3. $r^k=r^{k-<!--\; -\; -->1}-<!--\; -\; -->{\mathrm{\alpha <!--\; \alpha \; -->}}_k{M}^{-<!--\; -\; -->1}A{P}^{-<!--\; -\; -->1}{z}^{k-<!--\; -\; -->1}$$r^{k} = r^{k-1} - \alpha_k M^{-1}AP^{-1}z^{k-1}$ 
4. $p^k=p^{k-<!--\; -\; -->1}-<!--\; -\; -->{\mathrm{\alpha <!--\; \alpha \; -->}}_k{P}^{-<!--\; -\; -->T}{A}^T{M}^{-<!--\; -\; -->T}{s}^{k-<!--\; -\; -->1}$$p^k = p^{k-1} - \alpha_k P^{-T} A^T M^{-T} s^{k-1}$ 
5. ${\mathrm{\beta <!--\; \beta \; -->}}_k=\frac{(p^k,r^k)}{(p^{k-<!--\; -\; -->1},r^{k-<!--\; -\; -->1})}$$\beta_k = \frac{(p^k, r^k)}{(p^{k-1}, r^{k-1})}$ 
6. $z^k=r^k+{\mathrm{\beta <!--\; \beta \; -->}}_k{z}^{k-<!--\; -\; -->1}$$z^k = r^k + \beta_k z^{k-1}$ 
7. $s^k=p^k+{\mathrm{\beta <!--\; \beta \; -->}}_k{s}^{k-<!--\; -\; -->1}$$s^k = p^k + \beta_k s^{k-1}$ 

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

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

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

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

Особенности и модификации методаПравить

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