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 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.
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.
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 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 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:
- The domain of is an interval [a, b].
- and are continuous on [a, b].
- The data points such that and is a polynomial of order at most 2 on each subinterval .