Spline Interpolation: Problems

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
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!
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
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?
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
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

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

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.
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.
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
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
 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

Spline Interpolation: Problems

Uploaded by

Copyright:

Available Formats

Spline Interpolation: Problems

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Spline Interpolation: Problems

Uploaded by

Copyright:

Available Formats

Spline Interpolation

 Polynomial interpolation involves finding a polynomial of order ‘n’ that passes

 The most common spline interpolations are;

 This is especially useful when there are

 Spline usually provide superior

Need to find the spline

Linear spline function for

Need to find the spline

 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

 There are 3n unknown constants.

1. Each quadratic spline goes through two consecutive data points

For first spline

For last spline

There are 2n equations, in general :

In general; 2a i xi  b i  2a i 1x i  b i 1  0 (i  1,2,...n 1)

There is 1 equation here! Which gives a1 = 0

 From 1 ,2 & 3, we have

Can solve for 3n unknown constants ai, bi & ci

In general; 2a i xi  b i  2a i 1x i  b i 1  0 (i  1,2,...n 1)

There is 1 equation here! Which gives a1 = 0

 From 1 ,2 & 3, we have

Can solve for 3n unknown constants ai, bi & ci

1. Straight line between the 1st and 2nd data points

Solution???????: Use cubic spline!

 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

 The 4n equations are given by

3. The second derivative at interior knots are the same.

 1. Functions are equal at the interior nodes.

 2. First and last functions pass through the end points.

 3. The first derivatives are equal at the interior nodes.

 4. The second derivative at the first point is zero.

The interpolation at x = 2.7,

You might also like