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

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

概要 数列 がある極限値に収束するとき、以下の定義によって新たな数列 を作ると、後者の収束が極めて良くなることがある（状況によっては速くならない場合もある）。

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

right|420x350px|エイトケンの2乗加速法の定義式の説明用グラフ

加速される理由 以下に見るように、エイトケンの 加速法は一種のはさみうち法である。今、 は によって決まり、数列はある極限値 へ収束すると仮定する。

したがって、 は の不動点 () である。 を求めることは、方程式 の解を求めることと等価であり、図形的には、直線 と曲線 の交点を求めることに等しい。ここで図を参照すると、2点 を通る直線 の方程式は、

で与えられる。 と直線 との交点を とすると、 の方程式に を代入して、

を得る。図では、交点 は よりも不動点 に近づいている。これがエイトケンの 加速法の定義式の理由である。

注意点 収束を加速できるのは、出発値が収束値に十分近いときであり、離れているときは多くのステップを要する、または収束しないことも起こりうる。また、本来は収束しない数列に対してエイトケンの 加速法を適用した場合は、あたかも極限値が存在してそれに収束するように振る舞うことがある。エイトケンの 加速法により数列の極限値への収束を加速できるか否かは、元の数列の性質に依存する。対数収束のような収束が遅い数列に対しては殆ど効果が無いので別の加速法が必要である。

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

歴史 現時点に於いて判明しているところによると、エイトケンの 加速法は和算家の関孝和によって1681年頃に導出されたのが世界で最初である。関孝和は暦の作成で必要になった円周率の近似計算でこの加速法を用いて、小数点以下第16位までを正確に求めたただし関が最終的に円周率の近似値として採用した値は「3.14159265359 微弱」である。。関孝和の業績は日本でも長らく忘却されていたが、フランス人に指摘されて再発見された。西洋に於いてエイトケンの 加速法が導出されたのは、それから約200年後の1876年であり、による。エイトケンの 加速法という名前で今日呼ばれるようになったのはさらに後の、の論文にちなむ。

参考文献

室田一雄、杉原正顕：「Aitken 加速に関する一つの注意」、情報処理学会論文誌、Vol.25, No.5, pp.892-894 (1984).

脚注