|
|
| 1行目: |
1行目: |
| − | [[線型代数]]、[[数値解析]]において、行列''A''の'''前処理行列'''''P''とは、''P''<sup>−1</sup>''A''が''A''より小さな[[条件数]]を持つ行列を指す。
| + | {{テンプレート:20180815sk}} |
| − | 前処理は、大規模[[疎行列]]を係数とする連立一次方程式
| |
| − | | |
| − | {{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>の固有値を互いに近づけることに相当する
| |
| − | [http://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>}}
| |
| − | | |
| − | となるように取る。ωは<math>0 < \omega < 2</math>を満たす緩和パラメータである。
| |
| − | | |
| − | ''A''が対称な場合を'''対称逐次過緩和前処理'''もしくは'''SSOR前処理'''という。
| |
| − | | |
| − | == 関連項目 ==
| |
| − | | |
| − | * 他の前処理:
| |
| − | ** 不完全[[コレスキー分解]]
| |
| − | ** 不完全[[LU分解]]
| |
| − | * [[クリロフ部分空間]]
| |
| − | * [[反復法 (数値計算)|反復法]]
| |
| − | * [[共役勾配法]]
| |
| − | * [[前処理付き共役勾配法]]
| |
| − | | |
| − | ==外部リンク==
| |
| − | * [http://www.math-linux.com/spip.php?article55 Preconditioned Conjugate Gradient] – math-linux.com
| |
| − | * [http://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:行列]]
| |