前処理行列
線型代数、数値解析 (数値線形代数) において、行列Aの前処理行列Pとは、PAが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}}
の条件数を小さくすることにある。
以下の前処理では、Aを下三角部分L、対角部分D、上三角部分Uに分割する。