Construct Newton's divided-difference interpolating polynomial and evaluate at a given x.
Newton's divided-difference interpolation builds the polynomial incrementally: P(x) = c₀ + c₁(x-x₀) + c₂(x-x₀)(x-x₁) + .... The coefficients cₖ are divided differences computed from the data. This form is computationally efficient and makes it easy to add new points without recomputing everything.
Newton form
P(x) = f[x₀] + f[x₀,x₁](x-x₀) + f[x₀,x₁,x₂](x-x₀)(x-x₁) + ...
Divided difference
f[xᵢ,...,xⱼ] = (f[xᵢ₊₁,...,xⱼ] - f[xᵢ,...,xⱼ₋₁]) / (xⱼ - xᵢ)
Both produce the same polynomial, but Newton's form is more efficient when adding new points incrementally and uses Horner's scheme for fast evaluation.
They generalize finite differences to non-uniform spacing. The k-th divided difference f[x₀,...,xₖ] equals the leading coefficient of the degree-k interpolating polynomial through those k+1 points.