前処理行列

線型代数、数値解析 (数値線形代数) において、行列Aの前処理行列Pとは、P−1AがAより小さな条件数を持つ行列を指す。 前処理は、大規模疎行列を係数とする連立一次方程式

A x = b {\displaystyle Ax=b}

を解くために反復法を用いる場合に有効である。これは、ほとんどの反復法で行列の条件数が増大するに従って収束率が低下するためである。具体的には、元の方程式を解く代わりに、左前処理を適用した方程式

P − 1 A x = P − 1 b , {\displaystyle P^{-1}Ax=P^{-1}b,\,}

すなわち

c = P − 1 b , ( P − 1 A ) x = c {\displaystyle c=P^{-1}b,\qquad (P^{-1}A)x=c}

を解くか、もしくは右前処理を適用した方程式

A P − 1 P x = b , {\displaystyle AP^{-1}Px=b,\,}

すなわち

( A P − 1 ) y = b , x = P − 1 y {\displaystyle (AP^{-1})y=b,\qquad x=P^{-1}y}

を解く。これらは、前処理行列Pが正則なら元の方程式と同値である。

これらの前処理の目的は、前処理を施した行列

P − 1 A {\displaystyle P^{-1}A}

もしくは

A P − 1 {\displaystyle AP^{-1}}

の条件数を小さくすることにある。

通常、Pの選択に関してはトレードオフがある。P-1は反復法の各ステップで適用する必要があるため、コストを抑えるためには計算しやすいものでなければならない。最も効率のよい前処理は

P = I {\displaystyle P=I}

もしくは

P − 1 = I {\displaystyle P^{-1}=I}

であるが、これは元の方程式と同じで前処理行列は何もしない。一方、

P = A {\displaystyle P=A}

すなわち

P − 1 A = A P − 1 = I {\displaystyle \quad P^{-1}A=AP^{-1}=I}

とすると条件数は最適な1となり、1回の反復で収束するが、

P − 1 = A − 1 {\displaystyle P^{-1}=A^{-1}}

の計算は元の方程式の求解と同程度に難しい。

そこで行列Pをこれらの中間から選び、P-1ができるだけ簡単に計算でき、かつ最小の反復回数となるように取る。

上の議論で、前処理行列

P − 1 A {\displaystyle P^{-1}A}

もしくは

A P − 1 {\displaystyle AP^{-1}}

は明に計算されないことに注意されたい。すなわち反復法では、与えられたベクトルに対する前処理の適用P-1だけが必要である。

また、Aが対称な場合、前処理の効果は、 P − 1 A {\displaystyle P^{-1}A} の固有値を互いに近づけることに相当する [1]。

例

以下の前処理では、Aを下三角部分L、対角部分D、上三角部分Uに分割する。

ヤコビ前処理

ヤコビ前処理は前処理の最も単純な形態の一つで、前処理行列

P = D {\displaystyle P=D}

は係数行列の対角要素のみからなる。つまり

P i j = A i i δ i j = { A i i i = j 0 otherwise {\displaystyle P_{ij}=A_{ii}\delta _{ij}={\begin{cases}A_{ii}&i=j\\0&{\mbox{otherwise}}\end{cases}}}

である。

SOR

逐次過緩和（SOR）前処理では、Pを

P = ( D ω + L ) ω 2 − ω D − 1 ( D ω + U ) {\displaystyle P=\left({\frac {D}{\omega }}+L\right){\frac {\omega }{2-\omega }}D^{-1}\left({\frac {D}{\omega }}+U\right)}

となるように取る。ωは 0 < ω < 2 {\displaystyle 0<\omega <2} を満たす緩和パラメータである。

Aが対称な場合を対称逐次過緩和前処理もしくはSSOR前処理という。

関連項目

さらなる学習用の参考図書

  • Ke Chen: "Matrix Preconditioning Techniques and Applications", Cambridge University Press, ISBN 978-0521838283 (2005).
  • 藤野清次, 阿部邦美, 杉原正顯, 中嶋徳正:「線形方程式の反復解法」、丸善出版、ISBN 978-4621087411（2013）。


外部リンク

  • Preconditioned Conjugate Gradient – math-linux.com
  • An Introduction to the Conjugate Gradient Method Without the Agonizing Pain by Jonathan Richard Shewchuk.
  • www.preconditioners.com