マルチグリッド法

マルチグリッド（MG）法は、複数階層で離散化を行うことにより、微分方程式を解くための数値アルゴリズムの一種である。間隔の異なる格子間での補外と考えることもできる。マルチグリッド法は、主に多次元の楕円型偏微分方程式の数値計算に用いられる。
マルチグリッド法は任意の離散化手法と組み合わせることができ、現在知られているものの中でも最速な解法の一つである。他の手法と異なり、マルチグリッド法は任意の領域・境界条件を扱うことができる。これは微分方程式の性質（変数分離可能かどうか等）には依存しない。MG法は、弾性に関するラメの微分方程式やナビエ・ストークス方程式などの、より複雑な非対称・非線形問題にもそのまま適用することができる。
一般化.
マルチグリッド法はさまざまな方法で一般化することができる。双曲型偏微分方程式の時間発展解や、時間依存型の偏微分方程式に適用することもできる。現在、双曲型方程式に関する研究が進められている。積分方程式や、統計力学上の問題への応用も可能である。
一方、偏微分方程式や問題の物理的な性質を仮定しない場合にも、係数行列から多段階の階層を構成することができる。これを代数的マルチグリッド法といい、疎行列を対象としたブラックボックス型のソルバとして利用することができる。
有限要素法において、線形なウェーブレットを基底に選ぶことにより、マルチグリッド法に帰着させることができる。
アルゴリズム.
いろいろな手法があるが、多階層の離散化を行う点が特徴である。
収束率.
この手法の利点は、計算に使用するプロセッサ数に比例して線形に性能が向上する点にある。つまり、問題のサイズに比例した計算量で、与えられた精度まで計算することができる。
密度がformula_1の格子formula_2上で、微分方程式の近似解を（与えられた精度まで）求めることを考える。formula_3を格子上での解の計算に関する定数、また隣り合う格子の密度の比formula_4は常に一定であるとする。格子formula_5の解を用いて、格子formula_2上での解がformula_7の計算量で求められるとすると、
特に最も細かい格子formula_9に関して
の関係が格子formula_11上での計算量に関して成り立つ。これらとformula_12の関係から、
が得られる。幾何級数を使えば、（有限のformula_14について）
なので、解はformula_16の計算時間で得られることが分かる。