数列の加速法
表示
数値解析における数列の加速法 (英: 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 積分[編集]
詳細は「:en:Romberg integration」を参照
これは台形公式と加速法を組み合わせた数値積分法である[1][10]。Bauer-Rutishauser-Stiefel (1963) により詳細な解析がなされている[11]。現代では精度保証付き数値計算にも使われている[12]。
特殊関数[編集]
加速法によって複素関数をより広い領域で計算可能になるので、一種の解析接続と見なすことも可能である[13]。加速法は誤差関数などの特殊関数への計算に応用可能である[13]。類似概念[編集]
「超収束」も参照
常微分方程式の数値解法・偏微分方程式の数値解法においても収束加速が研究されており、有限要素法[14]やShortley-Weller近似 (差分法の一つ)[15]などを加速できることが分かっている。
出典[編集]
(一)^ abcde山本哲朗﹃数値解析入門﹄︵増訂版︶サイエンス社︿サイエンスライブラリ 現代数学への入門14﹀、2003年6月。ISBN 4-7819-1038-6。
(二)^ ab長田直樹﹁収束の加速法の歴史 : 17世紀ヨーロッパと日本の加速法 (数学史の研究)﹂﹃数理解析研究所講究録﹄第1787巻、京都大学数理解析研究所、2012年4月、88-104頁、CRID 1050282810743934208、hdl:2433/172780、ISSN 1880-2818。
(三)^ abWeisstein, 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.
(11)^ F. L. Bauer, H. Rutishauser and E. Stiefel, New aspects in numerical quadrature, Proc. Symp. Appl. Math. (AMS, 1963), vol. 15, p. 198–218.
(12)^ 大石進一 et al.(2018) 精度保証付き数値計算の基礎, コロナ社.
(13)^ ab森正武﹁解析接続と級数の収束の加速 (解析接続の応用)﹂﹃数理解析研究所講究録﹄第1155巻、京都大学数理解析研究所、2000年5月、104-119頁、CRID 1050282676913607168、hdl:2433/64145、ISSN 1880-2818、NAID 110000164534。
(14)^ 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.
(15)^ 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.