ネヴィルのアルゴリズム () はラグランジュ補間の計算アルゴリズムのひとつである。と近い関係にありPress et al., p. 108.、エリック・ハロルド・ネヴィルによって考案された。
アルゴリズム 与えられた 点 のラグランジュ補間多項式 、すなわちこれらの点を通る 次多項式を求めることを考える。ただし () とする。ネヴィルのアルゴリズムは、 個の点 を通る 次多項式 を以下のように再帰的に定めるものであるPress et al., pp. 108-109.Deuflhard & Hofmann, pp. 184-185.Stoer & Bulirsch, pp. 40-42.ここでの表記法は Stoer & Bulirsch および Dieflhard & Hofmann に沿うものである。。
ゼロ次多項式 () をにより定める。 多項式 を と から漸化式によって定める。 が求めるラグランジュ多項式を与える。
ここで2番目のステップにおいて、漸化式の右辺に現れる多項式 , はともに 個の点 を通ることに注意する。その結果として上記漸化式により は2点 , をも通る多項式 が構成できるStoer & Bulirsch, p. 40.。
例えば の場合, このアルゴリズムは次の表を左から埋めていくことに対応するPress et al., p. 109.Stoer & Bulirsch, p. 41.。多項式 は自身の左側にあるふたつの多項式 , から上記漸化式を通じて定まる「娘」である。
特徴 ネヴィルのアルゴリズムはラグランジュ補間多項式のある一点 での値 を評価する目的に適しているStoer & Bulirsch, pp. 40-41.。多項式それ自体を求める場合、あるいは複数の点の補間値が必要な場合、ニュートン補間の方が好ましいStoer & Bulirsch, pp. 43-44.。補間値を得るためには必ずしもネヴィルのアルゴリズムを最後まで実行する必要はなく、途中で止めることも可能である。
ネヴィルのアルゴリズムは定積分を数値的に求めるロンバーグ積分に用いられるPress et al., pp. 140-141.。
脚注 注釈
出典
参考文献
関連項目 ラグランジュ補間 リチャードソンの補外