数列の加速法

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

歴史

19世紀以前
ヨーロッパと日本で研究が始まった。日本では関孝和、建部賢弘など、ヨーロッパではアイザック・ニュートンなどが取り組んだ。

20世紀前半
エイトケンのΔ2乗加速法(但し、初出は関孝和の論文)、-算法など、様々な加速法が作られる。なお、現代において-算法はMathematicaのNSum、NLimitに組み込まれている。

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

応用

Steffensen 反復
これはエイトケンのΔ2乗加速法の応用で、方程式の解を求めるための反復法である。初期値を十分近くとれば1次収束する ( が 級なら超１次収束,  級なら2次収束する)。

Romberg 積分

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

特殊関数
加速法によって複素関数をより広い領域で計算可能になるので、一種の解析接続と見なすことも可能である。加速法は誤差関数などの特殊関数への計算に応用可能である。

類似概念

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

出典

参考文献
 
 
 
 
 
 
 
 
 
 
 （-算法の開発者であるWynnの研究業績をまとめた文献）
 
 
 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
 離散ソリトン方程式の数理工学への応用
 長田直樹:「収束の加速法」、数理解析研究所講究録、第880巻、1994年、頁28-43

数列
収束
数値解析
計算科学
応用数学
アルゴリズム
数学に関する記事