Build interpolation one node at a time

Try

Interpolate (0,1),(1,3),(3,13). Begin with the constant 1. Adding 2x fits the second point without changing the first. At x=3 this linear part is 7, leaving discrepancy 6. The product x(x−1) equals 6 there and vanishes at both old nodes, so adding x(x−1) completes the fit. The result is p(x)=1+2x+x(x−1)=1+x+x².

Predict

Predict what happens when a fourth node is added. A multiple of x(x−1)(x−3) leaves all three old values unchanged. Only one new coefficient is required. This incremental construction is a practical advantage of Newton form. It produces the same unique polynomial as Lagrange form, not a different approximation method; what changes is representation and the arithmetic used to construct or evaluate it.

Experiment

Construct the triangular table.

Node	Value	First divided difference to next node	Second divided difference
0	1	2	1
1	3	5	—
3	13	—	—

The first-row entries 1,2,1 are Newton coefficients. Evaluate at x=2 using 1+2[2+(2−1)·1]=7. Then append a data point at x=4 with value 21 and show that the cubic coefficient is zero.

Understand

Define f[xᵢ]=yᵢ and recursively f[xᵢ,…,xᵢ₊ₖ]=(f[xᵢ₊₁,…,xᵢ₊ₖ]−f[xᵢ,…,xᵢ₊ₖ₋₁])/(xᵢ₊ₖ−xᵢ). Distinct nodes keep denominators nonzero. The Newton polynomial is Σₖ₌₀ⁿ f[x₀,…,xₖ]∏ⱼ<ₖ(x−xⱼ), with the empty product equal to one. The incremental construction proves that each new coefficient must be the discrepancy divided by the node product. The divided-difference recurrence computes exactly these coefficients: compare leading coefficients of interpolants on overlapping node lists, whose difference vanishes at their shared nodes. Uniqueness ensures the result agrees with the Lagrange polynomial.

Apply

Nested evaluation begins at the highest coefficient and works backward: v=aₙ, then v=aⱼ+(x−xⱼ)v. Expanding one stage at a time proves the identity and uses n multiplication/addition stages. Coefficient construction still requires a triangular amount of work, ordinarily order n² arithmetic operations. Reordering nodes changes intermediate divided differences and roundoff, though the exact polynomial is unchanged. Closely spaced nodes can make noisy data differences and small denominators problematic. Repeated nodes require a confluent construction using derivative data; substituting equal nodes into the ordinary recurrence is invalid.

Divided differences are symmetric in their nodes in exact arithmetic, although the triangular table uses an order. One proof identifies f[x₀,…,xₙ] with the leading coefficient of the unique degree-at-most-n interpolant; that coefficient cannot depend on the ordering used to describe the same data. This provides a useful test: reorder a small rational dataset and compare the final highest-order difference. Lower coefficients change because they refer to different subsets, so expecting every table entry to remain unchanged would be an incorrect test.

Continue

Design a written implementation with a copied work array, explicit loop order, duplicate-node rejection and independent checks at every node. A successful interpolation residual does not measure error between nodes or prove numerical stability. Compare nested evaluation with an independent low-degree expansion on exact rational cases. Next, Runge’s phenomenon shows why increasing degree at equally spaced nodes can worsen approximation even when every table entry is computed exactly. Better representation alone cannot repair an unsuitable node distribution.

Review calculus and linear algebra when a prerequisite needs practice. Continue to Separate polynomial approximation from a poor node choice.