トップ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 積分
→詳細は「en:Romberg integration」を参照
これは台形公式と加速法を組み合わせた数値積分法である[1][14]。Bauer-Rutishauser-Stiefel (1963) により詳細な解析がなされている[15]。現代では精度保証付き数値計算にも使われている[16]。
特殊関数
べき級数で定義された複素関数のある点に於ける値を求めるのに、元のべき級数の展開中心の位置を解析接続により移動させることでより収束率の高いべき級数の和に置き換えて計算ができたなら,それは元の級数の和に対する一種の加速法であると見なしうる[17]。このような加速法は誤差関数などの特殊関数への計算に応用が可能である[17]。
Remove ads
類似概念
→「超収束」も参照
常微分方程式の数値解法・偏微分方程式の数値解法においても収束の加速法が研究されており、有限要素法[18]やShortley-Weller近似 (差分法の一つ)[19]などを加速できることが分かっている。
出典
参考文献
関連項目
外部リンク
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads