数値解析 における数列の加速法 (英 : Series acceleration ) とは、収束の遅い数列 を収束の速い数列 に変換するアルゴリズム の総称である[ 1]
級数加速の技法は、例えば特殊関数 の様々な恒等式を得るためにも使われる。 例えばオイラー変換 を超幾何級数 に適用すると、古典的でよく知られた超幾何級数の恒等式のいくつかが得られる。
与えられた数列
S
=
{
s
n
}
n
∈
N
{\displaystyle S=\{s_{n}\}_{n\in \mathbb {N} }}
が極限
lim
n
→
∞
s
n
=
ℓ
,
{\displaystyle \lim _{n\to \infty }s_{n}=\ell ,}
を持つとする。
ここで別の数列
S
′
=
{
s
n
′
}
n
∈
N
{\displaystyle S'=\{s'_{n}\}_{n\in \mathbb {N} }}
が加速された数列であるとは、元の数列より
ℓ
{\displaystyle \ell }
速く収束する 、すなわち
lim
n
→
∞
s
n
′
−
ℓ
s
n
−
ℓ
=
0
{\displaystyle \lim _{n\to \infty }{\frac {s'_{n}-\ell }{s_{n}-\ell }}=0}
が成り立つ事と定める。
もし元の数列が発散数列の場合、数列の変換はen:antilimit への 補外法 となる。
数列の変換は非線形なものほど強力である傾向がある。
ヨーロッパと日本で研究が始まった。古典的な二つの加速法はオイラー変換 [ 2] クンマー変換 である。日本では関孝和 、建部賢弘 など、ヨーロッパではアイザック・ニュートン などが取り組んだ[ 3]
エイトケンのΔ2乗加速法 (但し、初出は関孝和 による)[ 1] [ 3]
ϵ
{\displaystyle \epsilon }
[ 4] リチャードソンの補外 （建部賢弘 が1722に考案したのが初出）など、様々な加速法が作られる。なお、現代において
ϵ
{\displaystyle \epsilon }
Mathematica のNSum、NLimitに組み込まれている[ 4]
1956年にピーター・ウィン によって提案されたepsilon method 、レヴィンのu-変換、そしてWilf-Zeilberger-Ekhad法またはWZ法 が挙げられます。
交互級数 に対しては、Cohen et al .によって記述された強力な手法がいくつかあり、それらは
5.828
−
n
{\displaystyle 5.828^{-n}}
17.93
−
n
{\displaystyle 17.93^{-n}}
n
{\displaystyle n}
[ 5]
加速法と可積分系 ・離散ソリトン 方程式の関係が明らかになり、可積分系 ・離散ソリトン 方程式から加速法を作る試みが始まった[ 6] [ 7] [ 8] [ 9] q-類似 を構成する試みもなされている[ 10] [ 11]
基本的な線形数列変換 の例として、収束性を改善するオイラー変換があります。これは交代級数（隣り合う項の符号が反転する実数の級数）に適用され、次のように与えられます。
∑
n
=
0
∞
(
−
1
)
n
a
n
=
∑
n
=
0
∞
(
−
1
)
n
(
Δ
n
a
)
0
2
n
+
1
{\displaystyle \sum _{n=0}^{\infty }(-1)^{n}a_{n}=\sum _{n=0}^{\infty }(-1)^{n}{\frac {(\Delta ^{n}a)_{0}}{2^{n+1}}}}
ここで、
Δ
{\displaystyle \Delta }
前進差分演算子 であり、その公式は以下の通りです。
(
Δ
n
a
)
0
=
∑
k
=
0
n
(
−
1
)
k
(
n
k
)
a
n
−
k
.
{\displaystyle (\Delta ^{n}a)_{0}=\sum _{k=0}^{n}(-1)^{k}{n \choose k}a_{n-k}.}
元の級数（左辺）が収束が遅い場合、前進差分の大きさは急速に減少し、さらに2の負冪が乗じられることにより、右辺の級数の収束速度がさらに改善されます。
オイラー変換の特に効率的な数値実装はファン・ウィンガーデン変換 [ 12]
ある級数
S
=
∑
n
=
0
∞
a
n
{\displaystyle S=\sum _{n=0}^{\infty }a_{n}}
は、関数f を
f
(
z
)
=
∑
n
=
0
∞
a
n
z
n
{\displaystyle f(z)=\sum _{n=0}^{\infty }a_{n}z^{n}}
と定義すると、
f
(
1
)
{\displaystyle f(1)}
f
(
z
)
{\displaystyle f(z)}
複素平面 内に特異点 （分岐点 特異点、極 または真性特異点 ）を持ち、これが級数の収束半径 を制限します。
z
=
1
{\displaystyle z=1}
S
{\displaystyle S}
z
=
1
{\displaystyle z=1}
共形変換
z
=
Φ
(
w
)
{\displaystyle z=\Phi (w)}
Φ
(
0
)
=
0
{\displaystyle \Phi (0)=0}
w = 0で有限の微分 を持つ関数を選びます。一般性を失うことなく
Φ
(
1
)
=
1
{\displaystyle \Phi (1)=1}
w を再スケールして
Φ
{\displaystyle \Phi }
g
(
w
)
=
f
(
Φ
(
w
)
)
.
{\displaystyle g(w)=f(\Phi (w)).}
Φ
(
1
)
=
1
{\displaystyle \Phi (1)=1}
f
(
1
)
=
g
(
1
)
{\displaystyle f(1)=g(1)}
Φ
(
0
)
=
0
{\displaystyle \Phi (0)=0}
f
(
z
)
{\displaystyle f(z)}
z
=
Φ
(
w
)
{\displaystyle z=\Phi (w)}
g
(
w
)
{\displaystyle g(w)}
Φ
′
(
0
)
≠
0
{\displaystyle \Phi '(0)\neq 0}
f
(
z
)
{\displaystyle f(z)}
n
{\displaystyle n}
g
(
w
)
{\displaystyle g(w)}
n
{\displaystyle n}
w
=
1
{\displaystyle w=1}
非線形数列変換の例として、パデ近似 、シャンクス変換 、およびレヴィン型数列変換 があります。
特に非線形数列変換は、摂動論 などで生じる発散級数 や漸近級数 の総和法 に強力な数値手法を提供し、非常に効果的な外挿法 として使用できます。
これはエイトケンのΔ2乗加速法 の応用で、方程式
x
=
g
(
x
)
{\displaystyle x=g(x)}
[ 1]
g
(
x
)
{\displaystyle g(x)}
C
1
{\displaystyle C^{1}}
C
2
{\displaystyle C^{2}}
[ 1]
x
:=
g
(
x
)
{\displaystyle x:=g(x)}
p
{\displaystyle p}
p
≥
2
{\displaystyle p\geq 2}
x
:=
G
(
x
)
≡
{
x
g
(
g
(
x
)
)
−
(
g
(
x
)
)
2
}
/
{
x
−
2
g
(
x
)
+
g
(
g
(
x
)
)
}
{\displaystyle x:=G(x)\equiv \{xg(g(x))-(g(x))^{2}\}/\{x-2g(x)+g(g(x))\}}
2
p
−
1
{\displaystyle 2p-1}
p
=
1
{\displaystyle p=1}
x
=
g
(
x
)
{\displaystyle x=g(x)}
p
=
1
{\displaystyle p=1}
[ 13]
これは台形公式 と加速法を組み合わせた数値積分 法である[ 1] [ 14] [ 15] 精度保証付き数値計算 にも使われている[ 16]
べき級数で定義された複素関数 のある点に於ける値を求めるのに、元のべき級数の展開中心の位置を解析接続 により移動させることでより収束率の高いべき級数の和に置き換えて計算ができたなら，それは元の級数の和に対する一種の加速法であると見なしうる[ 17] 誤差関数 などの特殊関数 への計算に応用が可能である[ 17]
常微分方程式の数値解法 ・偏微分方程式の数値解法 においても収束の加速法が研究されており、有限要素法 [ 18] 差分法 の一つ)[ 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 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
{\displaystyle q}
ϵ
{\displaystyle \epsilon }
^ 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-274-02011-7 (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-4-254-11362-4 。 Delahaye, J. P. (1988). Sequence Transformations . Springer-Verlag. ISBN 978-3-54015283-5 Brezinski, C.; Redivo-Zaglia, M. (1991). Extrapolation Methods. Theory and Practice . North-Holland. ISBN 0-444-88814-4 Naoki Osada: "A Convergence Acceleration Method for Some Logarithmically Convergent Sequences", SIAM J. Numer. Anal., Vol.27, No.1, pp.178-189 (Feb., 1990).
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-4-00-005518-5 。 長田直樹「収束の加速法（数値計算アルゴリズムの現状と展望） 」『数理解析研究所講究録』第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 .
