# Degrees of interpolating polynomials

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_{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.

-

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.
Suppose the polynomial interpolating the first $n - 1$ points actually has degree much less than $n - 2$, and it does not pass through the $n$th point. Then the poly interpolating all $n$ points has to be higher degree, sure -- but there's still lots of leeway, yes? To run with my example, let's say I have 10 points on $y = x^2$, and I add an 11th, not on that curve. How often will I jump from a 2nd degree all the way up to 10th? I'm guessing almost always often, but is there a way to make this more precise? – AndrewG Nov 22 '13 at 18:58