MTH2212 – Computational Methods and
Statistics
Curve Fitting and Interpolation
Lecture 6:
Interpolation by Spline Functions
Objectives
Introduction
Linear Splines
Quadratic Splines
Cubic Splines
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 2
Introduction
Higher order polynomials can lead to erroneous results
because of round off error and oscillations to be
avoided.
Lower-order polynomial fits should be used.
Alternative approach is to apply lower-order polynomials
to subsets of data points : spline functions.
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 3
Introduction
The drafting technique of using a spline to draw smooth
curves through a series of points. Notice how, at the end
points, the spline straightens out This is “natural” spline.
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 4
Introduction
Notation used to derive splines. Notice that there are n–1
intervals and n data points.
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 5
Why Splines ?
16th Order
Polynomial
Original
Function
4th Order
Polynomial
8th Order
Polynomial
Higher order polynomial interpolation is a bad idea
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 6
Why Splines ?
f(x) = 1/(1+25x2)
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 7
Spline Interpolation Definition
Notation used to derive splines. Notice that there are n–1
intervals and n data points.
Each interval i has its own spline function Si(x)
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 8
Spline Interpolation Definition
Given n distinct knots xi such that:
x1 x2 ... xn 1 xn
with n knot values fi find a spline function
S1 ( x) x [ x1 , x2 ]
S ( x) x [ x , x ]
S ( x) 2 2 3
S n 1 ( x) x [ x n 1 , x n ]
with each Si(x) a polynomial of degree at most n.
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 9
Linear Splines
Simplest form of spline interpolation
Given the data ( x1 , f1 ), ( x2 , f 2 ),....., ( xn 1 , f n 1 ), ( xn , f n )
Consecutive data points connected through straight lines.
Each Si is a linear interpolation function constructed as:
S i ( x) ai bi ( x xi )
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 10
Linear Splines
Using the formulation of Newton linear interpolation, the
linear splines can be written as:
f ( x 2 ) f ( x1 )
S1 ( x) f ( x1 ) x2 x1
( x x1 ) x [ x1 , x2 ]
f ( x3 ) f ( x 2 )
S 2 ( x) f ( x 2 ) ( x x 2 ) x [ x 2 , x3 ]
S ( x) x3 x 2
f ( xn ) f ( xn 1 )
S n 1 ( x) f ( x n 1 ) xn xn 1
( x x0 ) x [ xn 1 , xn ]
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 11
Example 1
Given the following data, evaluate the function at x=5 using
linear splines.
i xi fi
1 3.0 2.5
2 4.5 1.0
3 7.0 2.5
4 9.0 0.5
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 12
Example 1 - Solution
x=5 is between x=4.5 and x=7. Hence, f(5) is evaluated using
linear splines on the second interval
f ( x3 ) f ( x2 )
S 2 ( x ) f ( x2 ) ( x x2 )
x3 x2
2.5 - 1.0
1.0 ( x 4.5)
7.0 - 4.5
The function value at x=5
2.5-1.0
f (5) S 2 (5) 1.0 (5 4.5) 1.3
7.0-4.5
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 13
Quadratic Splines
Quadratic splines are rarely used for interpolation for
practical purposes
Ideally quadratic splines are only used to understand cubic
splines
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 14
Quadratic Splines
Each Si is a second-order polynomial constructed as:
S i ( x) ai bi ( x xi ) ci ( x xi ) 2
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 15
Quadratic Splines
The splines are given by:
S1 ( x) a1 b1 ( x x1 ) c1 ( x x1 ) 2 x [ x1 , x2 ]
S 2 ( x) a2 b2 ( x x2 ) c2 ( x x2 ) x [ x2 , x3 ]
2
S ( x)
S ( x) a b ( x x ) c ( x x ) 2 x [ xn1 , xn ]
n1 n 1 n 1 n 1 n 1 n 1
Find ai, bi, ci for i=1,2,…,n-1 3(n-1) unknown constants to
evaluate 3(n-1) equations are required.
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 16
Derivation of Quadratic Splines
1. The function must pass through all the points (Continuity
condition), i.e. for x=xi, we have:
S (
i i x ) f i ai bi ( xi xi ) ci ( xi xi ) 2
ai f i
(n-1) equations
2. Functions value of adjacent polynomials must be equal at
the knots i.e. for knot i+1 we have:
fi bi ( xi 1 xi ) ci ( xi 1 xi ) 2 fi 1 bi 1 ( xi 1 xi 1 ) ci 1 ( xi 1 xi 1 ) 2
By setting hi = xi+1 – xi, the above equation simplifies to:
2
f i bi hi ci hi f i 1
this equation can be written for knots i=1,2,…,n-1
(n-1) equations
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 17
Derivation of Quadratic Splines
3. The first derivatives at the interior nodes must be equal
(adjacent splines will be joined smoothly).
Quadric spline function can be differentiated to
S 'i ( x) bi 2ci ( x xi )
first derivatives at interior knot i+1 gives:
bi 2ci hi bi 1
(n-2) equations
4. Make one arbitrary choice i.e. assume the second derivative
is zero at the first point.
c1 0
(1) equations
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 18
Example 2
Given the following data, evaluate the function at x=5 using
Quadratic splines.
i xi fi
1 3.0 2.5
2 4.5 1.0
3 7.0 2.5
4 9.0 0.5
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 19
Example 2 - Solution
Since there are 4 data points, 3 quadratic splines pass
through them
S1 ( x) a1 b1 ( x 3) c1 ( x 3) 2 x [3,4.5]
S 2 ( x) a2 b2 ( x 4.5) c2 ( x 4.5) 2 x [4.5,7]
S3 ( x) a3 b3 ( x 7) c3 ( x 7) 2 x [7,9]
The necessary function and interval width values are:
i xi fi hi
1 3.0 2.5 4.5 – 3.0 = 1.5
2 4.5 1.0 7.0 – 4.5 = 2.5
3 7 2.5 9.0 – 7.0 = 2.0
4 9 0.5
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 20
Example 2 - Solution
Setting up the equations
1. The function must pass through all the points:
a1 f1 2.5
ai f i a2 f 2 1.0
a3 f 3 2.5
2. Functions value of adjacent polynomials must be equal at
the knots:
2
f1 b1h1 c1h1 f 2 2.5 1.5b1 1.0
2
f i bi hi ci hi f i 1 f 2 b2 h2 c2 h2 2 f 3 1.0 2.5b2 6.25c2 2.5
f 3 b3h3 c3h3 f 4
2 2.5 2.0b3 4c3 0.5
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 21
Example 2 - Solution
3. The first derivatives at the interior nodes must be equal
b1 b2 b1 b2
bi 2ci hi bi 1
b2 2c2 h2 b3 b2 5c2 b3
4. Assume the second derivative is zero at the first point.
c1 0
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 22
Example 2 - Solution
All the equations can be assembled in a matrix form as
1.5 0 0 0 0 b1 1.5
0 2.5 6.25 0
0 b2 1.5
0 0 0 2 4 c2 2
1 1 0 0 0 b3 0 b1 1.0
0 1 5 1 0 c3 0 b2 1.0
These equations can be solved with the results: c2 0.64
b3 2.2
a1 2.5 c3 1.6
Along with a2 1.0 and c1 0
a3 2.5
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 23
Example 2 - Solution
The quadratic splines are then given by
S1 ( x) 2.5 ( x 3) x [3,4.5]
S 2 ( x) 1.0 ( x 4.5) 0.64( x 4.5) 2 x [4.5,7]
S3 ( x) 2.5 2.2( x 7) - 1.6( x 7) 2 x [7,9]
Because x=5 lies in the second interval, we use S2 to make
the prediction
S 2 (5) 1.0 (5 4.5) 0.64(5 4.5) 2 0.66
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 24
Cubic Splines
Third-order curves used to connect each pair of data
points are called cubic splines.
si ( x) ai bi ( x xi ) ci ( x xi ) 2 d i ( x xi ) 3
We have n data points n-1 intervals 4n-4 unknowns
constants 4n-4 conditions are needed
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 25
Cubic Splines
The first 3 conditions are identical to those used for the
quadratic splines:
1. Spline functions must pass through all the data points
2. Function values must be equal at the interior knots
3. First derivatives at the interior knots must be equal
4. Second derivatives at the interior knots must be equal
5. Second derivatives at the end knots are zero
Natural Spline
Or
5. First derivatives at the first and last knots are specified
Clamped End
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 26
Derivation of Cubic Splines
1. The function must pass through all the points (Continuity
condition), i.e. for x=xi, we have:
ai f i
2. Functions value of adjacent polynomials must be equal at
the knots i.e. for knot i+1 we have:
f i bi hi ci hi 2 d i hi 3 f i 1
3. The first derivatives at the interior nodes must be equal i.e.
at interior knot i+1 gives:
2
bi 2ci hi 3d i hi bi 1
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 27
Derivation of Cubic Splines
4. The second derivatives at the interior nodes must also be
equal.
Cubic spline function can be differentiated to
S ''i ( x) 2ci 6d i ( x xi )
second derivatives at interior knot i+1 gives:
ci 3d i hi ci 1
5. Second derivatives at the end knots are zero
c1 0
cn 0
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 28
Derivation of Cubic Splines
Let’s summarize the obtained equations:
ai f i (1)
f i bi hi ci hi 2 d i hi 3 f i 1 (2)
2
bi 2ci hi 3d i hi bi 1 (3)
ci 3d i hi ci 1 (4)
c1 0
(5)
cn 0
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 29
Derivation of Cubic Splines
Solve Eq. (4) for di:
ci 1 ci
di (6)
3hi
Substitute into Eq. (2) and (3)
hi2
f i bi hi (2ci ci 1 ) f i 1 (7)
3
bi 1 bi hi (ci ci 1 ) (8)
Solve Eq.(7) for bi:
f i 1 f i hi
bi (2ci ci 1 ) (9)
hi 3
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 30
Derivation of Cubic Splines
Reduce the index of Eq. (8) and (9) by 1
f i f i 1 hi 1
bi 1 (2ci 1 ci ) (10)
hi 1 3
bi bi 1 hi 1 (ci 1 ci ) (11)
Substitute Eq. (9) and (10) into Eq. (11)
hi 1ci 1 2(hi 1 hi )ci hi ci 1 3( f [ xi 1 , xi ] f [ xi , xi 1 ]) (12)
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 31
Derivation of Cubic Splines
Equation (12) can be written in matrix form as
1 c1 0
h 2(h h ) h c 3( f [ x , x ] f [ x x ])
1 1 2 2 2 3 2 2 1
hn 2 2(hn 2 hn 1 ) hn 1 cn 1 3( f [ xn , xn 1 ] f [ xn 1 xn 2 ])
1 cn 0
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 32
Example 3
Given the following data, evaluate the function at x=5 using
Cubic splines.
i xi fi
1 3.0 2.5
2 4.5 1.0
3 7.0 2.5
4 9.0 0.5
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 33
Example 2 - Solution
Since there are 4 data points, 3 quadratic splines pass
through them
S1 ( x) a1 b1 ( x 3) c1 ( x 3) 2 d1 ( x 3)3 x [3,4.5]
S 2 ( x) a2 b2 ( x 4.5) c2 ( x 4.5) 2 d 2 ( x 4.5)3 x [4.5,7]
S3 ( x) a3 b3 ( x 7) c3 ( x 7) 2 d 3 ( x 7)3 x [7,9]
The necessary function and interval width values are:
i xi fi hi
1 3.0 2.5 4.5 – 3.0 = 1.5
2 4.5 1.0 7.0 – 4.5 = 2.5
3 7 2.5 9.0 – 7.0 = 2.0
4 9 0.5
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 34
Example 2 - Solution
Determine the c coefficients from the set of simultaneous
equations
1 c1 0
h 2( h h ) h c 3( f [ x , x ] f [ x x ])
1 1 2 2 2 3 2 2 1
h2 2( h2 h3 ) h3 c3 3( f [ x4 , x3 ] f [ x3 x2 ])
1 c4 0
1 c1 0 c1 0
1.5 8 2.5 c 4.8 c2 0.8395
2
2.5 9 2 c3 4.8 c3 0.7665
1 c4 0 c4 0
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 35
Example 2 - Solution
Use equations (9) and (6) to compute bi and di
b1 1.42
f i 1 f i hi
bi (2ci ci 1 ) b2 0.16
hi 3
d1 0.187 b3 0.022
ci 1 ci
di d 2 0.214
3hi
d 3 0.128
The cubic splines for each interval
S1 ( x) 2.5 1.42( x 3) 0.187( x 3)3 x [3,4.5]
S 2 ( x) 1.0 0.16( x 4.5) 0.84( x 4.5) 2 0.214d 2 ( x 4.5)3 x [4.5,7]
S3 ( x) 2.5 0.022( x 7) - 0.767( x 7) 2 0.128( x 7)3 x [7,9]
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 36
Example 2 - Solution
The function value at x=5 is calculated using S2
S 2( 5 ) 1.0 0.16( 5 4.5 ) 0.84( 5 4.5 )2 0.214d 2( 5 4.5 )3
1.103
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 37
Example - Summary
Spline fits of the set of four
points given in the example
(a) Linear spline,
(b) quadratic spline, and
(c) cubic spline, with a cubic
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 38
Assignment #3
Computational Methods
20.10, 20.32
Statistics
Check with Dr. Faiz
Dr. M. Hrairi MTH2212 - Computational Methods and Statistics 39
