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

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

概要

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

[math]t_n := s_n - \frac{(s_{n+1} - s_n)^2}{s_{n+2} - 2 s_{n+1} + s_n}.[/math]

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

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

加速される理由

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

[math]s_{n+1} = g(s_n)\longrightarrow \alpha,\quad(n\longrightarrow +\infty),[/math]

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

[math]y - s_{n+2}= \frac{s_{n+1} - s_{n+2}}{s_{n} - s_{n+1}}(x - s_{n+1}),[/math]

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

[math]\;x_0=s_n - \frac{(s_{n+1} - s_n)^2}{s_{n+2} - 2 s_{n+1} + s_n},\;[/math]

を得る。図では、交点 Q は P_n+2 よりも不動点 F := (α, α) に近づいている。これがエイトケンの Δ² 加速法の定義式の理由である。

注意点

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

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

歴史

現時点に於いて判明しているところによると、エイトケンの Δ² 加速法は和算家の関孝和によって1681年頃に導出されたのが世界で最初である。関孝和は暦の作成で必要になった円周率の近似計算でこの加速法を用いて、小数点以下第16位までを正確に求めた。関孝和の業績は日本でも長らく忘却されていたが、フランス人Brezinski 1991に指摘されて再発見された。西洋に於いてエイトケンの Δ² 加速法が導出されたのは、それから約200年後の1876年であり、H. von. Nägelsbach 1876による。エイトケンの Δ² 加速法という名前で今日呼ばれるようになったのはさらに後の、アレクサンダー・エイトケンの論文{{#invoke:Footnotes | harvard_citation }}にちなむ。

参考文献

• H. von. Nägelsbach (1876). Arch. Math. Phys. 59.: 147-192. 
• Aitken, A. C. (1926). “On Bernoulli's numerical solution of algebraic equations”. Proc. Royal. Soc. (Edinburgh) 46: 289-305. 
• Breziski, Claude (1991). History of continued fractions and Padé approximants. Berlin: Springr Verlag. OCLC 21411454. 
• 「第6章 離散可積分系と数列の加速法」『可積分系の応用数理』 中村佳正・編、裳華房、2000年。ISBN 4-7853-1520-2。