= Node order in Newton interpolation
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 now
$$
\begin{aligned}
D_{i,1}&:\quad 17,\ 2,\ -1,\\
D_{i,2}&:\quad 5,\ 1,\\
D_{i,3}&:\quad 1.
\end{aligned}
$$
For example, the first second <divided difference> is $(2-17)/(0-3)=5$. The top row becomes $(22,17,5,1)$, giving
$$
\begin{aligned}
q_0(x)&=22,\\
q_1(x)&=22+17(x-3)=17x-29,\\
q_2(x)&=22+17(x-3)+5(x-3)(x-2)=5x^2-8x+1,\\
q_3(x)&=22+17(x-3)+5(x-3)(x-2)+(x-3)(x-2)x\\
&=x^3-2x+1=p_3(x).
\end{aligned}
$$
The 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>.
\Image[/newton-interpolation-node-order.png]
{title=Reversing the interpolation nodes changes the Newton construction but gives the same final polynomial}
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.
Back to article page
