Aitken’s and Neville’s Interpolation
Source inspiration: (Mathew 2000-2019).
Description
Neville’s interpolation algorithm evaluates the unique degree-\((n-1)\) polynomial through data points \((x_i,y_i)\) without first converting to expanded polynomial coefficients. It uses a recursive tableau
\[ P_{i,i}(x)=y_i, \qquad P_{i,j}(x)=\frac{(x-x_i)P_{i+1,j}(x)-(x-x_j)P_{i,j-1}(x)}{x_j-x_i}, \quad i<j. \]
The final interpolated value at a query point \(x\) is \(P_{0,n-1}(x)\). Aitken’s process is the same recursion viewed as repeated linear interpolation between neighboring approximants; Neville’s table is the standard tabular form used for robust numerical evaluation.
Animations
The animation below illustrates Neville’s algorithm for polynomial interpolation of \(f(x) = \cos(x)\) at 5 nodes \(x_0 = 0,\, \tfrac{\pi}{4},\, \tfrac{\pi}{2},\, \tfrac{3\pi}{4},\, \pi\). Each frame adds one node, building successively higher-degree interpolants \(P_{0,j}(x)\).
Julia source scripts that generated these animations are linked under each case.
Case 1 — Neville’s algorithm: degree 0 through 4 for \(\cos(x)\)
Behavior: Neville’s algorithm builds the degree-\(n\) interpolating polynomial by combining two polynomials of degree \(n-1\): \(P_{i,j}(x) = \tfrac{(x-x_i)P_{i+1,j} - (x-x_j)P_{i,j-1}}{x_j - x_i}\). Adding each node refines the polynomial. By degree 4 (using all 5 nodes) the interpolant closely matches \(\cos(x)\) on the whole interval.
