エイトケンのΔ2乗加速法のソースを表示

{{記事名の制約|title=エイトケンのΔ<sup>2</sup>加速法}}
'''エイトケンのΔ2乗加速法'''（エイトケンのデルタじじょうかそくほう、{{lang|en|Aitken's &Delta;{{sup|2}} process}}）とは、少ない計算量で[[数列]]の[[収束]]を速めるための[[アルゴリズム]]の一つである。

== 概要 ==
数列 {{mvar|s{{sub|n}}}} がある[[極限値]]に[[収束]]するとき、以下の定義によって新たな数列 {{mvar|t{{sub|n}}}} を作ると、後者の収束が極めて良くなることがある（状況によっては速くならない場合もある）。
:<math>t_n := s_n - \frac{(s_{n+1} - s_n)^2}{s_{n+2} - 2 s_{n+1} + s_n}.</math>
この新たな数列 {{mvar|t{{sub|n}}}} によって、極限値の[[近似値]]の精度を上げる方法をエイトケンの {{math|&Delta;{{sup|2}}}} 加速法と呼ぶ。

[[ファイル:aitken_graph_explanation.svg|right|420x350px|エイトケンの2乗加速法の定義式の説明用グラフ]]

== 加速される理由 ==
以下に見るように、エイトケンの {{math|&Delta;{{sup|2}}}} 加速法は一種の[[はさみうちの原理|はさみうち法]]である。今、{{mvar|s{{sub|n+1}}}} は {{mvar|s{{sub|n}}}} によって決まり、数列はある極限値 {{mvar|&alpha;}} へ収束すると仮定する。
:<math>s_{n+1} = g(s_n)\longrightarrow \alpha,\quad(n\longrightarrow +\infty),</math>
したがって、 {{mvar|&alpha;}} は {{math|''g''(''x'')}} の不動点 ({{lang|en|fixed point}}) である。{{mvar|&alpha;}} を求めることは、方程式 {{math|1=''x'' = ''g''(''x'')}} の解を求めることと等価であり、図形的には、直線 {{math|1=''y'' = ''x''}} と曲線 {{math|1=''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> を通る直線 {{mvar|L}} の方程式は、
:<math>y - s_{n+2}= \frac{s_{n+1} - s_{n+2}}{s_{n} - s_{n+1}}(x - s_{n+1}),</math>
で与えられる。 {{mvar|L}} と直線 {{math|1=''y'' = ''x''}} との交点を {{math|1=''Q'' = (''x''{{sub|0}}, ''x''{{sub|0}})}} とすると、{{mvar|L}} の方程式に {{math|1=''y'' = ''x'' = ''x''{{sub|0}}}} を代入して、
:<math>\;x_0=s_n - \frac{(s_{n+1} - s_n)^2}{s_{n+2} - 2 s_{n+1} + s_n},\;</math>
を得る。図では、交点 {{mvar|Q}} は {{math|''P''{{sub|''n''+2}}}} よりも不動点 {{math|1=''F'' := (''&alpha;'', ''&alpha;'')}} に近づいている。これがエイトケンの {{math|&Delta;{{sup|2}}}} 加速法の定義式の理由である。

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

エイトケンの {{math|&Delta;{{sup|2}}}} 加速法は、上の説明からわかるように方程式 {{math|1=''x'' = ''g''(''x'')}} の数値計算にも応用可能である。事実、エイトケンは代数方程式の近似計算にこの方法を適用した{{Sfn|Aitken|1926}}{{Sfn|中村佳正・編|2000}}。

==歴史==
現時点に於いて判明しているところによると、エイトケンの {{math|&Delta;{{sup|2}}}} 加速法は[[和算]]家の[[関孝和]]によって[[1681年]]頃に導出されたのが世界で最初である。関孝和は[[暦]]の作成で必要になった[[円周率]]の[[近似値|近似]]計算でこの加速法を用いて、[[小数点]]以下第16位までを正確に求めた{{Sfn|中村佳正・編|2000}}<ref>ただし関が最終的に円周率の近似値として採用した値は「3.14159265359 微弱」である。</ref>。関孝和の業績は日本でも長らく忘却されていたが、フランス人{{Harvnb|Brezinski|1991}}に指摘されて{{Sfn|中村佳正・編|2000}}再発見された。西洋に於いてエイトケンの {{math|&Delta;{{sup|2}}}} 加速法が導出されたのは、それから約200年後の[[1876年]]であり、{{Harvnb|H. von. N&auml;gelsbach|1876}}による。エイトケンの {{math|&Delta;{{sup|2}}}} 加速法という名前で今日呼ばれるようになったのはさらに後の、{{仮リンク|アレクサンダー・エイトケン|en|Alexander Aitken|de|Alexander Aitken}}の論文{{Harv|Aitken|1926}}にちなむ。

==参考文献==
{{Refbegin}}
*{{Cite journal |author =H. von. N&auml;gelsbach |year=1876|journal=Arch. Math. Phys. |volume=59. |pages=147-192 |ref=harv }}
*{{Cite journal |first =A. C. |last =Aitken |year=1926 |title=On Bernoulli's numerical solution of algebraic equations |journal=Proc. Royal. Soc. |volume=46 |publisher= Edinburgh |pages=289-305 |ref=harv }}
*{{Cite book |last=Breziski |first=Claude |year=1991 |title=History of continued fractions and Pad&eacute; approximants |publisher=Springr Verlag |location=Berlin |oclc=21411454 }}
*{{Cite book |和書 |editor=中村佳正・編|year=2000 |title=[[可積分]]系の[[応用数理]]|chapter=第6章 離散[[可積分]]系と[[数列]]の加速法 |publisher=[[裳華房]] |page= |id= |isbn=4-7853-1520-2 |ref=harv }}
* 室田一雄、杉原正顕：「Aitken 加速に関する一つの注意」、情報処理学会論文誌、Vol.25, No.5, pp.892-894 (1984).
{{Refend}}

==脚注==
{{脚注ヘルプ}}
{{Reflist|2}}
{{級数}}
{{DEFAULTSORT:えいとけんのてるたししようかそくほう}}
[[Category:数値解析]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]