マルチグリッド法のソースを表示

{{pathnav|数学|数値解析|偏微分方程式の数値解法}}
'''マルチグリッド（MG）法'''は、階層間での多段階の離散化を行うことで、滑らかな解を持つ[[微分方程式]]を解くための[[数値解析|数値]][[アルゴリズム]]の手法である<ref name="briggs">William L. Briggs: ''A Multigrid Tutorial'', SIAM, ISBN 0-89871-221-1 (1987).</ref><ref name="wolf">Wolfgang Hackbusch: ''Multi-Grid Methods and Applications'', Springer, ISBN 978-3-642-05722-9 (1985).</ref><ref name="mc">McCormick, S. F. (Ed.). (1987). Multigrid methods. Society for Industrial and Applied Mathematics.</ref><ref name="ht">Hackbusch, W., & Trottenberg, U. (Eds.). (2006). Multigrid methods: proceedings of the conference held at Köln-Porz, November 23-27, 1981 (Vol. 960). Springer.</ref><ref name="why">Yavneh, I. (2006). Why multigrid methods are so efficient. Computing in science & engineering, 8(6), 12-22.</ref><ref name="bra">Bramble, J. H. (2018). Multigrid methods. Routledge.</ref>。間隔の異なる格子間での[[外挿|補外]]<ref>Brezinski, C., & Zaglia, M. R. (2013). Extrapolation methods: theory and practice. Elsevier.</ref>と考えることもできる。マルチグリッド法は、主に多次元の楕円型偏微分方程式の数値計算に用いられる<ref>Zubair, H. B., Oosterlee, C. W., & Wienands, R. (2007). Multigrid for high-dimensional elliptic partial differential equations on non-equidistant grids. SIAM Journal on Scientific Computing, 29(4), 1613-1636.</ref><ref>Fulton, S. R., Ciesielski, P. E., & Schubert, W. H. (1986). Multigrid methods for elliptic problems: A review. Monthly Weather Review, 114(5), 943-959.</ref>。

マルチグリッド法は任意の離散化手法と組み合わせることが可能で、漸近的に最も高速な解法のうちの一つである<ref name="wolf"/><ref name="mc"/><ref name="ht"/><ref name="why"/><ref name="bra"/>。他の手法とは異なり、マルチグリッド法では任意の領域・[[境界条件]]を扱うことができる<ref name="wolf"/><ref name="mc"/><ref name="ht"/><ref name="why"/><ref name="bra"/>。それは微分方程式の性質（たとえば変数分離可能であるかどうかなど）には依存しないからである。マルチグリッド法は、[[弾性]]に関するラメの微分方程式や[[ナビエ・ストークス方程式]]<ref>Constantin, P., & Foias, C. (1988). Navier-stokes equations. University of Chicago Press.</ref><ref>Temam, R. (2001). Navier-Stokes equations: theory and numerical analysis (Vol. 343). American Mathematical Society.</ref><ref>Foias, C., Manley, O., Rosa, R., & Temam, R. (2001). Navier-Stokes equations and turbulence (Vol. 83). Cambridge University Press.</ref>などの、より複雑な非対称・非線形の問題にもそのまま適用できる<ref>Henson, V. E. (2002). Multigrid methods for nonlinear problems: an overview (Vol. 5016, No. UCRL-JC-150259). Lawrence Livermore National Lab., CA (US).</ref>。
==一般化==
マルチグリッド法はさまざまな形に一般化が可能である<ref name="wolf"/><ref name="mc"/><ref name="ht"/><ref name="why"/><ref name="bra"/>。双曲型[[偏微分方程式]]の時間発展解や、時間依存型の偏微分方程式に適用可能である。現在、双曲型方程式への適用について研究が進められている<ref>Katzer, E. (1991). Multigrid methods for hyperbolic equations. In Multigrid methods III (pp. 253-263). Birkhäuser, Basel.</ref>。[[積分方程式]]や、[[統計力学]]上の問題にも応用が可能である<ref>Schippers, H. (1982). Application of multigrid methods for integral equations to two problems from fluid dynamics. Journal of Computational Physics, 48(3), 441-461.</ref><ref>Von Petersdorff, T., & Stephan, E. P. (1992). Multigrid solvers and preconditioners for first kind integral equations. Numerical Methods for Partial Differential Equations, 8(5), 443-450.</ref>。

