ステフェンセンの方法

数値解析において、ステフェンセン法は、ヨハン・フレデリック・ステフェンセンにちなんで名付けられた反復法であり、数値根探索法として、割線法やニュートン法に類似している。ステフェンセン法は導関数を用いずに2次収束を達成するのに対し、より一般的なニュートン法も2次収束するが導関数を必要とし、割線法は導関数を必要としないが2次収束よりも収束速度が遅い。

ステフェンセン法は、ステップごとに2回の関数評価が必要となるという欠点がある。一方、割線法はステップごとに1回の評価しか必要としないため、それぞれの反復回数によっては、計算コストの面で最も効率的とは限らない。ニュートン法も、ステップごとに2つの関数（関数とその導関数）を評価する必要があり、その計算コストは​​、最良の場合は割線法と同じ、最悪の場合はステフェンセン法と同じとなる。ほとんどの関数では、導関数の計算は元の関数の計算と同じくらい計算コストがかかるため、通常はニュートン法とステフェンセン法のコストは同程度となる。^{[ a ]}

ステフェンセンの方法は、エイトケンのデルタ二乗法を不動点反復に適用したものとして導出できます。このように考えると、ステフェンセンの方法は、バナッハの不動点定理によって不動点の存在が保証され、不動点反復が収束することが保証されている場合（収束速度は遅い場合もある）、一般的なバナッハ空間における効率的な不動点計算に自然に一般化されます。

ステフェンセン法の公式の最も単純な形式は、実関数の零点を求める際に用いられる。${\displaystyle f}$つまり、真の値を求める${\displaystyle \ x_{\star }\ }$満たす${\displaystyle \ f(x_{\star })=0~.}$解決策の近く${\displaystyle \ x_{\star }\ ,}$関数の導関数、${\displaystyle \ f'\ ,}$完全に、またはほぼ満たす必要がある${\displaystyle -1<f'(x_{\star })<0~.}$^{[ b ]} 一部の関数では、この条件が満たされなくてもステフェンセンの方法が有効ですが、その場合、開始値は${\displaystyle \ x_{0}\ }$実際の解に非常に近いものでなければならない${\displaystyle \ x_{\star }\ ,}$また、解への収束が遅くなる場合もあります。後述するように、この手法の中間ステップのサイズを調整することで、こうしたケースの一部において収束を改善できる可能性があります。

適切な初期値を与えると${\displaystyle \ x_{0}\ ,}$値のシーケンス${\displaystyle \ x_{0},\ \ x_{1},\ x_{2},\ \dots ,\ x_{n},\ \dots \ }$以下の式を使用して生成できます。うまく機能すると、数列の各値は解に非常に近くなります。${\displaystyle \ x_{\star }\ }$以前の値よりも。${\displaystyle \ x_{n}\ }$現在のステップから値が生成されます${\displaystyle \ x_{n+1}\ }$次のステップでは、式^{[ 1 ]を使用します。}

${\displaystyle x_{n+1}=x_{n}-{\frac {f(x_{n})}{g(x_{n})}}}$

のために${\displaystyle \ n=0,1,2,3,...\ ,}$傾き関数${\displaystyle \ g(x)\ }$元の関数の合成です${\displaystyle \ f\ }$式で与えられる

${\displaystyle g(x)={\frac {f{\bigl (}x+f(x){\bigr )}}{f(x)}}-1}$

あるいはもっと明確に言うと、

