プレコンディショナー

数学において、前処理とは、与えられた問題を数値解法に適した形式に調整する、前処理子と呼ばれる変換の適用です。前処理は通常、問題の条件数を減らすことに関連しています。前処理された問題は、通常、反復法によって解決されます。

線型代数と数値解析において、行列の前処理子 とは、が よりも小さい条件数を持つような行列のことです。また、ではなく を前処理子と呼ぶこともよくあります。これは、前処理子自体が明示的に利用できることはめったにないからです。現代の前処理では、 の適用 、つまり列ベクトルまたは列ベクトルのブロックに を乗算することは、一般に行列を使用しない形式で実行されます。つまり、 も も (多くの場合 さえも) も、行列形式では明示的に利用できません。 ${\displaystyle P}$${\displaystyle A}$${\displaystyle P^{-1}A}$${\displaystyle A}$${\displaystyle T=P^{-1}}$${\displaystyle P}$${\displaystyle P}$${\displaystyle T=P^{-1}}$${\displaystyle T=P^{-1}}$${\displaystyle P}$${\displaystyle T=P^{-1}}$${\displaystyle A}$

前処理子は、反復法で線形システムを解く際に 役立ちます。これは、前処理の結果として行列の条件数が減少するため、ほとんどの反復線形ソルバーの収束率が上がるためです。前処理付き反復ソルバーは、通常、大規模な行列、特に疎行列に対して、ガウス消去法などの直接ソルバーよりも優れたパフォーマンスを発揮します。反復ソルバーは、行列を使用しない方法として使用することもできます。つまり、係数行列が明示的に格納されていない場合は、これが唯一の選択肢になりますが、行列とベクトルの積を評価することによってアクセスされます。 ${\displaystyle Ax=b}$${\displaystyle x}$${\displaystyle A}$

について元の線形システムを解く代わりに、適切な前処理を施したシステム を検討し 、 について、 について解くことができます。 ${\displaystyle Ax=b}$${\displaystyle x}$$${\displaystyle AP^{-1}(Px)=b}$$$${\displaystyle AP^{-1}y=b}$$${\displaystyle y}$$${\displaystyle Px=y}$$${\displaystyle x}$

あるいは、左前処理系 を解くこともできる。$${\displaystyle P^{-1}(Ax-b)=0.}$$

どちらのシステムも、前処理行列が特異でない限り、元のシステムと同じ解を与えます。左の前処理はより伝統的です。 ${\displaystyle P}$

両側前処理システムは 、 例えば行列の対称性を保つために有益な場合があります。元の行列が実対称で、実前処理子とがを満たす 場合、前処理行列も対称です。両側前処理は、前処理子とが対角で、スケーリングが元の行列の列と行の両方に適用され、例えば行列のエントリの動的範囲を狭める場合に、 対角スケーリングでよく使用されます。$${\displaystyle QAP^{-1}(Px)=Qb}$$${\displaystyle A}$${\displaystyle Q}$${\displaystyle P}$${\displaystyle Q^{T}=P^{-1}}$${\displaystyle QAP^{-1}}$${\displaystyle Q}$${\displaystyle P}$${\displaystyle A}$

前処理の目的は、たとえば、左または右の前処理済みシステム行列またはの条件数 を減らすことです。条件数が小さいと、反復ソルバーの収束が速くなり、システム行列と右側の摂動に対する解の安定性が向上します。たとえば、より低いコンピュータ精度を使用して、行列エントリのより積極的な量子化が可能になります。 ${\displaystyle P^{-1}A}$${\displaystyle AP^{-1}}$

前処理行列またはが明示的に形成されることはほとんどありません。与えられたベクトルに 前処理子の解決操作を適用するアクションのみ を計算する必要がある場合があります。${\displaystyle P^{-1}A}$${\displaystyle AP^{-1}}$${\displaystyle P^{-1}}$

