# Lagrange Interpolation Theorem?

The polynomials $p(x) = 5x^3 - 27x^2 + 45x - 21$ and $q(x) = x^4 - 5x^3 + 8x^2 - 5x + 3$ both interpolate the points $(1,2) , (2,1) , (3,6), (4,47)$. Even though these polynomials are of different degree, I do not understand how this is possible when the Lagrange interpolation theorem states there is only one polynomial which should interpolate these points.

-
Only the polynomial of least degree is unique. – Silynn Jul 17 '14 at 13:07

There is a unique polynomial of degree $n$ or less through $n+1$ points but as many as you want of higher degree.

-
Hi, am i right in saying then, that in this case p(x) is the only polynomial that satisfies the theorem because it is a third degree polynomial and there are 4 points. However there are numerous polynomials of degree 4 and higher that will interpolate the 4 points. – Jed Jul 17 '14 at 13:16
Erm...no, this is not correct as stated. Being non-collinear is not important. Having distinct $x$ values is what matters. And the degree need not actually be $n$, it can be less than $n$. For example, I can interpolate $(0,0),(1,1),(2,4),(3,9),(4,16)$ with a quadratic polynomial even though there are $5$ points. – Ian Jul 17 '14 at 13:18
@Ian Would I be correct is saying there is a unique polynomial of degree less than or equal to $n$ through $n+1$ points? – Jp McCarthy Jul 17 '14 at 14:01
Close. You can't interpolate a polynomial through two points on the same vertical line, for obvious reasons. This is the only requirement on the points themselves, however. – Ian Jul 17 '14 at 14:05
@Ian To be honest as far as I am concerned that goes without saying. Thanks for your help. – Jp McCarthy Jul 17 '14 at 15:09

Working in the Newton basis makes this clearer. The Lagrange interpolation theorem says that your cubic polynomial is the unique polynomial interpolant whose degree is at most $3$. It can be written in the Newton basis as:

$$c_1 + c_2 (x-1) + c_3 (x-1)(x-2) + c_4 (x-1)(x-2)(x-3)$$

for some $c_1 , \dots , c_4$. If I now consider a polynomial of the form

$$c_1 + c_2 (x-1) + c_3 (x-1)(x-2) + c_4 (x-1)(x-2)(x-3) + c_5 (x-1)(x-2)(x-3)(x-4)$$

then no matter what $c_5$ is, this will also be an interpolant. (Why?) I can also replace $c_5$ by any polynomial I want, and it will still be an interpolant.

-
Ok, then I am right in saying, if there are $(n+1)$ points to interpolate the Lagrange Interpolation theorem does not take into account polynomials of degree $(n+1)$ or higher. – Jed Jul 17 '14 at 13:30
In its statement of uniqueness, yes. It implies existence and non-uniqueness of higher degree interpolants. – Ian Jul 17 '14 at 14:15

Hint $\,f(x)\,$ is a solution $\!\iff\! f(x) + (x\!-\!1)(x\!-\!2)(x\!-\!3)(x\!-\!4)g(x)\,$ is a solution, for any $\,g(x),\,$ since both take the same values for $\,x\in\{1,2,3,4\}.\,$ The least degree polynomial of RHS form is the remainder of $\,f(x)\,$ when divided by $\,h(x) = (x\!-\!1)\cdots(x\!-\!4).\,$ This is the unique solution having degree $\,< \deg h = 4,\,$ since the remainder $\,r(x)\,$ is unique  (else $\ h\mid f-r, f-r',\,$ therefore $\,h\,$ divides their difference $\, r'-r,\,$ contra $\,\deg(r'-r) < \deg h,\,$ by $\,\deg r'<h,\ \deg r< h\,).$

If you know the Chinese Remainder Theorem (CRT) then you may find it instructive to reformulate Lagrange interpolation in the more general CRT form, by employing $\,f(x_i) = y_i \iff f\equiv y_i \pmod{ x - x_i}.$

-