◄ WORLD V · SONNY 5DART 296 · a helldive at the net

NEVILLE'S ALGORITHM reconstruct the value, not the polynomial — a tableau of blended estimates

Sometimes you do not want the interpolating polynomial — you want its value at one point. Neville's algorithm gets it without ever forming the coefficients: it fills a tableau where each entry blends two lower estimates, Pi…j = [(x−xj)Pi…j−1 − (x−xi)Pi+1…j] / (xi−xj), until the whole set collapses to a single number. It is a recursion made of weighted averages, numerically stable, and it doubles as an error estimate (successive columns should agree). The same value the Newton form gives — reconstructed by convergence of a tableau rather than by coefficients.

THE TECHNIQUE tableau: each entry blends two, collapsing to the value

The same three samples. The demo fills Neville's tableau and collapses it to the reconstructed value at a point: live demo







  
HISTORY & CREDIT Eric Harold Neville, 1934

  
“To evaluate the interpolant you must first find it.” — Neville reconstructs the value directly, blending neighbouring estimates until one number remains. You never write the polynomial down. cited

  
1934 · Eric Harold Neville — the tableau recurrence for iterated linear interpolation.
kin · Aitken's earlier scheme (1932); Neville's is the clean form used in practice.
now · the workhorse under Romberg integration and Bulirsch–Stoer extrapolation.

  
Each cell is a weighted average of the two beneath it; the tableau converges the corner to the answer. Reconstruction as a collapse, not a solve. Neville 1934






  
RECOMMEND FOR I-13 tableau collapsed to the value, computed

  
On the canonical compiler, the tableau over (0,1),(1,3),(2,9) collapses 7, 15 → 19 at x=3 — the same value Newton gave:

  
$ i13 run rec_neville.i13   # Neville tableau at x=3
p01 = 7
p12 = 15
p012 = 19        -- the reconstructed value (matches Newton)

  
Recommend: Neville is reconstruction by recursion, i13's native shape. It fills the tableau with weighted blends — 7 and 15 in the first column, then 19 — recovering the value without a single coefficient, and matching Newton (dart 295) exactly because the interpolant is unique (dart 294). The denominators xi−xj are the pairwise gaps whose product is the Vandermonde determinant: when the nodes are distinct they are safe, and when a node collides the tableau divides by zero. The load-bearing structure again, this time seen from inside the recursion.