Стабилизированный метод бисопряжённых градиентов

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

Стабилизированный метод бисопряжённых градиентов (англ. Biconjugate gradient stabilized method, BiCGStab) — итерационный метод решения СЛАУ крыловского типа. Разработан Ван дэр Ворстом (англ.) для решения систем с несимметричными матрицами. Сходится быстрее, чем обычный метод бисопряженных градиентов, который является неустойчивым[1], и поэтому применяется чаще[2].

Обозначения

Для комплексных СЛАУ, в методе используются два вида скалярных произведений, в случае действительных матрицы и правой части они совпадают.

  • [math]\displaystyle{ (u, v) = \sum_{i=1}^n \overline{u}_i v_i }[/math]
  • [math]\displaystyle{ [u, v] = \sum_{i=1}^n u_i v_i }[/math]

Алгоритм метода

Для решения СЛАУ вида [math]\displaystyle{ Ax = b }[/math], где [math]\displaystyle{ A }[/math] — комплексная матрица, стабилизированным методом бисопряжённых градиентов может использоваться следующий алгоритм[1][3]:

Подготовка перед итерационным процессом
  1. Выберем начальное приближение [math]\displaystyle{ x^0 }[/math]
  2. [math]\displaystyle{ r^0 = b - Ax^0 }[/math]
  3. [math]\displaystyle{ \tilde{r} = r^0 }[/math]
  4. [math]\displaystyle{ \rho^0 = \alpha^0 = \omega^0 = 1 }[/math]
  5. [math]\displaystyle{ v^0 = p^0 = 0 }[/math]
[math]\displaystyle{ k }[/math]-я итерация метода
  1. [math]\displaystyle{ \rho^k = (\tilde{r}, r^{k-1}) }[/math]
  2. [math]\displaystyle{ \beta^k = \frac{\rho^{k}}{\rho^{k-1}} \frac{\alpha^{k-1}}{\omega^{k-1}} }[/math]
  3. [math]\displaystyle{ p^k = r^{k-1} + \beta^k ( p^{k-1} - \omega^{k-1} v^{k-1} ) }[/math]
  4. [math]\displaystyle{ v^k = A p ^k }[/math]
  5. [math]\displaystyle{ \alpha^k = \frac{\rho^k}{(\tilde{r}, v^k)} }[/math]
  6. [math]\displaystyle{ s^k = r^{k-1} - \alpha^k v^k }[/math]
  7. [math]\displaystyle{ t^k = A s^k }[/math]
  8. [math]\displaystyle{ \omega^k = \frac{[t^k, s^k]} {[t^k, t^k]} }[/math]
  9. [math]\displaystyle{ x^k = x^{k-1} + \omega^k s^k + \alpha^k p^k }[/math]
  10. [math]\displaystyle{ r^k = s^k - \omega^k t^k }[/math]
Критерий остановки итерационного процесса

Кроме традиционных критериев остановки, как число итераций ([math]\displaystyle{ k \le k_{max} }[/math]) и заданная невязка ([math]\displaystyle{ \||r^k|| / ||b|| \lt \varepsilon }[/math]), так же остановку метода можно производить, когда величина [math]\displaystyle{ |\omega^k| }[/math] стала меньше некоторого заранее заданного числа [math]\displaystyle{ \varepsilon_{\omega} }[/math].

См. также

Примечания

  1. ↑ 1,0 1,1 Henk A. van der Vorst. Iterative Krylov Methods for Large Linear System. — Cambridge University Press, 2003. — 221 с. — ISBN 9780521818285.
  2. ↑ T. Huttunen, M. Malinen, P. Monk. Solving Maxwell’s Equations using Ultra Weak Variational Formulation (англ.). — 2006.
  3. ↑ A. Formmer, V. Hannemann, B. Nokel, Th. Lippert, K. Schilling. Accelerating Wilson Fermion Matrix Invesion by Means of the Stibilized Biconjugate Cgadient Agorithm (англ.). — 1994.
Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Стабилизированный_метод_бисопряжённых_градиентов&oldid=5869166