マルチグリッド法
マルチグリッド法は、複数階層で離散化を行うことにより、微分方程式を解くための数値アルゴリズムの一種である。間隔の異なる格子間での補外と考えることもできる。マルチグリッド法は、主に多次元の楕円型偏微分方程式の数値計算に用いられる。
マルチグリッド法は任意の離散化手法と組み合わせることができ、現在知られているものの中でも最速な解法の一つである。他の手法と異なり、マルチグリッド法は任意の領域・境界条件を扱うことができる。これは微分方程式の性質（変数分離可能かどうか等）には依存しない。MG法は、弾性に関するラメの微分方程式やナビエ・ストークス方程式などの、より複雑な非対称・非線形問題にもそのまま適用することができる。
マルチグリッド法はさまざまな方法で一般化することができる。双曲型偏微分方程式の時間発展解や、時間依存型の偏微分方程式に適用することもできる。現在、双曲型方程式に関する研究が進められている。積分方程式や、統計力学上の問題への応用も可能である。
一方、偏微分方程式や問題の物理的な性質を仮定しない場合にも、係数行列から多段階の階層を構成することができる。これを代数的マルチグリッド法といい、疎行列を対象としたブラックボックス型のソルバとして利用することができる。
有限要素法は、線形なウェーブレットを基底に選ぶことにより、マルチグリッド法になる。
アルゴリズム
いろいろな手法があるが、多階層の離散化を行う点が特徴である。
- 緩和 – ガウス・ザイデル法などを数反復実行して、誤差の高周波成分を減少させる
- 縮約 – より間隔の粗い格子に対して、残差のダウンサンプリングを行う
- 補間 – 粗い格子で計算した修正を細かい格子上に補間する
収束率
この手法の利点は、計算に使用するプロセッサ数に比例して線形に性能が向上する点にある。つまり、問題のサイズに比例した計算量で、与えられた精度まで計算することができる。
密度が[math]N_i[/math]の格子[math]i[/math]上で、微分方程式の近似解を（与えられた精度まで）求めることを考える。[math]K[/math]を格子上での解の計算に関する定数、また隣り合う格子の密度の比[math]\rho = N_{j+1} / N_j \lt 1[/math]は常に一定であるとする。格子[math]i+1[/math]の解を用いて、格子[math]i[/math]上での解が[math]W_i = \rho K N_i[/math]の計算量で求められるとすると、
- [math]W_k = W_{k+1} + \rho K N_k\, [/math]
特に最も細かい格子[math]N_1[/math]に関して
- [math]W_1 = W_2 + \rho K N_1\, [/math]
の関係が格子[math]k[/math]上での計算量に関して成り立つ。これらと[math]N_{k} = \rho^{k-1} N_1[/math]の関係から、
- [math]W_1 = K N_1 \sum_{p=0}^n \rho^p [/math]
が得られる。幾何級数を使えば、（有限の[math]n[/math]について）
- [math]W_1 \lt K N_1 \frac{1}{1 - \rho}[/math]
なので、解は[math]O(N)[/math]の計算時間で得られることが分かる。
関連項目
参考文献
- Achi Brandt: Multi-Level Adaptive Solutions to Boundary-Value Problems, Math. Comp, vol.31(1977), pp.333-390 (jstor link).
- Wolfgang Hackbusch: Multi-Grid Methods and Applications, Springer, ISBN 978-3-642-05722-9 (1985).
- William L. Briggs, Van Emden Henson, and Steve F. McCormick: A Multigrid Tutorial, Second Edition, SIAM, 2000 (book home page), ISBN 0-89871-462-1 .