Metoda stabilizovaná pomocí dvojitého konjugátu - Biconjugate gradient stabilized method

tento článek může být pro většinu čtenářů příliš technická na to, aby je pochopili. Prosím pomozte to vylepšit na aby to bylo srozumitelné pro neodborníky, aniž by byly odstraněny technické podrobnosti. (Květen 2015) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v numerická lineární algebra, metoda stabilizovaná bikonjugovaným gradientem, často zkráceně jako BiCGSTAB, je iterační metoda vyvinutý uživatelem H. A. van der Vorst pro numerické řešení nesymetrických lineární systémy. Jedná se o variantu biconjugate gradientní metoda (BiCG) a má rychlejší a plynulejší konvergenci než původní BiCG a další varianty, jako je metoda sdruženého přechodu na druhou (CGS). Je to Krylovský podprostor metoda.

Algoritmické kroky

Bezpodmínečný BiCGSTAB

Řešit lineární systém Sekera = b, BiCGSTAB začíná počátečním odhadem X₀ a postupuje následovně:

1. r₀ = b − Sekera₀
2. Vyberte libovolný vektor r̂₀ takhle (r̂₀, r₀) ≠ 0, např. r̂₀ = r₀ . (X,y) označuje tečkový produkt vektorů (X,y) = X^T y
3. ρ₀ = α = ω₀ = 1
4. proti₀ = str₀ = 0
5. Pro i = 1, 2, 3, …
   1. ρ_i = (r̂₀, r_i−1)
   2. β = (ρ_i/ρ_i−1)(α/ω_i−1)
   3. str_i = r_i−1 + β(str_i−1 − ω_i−1proti_i−1)
   4. proti_i = Ap_i
   5. α = ρ_i/(r̂₀, proti_i)
   6. h = X_i−1 + αstr_i
   7. Li h je dostatečně přesný, pak je nastaven X_i = h a skončit
   8. s = r_i−1 − αproti_i
   9. t = Tak jako
   10. ω_i = (t, s)/(t, t)
   11. X_i = h + ω_is
   12. Li X_i je dostatečně přesný, pak ukončete
   13. r_i = s − ω_it

Předpřipravený BiCGSTAB

Předpoklady se obvykle používají k urychlení konvergence iteračních metod. Řešit lineární systém Sekera = b s kondicionérem K. = K.₁K.₂ ≈ A, předem připravený BiCGSTAB začíná počátečním odhadem X₀ a postupuje následovně:

1. r₀ = b − Sekera₀
2. Vyberte libovolný vektor r̂₀ takhle (r̂₀, r₀) ≠ 0, např. r̂₀ = r₀
3. ρ₀ = α = ω₀ = 1
4. proti₀ = str₀ = 0
5. Pro i = 1, 2, 3, …
   1. ρ_i = (r̂₀, r_i−1)
   2. β = (ρ_i/ρ_i−1)(α/ω_i−1)
   3. str_i = r_i−1 + β(str_i−1 − ω_i−1proti_i−1)
   4. y = K. −1
      2 str_i
   5. proti_i = Ay
   6. α = ρ_i/(r̂₀, proti_i)
   7. h = X_i−1 + αy
   8. Li h je tedy dostatečně přesný X_i = h a skončit
   9. s = r_i−1 − αproti_i
   10. z = K. −1
       2 s
   11. t = Az
   12. ω_i = (K. −1
       1 t, K. −1
       1 s)/(K. −1
       1 t, K. −1
       1 t)
   13. X_i = h + ω_iz
   14. Li X_i je dostatečně přesný, než přestat
   15. r_i = s − ω_it

Tato formulace je ekvivalentní použití bezprecedentního BiCGSTABu na explicitně předpřipravený systém

Sekera = b̃

s A = K. −1
1 AK. −1
2 , X = K.₂X a b̃ = K. −1
1 b. Jinými slovy, u této formulace je možná jak pravá, tak pravá stabilizace.

Derivace

BiCG v polynomické formě

V BiCG směry hledání str_i a p̂_i a zbytky r_i a r̂_i jsou aktualizovány pomocí následujících relace opakování:

str_i = r_i−1 + β_istr_i−1,

