Interpolation Error Theorem

The interpolation error theorem quantifies how well a polynomial approximates a function, revealing the dependence on data spacing and function smoothness.

TheoremPolynomial Interpolation Error

Let $f \in C^{n+1}[a,b]$ and let $p_n$ be the polynomial of degree $\leq n$ interpolating $f$ at distinct nodes $x_0, \ldots, x_n \in [a,b]$ . Then for any $x \in [a,b]$ , there exists $\xi_x \in (a,b)$ such that: $f(x) - p_n(x) = \frac{f^{(n+1)}(\xi_x)}{(n+1)!} \prod_{i=0}^n (x - x_i)$

Consequently: $\|f - p_n\|_\infty \leq \frac{M_{n+1}}{(n+1)!} \|\omega_{n+1}\|_\infty$ where $M_{n+1} = \max_{x \in [a,b]} |f^{(n+1)}(x)|$ and $\omega_{n+1}(x) = \prod_{i=0}^n (x - x_i)$ .

This theorem has a form similar to Taylor's theorem, but the error depends on the product $\omega_{n+1}(x)$ rather than $(x-x_0)^{n+1}$ . The choice of interpolation nodes significantly affects $\|\omega_{n+1}\|_\infty$ .

ExampleError for Chebyshev vs Uniform Nodes

On $[-1,1]$ with $n+1$ nodes:

Uniform spacing: $\|\omega_{n+1}\|_\infty = O(1)$ (grows unboundedly with $n$ )

Chebyshev nodes: $\|\omega_{n+1}\|_\infty = 2^{-n}$ (exponentially decaying)

For $f(x) = e^x$ on $[-1,1]$ with $n=5$ :

Uniform: max error $\approx 0.005$
Chebyshev: max error $\approx 0.0002$

The factor-of-25 improvement demonstrates the value of optimal node placement.

Remark

Implications:

If $f$ is smooth ( $f^{(n+1)}$ bounded), error decreases as $O(h^{n+1})$ where $h = \max_i |x_{i+1} - x_i|$
For analytic functions with bounded derivatives, Chebyshev interpolation converges exponentially
For functions with singularities, convergence can be arbitrarily slow regardless of node choice

The theorem explains the Runge phenomenon: interpolating $f(x) = 1/(1+25x^2)$ with equally-spaced nodes gives $M_{n+1} = O((n+1)!)$ , which grows faster than $(n+1)!$ shrinks, causing divergence near endpoints.

The error formula extends to piecewise polynomial approximation. For cubic splines with spacing $h$ , the error is $O(h^4)$ for $C^4$ functions, independent of the number of knots. This makes splines more practical than global polynomial interpolation for large datasets.

Understanding interpolation error guides numerical method design: finite difference formulas derive from polynomial interpolation, inheriting the same error behavior. Higher-order methods require more function evaluations but achieve faster convergence, balancing computational cost against accuracy requirements.