1 線形方程式の解法の選択
2 参考文献および参考書の記述
線形方程式, >>> 実非対称/複素非エルミート,
>>> その他 >>> マルチグリッド法: >>> 代数的マルチグリッド法
一般の次元線形方程式
に対する代数的マルチグリッド法は, 幾何的マルチグリッド法と同様に, 以下に示す2段グリッド法を再帰適用することで得られる.
以下では, 上記の代数的マルチグリッド法における2段グリッド法で現れる粗い格子の方程式
の係数行列, 制限行列
, 補完行列
の設定法について記す.
幾何的マルチグリッド法は, 定常反復法を適用すると誤差の空間的高周波成分が速く減衰するという平滑化作用に着目し, 空間的低周波成分で構成される粗い格子を用いて近似解を改善する.
一方代数的マルチグリッド法では, この性質を利用し, 定常反復法で減衰する成分を空間的高周波成分, 減衰しない成分を空間的低周波成分(代数的に滑らかな成分) と定義する.
つまり, 定常反復法の反復行列をとすると,
を満たすベクトル
を代数的に滑らかな成分と定義する.
ここで, 定常反復法として(減速)Jacobi 法を用い, また係数行列
の対角要素の値が要素毎に同程度であると仮定すると,
を満たす.
また, 行列の第
行における比較的大きな非対角要素の列番号を, ある閾値
を用い
と定義する.
この時, 行列が対称なM行列である場合, 式(2) より, 各
に対して,
が成り立つ.
(これを「
の方向に滑らか」と表現する.)
変数の番号の集合を, 粗い格子に属する番号の集合を
, 粗い格子に含まれない集合を
と置く.
この時, 代数的に滑らかな成分が
方向に滑らかである点に着目し,
の補完行列
を
のように設定する.
ただし, であり,
は適当な重みである.
[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