ネヴィルのアルゴリズム

与えられた ${\displaystyle N+1}$ 点 ${\displaystyle \{(x_{n},y_{n})\}_{n=0}^{N}}$ のラグランジュ補間多項式 ${\displaystyle L(x)}$、すなわちこれらの点を通る ${\displaystyle N}$ 次多項式を求めることを考える。ただし ${\displaystyle x_{n}\neq x_{m}}$ (${\displaystyle n\neq m}$) とする。ネヴィルのアルゴリズムは、 ${\displaystyle k+1}$ 個の点 ${\displaystyle \{(x_{n},y_{n})\}_{n=i-k}^{i}}$ を通る ${\displaystyle k}$ 次多項式 ${\displaystyle P_{i,k}}$ を以下のように再帰的に定めるものである^{[4][5][6][注釈 1]}。

1. ゼロ次多項式 ${\displaystyle P_{i,0}}$ (${\displaystyle i=0,1,\cdots ,N}$) を
   ${\displaystyle \qquad P_{i,0}=y_{i}}$
   により定める。
2. 多項式 ${\displaystyle P_{i,k}}$ を ${\displaystyle P_{i,k-1}}$ と ${\displaystyle P_{i-1,k-1}}$ から漸化式
   ${\displaystyle \qquad P_{i,k}(x)={\frac {(x-x_{i-k})P_{i,k-1}-(x-x_{i})P_{i-1,k-1}}{x_{i}-x_{i-k}}}=P_{i,k-1}+{\frac {x-x_{i}}{x_{i}-x_{i-k}}}(P_{i,k-1}-P_{i-1,k-1})}$
   によって定める。
3. ${\displaystyle P_{N,N}=L}$ が求めるラグランジュ多項式を与える。

ここで2番目のステップにおいて、漸化式の右辺に現れる多項式 ${\displaystyle P_{i,k-1}}$, ${\displaystyle P_{i-1,k-1}}$ はともに ${\displaystyle k-1}$ 個の点 ${\displaystyle \{(x_{n},y_{n})\}_{n=i-k+1}^{i-1}}$ を通ることに注意する。その結果として上記漸化式により ${\displaystyle P_{i,k}}$ は2点 ${\displaystyle (x_{i-k},y_{i-k})}$, ${\displaystyle (x_{i},y_{i})}$ をも通る多項式 ${\displaystyle P_{i,k}}$ が構成できる^[7]。

例えば ${\displaystyle N=3}$ の場合, このアルゴリズムは次の表を左から埋めていくことに対応する^[8][9]。多項式 ${\displaystyle P_{i,k}}$ は自身の左側にあるふたつの多項式 ${\displaystyle P_{i,k-1}}$, ${\displaystyle P_{i-1,k-1}}$ から上記漸化式を通じて定まる「娘」である^[8]。

ネヴィルのアルゴリズムはラグランジュ補間多項式のある一点 ${\displaystyle x}$ での値 ${\displaystyle L(x)}$ を評価する目的に適している^[1][10]。多項式それ自体を求める場合、あるいは複数の点の補間値が必要な場合、ニュートン補間の方が好ましい^[11]。補間値を得るためには必ずしもネヴィルのアルゴリズムを最後まで実行する必要はなく、途中で止めることも可能である^[12]。

ネヴィルのアルゴリズムは定積分を数値的に求めるロンバーグ積分に用いられる^[13]。