二共役勾配安定化法

数値線形代数において、共役勾配安定化法（ BiCGSTABと略されることが多い）は、非対称線形システムの数値解法としてHA van der Vorstが開発した反復法です。これは共役勾配法(BiCG)の派生であり、元の BiCG や共役勾配二乗法(CGS) などの派生法よりも収束が速く、スムーズです。これはクリロフ部分空間法です。元の BiCG 法とは​​異なり、システム行列の転置による乗算は必要ありません。

以下のセクションでは、( x , y ) = x ^T y はベクトルのドット積を表します。線形システムAx = bを解くために、BiCGSTAB は初期推定値x ₀から開始し、次のように進行します。

1. r ₀ = b − Ax ₀
2. _任意のベクトルr̂0_を( r̂0 , r0 )≠0と_なるように選ぶ。例えば、r̂0 _{= r0}
3. ρ ₀ = ( r̂ ₀ , r ₀ )
4. r ₀ = 0_である。
5. i = 1, 2, 3, …の場合
   1. v = Ap _{i −1}
   2. α = ρ _{i −1} /( r̂ ₀ , v )
   3. h = x _{i −1} + α p _{i −1}
   4. s = r _{i −1} − α v
   5. hが十分に正確であれば、つまりsが十分に小さければ、x _i = hに設定して終了する。
   6. t =として
   7. ω = ( t , s )/( t , t )
   8. x _i = h + ω s
   9. r _i = s − ω t
   10. x _{i が}十分に正確であれば、つまりr _iが十分に小さければ終了する
   11. ρ _i = ( r̂ ₀ , r _i )
   12. β = ( ρ _i / ρ _{i −1} )( α / ω )
   13. p _i = r _i + β ( p _{i −1} − ω v )

場合によっては、ベクトルr̂0_をランダムに選択すると数値安定性が向上する。^[1]

前処理は通常、反復法の収束を加速するために使用されます。前処理K = K ₁ K ₂ ≈ Aを使用して線形システムAx = b を解くには、前処理された BiCGSTAB は初期推定値x ₀から開始し、次のように進行します。

1. r ₀ = b − Ax ₀
2. _任意のベクトルr̂0_を( r̂0 , r0 )≠0と_なるように選ぶ。例えば、r̂0 _{= r0}
3. ρ ₀ = ( r̂ ₀ , r ₀ )
4. r ₀ = 0_である。
5. i = 1, 2, 3, …の場合
   1. y = K −1
      2 け −1
      1 π _{i −1 ...}
   2. v =ああ
   3. α = ρ _{i −1} /( r̂ ₀ , v )
   4. h = x _{i −1} + α y
   5. s = r _{i −1} − α v
   6. hが十分に正確であれば、x i ₌ hとなり終了する。
   7. Θ = K −1
      2 け −1
      1 s
   8. t =アズ
   9. ω = ( K −1
      1 t、 K −1
      1 s )/( K −1
      1 t、 K −1
      1 t )
   10. x _i = h + ω z
   11. r _i = s − ω t
   12. x _{i が}十分に正確であれば終了する
   13. ρ _i = ( r̂ ₀ , r _i )
   14. β = ( ρ _i / ρ _{i −1} )( α / ω )
   15. p _i = r _i + β ( p _{i −1} − ω v )

この定式化は、明示的に前処理されたシステムに前処理なしのBiCGSTABを適用することと同等である。

x̃ = b̃

ここでÃ = K −1
1 A K −1
2 , x̃ = K ₂ xかつb̃ = K −1
1 b . 言い換えれば、この定式化では左前処理と右前処理の両方が可能です。

BiCGでは、探索方向p _iとp̂ _iおよび残差r _iとr̂ _{i は}次の再帰関係を使用して更新されます。

p _i = r _{i −1} + β _i p _{i −1}、

p̂ _i = r̂ _{i −1} + β _i p̂ _{i −1}、

r _i = r _{i −1} − α _i Ap _i、

r̂ _i = r̂ _{i −1} − α _i A ^T p̂ _{i です}。

定数α _iとβ _{i は}次のように選ばれる。

