# Interpolation error

Working with a homework problem where I'm to derive an estimation of the interpolation error, and compare it with the actual error. This part is ok and I'm done with it. But while working with this in Matlab I've started to wonder about something which I can't figure out (yet).

If we interpolate the polynomial $f(x)=c_3x^3+c_2x^2+c_1x+c_0$ for $x\in[a,b]$ with i.e. a Newton polynomial of degree two, $p_2(x)=b_2x^2+b_1x+b_0$ (using $x=[x_0,x_1,x_2]$ in the interpolation), we can estimate the interpolation error by

$|f(x)-p_2(x)|=\left|\frac{f^{(3)}(\xi)}{(3)!}\prod_{i=0}^2(x-x_i)\right|$.

I've implemented some code for both the Newton interpolation polynomials in Matlab, together with this error estimate. Now, when I make a plot of the error estimate it becomes surprisingly equal to the actual error $|f(x)-p_2(x)|$, so equal that I assume it's just the numerical precision that causes the deviation.

Will it always be like this, that the two errors will be equal, when you interpolate a polynomial of degree $n$ with a interpolating polynomial of degree $n-1$?

For my problem, the actual error will be on the form $e(x) = c_3x^3-(c_2-b_2)x^2+(c_1-b_1)x+(c_0-b_0)$, whereas the error estimate will be on form $\hat{e}(x)=c_3(x-x_0)(x-x_2)(x-x_3)$. Is it just "luck" that the coefficients in the actual error are "equal" to the coefficients in the estimated error? Is this something that can be proved, or?

-
The third derivative is constant! – André Nicolas Mar 1 '12 at 14:27
Yes, that's obvious, but I can't see that it answers the question, e.g. why $c_3(x_0x_1x_2) = (c_0-b_0)$, and the same for the rest of the coefficients in the resulting error. – ritualmagick Mar 1 '12 at 14:41
I take it you are quoting an "exact" formula for the interpolation error, except that as usual in Mean Value Theorem based formulas, we don't know $\xi$. So the error is exactly as given, with $\xi$ unknown except it lies in the interval. But the value of $\xi$ does not matter, because the third derivative is constant! – André Nicolas Mar 1 '12 at 15:41

The formula that you give for the absolute value of the error is exact, sort of. By that I mean that for every $x$, there is a $\xi(x)$ in our interval such that the error when you use the interpolating quadratic at $x$ is exactly the one obtained by putting $\xi=\xi(x)$ in the error formula.

In most cases, this kind of Mean Value Theorem information leads to estimates, but not to exact values, since we don't know $\xi(x)$.

However, here we are evaluating the third derivative of our cubic at $\xi(x)$. The third derivative is constant! So it doesn't matter what $\xi(x)$ is, that part of the error estimate does not change. The rest is an explicit polynomial in $x$. It follows that the error estimate and the actual error are equal, as you noticed computationally. Both are polynomials in $x$. Given any two polynomials, equality at all values of $x$ (or even at infinitely many values of $x$, or, for cubics, at $4$ values of $x$) means that the coefficients match.

Precisely the same thing happens when you use the same process to approximate a polynomial of degree $n+1$ by a Newton interpolating polynomial of degree $n$. If you look up the error estimate, you will see that it is a certain polynomial in $x$ times a term $f^{(n+1)}(\xi(x))$. (I like that version better than the absolute value version, since we also get information about the sign of the error.)

For a polynomial $f$ of degree $n+1$, the $(n+1)$-th derivative is constant, so
the term $f^{(n+1)}(\xi(x))$ is a constant independent of $x$. Thus the error estimate and the error are identically equal. Since they are both polynomials, that means their coefficients are equal.

-
Thanks to both of you for the explanations. It makes sense when you tell it like that; was just that I couldn't find a good way of convincing myself that it was like this. But hopefully that's what I will learn during the course. – ritualmagick Mar 1 '12 at 17:30
I must have been on crack or something when I wrote the comment above. It should say thank YOU, not both of you! :) – ritualmagick Mar 1 '12 at 17:46
@theTraumatizer: My fault, wrote both a comment and an answer. The reason I expanded the comment to an answer is that after the brief comment, you seemed to have remaining doubts. – André Nicolas Mar 1 '12 at 17:49