Метод двусопряженной градиентной стабилизации - Biconjugate gradient stabilized method

В числовая линейная алгебра, то метод двусопряженной градиентной стабилизации, часто сокращенно BiCGSTAB, является итерационный метод разработан Х. А. ван дер Ворст для численного решения несимметричных линейные системы. Это вариант метод двусопряженных градиентов (BiCG) и имеет более быструю и плавную сходимость, чем исходный BiCG, а также другие варианты, такие как метод квадрата сопряженного градиента (CGS). Это Крыловское подпространство метод.

Алгоритмические шаги

Без предварительной подготовки BiCGSTAB

Решить линейную систему Топор = б, BiCGSTAB начинается с первоначального предположения Икс₀ и происходит следующее:

1. р₀ = б − Топор₀
2. Выберите произвольный вектор р₀ такой, что (р₀, р₀) ≠ 0, например, р₀ = р₀ . (Икс,y) обозначает скалярное произведение векторов (Икс,y) = Икс^Т y
3. ρ₀ = α = ω₀ = 1
4. v₀ = п₀ = 0
5. За я = 1, 2, 3, …
   1. ρ_я = (р₀, р_я−1)
   2. β = (ρ_я/ρ_я−1)(α/ω_я−1)
   3. п_я = р_я−1 + β(п_я−1 − ω_я−1v_я−1)
   4. v_я = Ap_я
   5. α = ρ_я/(р₀, v_я)
   6. час = Икс_я−1 + αп_я
   7. Если час достаточно точно, затем установите Икс_я = час и выйти
   8. s = р_я−1 − αv_я
   9. т = В качестве
   10. ω_я = (т, s)/(т, т)
   11. Икс_я = час + ω_яs
   12. Если Икс_я достаточно точный, затем выйти
   13. р_я = s − ω_ят

Предварительно подготовленный BiCGSTAB

Прекондиционеры обычно используются для ускорения сходимости итерационных методов. Решить линейную систему Топор = б с прекондиционером K = K₁K₂ ≈ А, предварительно подготовленный BiCGSTAB начинается с первоначального предположения Икс₀ и происходит следующее:

1. р₀ = б − Топор₀
2. Выберите произвольный вектор р₀ такой, что (р₀, р₀) ≠ 0, например, р₀ = р₀
3. ρ₀ = α = ω₀ = 1
4. v₀ = п₀ = 0
5. За я = 1, 2, 3, …
   1. ρ_я = (р₀, р_я−1)
   2. β = (ρ_я/ρ_я−1)(α/ω_я−1)
   3. п_я = р_я−1 + β(п_я−1 − ω_я−1v_я−1)
   4. y = K −1
      2 п_я
   5. v_я = Ау
   6. α = ρ_я/(р₀, v_я)
   7. час = Икс_я−1 + αy
   8. Если час достаточно точно Икс_я = час и выйти
   9. s = р_я−1 − αv_я
   10. z = K −1
       2 s
   11. т = Аз
   12. ω_я = (K −1
       1 т, K −1
       1 s)/(K −1
       1 т, K −1
       1 т)
   13. Икс_я = час + ω_яz
   14. Если Икс_я достаточно точен, тогда брось
   15. р_я = s − ω_ят

Эта формулировка эквивалентна применению безусловного BiCGSTAB к явно предварительно подготовленной системе.

Ãx̃ = b̃

с Ã = K −1
1 АK −1
2 , Икс = K₂Икс и b̃ = K −1
1 б. Другими словами, с этой формулировкой возможны как левое, так и правое предварительное кондиционирование.

Вывод

BiCG в полиномиальной форме

В BiCG направления поиска п_я и п_я а остатки р_я и р_я обновляются с использованием следующих повторяющиеся отношения:

п_я = р_я−1 + β_яп_я−1,

п_я = р_я−1 + β_яп_я−1,

р_я = р_я−1 − α_яAp_я,

р_я = р_я−1 − α_яА^Тп_я.

Константы α_я и β_я выбраны быть

