[Math] Determine error in Neville’s Algorithm calculation

interpolationnumerical methods

I've been mulling over this problem for a while and I don't even know how to start it. The book is hopelessly vague.

The problem states

Neville's Algorithm is used to approximate $f(0)$ using $f(-2), f(-1), f(1), f(2)$. Suppose $f(-1)$ was understated by 2 and $f(1)$ was overstated by 3. Determine the error in the original calculation of the value of the interpolating polynomial to approximate $f(0)$.

According to the book, the proper answer is:

The incorrect approximation is $\frac{-f(2)}{6}+\frac{2f(1)}{3}+\frac{4}{3}+\frac{2f(-1)}{3} – \frac{f(-2)}{6}$ and the correct approximation is $\frac{-f(2)}{6}+\frac{2f(1)}{3}+\frac{2f(-1)}{3}-\frac{f(-2)}{6}$ so the incorrect approximation is $\frac{4}{3}$ too large.

But I have no idea how they even got this. Can someone please walk me through this problem? My homework assigns a similar problem, and this is the problem from the book that does a similar thing.

Thank you!

Best Answer

First of all, you should determine the interpolating polynomial $P(x)$ passing by the 4 points $(x_{-2},y_{-2}) = (-2,f(-2))$, $(x_{-1},y_{-1}) = (-1,f(-1))$, $(x_{1},y_{1}) = (1,f(1))$ and $(x_{2},y_{2}) = (2,f(2))$.

Then, evaluate the polynomial $P$ in $x=0$ and you should get the "correct approximation".

Now restart the whole process with a second interpolating polynomial $Q(x)$ passing by the 4 modified points. Again, evaluate the polynomial $Q$ in $x=0$ and you should find the "incorrect approximation".

The error, well, is just the difference between the two.

Related Solutions

[Math] Hermite Interpolation of $e^x$. Strange behaviour when increasing the number of derivatives at interpolating points.

I have found the cause, it seems that the Hermite Interpolation like other Interpolation methods most likely is unstable in the sense that if $\left(\tilde{x}_{i},\tilde{f}(\tilde{x}_{i})\right)$ are the perturbed values of $(x_i,f(x_i))$ say due to round off error or measurement then the resulting interpolating polynomials will wildly deviate from the true Hermite Interpolating polynomial (which of course is unique). Especially when the Lebesgue constant is large. To remedy this increase the working precision in the second line of the code above

x[k_] := N[Cos[(k + 1/2) \[Pi]/(n + 1)],20]

[Math] Interpolation error

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.

Best Answer

Related Solutions

[Math] Hermite Interpolation of $e^x$. Strange behaviour when increasing the number of derivatives at interpolating points.

[Math] Interpolation error

Related Question