一方、偏微分方程式や問題の物理現象に由来する性質を仮定せずに、係数行列から多段階の階層を構成することができる。これを'''代数的マルチグリッド法'''といい<ref>Notay, Y. (2010). An aggregation-based algebraic multigrid method. Electronic transactions on numerical analysis, 37(6), 123-146.</ref><ref>Reitzinger, S., & Schöberl, J. (2002). An algebraic multigrid method for finite element discretizations with edge elements. Numerical linear algebra with applications, 9(3), 223-238.</ref><ref>Napov, A., & Notay, Y. (2012). An algebraic multigrid method with guaranteed convergence rate. SIAM journal on scientific computing, 34(2), A1079-A1109.</ref><ref>Van, P., Brezina, M., & Mandel, J. (2001). Convergence of algebraic multigrid based on smoothed aggregation. Numerische Mathematik, 88(3), 559-579.</ref>、[[疎行列]]を対象としたブラックボックス型のソルバとして利用することができる。

[[有限要素法]]<ref name="mori">[[森正武]]. (1986) 有限要素法とその応用. [[岩波書店]].</ref><ref name="kikuchi1999">菊池文雄. (1999). 有限要素法概説 [新訂版]. サイエンス社.</ref><ref name="kikuchi1994">菊池文雄. (1994). 有限要素法の数理. 培風館.</ref><ref name="freefem">有限要素法で学ぶ現象と数理―[[FreeFem++]]数理思考プログラミング―, [[日本応用数理学会]] 監修・大塚 厚二・高石 武史著, [[共立出版]].</ref>は、解の展開基底に線形な[[ウェーブレット]]を選ぶと、マルチグリッド法に帰着する。

== アルゴリズム ==
いろいろな手法があるが、階層間での離散化を多段階行うところが特徴である<ref name="wolf"/><ref name="mc"/><ref name="ht"/><ref name="why"/><ref name="bra"/>。
* '''緩和''' – [[ガウス・ザイデル法]]などを数回程度反復実行して、誤差の高周波成分を強く減少させる
* '''縮約''' – より間隔の粗い格子に対して、残差の[[サンプリング周波数変換|ダウンサンプリング]]を行う
* '''補間''' – 粗い格子上で計算した修正を細かい格子上に[[補間]]する

== 収束率 ==
この手法の利点は、計算に用いるプロセッサの数に正比例して性能が向上する点にある。つまり、指定した精度の近似解を問題のサイズに比例した計算量で求めることができる。そのことを以下で示そう。

密度が<math>N_i</math>の格子<math>i</math>上で、微分方程式の近似解を（与えられた精度まで）求めることを考える。<math>K</math>を格子上での解の計算に関する定数、また隣り合う格子の密度の比<math>\rho = N_{j+1} / N_j < 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 < 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 ([http://links.jstor.org/sici?sici=0025-5718%28197704%2931%3A138%3C333%3AMASTBP%3E2.0.CO%3B2-M 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 ([http://www.llnl.gov/casc/people/henson/mgtut/welcome.html book home page]), ISBN 0-89871-462-1 .

== 関連文献 ==
* Roman Wienands and Wolfgang Joppich: ''Practical Fourier Analysis for Multigrid Methods'', Chapman and Hall/CRC, ISBN 978-1-58488492-7 (2004年).
* [https://github.com/copper-multigrid-conference Copper Mountain Conference on Multigrid Methods (Multigrid Conference materials) GitHub]

==脚注==
{{reflist|2}}
{{偏微分方程式の数値解法}}
{{DEFAULTSORT:まるちくりつとほう}}
[[Category:数値解析]]
[[Category:数値微分方程式]]
[[Category:数学に関する記事]]