Aitken加速

Aitken加速を書いてみた。
短いのでコードはここに掲載

module Aitken where

a n = foldl (+) 0.take n $ map term [0..n]
term k = (-1)^k/(2*fromIntegral k+1)

--収束率
--lambda n = (a (n+2) - a (n+1)) / (a (n+1) - a n)

--極限値
aitken n = a n - (a (n+1) - a n)^2/(a (n+2)-2*a (n+1)+a n)

a n で表される数列はpi/4に収束するはずです。
確かめてみた。

実行結果

> pi/4
0.7853981633974483
> a 1000
0.7851481634599485
> a 5000
0.7853481633979478
> a 10000
0.7853731633975086
> aitken 20
0.785391433664637

となり、小数点第5位までの制度を得ようと思うと、普通に数列計算すると1000回程度かかりますが、Aitken法では第20項までの計算で収束しています。Aitken内では5回 数列の値を計算しているのでこの場合は約100回程度、実に100倍の速度で収束！
すごい！