マルチグリッド法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

マルチグリッド法は、複数階層で離散化を行うことにより、微分方程式を解くための数値アルゴリズムの一種である。間隔の異なる格子間での補外と考えることもできる。マルチグリッド法は、主に多次元の楕円型偏微分方程式の数値計算に用いられる。

マルチグリッド法は任意の離散化手法と組み合わせることができ、現在知られているものの中でも最速な解法の一つである。他の手法と異なり、マルチグリッド法は任意の領域・境界条件を扱うことができる。これは微分方程式の性質(変数分離可能かどうか等)には依存しない。MG法は、弾性に関するラメの微分方程式やナビエ・ストークス方程式などの、より複雑な非対称・非線形問題にもそのまま適用することができる。

マルチグリッド法はさまざまな方法で一般化することができる。双曲型偏微分方程式の時間発展解や、時間依存型の偏微分方程式に適用することもできる。現在、双曲型方程式に関する研究が進められている。積分方程式や、統計力学上の問題への応用も可能である。

一方、偏微分方程式や問題の物理的な性質を仮定しない場合にも、係数行列から多段階の階層を構成することができる。これを代数的マルチグリッド法といい、疎行列を対象としたブラックボックス型のソルバとして利用することができる。

有限要素法は、線形なウェーブレットを基底に選ぶことにより、マルチグリッド法になる。

アルゴリズム[編集]

いろいろな手法があるが、多階層の離散化を行う点が特徴である。

収束率[編集]

この手法の利点は、計算に使用するプロセッサ数に比例して線形に性能が向上する点にある。つまり、問題のサイズに比例した計算量で、与えられた精度まで計算することができる。

密度がN_iの格子i上で、微分方程式の近似解を(与えられた精度まで)求めることを考える。Kを格子上での解の計算に関する定数、また隣り合う格子の密度の比\rho = N_{j+1} / N_j < 1は常に一定であるとする。格子i+1の解を用いて、格子i上での解がW_i = \rho K N_iの計算量で求められるとすると、

W_k = W_{k+1} + \rho K N_k\,

特に最も細かい格子N_1に関して

W_1 = W_2 + \rho K N_1\,

の関係が格子k上での計算量に関して成り立つ。これらとN_{k} = \rho^{k-1} N_1の関係から、

W_1 = K N_1 \sum_{p=0}^n \rho^p

が得られる。幾何級数を使えば、(有限のnについて)

W_1 < K N_1 \frac{1}{1 - \rho}

なので、解はO(N)の計算時間で得られることが分かる。

関連項目[編集]

参考文献[編集]

  • Achi Brandt, Multi-Level Adaptive Solutions to Boundary-Value Problems, Math. Comp, 1977(31), 333-390 (jstor link).
  • 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