GMRES法

数学において、GMRES法は、連立一次方程式の数値解を求めるための反復法の一種である。残差をクリロフ部分空間において最小化することにより、近似解を計算する。ベクトルの計算にはアーノルディ法が用いられる。ヨセフ・サードとマルティン・H・シュルツにより、1986年に開発された。

1. 解法
-----

解くべき方程式を

とする。ただし行列//A//は正則な//m//次正方行列、//b//は正規化されたベクトルとする。

この問題の//n//次クリロフ部分空間は

である。GMRES法では、残差//Ax////n// − //b//を最小化するベクトル//x////n// ∈ //K////n//によって、//Ax// = //b//の厳密解を近似する。

//b//, //Ab//, …, //A////n//−1//b//は線形従属に近いため、これを用いる代わりに、アーノルディ法を用いて//K////n//の基底を構成する正規直交化ベクトル列

を計算する。すなわち、//x////n// ∈ //K////n//は//y////n// ∈ R//n//を用いて//x////n// = //Q////n////y////n//と書くことができる。ただし//Q////n//は//q//1, …, //q//nにより構成される//m//×//n//行列とする。

アーノルディ過程では、

を満たす×//n//次上ヘッセンベルグ行列が生成される。は直交行列なので、

を標準基底R//n//+1の第1ベクトルとして、

が成り立つ。したがって、は残差

のノルムを最小化することにより計算できる。これは//n//次の線形最小二乗問題である。

以上からGMRES法のアルゴリズムが得られる。すなわち、以下の反復を実行する。

アーノルディ法を1ステップ計算する
||//r////n//||を最小化するを見つける
を計算する
残差が十分小さくなるまでこれを繰り返す各反復で、行列ベクトル積//Aq////n//を計算する必要がある。これは//m//次の一般密行列では約2//m//2回の浮動小数点数演算を要するが、疎行列ではOとすることができる。行列ベクトル積の他に、第//n//ステップの計算にはOの浮動小数演算が必要である。

2. 収束特性
-------

第//n//ステップでは、クリロフ部分空間//K////n//内での残差が最小化される。部分空間は常に次の部分空間に含まれるので、残差は単調に減少する。//A//の次数を//m//とすると、//m//回目の反復の後ではクリロフ部分空間//K////m//はR//m//と等しいので、GMRES法は厳密解に到達する。しかし、アイデアの骨子は、少ない回数の反復でベクトル//x////n//が十分な解の近似になる点にある。

一般にはこれは成り立たない。実際、Greenbaum・Pták・Strakošの定理によれば、任意の単調減少列//a//1, …, //a////m//−1、//a////m// = 0について、上で定義された//r////n//に関して、すべての//n//で||//r////n//|| = //a////n//となるような行列//A//を見つけることができる。特に、//m//   −   1回の反復で一定の値を保ちながら、最後の1反復で残差が0になるような行列を見つけることができる。

ただ、実際にはGMRES法は良い性能を示すことも多い。これは特定の場合に証明できる。//A//が正定値なら、、をそれぞれ最小、最大固有値として、 が成り立つ。

//A//が対称正定値なら、を//A//のユークリッドノルムでの条件数として、 が成り立つ。

//A//が正定値でない場合には、//P////n//を//p// = 1を満たす高々//n//次の多項式集合、//V//を//A//のスペクトル分解に現れる行列、σを//A//のスペクトルとして、 を得る。おおざっぱに言えば、これは//A//の固有値が0から遠くかつ密集しており、//A//が正規行列からそれほど離れていない場合に、速く収束することを意味している。

これらの不等式は誤差、つまり現在の反復ベクトル//x////n//と真の解との距離ではなく、残差に関するものである。

3. 解法の拡張
--------

3.1. 前処理
--------

他の反復法と同様に、GMRES法も通常は収束を速める目的で前処理と組み合わせて使用される。

3.2. リスタート
----------

//n//を反復回数として、反復のコストはOである。すなわち、//n//として、連立方程式の本数//N//を用いると、直接解法と同程度の求解コストがかかることになる。したがって、GMRES法では//k//回の反復の後に、//x////k//を初期ベクトルとして、リスタートを行うことがある。これをGMRESと呼ぶ。しかしながら、リスタートを行うと、収束は非常に遅くなることが知られている。

3.3. Flexible GMRES法
--------------------

前処理をより効率的に行えるよう、アルゴリズムに変更を加えた手法である。前処理に反復解法を用いることができる。

4. 他の解法との比較
-----------

アーノルディ法は対称行列の場合にはランチョス法に帰着する。対応するクリロフ部分空間法はPaige・SaundersによるMINRES法である。非対称な場合と異なり、MINRES法は3項漸化式で与えられる。一般行列の場合には、GMRES法のように短い漸化式で残差ノルムを最小化するようなクリロフ部分空間法は存在しないことが知られている。

別な系統として、非対称ランチョス法、特に双共役勾配法に基づく解法がある。これらは3項漸化式を用いるが、最小残差は計算しない。したがって残差は単調には減少せず、収束も保証されない。

さらに、CGS法やBiCGSTAB法などによる解法がある。これらも3項漸化式に基づいているため、最適性は保証されず、解に収束する前に終了することがある。これらの解法のアイデアは、反復毎の生成多項式を適切に選択する点にある。

これらのいずれも、すべての行列に対して万能というわけではない。したがって、実際には与えられた問題に対して複数の解法を試みる必要がある。

5. 最小二乗問題の求解
------------

GMRES法では、 を最小化するベクトルを見つける必要がある。 これはQR分解を計算することで実現できる。すなわち、 を満たす//n//+1次正方直交行列Ω//n//と//n//+1×//n//次上三角行列を計算する。三角行列の行数は列数より1多いので、最下行はすべて零である。したがって、を//n//×//n//次三角行列として、これを と分解することができる。

QR分解は、零の行と1列分の値が異なるだけなので、簡単に更新することができる。つまり//h////n// = Tとして が成り立つので、 は三角行列に近く、σが0であれば三角行列である。これを更新するためには、: としてギブンス回転 を行えばよい。これにより、 を得る。 は三角行列である。

QR分解が与えられると、最小化問題は から容易に解くことができる。実際、//g////n// ∈ R//n//、γ//n// ∈ Rとして、ベクトルを と表すと、これは と書ける。これを最小化するベクトル//y//は で与えられる。の更新も容易に行うことができる。

6. 補足
-----

7. 参考文献
-------

A. Meister, //Numerik linearer Gleichungssysteme//, 2nd edition, Vieweg 2005, ISBN 978-3-528-13135-7.
Y. Saad, //Iterative Methods for Sparse Linear Systems//, 2nd edition, :en:Society for Industrial and Applied Mathematics, 2003. ISBN 978-0-89871-534-7.
Y. Saad and M.H. Schultz, "GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems", //SIAM J. Sci. Stat. Comput.//, 7:856-869, 1986. 10.1137/0907058}}.
J. Stoer and R. Bulirsch, //Introduction to numerical analysis//, 3rd edition, Springer, New York, 2002. ISBN 978-0-387-95452-3.
Lloyd N. Trefethen and David Bau, III, //Numerical Linear Algebra//, Society for Industrial and Applied Mathematics, 1997. ISBN 978-0-89871-361-9.
[1], 2nd Edition, SIAM, Philadelphia, 1994.