ネヴィルのアルゴリズム

ネヴィルのアルゴリズム () はラグランジュ補間の計算アルゴリズムのひとつである。と近い関係にあり、によって考案された。
アルゴリズム.
与えられた formula_1 点 formula_2 のラグランジュ補間多項式 formula_3、すなわちこれらの点を通る formula_4 次多項式を求めることを考える。ただし formula_5 (formula_6) とする。ネヴィルのアルゴリズムは、 formula_7 個の点 formula_8 を通る formula_9 次多項式 formula_10 を以下のように再帰的に定めるものである。
ここで2番目のステップにおいて、漸化式の右辺に現れる多項式 formula_15, formula_16 はともに formula_21 個の点 formula_22 を通ることに注意する。その結果として上記漸化式により formula_10 は2点 formula_24, formula_25 をも通る多項式 formula_10 が構成できる。
例えば formula_27 の場合, このアルゴリズムは次の表を左から埋めていくことに対応する。多項式 formula_10 は自身の左側にあるふたつの多項式 formula_15, formula_16 から上記漸化式を通じて定まる「娘」である。
特徴.
ネヴィルのアルゴリズムはラグランジュ補間多項式のある一点 formula_31 での値 formula_3 を評価する目的に適している。多項式それ自体を求める場合、あるいは複数の点の補間値が必要な場合、ニュートン補間の方が好ましい。補間値を得るためには必ずしもネヴィルのアルゴリズムを最後まで実行する必要はなく、途中で止めることも可能である。
ネヴィルのアルゴリズムは定積分を数値的に求めるロンバーグ積分に用いられる。