SPLINE INTERPOLATION AN INTERACTIVE EBOOK
On non Internet Explorer browsers, the equations may not show up. As an alternative or if you prefer, you can see the pdf version of the ebook instead
Title	An interactive e-book for illustrating the Spline Method for interpolation.
Creator	Autar K Kaw
Subject and Keywords	Spline Method, Interpolation, Mathcad, Maple, Mathematica, Matlab, Simulations.
Description	This is an interactive ebook for illustrating spline method for interpolation. It includes links to simulations in Mathcad, Maple, Mathematica and Matlab for the algorithm, multiple choice quizzes, problem set, and a PowerPoint presentation.
Publisher	Holistic Numerical Methods Institute, College of Engineering, University of South Florida, Tampa, FL 33620-5350.
Contributors	Autar Kaw, Michael Keteltas
Format	Text/HTML
Last Revised	June 14, 2004
Identifier	http://numericalmethods.eng.usf.edu/ebooks/spline_05inp_ebook.pdf
Language	English
Rights	http://numericalmethods.eng.usf.edu/rights.htm

Table of Contents

Spline Method of Interpolation

Linear spline interpolation

Quadratic spline interpolation

PowerPoint presentation

Examples

Example 1: Linear spline application problem

Example 2: Quadratic spline application problem

Simulation [MAPLE] [MATHCAD] [MATHEMATICA] [MATLAB]

Problem Sets

Multiple choice question examination

A set of homework assignment problems

Background

This is an example of how an instructor of a Numerical Methods course can develop an E-book on a single topic by using resources that are only available at the Holistic Numerical Methods Institute (HNMI) Website.

Although one of the primary advantages of a web-based resource is that one can use documents outside of its own domain, we are particularly using this example as a way to illustrate the holistic nature of the resources available at HNMI. You are welcome to modify and edit this e-book to suit your purpose.

Using the textbook document written in MS Word 2000 as a foundation, it was made interactive within MS Word 2000 by putting bookmarks and hyperlinks to background information, PowerPoint presentations, Mathcad simulations, historical anecdotes, multiple choice tests, problem sets, etc. Then the MS Word 2000 file was saved as a webpage and that is what you are about to read here.

Back to TOC

What is interpolation?

Many a times, a function is given only at discrete points such as . How does one find the value of ‘y’ at any other value of ‘x’? Well, a continuous function may be used to represent the ‘n+1’ data values with passing through the ‘n+1’ points. Then one can find the value of y at any other value of x. This is called interpolation. Of course, if 'x' falls outside the range of 'x' for which the data is given, it is no longer interpolation but is called extrapolation.

So what kind of function should one choose? A polynomial is a common choice because polynomials are easy to

a) evaluate

b) differentiate, and

c) integrate

as opposed to other choices such as a sine or exponential series.

Figure 1: Interpolation of discrete data

Polynomial interpolation involves finding a polynomial of order ‘n’ that passes through ‘n+1’ data points. Several methods to obtain such a polynomial include direct method, Newton’s Divided Difference polynomial, and Lagrangian interpolation method. So is spline just another method of obtaining this ‘n’^th order polynomial? …… NO! Actually, when ‘n’ becomes large, in many cases, one may get oscillatory behavior in the resulting polynomial. This was shown by Runge when he interpolated data based on a simple function of

on an interval of [-1, 1]. For example, take six equidistantly spaced points in [-1, 1] and find y at these points as given in Table 1.

Table 1: Six equidistantly spaced points in [-1, 1]


-1.0	0.038461
-0.6	0.1
-0.2	0.5
0.2	0.5
0.6	0.1
1.0	0.038461

Figure 2: 5^th order polynomial vs. exact function

Now through these six points, one can pass a fifth order polynomial

through the six data points. On plotting the fifth order polynomial and the original function, one can see that the two do not match well. One may consider choosing more points in the interval [-1, 1] to get a better match, but it diverges even more (see Figure 3), where 21 equidistant points were chosen in the interval [-1, 1] to draw a 20 ^th order polynomial. In fact, Runge found that as the order of the polynomial becomes infinite, the polynomial diverges in the interval of –1 < x < 0.726 and 0.726 < x < 1.

Figure 3: Higher order polynomial interpolation is a bad idea

So what is the answer to using information from more data points, but at the same time keeping the function true to the data behavior? The answer is in spline interpolation. The most common spline interpolations used are linear, quadratic, and cubic splines.

Back to TOC

Linear spline interpolation: Given , fit linear splines to the data. This simply involves forming the consecutive data through straight lines. So if the above data is given in an ascending order, the linear splines are given by

Figure 4: Linear splines

Note the terms of

in the above function are simply slopes between and .

Back to TOC

Example 1

The upward velocity of a rocket is given as a function of time as

Table 2: Velocity as a function of time

t	v(t)
s	m/s
0	0
10	227.04
15	362.78
20	517.35
22.5	602.97
30	901.67

Figure 5: Velocity vs. time data for the rocket example

Determine the value of the velocity at t=16 seconds using a first order polynomial.

Solution

Since we need to evaluate the velocity at t = 16 s, we choose the two data points closest to t = 16 s and that bracket t = 16. Those two points are and

m/s

Linear splines are no different from linear interpolation. It still uses data only from the two consecutive data points. Also at the interior points of the data, the slope changes abruptly. This means that the first derivative is not continuous at these points. So how do we improve on this? We can do so by using quadratic splines.

Back to TOC

Quadratic Splines: In these splines, a quadratic polynomial approximates the data between two consecutive data points. Given , fit quadratic splines through the data. The splines are given by

So how does one find the coefficients of these quadratic splines? There are 3n such coefficients

