Skip to main content

Section 22.1 Estimating the error of polynomial interpolation

One of the uses of polynomial interpolation (Chapter 21) is to approximate a possible complicated function \(y = f(x)\) by a polynomial, interpolating the values of the function at some points \(x_1, \dots, x_n\text{.}\) Indeed, this is what we tried in Exercise 21.4.3 for the functions \(f(x)=\cos x\) and \(f(x)=\cos 2x\text{,}\) with mixed success. The following theorem is a first step toward understanding what is going on.

Suppose a polynomial \(p\) of degree less than \(n\) interpolates a smooth function \(f\) at some points \(x_1, \dots, x_n\) of an interval \([a, b]\text{.}\) Then for each \(x\in [a, b]\) there exists a point \(\xi \in [a, b]\) such that

\begin{equation} f(x) - p(x) = \frac{f^{(n)}(\xi)}{n!} \prod_{k=1}^n (x-x_k)\label{eq-error-polynomial-interpolation}\tag{22.1.1} \end{equation}

where \(f^{(n)}\) is the \(n\)th derivative of \(f\text{.}\)

The above theorem is easier to prove than one might expect. If \(x\) is one of interpolation points, then both sides of (22.1.1) are equal to 0. Suppose \(x\) is not equal to any interpolation point. Then we can let

\begin{equation*} A = \frac{f(x) - p(x)}{ \prod_{k=1}^n (x-x_k) } \end{equation*}

so that \(f(x) -p(x) - A \prod_{k=1}^n (x-x_k) = 0\text{.}\) Consider the function

\begin{equation} g(t) = f(t) -p(t) - A \prod_{k=1}^n (t-x_k)\label{eq-proof-poly-interp-error}\tag{22.1.2} \end{equation}

and notice that it has at least \(n+1\) roots on the interval \([a, b]\text{,}\) namely \(x, x_1, x_2, \dots, x_n\text{.}\) Between any two roots of \(g\) there is a root of \(g'\text{:}\) this is Rolle's theorem. Therefore, \(g'\) has at least \(n\) roots on the interval \([a, b]\text{.}\) Repeat this argument: \(g''\) has at least \(n-1\) roots, … , \(g^{(n)}\) has at least 1 root. Call this root \(\xi\) and notice that according to (22.1.2),

\begin{equation*} g^{(n)}(\xi) = f^{(n)}(\xi) - 0 - A n! \end{equation*}

hence \(A = f^{(n)}(\xi) / n!\text{,}\) completing the proof of (22.1.1).

What guidance can we extract from (22.1.1)? To minimize the interpolation error, we want the product

\begin{equation} \prod_{k=1}^n (x-x_k)\label{eq-product-interp-points}\tag{22.1.3} \end{equation}

to be small on the interval \([a, b]\text{.}\) If the points \(x_1, \dots, x_n\) are equally spaced, the product (22.1.3) can become large toward the endpoints, as the following Matlab example shows for 11 points on the interval \([0, 7]\text{.}\)

Plot the product (22.1.3) for 11 equally spaced points on the interval \([0, 7]\text{.}\)

Answer
a = 0;
b = 7;
n = 11;
x = linspace(a, b, n);     % interpolation points x1, ..., xn.
t = linspace(a, b, 1000);  % points for plotting
plot(t, prod(t - x'))

Using larger \(n\) in Example 22.1.1 would only make things worse. This indicates that polynomial interpolation at a large number of equally spaced points is unadvisable. As it was with numerical integration, a smarter choice of points \(x_1, \dots, x_n\) is possible, and once again it is provided by the roots of certain orthogonal polynomials.