Previous Lecture

Polynomial interpolation

-Difference interpolation
Polynomial interpolation

Lagrange Interpolation

Splines and piecewise interpolation

 CURVE FITTING
Describes techniques to fit curves (curve fitting) to
discrete data to obtain intermediate estimates.

There are two general approaches two curve fitting:

Data exhibit a significant degree of scatter. The strategy is to
derive a single curve that represents the general trend of the
data.
Data is very precise. The strategy is to pass a curve or a series of
curves through each of the points.

In engineering two types of applications are

encountered:
Trend analysis. Predicting values of dependent variable, may
include extrapolation beyond data points or interpolation
between data points.
Hypothesis testing. Comparing existing mathematical model
with measured data.
Quadratic Interpolation
If three data points are available, the estimate is
improved by introducing some curvature into the
line connecting the points.
f 2 ( x) b0 b1 ( x x0 ) b2 ( x x0 )( x x1 )
A simple procedure can be used to determine the
values of the coefficients.
x x0 b0 f ( x0 )
f ( x1 ) f ( x0 )
x x1 b1
x1 x0
f ( x2 ) f ( x1 ) f ( x1 ) f ( x0 )
x2 x1 x1 x0
x x2 b2
x2 x0
Lagrange Interpolating Polynomials

The Lagrange interpolating polynomial is simply a

avoids the computation of divided differences:

n
f n ( x) Li ( x) f ( xi )
i 0
n x xj
Li ( x)
j 0 xi xj
j i
 x x1 x x0
f1 ( x) f ( x0 ) f ( x1 )
x0 x1 x1 x0
x x1 x x2 x x0 x x2
f 2 ( x) f ( x0 ) f ( x1 )
x0 x1 x0 x 2 x1 x0 x1 x 2
x x0 x x1
f ( x2 )
x2 x0 x2 x1

an estimated error of:

n
Rn f [ x, xn , xn 1 , , x0 ] ( x xi )
i 0
 Lagrangian Interpolation

Lagrangian interpolating polynomial is given by

n
f n ( x) Li ( x) f ( xi )
i 0

n f n (x) stands for the n th order polynomial that approximates the function y f (x)

given at (n 1) data points as x0 , y 0 , x1 , y1 ,......, x n 1 , y n 1 , x n , y n , and

n x xj
Li ( x)
j 0 xi xj
j i

Li (x) is a weighting function that includes a product of (n 1) terms with terms of j i

omitted.
Example
The upward velocity of a rocket is given as a function of time
in Table 1. Find the velocity at t=16 seconds using the
Lagrangian method for linear interpolation.

Table. Velocity as a
function of time

t (s) v(t ) (m/s )

0 0
10 227.04
15 362.78
20 517.35
22.5 602.97
30 901.67
Figure. Velocity vs. time data
for the rocket example
 Linear Interpolation
1 550
v(t ) Li (t )v(ti ) 517.35

i 0

L 0 (t ) v (t 0 ) L1 (t )v (t1 ) 500

ys

f ( range)
450
f x de sire d

t0 15, t 0 362.78
400

t1 20, t1 517.35
362.78 350
10 12 14 16 18 20 22 24
xs 10 x s range x de sire d xs 10
0 1
Linear Interpolation (contd)
1 t tj t t1
L0 (t )
j 0 t0 tj t 0 t1
j 0

1 t tj t t0
L1 (t )
j 0 t1 tj t1 t 0
j 1

t t1 t t0 t 20 t 15
v(t ) v(t 0 ) v(t1 ) (362.78) (517.35)
t 0 t1 t1 t 0 15 20 20 15
16 20 16 15
v(16) (362.78) (517.35)
15 20 20 15
0.8(362.78) 0.2(517.35)

393.7 m/s.
 Quadratic Interpolation
For the second order polynomial interpolation (also called quadratic interpolation), we
choose the velocity given by
2
v (t ) Li ( t ) v(t i )
i 0

L0 (t )v (t 0 ) L1 (t ) v( t1 ) L2 (t ) v( t 2 )
Example
The upward velocity of a rocket is given as a function of time
in Table 1. Find the velocity at t=16 seconds using the
Lagrangian method for quadratic interpolation.

