next up previous
Next: Neville algorithm Up: Lagrange Interpolation Previous: Generalized Lagrange Interpolation

Errors in Interpolation

No numerical result has meaning without an estimate of the error. The exponential integral function we are attempting to interpolate is not a polynomial, so a polynomial representation is bound to be inexact. If we construct the quartic polynomial interpolating all five points in the table above, and evaluate it at 0.15, we get

\begin{displaymath}
P_{01234}(0.15) = -1.1719
\end{displaymath}

whereas the correct value to six decimal digits is ${\rm Ei}(x) =
-1.16409$. The quartic polynomial is low by about 1%.

For any suitably smooth function $f(x)$ the discrepancy can be quantified somewhat through a theorem that states

\begin{displaymath}
f(x) = P_{0,\ldots{},n}(x)
+ \frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^n(x - x_i).
\end{displaymath}

where $\xi$ depends on $x$, but lies in the interval $[x_0,x_n]$. (The notation $f^{(n+1)}$ means the $n+1$st derivative of $f$.) In nearly all cases we don't know how $\xi$ depends on $x$. But sometimes we can find an upper bound $D$ on the magnitude of the $n+1$st derivative of $f$, which then gives us a bound on the error:

\begin{displaymath}
\vert f(x) - P_{0,\ldots{},n}(x)\vert < \frac{D}{(n+1)!}\vert\prod_{i=0}^n(x - x_i)\vert.
\end{displaymath}

Notice that the error bound vanishes at the interpolation points and rises in the intervals between them, as would be expected. If the points are equally spaced and the degree of the polynomial is high, the error tends to be largest in the first and last intervals of the table, but better toward the middle. This is the case for the ${\rm Ei}(x)$ function, as we can see in the figure. So we should avoid high degree polynomials when interpolating evenly spaced points.

\epsfig{bbllx=100,bblly=230,bburx=730,bbury=740,clip=,
file=polyerror.ps,width=125mm}


next up previous
Next: Neville algorithm Up: Lagrange Interpolation Previous: Generalized Lagrange Interpolation