Connecting the Dots

The Theory and Practice of Interpolation

MASS colloquium, November 12, 1996 and September 25, 1997
by Douglas N. Arnold

Abstract: If you know the value of a function at only a handful of points, what is the best way to guess to the function's value elsewhere? In other words: given a few dots on a graph, how should you connect them? This seemingly simple question inspired the rich subject known as interpolation theory. In this talk, which will be extensively illustrated with computer examples, I will survey some of the lovely, and often deep, mathematical results of this theory. We will mostly tour the classical world of polynomial interpolation, but will end with an excursion to the more modern land of piecewise polynomial interpolation and finite elements, and glimpse an application to the simulation of colliding black holes.

This colloquium was delivered in the McAllister Technology Classroom and consisted mostly of live graphical illustrations in Matlab, prepared Mathematica animations, prepared GIF images, some "slides" prepared in TeX, and occasional recourse to the blackboard. In response to popular demand, the materials for the lecture are available here.

Matlab files

These files can be downloaded to your site and run. This requires, of course, that you have Matlab, a commercial software product from Mathworks, installed at your site. The main file I used was ginterp.m, a Matlab file that allows you to enter points on a displayed x-y axis, either by clicking with the mouse or by typing Matlab commands (which may of course be prepared Matlab scripts), and then displaying the polynomial interpolant, piecewise linear interpolant, or cubic spline interpolant. Various options are available, including the ability to extend the interpolant beyond the first and last data points, that is, to extrapolate. Here is a screendump of ginterp.

I began the colloquium by using ginterp.m to demonstrate polynomial interpolation and to explore its utility in interpolating the twentieth century US census data. (It's utility for this purpose is doubtful, especially near the beginning and end of the century, and polynomial extrapolation is clearly hopeless--or else we're all in a lot of trouble!) The census data can be entered into ginterp by downloading the file pop.m and typing "pop" into the ginterp load box.

Next we explored the accuracy of polynomial interpolation using interpolation points with equally spaced abscissas. The accuracy is rather good for a simple bell shaped curved defined by a Gaussian (in the file gaussian.m which should be loaded into ginterp as "gaussian(16)" with the number giving the desired polynomial degree) but for the very similar looking bell shaped curve defined as a rational function in Runge's famous example (runge.m), the results are entirely different. What's so different about these examples?

Much of the difficulty with polynomial interpolation can be avoided by interpolating not at equally spaced points but at the Chebyshev points. This matlab file displays graphically the construction of the Chebyshev points. Loading the file rungec.m into ginterp shows that Chebyshev interpolation converges just fine for for Runge's example (but does a strikingly poor job of extrapolation).

Given all the pitfalls of polynomial interpolation, more robust procedures are needed. The best general purpose interpolation methods are based on piecewise polynomials. The simple case of piecewise linear interpolation and the more sophisticated method of cubic spline interpolation are both included in ginterp. An amusing example of spline interpolation is the matlab file plotsig.m, which uses cubic splines to interpolate President Clinton's signature.

Mathematica animations

I showed four animations created with Mathematica. They are in this gzipped Mathematica notebook, which can all be viewed with Mathematica (version 3 or above) from Wolfram Research. The animations are

In an earlier version I used Mathematica animation files, rather than a notebook. If you have the software to view them (e.g., motifps from pre-version 3 Mathematica), they are here: errprod.anim, errprodc.anim, absint.anim, and absintc.anim. The animations were created with errprod.m and absint.m.

GIF images

Here's a picture of Pafnuty Lvovitch Chebyshev (1821-1894). The end of the talk concentrated on piecewise polynomial interpolation in three dimensions, and particularly on some recent work concerning the adaptive construction of tetrahedral meshes for computing initial data for black hole collisions. (To learn more about the general scientific project, see the Binary Black Hole Alliance page. To learn more about our work see Arup Mukherjee's thesis.) I illustrated with these GIF files:

contour map of a 2D piecewise linear function on an adaptive mesh; this function is a metric component in axisymmetric binary black hole initial data for the Einstein equations
elevation of the same function
boundary faces of a coarse (about 3,000 elements) tetrahedral mesh for use in constructing 3D binary black hole initial data
zoom of the same
boundary faces of a fine (about 350,000 elements) adaptively constructed tetrahedral mesh for use in constructing 3D binary black hole initial data
zoom of the same
piecewise linear approximation on a tetrahedral mesh of binary black hole initial data (contour plot on a slice across the 3D domain)
zoom of the same
illustration an our algorithm for repeated bisection of a tetrahedron without degeneration of shape

Postscript file

This Postscript file contains prepared "slides" used at various times during the talk. These mostly contain precise statements of some of the theorems describing the convergence, and lack of thereof, of univariate polynomial interpolation. But there are a few other things as well, including a whole slide of different spelling's of Chebyshev's name.

Bonus for web visitors!

In Runge's example of Lagrange interpolation to a rational function, convergence takes place only in an interval of radius 3.633... about the origin. Here is another gzipped Mathematica notebook, explaining where this constant comes from and showing how to compute it.

Last modified November 28, 1996 by Douglas N. Arnold