What’s that shape? Instability in interpolation

cover of Numerical Analysis: Theory and Experiments
A curious shape on the cover of Numerical Analysis: Theory and Experiments

Interpolation is a surprisingly difficult problem. The basic idea is simple: given a set of points in the xy-plane, fill the gaps to produce a continuous function. A simple approach is piecewise-linear interpolation:

points in the planepiecewise-linear interpolant

However, the resulting function is not smooth. Lack of smoothness can cause various problems—theorems may not apply, methods may fail. Plus, if the data points are assumed to come from some smooth function lurking in the background, then a nonsmooth interpolant will likely not produce a very close fit.

A natural candidate for a smooth interpolant is a polynomial. Polynomials are ubiquitous in high school algebra, most often written in the form c_0 + c_1 x + c_2 x^2 + \cdots + c_n x^n. Using calculus, a degree-n polynomial can alternatively be characterized as a function whose (n+1)th derivative equals zero. Polynomials are smooth and relatively easy to work with.

The problem of polynomial interpolation is to find a single high-degree polynomial to fit the data points rather than a sequence of short linear functions. A robust solution to this problem is harder than we might expect.

Let f be a smooth function, and consider replacing f by a close-fitting polynomial p. This might be desirable if f is defined by a complicated formula or if it is defined implicitly as the solution of an equation or an indefinite integral, for example. A natural idea is to sample f at regularly spaced points—

Runge's functionsample on uniformly spaced points

—and then to construct a polynomial p whose graph passes through those points. Unfortunately, this often fails! The classic example is Runge’s function f(x) = 1/(1+25x^2). The plotted function f above is in fact Runge’s function. The polynomial that interpolates the data points above is the following:

Runge phenomenon

This is bad! The polynomial introduces extreme oscillations that are not present in the graph of f. Even worse, the oscillations increase in frequency and amplitude as the number of data points is increased. This phenomenon is known as the Runge phenomenon.

There is a surprisingly simple resolution. Instead of sampling f at uniformly spaced points, sample on a Chebyshev grid

    \[ x_i = \cos(i \pi/n), \quad i = 0,\dots,n. \]

Runge's function againsample on a Chebyshev grid

Notice how the Chebyshev points are more dense near the endpoints of the interval, where the oscillations were previously most severe. As long as f is sufficiently smooth, the Runge phenomenon will not occur.

Chebyshev interpolant

The cover of my book Numerical Analysis: Theory and Experiments features the following shapes:

Runge phenomenon in the complex planesuccess of Chebyshev interpolation in the complex plane

These show polynomial interpolants in the complex plane. The “wavy ribbon” comes from uniformly spaced sample points, while the “saddle” comes from Chebyshev points. In the first case, we see a more complete picture of the Runge phenomenon. In the second case, we see that the Chebyshev interpolant captures behavior not just along the real line but also into the complex plane.

The Runge phenomenon occurs when there are singularities in the complex plane sufficiently close to the interpolation interval on the real line. In the case of Runge’s function f(z) = 1/(1+25z^2), there are singularities at z=\pm (1/5)\sqrt{-1}. These are suggested by the two “pommels” at the top of the saddle. If the graph were extended farther into the complex plane, these peaks would explode to infinity. Chebyshev interpolation performs well even in the presence of such infinite singularities.

The Runge phenomenon is discussed in chapter 9 of my book, along with another, arguably greater, danger called “ill conditioning.”