通常、 の選択にはトレードオフがあります。 演算子は反復線形ソルバーの各ステップで適用する必要があるため、 演算を適用するコスト (計算時間) は小さくなければなりません。 したがって、最も安価な前処理は になります。これは、次のとおりです。 明らかに、これにより元の線形システムが得られ、前処理は何も行いません。 もう一方の極端な例では、 を選択すると が 得られ、これは最適な条件数が 1 で、収束には 1 回の反復が必要です。 ただし、この場合、 および 前処理を適用することは、元のシステムを解くのと同じくらい困難です。 したがって、 演算子をできるだけ単純に保ちながら線形反復の回数を最小限に抑えるために、これら 2 つの極端な例の中間を として選択します。 以下に、一般的な前処理アプローチの例を示します。 ${\displaystyle P}$${\displaystyle P^{-1}}$${\displaystyle P^{-1}}$${\displaystyle P=I}$${\displaystyle P^{-1}=I.}$${\displaystyle P=A}$${\displaystyle P^{-1}A=AP^{-1}=I,}$${\displaystyle P^{-1}=A^{-1},}$${\displaystyle P}$${\displaystyle P^{-1}}$

に対する前処理反復法は、ほとんどの場合、前処理系に適用される標準的な反復法と数学的に同等である。 例えば、に対する標準的なリチャードソン反復法は、${\displaystyle Ax-b=0}$${\displaystyle P^{-1}(Ax-b)=0.}$${\displaystyle Ax-b=0}$$${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}(A\mathbf {x} _{n}-\mathbf {b} ),\ n\geq 0.}$$

事前条件付けされたシステムに適用すると、事前条件付けされた方法になる。 ${\displaystyle P^{-1}(Ax-b)=0,}$$${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P^{-1}(A\mathbf {x} _{n}-\mathbf {b} ),\ n\geq 0.}$$

線形システムに対する一般的な前処理付き反復法の例としては、前処理付き共役勾配法、共役勾配法、一般化最小残差法などがある。反復法では、反復パラメータを計算するためにスカラー積を使用するため、スカラー積の対応する変更と、${\displaystyle P^{-1}(Ax-b)=0}$${\displaystyle Ax-b=0.}$

定常反復法は、行列分割と反復行列によって決定される。 ${\displaystyle A=M-N}$${\displaystyle C=I-M^{-1}A}$

• システム行列は対称正定値であり、${\displaystyle A}$
• 分割行列は対称正定値行列であり、${\displaystyle M}$
• 定常反復法は収束することが決定され、${\displaystyle \rho (C)<1}$

条件数 は、 ${\displaystyle \kappa (M^{-1}A)}$$${\displaystyle \kappa (M^{-1}A)\leq {\frac {1+\rho (C)}{1-\rho (C)}}\,.}$$

対称 正定値行列の場合、前処理子も通常対称正定値になるように選択される。前処理された演算子も対称正定値であるが、-ベースのスカラー積に関してである。この場合、前処理子を適用する際に望ましい効果は、-ベースのスカラー積に関して前処理された演算子の2次形式をほぼ球形にすることである。^[1]${\displaystyle A}$${\displaystyle P}$${\displaystyle P^{-1}A}$${\displaystyle P}$${\displaystyle P^{-1}A}$${\displaystyle P}$

と表記すると、前処理は実際には何らかのベクトルにを掛ける、つまり積を計算することで実装されていることが強調されます。多くのアプリケーションでは、は行列としてではなく、ベクトル に作用する演算子として与えられます。ただし、一部の一般的な前処理は とともに変化し、 への依存性は線形ではない場合があります。一般的な例としては、前処理構築の一部として、共役勾配法などの非線形反復法を使用することがあります。このような前処理は実際には非常に効率的ですが、その動作を理論的に予測することは困難です。 ${\displaystyle T=P^{-1}}$${\displaystyle r}$${\displaystyle T}$${\displaystyle Tr.}$${\displaystyle T}$${\displaystyle T(r)}$${\displaystyle r}$${\displaystyle r}$${\displaystyle r}$

変数前処理の興味深い特定のケースの1つは、ランダム前処理、たとえばランダム粗グリッド上のマルチグリッド前処理です。 [ 2 ^]勾配降下法で使用する場合、ランダム前処理は確率的勾配降下法の実装と見なすことができ、勾配降下法の漸近的な「ジグザグ」パターンを破るため、固定前処理と比較して収束が速くなります。

