I have been given an assignment to compute the polynomial interpolant of a function, but in the assignment question it says $x_0=1,x_1=0.5, x_2=2$, and I was wondering if I would have to re-label them so $x_0<x_1<x_2$.
I have seen on wikipedia that "Newton's form has the simplicity that the new points are always added at one end", but have never seen it explicitly stated that the interpolation points, $x_k$, must be of the form $x_0<x_1<…<x_n$.
I was wondering if anyone could clear this up, and if the points do need to be increasing, if anyone could explain why they need to be increasing. Thanks very much!
Best Answer
No, it is a theorem that the Newton divided difference $f[x_0,x_1,\dots,x_n]$ is invariant under permutation. This is tedious but mostly straightforward to prove by induction.
I think you have actually misunderstood Wikipedia's statement. I think they are probably referring to the algebraic form. For example, if you have a Newton interpolant $a+b(x-x_0)$ for two points and you add a third point $(x_2,y_2)$ (irrespective of how $x_2$ compares to $x_0$ and $x_1$), then you get $a+b(x-x_0)+c(x-x_0)(x-x_1)$. The first two terms stay the same! In the Lagrange form this does not hold, because each of the Lagrange basis elements depends on all of the points.