Table. Velocity as a
function of time

t (s) v(t ) (m/s )

0 0
10 227.04
15 362.78
20 517.35
22.5 602.97
30 901.67
Figure. Velocity vs. time data
for the rocket example
 Quadratic Interpolation (contd)

t0 10, v(t 0 ) 227.04 517.35

550

t1 15, v(t1 ) 362.78 500

t2 20, v(t 2 ) 517.35 450

ys
400
f ( range)

2 t tj t t1 t t2 f x de sire d 350
L0 (t )
j 0 t0 tj t0 t1 t0 t2
j 0 300

2 t tj t t0 t t2 250
L1 (t )
j 0 t1 tj t1 t 0 t1 t 2
j 1 227.04 200
10 12 14 16 18 20
10 x s range x de sire d 20
2 t tj t t0 t t1
L2 (t )
j 0 t2 tj t2 t0 t 2 t1
j 2
 Quadratic Interpolation (contd)

t t1 t t2 t t0 t t2 t t0 t t1
vt v t0 v t1 v t2
t0 t1 t0 t 2 t1 t0 t1 t 2 t 2 t0 t 2 t1

16 15 16 20 16 10 16 20 16 10 16 15
v 16 227.04 362.78 517.35
10 15 10 20 15 10 15 20 20 10 20 15

0.08 227.04 0.96 362.78 0.12 527.35 392 . 19 m/s

The absolute relative approximate error a obtained between the results

from the first and second order polynomial is

392.19 393.70
a 100
392.19
0.38410 %
 Cubic Interpolation
For the third order polynomial (also called cubic interpolation), we choose the velocity given by
3
v (t ) Li ( t ) v(t i )
i 0

L0 (t ) v( t 0 ) L1 ( t ) v(t 1 ) L2 ( t ) v(t 2 ) L3 ( t ) v(t 3 )

700
602.97

600

ys 500

f ( range)

f x de sire d
400

300

227.04 200
10 12 14 16 18 20 22 24
10 x s range x de sire d 22.5
Example
The upward velocity of a rocket is given as a function of time
in Table 1. Find the velocity at t=16 seconds using the
Lagrangian method for cubic interpolation.

Table. Velocity as a
function of time

t (s) v(t ) (m/s )

0 0
10 227.04
15 362.78
20 517.35
22.5 602.97
30 901.67
Figure. Velocity vs. time data
for the rocket example
 Cubic Interpolation (contd)
to 10, v t o 227.04 t1 15, v t1 362.78

t2 20, v t 2 517.35 t3 22.5, v t 3 602.97

3 t tj t t1 t t2 t t3
L0 (t ) ; 700
j 0 t0 tj t0 t1 t0 t 2 t0 t3 602.97

j 0

600
3 t tj t t0 t t2 t t3
L1 (t )
j 0 t1 tj t1 t 0 t1 t 2 t1 t 3 ys 500
j 1
f ( range)

3 t tj t t0 t t1 t t3 f x de sire d
400
L2 (t ) ;
j 0 t2 tj t2 t0 t 2 t1 t 2 t3
j 2
300

3 t tj t t0 t t1 t t2
L3 ( t )
j 0 t3 tj t3 t 0 t 3 t1 t3 t 2 227.04 200
10 12 14 16 18 20 22 24
j 3 10 x s range x de sire d 22.5
 Cubic Interpolation (contd)
t t1 t t2 t t3 t t0 t t2 t t3
vt v t0 v t1
t0 t1 t0 t 2 t 0 t3 t1 t0 t1 t 2 t1 t3
t t0 t t1 t t3 t t1 t t1 t t2
v t2 v t3
t 2 t0 t 2 t1 t 2 t3 t3 t1 t3 t1 t3 t 2
16 15 16 20 16 22.5 16 10 16 20 16 22.5
v 16 227.04 362.78
10 15 10 20 10 22.5 15 10 15 20 15 22.5
16 10 16 15 16 22.5 16 10 16 15 16 20
517.35 602.97
20 10 20 15 20 22.5 22.5 10 22.5 15 22.5 20
0.0416 227.04 0.832 362.78 0.312 517.35 0.1024 602.97
392.06 m/s

