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

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

Interpolation

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

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

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

With n+1 values for $x$ and the n+1 corresponding values for $y$ we can solve for $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 $(x_0,y_0)$ and $(x_1,y_1)$ we can use a linear function $y=f(x)=a_0+a_{1}x$ to pass through the two data points:

$y_0=a_0+a_1{x}_0$

$y_1=a_0+a_1{x}_1$

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

Newton's Method

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

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

$a_0=y_0$

$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 $x=x_0$ is $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

$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 $y_0=a_0$ we get $a_0=y_0$

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

As $y_2=a_0+a_1(x_2-x_0)+a_2(x_2-x_1)(x_2-x_0)$

we get

$\begin{array}{cc}{a}_2& =\frac{y_2-a_0-a_1(x_2-x_0)}{(x_2-x_1)(x_2-x_0)}\\ & =\frac{y_2-y_0-\frac{y_1-y_0}{x_1-x_0}(x_2-x_0)}{(x_2-x_1)(x_2-x_0)}\\ & =\frac{y_2-y_0-\frac{y_1-y_0}{x_1-x_0}((x_2-x_1)+(x_1-x_0))}{(x_2-x_1)(x_2-x_0)}\\ & =\frac{y_2-y_0-\frac{y_1-y_0}{x_1-x_0}(x_2-x_1)-(y_1-y_0)}{(x_2-x_1)(x_2-x_0)}\\ & =\frac{y_2-y_1-\frac{y_1-y_0}{x_1-x_0}(x_2-x_1)}{(x_2-x_1)(x_2-x_0)}\\ & =\frac{\frac{y_2-y_1}{x_2-x_1}-\frac{y_1-y_0}{x_1-x_0}}{x_2-x_0}\\ \end{array}$

This third degree polynomial function passes all three data points (the second derivative and the third derivative at $x_0$ and $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 as divided difference. For example$a_1=\frac{y_1-y_0}{x_1-x_0}$ is called divided difference of order 1 (denoted as $f[x_0,x_1]$) because it depends on $x_0$ and $x_1$. The divided difference notation can be used to write the general order (form) Newton polynomial:

$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)+...$

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

Where

$a_0=f[x_0]=y_0$ because $f[x_i]=y_i$ by definition

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

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

$\dots$

$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

$\begin{array}{ccccc}{x}_0& y_0=f[x_0]& & & \\ & & f[x_0,x_1]& & \\ x_1& y_1=f[x_1]& & f[x_0,x_1,x_2]& \\ & & f[x_1,x_2]& & f[x_0,x_1,x_2,x_3]\\ x_2& y_2=f[x_2]& & f[x_1,x_2,x_3]& \\ & & f[x_2,x_3]& & \\ x_3& y_3=f[x_3]& & & \end{array}$

because

$f[x_i]=y_i$

$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 $(1,6)$, $(2,11)$, $(3,18)$, and $(4,27)$ we can draw the following table:

$\begin{array}{cccccc}i& x_i& y_i& f[x_i,x_{i+1}]& f[x_i,x_{i+1},x_{i+2}]& f[x_i,x_{i+1},x_{i+2},x_{i+3}]\\ 0& x_0=1& \begin{array}{cc}{y}_0& =f[x_0]\\ & =6\end{array}& \begin{array}{cc}f[x_0,x_1]& =\frac{f[x_1]-f[x_0]}{x_1-x_0}\\ & =\frac{11-6}{2-1}\\ & =5\end{array}& \begin{array}{cc}f[x_0,x_1,x_2]& =\frac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0}\\ & =\frac{7-5}{3-1}\\ & =1\end{array}& \begin{array}{cc}& f[x_0,x_1,x_2,x_3]\\ & =\frac{f[x_1,x_2,x_3]-f[x_0,x_1,x_2]}{x_3-x_0}\\ & =\frac{1-1}{4-1}\\ & =0\end{array}\\ 1& x_1=2& \begin{array}{cc}{y}_1& =f[x_1]\\ & =11\end{array}& \begin{array}{cc}f[x_1,x_2]& =\frac{f[x_2]-f[x_1]}{x_2-x_1}\\ & =\frac{18-11}{3-2}\\ & =7\end{array}& \begin{array}{cc}f[x_1,x_2,x_3]& =\frac{f[x_2,x_3]-f[x_1,x_2]}{x_3-x_1}\\ & =\frac{9-7}{4-2}\\ & =1\end{array}& \\ 2& x_2=3& \begin{array}{cc}{y}_2& =f[x_2]\\ & =18\end{array}& \begin{array}{cc}f[x_2,x_3]& =\frac{f[x_3]-f[x_2]}{x_3-x_2}\\ & =\frac{27-18}{4-3}\\ & =9\end{array}& & \\ 3& x_3=4& \begin{array}{cc}{y}_3& =f[x_3]\\ & =27\end{array}& & & \end{array}$

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

$\begin{array}{cc}y& =a_0+a_1(x-x_0)+a_2(x-x_1)(x-x_0)\\ & =6+5\times (x-1)+1\times (x-2)(x-1)\\ & =x^2+2x+3\end{array}$

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

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

$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 this Jupyter notebook.

Lagrange Form

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:

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

$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 $n$ is the order of the polynomial.

For example, given two data points we get $n=1$ and

$\begin{array}{cc}f(x)& =L_{0}f(x_0)+L_{1}f(x_1)\\ & =\frac{x-x_1}{x_0-x_1}f(x_0)+\frac{x-x_0}{x_1-x_0}f(x_1)\\ \end{array}$

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

$\begin{array}{cc}{f}^{\prime }(x)& =\frac{f(x_0)}{x_0-x_1}+\frac{f(x_1)}{x_1-x_0}\\ & =\frac{f(x_1)-f(x_0)}{x_1-x_0}\\ \end{array}$

Spline Interpolation

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