代数的マルチグリッド法

1 線形方程式の解法の選択
2 参考文献および参考書の記述
線形方程式, >>> 実非対称/複素非エルミート, >>> その他 >>> マルチグリッド法： >>> 代数的マルチグリッド法

概要 †

• 一般の線形方程式に対して幾何的マルチグリッド法と同様の手法を適用する方法.
• 粗い方程式の生成, ベクトルの制限及び補完はそれぞれ代数的に行われる.

代数的マルチグリッド法とその2段グリッド法 †

一般の次元線形方程式

に対する代数的マルチグリッド法は, 幾何的マルチグリッド法と同様に, 以下に示す2段グリッド法を再帰適用することで得られる.

2段グリッド法のアルゴリズム †

1. 方程式に対し定常反復法を数反復適用する.
2. 残差の粗い格子への制限(restriction)を計算する.
3. 粗い格子の方程式を解く.
4. の補完(interpolation)を用い, 細かい格子上の近似解をと修正する.
5. 方程式に対しを初期近似解として, 定常反復法を数反復適用する.

2段グリッド法 †

以下では, 上記の代数的マルチグリッド法における2段グリッド法で現れる粗い格子の方程式

・・・(1)

の係数行列, 制限行列, 補完行列の設定法について記す.

空間的高周波成分と空間的低周波成分 †

幾何的マルチグリッド法は, 定常反復法を適用すると誤差の空間的高周波成分が速く減衰するという平滑化作用に着目し, 空間的低周波成分で構成される粗い格子を用いて近似解を改善する. 一方代数的マルチグリッド法では, この性質を利用し, 定常反復法で減衰する成分を空間的高周波成分, 減衰しない成分を空間的低周波成分(代数的に滑らかな成分) と定義する. つまり, 定常反復法の反復行列をとすると, を満たすベクトルを代数的に滑らかな成分と定義する. ここで, 定常反復法として(減速)Jacobi 法を用い, また係数行列の対角要素の値が要素毎に同程度であると仮定すると,

・・・(2)

を満たす.

また, 行列の第行における比較的大きな非対角要素の列番号を, ある閾値を用い

と定義する. この時, 行列が対称なM行列である場合, 式(2) より, 各に対して, が成り立つ. (これを「 の方向に滑らか」と表現する.)

補完行列の設定 †

変数の番号の集合を, 粗い格子に属する番号の集合を, 粗い格子に含まれない集合をと置く. この時, 代数的に滑らかな成分が方向に滑らかである点に着目し, の補完行列を

・・・(3)

のように設定する. ただし, であり, は適当な重みである.

参考文献および参考書 †

原著論文 †

教科書 †

[14] Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM: Philadelphia, PA, 2003.
P407–449

[23] Masaaki Sugihara and Kazuo Murota, Theoretical Numerical Linear Algebra, Iwanami Press: Tokyo, 2009, (in Japanese).
P106–136