![[JICFuS Wiki]](image/pukiwiki.png "[JICFuS Wiki]")
[[1 線形方程式の解法の選択]]&br; [[2 参考文献および参考書の記述]]&br; 線形方程式, &math(Ax=b); >>> 実非対称/複素非エルミート, &math(A\not=A^H); >>> その他 >>> マルチグリッド法： >>> 幾何的マルチグリッド法 #contents --------------------------------------------- *概要 [#pe324e74] - 偏微分方程式を離散化して得られる方程式に対して適用される. - 粗い格子から得られる方程式を利用して近似解を改善する2段グリッド法を再帰的に提要した方法. *2段グリッド法 [#k54ebee1] 偏微分方程式を離散化して得られる方程式 *モデル問題 [#c67d6246] 境界&math(\Gamma);において, Dirichlet条件を課した, 単位正方領域&math(\Omega = [0,1] \times [0,1]);内部のLaplace方程式 #br #math({A}^{h} {\vec x}^{h} = {\vec b}^{h}); CENTER:&math(\frac{\partial^2 u}{\partial x^2} + \frac{\partial^2 u}{\partial y^2} = 0 &\quad& ( (x,y) \in (0,1) \times (0,1) ) \\ u(x,y) = g(x,y) &\quad& ( (x,y) \in \Gamma)); #br に対してJacobi法やGauss-Seidel法などの定常反復法を適用すると, 誤差の持つ空間的高周波成分が速く減衰すること(平滑化作用)が知られている. を刻み幅&math(h=1/N);の格子を用いた5点中心差分法 #br CENTER:&math(4 u_{i,j} - u_{i+1,j} - u_{i-1,j} - u_{i,j+1} - u_{i,j-1} = 0 \quad (1 \leq i,j \leq N-1)); #br で離散化して得られる方程式 #br #math({A}^{h} {\vec u}^{h} = {\vec b}^{h}); #br を例に, 幾何的マルチグリッド法の概略を示す. *2段グリッド法 [#k54ebee1] 偏微分方程式を離散化して得られる方程式(1)に対してJacobi法やGauss-Seidel法などの定常反復法を適用すると, 誤差の持つ空間的高周波成分が速く減衰すること(平滑化作用)が知られている. このため空間的低周波成分で構成される粗い格子に対応する低次元の方程式 #br #math({A}^{2h} {\vec x}^{2h} = {\vec b}^{2h}); #math({A}^{2h} {\vec u}^{2h} = {\vec b}^{2h}); #br を用いて, 方程式(1)の近似解の精度を効率的に改善できることが期待される. この方法を2段グリッド法と呼ぶ. **制限(restriction) [#l0f83dfe] 細かい格子上の近似解&math({\vec u}^{h});から粗い格子上の近似解&math({\vec u}^{2h});を作ることを制限(restriction)と呼び, 一般には横長の長方行列&math(R^h);を用い&math({\vec u}^{2h} = R^h {\vec u}^h);とする. 制限行列&math(R^h);の設定の最も単純な方法は&math(u_{i,j}^{2h} = u_{2i,2j}^h);と設定することであるが, 通常は近傍の9点を用い, #br CENTER:&math(u_{i,j}^{2h} = \frac{1}{4} u_{2i,2j}^h + \frac{1}{8} \sum_{p=\pm 1} u_{2i+p,2j}^h + \frac{1}{8} \sum_{q=\pm 1} u_{2i,2j+q}^h + \frac{1}{16} \sum_{q=\pm 1} u_{2i+p,2j+q}^h); #br となるように設定する. **補完(interpolation)または延長(prolongation) [#v008d1d1] 逆に, 粗い格子上の近似解&math({\vec u}^{2h});から細かい格子上の近似解&math({\vec u}^{h});を作ることを補完(interpolation)または延長(prolongation)と呼び, 一般には縦長の長方行列&math(P^h);を用い&math({\vec u}^{h} = P^h {\vec u}^{2h});とする. 補完行列&math(P^h);の設定の標準的な方法としては, #br CENTER:&math(u_{2i,2j}^h &=& u_{i,j}^{2h}, \\ u_{2i+1,2j}^h &=& \frac{1}{2} (u_{i,j}^{2h} + u_{i+1,j}^{2h} ), \\ u_{2i,2j+1}^h &=& \frac{1}{2} (u_{i,j}^{2h} + u_{i,j+1}^{2h} ), \\ u_{2i+1,2j+1}^h &=& \frac{1}{4} (u_{i,j}^{2h} + u_{i+1,j}^{2h} + u_{i,j+1}^{2h}+ u_{i+1,j+1}^{2h} )); #br とすることである. **2段グリッド法のアルゴリズム [#d94c29b1] + 方程式&math(A^h{\vec x}^h={\vec b}^h);に対し定常反復法を数反復適用し近似解&math({\vec x}^h);を得る. + 残差&math({\vec r}^h:={\vec b}^h-A^h{\vec x}^h);の粗い格子への制限(restriction)&math({\vec r}^{2h}=R{\vec r}^h);を計算する. + 方程式&math(A^h{\vec u}^h={\vec b}^h);に対し定常反復法を数反復適用し近似解&math({\vec u}^h);を得る. + 残差&math({\vec r}^h:={\vec b}^h-A^h{\vec u}^h);の粗い格子への制限(restriction)&math({\vec r}^{2h}=R{\vec r}^h);を計算する. + 粗い格子の方程式&math({A}^{2h}{\vec e}^{2h}={\vec r}^{2h});を解く. + &math({\vec e}^{2h});の補完(interpolation)&math(P{\vec e}^{2h});を用い, 細かい格子上の近似解を&math({\vec x}^{h}={\vec x}^{h}+P{\vec e}^{2h});と修正する. + 方程式&math(A^h{\vec x}^h={\vec b}^h);に対し&math({\vec x}^h);を初期近似解として, 定常反復法を数反復適用し近似解&math({\vec x}^h);を得る. + &math({\vec e}^{2h});の補完(interpolation)&math(P{\vec e}^{2h});を用い, 細かい格子上の近似解を&math({\vec u}^{h}={\vec u}^{h}+P{\vec e}^{2h});と修正する. + 方程式&math(A^h{\vec u}^h={\vec b}^h);に対し&math({\vec u}^h);を初期近似解として, 定常反復法を数反復適用し近似解&math({\vec u}^h);を得る. * マルチグリッド法 [#p1f6a5f7] - マルチグリッド法は上記の2段グリッド法を再帰的に行う方法である. - マルチグリッド法を連立一次方程式に対する解法として用いる場合, 粗い方程式(2)が十分小さくなるまで再帰的に2段グリッド法を適用し, 十分小さい方程式をLU分解等の直接法で解く. 再帰の具体的な方法についてはVサイクルやWサイクルなどいくつかの方法が提案されている. - 一方, マルチグリッド法を前処理として用いる場合は, 2段グリッド法を数段階だけ再帰的に行い, この時, 最も粗い方程式に対しては定常反復法を数反復適用することで近似解を得る. *参考文献および参考書 [#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
