Spline Interpolation
Polynomial interpolation involves finding a polynomial of order ‘n’ that passes
through ‘n+1’ data points
Problems:
When ‘n’ becomes large, in many cases, polynomials can lead to erroneous
results because of round-off errors and overshoot.
Solution:
Use lower-order polynomials to subsets (2 consecutive data points) of data
points Such connecting polynomials are called spline functions.
The most common spline interpolations are;
linear
quadratic
cubic splines
Spline Interpolation vs Polynomial Interpolation
Splines eliminate oscillations by using
small subsets of points for each
interval rather than every point.
This is especially useful when there are
jumps (sudden changes) in the data:
a) 3rd order polynomial
b) 5th order polynomial
c) 7th order polynomial
d) Linear spline
seven 1st order polynomials
generated by using pairs of
points at a time
Spline usually provide superior
approximation of function that have
local, abrupt changes.
a) Linear Spline Interpolation
Data points: (x0,y0), (x1,y1),…….,(xn-1,yn-1), (xn,yn)
Linear spline fit a straight line for each interval between knots & the data must
be in order.
Need to find the spline
Spline function for each interval
knot function
a) Linear Spline Interpolation
f(x 1 ) f(x 0 )
f(x) f(x 0 ) (x x 0 ), for x 0 x x 1
x1 x0
f(x) f(x 0 ) m 0 (x x 0 ) for x 0 x x 1
f(x) f(x 1 ) m 1 (x x 1 ) for x 1 x x 2
.
f(x) f(x n -1 ) m (n -1)(x x n -1 ) for x n -1 x x n
Linear spline function for
each interval
f(x i 1 ) f(x i )
Where mi (slope connecting two points)
x i 1 x i
These equations can be used to evaluate the function at any point between x0
and xn by locating the interval where the point lies same a linear interpolation!
a) Linear Spline Interpolation
Disadvantages:
Functions are not smooth.
At knot, slope change abruptly first derivatives are discontinuous at knots.
Solution
Use higher order polynomial splines.
To ensure smoothness at knot, equate the derivatives at knots
b) Quadratic Spline Interpolation
Data points: (x0,y0), (x1,y1),…….,(xn-1,yn-1), (xn,yn)
Quadratic spline fit a quadratic polynomial for each interval between knots
Need to find the spline
function for each interval
b) Quadratic Spline Interpolation
f(x) a1x 2 b1x c1 , for x 0 x x1
f(x) a 2 x 2 b 2 x c 2 , for x1 x x 2
.
f(x) a n x 2 b n x c n , for x n -1 x x n
The quadratic spline for each interval is;
f i (x) a i x 2 bi x ci , for x i-1 x x i ; i 1,....n
Need to find ai, bi & ci for i=1,…n
There are 3n unknown constants.
Thus, 3n equations/conditions are required to solve for the unknowns! How to find
these constant?
b) Quadratic Spline Interpolation
Finding the constants ai, bi & ci.
1. Each quadratic spline goes through two consecutive data points
a 1x 0 b1x 0 c1 f(x 0 )
2
For first spline
a 1x1 b1x1 c1 f(x1 )
2
.
a n x n 1 b n x n 1 c n f(x n 1 )
2
For last spline
a n x n b n x n c n f(x n )
2
There are 2n equations, in general :
a i x i 1 b i x i 1 c i f(x i 1 )
2
a i x i b i x i ci f(x i )
2
b) Quadratic Spline Interpolation
2. The first derivatives of two quadratic splines are continuous (i.e. the same) at the
interior knots
In general; 2a i xi b i 2a i 1x i b i 1 0 (i 1,2,...n 1)
Since there are (n-1) interior points, there are (n-1) such equations!
3. Assume the first spline is linear or the 2nd derivative is zero at the first knot.
There is 1 equation here! Which gives a1 = 0
From 1 ,2 & 3, we have
2n + (n-1) + 1 = 3n equations
Can solve for 3n unknown constants ai, bi & ci
b) Quadratic Spline Interpolation
2. The first derivatives of two quadratic splines are continuous (i.e. the same) at the
interior knots
In general; 2a i xi b i 2a i 1x i b i 1 0 (i 1,2,...n 1)
Since there are (n-1) interior points, there are (n-1) such equations!
3. Assume the first spline is linear or the 2nd derivative is zero at the first knot.
There is 1 equation here! Which gives a1 = 0
From 1 ,2 & 3, we have
2n + (n-1) + 1 = 3n equations
Can solve for 3n unknown constants ai, bi & ci
b) Quadratic Spline Interpolation
Shortcoming of quadratic spline
1. Straight line between the 1st and 2nd data points
2. Overshoot too high in the last interval.
Solution???????: Use cubic spline!
c) Cubic Spline Interpolation
Preferred because they provide the simplest representation that exhibit the desired
appearance and smoothness
To derive a third-order polynomial for each interval between knots.
The general cubic spline is given by
fi (x) a i x 3 b i x 2 c i x d i , for x i -1 x x i ; i 1,....n
For (n+1) data points (i=0,1…n), there are n interval
4n unknown constants to be determined.
c) Cubic Spline Interpolation
Finding the constants ai, bi , ci & di
The 4n equations are given by
1. Each cubic spline goes through 2 consecutive data points
There are 2 equations.
2. The first derivatives of two cubic spline are continuous at the inner knots.
There are (n-1) equations.
3. The second derivative at interior knots are the same.
There are (n-1) equations.
4. The second derivatives at the end knots are zero –assume a ‘natural’ spline.
There are 2 equations.
(Need to specify the end condition Refer to the end knot conditions)
Thus, there are 4n equations to solve simultaneously to determine a’s, b’s, c’s and d’s.
c) Cubic Spline Interpolation
Variety of the end knots condition
1. Natural end conditions - assume the second derivative at the end knots are zero function
become straight line at the end knots.
2. Clamped end conditions - assume the first derivatives at the first and last knots are known –
need to specify the desired slope at the end knots.
3. “Not-a-knot” end conditions – to force continuity of the third derivative at the second and
next-to-last knots (results in the first two intervals having the same spline function and the
last two intervals having the same spline function)
Spline Interpolation – Example
Fit the data with the quadratic splines and evaluate the function at x = 2.7.
20
X f(x) 15
1 1
2 4
10
3 9 5
4 16
0
0 1 2 3 4 5
Spline Interpolation – Example
Solution:
Since we have 4 data points, we need 3 intervals and 9 conditions to solve for the quadratic
splines.
1. Functions are equal at the interior nodes.
@ x = 2, 4a1 + 2b1 + c1 = 4a2 + 2b2 + c2 = 4
@ x = 3, 9a2 + 3b2 + c2 = 9a3 + 3b3 + c3 = 9
2. First and last functions pass through the end points.
@ x = 1, a1 + b1 + c1 = 1
@ x = 4, 16a3 + 4b3 + c3 = 16
3. The first derivatives are equal at the interior nodes.
@ x = 2, 4a1 + b1 = 4a2 + b2
@ x = 3, 6a2 + b2 = 6a3 + b3
4. The second derivative at the first point is zero.
a1 = 0
Spline Interpolation – Example
We now only have 8 unknowns since a1 = 0. We may express the preceding conditions in a
matrix form as
Solving for the unknown constants yield The quadratic splines for each interval are then,
a1 = 0 b1 = 3 c1 = - 2 •f1 (x) = 3x - 2 1 1≤ x ≤ 2
a2 = 2 b2 = - 5 c2 = 6 •f2 (x) = 2x2 - 5x + 6 2 ≤ x ≤ 3
a3 = 0 b3 = 7 c3 = - 12 •f3 (x) = 7x - 12 3≤x≤4
The interpolation at x = 2.7,
•f2 (2.7) = 2 (2.7)2 - 5 (2.7) + 6 = 7.08
