エイトケンのデルタ二乗過程

数値解析において、エイトケンのデルタ二乗過程またはエイトケン外挿法は、数列の収束速度を加速するために使用される級数加速法である。この方法は、1926年にこの方法を導入したアレクサンダー・エイトケンにちなんで名付けられました。 ^[1]これは、線形収束する数列の収束を加速するのに最も役立ちます。前身となる形式は関興和（1642年 - 1708年）に知られており、円の修正、つまりπの計算に適用されました。

エイトケンのデルタ二乗過程 を伴うシーケンスが与えられた場合、このシーケンスに新しいシーケンスが関連付けられます。${\displaystyle X={(x_{n})}}$${\displaystyle n=0,1,2,3,\ldots ,}$

$${\displaystyle A[X]=(a_{n})={\left({\frac {x_{n}\,x_{n+2}-x_{n+1}^{2}}{x_{n}+x_{n+2}-2\,x_{n+1}}}\right)},}$$

これは次のようにも書ける。

$${\displaystyle A[X]=\left(x_{n}-{\frac {(\Delta x_{n})^{2}}{\Delta ^{2}x_{n}}}\right),}$$

およびは代数的には両方とも同じシーケンスですが、後者は計算実装における 数値安定性が向上しています。${\textstyle \Delta x_{n}=x_{n+1}-x_{n}}$${\textstyle \Delta ^{2}x_{n}=x_{n}-2x_{n+1}+x_{n+2}=\Delta x_{n+1}-\Delta x_{n}.}$

${\textstyle A[X]}$シーケンスにゼロ要素が含まれる場合、 は不完全定義です。これは、前進差分シーケンス に繰り返される項がある場合に発生します。理論的な観点から、これが有限個のインデックスに対してのみ発生する場合、 がシーケンスが繰り返される最後のインデックスとなる ようなインデックスを持つシーケンスの部分にのみ Aitken プロセスを適用できます 。実際には、シーケンスの最初の数項で通常必要な精度が得られます。また、シーケンスを数値的に計算する場合、シーケンス変換によって有効桁がキャンセルされる場合があるため、分母の丸め誤差が大きくなりすぎる前に計算を停止するように注意する必要があります。 ${\textstyle \Delta ^{2}[X]=(\Delta ^{2}x_{n})}$${\textstyle \Delta [X]=(\Delta x_{n}),}$${\displaystyle X}$${\displaystyle n>n_{0}}$${\displaystyle n_{0}}$${\textstyle \デルタ[X]}$${\textstyle \Delta ^{2}}$

エイトケンのデルタ二乗過程は、収束加速法であり、非線形シーケンス変換の特殊なケースです。

極限値に収束する数列は、ある数に対して ${\textstyle X=(x_{n})}$${\textstyle \ell }$${\textstyle \mu \in (0,1)}$

$${\displaystyle \lim _{n\to \infty }{\frac {|x_{n+1}-\ell |}{|x_{n}-\ell |}}=\mu .}$$

これは、漸近的に、数列とその極限の間の距離が、各ステップでほぼ同じ割合で縮小し、縮小率がその割合にどんどん近づいていくことを意味します。これは、幾何級数の特性であるため「幾何収束」と呼ばれることもあります。または、次のような収束であるため「指数収束」と呼ばれることもあります。${\displaystyle \mu ,}$${\displaystyle \mu ^{n}=\exp(n\ln \mu ).}$

エイトケン法は、上で定義した条件が次式を満たす場合、シーケンスの収束を加速します。${\displaystyle X}$${\displaystyle A[X]=(a_{n}),}$${\textstyle \lim _{n\to \infty }{\frac {a_{n}-\ell }{x_{n}-\ell }}=0.}$

${\displaystyle A}$は数列上の線形作用素ではないが、定数数列の加算に関しては線形である。が任意の定数数列 であれば 、すべての に対して定数である。これは、 を有限差分作用素で表現すると明らかである。${\textstyle A[XC]=A[X]-C,}$${\displaystyle C}$${\displaystyle C=(c)}$${\displaystyle n.}$${\displaystyle A[X]}$ ${\displaystyle \Delta .}$