前処理の最も一般的な用途は、偏微分方程式の近似から得られる線形システムの反復解を求めることです。近似品質が優れているほど、行列のサイズは大きくなります。このような場合、最適な前処理の目標は、一方では、 のスペクトル条件数が行列のサイズとは無関係な定数によって上限が定められるようにすることです。これは、 D'yakonovによってスペクトル等価前処理と呼ばれています。他方では、 の適用コストは、 理想的には をベクトルで乗算するコストに比例する (行列のサイズとは無関係) 必要があります。 ${\displaystyle P^{-1}A}$${\displaystyle P^{-1}}$${\displaystyle A}$

ヤコビ前処理は前処理の最も単純な形式の一つで、前処理は行列の対角線になるように選択される。と仮定すると、次式が得られる。 これは対角優勢行列に効率的である。 これは梁問題や1次元問題（例：STAAD.Pro） の解析ソフトウェアで使用される。${\displaystyle P=\mathrm {diag} (A).}$${\displaystyle A_{ii}\neq 0,\forall i}$${\displaystyle P_{ij}^{-1}={\frac {\delta _{ij}}{A_{ij}}}.}$ ${\displaystyle A}$

スパース近似逆行列前処理子は、 を最小化します。ここで、 はフロベニウスノルムであり、は適切に制約されたスパース行列の集合から得られます。フロベニウスノルムの下では、これは多数の独立した最小二乗問題（各列に1つ）を解くことに帰着します。 のエントリは、何らかのスパースパターンに制限される必要があります。そうしないと、問題は の正確な逆行列を求めるのと同じくらい困難で時間がかかります。この方法は、MJ Grote と T. Huckle によって、スパースパターンを選択するアプローチとともに導入されました。^[3]${\displaystyle \|AT-I\|_{F},}$${\displaystyle \|\cdot \|_{F}}$${\displaystyle T=P^{-1}}$${\displaystyle T}$${\displaystyle A}$

• 不完全コレスキー分解
• 不完全なLU分解
• 連続した過度のリラックス
  • 対称的な連続的な過剰緩和
• マルチグリッド前処理

• 前処理付き共役勾配 – math-linux.com
• 線形システムの解法テンプレート: 反復法の構成要素

固有値問題はいくつかの方法で表現することができ、それぞれ独自の前処理が行われます。従来の前処理は、いわゆるスペクトル変換に基づいています。対象となる固有値が（おおよそ）わかれば、関連する同次線形システムを解くことで対応する固有ベクトルを計算でき、線形システムの前処理が可能になります。最後に、固有値問題をレイリー商の最適化として定式化することで、前処理された最適化手法が利用できるようになります。^[4]

線形システムの場合と同様に、固有値問題では、前処理子 を使って行列 を行列 に置き換えたくなるかもしれません。しかし、これは、との 求める固有ベクトルが同じである場合にのみ意味があります。これはスペクトル変換の場合に当てはまります。 ${\displaystyle Ax=\lambda x}$${\displaystyle A}$${\displaystyle P^{-1}A}$${\displaystyle P}$${\displaystyle A}$${\displaystyle P^{-1}A}$

最も一般的なスペクトル変換は、いわゆるシフト・アンド・インバート変換です。これは、シフトと呼ばれる特定のスカラー に対して、元の固有値問題 がシフト・アンド・インバート問題 に置き換えられるものです。固有ベクトルは保存され、シフト・アンド・インバート問題は、たとえば累乗反復などの反復ソルバーによって解くことができます。これにより、逆反復が得られ、これは通常、シフト に最も近い固有値に対応する固有ベクトル に収束します。レイリー商反復 は、可変シフトによるシフト・アンド・インバート法です。 ${\displaystyle \alpha }$${\displaystyle Ax=\lambda x}$${\displaystyle (A-\alpha I)^{-1}x=\mu x}$${\displaystyle \alpha }$

