数列の加速法

数値解析における数列の加速法 (英: 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 長田直樹「収束の加速法の歴史 : 17世紀ヨーロッパと日本の加速法 (数学史の研究)」『数理解析研究所講究録』第1787巻、京都大学数理解析研究所、2012年4月、88-104頁、CRID 1050282810743934208、hdl:2433/172780、ISSN 1880-2818。
^ ^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 森正武「解析接続と級数の収束の加速 (解析接続の応用)」『数理解析研究所講究録』第1155巻、京都大学数理解析研究所、2000年5月、104-119頁、CRID 1050282676913607168、hdl:2433/64145、ISSN 1880-2818、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『Acceleration Methods for Slowly Convergent Sequences and their Applications』（博士（工学）論文）乙第4391号、名古屋大学、1993年1月1日。doi:10.11501/3068987。http://www.cis.twcu.ac.jp/~osada/thesis_osada.pdf。
杉原, 正顕、室田, 一雄「第12章加速」『数値計算法の数理』岩波書店、1994年。ISBN 978-4000055185。
長田, 直樹「収束の加速法（数値計算アルゴリズムの現状と展望）」『数理解析研究所講究録』第880号、京都大学数理解析研究所、1994年、28-43頁、CRID 1050282810580235648、ISSN 1880-2818、NAID 110004757389。
近藤, 弘一、中村, 佳正「高次収束するSteffensen型反復解法（数値計算アルゴリズムの研究）」『数理解析研究所講究録』第1040号、京都大学数理解析研究所、1998年、228-236頁、CRID 1050282677086372480、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
離散ソリトン方程式の数理工学への応用

級数・数列

等差数列

発散級数	1 + 1 + 1 + 1 + ⋯ 1 + 2 + 3 + 4 + ⋯ 無限算術級数

等比数列

収束級数	1/2 − 1/4 + 1/8 − 1/16 + ⋯ 1/2 + 1/4 + 1/8 + 1/16 + ⋯ 1/4 + 1/16 + 1/64 + 1/256 + ⋯
発散級数	1 + 1 + 1 + 1 + ⋯ 1 + 2 + 4 + 8 + ⋯ 1 − 2 + 4 − 8 + ⋯ グランディ級数

整数列

その他の数列

発散級数	1 − 2 + 3 − 4 + ⋯ 1 − 1 + 2 − 6 + 24 − 120 + ⋯ 調和級数
収束級数	交項級数幾何級数超幾何級数 q超幾何級数ライプニッツの公式

数列の加速法

エイトケンのΔ2乗加速法

カテゴリ:級数・カテゴリ:数列

表話編歴微分積分学
Precalculus	二項定理凹関数連続関数階乗有限差分自由変数と束縛変数基本定理関数のグラフ線型関数平均値の定理ラジアンロルの定理割線傾き接線
極限	不定形（英語版）関数の極限片側極限数列の極限数列の加速法近似のオーダー（英語版） ε-δ論法
微分法	連鎖律導関数微分微分方程式微分作用素陰関数微分逆関数の微分（英語版）ロピタルの定理ライプニッツ則対数微分平均値の定理ニュートン法記法ライプニッツの記法ニュートンの記法レギオモンタヌスの問題相対変化率（英語版）基本法則線型性（英語版）積商冪函数（英語版）停留点極値の判定（英語版）最大値の定理極値テイラーの定理
積分法	逆微分弧長積分定数積分記号下の微分（英語版）微分積分学の基本定理正割の立方の積分（英語版）正割関数の積分（英語版）半角正接置換法（英語版）積分における部分分数（英語版）二次有理式の積分（英語版）円周率が22/7より小さいことの証明基本法則線型性（英語版）部分積分置換積分台形公式三角函数置換法（英語版）
ベクトル解析	回転方向微分発散発散定理勾配勾配定理（英語版）グリーンの定理ラプラシアンストークスの定理
多変数微分積分学	曲率 Disc integration（英語版）発散定理外微分ガブリエルのホルン幾何解析（英語版）ヘッセ行列ヤコビ行列と行列式線積分 Matrix calculus 多重積分偏微分バウムクーヘン積分面積分テンソル解析体積分
級数	アーベルの判定法（英語版）交代交代級数判定法（英語版）算術幾何数列二項コーシーの凝集判定法比較判定法ディリクレの判定法オイラー–マクローリンの公式フーリエ幾何超幾何 q超幾何調和無限積分判定法極限比較判定法（英語版）マクローリン冪比判定法冪根判定法テイラー項判定法（英語版）
特殊関数と数学定数	ベルヌーイ数ネイピア数オイラー定数指数関数自然対数ガンマ関数スターリングの近似楕円関数
歴史（英語版）	擬等式（英語版）ブルック・テイラーコリン・マクローリン代数の一般性（英語版）ゴットフリート・ヴィルヘルム・ライプニッツ無限小無限小解析（英語版）アイザック・ニュートン連続の法則（英語版）レオンハルト・オイラー『流率法』 (流率（英語版）) 『方法（英語版）』
一覧	微分法則（英語版）指数関数の原始関数双曲線関数の原始関数逆双曲線関数の原始関数逆三角関数の原始関数無理関数の原始関数対数関数の原始関数有理関数の原始関数三角関数の原始関数極限数学記号原始関数
カテゴリ