p̂_i = r̂_i−1 + β_ip̂_i−1,

r_i = r_i−1 − α_iAp_i,

r̂_i = r̂_i−1 − α_iA^Tp̂_i.

Konstanty α_i a β_i jsou vybráni

α_i = ρ_i/(p̂_i, Ap_i),

β_i = ρ_i/ρ_i−1

kde ρ_i = (r̂_i−1, r_i−1) tak, aby zbytky a směry hledání splňovaly biortogonalitu a bikonjugaci, tj. pro i ≠ j,

(r̂_i, r_j) = 0,

(p̂_i, Ap_j) = 0.

Je jednoduché to ukázat

r_i = P_i(A)r₀,

r̂_i = P_i(A^T)r̂₀,

str_i+1 = T_i(A)r₀,

p̂_i+1 = T_i(A^T)r̂₀

kde P_i(A) a T_i(A) jsou ipolynomy th-stupně v A. Tyto polynomy splňují následující relace opakování:

P_i(A) = P_i−1(A) − α_iAT_i−1(A),

T_i(A) = P_i(A) + β_i+1T_i−1(A).

Odvození BiCGSTAB od BiCG

Není nutné výslovně sledovat zbytky a směry hledání BiCG. Jinými slovy lze iterace BiCG provádět implicitně. V BiCGSTABu si někdo přeje mít relace opakování pro

r̃_i = Q_i(A)P_i(A)r₀

kde Q_i(A) = (Já − ω₁A)(Já − ω₂A)⋯(Já − ω_iA) s vhodnými konstantami ω_j namísto r_i = P_i(A) v naději, že Q_i(A) umožní rychlejší a plynulejší konvergenci v systému Windows r̃_i než r_i.

Vyplývá to z relací opakování pro P_i(A) a T_i(A) a definice Q_i(A) že

Q_i(A)P_i(A)r₀ = (Já − ω_iA)(Q_i−1(A)P_i−1(A)r₀ − α_iAQ_i−1(A)T_i−1(A)r₀),

což s sebou nese nutnost relace opakování pro Q_i(A)T_i(A)r₀. To lze také odvodit ze vztahů BiCG:

Q_i(A)T_i(A)r₀ = Q_i(A)P_i(A)r₀ + β_i+1(Já − ω_iA)Q_i−1(A)P_i−1(A)r₀.

Podobně jako definování r̃_i, Definuje BiCGSTAB

p̃_i+1 = Q_i(A)T_i(A)r₀.

Napsáno ve vektorové formě, relace opakování pro p̃_i a r̃_i jsou

p̃_i = r̃_i−1 + β_i(Já − ω_i−1A)p̃_i−1,

r̃_i = (Já − ω_iA)(r̃_i−1 − α_iAp̃_i).

Odvodit relaci opakování pro X_i, definovat

s_i = r̃_i−1 − α_iAp̃_i.

Vztah opakování pro r̃_i pak lze zapsat jako

r̃_i = r̃_i−1 − α_iAp̃_i − ω_iTak jako_i,

což odpovídá

X_i = X_i−1 + α_ip̃_i + ω_is_i.

Stanovení BiCGSTAB konstant

Nyní zbývá určit konstanty BiCG α_i a β_i a vybrat vhodný ω_i.

V BiCG, β_i = ρ_i/ρ_i−1 s

ρ_i = (r̂_i−1, r_i−1) = (P_i−1(A^T)r̂₀, P_i−1(A)r₀).

Protože BiCGSTAB výslovně nesleduje r̂_i nebo r_i, ρ_i není z tohoto vzorce okamžitě vypočítatelný. Může to však souviset se skalárem

ρ̃_i = (Q_i−1(A^T)r̂₀, P_i−1(A)r₀) = (r̂₀, Q_i−1(A)P_i−1(A)r₀) = (r̂₀, r_i−1).