α _i = ρ _i / ( p̂ _i , Api ₎、

β _i = ρ _i / ρ _{i −1}

ここでρ _i = ( r̂ _{i −1} , r _{i −1} )であり、残差と探索方向はそれぞれ双直交性と双共役性を満たす。すなわち、i ≠ jに対して、

( r̂ _i , r _j ) = 0、

( p̂ _i , Ap _j ) = 0 です。

それは簡単に証明できる。

r _i = P _i ( A ) r ₀、

r̂ _i = P _i ( A ^T ) r̂ ₀、

p _{i +1} = T _i ( A ) r ₀、

p̂ _{i +1} = T _i ( A ^T ) r̂ ₀

ここで、P _i ( A )とT _i ( A )はAのi次多項式です。これらの多項式は次の再帰関係を満たします。

P _i ( A ) = P _{i −1} ( A ) − α _i A T _{i −1} ( A )、

T _i ( A ) = P _i ( A ) + β _{i +1} T _{i −1} ( A )です。

BiCGの残差と探索方向を明示的に追跡する必要はありません。言い換えれば、BiCGの反復は暗黙的に実行できます。BiCGSTABでは、

r̃ _i = Q _i ( A ) P _i ( A ) r ₀

ここで、Q _i ( A ) = ( I − ω ₁ A )( I − ω ₂ A )⋯( I − ω _i A )であり、適切な定数ω _jをr _i = P _i ( A ) r ₀の代わりに使用することで、Q _i ( A )によりr̃ _{iでの収束が}r _iよりも速く滑らかになることを期待しています。

P _i ( A )とT _i ( A )の再帰関係とQ _i ( A )の定義から次のことが分かります。

Q _i ( A ) P _i ( A ) r ₀ = ( I − ω _i A )( Q _{i −1} ( A ) P _{i −1} ( A ) r ₀ − α _i A Q _{i −1} ( A ) T _{i −1} ( A ) r ₀ )、

これはQ _i ( A ) T _i ( A ) r ₀の再帰関係の必要性を伴います。これはBiCG関係からも導くことができます。

Q _i ( A ) T _i ( A ) r ₀ = Q _i ( A ) P _i ( A ) r ₀ + β _{i +1} ( I − ω _i A ) Q _{i −1} ( A ) P _{i −1} ( A ) r ₀。

r̃ _{i の}定義と同様に、BiCGSTABは次のように定義します。

p̃ _{i +1} = Q _i ( A ) T _i ( A ) r _{0 です}。

ベクトル形式で書くと、 p̃ _iとr̃ _iの再帰関係は

p̃ _i = r̃ _{i −1} + β _i ( I − ω _{i −1} A ) p̃ _{i −1}、

r̃ _i = ( I − ω _i A )( r̃ _{i −1} − α _i A p̃ _i )です。

x _iの再帰関係を導くには、次のように定義する。

s _i = r̃ _{i −1} − α _i A p̃ _{i です}。

r̃ _iの再帰関係は次のように表される。

r̃ _i = r̃ _{i −1} − α _i A p̃ _i − ω _iとして_、​

これは

x _i = x _{i −1} + α _i p̃ _i + ω _i s _{i です}。

_ここで、 BiCG定数αiとβiを決定し、 適切な_ωiを選択し_ます。

BiCGでは、β _i = ρ _i / ρ _{i −1}であり、

ρ _i = ( r̂ _{i −1} , r _{i −1} ) = ( P _{i −1} ( A ^T ) r̂ ₀ , P _{i −1} ( A ) r ₀ )です。

BiCGSTABはr̂ _iやr _iを明示的に記録しないので、ρ _iはこの式からすぐには計算できない。しかし、スカラーと関連づけることができる。

ρ̃ _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} )です。

双直交性により、r _{i −1} = P _{i −1} ( A ) r _0はU _{i −2} ( A ^T ) r̂ ₀に直交します。ここで、 U _{i −2} ( A ^T )はA ^Tのi − 2次多項式の任意のものです。したがって、ドット積( P _{i −1} ( A ^T ) r̂ 0 , P _{i −1 (} A ) r 0 )と( Q _{i −1} ( A ^T ) r̂ ₀ , P _{i −1} ( A ) r ₀ )では、 P i −1 ( A ^T )とQ _{i −1} ( A ^T )の_最高次の項のみ_が重要に_なります。P _{i −1} ( A ^T )とQ _{i −1} ( A ^T )の主係数はそれぞれ(−1) ^{i −1} α ₁ α ₂ ⋯ α _{i −1}と(−1) ^{i −1} ω ₁ ω ₂ ⋯ ω _{i −1}である。したがって、

