代数的マルチグリッド法の変更点

追加された行はこの色です。
削除された行はこの色です。
代数的マルチグリッド法へ行く。
代数的マルチグリッド法の差分を削除
[[1 線形方程式の解法の選択]]&br;
[[2 参考文献および参考書の記述]]&br;
線形方程式, &math(Ax=b); &#x3e;&#x3e;&#x3e; 実非対称/複素非エルミート, &math(A\not=A^H); &#x3e;&#x3e;&#x3e; その他 &#x3e;&#x3e;&#x3e; マルチグリッド法： &#x3e;&#x3e;&#x3e; 代数的マルチグリッド法
#contents

---------------------------------------------

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

*代数的マルチグリッド法とその2段グリッド法 [#t323b7f1]
一般の&math(n);次元線形方程式
#br
CENTER:&math(A{\vec u}={\vec b});
#br
に対する代数的マルチグリッド法は, [[幾何的マルチグリッド法]]と同様に, 以下に示す2段グリッド法を再帰適用することで得られる.

**2段グリッド法のアルゴリズム [#d94c29b1]
+ 方程式&math(A{\vec u}={\vec b});に対し定常反復法を数反復適用する.
+ 残差&math({\vec r}:={\vec b}-A^h{\vec u}^h);の粗い格子への制限(restriction)&math({\vec r}'=R{\vec r});を計算する.
+ 粗い格子の方程式&math(A' {\vec v}'={\vec r}');を解く.
+ &math({\vec v}');の補完(interpolation)&math(P{\vec v}');を用い, 細かい格子上の近似解を&math({\vec u}={\vec u}+P{\vec v}');と修正する.
+ 方程式&math(A{\vec u}={\vec b});に対し&math({\vec u});を初期近似解として, 定常反復法を数反復適用する.

*2段グリッド法 [#p8d56bf5]
以下では, 上記の代数的マルチグリッド法における2段グリッド法で現れる粗い格子の方程式
#br
#math(A' {\vec u}' = {\vec b}');
#br
の係数行列&math(A');, 制限行列&math(R);, 補完行列&math(P);の設定法について記す.

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

また, 行列&math(A);の第&math(i);行における比較的大きな非対角要素の列番号を, ある閾値&math(0 < \theta \leq 1);を用い
#br
CENTER:&math(S_i := \{j|j \neq i; |a_{ij} | \geq \theta \max_{k \neq i} |a_{ik}| \} );
#br
と定義する.
この時, 行列&math(A);が対称なM行列である場合, 式(2) より, 各&math(j \in S_i);に対して, &math(e_i \approx e_j);が成り立つ.
(これを「&math(S_i); の方向に滑らか」と表現する.)

** 補完行列&math(P);の設定 [#i6513e4f]
変数の番号の集合を&math(V:=\{1, 2, \ldots, n\});, 粗い格子に属する番号の集合を&math(C \in V);, 粗い格子に含まれない集合を&math(F := V \setminus C);と置く.
この時, 代数的に滑らかな成分が&math(S_i);方向に滑らかである点に着目し, &math(n \times |C|);の補完行列&math(P);を
#br
#math((P{\vec v}')_i = \left\{ \begin{array}{ll} {v}'_i & (i \in C) \\ \sum_{j \in C_i} \pi_{ij} {v}'_j & (i \in F) \end{array} \right. );
#br
のように設定する.
ただし, &math(C_i = C \cap S_i);であり, &math(\pi_{ij});は適当な重みである.

// 近似解&math({\vec u});の誤差&math({\vec e});が代数的に滑らかな時, 適当なベクトル&math(\widehat{\vec v});を選んで新しい近似解&math(\widetilde{\vec u}={\vec u} + P \widehat{\vec v});の誤差&math(\widetilde{\vec e}={\vec e}+P\widehat{\vec v});を&math({\bm 0});にできるためには&math({\vec e} \in {\rm Ran}(P));が成り立つ必要がある.
// このため, 任意の代数的に滑らかな成分が(少なくとも近似的に)&math({\rm Ran}(P));に属するように, 重み&math(\pi_{ij});を設定する.


*参考文献および参考書 [#l077e0f3]

**原著論文 [#s16e076d]

**教科書 [#v582b626]
[14] Yousef Saad, Iterative Methods for Sparse Linear Systems, 2nd ed., SIAM: Philadelphia, PA,
2003.&br;
P407–449

[23] Masaaki Sugihara and Kazuo Murota, Theoretical Numerical Linear Algebra, Iwanami Press: Tokyo, 2009, (in Japanese).&br;
P106–136
代数的マルチグリッド法 の変更点

代数的マルチグリッド法の変更点
