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

概要

|a_(n+1) - a| < λ | a_n - a|となるような数列等を対象に数列の極限を計算するにあたって近似値計算を加速する方法についてまとめます.基本的なRichardson加速とそれを改善したAitkin加速について紹介します.
Facebookシェア Twitterツイート LINEで送る このエントリーをはてなブックマークに追加
この章を学ぶ前に必要な知識
0
条件
  • 収束する数列(収束しない数列でも解は出る)
  • Richardson加速は収束率が分かっていること前提
  • Aitken加速は特に数列がゆっくりと収束すること以外特に条件なし.
効果
  • 極限の近似値を高速に求める
ポイント
  • 元々の数式を別の数式に変換(数列変換,sequence transformation)を行う
  • Aitkenは値がばたつくが収束するものや複数の混合した数列でも適用可能

解 説

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

1.Richardson加速

Richardson加速はAitkenの加速のベースとなっている技術です. Richardson加速は x_(n+1) - a = γ(x_n - a) のように記述できる数列においてこれを収束値aについて整理したものを新しい数列としたものです. a ≒ y_n = (x_(n+1) - γx_n) / (1- γ) 数列が進むにつれて段々と近似値に近づくのがわかると思います.
Richardson法による近似計算の加速
Richardson加速では指揮中にγを使用しているため、この収束値があらかじめわかっていけません.
Richardson加速の特徴

2.Aitken加速

$$ \gamma \fallingdotseq \frac{x_{n+2} - x_{n+1}}{x_{n+1} - x_{n}} $$
比例しているのであれば左の式が成立するはず
Aitken加速はRichardson加速で必要だったγもxの数列で置き換えたものです. γの収束率も知らなくても近似値を求めることができます. 左記のRichardson加速の最後の式に上記のγの式を入れると新しい数列を得ることができます.この数列を変わりに計算することで、数列の極限値の近似を加速させることができます.
Aitken加速概要
$$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加速の新しい数式y_n
Aitken加速の特徴として、 オイラー級数のような一見収束しそうな数列に対しても適用可能です.オイラー級数に当てはめたときは、収束しそうに見えるところの解を求めます. Aitken加速で得られた数式にもう一度Aitken加速を適用することができる. それによってさらに精度のよい値を高速に求めることが可能.
Aitken加速の特徴
この章を学んで新たに学べる
Comments

Reasons
>>隠す