Kvůli biortogonálnosti r_i−1 = P_i−1(A)r₀ je kolmý na U_i−2(A^T)r̂₀ kde U_i−2(A^T) je libovolný polynom stupně i − 2 v A^T. Proto pouze podmínky nejvyššího řádu P_i−1(A^T) a Q_i−1(A^T) záleží na bodových produktech (P_i−1(A^T)r̂₀, P_i−1(A)r₀) a (Q_i−1(A^T)r̂₀, P_i−1(A)r₀). Hlavní koeficienty P_i−1(A^T) a Q_i−1(A^T) jsou (−1)ⁱ⁻¹α₁α₂⋯α_i−1 a (−1)ⁱ⁻¹ω₁ω₂⋯ω_i−1, resp. Z toho vyplývá, že

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

a tudíž

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

Jednoduchý vzorec pro α_i lze odvodit podobně. V BiCG,

α_i = ρ_i/(p̂_i, Ap_i) = (P_i−1(A^T)r̂₀, P_i−1(A)r₀)/(T_i−1(A^T)r̂₀, AT_i−1(A)r₀).

Podobně jako v předchozím případě platí pouze podmínky nejvyššího řádu P_i−1(A^T) a T_i−1(A^T) hmota v bodových produktech díky biortogonalitě a biconjugacy. Stává se to P_i−1(A^T) a T_i−1(A^T) mají stejný počáteční koeficient. Lze je tedy nahradit současně Q_i−1(A^T) ve vzorci, který vede k

α_i = (Q_i−1(A^T)r̂₀, P_i−1(A)r₀)/(Q_i−1(A^T)r̂₀, AT_i−1(A)r₀) = ρ̃_i/(r̂₀, AQ_i−1(A)T_i−1(A)r₀) = ρ̃_i/(r̂₀, Ap̃_i).

Nakonec vybere BiCGSTAB ω_i minimalizovat r̃_i = (Já − ω_iA)s_i v 2-norm jako funkce ω_i. Toho je dosaženo, když

((Já − ω_iA)s_i, Tak jako_i) = 0,

dávat optimální hodnotu

ω_i = (Tak jako_i, s_i)/(Tak jako_i, Tak jako_i).

Zobecnění

Na BiCGSTAB lze pohlížet jako na kombinaci BiCG a GMRES kde po každém kroku BiCG následuje GMRES (1) (tj. GMRES restartován v každém kroku) krok k nápravě chování nepravidelné konvergence CGS, jehož zdokonalením byl vyvinut BiCGSTAB. Avšak vzhledem k použití minimálních zbytkových polynomů stupně jedna nemusí být taková oprava v případě matice účinná A má velké složité vlastní páry. V takových případech je pravděpodobné, že BiCGSTAB stagnuje, což potvrzují numerické experimenty.

Lze očekávat, že minimální zbytkové polynomy vyššího stupně mohou tuto situaci lépe zvládnout. Tak vznikají algoritmy včetně BiCGSTAB2^[1] a obecnější BiCGSTAB (l)^[2]. V BiCGSTAB (l), GMRES (l) krok následuje po každém l Kroky BiCG. BiCGSTAB2 je ekvivalentní s BiCGSTAB (l) s l = 2.

Viz také

• Biconjugate gradientní metoda
• Konjugovaná metoda přechodu na druhou
• Konjugovaná metoda přechodu

Reference

• Van der Vorst, H. A. (1992). „Bi-CGSTAB: Rychlá a plynulá konvergující varianta Bi-CG pro řešení nesymetrických lineárních systémů“. SIAM J. Sci. Stat. Comput. 13 (2): 631–644. doi:10.1137/0913035. hdl:10338.dmlcz / 104566.
• Saad, Y. (2003). „§7.4.2 BICGSTAB“. Iterační metody pro řídké lineární systémy (2. vyd.). SIAM. str.231–234. doi:10.2277/0898715342. ISBN  978-0-89871-534-7.
• ^ Gutknecht, M. H. (1993). "Varianty BICGSTAB pro matice s komplexním spektrem". SIAM J. Sci. Comput. 14 (5): 1020–1033. doi:10.1137/0914062.
• ^ Sleijpen, G. L. G .; Fokkema, D. R. (listopad 1993). „BiCGstab (l) pro lineární rovnice zahrnující nesymetrické matice se složitým spektrem " (PDF). Elektronické transakce na numerické analýze. Kent, OH: Kent State University. 1: 11–32. ISSN  1068-9613. Archivovány od originál (PDF) dne 06.06.2011. Citováno 2010-02-07.