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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Постановка задачи[править | править исходный текст]

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

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

Подготовка перед итерационным процессом
  1. Выберем начальное приближение x^0
  2. r^0 = b - Ax^0
  3. p^0 = r^0
  4. z^0 = r^0
  5. s^0 = r^0
k-я итерация метода[1]
  1. \alpha_k = \frac{(p^{k-1}, r^{k-1})}{(s^{k-1}, Az^{k-1})}
  2. x^k = x^{k-1} +\alpha_k z^{k-1}
  3. r^{k} = r^{k-1} -  \alpha_k Az^{k-1}
  4. p^k = p^{k-1} - \alpha_k A^T s^{k-1}
  5. \beta_k = \frac{(p^k, r^k)}{(p^{k-1}, r^{k-1})}
  6. z^k = r^k +  \beta_k z^{k-1}
  7. s^k = p^k + \beta_k s^{k-1}
Критерий остановки итерационного процесса

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

Алгоритм для преобусловленной системы[править | править исходный текст]

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

Подготовка перед итерационным процессом
  1. Выберем начальное приближение x^0
  2. \widetilde{x}^0 = P^{-1}x^0
  3. r^0 = M^{-1}\left( b - A \widetilde{x}^0 \right)
  4. p^0 = r^0
  5. z^0 = r^0
  6. s^0 = r^0
k-я итерация метода
  1. \alpha_k = \frac{(p^{k-1}, r^{k-1})}{(s^{k-1}, M^{-1}AP^{-1}z^{k-1})}
  2. \widetilde{x}^k = \widetilde{x}^{k-1} +\alpha_k z^{k-1}
  3. r^{k} = r^{k-1} -  \alpha_k M^{-1}AP^{-1}z^{k-1}
  4. p^k = p^{k-1} - \alpha_k P^{-T} A^T M^{-T} s^{k-1} [2]
  5. \beta_k = \frac{(p^k, r^k)}{(p^{k-1}, r^{k-1})}
  6. z^k = r^k +  \beta_k z^{k-1}
  7. s^k = p^k + \beta_k s^{k-1}
После итерационного процесса
  1. x^* = P \widetilde{x}^m , где x^* — приближенное решение системы, \widetilde{x}^m — решение предобусловленной системы на последней итерации.
Критерий остановки итерационного процесса

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

Особенности и модификации метода[править | править исходный текст]

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

Примечания[править | править исходный текст]

  1. 1 2 Henk A. van der Vorst Iterative Krylov Methods for Large Linear System. — Cambridge University Press, 2003. — 221 с. — ISBN 9780521818285
  2. P^{-T} = (P^{-1})^T
  3. T. Huttunen, M. Malinen, P. Monk Solving Maxwell’s Equations using Ultra Weak Variational Formulation (англ.). — 2006.