前処理行列のソースを表示

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

{{Indent|<math> Ax = b</math>}}

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

{{Indent|<math> P^{-1}Ax = P^{-1}b,\,</math>}}

すなわち

{{Indent|<math>c=P^{-1}b, \qquad (P^{-1}A)x=c</math>}}

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

{{Indent|<math> AP^{-1}Px = b,\,</math>}}

すなわち

{{Indent|<math>(AP^{-1})y=b, \qquad x=P^{-1}y</math>}}

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

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

{{Indent|<math>P^{-1}A</math>}}

もしくは

{{Indent|<math>AP^{-1}</math>}}

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

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

{{Indent|<math> P=I</math>}}

もしくは

{{Indent|<math> P^{-1}=I</math>}}

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

{{Indent|<math> P=A</math>}}

すなわち

{{Indent|<math> \quad P^{-1}A = AP^{-1} = I</math>}}

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

{{Indent|<math> P^{-1}=A^{-1}</math>}}

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

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

上の議論で、前処理行列

{{Indent|<math> P^{-1}A</math>}}

もしくは

{{Indent|<math> AP^{-1}</math>}}

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

また、''A''が対称な場合、前処理の効果は、<math>P^{-1}A</math>の固有値を互いに近づけることに相当する
[https://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf]。

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

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

{{Indent|<math> P = D</math>}}

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

{{Indent|<math>P_{ij} = A_{ii}\delta_{ij} = \begin{cases}A_{ii} & i=j \\ 0 &\mbox{otherwise}\end{cases}</math>}}

である。

===SOR===
'''逐次過緩和'''（'''[[SOR法|SOR]]'''）前処理では、''P''を

{{Indent|<math>P=\left(\frac{D}{\omega}+L\right)\frac{\omega}{2-\omega}D^{-1}\left(\frac{D}{\omega}+U\right)</math>}}

となるように取る。&omega;は<math>0 < \omega < 2</math>を満たす緩和パラメータである。

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

== 関連項目 ==

* 他の前処理:
** 不完全[[コレスキー分解]]
** 不完全[[LU分解]]
* [[クリロフ部分空間]]
* [[反復法 (数値計算)|反復法]]
* [[共役勾配法]]
* [[前処理付き共役勾配法]]

== さらなる学習用の参考図書 ==
* Ke Chen: "Matrix Preconditioning Techniques and Applications", Cambridge University Press, ISBN 978-0521838283 (2005).

* 藤野清次, 阿部邦美, 杉原正顯, 中嶋徳正:「線形方程式の反復解法」、丸善出版、ISBN 978-4621087411（2013）。


==外部リンク==
* [http://www.math-linux.com/spip.php?article55 Preconditioned Conjugate Gradient] – math-linux.com
* [https://www.cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf An Introduction to the Conjugate Gradient Method Without the Agonizing Pain] by Jonathan Richard Shewchuk.
* [http://www.preconditioners.com www.preconditioners.com]

{{DEFAULTSORT:まえしよりきようれつ}}
[[Category:数値線形代数]]
[[Category:数学に関する記事]]
[[Category:行列]]