Lab 07: Interpolation

The problem of interpolation is that,

"given a set of $K$ experimentally determined points $(x_i, y_i), i = 1, 2, \ldots, K$, we need to determine the value of an unknown $y_u$ at a previously unseen point $x_u$ that lies somewhere in between."
The standard way of solving the problem is to fit a curve through the known points and use the curve to find the values at unseen or intermediate points.

In this lab, we implement three solutions to the interpolation problem.

  1. Piecewise linear
  2. Vandermonde polynomial
  3. Lagrange polynomial

Piecewise Linear Interpolation

In this simple but popular method, we fit straight lines between adjacent known points.

  1. Let the unknown point $x$ lie between known points $(x_i, y_i)$ and $(x_{i+1}, y_{i+1})$.
  2. The unknown value $y_u$ is given by fitting the line $y = ax + b$ where $$ a = \frac{y_{i+1} - y_i}{x_{i+1} - x_i}~ \mbox{and}~ b = y_i $$The unknown $y_u$ at a newly given $x_u$ is $$ y_u = a(x_u - x_i) + b $$
Use the code cells below to write your code.

In [ ]:
import numpy as np
from matplotlib import pyplot as plt      # For plotting data
np.set_printoptions(suppress=True, precision=2)
In [ ]:
### The data is given in this cell for you
X = np.arange(1, 5, 0.5)
Y = np.random.random(X.shape[0]) * 10
# Let us plot instead of printing the data points
plt.grid(True)
plt.plot(X, Y, 'bo')
plt.show()
In [ ]:
### Write your interpolation code here
def linear_interpolation(X, Y, x_u) :

    
    
    return a, b
In [ ]:
### Test your code here first by calculating and then plotting
### (x_u, y_u)
a, b = linear_interpolation(X, Y, x_u)
x_u = 2.15
y_u = a * x_u + b

### Let us plot the data and see if it looks good!
plt.grid(True)
plt.plot(X, Y, 'b.')
plt.plot(X, Y, 'xkcd:lime')
plt.plot(x_u, y_u, 'ro')
plt.show()

Vandermonde Polynomial

In this method, we fit a $K-1$ degree polynomial $$ y = a_0 + a_1x + a_2x^2 + \ldots + a_{K-1}x^{K-1} $$ through the $K$ given points $(x_i, y_i), i=1, 2, \ldots, K$. It is done by defining the following.

  1. $$ A = \left(\begin{array}{ccccc} 1 & x_1 & x_1^2 & \ldots & x_1^{K-1} \\ 1 & x_2 & x_2^2 & \ldots & x_2^{K-1} \\ & & \vdots& \vdots & \\ 1 & x_K & x_K^2 & \ldots & x_K^{K-1} \end{array}\right) $$
  2. $$ B = \left(\begin{array}{c} y_1 \\ y_2 \\ \vdots \\ y_K \end{array}\right) $$
We then solve for the coefficient matrix $C$ by using gauss elimination and back substitution in the equation $$AC = B$$

In [14]:
### Write your code here
def vandermonde_interpolation(X, Y) :
    C = np.zeros(Y.shape[0])
    
    
    return C

Lagrange Polynomial

Lagrange method is a clever way of getting the $K-1$ degree polynomial by direct calculations of the coefficient $a_0, a_1, \ldots, a_{K-1}$.

At an unknown value $x_u$, the polynomial is calculated as $$ y_u = \frac{(x-x_1)(x-x_2)\ldots(x-x_K)} {(x_0-x_1)(x_0-x_2)\ldots(x_0-x_K)}y_0 + \frac{(x-x_0)(x-x_2)\ldots(x-x_K)} {(x_1-x_0)(x_1-x_2)\ldots(x_1-x_K)}y_1 + \ldots + \frac{(x-x_1)(x-x_2)\ldots(x-x_{K-1})} {(x_{K}-x_1)(x_{K}-x_2)\ldots(x_K-x_{K-1})} $$

In [15]:
### Implement Lagrange Polynomial code here
def lagrange_interpolation(X, Y) :
    lagrange = np.zeros(Y.shape[0])
    
    
    return lagrange