Numerical Methods

Lecture 6
Interpolation
Direct Method & Lagrange Method
 y0,
xfxUrLa0x,%
U
m
L

What is interpolation?
 Many times, data is given only at discrete points
such
x , y , as
0 0 x1 , y1 , x2 , y2 ,
n 1 x , y , xn , yn 
n 1

........... . So, how then does one find the

value of y at any other value of x ?
 Well, a continuous function f(x) may be used to
represent the n+1 data values with f(x) passing
through the n+1 points (Figure 1).
 y
Then one can find the value of y at any other value
of x. This is called interpolation. (x3,y3
)
(x1,y1
Figure 1
)
(x2,y2 f(x)
(x0,y0 )
) x
 Polynomial interpolation?
 Of course, if new ‘x’ falls outside the range of x
for which the data is given, it is no longer
interpolation but instead is called extrapolation.
 So what kind of function f(x) should one choose?
A polynomial is a common choice for an
interpolating function because polynomials are
easy to
 evaluate,
 differentiate, and
 integrate
relative to other choices such as a trigonometric
and exponential series
 Polynomial interpolation involves finding a
 Direct Method of
Interpolation
 One of the methods of interpolation is called the
direct method.
 Other methods include the Lagrangian
interpolation method and Newton’s divided
difference polynomial method
 The direct method of interpolation is based on
the following premise. Given n+1 data points,
fit a polynomial of order n as given n
below
y a0  a1 x  ...............  an x
(1)
through the data, where a0, a1, a2,....... an+1, an are
real
constants.
 Direct Method of
Interpolation (continued)
 Since values of f(x) are given at values of x, one can write
equations
2 n
f ( x0 ) a0  a1 x0  a2 x0  .........  an x0
2 n
f ( x1 ) a0  a1 x1  a2 x1  .........  an x1
2 n
f ( x2 ) a0  a1 x2  a2 x2  .........  an x2
.....
.....
2 n
f ( xn 1 ) a0  a1 xn 1  a2 xn 1  .........  an xn 1
Direct Method of
Interpolation (continued)
 Then the constants, can be found by solving
the simultaneous linear equations.
 To find the value of f(x) at a given value of x,
simply substitute the value of x in Equation 1.
 But, it is not necessary to use all the data
points.
 How does one then choose the order of the
polynomial and what data points to use?
 This concept and the direct method of
interpolation are best illustrated using
examples
tv(t )

Example 1
 The upward velocity of a rocket is given as a function of
time in Table 1. Corresponding graph is shown in Figure 1
Table 1: Velocity as function of time Figure 1:
Graph of Velocity
Time (s) Velocity (m/s)
0 0
10 227.04
15 362.78
20 517.35
22.5 602.97
30 901.67

 Determine the value of the velocity at t = 16seconds using the

direct method of interpolation and a first order polynomial.
x0 , y0 
x1 , y1 
f1 x 

Solution to example 1
x
y

 For first order polynomial interpolation (also

called linear interpolation), the velocity is
given by
y

(x1 , y1)

f1(x)

(x0 , y0)
x
Figure 3 Linear interpolation
Solution to example 1
(continued)
 Since we want to find the velocity at t=16 sec,
and we are using a first order polynomial, we
need to choose the two data points that are
closest to t = 16 sec that also bracket t=16 sec to
evaluate it. The two points are t0=15 sec and
t1=20 sec
 Then
t0=15, v(t0)=362.78 a0=-100.93
t1=20, v(t1)=517.35 a1=30.914
Gives
v(15)=a0+a1 x 15=362.78 v(t)=ao+a1t
v(20)=a0+a1 x 20=517.35 v(16)=393.7
x0 , y0 
x1 , y1 
x2 , y2 
f 2 x 
Example 2
 Determine the value of the velocity at t = 16 seconds using the
direct method of interpolation and a second order polynomial.

y
Solution
For second order x1 , y 1
polynomial
x2 , y 2
interpolation (also
called quadratic
interpolation), the
f(x)
velocity is given by
x0 , y 0

x
v(t)=a0+a1t+a2t2
Solution to example 2
(continued)
 Since we want to find the velocity at t=16, and
we are using a second order polynomial, we need
to choose the three data points that are closest
to t = 16 that also bracket t = 16 to evaluate it.
The three points are t0=10, t1=15 and t2=20
 Then v(10)=227.04=a0+a1 x 10+a2 x 102
v(15)=362.78=a0+a1 x 15+a2 x 152
v(20)=517.35=a0+a1 x 20+a2 x 202
They gives, a0=12.05
a1=17.733
a2=0.3766
Solution to example 2
(continued)
Hence v(t)=12.05+17.733t+0.3766t 2
V(16)=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%
Example 3
For the rocket problem of the previous examples

 a) Determine the value of the velocity at t=16

seconds
using the direct method of interpolation and a third
order polynomial.
 b) Find the absolute relative approximate error for the
third order polynomial approximation.
 c) Using the third order polynomial interpolant for
velocity from part (a), find the distance covered by
the rocket from t=11 s to t=16 s.
 d) Using the third order polynomial interpolant for
velocity from part (a), find the acceleration of the
rocket at t=16s.
Solution to example 3
 For third order polynomial interpolation (also
called cubic interpolation), we choose the
vt  by
velocity given a0  a1t  a2t 2  a3t 3
y

(x3 ,
(x1 , y3)
y1)

(x2 , f3(x)
(x0 , y2)
y0)
x
Solution to example 3
(continued)
 Since we want to find the velocity at t=16, and
we are using a third order polynomial, we need
to choose the four data points closest to and also
bracket that.
 The four points are (t0, v0)=(10, 227.04), (t1,
v1)=(15, 362.78), (t2, v2)=(20, 517.35) and (t3,
v3)=(22.5, 602.97)
 Solving the above four equations gives
