前処理行列

線型代数、数値解析 (数値線形代数) において、行列Aの前処理行列Pとは、P−1AがAより小さな条件数を持つ行列を指す。前処理は、大規模疎行列を係数とする連立一次方程式 を解くために反復法を用いる場合に有効である。これは、ほとんどの反復法で行列の条件数が増大するに従ってが低下するためである。具体的には、元の方程式を解く代わりに、左前処理を適用した方程式 すなわち を解くか、もしくは右前処理を適用した方程式 すなわち を解く。これらは、前処理行列Pが正則なら元の方程式と同値である。 これらの前処理の目的は、前処理を施した行列 もしくは の条件数を小さくすることにある。 通常、Pの選択に関してはトレードオフがある。P-1は反復法の各ステップで適用する必要があるため、コストを抑えるためには計算しやすいものでなければならない。最も効率のよい前処理は もしくは であるが、これは元の方程式と同じで前処理行列は何もしない。一方、 すなわち とすると条件数は最適な1となり、1回の反復で収束するが、 の計算は元の方程式の求解と同程度に難しい。 そこで行列Pをこれらの中間から選び、P-1ができるだけ簡単に計算でき、かつ最小の反復回数となるように取る。 上の議論で、前処理行列 もしくは は明に計算されないことに注意されたい。すなわち反復法では、与えられたベクトルに対する前処理の適用P-1だけが必要である。 また、Aが対称な場合、前処理の効果は、の固有値を互いに近づけることに相当する[1]。