WikiSort.ru - Не сортированное

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

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

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

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

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

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

${\displaystyle k}$ -я итерация метода^[1]

1. ${\displaystyle \alpha _{k}={\frac {(p^{k-1},r^{k-1})}{(s^{k-1},Az^{k-1})}}}$
2. ${\displaystyle x^{k}=x^{k-1}+\alpha _{k}z^{k-1}}$
3. ${\displaystyle r^{k}=r^{k-1}-\alpha _{k}Az^{k-1}}$
4. ${\displaystyle p^{k}=p^{k-1}-\alpha _{k}A^{T}s^{k-1}}$
5. ${\displaystyle \beta _{k}={\frac {(p^{k},r^{k})}{(p^{k-1},r^{k-1})}}}$
6. ${\displaystyle z^{k}=r^{k}+\beta _{k}z^{k-1}}$
7. ${\displaystyle s^{k}=p^{k}+\beta _{k}s^{k-1}}$

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

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

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

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

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

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

${\displaystyle k}$ -я итерация метода

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

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

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

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

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

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

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

Примечания