${\displaystyle g(x)={\frac {f(x+h)-f(x)}{h}}\qquad \approx \quad {\frac {\operatorname {d} f(x)}{\operatorname {d} x}}\equiv f'(x),}$

どこ${\displaystyle \ h\equiv f(x)\ }$は、最後の反復ポイント間のステップサイズです。${\displaystyle \ x\ ,}$そして補助ポイントは${\displaystyle \ x+h~.}$

技術的には、その機能は${\displaystyle \ g\ }$これは、${\displaystyle \ f\ }$2点間の^{[ c ]}実際には、これは傾きの平均値です${\displaystyle f'}$関数の${\displaystyle \ f\ }$最後のシーケンスポイントの間${\displaystyle \left(x,y\right)={\bigl (}x_{n},f\left(x_{n}\right){\bigr )}}$そして補助点は${\displaystyle \ {\bigl (}x,y{\bigr )}={\bigl (}x_{n}+h,f\left(x_{n}+h\right){\bigr )}\ ,}$中間ステップのサイズ（およびその方向）は、${\displaystyle \ h=f(x_{n})~.}$

価値が${\displaystyle \ g\ }$は、の近似値です。${\displaystyle \ f'\ ,}$その値は、条件を満たしているかどうかを確認するためにオプションでチェックできます。${\displaystyle \ -1<g<0\ ,}$これは、ステフェンセンのアルゴリズムの収束を保証するために必要な条件です。わずかな不適合は必ずしも深刻な問題ではありませんが、条件から大きく逸脱すると、ステフェンセンの方法が失敗する可能性があることを警告し、代替アルゴリズム（例えば、より堅牢なイリノイアルゴリズム、または単純なregula falsi）を一時的に使用することが推奨されます。

それはただ見つけるためだけのものです${\displaystyle \ h\ }$この補助点では、関数の値は${\displaystyle \ f\ }$以下の要件を満たさなければならない${\displaystyle \ -1<f'(x_{\star })<0~.}$^{[ b ]}計算の他のすべての部分については、ステフェンセンの方法では関数のみが必要です${\displaystyle \ f\ }$連続的であり、実際に近傍に解が存在すること。^{[ 1 ]}ステップのいくつかの小さな修正${\displaystyle \ h\ }$傾きの式で使用される${\displaystyle \ g\ }$関数に対応するために、 1 / 2や3/4を掛けるなどの方法が存在する 。 ${\displaystyle \ f\ }$要件を完全に満たしていないもの。

ステフェンセン法の主な利点は、ニュートン法と同様に二次収束性を持つことである^{[ 1 ]}。つまり、どちらの方法も方程式の根を見つける。${\displaystyle \ f\ }$同じように「素早く」。この場合、「素早く」とは、どちらの方法でも、各ステップごとに正解の桁数が倍になることを意味します。しかし、ニュートン法の公式では、関数の導関数を評価する必要があります。${\displaystyle \ f'\ }$機能も同様に${\displaystyle \ f\ ,}$ステフェンセンの方法では、${\displaystyle \ f\ }$それ自体が重要です。これは、デリバティブが容易に、あるいは効率的に入手できない場合に特に重要です。

迅速な収束の代償は、関数評価の2倍です。${\displaystyle \ f(x_{n})\ }$そして${\displaystyle \ f(x_{n}+h)\ }$計算する必要があるが、時間がかかる可能性がある${\displaystyle \ f\ }$は複雑です。比較のために、regula falsiと割線法はどちらも、ステップごとに 1 つの関数評価しか必要としません。割線法は、 ステップごとに正しい桁数を「わずか」約 1.6 倍に増やしますが、与えられた時間内に割線法の 2 倍のステップを実行できます。割線法は Steffensen の方法と同じ時間で 2 倍のステップを実行できるため、^{[ d ]}実際には、両方のアルゴリズムが成功した場合、割線法は Steffensen の方法よりも速く収束します。割線法は、2 ステップ (2 つの関数評価) ごとに約(1.6) ² ≈ 2.6倍の桁数を達成しますが、Steffensen の方法では 1 ステップ (2 つの関数評価) ごとに2倍になります。

他のほとんどの反復根探索アルゴリズムと同様に、ステフェンセン法の決定的な弱点は、「十分に近い」初期値を選択することにある。${\displaystyle \ x_{0}~.}$値が${\displaystyle \ x_{0}\ }$実際の解決策に「十分近い」とは言えない${\displaystyle \ x_{\star }\ ,}$この方法は失敗する可能性があり、値のシーケンスは${\displaystyle \ x_{0},\,x_{1},\,x_{2},\,x_{3},\,\dots \ }$2つ（またはそれ以上）の極端な状態の間を不規則に揺れ動くか、無限大に発散するか、あるいはその両方になる可能性がある。

以下のMATLABコードに実装されているSteffensen法のバージョンは、収束加速のためのAitkenのデルタ二乗法を用いて見つけることができます。以下の式を上記のセクションの式と比較するには、次の点に注意してください。${\displaystyle x_{n}=p-p_{n}}$この方法は、線形収束する数列から始めて、その数列の収束速度を上げることを前提としています。${\displaystyle p_{n},\,p_{n+1},\,p_{n+2}}$同意して${\displaystyle p_{n}}$数列の望ましい限界に「十分近い」${\displaystyle p}$すると仮定できる

${\displaystyle {\frac {p_{n+1}-p}{p_{n}-p}}\approx {\frac {p_{n+2}-p}{p_{n+1}-p}},}$

となることによって

${\displaystyle (p_{n+2}-2p_{n+1}+p_{n})p\approx p_{n+2}p_{n}-p_{n+1}^{2}.}$

数列の目的の極限を求める${\displaystyle p}$与える：

${\displaystyle p\approx {\frac {p_{n+2}p_{n}-p_{n+1}^{2}}{p_{n+2}-2p_{n+1}+p_{n}}}}$

${\displaystyle =~{\frac {\,(\,p_{n}^{2}+p_{n}\,p_{n+2}-2\,p_{n}\,p_{n+1}\,)-(\,p_{n}^{2}-2\,p_{n}\,p_{n+1}+p_{n+1}^{2}\,)\,}{\,p_{n+2}-2\,p_{n+1}+p_{n}\,}}}$

${\displaystyle =p_{n}-{\frac {(p_{n+1}-p_{n})^{2}}{p_{n+2}-2p_{n+1}+p_{n}}},}$

その結果、より速やかに収束する数列が得られる。

${\displaystyle p\approx p_{n+3}=p_{n}-{\frac {(p_{n+1}-p_{n})^{2}}{p_{n+2}-2p_{n+1}+p_{n}}}.}$

Steffensen's method can also be used to find an input ${\displaystyle \ x=x_{\star }\ }$ for a different kind of function ${\displaystyle \ F\ }$ that produces output the same as its input: ${\displaystyle \ x_{\star }=F(x_{\star })\ }$ for the special value ${\displaystyle \ x_{\star }~.}$ Solutions like ${\displaystyle \ x_{\star }\ }$ are called fixed points. Many of these functions can be used to find their own solutions by repeatedly recycling the result back as input, but the rate of convergence can be slow, or the function can fail to converge at all, depending on the individual function. Steffensen's method accelerates this convergence, to make it quadratic.

Momentarily ignoring the issues of a more general Banach space vs. basic real numbers for the sake of an example: To re-orient the reader to the earlier section, a simple toy model fixed-point function, ${\displaystyle \ {\tilde {F}}\ ,}$ using any root function ${\displaystyle \ f\ ,}$ can be made with ${\displaystyle \ {\tilde {F}}(x)=x+\varepsilon \ f(x)~.}$ Here ${\displaystyle \ \varepsilon \ }$ is a constant with the appropriate sign that is small enough in magnitude to make ${\displaystyle \ {\tilde {F}}\ }$ stable under iteration, but large enough for the non-linearity of the function ${\displaystyle \ f\ }$ to be appreciable.

This method for finding fixed points of a real-valued function has been generalized for functions ${\displaystyle \ F:X\to X\ }$ that map a Banach space${\displaystyle \ X\ }$それ自体に、あるいはさらに一般的に${\displaystyle \ F:X\to Y\ }$あるバナッハ空間からの地図${\displaystyle X}$別のバナッハ空間へ${\displaystyle \ Y~.}$一般化された方法は、有界線形演算子の族を仮定します。${\displaystyle \ {\bigl \{}\ G(u,v):u,v\in X\ {\bigr \}}\ }$関連する${\displaystyle \ u\ }$そして${\displaystyle \ v\ }$（局所的に）条件^{[ 2 ]を満たすように考案することができる。}

オペレーター${\displaystyle \ G\ }$これは、要素がすべてベクトル引数の関数である行列とほぼ同等です。${\displaystyle \ u\ }$そして${\displaystyle \ v~.}$もう一度、単純な関数を参照してください。${\displaystyle \ f\ ,}$最初のセクションで説明したように、関数は単に実数を入力として受け取り、実数を出力するだけです。${\displaystyle \ g\ }$これは分割差分です。ここでの一般化された形式では、演算子は${\displaystyle \ G\ }$これは、バナッハ空間で使用するための分割差分の類似物です。

バナッハ空間で除算が可能な場合、線形演算子${\displaystyle \ G\ }$入手先は

${\displaystyle G\left(u,v\right)={\bigl [}\ F\left(u\right)-F\left(v\right)\ {\bigr ]}\ {\bigl (}\ u-v\ {\bigr )}^{-1}\ ,}$

これは何らかの洞察を与えてくれるかもしれない。このように表現すると、線形演算子は${\displaystyle \ G\ }$これは分割差の精緻なバージョンとしてより容易に理解できる${\displaystyle \ g\ }$上記第1節で説明したとおりです。商形式は、ここでは理解を助けるためだけに示したものであり、必ずしも必要ではありません。また、バナッハ空間内での除算は、詳細なステフェンセンの方法が有効であるために必要ではありません。唯一の要件は、演算子が${\displaystyle \ G\ }$（１）を満たす。

ステフェンセン法は、分割差分を用いる点を除けば、ニュートン法と非常によく似ている。${\displaystyle \ G{\bigl (}F\left(x\right),x{\bigr )}\ }$導関数の代わりに${\displaystyle \ F'(x)~.}$引数については、${\displaystyle \ x\ }$ある固定点に近い${\displaystyle \ x_{\star }\ ,}$不動点関数${\displaystyle \ F\ }$およびそれらの線形演算子${\displaystyle \ G\ }$条件（１）を満たす、${\displaystyle \ F'(x)\ \approx \ G{\bigl (}F\left(x\right),x{\bigr )}\ \approx \ I\ ,}$どこ${\displaystyle \ I\ }$は恒等演算子です。

バナッハ空間で除算が可能な場合、一般化された反復式は次のように与えられる。

${\displaystyle x_{n+1}=x_{n}+{\Bigl [}\ I-G{\bigl (}F\left(x_{n}\right),x_{n}{\bigr )}\ {\Bigr ]}^{-1}{\Bigl [}\ F\left(x_{n}\right)-x_{n}\ {\Bigr ]}\ ,}$

のために${\displaystyle \ n=1,\ 2,\ 3,\ ...~.}$除算が不可能なより一般的なケースでは、反復式は解を求める必要がある。${\displaystyle \ x_{n+1}\ }$近い${\displaystyle \ x_{n}\ }$そのために

${\displaystyle {\Bigl [}\ I-G{\bigl (}F\left(x_{n}\right),x_{n}{\bigr )}\ {\Bigr ]}{\bigl (}\ x_{n+1}-x_{n}\ {\bigr )}=F\left(x_{n}\right)-x_{n}~.}$

言い換えれば、解決策を求めることもできる。${\displaystyle \ x_{n+1}\ }$やや縮小された形

${\displaystyle {\Bigl [}\ I-G{\bigl (}F\left(x_{n}\right),x_{n}{\bigr )}\ {\Bigr ]}\ x_{n+1}={\Bigl [}\ F\left(x_{n}\right)-G{\bigl (}F\left(x_{n}\right),x_{n}{\bigr )}\ x_{n}\ {\Bigr ]}\ ,}$

角括弧内のすべての値は独立している${\displaystyle \ x_{n+1}\$ :} 括弧内の項はすべて、${\displaystyle \ x_{n}\ }$しかし、2番目の形式は1番目の形式ほど数値的に安定していない可能性があります。1番目の形式は（願わくば）小さな差の値を求めるため、反復値の過度に大きな変化や不規則な変化を数値的に回避できる可能性が高くなります。${\displaystyle \ x_{n}~.}$

線形演算子${\displaystyle \ G\ }$満たす

${\displaystyle {\Bigl \|}G\left(u,v\right)-G\left(x,y\right){\Bigr \|}\leq k{\biggl (}{\Bigl \|}u-x{\Bigr \|}+{\Bigr \|}v-y{\Bigr \|}{\biggr )}}$

ある正の実定数に対して${\displaystyle \ k\ ,}$すると、この方法は2次収束して固定点に収束する。${\displaystyle \ F\ }$初期近似値の場合${\displaystyle \ x_{0}\ }$望ましい解に「十分近い」${\displaystyle \ x_{\star }\ }$満たす${\displaystyle \ x_{\star }=F(x_{\star })~.}$