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

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

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

Пусть дана система линейных алгебраических уравнений вида: [math]\displaystyle{ Ax = b }[/math]. В отличие от МСГ на матрицу не накладывается условие самосопряжённости, то есть возможно, что [math]\displaystyle{ A \ne A^* }[/math]. Для действительной матрицы это означает, что матрица может быть несимметричной.

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

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

1. Выберем начальное приближение [math]\displaystyle{ x^0 }[/math]
2. [math]\displaystyle{ r^0 = b - Ax^0 }[/math]
3. [math]\displaystyle{ p^0 = r^0 }[/math]
4. [math]\displaystyle{ z^0 = r^0 }[/math]
5. [math]\displaystyle{ s^0 = r^0 }[/math]

[math]\displaystyle{ k }[/math]-я итерация метода

1. [math]\displaystyle{ \alpha_k = \frac{(p^{k-1}, r^{k-1})}{(s^{k-1}, Az^{k-1})} }[/math]
2. [math]\displaystyle{ x^k = x^{k-1} +\alpha_k z^{k-1} }[/math]
3. [math]\displaystyle{ r^{k} = r^{k-1} - \alpha_k Az^{k-1} }[/math]
4. [math]\displaystyle{ p^k = p^{k-1} - \alpha_k A^T s^{k-1} }[/math]
5. [math]\displaystyle{ \beta_k = \frac{(p^k, r^k)}{(p^{k-1}, r^{k-1})} }[/math]
6. [math]\displaystyle{ z^k = r^k + \beta_k z^{k-1} }[/math]
7. [math]\displaystyle{ s^k = p^k + \beta_k s^{k-1} }[/math]

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

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

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

Пусть дана предобусловленная система [math]\displaystyle{ M^{-1}AP^{-1}x = M^{-1}b }[/math]

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

1. Выберем начальное приближение [math]\displaystyle{ x^0 }[/math]
2. [math]\displaystyle{ \widetilde{x}^0 = P^{-1}x^0 }[/math]
3. [math]\displaystyle{ r^0 = M^{-1}\left( b - A \widetilde{x}^0 \right) }[/math]
4. [math]\displaystyle{ p^0 = r^0 }[/math]
5. [math]\displaystyle{ z^0 = r^0 }[/math]
6. [math]\displaystyle{ s^0 = r^0 }[/math]

[math]\displaystyle{ k }[/math]-я итерация метода

1. [math]\displaystyle{ \alpha_k = \frac{(p^{k-1}, r^{k-1})}{(s^{k-1}, M^{-1}AP^{-1}z^{k-1})} }[/math]
2. [math]\displaystyle{ \widetilde{x}^k = \widetilde{x}^{k-1} +\alpha_k z^{k-1} }[/math]
3. [math]\displaystyle{ r^{k} = r^{k-1} - \alpha_k M^{-1}AP^{-1}z^{k-1} }[/math]
4. [math]\displaystyle{ p^k = p^{k-1} - \alpha_k P^{-T} A^T M^{-T} s^{k-1} }[/math]
5. [math]\displaystyle{ \beta_k = \frac{(p^k, r^k)}{(p^{k-1}, r^{k-1})} }[/math]
6. [math]\displaystyle{ z^k = r^k + \beta_k z^{k-1} }[/math]
7. [math]\displaystyle{ s^k = p^k + \beta_k s^{k-1} }[/math]

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

1. [math]\displaystyle{ x^* = P \widetilde{x}^m }[/math], где [math]\displaystyle{ x^* }[/math] — приближенное решение системы, [math]\displaystyle{ \widetilde{x}^m }[/math] — решение предобусловленной системы на последней итерации.

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

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

Особенности и модификации метода

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