Introduction to Numerical Methods/Interpolation

Objectives

  • understand interpolation
  • derive Newton’s divided difference method of interpolation
  • derive Lagrangian method of interpolation
  • apply the interpolation methods to solve problems
  • find derivatives and integrals of discrete functions using interpolation

Resources

Interpolation edit

Interpolation is the process of deriving a simple function from a set of discrete data points so that the function passes through all the given data points (i.e. reproduces the data points exactly) and can be used to estimate data points in-between the given ones. It is necessary because in science and engineering we often need to deal with discrete experimental data. Interpolation is also used to simplify complicated functions by sampling data points and interpolating them using a simpler function. Polynomials are commonly used for interpolation because they are easier to evaluate, differentiate, and integrate - known as polynomial interpolation.

It can be proven that given n+1 data points it is always possible to find a polynomial of order/degree n to pass through/reproduce the n+1 points.

Direct Method edit

Given n+1 data points the direct method assumes the following polynomial:

 

With n+1 values for   and the n+1 corresponding values for   we can solve for   by solving the n+1 simultaneous linear equations, which is known as the direct method.

For example, given two data points   and   we can use a linear function   to pass through the two data points:

 
 

Once we solve for  and   (the coefficients of  ) we can use the function as the basis for interpolation - estimating the missing data points in-between.

Newton's Method edit

In Newton's method the interpolating function is written in Newton polynomial(a.k.a Newton form). For example, given one data point   we can only derive a polynomial of order zero:  . Because   the newton polynomial of order zero is  .

Given two data points we can write Newton's polynomial in the form of  . Plugging in the two data points gives us

 
 

Obviously this function passes through both data points (i.e. accurately reproduces the two data points). The first derivative of the function at   is  , which matches the result from the forward divided difference method.

Given three data points we can write Newton's polynomial in the form of

 

Plugging in the three data points gives us

As   we get  
As   we get  
As  
we get
 

This third degree polynomial function passes all three data points (the second derivative and the third derivative at   and  match that from the divided difference method).

From the two examples we can see the coefficients of a Newton polynomial follow a pattern known as divided difference. For example  is called divided difference of order 1 (denoted as  ) because it depends on   and  . The divided difference notation can be used to write the general order (form) Newton polynomial:

 
 

Where

  because   by definition
 
 
 
 

We can calculate the coefficients of Newton polynomial using the following table

 

because

 
 

The following figures shows the dependency between the divided differences:

 

For example, given data points  ,  ,  , and   we can draw the following table:

 

The four data points lie on a polynomial of order 2, which is why the coefficient  ( ) is zero. Given   the result polynomial is:

 

Once the coefficients of a Newton's polynomial are solved, we can evaluate the polynomial function for any  . A Newton polynomial is often rewritten in a nested form:

 ,

because this nested form of interpolating polynomial is easier to evaluate because x only appears in the function n times.

For example, the nested form of a third order interpolating polynomial is:

 

The algorithm of Newton's method and its implementation can be found in this Jupyter notebook.

Lagrange Form edit

Lagrange polynomial is another form used for polynomial interpolation. It is called a form because with a given set of distinct points the interpolating polynomial is unique. We can arrive at the same polynomial through different methods.

The Lagrange form specifies the interpolation polynomial as:

 
 

where   is the order of the polynomial.

For example, given two data points we get   and

 

Obviously the function curve passes both data points. The first derivative also matches that of the divided difference method:

 

Spline Interpolation edit

Spline interpolation uses a number of polynomial functions to interpolate a set of data points with each polynomial for two adjacent data points. The Spline method is necessary because often times when the order of the polynomial become large polynomial interpolation shows oscillatory behavior (instability known as Runge's phenomenon). The following iPython notebook shows an example that suffers this issue: [1]

Spline method is not another method for finding polynomial interpolation of a discrete function, but instead it results in a piecewise polynomial (splines) in order to avoid the oscillatory behavior. The most common spline interpolations are linear, quadratic, and cubic splines. Linear interpolation uses lines to connect each pair of consecutive data points resulting in a piecewise interpolation.

 

A quadratic spline uses a quadratic polynomial to connect consecutive data points.

 

A function f(x) is a quadratic spline if the following conditions are true:

  1. The domain of   is an interval [a, b].
  2.   and   are continuous on [a, b].
  3. The data points   such that   and   is a polynomial of order at most 2 on each subinterval  .