逆二次補間

数値解析において、逆二次補間は根を求めるアルゴリズムであり、 f ( x ) = 0の形の方程式を解くためのアルゴリズムです。その考え方は、二次補間を用いてfの逆関数を近似することです。このアルゴリズムは単独で使用されることは稀ですが、広く用いられているBrent 法の一部を構成するため重要です。

逆二次補間アルゴリズムは、次の漸化式で定義される。

${\displaystyle x_{n+1}={\frac {f_{n-1}f_{n}}{(f_{n-2}-f_{n-1})(f_{n-2}-f_{n})}}x_{n-2}+{\frac {f_{n-2}f_{n}}{(f_{n-1}-f_{n-2})(f_{n-1}-f_{n})}}x_{n-1}}$

${\displaystyle {}+{\frac {f_{n-2}f_{n-1}}{(f_{n}-f_{n-2})(f_{n}-f_{n-1})}}x_{n},}$

ここでf _k = f ( x _k ) です。漸化式からわかるように、この方法ではx ₀、x ₁、x ₂の 3 つの初期値が必要です。

我々は、前述の 3 つの反復関数x _{n − 2}、x _{n − 1}、x _nと、それらの関数値f _{n − 2}、f _{n − 1}、f _nを使用します。fの逆関数に対して二次補間を行うためにラグランジュ補間公式を適用すると、次のようになります。

${\displaystyle f^{-1}(y)={\frac {(y-f_{n-1})(y-f_{n})}{(f_{n-2}-f_{n-1})(f_{n-2}-f_{n})}}x_{n-2}+{\frac {(y-f_{n-2})(y-f_{n})}{(f_{n-1}-f_{n-2})(f_{n-1}-f_{n})}}x_{n-1}}$

${\displaystyle \qquad +{\frac {(y-f_{n-2})(y-f_{n-1})}{(f_{n}-f_{n-2})(f_{n}-f_{n-1})}}x_{n}.}$

fの根を求めているので、上記の式にy = f ( x ) = 0を代入すると、上記の漸化式が得られます。

漸近挙動は非常に良好で、一般的に、反復値x _{n は}根に近づくと速やかに収束します。しかし、初期値が実際の根に近くない場合、パフォーマンスは著しく低下することがよくあります。例えば、関数値f _{n − 2}、f _{n − 1}、f _nのうち2つが偶然一致すると、アルゴリズムは完全に失敗します。そのため、逆二次補間は単独のアルゴリズムとして使用されることはありません。

割線法による解析で証明できるように、この収束の次数は約1.84である。

序論で述べたように、ブレントの方法では逆二次補間が使用されています。

逆二次補間は、他のいくつかの根を求める方法とも密接に関連しています。二次補間の代わりに線形補間を使用すると、割線法が得られます。fの逆関数の代わりにf を補間すると、ミュラー法が得られます。

• 逐次放物線補間法は、根ではなく放物線を用いて極値を求める関連手法である。

• ジェームズ・F・エパーソン著、『数値解析入門』、182～185ページ、Wiley-Interscience、2007年。ISBN 978-0-470-04963-1