The absolute relative approximate error a obtained between the results

from the first and second order polynomial is
392.06 392.19
a 100
392.06
0.033269 %
 Comparison Table

Order of Polynomial 1 2 3
v(t=16) m/s 393.69 392.19 392.06
Absolute Relative
-------- 0.38410% 0.033269%
Approximate Error
Distance from Velocity Profile

Find the distance covered by the rocket from t=11s to

t=16s ?
v(t ) (t 3 57.5t 2 1087.5t 6750)( 0.36326) (t 3 52.5t 2 875t 4500)(1.9348)
(t 3 47.5t 2 712.5t 3375)( 4.1388) (t 3 45t 2 650t 3000)(2.5727)

v (t ) 4.245 21.265t 0.13195t 2 0.00544t 3 , 10 t 22.5

16

s(16) s (11) v( t ) dt
11

16

( 4.245 21.265t 0.13195t 2 0.00544t 3 ) dt

11

t2 t3 t 4 16
[ 4.245t 21.265 0.13195 0.00544 ]11
2 3 4

1605 m
Acceleration from Velocity Profile

Find the acceleration of the rocket at t=16s given that

v(t ) 4.245 21.265t 0.13195t 2 0.00544t 3 , 10 t 22.5

,
d d
at vt 4.245 21.265t 0.13195t 2 0.00544t 3
dt dt

21.265 0.26390t 0.01632t 2

a (16) 21. 265 0.26390(16) 0.01632(16) 2

29.665 m / s 2
Coefficients of an Interpolating Polynomial

Although both the Newton and Lagrange

polynomials are well suited for determining
intermediate values between points, they do not
provide a polynomial in conventional form:

f ( x) a0 a1 x a2 x 2 ax x n
Since n+1 data points are required to determine n+1
coefficients, simultaneous linear systems of
a
f ( x0 ) a0 a1 x0 a2 x02 an x0n
f ( x1 ) a0 a1 x1 a2 x12 an x1n

f ( xn ) a0 a1 xn a2 xn2 an xnn

unknowns.
Reading
To read
MATLAB M-file functions
Newtint
Lagrange
Inverse interpolation (page 350)

Extrapolation and Oscillations (page 351)

Spline Interpolation
There are cases where polynomials can
lead to erroneous results because of
round off error and overshoot.

Alternative approach is to apply lower-

order polynomials to subsets of data
points. Such connecting polynomials are
called spline functions.
Figure 16.1
Figure 16.2
Figure 16.3
Figure 16.4
Why Splines ?
1
f ( x)
1 25 x 2
Table : Six equidistantly spaced points in [-1, 1]
1
x y
1 25 x 2

-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 : 5th order polynomial vs. exact function

 Why Splines ?
1.2

0.8

0.4
y

0
-1 -0.5 0 0.5 1
-0.4

-0.8
x
19th Order Polynomial f (x) 5th Order Polynomial

Figure : Higher order polynomial interpolation is a bad idea

 Linear Interpolation
Given x0 , y0 , x1 , y1 ,......, x n 1 , y n 1 x n , y n , 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 yi f ( xi )
Figure : Linear splines
Linear Interpolation (contd)
f ( x1 ) f ( x 0 )
f (x ) f ( x0 ) ( x x 0 ), x0 x x1
x1 x 0

f ( x 2 ) f ( x1 )
f ( x1 ) ( x x1 ), x1 x x2
x2 x1

.
.
.
f ( xn ) f ( xn 1 )
f (x n 1 ) ( x x n 1 ), x n 1 x xn
xn xn 1

Note the terms of

f ( xi ) f ( x i 1 )
xi x i 1

in the above function are simply slopes between xi 1 and x i .

Example
The upward velocity of a rocket is given as a function of time
in Table 1. Find the velocity at t=16 seconds using using linear
splines.

Table. Velocity as a
function of time

t (s) v(t ) (m/s )

0 0
10 227.04
15 362.78
20 517.35
22.5 602.97
30 901.67
Figure. Velocity vs. time data
for the rocket example
 Linear Interpolation
550
517.35

