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.

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?

share|improve this question
    
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. –  militiaOfDeath 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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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. –  militiaOfDeath 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! :) –  militiaOfDeath 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

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.