α_я = ρ_я/(п_я, Ap_я),

β_я = ρ_я/ρ_я−1

куда ρ_я = (р_я−1, р_я−1) так что остатки и направления поиска удовлетворяют биортогональности и двусопряженности соответственно, т. е. для я ≠ j,

(р_я, р_j) = 0,

(п_я, Ap_j) = 0.

Несложно показать, что

р_я = п_я(А)р₀,

р_я = п_я(А^Т)р₀,

п_я+1 = Т_я(А)р₀,

п_я+1 = Т_я(А^Т)р₀

куда п_я(А) и Т_я(А) находятся ямногочлены степени от А. Эти многочлены удовлетворяют следующим рекуррентным соотношениям:

п_я(А) = п_я−1(А) − α_яАТ_я−1(А),

Т_я(А) = п_я(А) + β_я+1Т_я−1(А).

Получение BiCGSTAB из BiCG

Нет необходимости явно отслеживать остатки и направления поиска BiCG. Другими словами, итерации BiCG могут выполняться неявно. В BiCGSTAB желательно иметь рекуррентные соотношения для

р_я = Q_я(А)п_я(А)р₀

куда Q_я(А) = (я − ω₁А)(я − ω₂А)⋯(я − ω_яА) с подходящими константами ω_j вместо р_я = п_я(А) в надежде, что Q_я(А) обеспечит более быструю и плавную сходимость в р_я чем р_я.

Из рекуррентных соотношений для п_я(А) и Т_я(А) и определение Q_я(А) который

Q_я(А)п_я(А)р₀ = (я − ω_яА)(Q_я−1(А)п_я−1(А)р₀ − α_яАQ_я−1(А)Т_я−1(А)р₀),

что влечет за собой необходимость рекуррентного соотношения для Q_я(А)Т_я(А)р₀. Это также можно получить из отношений BiCG:

Q_я(А)Т_я(А)р₀ = Q_я(А)п_я(А)р₀ + β_я+1(я − ω_яА)Q_я−1(А)п_я−1(А)р₀.

Аналогично определению р_я, BiCGSTAB определяет

п_я+1 = Q_я(А)Т_я(А)р₀.

В векторной форме рекуррентные соотношения для п_я и р_я находятся

п_я = р_я−1 + β_я(я − ω_я−1А)п_я−1,

р_я = (я − ω_яА)(р_я−1 − α_яАп_я).

Чтобы вывести рекуррентное соотношение для Икс_я, определять

s_я = р_я−1 − α_яАп_я.

Рекуррентное соотношение для р_я тогда можно записать как

р_я = р_я−1 − α_яАп_я − ω_яВ качестве_я,

что соответствует

Икс_я = Икс_я−1 + α_яп_я + ω_яs_я.

Определение констант BiCGSTAB

Теперь осталось определить константы BiCG. α_я и β_я и выберите подходящий ω_я.

В BiCG, β_я = ρ_я/ρ_я−1 с

ρ_я = (р_я−1, р_я−1) = (п_я−1(А^Т)р₀, п_я−1(А)р₀).

Поскольку BiCGSTAB явно не отслеживает р_я или же р_я, ρ_я не вычисляется сразу по этой формуле. Однако это может быть связано со скалярным

ρ̃_я = (Q_я−1(А^Т)р₀, п_я−1(А)р₀) = (р₀, Q_я−1(А)п_я−1(А)р₀) = (р₀, р_я−1).

Благодаря биортогональности, р_я−1 = п_я−1(А)р₀ ортогонален U_я−2(А^Т)р₀ куда U_я−2(А^Т) - любой многочлен степени я − 2 в А^Т. Следовательно, только члены высшего порядка п_я−1(А^Т) и Q_я−1(А^Т) вопрос в скалярных произведениях (п_я−1(А^Т)р₀, п_я−1(А)р₀) и (Q_я−1(А^Т)р₀, п_я−1(А)р₀). Старшие коэффициенты п_я−1(А^Т) и Q_я−1(А^Т) находятся (−1)^я−1α₁α₂⋯α_я−1 и (−1)^я−1ω₁ω₂⋯ω_я−1, соответственно. Следует, что

