収束する数列の極限の近似を加速したい

収束する数列の極限値の近似計算を加速する方法についての紹介です.

詳しくはWikipedaにて紹介されていますので、ここでは簡単にとどめます. Aitkenの加速法を用いると元の式を別の式に変換することになります.これを数列変換(Sequence Transformation)と言います.この変換によってもっと収束の早い数列になります. Wikipediaで解説されている加速の理由に関して簡単に触っておきます. s_(n+1) = g(s_n) のように関数gを通して数列はある値に収束していくことになります. 収束直前では、ほぼ収束しているはずなので入力と出力が等しくなってきているはずで、s = g(s)のような形になるということが分かります. それを連続値xを使って図示すると、y=xとy=g(x)の交点を求めることと同様なことになっていることがわかるとwikipediaでは解説しています.

Richardson加速はAitkenの加速のベースとなっている技術です. Richardson加速は x_(n+1) - a = γ(x_n - a) のように記述できる数列においてこれを収束値aについて整理したものを新しい数列としたものです. a ≒ y_n = (x_(n+1) - γx_n) / (1- γ) 数列が進むにつれて段々と近似値に近づくのがわかると思います.

Richardson加速では指揮中にγを使用しているため、この収束値があらかじめわかっていけません.

$$ \gamma \fallingdotseq \frac{x_{n+2} - x_{n+1}}{x_{n+1} - x_{n}} $$

Aitken加速はRichardson加速で必要だったγもxの数列で置き換えたものです. γの収束率も知らなくても近似値を求めることができます. 左記のRichardson加速の最後の式に上記のγの式を入れると新しい数列を得ることができます.この数列を変わりに計算することで、数列の極限値の近似を加速させることができます.

$$y_n = x_n - \frac{(x_{n+1}-x_n)^2}{x_{n+2} - 2x_{n+1}+x_n}$$ $$y_n = x_n - \frac{(\Delta x_n)^2}{\Delta^2x_n}$$

Aitken加速の特徴として、 オイラー級数のような一見収束しそうな数列に対しても適用可能です.オイラー級数に当てはめたときは、収束しそうに見えるところの解を求めます. Aitken加速で得られた数式にもう一度Aitken加速を適用することができる. それによってさらに精度のよい値を高速に求めることが可能.