Русская Википедия:Метод бисопряжённых градиентов

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

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

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

<math>k</math>-я итерация метода

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

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

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

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

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

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

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

<math>k</math>-я итерация метода

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

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

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

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

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

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

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