ρ_я = (α₁/ω₁)(α₂/ω₂)⋯(α_я−1/ω_я−1)ρ̃_я,

и поэтому

β_я = ρ_я/ρ_я−1 = (ρ̃_я/ρ̃_я−1)(α_я−1/ω_я−1).

Простая формула для α_я можно получить аналогично. В BiCG,

α_я = ρ_я/(п_я, Ap_я) = (п_я−1(А^Т)р₀, п_я−1(А)р₀)/(Т_я−1(А^Т)р₀, АТ_я−1(А)р₀).

Как и в предыдущем случае, только члены высшего порядка п_я−1(А^Т) и Т_я−1(А^Т) имеет значение в скалярных произведениях благодаря биортогональности и двусопряженности. Бывает что п_я−1(А^Т) и Т_я−1(А^Т) имеют одинаковый ведущий коэффициент. Таким образом, их можно заменить одновременно с Q_я−1(А^Т) в формуле, что приводит к

α_я = (Q_я−1(А^Т)р₀, п_я−1(А)р₀)/(Q_я−1(А^Т)р₀, АТ_я−1(А)р₀) = ρ̃_я/(р₀, АQ_я−1(А)Т_я−1(А)р₀) = ρ̃_я/(р₀, Ap̃_я).

Наконец, BiCGSTAB выбирает ω_я минимизировать р_я = (я − ω_яА)s_я в 2-норма как функция ω_я. Это достигается, когда

((я − ω_яА)s_я, В качестве_я) = 0,

давая оптимальное значение

ω_я = (В качестве_я, s_я)/(В качестве_я, В качестве_я).

Обобщение

BiCGSTAB можно рассматривать как комбинацию BiCG и GMRES где за каждым шагом BiCG следует GMRES (1) (т.е. GMRES перезапускается на каждом шаге), чтобы исправить неправильное поведение конвергенции CGS, в качестве улучшения которого был разработан BiCGSTAB. Однако из-за использования полиномов минимальной остаточной степени один такой ремонт может быть неэффективным, если матрица А имеет большие комплексные собственные пары. В таких случаях BiCGSTAB может застаиваться, что подтверждается численными экспериментами.

Можно ожидать, что минимальные остаточные многочлены более высокой степени могут лучше справиться с этой ситуацией. Это дает начало алгоритмам, включая BiCGSTAB2^[1] и более общий BiCGSTAB (л)^[2]. В BiCGSTAB (л), а GMRES (л) шаг следует за каждым л Шаги BiCG. BiCGSTAB2 эквивалентен BiCGSTAB (л) с л = 2.

Смотрите также

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

Рекомендации

• Ван дер Ворст, Х.А. (1992). «Bi-CGSTAB: быстрый и плавно сходящийся вариант Bi-CG для решения несимметричных линейных систем». SIAM J. Sci. Стат. Comput. 13 (2): 631–644. Дои:10.1137/0913035. HDL:10338.dmlcz / 104566.
• Саад, Ю. (2003). "§7.4.2 BICGSTAB". Итерационные методы для разреженных линейных систем. (2-е изд.). СИАМ. стр.231–234. Дои:10.2277/0898715342. ISBN  978-0-89871-534-7.
• ^ Гуткнехт, М. Х. (1993). «Варианты BICGSTAB для матриц с комплексным спектром». SIAM J. Sci. Comput. 14 (5): 1020–1033. Дои:10.1137/0914062.
• ^ Sleijpen, G.L.G .; Фоккема Д. Р. (ноябрь 1993 г.). «BiCGstab (л) для линейных уравнений с несимметричными матрицами комплексного спектра » (PDF). Электронные транзакции по численному анализу. Кент, Огайо: Государственный университет Кента. 1: 11–32. ISSN  1068-9613. Архивировано из оригинал (PDF) на 2011-06-06. Получено 2010-02-07.