Interactive Educational Modules in
Scientific Computing

Newton Interpolation

This modules illustrates Newton interpolation. For an ordered set of points (t_i, y_i),  i = 1,…,n, the j-th Newton basis function is given by π_j (t) = (t − t₁) · · · (t − t_j−1). Because of the resulting triangular structure of the Newton basis matrix, the Newton interpolant can be computed incrementally as data points are added. The resulting interpolating polynomial is independent of the ordering of the data points.

First the user selects a set of data points by clicking either Choose Random Points to generate all the points randomly, or Choose Specific Points to specify points individually. In the latter case, the user clicks on the graph to indicate the locations of the points. To prevent points from being too close to each other, they may not be chosen in the shaded buffer zone surrounding existing points. After the set of data points has been chosen, the user clicks Apply to have them take effect. Now the user clicks on the points one at a time in any desired order to build the Newton interpolant incrementally. As each point is clicked, the plotted interpolant changes to include the new point, and the resulting polynomical is expressed below as a linear combination of the Newton basis functions. At any time during this process, Reset Interpolant clears the interpolant while retaining the current set of points. By resetting the interpolant, the user can observe that the final interpolant is independent of the order in which the points are selected.

Reference: Michael T. Heath, Scientific Computing, An Introductory Survey, 2nd edition, McGraw-Hill, New York, 2002. See Section 7.3.3, especially Example 7.4.

Developers: Evan VanderZee and Michael Heath