Open Educational Resources

Piecewise Interpolation: Piecewise Linear Spline Interpolation

Piecewise Linear (Piecewise Affine) Spline Interpolation

Given a set of k data points (x_1,y_1),(x_2,y_2),\cdots, (x_k,y_k), a piecewise linear (piecewise affine) spline can be defined as:

    \[ y=\begin{cases} a_1x+b_1,&x\in [x_1, x_2) \\ a_2x+b_2,&x\in [x_2, x_3) \\ \vdots & \vdots \\ a_{k-1}x+b_{k-1},&x\in [x_{k-1}, x_k] \end{cases} \]

The k data points have k-1 intervals. The linear function for each interval is defined using two coefficients, and therefore, we need to find 2(k-1) coefficients a_1,b_1,a_2,b_2,\cdots,a_{k-1},b_{k-1}. The coefficients a_i and b_i can be found by solving the two equations:

    \[\begin{split} y_i&=a_ix_i + b_i\\ y_{i+1}&=a_ix_{i+1}+b_i \end{split} \]

Therefore:

    \[\begin{split} a_i&=\frac{y_i-y_{i+1}}{x_i-x_{i+1}}\\ b_i&=\frac{y_{i+1}x_i-y_ix_{i+1}}{x_i-x_{i+1}} \end{split} \]

Example

Consider the following 11 data points: (-1.00,0.038),(-0.80,0.058),(-0.60,0.100),(-0.4,0.200),(-0.20,0.500),(0.00,1.000),(0.20,0.500),(0.40,0.200),(0.60,0.100),(0.80,0.0580),(1.00,0.038) which were generated using the Runge function. Find the explicit representation of the linear spline interpolating function for these data points.

Solution

There are 11 data points surrounding 10 intervals. For each interval i, a set of coefficients a_i and b_i are required for the linear interpolation. For the first interval, the coefficients are:

    \[\begin{split} a_1&=\frac{y_1-y_2}{x_1-x_2}=\frac{0.038-0.058}{-1-(-0.8)}=0.1\\ b_1&=\frac{y_2x_1-y_1x_2}{x_1-x_2}=\frac{0.058(-1)-0.038(-0.8)}{-1-(-0.8)}=0.138 \end{split} \]

Similarly:

    \[\begin{split} a_2&=\frac{y_2-y_3}{x_2-x_3}=\frac{0.058-0.1}{-0.8-(-0.6)}=0.21\\ b_2&=\frac{y_3x_2-y_2x_3}{x_2-x_3}=\frac{0.1(-0.8)-0.058(-0.6)}{-0.8-(-0.6)}=0.226 \end{split} \]

Repeating for the other coefficients, the required explicit equation has the form:

    \[ y=\begin{cases} 0.1x+0.138,&x\in [-1, -0.8) \\ 0.21x+0.226,&x\in [-0.8, -0.6) \\ 0.5x+0.4,&x\in [-0.6, -0.4)\\ 1.5x+0.8,&x\in [-0.4, -0.2)\\2.5x+1,&x\in [-0.2, 0.0)\\-2.5x+1,&x\in [0.0, 0.2)\\-1.5x+0.8,&x\in [0.2, 0.4)\\-0.5x+0.4,&x\in [0.4, 0.6)\\-0.21x+0.226,&x\in [0.6, 0.8)\\-0.1x+0.138,&x\in [0.8, 1.0] \end{cases} \]

Notice that for the procedure to work, the x components of the data points have to satisfy: x_1<x_2<\cdots<x_{k}. The following Mathematica code utilizes a user defined procedure “Spline1” that creates the required piecewise linear function.

View Mathematica Code
Data = {{-1, 0.038}, {-0.8, 0.058}, {-0.60, 0.10}, {-0.4,0.20}, {-0.2, 0.50}, {0, 1}, {0.2, 0.5}, {0.4, 0.2}, {0.6,0.1}, {0.8, 0.058}, {1, 0.038}};
Spline1[Data_] := (
k1 = Length[Data] - 1;  
atable = Table[(Data[[i, 2]] - Data[[i + 1, 2]])/(Data[[i, 1]] -Data[[i + 1, 1]]), {i, 1, k1}]; 
btable = Table[(Data[[i + 1, 2]]*Data[[i, 1]] -Data[[i, 2]]*Data[[i + 1, 1]])/(Data[[i, 1]] - Data[[i + 1, 1]]), {i, 1, k1}]; 
pf = Table[{atable[[i]] x + btable[[i]],Data[[i, 1]] <= x <= Data[[i + 1, 1]]}, {i, 1, k1}]; 
Piecewise[pf]
)
y = Spline1[Data]
a = Plot[{y, yactual}, {x, -1, 1}, Epilog -> {PointSize[Large], Point[Data]}, AxesLabel -> {"x", "y1"}, ImageSize -> Medium, PlotRange -> All,  PlotLegends -> {"y1", "yactual"}, PlotLabel -> "Linear splines"]
View Python Code
import numpy as np
import matplotlib.pyplot as plt
Data = [[-1, 0.038], [-0.8, 0.058], [-0.60, 0.10], [-0.4,0.20], [-0.2, 0.50], [0, 1], [0.2, 0.5], [0.4, 0.2], [0.6, 0.1], [0.8, 0.058], [1, 0.038]]
def Spline1(x, Data):
  k1 = len(Data) - 1
  atable = [(Data[i][1] - Data[i + 1][1])/(Data[i][0] - Data[i + 1][0]) for i in range(k1)] 
  btable = [(Data[i + 1][1]*Data[i][0] - Data[i][1]*Data[i + 1][0])/(Data[i][0] - Data[i + 1][0]) for i in range(k1)] 
  display([['{:15}'.format(str(round(atable[i],3))+'x + '+str(round(btable[i],3))),
            '{:15}'.format(str(round(Data[i][0],3))+' <=x<= '+str(round(Data[i + 1][0],3)))] for i in range(k1)])
  return np.piecewise(x, [(x >= Data[i][0])&(x <= Data[i + 1][0]) for i in range(k1)],
                         [lambda x, j=i: atable[j]*x + btable[j] for i in range(k1)])
x = np.arange(-1,1,0.01)
y = Spline1(x, Data)
yactual = 1/(1 + 25*x**2)
plt.plot(x,yactual, label="yactual")
plt.plot(x, y, label="y1")
plt.scatter([point[0] for point in Data],[point[1] for point in Data], c='k')
plt.title("Linear splines")
plt.xlabel("x"); plt.ylabel("y1")
plt.legend(); plt.grid(); plt.show()

Lecture Video



Leave a Reply

Your email address will not be published.