新しいプロセスは一般には2次収束しませんが、固定点に収束する何らかの関数を満たす反復関数シーケンスの場合、加速シーケンスの収束は2次になります。この場合、この手法はステフェンセン法として知られています。 ${\displaystyle x_{n+1}=f(x_{n})}$${\displaystyle f}$

経験的に、A演算は「最も重要な誤差項」を排除します。 これは、 という形式のシーケンスを検討することで確認できます。ここで、 シーケンスはがゼロになるのと同じように極限になります。 ${\displaystyle x_{n}=\ell +a^{n}+b^{n}}$${\displaystyle 0<b<a<1}$${\displaystyle A[X]}$${\textstyle \ell }$${\displaystyle b^{n}}$

幾何学的には、を満たし、の場合に水平漸近線を持つ指数関数のグラフです。 ${\displaystyle f(t)}$${\displaystyle f(n)=x_{n}}$${\displaystyle f(n+1)=x_{n+1}}$${\displaystyle f(n+2)=x_{n+2}}$${\displaystyle {\frac {x_{n}x_{n+2}-x_{n+1}^{2}}{x_{n}-2x_{n+1}+x_{n+2}}}}$${\displaystyle x_{n}-2x_{n+1}+x_{n+2}\neq 0}$

また、シーケンスが1 よりも厳密に大きい速度で極限に収束する場合、収束速度はそれほど高くないことも示せます。(実際には、たとえば 5 回 (それぞれ 7 回) の反復 (正しい桁が 1 つから開始) 後に 30 桁 (それぞれ 100 桁) を超える正しい小数点数を意味する二次収束が発生することはめったにありません。通常、その場合は加速は必要ありません。) ${\displaystyle X}$${\displaystyle \ell }$${\displaystyle A[X]}$

実際には、以下の計算例で示されているように、 はよりもはるかに速く極限に収束することがよくあります。通常、数列 の項をもっとたくさん計算するよりも、 を計算する (差の計算、1 回の乗算、1 回の除算のみ) 方がはるかに安価です。ただし、式の分子と分母の差を計算するときに精度が不十分なために誤差が生じないように注意する必要があります。 ${\displaystyle A[X]}$${\displaystyle X}$${\displaystyle A[X]}$${\displaystyle X}$

例1 : の値は、の初期値を仮定し、ヘロン法 と呼ばれる以下の手順を繰り返すことで近似できます。 ${\displaystyle {\sqrt {2}}\approx 1.4142136}$${\displaystyle x_{0}}$$${\displaystyle x_{n+1}={\frac {x_{n}+{\frac {2}{x_{n}}}}{2}}.}$$${\displaystyle x_{0}=1:}$

ここで注目すべきは、エイトケンの方法で 2 回の反復計算のコストが節約されないことです。最初の 3 つの値の計算には、最初の 5 つの値が必要でした。また、2 番目の値は 4 番目の値よりも精度が低くなりますが、これはエイトケンのプロセスが 2 次ではなく 1 次収束するシーケンスに最適であり、平方根を計算するヘロンの方法は 2 次収束するため、驚くことではありません。^{[引用が必要]}${\textstyle A[X]}$${\textstyle X}$${\textstyle A[X]}$${\textstyle X}$

例2 : の値は、πのライプニッツの公式を使用して無限和として計算できます。${\displaystyle {\frac {\pi }{4}}}$

$${\displaystyle {\frac {\pi }{4}}=\sum _{n=0}^{\infty }{\frac {(-1)^{n}}{2n+1}}\approx 0.785398}$$

この例では、Aitken 法が非線形収束する級数に適用され、収束が大幅に加速されます。収束は依然として非線形ですが、元の収束よりもはるかに高速です。計算に最初の 3 つの値が必要だった最初の値は、8 番目の値よりも限界に近くなります。 ${\textstyle A[X]}$${\textstyle X}$${\textstyle X}$

