1-D Polynomial Interpolation On Equispaced Vs. Chebyshev Node Distributions


This applet compares 1-D polynomial interpolation when the nodes (or data points) are distributed on an equispaced grid versus when they are distributed on a Chebyshev grid.

A common problem in many scientific discplines can be stated as follows:

Given N+1 samples (referred to as nodes) of some unknown function, say F, calculate an approximation to F so that further insights can be gained about the function.
One way of solving this problem is called polynomial interpolation. It involves finding a Nth degree polynomial that passes through all the N+1 nodes. One of the fundamental theorems about polynomials is that if we are given N+1 distinct nodes then we can find a unique polynomial of degree N that passes through all the nodes.

As you may have guessed, the way the nodes are distributed in the independent variable (commonly given as x or t) greatly affects the resulting polynomial. A common, somewhat obvious way of distributing the nodes is by spacing them equally over the interval you are interested in approximating the unknown function. This is referred to as an equispaced distribution.

Unfortunately, this type of distribution causes the interpolant to exhibit the Runge phenomenon (divergence of the interpolant near the ends of the interval. For example, if you select one of the interior nodes (represented by the black circles) of equispaced distribution in the applet below with your mouse and raise or lower it, the resulting polynomial interpolant to the given data will be displayed. You should notice the large oscillations near the ends of the interval; this is the Runge phenomenon.

It might seem intuitive that to overcome this problem we could simply just increase the number of nodes. However, it can be shown that the oscillations near the end of the interval will actually grow exponentially as the number of points is increased.

So, how can we offset this problem? The easiest way is to concentrate the nodes toward the ends of the interval. The question now becomes: How much grid clustering will result in the minimum amout of spurious oscillations? To answer this question we must turn to the area of orthogonal polynomials. Once there, we learn that the optimal distribution of nodes that minimizes the spurious oscillations is the Chebyshev distribution.

The Chebyshev distribution of N+1 data points, xj, on [-1,1] is given as follows:

xj = -cos(jpi/N), j=0,1,...,N
If you repeat the same example as you did on the equispaced nodes with the Chebyshev nodes, you will see that oscillations near the end of the intervals have been greatly reduced.

Further examples comparing the resulting polynomial interpolants to the 2 distributions can be performed with the applet. Please experiment around by either moving the nodes with your mouse, selecting the random option, or pressing one of the predefined function buttons.

An excellent reference on polynomial interpolation with different node distributions can be found on pages 23-31 in A Pratical Guide to Pseudospectral Methods by Bengt Fornberg. This book was the motivation for this applet.


Note: In order to run the applet above your browser must use the JRE 1.1 or higher


Home

Updated 02-Aug-2001