数列の加速法

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

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

定義

与えられた数列

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

が極限

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

を持つとする。

ここで別の数列

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

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

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

が成り立つ事と定める。

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

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

歴史

19世紀以前

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

20世紀前半

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

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

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

1990年代以降

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

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

オイラー変換

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

${\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 }$は前進差分演算子であり、その公式は以下の通りです。

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

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

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

共形変換

ある級数

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

は、関数fを

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

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

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

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

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

非線形数列変換

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

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

応用

Steffensen 反復

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

Romberg 積分

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

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

特殊関数

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

類似概念

→「超収束」も参照

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