数列の加速法
数値解析における数列の加速法 (英: Series acceleration) とは、収束の遅い数列を収束の速い数列に変換するアルゴリズムの総称である[1]。ただし,収束の極めて遅い対数収束列と呼ばれる数列全般に対して、収束を加速できるような単一のアルゴリズムは存在しないことが証明されている。なお、ベクトル列についても収束の加速法の研究がなされている。
歴史
19世紀以前
ヨーロッパと日本で研究が始まった。日本では関孝和、建部賢弘など、ヨーロッパではアイザック・ニュートンなどが取り組んだ[2]。
20世紀前半
エイトケンのΔ2乗加速法(但し、初出は関孝和の論文)[1][2]、-算法[3]など、様々な加速法が作られる。なお、現代において-算法はMathematicaのNSum、NLimitに組み込まれている[3]。
1990年代以降
加速法と可積分系・離散ソリトン方程式の関係が明らかになり、可積分系・離散ソリトン方程式から加速法を作る試みが始まった[4][5][6][7]。加速法のq-類似を構成する試みもなされている[8][9]。
応用
Steffensen 反復
これはエイトケンのΔ2乗加速法の応用で、方程式の解を求めるための反復法である[1]。初期値を十分近くとれば1次収束する ( が 級なら超1次収束, 級なら2次収束する[1])。
Romberg 積分
これは台形公式と加速法を組み合わせた数値積分法である[1][10]。Bauer-Rutishauser-Stiefel (1963) により詳細な解析がなされている[11]。現代では精度保証付き数値計算にも使われている[12]。
特殊関数
加速法によって複素関数をより広い領域で計算可能になるので、一種の解析接続と見なすことも可能である[13]。加速法は誤差関数などの特殊関数への計算に応用可能である[13]。
類似概念
常微分方程式の数値解法・偏微分方程式の数値解法においても収束加速が研究されており、有限要素法[14]やShortley-Weller近似 (差分法の一つ)[15]などを加速できることが分かっている。
出典
- ^ a b c d e 山本哲朗『数値解析入門』(増訂版)サイエンス社〈サイエンスライブラリ 現代数学への入門 14〉、2003年6月。ISBN 4-7819-1038-6。
- ^ a b 長田直樹, 「収束の加速法の歴史」 京都大学数理解析研究所講究録 第1787 巻, 2012 年, 88-104, NAID 110009423483。
- ^ a b Weisstein, Eric W. ”Wynn’s Epsilon Method.” From MathWorld–A Wolfram Web Resource. Wynn's Epsilon Method -- from Wolfram MathWorld
- ^ 可積分系の応用数理、裳華房、中村佳正 et al.(2000)
- ^ 永井敦, 薩摩順吉「加速法と離散型ソリトン方程式(非線形可積分系の応用数理)」『数理解析研究所講究録』第933号、京都大学数理解析研究所、1995年、44-60頁、ISSN 1880-2818、NAID 110004701995。
- ^ Papageorgiou, Grammaticos and Ramani (1993). Integrable Lattices and Convergence Acceleration Algorithms, Phys. Lett. A 179, 111-115.
- ^ Chang, X. K., He, Y., Hu, X. B., & Li, S. H. (2018). A new integrable convergence acceleration algorithm for computing Brezinski-Durbin-Redivo-Zaglia’s sequence transformation via Pfaffians. Numerical Algorithms, 1-20.
- ^ He, Y., Hu, X. B., Tam, H. W. (2009). A -Difference Version of the -Algorithm. Journal of Physics A: Mathematical and Theoretical, 42(9), 095202.
- ^ Sun Jian-Qing, He Yi, Hu Xing-Biao, Tam Hon-Wah (2011). “Q-difference and confluent forms of the lattice Boussinesq equation and the relevant convergence acceleration algorithms”. Journal of mathematical physics (American Institute of Physics) 52 (2): 023522. doi:10.1063/1.3554693 .
- ^ Romberg, W. (1955). Vereinfachte numerische integration. Norske Vid. Selsk. Forh., 28, 30-36, NAID 10004043042.
- ^ F. L. Bauer, H. Rutishauser and E. Stiefel, New aspects in numerical quadrature, Proc. Symp. Appl. Math. (AMS, 1963), vol. 15, p. 198–218.
- ^ 大石進一 et al.(2018) 精度保証付き数値計算の基礎, コロナ社.
- ^ a b 森正武 (2000), 「解析接続と級数の収束の加速 (解析接続の応用)」 京都大学数理解析研究所講究録, 1155, 104-119, NAID 110000164534.
- ^ Kříek, M. (1994). "Superconvergence phenomena in the finite element method". Computer methods in applied mechanics and engineering, 116(1-4), 157-163, doi:10.1016/S0045-7825(94)80019-7.
- ^ Matsunaga, N., & Yamamoto, T. (2000). "Superconvergence of the Shortley–Weller approximation for Dirichlet problems". en:Journal of computational and applied mathematics, 116(2), 263-273, doi:10.1016/S0377-0427(99)00321-0.
参考文献
- 伊理正夫:「数値計算」、朝倉書店、ISBN 978-4254113624(1981)の第1章第6節"エイトケン加速とステフェンセン変換"、同章第7節"ε算法"。
- J. P. Delahaye : Sequence Transformations, Springer-Verlag, Berlin, ISBN 978-3540152835 (1988).
- C. Brezinski and M. Redivo Zaglia : Extrapolation Methods. Theory and Practice, North-Holland, 1991.
- Naoki Osada : "Acceleration Methods for Slowly Convergent Sequences and their Applications" (1993), Ph.D. Thesis. (PDF)
- 杉原正顕、室田一雄:「数値計算法の数理」岩波書店、ISBN 978-4000055185 (1994)の第12章"加速"。
- 長田直樹「収束の加速法(数値計算アルゴリズムの現状と展望)」『数理解析研究所講究録』第880号、京都大学数理解析研究所、1994年、28-43頁、ISSN 1880-2818、NAID 110004757389。
- 近藤弘一, 中村佳正「高次収束するSteffensen型反復解法(数値計算アルゴリズムの研究)」『数理解析研究所講究録』第1040号、京都大学数理解析研究所、1998年、228-236頁、ISSN 1880-2818、NAID 110002339362。
- Brezinski Claude and Redivo-Zaglia Michela : "The genesis and early developments of Aitken's process, Shanks transformation, the -algorithm, and related fixed point methods", Numerical Algorithms, Vol.80, No.1, (2019), pp.11-133.
- Sidi Avram : Vector Extrapolation Methods with Applications, SIAM, ISBN 978-1-61197-495-9 (2017).
- Brezinski Claude, Redivo-Zaglia Michela and Saad Yousef : "Shanks Sequence Transformations and Anderson Acceleration", SIAM Review, Vol.60, No.3 (2018), pp.646–669. doi:10.1137/17M1120725.
- Brezinski Claude: "Reminiscences of Peter Wynn", Numerical Algorithms, Vol.80 (2019), pp.5-10 (2019). (-算法の開発者であるWynnの研究業績をまとめた文献)
- Brezinski Claude and Redivo-Zaglia Michela : Extrapolation and Rational Approximation, Springer, ISBN 978-3-030-58417-7 (2020).
関連項目
- リチャードソンの補外
- en:Binomial transform
- en:Kummer's transformation of series
- en:Wilf–Zeilberger pair
- en:Shanks transformation
- en:Van Wijngaarden transformation
- en:Minimum polynomial extrapolation
- 解析接続