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:

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 aGivenN+1samples (referred to as nodes) of some unknown function, sayF, calculate an approximation toFso that further insights can be gained about the function.

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, x_{j}, on [-1,1] is given as follows:

xIf 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._{j}= -cos(jpi/N), j=0,1,...,N

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

Updated 02-Aug-2001