数列の加速法

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

級数加速の技法は、例えば特殊関数の様々な恒等式を得るためにも使われる。例えばオイラー変換を超幾何級数に適用すると、古典的でよく知られた超幾何級数の恒等式のいくつかが得られる。

定義

与えられた数列

S=\{s_{n}\}_{n\in \mathbb {N} }

が極限

\lim _{n\to \infty }s_{n}=\ell ,

を持つとする。

ここで別の数列

S'=\{s'_{n}\}_{n\in \mathbb {N} }

が加速された数列であるとは、元の数列より $\ell$ に速く収束する 、すなわち

\lim _{n\to \infty }{\frac {s'_{n}-\ell }{s_{n}-\ell }}=0

が成り立つ事と定める。

もし元の数列が発散数列の場合、数列の変換はen:antilimitへの補外法となる。

数列の変換は非線形なものほど強力である傾向がある。

歴史

19世紀以前

ヨーロッパと日本で研究が始まった。古典的な二つの加速法はオイラー変換^[2] とクンマー変換である。日本では関孝和、建部賢弘など、ヨーロッパではアイザック・ニュートンなどが取り組んだ^[3]。

20世紀前半

エイトケンのΔ2乗加速法(但し、初出は関孝和による)^[1]^[3]、 $\epsilon$ -算法^[4]やリチャードソンの補外（建部賢弘が1722に考案したのが初出）など、様々な加速法が作られる。なお、現代において $\epsilon$ -算法はMathematicaのNSum、NLimitに組み込まれている^[4]。

1956年にピーター・ウィンによって提案されたepsilon method、レヴィンのu-変換、そしてWilf-Zeilberger-Ekhad法またはWZ法が挙げられます。

交互級数に対しては、Cohen et al.によって記述された強力な手法がいくつかあり、それらは $5.828^{-n}$ から $17.93^{-n}$ までの収束速度を提供し、 $n$ 項の総和に適用できます。^[5]

1990年代以降

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

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

オイラー変換

基本的な線形数列変換の例として、収束性を改善するオイラー変換があります。これは交代級数（隣り合う項の符号が反転する実数の級数）に適用され、次のように与えられます。

\sum _{n=0}^{\infty }(-1)^{n}a_{n}=\sum _{n=0}^{\infty }(-1)^{n}{\frac {(\Delta ^{n}a)_{0}}{2^{n+1}}}

ここで、 $\Delta$ は前進差分演算子であり、その公式は以下の通りです。

(\Delta ^{n}a)_{0}=\sum _{k=0}^{n}(-1)^{k}{n \choose k}a_{n-k}.

元の級数（左辺）が収束が遅い場合、前進差分の大きさは急速に減少し、さらに2の負冪が乗じられることにより、右辺の級数の収束速度がさらに改善されます。

オイラー変換の特に効率的な数値実装はファン・ウィンガーデン変換^[12]です。

共形変換

ある級数

S=\sum _{n=0}^{\infty }a_{n}

は、関数fを

f(z)=\sum _{n=0}^{\infty }a_{n}z^{n}

と定義すると、 $f(1)$ と書けます。関数 $f(z)$ は複素平面内に特異点（分岐点特異点、極または本質的特異点）を持ち、これが級数の収束半径を制限します。 $z=1$ が収束円の境界近く、または上にある場合、級数 $S$ の収束は非常に遅くなります。このとき、共形写像を用いて特異点を移動させ、 $z=1$ に対応する点が新しい収束円内に深く入るようにすると、収束を改善できます。

共形変換 $z=\Phi (w)$ は $\Phi (0)=0$ となるように選ぶ必要があり、通常、w = 0で有限の微分を持つ関数を選びます。一般性を失うことなく $\Phi (1)=1$ と仮定でき、wを再スケールして $\Phi$ を再定義できます。その場合、次の関数を考えます。

g(w)=f(\Phi (w)).

$\Phi (1)=1$ なので、 $f(1)=g(1)$ となります。 $\Phi (0)=0$ であるため、 $f(z)$ の級数展開に $z=\Phi (w)$ を代入することで、 $g(w)$ の級数展開を得られます。 $\Phi '(0)\neq 0$ の場合、 $f(z)$ の級数展開の最初の $n$ 項は、 $g(w)$ の級数展開の最初の $n$ 項を与えます。 $w=1$ をその級数展開に代入すると、もし収束すれば、元の級数と同じ値に収束する級数が得られます。

非線形数列変換

非線形数列変換の例として、パデ近似、シャンクス変換、およびレヴィン型数列変換があります。

特に非線形数列変換は、摂動論などで生じる発散級数や漸近級数の総和法に強力な数値手法を提供し、非常に効果的な外挿法として使用できます。

応用

Steffensen 反復

これはエイトケンのΔ2乗加速法の応用で、方程式 $x=g(x)$ の解を求めるための反復法である^[1]。初期値を十分近くとれば1次収束する ( $g(x)$ が $C^{1}$ 級なら超１次収束, $C^{2}$ 級なら2次収束する^[1])。もしも反復法 $x:=g(x)$ の収束の次数が $p$ であるとき、それに対応するSteffensen反復法 $x:=G(x)\equiv \{xg(g(x))-(g(x))^{2}\}/\{x-2g(x)+g(g(x))\}$ の収束次数 $q$ は、 $p\geq 2$ ならば $q=2p-1$ であり、 $p=1$ の場合には収束先が $x=g(x)$ の単根である場合には $q=2$ であるが、収束先が重複根の場合には $q=1$ になる^[13]。

Romberg 積分

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

これは台形公式と加速法を組み合わせた数値積分法である^[1]^[14]。Bauer-Rutishauser-Stiefel (1963) により詳細な解析がなされている^[15]。現代では精度保証付き数値計算にも使われている^[16]。

特殊関数

べき級数で定義された複素関数の値をより広い領域で計算することが可能になるので、加速法は一種の解析接続と見なしうる^[17]。加速法は誤差関数などの特殊関数への計算に応用可能である^[17]。

類似概念

→「超収束」も参照

常微分方程式の数値解法・偏微分方程式の数値解法においても収束の加速法が研究されており、有限要素法^[18]やShortley-Weller近似 (差分法の一つ)^[19]などを加速できることが分かっている。

出典

[脚注の使い方]

^ ^a ^b ^c ^d ^e 山本哲朗『数値解析入門』（増訂版）サイエンス社〈サイエンスライブラリ現代数学への入門 14〉、2003年6月。ISBN 4-7819-1038-6。
^ Abramowitz, Milton [in 英語]; Stegun, Irene Ann [in 英語], eds. (1983) [June 1964]. "Chapter 3, eqn 3.6.27". Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. Applied Mathematics Series. Vol. 55 (Ninth reprint with additional corrections of tenth original printing with corrections (December 1972); first ed.). Washington D.C.; New York: United States Department of Commerce, National Bureau of Standards; Dover Publications. p. 16. ISBN 978-0-486-61272-0. LCCN 64-60036. MR 0167642. LCCN 65-12253。
^ ^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
^ Henri Cohen, Fernando Rodriguez Villegas, and Don Zagier, "Convergence Acceleration of Alternating Series", Experimental Mathematics, 9:1 (2000) page 3.
^ 可積分系の応用数理、裳華房、中村佳正 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.
^ William H. Press, et al., Numerical Recipes in C, (1987) Cambridge University Press, ISBN 0-521-43108-5（5.1節を参照）
^ 牧之内三郎、鳥居達生：「数値解析」（3.2.4:'Steffensen法')、オーム社、ISBN 978-4-274020117 (1975年10月25日）
^ 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。
杉原, 正顕、室田, 一雄「第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 .

外部リンク

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

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

[2] Abramowitz, Milton [in 英語]; Stegun, Irene Ann [in 英語], eds. (1983) [June 1964]. "Chapter 3, eqn 3.6.27". Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. Applied Mathematics Series. Vol. 55 (Ninth reprint with additional corrections of tenth original printing with corrections (December 1972); first ed.). Washington D.C.; New York: United States Department of Commerce, National Bureau of Standards; Dover Publications. p. 16. ISBN 978-0-486-61272-0. LCCN 64-60036. MR 0167642. LCCN 65-12253。

[history-3] 長田直樹「収束の加速法の歴史 : 17世紀ヨーロッパと日本の加速法 (数学史の研究)」『数理解析研究所講究録』第1787巻、京都大学数理解析研究所、2012年4月、88-104頁、CRID 1050282810743934208、hdl:2433/172780、ISSN 1880-2818。

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

[5] Henri Cohen, Fernando Rodriguez Villegas, and Don Zagier, "Convergence Acceleration of Alternating Series", Experimental Mathematics, 9:1 (2000) page 3.

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

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

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

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

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

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

[12] William H. Press, et al., Numerical Recipes in C, (1987) Cambridge University Press, ISBN 0-521-43108-5（5.1節を参照）

[13] 牧之内三郎、鳥居達生：「数値解析」（3.2.4:'Steffensen法')、オーム社、ISBN 978-4-274020117 (1975年10月25日）

[14] Romberg, W. (1955). Vereinfachte numerische integration. Norske Vid. Selsk. Forh., 28, 30-36, NAID 10004043042.

[15] F. L. Bauer, H. Rutishauser and E. Stiefel, New aspects in numerical quadrature, Proc. Symp. Appl. Math. (AMS, 1963), vol. 15, p. 198–218.

[16] 大石進一 et al.(2018) 精度保証付き数値計算の基礎, コロナ社.

[sp-17] 森正武「解析接続と級数の収束の加速 (解析接続の応用)」『数理解析研究所講究録』第1155巻、京都大学数理解析研究所、2000年5月、104-119頁、CRID 1050282676913607168、hdl:2433/64145、ISSN 1880-2818、NAID 110000164534。

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

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

[16]

[17]

[18]

[19]

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

定義

歴史