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

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

概要

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

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

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

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

加速される理由

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

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

したがって、 テンプレート:Mvar は テンプレート:Math の不動点 (テンプレート:Lang) である。テンプレート:Mvar を求めることは、方程式 テンプレート:Math の解を求めることと等価であり、図形的には、直線 テンプレート:Math と曲線 テンプレート:Math の交点を求めることに等しい。ここで図を参照すると、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})$ を通る直線 テンプレート:Mvar の方程式は、

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

で与えられる。 テンプレート:Mvar と直線 テンプレート:Math との交点を テンプレート:Math とすると、テンプレート:Mvar の方程式に テンプレート:Math を代入して、

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

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

注意点

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

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

歴史

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

参考文献

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