数列の加速法

数値解析における数列の加速法 (英: Series acceleration) とは、収束の遅い数列を収束の速い数列に変換するアルゴリズムの総称である^[1]。ただし，収束の極めて遅い対数収束列と呼ばれる数列全般に対して、収束を加速できるような単一のアルゴリズムは存在しないことが証明されている。なお、ベクトル列についても収束の加速法の研究がなされている。

歴史

19世紀以前

ヨーロッパと日本で研究が始まった。日本では関孝和、建部賢弘など、ヨーロッパではアイザック・ニュートンなどが取り組んだ^[2]。

20世紀前半

エイトケンのΔ2乗加速法(但し、初出は関孝和の論文)^[1]^[2]、 $\epsilon$ -算法^[3]など、様々な加速法が作られる。なお、現代において $\epsilon$ -算法はMathematicaのNSum、NLimitに組み込まれている^[3]。

1990年代以降

加速法と可積分系・離散ソリトン方程式の関係が明らかになり、可積分系・離散ソリトン方程式から加速法を作る試みが始まった^[4]^[5]^[6]^[7]。加速法のq-類似を構成する試みもなされている^[8]^[9]。

「可積分アルゴリズム」も参照

応用

Steffensen 反復

これはエイトケンのΔ2乗加速法の応用で、方程式 $x=g(x)$ の解を求めるための反復法である^[1]。初期値を十分近くとれば1次収束する ( $g(x)$ が $C^{1}$ 級なら超１次収束, $C^{2}$ 級なら2次収束する^[1])。

Romberg 積分

詳細は「:en:Romberg integration」を参照

これは台形公式と加速法を組み合わせた数値積分法である^[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 $q$ -Difference Version of the $\epsilon$ -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. https://doi.org/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.

参考文献

伊理, 正夫「1.6 エイトケン加速とステフェンセン変換、1.7 ε算法」『数値計算』朝倉書店、1981年。ISBN (978-4254113624)。
Delahaye, J. P. (1988). Sequence Transformations. Springer-Verlag. ISBN (978-3540152835)
Brezinski, C.; Redivo-Zaglia, M. (1991). Extrapolation Methods. Theory and Practice. North-Holland
Osada, Naoki (1 January 1993). Acceleration Methods for Slowly Convergent Sequences and their Applications (PDF) (博士（工学） thesis). 名古屋大学. doi:10.11501/3068987。
杉原, 正顕、室田, 一雄「第12章加速」『数値計算法の数理』岩波書店、1994年。
長田, 直樹「収束の加速法（数値計算アルゴリズムの現状と展望）」『数理解析研究所講究録』第880号、京都大学数理解析研究所、1994年、28-43頁、ISSN 1880-2818、NAID 110004757389。
近藤, 弘一、中村, 佳正「高次収束するSteffensen型反復解法（数値計算アルゴリズムの研究）」『数理解析研究所講究録』第1040号、京都大学数理解析研究所、1998年、228-236頁、ISSN 1880-2818、NAID 110002339362。
Brezinski, Claude; Redivo-Zaglia, Michela (2019). “The genesis and early developments of Aitken's process, Shanks transformation, the $ε$ -algorithm, and related fixed point methods”. Numerical Algorithms 80 (1): 11-133. doi:10.1007/s11075-018-0567-2.
Sidi, Avram (2017). Vector Extrapolation Methods with Applications. SIAM. ISBN (978-1-61197-495-9)
Brezinski, Claude; Redivo-Zaglia, Michela; Saad, Yousef (2018). “Shanks Sequence Transformations and Anderson Acceleration”. SIAM Review (SIAM) 60 (3): 646–669. doi:10.1137/17M1120725.
Brezinski, Claude (2019). “Reminiscences of Peter Wynn”. Numerical Algorithms 80: 5-10. doi:10.1007/s11075-018-0542-y. （ $ε$ -算法の開発者であるWynnの研究業績をまとめた文献）
Brezinski, Claude; Redivo-Zaglia, Michela (2020). Extrapolation and Rational Approximation. Springer. ISBN (978-3-030-58417-7)
Pepino, Rafael Tristão (2023). “Acceleration of sequences with transformations involving hypergeometric functions”. Numerical Algorithms 92: 893-915. doi:10.1007/s11075-022-01334-7.
Claude Brezinski, Michela Redivo-Zaglia & Ahmed Salam: "On the kernel of vector ε-algorithm and related topics", Numerical Algorithms, vol.92 (2023), pp.207–221. url=https://doi.org/10.1007/s11075-022-01358-z .

外部リンク

Convergence acceleration of series
Convergence Improvement, Wolfram MathWorld
離散ソリトン方程式の数理工学への応用
長田直樹:「収束の加速法」、数理解析研究所講究録、第880巻、1994年、頁28-43

この項目は、応用数学に関連した(書きかけの項目)です。この項目を加筆・訂正などしてくださる(協力者を求めています)。

[Yamamoto1-1] 山本哲朗『数値解析入門』（増訂版）サイエンス社〈サイエンスライブラリ現代数学への入門 14〉、2003年6月。ISBN (4-7819-1038-6)。

[history-2] 長田直樹, 「収束の加速法の歴史」京都大学数理解析研究所講究録第1787 巻, 2012 年, 88-104, NAID 110009423483。

[ep-3] Weisstein, Eric W. ”Wynn’s Epsilon Method.” From MathWorld–A Wolfram Web Resource. Wynn's Epsilon Method -- from Wolfram MathWorld

[app-4] 可積分系の応用数理、裳華房、中村佳正 et al.(2000)

[5] 永井敦, 薩摩順吉「加速法と離散型ソリトン方程式(非線形可積分系の応用数理)」『数理解析研究所講究録』第933号、京都大学数理解析研究所、1995年、44-60頁、ISSN 1880-2818、NAID 110004701995。

[6] Papageorgiou, Grammaticos and Ramani (1993). Integrable Lattices and Convergence Acceleration Algorithms, Phys. Lett. A 179, 111-115.

[7] 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.

[8] He, Y., Hu, X. B., Tam, H. W. (2009). A $q$ -Difference Version of the $\epsilon$ -Algorithm. Journal of Physics A: Mathematical and Theoretical, 42(9), 095202.

[9] 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. https://doi.org/10.1063/1.3554693.

[10] 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) 精度保証付き数値計算の基礎, コロナ社.

[sp-13] 森正武 (2000), 「解析接続と級数の収束の加速 (解析接続の応用)」京都大学数理解析研究所講究録, 1155, 104-119, 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

ウィキペディア	ランダム
毎日	カテゴリ