スペクトル変換は固有値問題に特有のものであり、線形システムには類似するものがありません。スペクトル変換には、関係する変換の正確な数値計算が必要であり、これが大規模な問題の主なボトルネックになります。

線形システムとの密接な関係を作るために、目標の固有値が（近似的に）わかっていると仮定しましょう。すると、同次線形システム から対応する固有ベクトルを計算できます。線形システムの左前処理の概念を使用すると、 が得られます。ここで は 前処理子であり、リチャードソン反復法を使用して解くことができます。${\displaystyle \lambda _{\star }}$${\displaystyle (A-\lambda _{\star }I)x=0}$${\displaystyle T(A-\lambda _{\star }I)x=0}$${\displaystyle T}$

$${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}T(A-\lambda _{\star }I)\mathbf {x} _{n},\ n\geq 0.}$$

ムーア・ペンローズ擬似逆行列は、上記の リチャードソン反復法をで 1 ステップで収束させる前処理子です。これは、 で表されるが、固有空間上の直交射影子であり、 に対応するためです。この選択は 、3 つの独立した理由により非現実的です。第 1 に、は実際には不明ですが、その近似値 で置き換えることができます。第 2 に、正確なムーア・ペンローズ擬似逆行列には、探している固有ベクトルの知識が必要です。これは、がを近似するJacobi-Davidson 前処理子 を使用することで、ある程度回避できます。最後に、このアプローチでは、システム行列 を持つ線形システムの正確な数値解が必要であり、これは、大規模な問題では上記のシフトおよび反転法と同じくらいコストがかかります。解の精度が十分でない場合、手順 2 は冗長になる可能性があります。 ${\displaystyle T=(A-\lambda _{\star }I)^{+}}$${\displaystyle \gamma _{n}=1}$${\displaystyle I-(A-\lambda _{\star }I)^{+}(A-\lambda _{\star }I)}$${\displaystyle P_{\star }}$${\displaystyle \lambda _{\star }}$${\displaystyle T=(A-\lambda _{\star }I)^{+}}$${\displaystyle \lambda _{\star }}$${\displaystyle {\tilde {\lambda }}_{\star }}$${\displaystyle T=(I-{\tilde {P}}_{\star })(A-{\tilde {\lambda }}_{\star }I)^{-1}(I-{\tilde {P}}_{\star })}$${\displaystyle {\tilde {P}}_{\star }}$${\displaystyle P_{\star }}$${\displaystyle (A-{\tilde {\lambda }}_{\star }I)}$

まず、上記のリチャードソン反復法の理論値を現在の近似値に置き換えて実用的なアルゴリズムを得ましょう。 ${\displaystyle \lambda _{\star }}$${\displaystyle \lambda _{n}}$$${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}T(A-\lambda _{n}I)\mathbf {x} _{n},\ n\geq 0.}$$

一般的な選択肢は、レイリー商関数を使用することです。実際の前処理は、 またはを使用するだけの簡単なものです。一部のクラスの固有値問題では、 の効率性が数値的にも理論的にも実証されています。この選択により、線形システム用に開発されたさまざまな前処理を固有値問題に簡単に利用できるようになります。 ${\displaystyle \lambda _{n}=\rho (x_{n})}$${\displaystyle \rho (\cdot )}$${\displaystyle T=(\operatorname {diag} (A))^{-1}}$${\displaystyle T=(\operatorname {diag} (A-\lambda _{n}I))^{-1}.}$${\displaystyle T\approx A^{-1}}$${\displaystyle T\approx A^{-1}}$

値が変化するため、リチャードソン反復法などの最も単純な方法であっても、包括的な理論的収束解析は線形システムの場合に比べてはるかに困難です。 ${\displaystyle \lambda _{n}}$

• 代数的固有値問題の解決のためのテンプレート: 実践ガイド

最適化では、前処理は通常、一次 最適化 アルゴリズムを高速化するために使用されます。

たとえば、勾配降下法を使用して実数値関数の局所的最小値を見つけるには、現在の点における関数の勾配 （または近似勾配）の 負の値に比例するステップを実行します。${\displaystyle F(\mathbf {x} )}$ ${\displaystyle -\nabla F(\mathbf {a} )}$$${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}\nabla F(\mathbf {x} _{n}),\ n\geq 0.}$$

