Стабилизированный метод бисопряжённых градиентов
Стабилизированный метод бисопряжённых градиентов (англ. Biconjugate gradient stabilized method, BiCGStab) — итерационный метод решения СЛАУ крыловского типа. Разработан Ван дэр Ворстом (англ.) для решения систем с несимметричными матрицами. Сходится быстрее, чем обычный метод бисопряженных градиентов, который является не устойчивыми[1], и поэтому применяется чаще[2].
Содержание
Обозначения
Для комплексных СЛАУ, в методе используются два вида скалярных произведений, в случае действительных матрицы и правой части они совпадают.
- <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][3]:
- Подготовка перед итерационным процессом
- Выберем начальное приближение <math> x^0 </math>
- <math> r^0 = b - Ax^0</math>
- <math> \tilde{r} = r^0 </math>
- <math> \rho^0 = \alpha^0 = \omega^0 = 1 </math>
- <math> v^0 = p^0 = 0 </math>
- <math>k</math>-я итерация метода
- <math>\rho^k = (\tilde{r}, r^{k-1})</math>
- <math> \beta^k = \frac{\rho^{k}}{\rho^{k-1}} \frac{\alpha^{k-1}}{\omega^{k-1}} </math>
- <math> p^k = r^{k-1} + \beta ( p^{k-1} - \omega^{k-1} v^{k-1} ) </math>
- <math> v^k = A p ^k </math>
- <math> \alpha^k = \frac{\rho^k}{(\tilde{r}, v^k)} </math>
- <math> s^k = r^{k-1} - \alpha v^k </math>
- <math> t^k = A s^k </math>
- <math> \omega^k = \frac{[t^k, s^k]} {[t^k, t^k]} </math>
- <math> x^k = x^{k-1} + \omega^k s^k + \alpha^k p^k </math>
- <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>.
См. также
Напишите отзыв о статье "Стабилизированный метод бисопряжённых градиентов"
Примечания
- ↑ 1 2 Henk A. van der Vorst. Iterative Krylov Methods for Large Linear System. — Cambridge University Press, 2003. — 221 с. — ISBN 9780521818285.
- ↑ T. Huttunen, M. Malinen, P. Monk Solving Maxwell’s Equations using Ultra Weak Variational Formulation (англ.). — 2006.
- ↑ A. Formmer, V. Hannemann, B. Nokel, Th. Lippert, K. Schilling Accelerating Wilson Fermion Matrix Invesion by Means of the Stibilized Biconjugate Cgadient Agorithm (англ.). — 1994.
|
||||||||||||||
Отрывок, характеризующий Стабилизированный метод бисопряжённых градиентов
– Настасья Ивановна, что от меня родится? – спросила она шута, который в своей куцавейке шел навстречу ей.– От тебя блохи, стрекозы, кузнецы, – отвечал шут.
– Боже мой, Боже мой, всё одно и то же. Ах, куда бы мне деваться? Что бы мне с собой сделать? – И она быстро, застучав ногами, побежала по лестнице к Фогелю, который с женой жил в верхнем этаже. У Фогеля сидели две гувернантки, на столе стояли тарелки с изюмом, грецкими и миндальными орехами. Гувернантки разговаривали о том, где дешевле жить, в Москве или в Одессе. Наташа присела, послушала их разговор с серьезным задумчивым лицом и встала. – Остров Мадагаскар, – проговорила она. – Ма да гас кар, – повторила она отчетливо каждый слог и не отвечая на вопросы m me Schoss о том, что она говорит, вышла из комнаты. Петя, брат ее, был тоже наверху: он с своим дядькой устраивал фейерверк, который намеревался пустить ночью. – Петя! Петька! – закричала она ему, – вези меня вниз. с – Петя подбежал к ней и подставил спину. Она вскочила на него, обхватив его шею руками и он подпрыгивая побежал с ней. – Нет не надо – остров Мадагаскар, – проговорила она и, соскочив с него, пошла вниз.
Как будто обойдя свое царство, испытав свою власть и убедившись, что все покорны, но что всё таки скучно, Наташа пошла в залу, взяла гитару, села в темный угол за шкапчик и стала в басу перебирать струны, выделывая фразу, которую она запомнила из одной оперы, слышанной в Петербурге вместе с князем Андреем. Для посторонних слушателей у ней на гитаре выходило что то, не имевшее никакого смысла, но в ее воображении из за этих звуков воскресал целый ряд воспоминаний. Она сидела за шкапчиком, устремив глаза на полосу света, падавшую из буфетной двери, слушала себя и вспоминала. Она находилась в состоянии воспоминания.
Соня прошла в буфет с рюмкой через залу. Наташа взглянула на нее, на щель в буфетной двери и ей показалось, что она вспоминает то, что из буфетной двери в щель падал свет и что Соня прошла с рюмкой. «Да и это было точь в точь также», подумала Наташа. – Соня, что это? – крикнула Наташа, перебирая пальцами на толстой струне.
– Ах, ты тут! – вздрогнув, сказала Соня, подошла и прислушалась. – Не знаю. Буря? – сказала она робко, боясь ошибиться.
