Neville's algorithm

In mathematics, Neville's algorithm is an algorithm used for polynomial interpolation. Given n + 1 points, there is a unique polynomial of degree n which goes through the given points. Neville's algorithm evaluates this polynomial.

Neville's algorithm is based on the Newton form of the interpolating polynomial and the recursion relation for the divided differences. It is similar to Aitken's algorithm, which is nowadays not used.

The algorithm

Given a set of n+1 data points (x_i, y_i) where no two x_i are the same, the interpolating polynomial is the polynomial p of degree at most n with the property

p(x_i) = y_i for all i = 0,…,n

This polynomial exists and it is unique. Neville's algorithm evaluates the polynomial at some point x.

Let p_i,j denote the polynomial of degree j − i which goes through the points (x_k, y_k) for k = i, i + 1, …, j. The p_i,j satisfy the recurrence relation

$p_{i,i}(x)=y_{i},\,$	$0\leq i\leq n,\,$
$p_{i,j}(x)={\frac {(x-x_{j})p_{i,j-1}(x)+(x_{i}-x)p_{i+1,j}(x)}{x_{i}-x_{j}}},\,$	$0\leq i<j\leq n.\,$

This recurrence can calculate p_0,n(x), which is the value being sought. This is Neville's algorithm.

For instance, for n = 4, one can use the recurrence to fill the triangular tableau below from the left to the right.

$p_{0,0}(x)=y_{0}\,$
	$p_{0,1}(x)\,$
$p_{1,1}(x)=y_{1}\,$		$p_{0,2}(x)\,$
	$p_{1,2}(x)\,$		$p_{0,3}(x)\,$
$p_{2,2}(x)=y_{2}\,$		$p_{1,3}(x)\,$		$p_{0,4}(x)\,$
	$p_{2,3}(x)\,$		$p_{1,4}(x)\,$
$p_{3,3}(x)=y_{3}\,$		$p_{2,4}(x)\,$
	$p_{3,4}(x)\,$
$p_{4,4}(x)=y_{4}\,$

This process yields p_0,4(x), the value of the polynomial going through the n + 1 data points (x_i, y_i) at the point x.

The complexity of this algorithm is (depending on the actual implementation): O(${\frac {3}{2}}n^{2}M+2n^{2}A$) with n being the degree of the interpolating polynomial, M meaning multiplications, and A meaning additions.

References

• Press, William (1992). "§3.1 Polynomial Interpolation and Extrapolation". Numerical Recipes in C. The Art of Scientific Computing (2nd edition ed.). Cambridge University Press. ISBN 978-0-521-43108-8, doi:10.2277/0521431085. {{cite book}}: |edition= has extra text (help); External link in |chapterurl= (help); Unknown parameter |chapterurl= ignored (|chapter-url= suggested) (help); Unknown parameter |coauthors= ignored (|author= suggested) (help)

External links

• Weisstein, Eric W. "Neville's Algorithm". MathWorld.