ネヴィルのアルゴリズム
多項式 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}} から漸化式 P i , k ( x ) = ( 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 + x − x i x i − x i − k ( P i , k − 1 − 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})} によって定める。
P N , N = L {\displaystyle P_{N,N}=L} が求めるラグランジュ多項式を与える。
ここで2番目のステップにおいて、漸化式の右辺に現れる多項式 P i , k − 1 {\displaystyle P_{i,k-1}} , P i − 1 , k − 1 {\displaystyle P_{i-1,k-1}} はともに k − 1 {\displaystyle k-1} 個の点 { ( x n , y n ) } n = i − k + 1 i − 1 {\displaystyle \{(x_{n},y_{n})\}_{n=i-k+1}^{i-1}} を通ることに注意する。