t0 15, v (t 0 ) 362.78
500
t1 20, v (t1 ) 517.35
ys

v(t 1 ) v (t 0 ) f ( range)
v (t ) v(t 0 ) (t t 0 ) 450

t1 t 0 f x de sire d

517.35 362.78 400

362.78 (t 15)
20 15
362.78
v (t ) 362.78 30.913( t 15) 350
10 12 14 16 18 20 22 24
xs 10 x s range x de sire d xs 10
0 1

At t 16,
v (16) 362.78 30.913(16 15)

393.7 m/s
 Quadratic Interpolation
Given x0 , y0 , x1 , y1 ,......, x n 1 , y n 1 , x n , y n , fit quadratic splines through the data. The splines
are given by
f (x ) a1 x 2 b1 x c1 , x0 x x1

a2 x 2 b2 x c2 , x1 x x2
.
.
.
an x 2 bn x cn , xn 1 x xn

Find a i , bi , ci , i
Quadratic Interpolation (contd)
Each quadratic spline goes through two consecutive data points
2
a1 x 0 b1 x 0 c1 f ( x0 )
2
a1 x1 b1 x1 c1 f ( x1 ) .
.
.
2
a i xi 1 bi xi 1 ci f ( xi 1 )
2
a i xi bi xi ci f ( xi ) .

.
.
2
an xn 1 bn x n 1 cn f ( xn 1 )
2
an xn bn xn cn f (x n )

This condition gives 2n equations

 Quadratic Splines (contd)
The first derivatives of two quadratic splines are continuous at the interior points.
For example, the derivative of the first spline
a1 x 2 b1 x c1 is 2 a1 x b1
The derivative of the second spline
a2 x2 b2 x c 2 is 2 a 2 x b2
and the two are equal at x x1 giving

2 a1 x1 b1 2a 2 x1 b2

2 a1 x1 b1 2a 2 x1 b2 0
 Quadratic Splines (contd)

Similarly at the other interior points,

2a 2 x 2 b2 2a3 x 2 b3 0
.
.
.
2ai x i bi 2ai 1 xi bi 1 0
.
.
.
2a n 1 x n 1 bn 1 2a n x n 1 bn 0

We have (n-1) such equations. The total number of equations is (2n) ( n 1) (3n 1) .
We can assume that the first spline is linear, that is a1 0
 Quadratic Splines (contd)
This gives u Once we find the 3n constants,
we can find the function at any value of x using the splines,

f ( x) a1 x 2 b1 x c1 , x0 x x1

a2 x 2 b2 x c 2 , x1 x x2
.
.
.
an x 2 bn x c n , xn 1 x xn

http://numericalmethods.eng.usf.edu 40
 Quadratic Spline Example
The upward velocity of a rocket is given as a function of time.
Using quadratic splines
a) Find the velocity at t=16 seconds
b) Find the acceleration at t=16 seconds
c) Find the distance covered between t=11 and t=16 seconds

Table Velocity as a
function of time

t (s) v(t ) (m/s)

0 0
10 227.04
15 362.78
20 517.35
22.5 602.97 Figure. Velocity vs. time data
for the rocket example
30 901.67
 Solution
2
v(t ) a1t b1t c1 , 0 t 10
2
a2 t b2 t c2 , 10 t 15
2
a3t b3t c3 , 15 t 20
2
a4 t b4 t c4 , 20 t 22.5
2
a5t b5t c5 , 22.5 t 30
Let us set up the equations
Each Spline Goes Through Two
Consecutive Data Points
2
v(t ) a1t b1t c1 , 0 t 10
2
a1 (0) b1 (0) c1 0
2
a1 (10) b1 (10) c1 227.04
Each Spline Goes Through Two
Consecutive Data Points
a2 (10) 2 b2 (10) c2 227.04
t v(t)
a2 (15) 2 b2 (15) c2 362.78
s m/s
0 0 a3 (15) 2 b3 (15) c3 362.78
10 227.04 a3 (20) 2 b3 (20) c3 517.35
15 362.78
a4 (20) 2 b4 (20) c4 517.35
20 517.35
a4 (22.5) 2 b4 (22.5) c4 602.97
22.5 602.97
30 901.67 a5 (22.5) 2 b5 (22.5) c5 602.97
a5 (30) 2 b5 (30) c5 901.67
 Derivatives are Continuous at