以下は、ある初期値が与えられ、この数列の極限が固定点( と仮定) であると仮定した場合に、Aitken 外挿を使用して数列の極限を見つける例です。たとえば、数列が で与えられ、開始点がである場合、関数は となり、 は固定点となります (平方根の計算方法 を参照)。この固定点の値が近似されます。 ${\displaystyle x_{n+1}=f(x_{n})}$${\displaystyle x_{0},}$${\displaystyle f}$${\displaystyle \alpha =f(\alpha )}$${\textstyle x_{n+1}={\frac {1}{2}}\left(x_{n}+{\frac {2}{x_{n}}}\right)}$${\displaystyle x_{0}=1,}$${\textstyle f(x):={\frac {1}{2}}\left(x+{\frac {2}{x}}\right),}$${\displaystyle \alpha :={\sqrt {2}}}$

この擬似コードは、 の Aitken 近似値も計算します。Aitken 外挿値は で表されます。外挿値の計算中は、分母が小さくなりすぎないか確認することが重要です。これは、すでに高い精度がある場合に発生する可能性があります。この確認を行わないと、除算によって大きな誤差が生じる可能性があります。この小さな数は で表されます。固定小数点の 2 進表現は無限大になる可能性がある (または少なくとも使用可能なメモリに収まらないほど大きい) ため、近似値が真の値の範囲内になると計算は停止します。 ${\displaystyle f^{\prime }(\alpha )}$aitkenXepsilontolerance

%これらの選択は解決する問題によって異なります
x0 = 1 %初期値f ( x ) = ( 1 / 2 ) * ( x + 2 / x ) %シーケンス内の次の要素を見つける関数tolerance = 10 ^ - 10 %10桁の精度が望まれますepsilon = 10 ^ - 16 %これより小さい数で割らないでください                        
          
            
              

maxIterations = 20 %反復を無期限に継続させないhaveWeFoundSolution = false %希望の許容範囲内で解決策を見つけることができましたか?まだです            
   

i = 1の場合:最大反復回数x1 = f ( x0 ) x2 = f ( x1 )      
      
      

    if ( x1 ~= x0 ) lambda = absoluteValue (( x2 - x1 ) / ( x1 - x0 )) %OPTIONAL: lambdaで表される|f'(fixedPoint)|の近似値を計算するend   
                
    

    分母= ( x2 - x1 ) - ( x1 - x0 );        

    if ( absoluteValue ( denominator ) < epsilon ) %誤差の大幅な増加を避けるため、小さすぎる数値で割らないでくださいprint ( '警告: denominator is too small' ) break %ループを終了しますend           
        
                                                
    

    aitkenX = x2 - ( ( x2 - x1 ) ^ 2 ) / denominator if ( absoluteValue ( aitkenX - x2 ) < tolerance ) %値が許容範囲内の場合print ( "固定点は " 、aitkenX )) %Aitken外挿の結果を表示しますhaveWeFoundSolution = true break %完了したので、ループを終了しますend        
    
              
                
          
                                                
    

    x0 = aitkenX % x0を更新して再度開始します                  end                                       


if ( haveWeFoundSolution == false ) % 希望する許容値内での解が見つからなかった場合はprint ( "警告: 希望する許容値 " 内での解が見つかりませんでした。, tolerance ) print ( "最後に計算された外挿は " , aitkenX ) end      
     
     

• 収束率
• シーケンスの制限
• 固定小数点反復
• リチャードソン外挿
• シーケンス変換
• シャンクスの変身
• ステフェンセン法

• William H. Press他著『Numerical Recipes in C』(1987) Cambridge University Press、ISBN 0-521-43108-5 (セクション 5.1 を参照) 
• アブラモウィッツとステグン『数学関数ハンドブック』、セクション 3.9.7
• ケンドール・E・アトキンソン『数値解析入門』(1989) John Wiley & Sons, Inc, ISBN 0-471-62489-6