Given a collection of $m+1$ points $\{(x_0,y_0), (x_1,y_1), …, (x_m,y_m)\}$, we can form the interpolating Lagrange polynomial $L(x)$: $$ L(x) = \sum_{i = 0}^{m} y_i l_i(x) \\ l_i(x) = \prod_{\substack{0 \le k \le m\\ k \ne i}} \frac{x – x_k}{x_i – x_k} $$ and it will be the unique polynomial of degree at most $m$ interpolating these points. But I'm curious:
When is this maximum degree actually obtained? When is there instead cancellation among the coefficients upon multiplying everything out?
For a rather extreme example, take any set of points on the parabola $f(x) = x^2$. This 2nd-degree polynomial trivially interpolates all of them, and if I were to use the above construction, things would always reduce down upon multiplying out, regardless of how many points (and terms) I start with.
In the other direction, can I say the following?
Any Lagrange polynomial interpolating a set of $m + 1$ points can't have degree $n < m$ if there exists a (different!) Lagrange polynomial of degree $n$ interpolating some subset of $n+1$ of those points, since this would violate uniqueness. So there seems to be some kind of recursiveness involved here: if I take any subset of $n+1$ points from the original $m+1$, and I interpolate on these instead, then the resulting Lagrange polynomial (which is of degree at most $n$) either interpolates all $m+1$ points, or these $m+1$ points require a polynomial of degree strictly higher than $n$.
If this is correct, does it get me anywhere towards answering the above question? I can't really see how, or how to approach it at all, really.
Best Answer
The basic answer is there is almost never cancellation. Following your example of $y=x^2$, you have the data points $(0,0),(1,1),(2,4)$ which it interpolates. Now if we pick one more point, say $(3,y)$ there will only be cancellation if $y=9$. For any other value, the interpolating polynomial will be of third degree. The same is true for $n$ points. There is a unique (at most) $n-2$ degree polynomial which interpolates the first $n-1$ points. There will only be cancellation if that polynomial passes exactly through the $n^{\text{th}}$ point.