Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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
1  
It is guaranteed to jump all the way to 10th degree. x^2 is the unique 9th degree polynomial interpolating the first 10 points, so no 9th degree polynomial will interpolate all 11. –  Ross Millikan Nov 22 '13 at 19:02
    
Oh, of course. I feel rather stupid now. Apologies for the basic question. –  AndrewG Nov 22 '13 at 19:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.