前処理行列

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

${\displaystyle Ax=b}$

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

${\displaystyle P^{-1}Ax=P^{-1}b,\,}$

すなわち

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

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

${\displaystyle AP^{-1}Px=b,\,}$

すなわち

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

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

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

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

もしくは

${\displaystyle AP^{-1}}$

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

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

${\displaystyle P=I}$

もしくは

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

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

${\displaystyle P=A}$

すなわち

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

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

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

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

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

上の議論で、前処理行列

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

もしくは

${\displaystyle AP^{-1}}$

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

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

例

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

ヤコビ前処理

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

${\displaystyle P=D}$ 

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

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

である。

SOR

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

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

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

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

関連項目

• 他の前処理:
  • 不完全コレスキー分解
  • 不完全LU分解
• クリロフ部分空間
• 反復法
• 共役勾配法
• 前処理付き共役勾配法

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

• 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