Interior Data Points
v(t ) a1t 2 b1t c1 , 0 t 10
a2 t 2 b2 t c2 ,10 t 15
d d
a1t 2 b1t c1 a2t 2 b2t c2
dt t 10 dt t 10

2a1t b1 t 10
2a2t b2 t 10

2a1 10 b1 2a2 10 b2
20a1 b1 20a2 b2 0
Derivatives are continuous at
Interior Data Points
At t=10

2a1 (10) b1 2a2 (10) b2 0

At t=15

2a2 (15) b2 2a3 (15) b3 0

At t=20

2a3 (20) b3 2a4 (20) b4 0

At t=22.5

2a4 (22.5) b4 2a5 (22.5) b5 0

Last Equation

a1 0
Final Set of Equations

0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 a1 0
100 10 1 0 0 0 0 0 0 0 0 0 0 0 0 b1 227.04
0 0 0 100 10 1 0 0 0 0 0 0 0 0 0 c1 227.04
0 0 0 225 15 1 0 0 0 0 0 0 0 0 0 a2 362.78
0 0 0 0 0 0 225 15 1 0 0 0 0 0 0 b2 362.78
0 0 0 0 0 0 400 20 1 0 0 0 0 0 0 c2 517.35
0 0 0 0 0 0 0 0 0 400 20 1 0 0 0 a3 517.35
0 0 0 0 0 0 0 0 0 506.25 22.5 1 0 0 0 b3 602.97
0 0 0 0 0 0 0 0 0 0 0 0 506.25 22.5 1 c3 602.97
0 0 0 0 0 0 0 0 0 0 0 0 900 30 1 a4 901.67
20 1 0 20 1 0 0 0 0 0 0 0 0 0 0 b4 0
0 0 0 30 1 0 30 1 0 0 0 0 0 0 0 c4 0
0 0 0 0 0 0 40 1 0 40 1 0 0 0 0 a5 0
0 0 0 0 0 0 0 0 0 45 1 0 45 1 0 b5 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 c5 0
Coefficients of Spline
i ai bi ci
1 0 22.704 0
2 0.8888 4.928 88.88
3 35.66
4 1.6048 554.55
5 0.20889 28.86
 Final Solution
v(t ) 22.704t , 0 t 10
0.8888t 2 4.928t 88.88, 10 t 15
0.1356t 2 35.66t 141.61, 15 t 20
1.6048t 2 33.956t 554.55, 20 t 22.5
0.20889t 2 28.86t 152.13, 22.5 t 30
Velocity at a Particular Point
a) Velocity at t=16
v(t ) 22.704t , 0 t 10
0.8888t 2 4.928t 88.88, 10 t 15
0.1356t 2 35.66t 141.61, 15 t 20
1.6048t 2 33.956t 554.55, 20 t 22.5
0.20889t 2 28.86t 152.13, 22.5 t 30

2
v 16 0.1356 16 35.66 16 141.61
394.24 m/s
Acceleration from Velocity Profile
b) The quadratic spline valid at t=16 is given by
d
a(16) v(t ) t 16
dt
vt 0.1356t 2 35.66t 141.61, 15 t 20
d
a (t ) ( 0.1356t 2 35.66t 141.61)
dt
0.2712t 35.66, 15 t 20
a(16) 0.2712(16) 35.66 31.321m/s 2
 Distance from Velocity Profile
c) Find the distance covered by the rocket from t=11s to t=16s.
16
S 16 S 11 v(t )dt
11

vt 0.8888t 2 4.928t 88.88, 10 t 15

0.1356t 2 35.66t 141.61, 15 t 20

16 15 16
S 16 S 11 v t dt v t dt v t dt
11 11 15
15 16
2
0.8888t 4.928t 88.88 dt 0.1356t 2 35.66t 141.61 dt
11 15

1595.9 m
Reading
MATLAB Built-in functions
spline

interp1
Multidimensional interpolation
Interp2

Interp3