GMRES法

GMRES法：連立一次方程式の数値解法

GMRES法（Generalized Minimal RESidual method）は、連立一次方程式の数値解を求めるための反復解法です。この方法は、残差ベクトルをクリロフ部分空間内で最小化することで近似解を効率的に求める点が特徴です。1986年、ヨセフ・サードとマルティン・H・シュルツによって開発されました。

問題設定

解くべき連立一次方程式を、正則なm次正方行列Aとベクトルbを用いてAx = bと表します。ここで、bはユークリッドノルムが1に正規化されているとします。

クリロフ部分空間とアーノルディ法

GMRES法では、n次クリロフ部分空間Kn = span{b, Ab, ..., A^(n-1)b} を用います。この部分空間の中で、残差ベクトルAx_n - b のノルムを最小化するベクトルx_n を近似解とします。

しかし、b, Ab, ... のベクトルは線形従属になりやすいので、代わりにアーノルディ法を用いてKnの正規直交基底{q_1, ..., q_n}を構成します。これにより、近似解x_n はx_n = Q_n y_n (Q_n はq_i を列ベクトルとする行列、y_n は係数ベクトル) と表せます。

アーノルディ法は、上ヘッセンベルグ行列~H_n を生成します。この行列を用いて、残差ノルムの最小化問題は、最小二乗問題として定式化できます。

アルゴリズム

GMRES法のアルゴリズムは以下の通りです。

1. アーノルディ法を1ステップ実行し、新たな直交ベクトルq_(n+1)と上ヘッセンベルグ行列~H_n を求める。
2. 最小二乗問題を解いて、残差ノルム||r_n|| = ||Ax_n - b|| を最小化する係数ベクトルy_n を求める。これは、QR分解を用いて効率的に解くことができます。
3. 近似解x_n = Q_n y_n を計算する。
4. 残差ノルムが十分小さくなるまで、1～3を繰り返す。

各反復では行列ベクトル積A q_n の計算が必要で、密行列の場合はO(m^2)、疎行列の場合はO(m) の計算量となります。さらに、最小二乗問題の解法にO(n m) の計算量が必要です。

収束特性

GMRES法は、各反復でクリロフ部分空間内で残差を最小化するため、残差ノルムは単調減少します。理論上、m回反復すれば厳密解に到達しますが、実際には少ない反復回数で十分な精度を得られることが期待されます。

しかし、Greenbaum・Pták・Strakošの定理によると、m-1回までは残差が変化せず、最後の1回で0になるような行列が存在します。そのため、GMRES法の収束速度は行列Aの性質に大きく依存します。

Aが正定値行列の場合、収束速度は条件数κ_2(A)に関係し、Aが対称正定値行列の場合は、より良い収束性が保証されます。一般の場合には、固有値の分布や行列の正規性などが収束性に影響を与えます。

解法の拡張

GMRES法は、単独で使用されるだけでなく、様々な拡張が提案されています。

前処理: 他の反復解法と同様に、前処理を用いることで収束速度を向上させることができます。
リスタート(GMRES(k)): 反復回数nが大きくなると計算コストが高くなるため、k回反復後にリスタートを行うGMRES(k)が用いられます。しかし、リスタートを行うと収束が遅くなる可能性があります。
* Flexible GMRES法: 前処理として反復解法を用いることを可能にした手法です。

他の解法との比較

GMRES法は、クリロフ部分空間法の中でも最小残差を達成するアルゴリズムですが、計算コストが高いため、他の解法が用いられることもあります。例えば、MINRES法(対称行列の場合)、双共役勾配法、CGS法、BiCGSTAB法などがあります。これらの解法は計算コストが低い反面、必ずしも最小残差を達成するわけではなく、収束性が保証されない場合もあります。

最小二乗問題の解法

GMRES法では、各反復で最小二乗問題を解く必要があります。この問題は、QR分解を用いて効率的に解くことができます。QR分解はギブンス回転を用いて逐次的に更新することで、計算コストを抑えることができます。

まとめ

GMRES法は、連立一次方程式を解くための強力な反復解法ですが、その収束性は行列Aの性質に大きく依存します。適切な前処理やリスタート、そして問題に合わせて解法を選択することが重要です。様々な拡張手法や他の解法と比較検討することで、最適な解法を選択する必要があります。

もう一度検索