ネヴィルのアルゴリズム
与えられた N + 1 {\displaystyle N+1} 点 { ( x n , y n ) } n = 0 N {\displaystyle \{(x_{n},y_{n})\}_{n=0}^{N}} のラグランジュ補間多項式 L ( x ) {\displaystyle L(x)} 、すなわちこれらの点を通る N {\displaystyle N} 次多項式を求めることを考える。ただし x n ≠ x m {\displaystyle x_{n}\neq x_{m}} ( n ≠ m {\displaystyle n\neq m} ) とする。ネヴィルのアルゴリズムは、 k + 1 {\displaystyle k+1} 個の点 { ( x n , y n ) } n = i − k i {\displaystyle \{(x_{n},y_{n})\}_{n=i-k}^{i}} を通る k {\displaystyle k} 次多項式 P i , k {\displaystyle P_{i,k}} を以下のように再帰的に定めるものである。
ゼロ次多項式 P i , 0 {\displaystyle P_{i,0}} ( i = 0 , 1 , ⋯ , N {\displaystyle i=0,1,\cdots ,N} ) を P i , 0 = y i {\displaystyle \qquad P_{i,0}=y_{i}} により定める。
その結果として上記漸化式により P i , k {\displaystyle P_{i,k}} は2点 ( x i − k , y i − k ) {\displaystyle (x_{i-k},y_{i-k})} , ( x i , y i ) {\displaystyle (x_{i},y_{i})} をも通る多項式 P i , k {\displaystyle P_{i,k}} が構成できる。
例えば N = 3 {\displaystyle N=3} の場合, このアルゴリズムは次の表を左から埋めていくことに対応する。多項式 P i , k {\displaystyle P_{i,k}} は自身の左側にあるふたつの多項式 P i , k − 1 {\displaystyle P_{i,k-1}} , P i − 1 , k − 1 {\displaystyle P_{i-1,k-1}} から上記漸化式を通じて定まる「娘」である。
y 0 = P 0 , 0 P 1 , 1 y 1 = P 1 , 0 P 2 , 2 P 2 , 1 P 3 , 3 = L y 2 = P 2 , 0 P 3 , 2 P 3 , 1 y 3 = P 3 , 0 {\displaystyle {\begin{matrix}y_{0}=P_{0,0}&\\&P_{1,1}\\y_{1}=P_{1,0}&&P_{2,2}\\&P_{2,1}&&P_{3,3}=L\\y_{2}=P_{2,0}&&P_{3,2}\\&P_{3,1}\\y_{3}=P_{3,0}&\end{matrix}}}