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

• The error product, a polynomial which governs the accuracy of polynomial interpolation. The animation shows the product for eighth degree polynomial interpolation using equally spaced points, and then shows how the maximum of the error product can be reduced by moving some of the points.
• This procedure taken to its logical extreme leads to the Chebyshev points.
• A demonstration of the divergence of Lagrange interpolation with equally spaced points for the absolute value function.
• A demonstration of the convergence of Lagrange interpolation with Chebyshev points for the absolute value function.

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:

black-hole-2d-contour.gif

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

black-hole-2d-elev.gif

elevation of the same function

p9.mesh.coar.nzoom.gif

boundary faces of a coarse (about 3,000 elements) tetrahedral mesh for use in constructing 3D binary black hole initial data

p9.mesh.coar.zoom.gif

zoom of the same

p9.mesh.fine.nzoom.gif

boundary faces of a fine (about 350,000 elements) adaptively constructed tetrahedral mesh for use in constructing 3D binary black hole initial data

p9.mesh.fine.zoom.gif

zoom of the same

p9nzoom.gif

piecewise linear approximation on a tetrahedral mesh of binary black hole initial data (contour plot on a slice across the 3D domain)

p9zoom.gif

zoom of the same

bisect3.gif

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