ρ _i = ( α ₁ / ω ₁ )( α ₂ / ω ₂ )⋯( α _{i −1} / ω _{i −1} ) ρ̃ _i、

そしてこうして

β _i = ρ _i / ρ _{i −1} = ( ρ̃ _i / ρ̃ _{i −1} )( α _{i −1} / ω _{i −1} )。

α _iの簡単な式も同様に導出できる。BiCGでは、

α _i = ρ _i /( p̂ _i , Ap _i ) = ( P _{i −1} ( A ^T ) r̂ ₀ , P _{i −1} ( A ) r ₀ )/( T _{i −1} ( A ^T ) r̂ ₀ , A T _{i −1} ( A ) r ₀ )です。

上の場合と同様に、双直交性と双共役性により、ドット積ではP _{i −1} ( A ^T )とT _{i −1} ( A ^T )の最高次の項のみが重要になります。 P _{i −1} ( A ^T )とT _{i −1} ( A T ) は同じ先頭係数を持ちます。したがって、式ではそれらを同時に Q i −1 ( A ^T )に置き換えることができ、 次_の式が得^られます。

α _i = ( Q _{i −1} ( A ^T ) r̂ ₀ , P _{i −1} ( A ) r ₀ )/( Q _{i −1} ( A ^T ) r̂ ₀ , A T _{i −1} ( A ) r ₀ ) = ρ̃ _i /( r̂ ₀ , A Q _{i −1} ( A ) T _{i −1} ( A ) r ₀ ) = ρ̃ _i /( r̂ ₀ , Ap̃ _i ) .

最後に、BiCGSTABはω _iの関数として2ノルムでr̃ _i = ( I − ω _i A ) s _{i を}最小化するω _{i を}選択します。これは次の場合に達成されます。

(( I − ω _i A ) s _i , As _i ) = 0 ,

最適な値を与える

ω _i = ( As _i、s _i )/( As _i、As _i )。

BiCGSTAB は BiCG とGMRESの組み合わせと見なすことができます。各 BiCG ステップの後に GMRES( 1 ) (つまり、各ステップで GMRES が再開される) ステップが続き、CGS の不規則な収束動作を修復します。BiCGSTAB は、CGS の改良として開発されました。ただし、次数 1 の最小残差多項式を使用しているため、行列Aに大きな複素固有値がある場合、このような修復は効果的でない可能性があります。このような場合、数値実験で確認されているように、BiCGSTAB は停滞する可能性があります。

高次の最小残差多項式の方がこの状況にうまく対処できると期待できます。これにより、BiCGSTAB2 ^[1]やより一般的なBiCGSTAB( l ) ^{[2]などのアルゴリズムが生まれました。BiCGSTAB(} l )では、 l回のBiCGステップごとにGMRES( l ) ステップが続きます。BiCGSTAB2 は、 l = 2の場合のBiCGSTAB( l )と同等です。

• 共役勾配法
• 共役勾配二乗法
• 共役勾配法

• Van der Vorst, HA (1992). 「Bi-CGSTAB: 非対称線形システムの解法のための Bi-CG の高速かつスムーズに収束する変形」SIAM J. Sci. Stat. Comput. 13 (2): 631–644. doi :10.1137/0913035. hdl : 10338.dmlcz/104566 .
• Saad, Y. (2003). 「§7.4.2 BICGSTAB」 .スパース線形システムの反復法(第 2 版). SIAM. pp. 231–234. ISBN 978-0-89871-534-7。
• ^ Gutknecht, MH (1993). 「複素スペクトルを持つ行列に対する BICGSTAB のバリアント」SIAM J. Sci. Comput. 14 (5): 1020–1033. doi :10.1137/0914062.
• ^ Sleijpen, GLG; Fokkema, DR (1993 年 11 月). 「複素スペクトルを持つ非対称行列を含む線形方程式の BiCGstab(l)」(PDF) .数値解析に関する電子取引. 1.ケント、オハイオ州: ケント州立大学: 11–32. ISSN  1068-9613.