1, 2, …, n

To find ‘3n’ unknowns, one needs to set up ‘3n’ equations and then simultaneously solve them. These ‘3n’ equations are found by the following.

1) Each quadratic spline goes through two consecutive data points

This condition gives 2n equations as there are ‘n’ quadratic splines going through two consecutive data points.

2) The first derivatives of two quadratic splines are continuous at the interior points. For example, the derivative of the first spline

The derivative of the second spline

and the two are equal at giving

Similarly at the other interior points,

Since there are (n-1) interior points, we have (n-1) such equations. So far, the total number of equations is equations. We still then need one more equation.

We can assume that the first spline is linear, that is

This gives us ‘3n’ equations and ‘3n’ unknowns. These can be solved by a number of techniques used to solve simultaneous linear equations.

Back to TOC

Example 2

The upward velocity of a rocket is given as a function of time as

Table 3: Velocity as a function of time

t	v(t)
s	m/s
0	0
10	227.04
15	362.78
20	517.35
22.5	602.97
30	901.67

Figure 6: Velocity vs. time data for the rocket example

Determine the value of the velocity at t=16 using quadratic splines.

a) Determine the value of the velocity at t=16 seconds using quadratic splines.

b) Using the quadratic splines as velocity functions, find the distance covered by the rocket from t=11s to t=16s.

c) Using the quadratic splines as velocity functions, find the acceleration of the rocket at t=16s.

Solution:

a) Since there are six data points, five quadratic splines pass through them.

Setting up the equations

Each quadratic spline passes through two consecutive data points giving

passes through t = 0 and t = 10,

(1)

(2)

passes through t = 10 and t = 15,

(3)

(4)

passes through t = 15 and t = 20,

(5)

(6)

passes through t = 20 and t = 22.5,

(7)

(8)

passes through t = 22.5 and t = 30,

(9)

(10)

Quadratic splines have continuous derivatives at the interior data points

At t = 10

(11)

At t = 15

(12)

At t = 20

(13)

At t = 22.5

(14)

3. Assuming the first spline is linear,

(15)

Solving the above 15 equations gives the 15 unknowns as

i
1	0	22.704	0
2	0.8888	4.928	88.88
3	-0.1356	35.66	-141.61
4	1.6048	-33.956	554.55
5	0.20889	28.86	-152.13

Therefore, the splines are given by

At t = 16

m/s

b) The distance covered by the rocket between 11 s and 16 s can be calculated as

But since the splines are valid over different ranges, we need to break the integral accordingly as

c) What is the acceleration at t = 16?

m/s²

Back to TOC

Simulations

[MAPLE] [MATHCAD] [MATHEMATICA] [MATLAB]

Problem Set

1. The following x‑y data is given

x	1	2	3	5	6
y	4.75	4	5.25	15	45

The data is fit by quadratic spline interpolants given by

f(x)= -0.75 x + 5.5, 1≤ x ≤2,

=2 x² ‑ 8.75 x + 13.5, 2≤ x ≤3,

=c x² + g x + h, 3≤ x ≤5,

=j x² + k x + l, 5≤ x ≤6,

where c, g, h, j, k, l are constants.

a) Find the value of c, g, h, j, k, l.

b) Compare the values of the function at x=2.3 using linear spline interpolation and quadratic spline interpolation.

Answer: (a) c=1.86029, g=-7.9117, h=12.242, j=19.308, k=-182.39, l=444.26

(b)Linear Spline = 5.625; Quadratic Spline = 3.955

*2. Given (x₁,y₁), (x₂,y₂), ........, (x_n,y_n), that is n data points. For conducting quadratic spline interpolation the x- data needs to be

A) equally spaced

B) in ascending or descending order

C) in integers

D) positive

Answer: B

*3. In cubic spline interpolation, for the splines

(A) The first derivatives are continuous at the interior data points

(B) The second derivatives are continuous at the interior data points

(D) The third derivatives are continuous

Answer: C

*4. The following incomplete y vs. x data is given

2.2

3.7

5.1

4.25

5.25

15.1

?????

The data is fit by quadratic spline interpolants given by

f(x) = 1.4583 x + 2.7916, 1£x£2.2,

= -1.3055 x² +7.2027 x -3.5272, 2.2£x£3.7,

= c x² + g x + h, 3.7 £x£5.1,

= j x² + k x + l, 5.1£x£6,

where c, g, h, j, k, l are constants. What is the value of g? Show all your steps clearly.

Answer: 4.2482

*5. The following incomplete y vs. x data is given

2.2

3.7

5.1

4.25

5.25

????

?????

The data is fit by quadratic spline interpolants given by

f(x) =1.4583 x + 2.7916, 1£x£2.2,

=-1.3055 x² +7.2027 x -3.5272, 2.2£x£3.7,

= c x² + g x + h, 3.7 £x£5.1,

= j x² + k x + l, 5.1£x£6,

where c, g, h, j, k, l are constants. What is the value of at x=2.67?

Answer: 0.23111

*6. The following incomplete y vs x data is given

2.2

3.7

5.1

4.25

5.25

????

?????

The data is fit by quadratic spline interpolants given by

f(x) =1.4583 x + 2.7916, 1£x£2.2,

=-1.3055 x² +7.2027 x -3.5272, 2.2£x£3.7,

= c x² + g x + h, 3.7 £x£5.1,

= j x² + k x + l, 5.1£x£6,

where c, g, h, j, k, l are constants. What is the value of?

Answer: 5.6965

Back to TOC

Multiple choice question examination

Title

Figure 1: Interpolation of discrete data

Figure 4: Linear splines