数列の加速法のソースを表示

[[数値解析]]における'''数列の加速法''' ({{lang-en-short|Series acceleration}}) とは、収束の遅い[[数列]]を収束の速い[[数列]]に変換する[[アルゴリズム]]の総称である<ref name="Yamamoto1">{{Cite book |和書 |author=山本哲朗 |title=数値解析入門 |edition=増訂版 |date=2003-06 |publisher=[[サイエンス社]] |series=サイエンスライブラリ 現代数学への入門 14 |ISBN=4-7819-1038-6}}</ref>。ただし，収束の極めて遅い対数収束列と呼ばれる数列全般に対して、収束を加速できるような単一のアルゴリズムは存在しないことが証明されている。なお、ベクトル列についても収束の加速法の研究がなされている。

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

==定義==
与えられた数列
:<math>S=\{ s_n \}_{n\in\N}</math>

が極限

:<math>\lim_{n\to\infty} s_n = \ell,</math>

を持つとする。

ここで別の数列

:<math>S'=\{ s'_n \}_{n\in\N}</math>

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

:<math>\lim_{n\to\infty} \frac{s'_n-\ell}{s_n-\ell} = 0</math>

が成り立つ事と定める。

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

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

==歴史==
===19世紀以前===
ヨーロッパと日本で研究が始まった。古典的な二つの加速法は[[:en:Euler's transformation of series|オイラー変換]]<ref>{{AS ref|3, eqn 3.6.27|16}}</ref> と [[:en:Kummer's transformation of series|クンマー変換]]である。日本では[[関孝和]]、[[建部賢弘]]など、ヨーロッパでは[[アイザック・ニュートン]]などが取り組んだ<ref name="history">{{Cite journal|和書|author=長田直樹 |date=2012-04 |url=https://hdl.handle.net/2433/172780 |title=収束の加速法の歴史 : 17世紀ヨーロッパと日本の加速法 (数学史の研究) |journal=数理解析研究所講究録 |ISSN=1880-2818 |publisher=京都大学数理解析研究所 |volume=1787 |pages=88-104 |hdl=2433/172780 |CRID=1050282810743934208}}</ref>。

===20世紀前半===
[[エイトケンのΔ2乗加速法]](但し、初出は[[関孝和]]による)<ref name="Yamamoto1"/><ref name="history"/>、<math>\epsilon</math>-算法<ref name="ep">Weisstein, Eric W. ”Wynn’s Epsilon Method.” From MathWorld–A Wolfram Web Resource. [http://mathworld.wolfram.com/WynnsEpsilonMethod.html Wynn's Epsilon Method -- from Wolfram MathWorld]</ref>や[[リチャードソンの補外]]（[[建部賢弘]]が1722に考案したのが初出）など、様々な加速法が作られる。なお、現代において<math>\epsilon</math>-算法は[[Mathematica]]のNSum、NLimitに組み込まれている<ref name="ep"/>。

1956年に[[ピーター・ウィン (数学者)|ピーター・ウィン]]によって提案された[http://mathworld.wolfram.com/WynnsEpsilonMethod.html epsilon method]、レヴィンのu-変換、そしてWilf-Zeilberger-Ekhad法または[[WZ理論|WZ法]]が挙げられます。

[[交互級数]]に対しては、Cohen ''et al''.によって記述された強力な手法がいくつかあり、それらは<math>5.828^{-n}</math>から<math>17.93^{-n}</math>までの収束速度を提供し、<math>n</math>項の総和に適用できます。<ref>[[Henri Cohen (number theorist)|Henri Cohen]], Fernando Rodriguez Villegas, and [[Don Zagier]],
"[http://people.mpim-bonn.mpg.de/zagier/files/exp-math-9/fulltext.pdf Convergence Acceleration of Alternating Series]", ''Experimental Mathematics'', '''9''':1 (2000) page 3.</ref>

===1990年代以降===
加速法と[[可積分系]]・離散[[ソリトン]]方程式の関係が明らかになり、[[可積分系]]・離散[[ソリトン]]方程式から加速法を作る試みが始まった<ref name="app">[[可積分系]]の応用数理、[[裳華房]]、中村佳正 et al.(2000)</ref><ref>{{Cite journal|和書|author=永井敦, [[薩摩順吉]] |date=1995 |title=加速法と離散型ソリトン方程式(非線形可積分系の応用数理) |url=https://hdl.handle.net/2433/59992 |journal=数理解析研究所講究録 |publisher=京都大学数理解析研究所 |issue=933 |pages=44-60 |naid=110004701995 |ISSN=1880-2818}}</ref><ref>Papageorgiou, Grammaticos and Ramani (1993). Integrable Lattices and Convergence Acceleration Algorithms, Phys. Lett. A 179, 111-115.</ref><ref>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.</ref>。加速法の[[q-類似]]を構成する試みもなされている<ref>He, Y., Hu, X. B., Tam, H. W. (2009). A <math>q</math>-Difference Version of the <math>\epsilon</math>-Algorithm. Journal of Physics A: Mathematical and Theoretical, 42(9), 095202.</ref><ref>{{cite journal |title=Q-difference and confluent forms of the lattice Boussinesq equation and the relevant convergence acceleration algorithms |author=Sun Jian-Qing, He Yi, Hu Xing-Biao, Tam Hon-Wah |journal=Journal of mathematical physics |volume=52 |issue=2 |pages=023522 |year=2011 |publisher=American Institute of Physics |url=https://doi.org/10.1063/1.3554693 |doi=10.1063/1.3554693}}</ref>。
{{seealso|可積分アルゴリズム}}

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

:<math>\sum_{n=0}^\infty (-1)^n a_n = \sum_{n=0}^\infty (-1)^n \frac{(\Delta^n a)_0}{2^{n+1}}</math>

ここで、<math>\Delta</math>は[[前進差分演算子]]であり、その公式は以下の通りです。

:<math>(\Delta^n a)_0 = \sum_{k=0}^n (-1)^k {n \choose k} a_{n-k}.</math>

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

オイラー変換の特に効率的な数値実装は[[ファン・ウィンガーデン変換]]<ref>William H. Press, ''et al.'', ''Numerical Recipes in C'', (1987) Cambridge University Press, {{isbn|0-521-43108-5}}（5.1節を参照）</ref>です。

== 共形変換 ==
ある級数

:<math>S = \sum_{n=0}^{\infty} a_n</math>

は、関数''f''を

:<math>f(z) = \sum_{n=0}^{\infty} a_n z^n</math>

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

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

:<math>g(w) = f(\Phi(w)).</math>

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

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

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


==応用==
===Steffensen 反復===
これは[[エイトケンのΔ2乗加速法]]の応用で、方程式<math>x=g(x)</math>の解を求めるための反復法である<ref name="Yamamoto1"/>。初期値を十分近くとれば1次収束する (<math>g(x)</math> が<math>C^1</math> 級なら超１次収束, <math>C^2</math> 級なら2次収束する<ref name="Yamamoto1"/>)。
反復法 <math>x:=g(x)</math>の収束次数が<math>p</math>のとき、<math>p \ge 2</math>ならばそれに対するSteffensen反復法<math>x:=G(x)\equiv\{xg(g(x))-(g(x))^2\}/\{x-2g(x)+g(g(x)) \}</math>の収束は<math>2p-1</math>次であり、<math>p=1</math>で収束先が<math>x=g(x)</math>の単根ならばSteffensen法は2次であり、<math>p=1</math>で収束先が重根の場合にはSteffensen法は1次になる<ref>牧之内三郎、鳥居達生：「数値解析」（3.2.4:'Steffensen法')、オーム社、ISBN 978-4-274-02011-7 (1975年10月25日）</ref>。

===Romberg 積分===
{{main|:en:Romberg integration}}
これは[[台形公式]]と加速法を組み合わせた[[数値積分]]法である<ref name="Yamamoto1"/><ref>Romberg, W. (1955). Vereinfachte numerische integration. Norske Vid. Selsk.
Forh., 28, 30-36, {{naid|10004043042}}.</ref>。Bauer-Rutishauser-Stiefel (1963) により詳細な解析がなされている<ref>F. L. Bauer, H. Rutishauser and E. Stiefel, New aspects in numerical quadrature, Proc. Symp. Appl. Math. ([[アメリカ数学会|AMS]], 1963), vol. 15, p. 198–218.</ref>。現代では[[精度保証付き数値計算]]にも使われている<ref>[[大石進一]] et al.(2018) [[精度保証付き数値計算]]の基礎, [[コロナ社 (出版社)|コロナ社]].</ref>。

===特殊関数===
べき級数で定義された[[複素関数]]のある点に於ける値を求めるのに、元のべき級数の展開中心の位置を[[解析接続]]により移動させることでより収束率の高いべき級数の和に置き換えて計算ができたなら，それは元の級数の和に対する一種の加速法であると見なしうる<ref name="sp">{{Cite journal|和書|author=[[森正武]] |date=2000-05 |url=https://hdl.handle.net/2433/64145 |title=解析接続と級数の収束の加速 (解析接続の応用) |journal=数理解析研究所講究録 |ISSN=1880-2818 |publisher=京都大学数理解析研究所 |volume=1155 |pages=104-119 |hdl=2433/64145 |naid=110000164534 |CRID=1050282676913607168}}</ref>。このような加速法は[[誤差関数]]などの[[特殊関数]]への計算に応用が可能である<ref name="sp"/>。

==類似概念==
{{seealso|超収束}}
[[常微分方程式の数値解法]]・[[偏微分方程式の数値解法]]においても収束の加速法が研究されており、[[有限要素法]]<ref>Kříek, M. (1994). "[https://doi.org/10.1016/S0045-7825(94)80019-7 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}}.</ref>やShortley-Weller近似 ([[差分法]]の一つ)<ref>Matsunaga, N., & Yamamoto, T. (2000). "[https://doi.org/10.1016/S0377-0427(99)00321-0 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}}.</ref>などを加速できることが分かっている。

==出典==
{{脚注ヘルプ}}
{{reflist}}

==参考文献==
* {{cite book|和書
 |author=伊理正夫
 |title=数値計算
 |publisher=朝倉書店
 |isbn=978-4-254-11362-4
 |year=1981
 |chapter=1.6 エイトケン加速とステフェンセン変換、1.7 ε算法
 |ref=harv
}}
* {{cite book
 |first=J. P.
 |last=Delahaye
 |title=Sequence Transformations
 |publisher=Springer-Verlag
 |isbn=978-3-54015283-5
 |year=1988
 |ref=harv
}}
* {{cite book
 |first1=C.
 |last1=Brezinski
 |first2=M.
 |last2=Redivo-Zaglia
 |title=Extrapolation Methods. Theory and Practice
 |publisher=North-Holland
 |isbn=0-444-88814-4
 |year=1991
 |ref=harv
}}
* Naoki Osada: "A Convergence Acceleration Method for Some Logarithmically Convergent Sequences", SIAM J. Numer. Anal., Vol.27, No.1, pp.178-189 (Feb., 1990).
* {{cite thesis|和書
 |url=http://www.cis.twcu.ac.jp/~osada/thesis_osada.pdf
 |first=Naoki
 |last=Osada
 |title=Acceleration Methods for Slowly Convergent Sequences and their Applications
 |date=1993-01-01
 |degree=博士（工学）
 |number=乙第4391号
 |publisher=名古屋大学
 |doi=10.11501/3068987
 }}
* {{cite book|和書
 |author1=杉原正顕
 |author2=室田一雄
 |title=数値計算法の数理
 |publisher=岩波書店
 |isbn=978-4-00-005518-5
 |year=1994
 |chapter=第12章 加速
 |ref=harv
}}
* {{cite journal|和書
 |author=長田直樹
 |date=1994
 |title=収束の加速法（数値計算アルゴリズムの現状と展望）
 |url=https://hdl.handle.net/2433/84207 
 |journal=数理解析研究所講究録
 |publisher=京都大学数理解析研究所 
 |issue=880
 |pages=28-43
 |naid=110004757389
 |CRID=1050282810580235648
 |issn=1880-2818
 |ref=harv
}}
* {{cite journal|和書
 |author1=近藤弘一
 |author2=中村佳正
 |date=1998
 |title=高次収束するSteffensen型反復解法（数値計算アルゴリズムの研究）
 |url=https://hdl.handle.net/2433/62016 
 |journal=数理解析研究所講究録
 |publisher=京都大学数理解析研究所
 |issue=1040
 |pages=228-236
 |naid=110002339362
 |issn=1880-2818
 |CRID=1050282677086372480
 |ref=harv
}}
* {{cite journal
 |last1=Brezinski
 |first1=Claude
 |last2=Redivo-Zaglia
 |first2=Michela
 |title=The genesis and early developments of Aitken's process, Shanks transformation, the {{mvar|&epsilon;}}-algorithm, and related fixed point methods
 |doi=10.1007/s11075-018-0567-2
 |journal=Numerical Algorithms
 |volume=80
 |issue=1
 |year=2019
 |pages=11-133
 |ref=harv
}}
* {{cite book
 |last=Sidi
 |first=Avram
 |title=Vector Extrapolation Methods with Applications
 |publisher=SIAM
 |isbn=978-1-61197-495-9
 |year=2017
 |ref=harv
}}
* {{cite journal
 |last1=Brezinski
 |first1=Claude
 |last2=Redivo-Zaglia
 |first2=Michela
 |last3=Saad
 |first3=Yousef
 |title=Shanks Sequence Transformations and Anderson Acceleration
 |journal=SIAM Review
 |publisher=SIAM
 |volume=60
 |issue=3
 |year=2018
 |pages=646–669
 |doi=10.1137/17M1120725
 |ref=harv
}}
* {{cite journal
 |last=Brezinski
 |first=Claude
 |title=Reminiscences of Peter Wynn
 |journal=Numerical Algorithms
 |volume=80
 |year=2019
 |pages=5-10
 |doi=10.1007/s11075-018-0542-y
 |ref=harv
}}（{{mvar|&epsilon;}}-算法の開発者であるWynnの研究業績をまとめた文献）
* {{cite book
 |last=Brezinski
 |first=Claude
 |last2=Redivo-Zaglia
 |first2=Michela
 |title=Extrapolation and Rational Approximation
 |publisher=Springer
 |isbn=978-3-030-58417-7
 |year=2020
 |ref=harv
}}
* {{cite journal
 |first=Rafael Tristão
 |last=Pepino
 |title=Acceleration of sequences with transformations involving hypergeometric functions
 |journal=Numerical Algorithms
 |volume=92
 |year=2023
 |pages=893-915
 |doi=10.1007/s11075-022-01334-7
 |ref=harv
}}
* 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]]
* [[解析接続]]

==外部リンク==
* [http://numbers.computation.free.fr/Constants/Miscellaneous/seriesacceleration.html Convergence acceleration of series]
* [http://mathworld.wolfram.com/ConvergenceImprovement.html Convergence Improvement], Wolfram [[MathWorld]]
* [https://kaken.nii.ac.jp/ja/grant/KAKENHI-PROJECT-11740063/ 離散ソリトン方程式の数理工学への応用]

{{級数}}
{{calculus topics}}
{{applied-math-stub}}

{{デフォルトソート:すうれつのかそくほう}}
[[Category:数列]]
[[Category:収束]]
[[Category:数値解析]]
[[Category:計算科学]]
[[Category:応用数学]]
[[Category:アルゴリズム]]
[[Category:数学に関する記事]]