数列の加速法

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

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

定義

与えられた数列

$S=\{s_n{\}}_{n\in \mathbb{N}}$

が極限

$\underset{n\to \mathrm{\infty }}{\lim }{s}_n=\ell ,$

を持つとする。

ここで別の数列

$S^{\prime }=\{s{\text{'}}_n{\}}_{n\in \mathbb{N}}$

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

$\underset{n\to \mathrm{\infty }}{\lim }\frac{s{\text{'}}_n-\ell }{s_n-\ell }=0$

が成り立つ事と定める。

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

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

歴史

19世紀以前

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

20世紀前半

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

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

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

1990年代以降

加速法と可積分系・離散ソリトン方程式の関係が明らかになり、可積分系・離散ソリトン方程式から加速法を作る試みが始まった。加速法のq-類似を構成する試みもなされている。 テンプレート:Seealso

オイラー変換

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

$\sum _{n=0}^{\mathrm{\infty }}(-1{)}^n{a}_n=\sum _{n=0}^{\mathrm{\infty }}(-1{)}^n\frac{({\mathrm{\Delta }}^{n}a{)}_0}{2^{n+1}}$

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

$({\mathrm{\Delta }}^{n}a{)}_0=\sum _{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})a_{n-k}.$

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

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

共形変換

ある級数

$S=\sum _{n=0}^{\mathrm{\infty }}{a}_n$

は、関数fを

$f(z)=\sum _{n=0}^{\mathrm{\infty }}{a}_n{z}^n$

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

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

$g(w)=f(\mathrm{\Phi }(w)).$

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

非線形数列変換

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

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

応用

Steffensen 反復

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

Romberg 積分

テンプレート:Main これは台形公式と加速法を組み合わせた数値積分法である。Bauer-Rutishauser-Stiefel (1963) により詳細な解析がなされている。現代では精度保証付き数値計算にも使われている。

特殊関数

べき級数で定義された複素関数のある点に於ける値を求めるのに、元のべき級数の展開中心の位置を解析接続により移動させることでより収束率の高いべき級数の和に置き換えて計算ができたなら，それは元の級数の和に対する一種の加速法であると見なしうる。このような加速法は誤差関数などの特殊関数への計算に応用が可能である。

類似概念

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

参考文献

• テンプレート:Cite book
• テンプレート:Cite book
• テンプレート:Cite book
• 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
• テンプレート:Cite book
• テンプレート:Cite journal
• テンプレート:Cite journal
• テンプレート:Cite journal
• テンプレート:Cite book
• テンプレート:Cite journal
• テンプレート:Cite journal（テンプレート:Mvar-算法の開発者であるWynnの研究業績をまとめた文献）
• テンプレート:Cite book
• テンプレート:Cite journal
• 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
• 離散ソリトン方程式の数理工学への応用