エイトケンのΔ2乗加速法

エイトケンのΔ2乗加速法（エイトケンのデルタじじょうかそくほう、Aitken's $\;\Delta^2\;$ process）とは、少ない計算量で数列の収束を速めるためのアルゴリズムの一つである。

概要

数列$\;s_n\;$がある極限値に収束するとき、以下の定義によって新たな数列$\;t_n\;$を作ると、後者の収束の速さが大きく加速されることがある。

$t_n := s_n - \frac{(s_{n+1} - s_n)^2}{s_{n+2} - 2 s_{n+1} + s_n}$

この新たな数列$\;t_n\;$によって、極限値の近似値の精度を上げる 方法をエイトケンの$\;\Delta^2\;$加速法と呼ぶ。

加速される理由

以下に見るように、エイトケンの$\;\Delta^2\;$加速法は一種のはさみうち法である。今、$\;s_{n+1}\;$は$\;s_n\;$によって決まり、数列はある極限値$\;\alpha\;$へ収束すると仮定する。

$s_{n+1} = g(s_n)\longrightarrow \alpha,\quad(n\longrightarrow +\infty),$

したがって、$\;\alpha\;$は$\;g(x)\;$の不動点(fixed point)である。$\;\alpha\;$を求めることは、方程式$\;x=g(x)\;$の解を求めることと等価であり、図形的には、直線$\;y=x\;$と曲線$\;y=g(x)\;$の交点を求めることに等しい。ここで図を参照すると、2点$\;P_n:=(s_n, g(s_n)) = (s_n, s_{n+1})\;$、$\;P_{n+1}:=(s_{n+1}, g(s_{n+1}))=(s_{n+1}, s_{n+2})\;$を通る直線$\;L\;$の方程式は、

$y - s_{n+2}= \frac{s_{n+1} - s_{n+2}}{s_{n} - s_{n+1}}(x - s_{n+1}),$

で与えられる。$\;L\;$と直線$\;y=x\;$との交点を$\;Q=(x_0,x_0)\;$とすると、$\;L\;$の方程式に$\;y=x=x_0\;$を代入して、

$\;x_0=s_n - \frac{(s_{n+1} - s_n)^2}{s_{n+2} - 2 s_{n+1} + s_n},\;$

を得る。図では、交点$\;Q\;$は$\;P_{n+2}\;$よりも不動点$\;F:=(\alpha,\alpha)\;$に近づいている。これがエイトケンの$\;\Delta^2\;$加速法の定義式の理由である。

注意点

加速されるのは、出発点となる点が収束値に十分近いときのことであり、収束値から遠い場合、極限値に達するまで長い時間がかかる、または収束しないということは起こりうる。また、本来収束しない数列にエイトケンの$\;\Delta^2\;$加速法を適用すると、あたかも極限値に向かって収束するように見えることがある。エイトケンの$\;\Delta^2\;$加速法によって数列の極限値を加速度的に求められるか否かは、元の数列の性質に依存する。対数収束のような収束の遅い数列に対しては別の加速法を用いないとほとんど効果がない。

エイトケンの$\;\Delta^2\;$加速法は、上の説明からわかるように方程式$\;x=g(x)\;$の数値計算にも応用可能である。事実、エイトケンは代数方程式の近似計算にこの方法を適用した。

歴史

現在わかっているところでは、エイトケンの$\;\Delta^2\;$加速法が世界で最初に開発されたのは1681年頃のことで、和算家の関孝和によってである。関孝和は暦の作成で必要になった円周率の近似計算でこの加速法を用い、小数点以下16位まで正確に求めている。関孝和の業績は日本でも久しく忘れられていたが、フランス人C.Brezinskiに指摘されてこの事実がわかった。西洋でエイトケンの$\;\Delta^2\;$加速法が再発見されるのは、それから約200年後の1876年のことで、H.von.Nägelsbachによってである。エイトケンの$\;\Delta^2\;$加速法という名前が通用するようになるのは、エイトケンの論文で用いられて以降である。