トップQs
タイムライン
チャット
視点

数列の加速法

収束の遅い数列を収束の速い数列に変換するアルゴリズムの総称 ウィキペディアから

Remove ads

数値解析における数列の加速法 (: Series acceleration) とは、収束の遅い数列を収束の速い数列に変換するアルゴリズムの総称である[1]。ただし,収束の極めて遅い対数収束列と呼ばれる数列全般に対して、収束を加速できるような単一のアルゴリズムは存在しないことが証明されている。なお、ベクトル列についても収束の加速法の研究がなされている。

級数加速の技法は、例えば特殊関数の様々な恒等式を得るためにも使われる。 例えばオイラー変換超幾何級数に適用すると、古典的でよく知られた超幾何級数の恒等式のいくつかが得られる。

定義

要約
視点

与えられた数列

が極限

を持つとする。

ここで別の数列

が加速された数列であるとは、元の数列より 速く収束する 、すなわち

が成り立つ事と定める。

もし元の数列が発散数列の場合、数列の変換はen:antilimitへの 補外法となる。

数列の変換は非線形なものほど強力である傾向がある。

Remove ads

歴史

19世紀以前

ヨーロッパと日本で研究が始まった。古典的な二つの加速法はオイラー変換[2]クンマー変換である。日本では関孝和建部賢弘など、ヨーロッパではアイザック・ニュートンなどが取り組んだ[3]

20世紀前半

エイトケンのΔ2乗加速法(但し、初出は関孝和による)[1][3]-算法[4]リチャードソンの補外建部賢弘が1722に考案したのが初出)など、様々な加速法が作られる。なお、現代において-算法はMathematicaのNSum、NLimitに組み込まれている[4]

1956年にピーター・ウィンによって提案されたepsilon method、レヴィンのu-変換、そしてWilf-Zeilberger-Ekhad法またはWZ法が挙げられます。

交互級数に対しては、Cohen et al.によって記述された強力な手法がいくつかあり、それらはからまでの収束速度を提供し、項の総和に適用できます。[5]

1990年代以降

加速法と可積分系・離散ソリトン方程式の関係が明らかになり、可積分系・離散ソリトン方程式から加速法を作る試みが始まった[6][7][8][9]。加速法のq-類似を構成する試みもなされている[10][11]

Remove ads

オイラー変換

要約
視点

基本的な線形数列変換の例として、収束性を改善するオイラー変換があります。これは交代級数(隣り合う項の符号が反転する実数の級数)に適用され、次のように与えられます。

ここで、前進差分演算子であり、その公式は以下の通りです。

元の級数(左辺)が収束が遅い場合、前進差分の大きさは急速に減少し、さらに2の負冪が乗じられることにより、右辺の級数の収束速度がさらに改善されます。

オイラー変換の特に効率的な数値実装はファン・ウィンガーデン変換[12]です。

Remove ads

共形変換

要約
視点

ある級数

は、関数f

と定義すると、と書けます。関数複素平面内に特異点分岐点特異点、または真性特異点)を持ち、これが級数の収束半径を制限します。が収束円の境界近く、または上にある場合、級数の収束は非常に遅くなります。このとき、共形写像を用いて特異点を移動させ、に対応する点が新しい収束円内に深く入るようにすると、収束を改善できます。

共形変換となるように選ぶ必要があり、通常、w = 0で有限の微分を持つ関数を選びます。一般性を失うことなくと仮定でき、wを再スケールしてを再定義できます。その場合、次の関数を考えます。

なので、となります。であるため、の級数展開にを代入することで、の級数展開を得られます。の場合、の級数展開の最初の項は、の級数展開の最初の項を与えます。をその級数展開に代入すると、もし収束すれば、元の級数と同じ値に収束する級数が得られます。

Remove ads

非線形数列変換

非線形数列変換の例として、パデ近似シャンクス変換、およびレヴィン型数列変換があります。

特に非線形数列変換は、摂動論などで生じる発散級数漸近級数総和法に強力な数値手法を提供し、非常に効果的な外挿法として使用できます。


応用

要約
視点

Steffensen 反復

これはエイトケンのΔ2乗加速法の応用で、方程式の解を求めるための反復法である[1]。初期値を十分近くとれば1次収束する ( 級なら超1次収束, 級なら2次収束する[1])。 反復法 の収束次数がのとき、ならばそれに対するSteffensen反復法の収束は次であり、で収束先がの単根ならばSteffensen法は2次であり、で収束先が重根の場合にはSteffensen法は1次になる[13]

Romberg 積分

これは台形公式と加速法を組み合わせた数値積分法である[1][14]。Bauer-Rutishauser-Stiefel (1963) により詳細な解析がなされている[15]。現代では精度保証付き数値計算にも使われている[16]

特殊関数

べき級数で定義された複素関数のある点に於ける値を求めるのに、元のべき級数の展開中心の位置を解析接続により移動させることでより収束率の高いべき級数の和に置き換えて計算ができたなら,それは元の級数の和に対する一種の加速法であると見なしうる[17]。このような加速法は誤差関数などの特殊関数への計算に応用が可能である[17]

Remove ads

類似概念

常微分方程式の数値解法偏微分方程式の数値解法においても収束の加速法が研究されており、有限要素法[18]やShortley-Weller近似 (差分法の一つ)[19]などを加速できることが分かっている。

出典

参考文献

関連項目

外部リンク

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads