|
数学において、GMRES法（generalized minimal residual method）は、連立一次方程式の数値解を求めるための反復法の一種である。残差をクリロフ部分空間において最小化することにより、近似解を計算する。ベクトルの計算にはアーノルディ法が用いられる。ヨセフ・サードとマルティン・H・シュルツにより、1986年に開発された〔Saad and Schultz〕。 == 解法 == 解くべき方程式を とする。ただし行列''A''は正則な''m''次正方行列、''b''は正規化された（ユークリッドノルム||·||に関して||''b''|| = 1となる）ベクトルとする。 この問題の''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''+1)×''n''次上ヘッセンベルグ行列が生成される。は直交行列なので、 を標準基底R''n''+1の第1ベクトルとして、 が成り立つ。したがって、は残差 のノルムを最小化することにより計算できる。これは''n''次の線形最小二乗問題である。 以上からGMRES法のアルゴリズムが得られる。すなわち、以下の反復を実行する。 # アーノルディ法を1ステップ計算する # ||''r''''n''||を最小化するを見つける # を計算する # 残差が十分小さくなるまでこれを繰り返す 各反復で、行列ベクトル積''Aq''''n''を計算する必要がある。これは''m''次の一般密行列では約2''m''2回の浮動小数点数演算を要するが、疎行列ではO(''m'')とすることができる。行列ベクトル積の他に、第''n''ステップの計算にはO(''n'' ''m'')の浮動小数演算が必要である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「GMRES法」の詳細全文を読む スポンサード リンク
|