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

• Direct method chapter
• Newton's method chapter
• Lagrange method chapter
• Spline method chapter
• A Chronology of Interpolation
• NIST Digital Library of Mathematical Functions

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 aspolynomial 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:

${\displaystyle y=f(x)=a_0+a_{1}x+a_2{x}^2+...+a_n{x}^n}$

With n+1 values for${\displaystyle x}$ and the n+1 corresponding values for${\displaystyle y}$ we can solve for${\displaystyle a_0,a_1,...,a_n}$ by solving the n+1 simultaneous linear equations, which is known as the direct method.

For example, given two data points${\displaystyle (x_0,y_0)}$ and${\displaystyle (x_1,y_1)}$ we can use a linear function${\displaystyle y=f(x)=a_0+a_{1}x}$ to pass through the two data points:

${\displaystyle y_0=a_0+a_1{x}_0}$

${\displaystyle y_1=a_0+a_1{x}_1}$

Once we solve for${\displaystyle a_0}$and${\displaystyle a_1}$ (the coefficients of${\displaystyle f(x)}$) 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 inNewton polynomial(a.k.a Newton form). For example, given one data point${\displaystyle (x_0,y_0)}$ we can only derive a polynomial of order zero:${\displaystyle y=f(x)=a_0}$. Because${\displaystyle f(x_0)=y_0}$ the newton polynomial of order zero is${\displaystyle y=f(x)=y_0}$.

Given two data points we can write Newton's polynomial in the form of${\displaystyle y=f(x)=a_0+a_1(x-x_0)}$. Plugging in the two data points gives us

${\displaystyle a_0=y_0}$

${\displaystyle a_1=\frac{y_1-y_0}{x_1-x_0}}$

Obviously this function passes through both data points (i.e. accurately reproduces the two data points). The first derivative of the function at${\displaystyle x=x_0}$ is${\displaystyle f^{\prime }(x_0)=a_1=\frac{y_1-y_0}{x_1-x_0}}$, which matches the result from the forward divided difference method.

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

${\displaystyle y=f(x)=a_0+a_1(x-x_0)+a_2(x-x_1)(x-x_0)}$

Plugging in the three data points gives us

As${\displaystyle y_0=a_0}$ we get${\displaystyle a_0=y_0}$

As${\displaystyle y_1=a_0+a_1(x_1-x_0)}$ we get${\displaystyle a_1=\frac{y_1-y_0}{x_1-x_0}}$

As${\displaystyle y_2=a_0+a_1(x_2-x_0)+a_2(x_2-x_1)(x_2-x_0)}$

we get

This third degree polynomial function passes all three data points (the second derivative and the third derivative at${\displaystyle x_0}$ and${\displaystyle x_1}$match that from the divided difference method).

From the two examples we can see the coefficients of a Newton polynomial follow a pattern known asdivided difference. For example${\displaystyle a_1=\frac{y_1-y_0}{x_1-x_0}}$ is called divided difference of order 1 (denoted as${\displaystyle f[x_0,x_1]}$) because it depends on${\displaystyle x_0}$ and${\displaystyle x_1}$. The divided difference notation can be used to write the general order (form) Newton polynomial:

${\displaystyle f(x)=f[x_0]+f[x_0,x_1](x-x_0)+f[x_0,x_1,x_2](x-x_0)(x-x_1)+...}$

${\displaystyle +f[x_0,x_1,x_2,...,x_n](x-x_0)(x-x_1)(x-x_2)...(x-x_{n-1})}$

Where

${\displaystyle a_0=f[x_0]=y_0}$ because${\displaystyle f[x_i]=y_i}$ by definition

${\displaystyle a_1=f[x_0,x_1]=\frac{f[x_1]-f[x_0]}{x_1-x_0}}$

${\displaystyle a_2=f[x_0,x_1,x_2]=\frac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0}}$

${\displaystyle \dots }$

${\displaystyle a_k=f[x_0,x_1,x_2,\dots ,x_{k-1},x_k]=\frac{f[x_1,x_2,\dots ,x_{k-1},x_k]-f[x_0,x_1,x_2,\dots ,x_{k-1}]}{x_k-x_0}}$

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

because

${\displaystyle f[x_i]=y_i}$

${\displaystyle f[x_i,x_{i+1}]=\frac{f[x_{i+1}]-f[x_i]}{x_{i+1}-x_i}}$

The following figures shows the dependency between the divided differences:

For example, given data points${\displaystyle (1,6)}$,${\displaystyle (2,11)}$,${\displaystyle (3,18)}$, and${\displaystyle (4,27)}$ we can draw the following table:

The four data points lie on a polynomial of order 2, which is why the coefficient${\displaystyle a_3}$(${\displaystyle f[x_0,x_1,x_2,x_3]}$) is zero. Given${\displaystyle [a_0,a_1,a_2]=[6,5,1]}$ the result polynomial is:

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

${\displaystyle f(x)=a_0+(x-x_0)(a_1+(x-x_1)(a_2+(x-x_2)(a_3+...+a_n(x-x_{n-1}))...)}$,

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:

${\displaystyle f(x)=a_0+(x-x_0)(a_1+(x-x_1)(a_2+(x-x_2)a_3))}$

The algorithm of Newton's method and its implementation can be found in thisJupyter 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:

${\displaystyle f_n(x):=\sum _{i=0}^n{L}_i(x)f(x_i)}$

${\displaystyle L_i(x):=\prod _{\begin{array}{c}0\le m\le n\\ m\ne i\end{array}}\frac{x-x_m}{x_i-x_m}=\frac{(x-x_0)}{(x_i-x_0)}\cdots \frac{(x-x_{i-1})}{(x_i-x_{i-1})}\frac{(x-x_{i+1})}{(x_i-x_{i+1})}\cdots \frac{(x-x_n)}{(x_i-x_n)},}$

where${\displaystyle n}$ is the order of the polynomial.

For example, given two data points we get${\displaystyle n=1}$ 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 asRunge'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.

Aquadratic 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${\displaystyle f(x)}$ is an interval [a, b].
2. ${\displaystyle f(x)}$ and${\displaystyle f^{\prime }(x)}$ are continuous on [a, b].
3. The data points${\displaystyle x_i}$ such that and${\displaystyle f(x)}$ is a polynomial of order at most 2 on each subinterval${\displaystyle [x_i,x_{i+1}]}$.

• Book:Introduction to Numerical Methods