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

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

Обозначения

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

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

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

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

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

1. Выберем начальное приближение <math> x^0 </math>
2. <math> r^0 = b - Ax^0</math>
3. <math> \tilde{r} = r^0 </math>
4. <math> \rho^0 = \alpha^0 = \omega^0 = 1 </math>
5. <math> v^0 = p^0 = 0 </math>

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

1. <math>\rho^k = (\tilde{r}, r^{k-1})</math>
2. <math> \beta^k = \frac{\rho^{k}}{\rho^{k-1}} \frac{\alpha^{k-1}}{\omega^{k-1}} </math>
3. <math> p^k = r^{k-1} + \beta^k ( p^{k-1} - \omega^{k-1} v^{k-1} ) </math>
4. <math> v^k = A p ^k </math>
5. <math> \alpha^k = \frac{\rho^k}{(\tilde{r}, v^k)} </math>
6. <math> s^k = r^{k-1} - \alpha^k v^k </math>
7. <math> t^k = A s^k </math>
8. <math> \omega^k = \frac{[t^k, s^k]} {[t^k, t^k]} </math>
9. <math> x^k = x^{k-1} + \omega^k s^k + \alpha^k p^k </math>
10. <math> r^k = s^k - \omega^k t^k</math>

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

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

См. также

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