マルチグリッド法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
数学 > 数値解析 > 偏微分方程式の数値解法 > マルチグリッド法

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

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

一般化[編集]

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

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

有限要素法[20][21][22][23]において、線形なウェーブレットを基底に選ぶことにより、マルチグリッド法に帰着させることができる。

アルゴリズム[編集]

いろいろな手法があるが、多階層の離散化を行う点が特徴である[1][2][3][4][5]

収束率[編集]

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

密度がの格子上で、微分方程式の近似解を(与えられた精度まで)求めることを考える。を格子上での解の計算に関する定数、また隣り合う格子の密度の比は常に一定であるとする。格子の解を用いて、格子上での解がの計算量で求められるとすると、

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

の関係が格子上での計算量に関して成り立つ。これらとの関係から、

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

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

関連項目[編集]

参考文献[編集]

  • 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 .

関連文献[編集]

  • Roman Wienands and Wolfgang Joppich:"Practical Fourier Analysis for Multigrid Methods", Chapman and Hall/CRC, ISBN 978-1584884927 (2004年).

脚注[編集]

  1. ^ a b c d e Wolfgang Hackbusch: Multi-Grid Methods and Applications, Springer, ISBN 978-3-642-05722-9 (1985).
  2. ^ a b c d e McCormick, S. F. (Ed.). (1987). Multigrid methods. Society for Industrial and Applied Mathematics.
  3. ^ a b c d e Hackbusch, W., & Trottenberg, U. (Eds.). (2006). Multigrid methods: proceedings of the conference held at Köln-Porz, November 23-27, 1981 (Vol. 960). Springer.
  4. ^ a b c d e Yavneh, I. (2006). Why multigrid methods are so efficient. Computing in science & engineering, 8(6), 12-22.
  5. ^ a b c d e Bramble, J. H. (2018). Multigrid methods. Routledge.
  6. ^ Brezinski, C., & Zaglia, M. R. (2013). Extrapolation methods: theory and practice. Elsevier.
  7. ^ 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.
  8. ^ Fulton, S. R., Ciesielski, P. E., & Schubert, W. H. (1986). Multigrid methods for elliptic problems: A review. Monthly Weather Review, 114(5), 943-959.
  9. ^ Constantin, P., & Foias, C. (1988). Navier-stokes equations. University of Chicago Press.
  10. ^ Temam, R. (2001). Navier-Stokes equations: theory and numerical analysis (Vol. 343). American Mathematical Society.
  11. ^ Foias, C., Manley, O., Rosa, R., & Temam, R. (2001). Navier-Stokes equations and turbulence (Vol. 83). Cambridge University Press.
  12. ^ Henson, V. E. (2002). Multigrid methods for nonlinear problems: an overview (Vol. 5016, No. UCRL-JC-150259). Lawrence Livermore National Lab., CA (US).
  13. ^ Katzer, E. (1991). Multigrid methods for hyperbolic equations. In Multigrid methods III (pp. 253-263). Birkhäuser, Basel.
  14. ^ Schippers, H. (1982). Application of multigrid methods for integral equations to two problems from fluid dynamics. Journal of Computational Physics, 48(3), 441-461.
  15. ^ 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.
  16. ^ Notay, Y. (2010). An aggregation-based algebraic multigrid method. Electronic transactions on numerical analysis, 37(6), 123-146.
  17. ^ 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.
  18. ^ Napov, A., & Notay, Y. (2012). An algebraic multigrid method with guaranteed convergence rate. SIAM journal on scientific computing, 34(2), A1079-A1109.
  19. ^ Van, P., Brezina, M., & Mandel, J. (2001). Convergence of algebraic multigrid based on smoothed aggregation. Numerische Mathematik, 88(3), 559-579.
  20. ^ 森正武. (1986) 有限要素法とその応用. 岩波書店.
  21. ^ 菊池文雄. (1999). 有限要素法概説 [新訂版]. サイエンス社.
  22. ^ 菊池文雄. (1994). 有限要素法の数理. 培風館.
  23. ^ 有限要素法で学ぶ現象と数理―FreeFem++数理思考プログラミング―, 日本応用数理学会 監修・大塚 厚二・高石 武史著, 共立出版.