前処理は勾配に適用されます。 $${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P^{-1}\nabla F(\mathbf {x} _{n}),\ n\geq 0.}$$

ここでの前処理は、レベルセットが円のように見えるようにすることを目的としてベクトル空間の幾何学を変更することと見ることができます。^[5]この場合、前処理された勾配は図のように極値の点に近づくことを目指しており、収束が速くなります。

およびが実列ベクトル で、が実対称正定値行列である二次関数の最小値は 、まさに線形方程式の解である。 であるため、最小化するための 前処理付き勾配降下法は、 $${\displaystyle F(\mathbf {x} )={\tfrac {1}{2}}\mathbf {x} ^{T}A\mathbf {x} -\mathbf {x} ^{T}\mathbf {b} ,}$$${\displaystyle \mathbf {x} }$${\displaystyle \mathbf {b} }$${\displaystyle A}$ ${\displaystyle A\mathbf {x} =\mathbf {b} }$${\displaystyle \nabla F(\mathbf {x} )=A\mathbf {x} -\mathbf {b} }$${\displaystyle F(\mathbf {x} )}$$${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P^{-1}(A\mathbf {x} _{n}-\mathbf {b} ),\ n\geq 0.}$$

これは、線形方程式系を解くための前提条件付きリチャードソン反復法です。

が実数非ゼロ列ベクトル で、が実数対称正定値行列であるときのレイリー商 の最小値はの最小の固有値であり、最小化関数は対応する固有ベクトルである。は に比例するので、 を最小化する前処理勾配降下法は次 のようになる。 $${\displaystyle \rho (\mathbf {x} )={\frac {\mathbf {x} ^{T}A\mathbf {x} }{\mathbf {x} ^{T}\mathbf {x} }},}$$${\displaystyle \mathbf {x} }$${\displaystyle A}$ ${\displaystyle A}$${\displaystyle \nabla \rho (\mathbf {x} )}$${\displaystyle A\mathbf {x} -\rho (\mathbf {x} )\mathbf {x} }$${\displaystyle \rho (\mathbf {x} )}$$${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P^{-1}(A\mathbf {x} _{n}-\rho (\mathbf {x_{n}} )\mathbf {x_{n}} ),\ n\geq 0.}$$

これは、固有値問題を解くための前処理付きリチャードソン反復法の類似物です。

多くの場合、レベルセットの形状の変化に対応するために、 反復アルゴリズムの一部またはすべてのステップで前処理を変更することが有益な場合があります。$${\displaystyle \mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}P_{n}^{-1}\nabla F(\mathbf {x} _{n}),\ n\geq 0.}$$

ただし、効率的な前処理を構築するには、多くの場合、計算コストがかかるということに留意する必要があります。前処理の更新にかかるコストの増加により、収束が速くなるというプラスの効果は簡単に打ち消されてしまいます。 が逆ヘッセ行列の BFGS 近似である場合、この方法は準ニュートン法と呼ばれます。 ${\displaystyle P_{n}^{-1}=H_{n}}$

• アクセルソン、オーウェ（1996）。反復解法。ケンブリッジ大学出版局。p.6722。ISBN 978-0-521-55569-2。
• D'yakonov, EG (1996)。楕円問題解決における最適化。CRC-Press。p. 592。ISBN 978-0-8493-2872-5。
• Saad, Yousef & van der Vorst, Henk (2001)。「20 世紀における線形システムの反復解法」。Brezinski, C. & Wuytack, L. (編)。数値解析: 20 世紀の歴史的発展。Elsevier Science Publishers。§8プレコンディショニング法、pp 193–8。ISBN 0-444-50617-9。
• van der Vorst, HA (2003).大規模線形システムのための反復クリロフ法ケンブリッジ大学出版局、ケンブリッジ。ISBN 0-521-81828-1。
• チェン・ケ（2005年）。行列前処理技術と応用。ケンブリッジ：ケンブリッジ大学出版局。ISBN 978-0521838283. OCLC  61410324.