a0= - 4.2540
a1= 21.266
a2= 0.13204
a3= 0.0054347
 Solution to example 3
(continued)
 a
b) The absolute percentage relative approximate
error for the value obtained for v(16) between
second and third order polynomial is
392.06  392.19
a  100 0.033269%
392.06

 c) The distance covered by the rocket between

t=11s and t=16s can be calculated from the
interpolating polynomial
vt   4.2540  21.266t  0.13204t 2  0.0054347t 3 , 10 t 22.5

 Note that the polynomial is valid between t = 10 s

and t = 22.5 s and hence includes the limits of
integration of t = 11 s and t = 16 s
 Solution to example 3
(continued)
16
s 16  s 11  vt dt
11
16
 ( 4.2540  21.266t  0.13204t 2  0.0054347t 3 ) dt
11
16
 t2 t3 t4 
=   4.2540t  21.266  0.13204  0.0054347 
 2 3 4  11
= 1605m
d
d) The acceleration at t=16sec is a16  vt t 16
dt
given by,
vt   4.2540  21.266t  0.13204t 2  0.0054347t 3 , 10 t 22.5
d
a (t )   4.2540  21.266t  0.13204t 2  0.0054347t 3 
dt
So, a(16) = 29.665 m/s2
Solving the coefficients of
polynomial having high order
 If the polynomial is of nth order, there are n
numbers of unknowns, how to find out them?
 One way is to arrange the equations in matrix
form as shown below:
 f ( x 0 )  1 x 0 x02 x03 ............x0n  2 x0n  1 x0n  a 
 f ( x )  1 x x12 x13 .............x1n  2 x1n  1 n
x1  a1
 0 
 1   1
 
 f ( x 2 )  1 x 2 x 22 x 23 .............x 2n  2 x 2n  1 n 
x 2   a3 
    
 .....    ......   .... 
 .....   ......  
     .... 
 f ( x n  2 )  1 x n  2 x n2 2 x n3 2 ..........x nn 22 x nn 12 x nn 2   a n  2 
 f (x )    
 n 1
 1 x n  1 x n2 1 x n3 1 ..........x nn 12 x nn 11 xn 1   an 1 
n

 f ( x n )  1 x x n2 x n3 .............x nn  2 x nn  1 n
 a 
x n   n 
 n

[Y] = [C]
Since [A][Y] = [C] [A]
So, [A] = [C]-1 [Y]
Langrange Method
 The Lagrangian interpolating polynomial is given by
n
f n ( x)  Li ( x) f ( xi )
i 0
where n in fn(x) stands for the nth order polynomial
that approximates the function y=f(x) given at n+1
data points as (x0,y0), (x1,y1), (x2,y2),……. (xn-1,yn-1), (xn,
yn) and
n x x
Li ( x) 
j

j 0 xi  x j
j i

Li(x) is a weighting function that includes a product of n-1

terms with terms of j = i omitted. The application of
Lagrangian interpolation will be clarified using an
example.
 Example 4
 Determine the value of the velocity of the rocket
problem at t=16 seconds using a first order
Lagrange polynomial.
Solution
 For first order polynomial interpolation (also
1
called linearv(tinterpolation),
)  Li (t )v(ti ) the velocity is given
by i 0

L0 (t )v(t0 )  L1 (t )v(t1 )

1 t  tj t  t1 t  t1 t  t0
L0 (t )   Hence,v(t )  v(t0 )  v(t1 )
j 0 t0  t j t0  t1 t0  t1 t1  t0
j 0
1 t  tj t  t0
L1 (t )   v(16) = 393.69 m/s
j 0 1 t  tj t1  t0
j 1
 Since we want to find the velocity at

t 16
t 16
t 16 Solution to example 4
t 0 10, t1 15, and t 2 20
to evaluate it. The three points are
.

2
 For quadratic approximation,
v(t )  Li (t )v(ti )
i 0
L0 (t )v(t0 )  L1 (t )v(t1 )  L2 (t )v(t 2 )
Since we want to find the velocity at t=16 , and we
are using a second order polynomial, we need to
choose the three data points that are closest to
t=16 that also bracket t=16 to evaluate it. The
three
v(t )  points
 t  t1   t  are

t 2  t0=10,  t  t0 t  =15
 v(t )   1
t  t 2  and tt2=20,
 v(t )  
t0   t  hence,

t1 
 v(t ), t t t
 t  t  t  t  0  t  t  t  t  1  t  t  t  t  2 0 2
 0 1  0 2   1 0  1 2   2 0  2 1 

v(16)=392.19 m/s a
392.19 approximate
b) The absolute relative 393.69 error
a  100 0.38410 %
392.19
with respect to direct method is
 Flow Chart for Direct
Method
1 Start
for i=1..n+1 F
5 9
for i=1..n+1
2 n F
T T
x(i), y(i), 6 10 a(i)=0
3
for j=1..n+1
i=1,1,....n+1 F 11 F
4 7 T for j=1..n+1
xu 12 T
c(i,j)=x(i)^(j-1)
a(i)=a(i)+ci(i,j)*y(j)
8 ci=inv(c)
13 fxu=0
14 F
for i=1..n+1
T
17 16 15 fxu=fxu+a(i)*xu^(i-1)
End xu, fxu
 Flow Chart for Langrage
method
1 Start 7
2 n L(i)=1
9
3
x(i), y(i), for j=1..n+1 T j:i
i=1...n+1 =
F 8 =
4 xu L(i)=L(i)*(xu-x(j))/(x(i)-
x(j))
5 fxu=0 1
fxu=fxu+L(i)*y(i)
0
1
6 for i=1..n+1 1
T
F 1
2
End
1 xu, fxu
0
Thanks