数値解析における数列の加速法 () とは、収束の遅い数列を収束の速い数列に変換するアルゴリズムの総称である。ただし，収束の極めて遅い対数収束列と呼ばれる数列全般に対して、収束を加速できるような単一のアルゴリズムは存在しないことが証明されている。なお、ベクトル列についても収束の加速法の研究がなされている。
級数加速の技法は、例えば特殊関数の様々な恒等式を得るためにも使われる。 例えばオイラー変換を超幾何級数に適用すると、古典的でよく知られた超幾何級数の恒等式のいくつかが得られる。
定義 与えられた数列
が極限
を持つとする。
ここで別の数列
が加速された数列であるとは、元の数列より に速く収束する 、すなわち
が成り立つ事と定める。
もし元の数列が発散数列の場合、数列の変換は:en:antilimitへの 補外法となる。
数列の変換は非線形なものほど強力である傾向がある。
歴史 19世紀以前 ヨーロッパと日本で研究が始まった。古典的な二つの加速法はオイラー変換 と クンマー変換である。日本では関孝和、建部賢弘など、ヨーロッパではアイザック・ニュートンなどが取り組んだ。
20世紀前半 エイトケンのΔ2乗加速法(但し、初出は関孝和による)、-算法Weisstein, Eric W. ”Wynn’s Epsilon Method.” From MathWorld–A Wolfram Web Resource. Wynn's Epsilon Method -- from Wolfram MathWorldやリチャードソンの補外（建部賢弘が1722に考案したのが初出）など、様々な加速法が作られる。なお、現代において-算法はMathematicaのNSum、NLimitに組み込まれている。
1956年にピーター・ウィンによって提案されたepsilon method、レヴィンのu-変換、そしてWilf-Zeilberger-Ekhad法またはWZ法が挙げられます。
交互級数に対しては、Cohen et al.によって記述された強力な手法がいくつかあり、それらはからまでの収束速度を提供し、項の総和に適用できます。Henri Cohen, Fernando Rodriguez Villegas, and Don Zagier, "Convergence Acceleration of Alternating Series", Experimental Mathematics, 9:1 (2000) page 3.
1990年代以降 加速法と可積分系・離散ソリトン方程式の関係が明らかになり、可積分系・離散ソリトン方程式から加速法を作る試みが始まった可積分系の応用数理、裳華房、中村佳正 et al.(2000)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.。加速法のq-類似を構成する試みもなされている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.。
オイラー変換 基本的な線形数列変換の例として、収束性を改善するオイラー変換があります。これは交代級数（隣り合う項の符号が反転する実数の級数）に適用され、次のように与えられます。
ここで、は前進差分演算子であり、その公式は以下の通りです。
元の級数（左辺）が収束が遅い場合、前進差分の大きさは急速に減少し、さらに2の負冪が乗じられることにより、右辺の級数の収束速度がさらに改善されます。
オイラー変換の特に効率的な数値実装はファン・ウィンガーデン変換William H. Press, et al., Numerical Recipes in C, (1987) Cambridge University Press, （5.1節を参照）です。
共形変換 ある級数
は、関数fを
と定義すると、と書けます。関数は複素平面内に特異点（分岐点特異点、極または真性特異点）を持ち、これが級数の収束半径を制限します。が収束円の境界近く、または上にある場合、級数の収束は非常に遅くなります。このとき、共形写像を用いて特異点を移動させ、に対応する点が新しい収束円内に深く入るようにすると、収束を改善できます。
共形変換はとなるように選ぶ必要があり、通常、w = 0で有限の微分を持つ関数を選びます。一般性を失うことなくと仮定でき、wを再スケールしてを再定義できます。その場合、次の関数を考えます。
なので、となります。であるため、の級数展開にを代入することで、の級数展開を得られます。の場合、の級数展開の最初の項は、の級数展開の最初の項を与えます。をその級数展開に代入すると、もし収束すれば、元の級数と同じ値に収束する級数が得られます。
非線形数列変換 非線形数列変換の例として、パデ近似、シャンクス変換、およびレヴィン型数列変換があります。
特に非線形数列変換は、摂動論などで生じる発散級数や漸近級数の総和法に強力な数値手法を提供し、非常に効果的な外挿法として使用できます。
応用 Steffensen 反復 これはエイトケンのΔ2乗加速法の応用で、方程式の解を求めるための反復法である。初期値を十分近くとれば1次収束する ( が 級なら超１次収束, 級なら2次収束する)。 反復法 の収束次数がのとき、ならばそれに対するSteffensen反復法の収束は次であり、で収束先がの単根ならばSteffensen法は2次であり、で収束先が重根の場合にはSteffensen法は1次になる牧之内三郎、鳥居達生：「数値解析」（3.2.4:'Steffensen法')、オーム社、ISBN 978-4-274-02011-7 (1975年10月25日）。
Romberg 積分
これは台形公式と加速法を組み合わせた数値積分法であるRomberg, W. (1955). Vereinfachte numerische integration. Norske Vid. Selsk. Forh., 28, 30-36, .。Bauer-Rutishauser-Stiefel (1963) により詳細な解析がなされている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) 精度保証付き数値計算の基礎, コロナ社.。
特殊関数 べき級数で定義された複素関数のある点に於ける値を求めるのに、元のべき級数の展開中心の位置を解析接続により移動させることでより収束率の高いべき級数の和に置き換えて計算ができたなら，それは元の級数の和に対する一種の加速法であると見なしうる。このような加速法は誤差関数などの特殊関数への計算に応用が可能である。
類似概念
常微分方程式の数値解法・偏微分方程式の数値解法においても収束の加速法が研究されており、有限要素法Kříek, M. (1994). "Superconvergence phenomena in the finite element method". Computer methods in applied mechanics and engineering, 116(1-4), 157-163, .やShortley-Weller近似 (差分法の一つ)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, .などを加速できることが分かっている。
出典
参考文献
Naoki Osada: "A Convergence Acceleration Method for Some Logarithmically Convergent Sequences", SIAM J. Numer. Anal., Vol.27, No.1, pp.178-189 (Feb., 1990).
（-算法の開発者であるWynnの研究業績をまとめた文献）
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 .
関連項目 リチャードソンの補外 :en:Binomial transform :en:Kummer's transformation of series :en:Wilf–Zeilberger pair :en:Shanks transformation :en:Van Wijngaarden transformation :en:Minimum polynomial extrapolation 解析接続
外部リンク Convergence acceleration of series Convergence Improvement, Wolfram MathWorld 離散ソリトン方程式の数理工学への応用