【数値解析】マルチグリッド法：反復法の高速化へ向けた多重格子法の利用
このノートは以下のノートに関係するものです．
Recap：反復法による解法と弱点
Poisson 方程式や，Helmholtz 方程式など，線形な偏微分方程式を数値的に解く．
Poisson 方程式や，Helmholtz 方程式などが当てはまるだろう．
楕円型など分類がなされているが，ここでは詳細は触れない．
これを離散化して，式（２）のような行列方程式を得る．
以後，$${\bm{u}}$$を厳密解，$${\bm{v}}$$を数値解として表す．
反復法では，式（２）の行列方程式について，行列$$A$$を分解することや，重みをつけることで，漸化式を得る．
この漸化式を収束条件を満たすまで繰り返し計算する．
式（３）の反復式の収束性は，行列 $${R}$$ のスペクトル半径に依存する．
収束するには，$${\rho(R) < 1}$$ を満たさなくてはならない．
また，$${\rho(R)}$$ が小さいほど，収束が早い．
いずれの方法を取っても，長波長$${k \ll 1}$$の固有値を抑制できない．
どのような手法を取っても，長波長$${k \ll 1}$$において，
固有値スペクトルが大きいままである．
このため，この長波長成分の収束はかなり遅い．
これを解決するために，最初に定義した格子，細かいグリッド（fine grid）から粗視化グリッド（coarse grid）を行き来して，長波長の収束も早めようというのが，マルチグリッド法（Multigrid method）の基本戦略である．
反復の収束を早めることができるので，反復数が減る．
これでどのくらい計算量が減るのかは状況によっても異なるが．
$$
\mathcal{O}(N^2) \to \mathcal{O}(N)
$$
という大幅な改善がなされることが期待される．
マルチグリッド法（Multigrid method）
いくつかの大きな手順に分けられる．
独特の用語が出てくるが，大事なことは，
細かい格子（fine grid）と粗い格子（coarse grid）の行き来がどのように行われるのか，
各格子でどのような計算を行なって，どのように補正を行うのか，
の肝を知ることであろう．
準備
まずは，通常の反復法と同じように，
初期値 $${\bm{v}^{(0), h}}$$を準備しておく．
上付きの$${h}$$は初期のグリッド（最も細かいグリッド）を示す．
緩和 (pre-smoothing, relaxation)
初期の細かい格子点で，通常通り反復法を数回実行する．
これで，短波長，高周波成分の緩和を行うことができる．
$$
\bm{v}^{(m+1), h} = R \bm{v}^{(m), h} + G \bm{b}, m = 0,1, .., \nu
$$
次に短波長，低周波成分を緩和させるために，
粗視化されたグリッドへ移って再び反復計算させる．
残差（residual）と誤差（error）
粗視化されたグリッドには，全ての情報を渡す必要はない．
緩和しきれていない短波長成分だけを渡して，緩和させれば十分である．
pre-smoothing で得た $${\bm{v}}$$ を用いて，厳密解 $${A \bm{u} = \bm{b}}$$ とのずれを知ろう．
以下の２つのベクトルを定義しておく：
残差（residual）：
$$
\bm{r} \equiv \bm{b} - A \bm{v}
$$
誤差（error）:
$$
\bm{e} \equiv \bm{u} - \bm{v}
$$
これから，以下の残差と誤差に関する方程式を得る：
誤差を直接緩和させることができる．
この式（４）の残差方程式（the residual equation）を用いれば，誤差を反復法で緩和させ，緩和させた誤差から，厳密解に近づけるような補正をすることができる．
新たな計算値$${\bm{v}^{\text{new}}}$$は厳密解に近づく．
制限補間（restriction）
original のグリッド $${\Omega_{h}}$$ から
順にグリッド間隔が倍ずつ増えていくような粗視化を行おう．
どのように粗視化グリッドを取るかは問題や状況によって異なるようだが，
ここでは，一般的な粗視化
$$
r^{2h}_{2i} = \frac{1}{4} (r_{2i -1}^{h} + 2 r_{2i}^{h} + r_{2i + 1}^{h}),
i = 1, 2, \cdots, N/2 - 1
$$
を用いよう．
図（２）をみていただければわかると思うが，
長波長（低周波）成分だけがこの制限補間では見事に取り出されていく．
粗視化するほど，長波長成分だけが残る．
この制限補間によって長波長成分が取り出されるので，
粗視化グリッドで反復法を使えば，効率的に長波長成分を緩和させることができる．
緩和させる方程式は以下であることに注意：
延長補間（prolongation）
次に，制限補間した粗視化グリッドで，長波長成分を緩和させた結果$${\bm{e}^{2h}}$$をどうやって，細かいグリッドへと反映するかを見てみよう．
図（３）のように基本的には逆の操作を行う．
粗視化されたグリッドから，細かいグリッドへと移す．
青矢印は，そのまま値を細かいグリッドに移す．
赤矢印は，隣接するグリッドでの値の平均で補間することを表す．
これは数式で表すと以下の操作で示される：
$$
\begin{equation*}
\begin{split}
e^{h}_{2j} &= e^{2h}_{j}, \\
e^{h}_{2j + 1} &= \frac{1}{2} ( e^{2h}_{j} + e^{2h}_{j+1}) \\
& \text{where} j = 0, 1, 2, \cdots, N/2-1
\end{split}
\end{equation*}
$$
これを用いて以下のように補正する：
補正された解を再び，緩和させる．これで解を得る．
まとめ
今回は，マルチグリッド法の基礎，fine-grid，coarse-grid，そしてそれらを補間する方法を学んだ．
次回は，V-cycleや，他のスキームを導入する話になるかも？
それとその実装？