Newton polynomial ($p_n(x)={\sum }_{k=0}^{n}f[x_0,\dots ,x_k]{\prod }_{i=0}^{k-1}(x-x_i)$)

The Newton polynomial expresses the interpolation polynomial in products that successively vanish at all previously used interpolation nodes. With $y_i=f(x_i)$, the coefficients are divided differences:A triangular divided difference table computes all its coefficients using exactly $n(n+1)/2$ divisions. The Newton polynomial and the Lagrange polynomial have the same polynomial degree bound and the same nodal values, hence are equal by uniqueness of polynomial interpolation.

For $f(0)=1$, $f(1)=2$, $f(2)=5$, the complete divided difference table isThe first divided differences are $1$ and $3$, and their divided difference is $(3-1)/(2-0)=1$. Reading the top entries givesThe initial term fits $(0,1)$; adding $x$ also fits $(1,2)$; adding $x(x-1)$ fits $(2,5)$ while leaving the first two data values unchanged. This is the practical beauty of the Newton polynomial: each new correction respects all previous interpolation constraints.

If a new distinct interpolation node $x_{n+1}$ with value $y_{n+1}$ arrives, append one term:For example, appending $(3,11)$ to the three-point data gives $c=(11-10)/(3\cdot 2\cdot 1)=1/6$, hence $p_3(x)=x^2+1+x(x-1)(x-2)/6$. Changing the order of the interpolation nodes changes the Newton polynomial coefficients and products, but not the final interpolation polynomial in exact arithmetic.

The products also permit nested evaluation analogous to Horner's method. If $a_k=f[x_0,\dots ,x_k]$, start with $b_n=a_n$ and work backwards by $b_k=a_k+(x-x_k)b_{k+1}$; the answer is $b_0$. The three-point example becomes $1+x[1+(x-1)]$, needing two multiplications for each evaluation. This organization is useful when adding observations incrementally or evaluating a stored Newton polynomial many times; the Runge phenomenon still depends on the interpolation nodes rather than on which representation is used.

To justify the update formula, its added product vanishes at every previous interpolation node. Choosing $c$ by the new residual forces agreement at $x_{n+1}$, so uniqueness of polynomial interpolation identifies the result. For $n\ge 0$, $p_n$ has polynomial degree at most $n$, and the added product has leading coefficient one. Thus the new coefficient $c$ is exactly $f[x_0,\dots ,x_{n+1}]$. The initial state is $p_0(x)=f(x_0)$, with the empty product interpreted as one.^[ref]

Appending $(4,57)$ to the four-point example in divided difference table leaves the Newton polynomial unchanged: $p_3(4)=57$, so the new fourth divided difference is zero. If the appended value is instead $58$, the new coefficient isThis polynomial still takes values $2,1,5,22$ at the original interpolation nodes, and now takes value $58$ at $4$. A zero update is a valid completed step: adding another exact sample of the original polynomial need not increase the polynomial degree.

Reordering the interpolation nodes changes the successive subsets used for the divided differences and the factors of the Newton polynomial. The final interpolation polynomial remains unchanged in exact arithmetic. For $f(x)=x^3-2x+1$, reversing $(-1,0,2,3)$ gives $(3,2,0,-1)$ and values $(22,5,1,2)$. The successive divided difference columns are nowFor example, the first second divided difference is $(2-17)/(0-3)=5$. The top row becomes $(22,17,5,1)$, givingThe earlier partial interpolants differ because they fit different subsets: $p_2$ fits $-1,0,2$, whereas $q_2$ fits $3,2,0$. The highest divided difference is invariant because both complete top rows finish with the same set of four interpolation nodes; this is symmetry of divided differences.

This distinction is useful when checking a divided difference table: permuting all the interpolation nodes must preserve its final divided difference, even though the intermediate entries change. It also explains why data can be appended in their arrival order. In floating-point arithmetic, the subtractions and divisions may accumulate different rounding errors in different orders; exact invariance describes the mathematical polynomial, rather than guaranteeing bit-for-bit equality of numerical results.