Newton’s Divided Difference

Polynomial Method of
Interpolation

Dr. Mohammad Salah Uddin

Assistant Professor
Department of Computer Science and Engineering
East West University, Dhaka.
CSE225 Numerical Methods 1
 Newton’s Divided
Difference Method of
Interpolation

CSE225 Numerical Methods 2

 What is Interpolation ?
Given (x0,y0), (x1,y1), …… (xn,yn), find the
value of ‘y’ at a value of ‘x’ that is not given.

3 CSE225 Numerical Methods

 Interpolants
Polynomials are the most common
choice of interpolants because they
are easy to:

Evaluate
Differentiate, and
Integrate.

4 CSE225 Numerical Methods

 Newton’s Divided Difference
Method
Linear interpolation: Given ( x0 , y0 ), ( x1 , y1 ), pass a
linear interpolant through the data
f1 ( x)  b0  b1 ( x  x0 )

where
b0  f ( x0 )
f ( x1 )  f ( x0 )
b1 
x1  x0

5 CSE225 Numerical Methods

 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 Newton Divided Difference 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
6
for the rocket example CSE225 Numerical Methods
 Linear Interpolation
550
517.35

v(t )  b0  b1 (t  t 0 ) 500

ys

t 0  15, v(t 0 )  362.78 f ( range)

450

f x de sire d
t1  20, v(t1 )  517.35
b0  v(t 0 )  362.78 400

v(t1 )  v(t 0 )
b1   30.914 362.78
t1  t 0
350
10 12 14 16 18 20 22 24
x s  10 x s  range x de sire d x s  10
0 1

7 CSE225 Numerical Methods

 Linear Interpolation (contd)
550
517.35

500

ys

f ( range)
450

f x de sire d

400

362.78 350
10 12 14 16 18 20 22 24
x s  10 x s  range x de sire d x s  10

v(t )  b0  b1 (t  t 0 )
0 1

 362.78  30.914(t  15), 15  t  20

At t  16
v(16)  362.78  30.914(16  15)
 393.69 m/s
8 CSE225 Numerical Methods
 Quadratic Interpolation
Given ( x0 , y0 ), ( x1 , y1 ), and ( x2 , y 2 ), fit a quadratic interpolant through the data.
f 2 ( x)  b0  b1 ( x  x0 )  b2 ( x  x0 )( x  x1 )

b0  f ( x0 )

f ( x1 )  f ( x0 )
b1 
x1  x0

f ( x 2 )  f ( x1 ) f ( x1 )  f ( x0 )

x 2  x1 x1  x0
b2 
x 2  x0

9 CSE225 Numerical Methods

 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 Newton Divided Difference 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
10
for the rocket example CSE225 Numerical Methods
 Quadratic Interpolation (contd)
550
517.35

500

450

ys
400
f ( range)


f x de sire d 350

300

250

227.04 200
10 12 14 16 18 20
10 x s  range x de sire d 20

t 0  10, v(t 0 )  227.04

t1  15, v(t1 )  362.78
t 2  20, v(t 2 )  517.35
11 CSE225 Numerical Methods
 Quadratic Interpolation (contd)
b0  v(t 0 )
 227.04
v(t )  v(t 0 ) 362.78  227.04
b1  1 
t1  t 0 15  10
 27.148

v(t 2 )  v(t1 ) v(t1 )  v(t 0 ) 517.35  362.78 362.78  227.04

 
t 2  t1 t1  t 0 20  15 15  10
b2  
t 2  t0 20  10
30.914  27.148

10
 0.37660
12 CSE225 Numerical Methods
 Quadratic Interpolation (contd)
v(t )  b0  b1 (t  t 0 )  b2 (t  t 0 )(t  t1 )
 227.04  27.148(t  10)  0.37660(t  10)(t  15), 10  t  20
At t  16,
v(16)  227.04  27.148(16  10)  0.37660(16  10)(16  15)  392.19 m/s

The absolute relative approximate error a obtained between the results from the first
order and second order polynomial is

392.19  393.69
a  x100
392.19

= 0.38502 %

13 CSE225 Numerical Methods

 General Form
f 2 ( x)  b0  b1 ( x  x0 )  b2 ( x  x0 )( x  x1 )
where
b0  f [ x0 ]  f ( x0 )
f ( x1 )  f ( x 0 )
b1  f [ x1 , x0 ] 
x1  x0
f ( x 2 )  f ( x1 ) f ( x1 )  f ( x0 )

f [ x 2 , x1 ]  f [ x1 , x0 ] x 2  x1 x1  x0
b2  f [ x 2 , x1 , x0 ]  
x 2  x0 x 2  x0
Rewriting
f 2 ( x)  f [ x0 ]  f [ x1 , x0 ]( x  x0 )  f [ x2 , x1 , x0 ]( x  x0 )( x  x1 )

14 CSE225 Numerical Methods

 General Form
Given (n  1) data points, x0 , y0 , x1 , y1 ,......, xn1 , y n1 , xn , y n  as
f n ( x)  b0  b1 ( x  x0 )  ....  bn ( x  x0 )( x  x1 )...( x  xn1 )
where
b0  f [ x0 ]
b1  f [ x1 , x0 ]
b2  f [ x2 , x1 , x0 ]

bn1  f [ xn1 , xn2 ,...., x0 ]
bn  f [ xn , xn1 ,...., x0 ]

15 CSE225 Numerical Methods

 General form
The third order polynomial, given ( x0 , y0 ), ( x1 , y1 ), ( x2 , y 2 ), and ( x3 , y3 ), is

f 3 ( x)  f [ x0 ]  f [ x1 , x0 ]( x  x0 )  f [ x2 , x1 , x0 ]( x  x0 )( x  x1 )
 f [ x3 , x2 , x1 , x0 ]( x  x0 )( x  x1 )( x  x2 )
b0
x0 f ( x0 ) b1
f [ x1 , x0 ] b2
x1 f ( x1 ) f [ x2 , x1 , x0 ] b3
f [ x2 , x1 ] f [ x3 , x2 , x1 , x0 ]
x2 f ( x2 ) f [ x3 , x2 , x1 ]
f [ x3 , x 2 ]
x3 f ( x3 )

16 CSE225 Numerical Methods

 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 Newton Divided Difference 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
17
for the rocket example CSE225 Numerical Methods
 Example
The velocity profile is chosen as
v(t )  b0  b1 (t  t 0 )  b2 (t  t 0 )(t  t1 )  b3 (t  t 0 )(t  t1 )(t  t 2 )
we need to choose four data points that are closest to t  16
t0  10, v(t 0 )  227.04
t1  15, v(t1 )  362.78
t 2  20, v(t 2 )  517.35
t 3  22.5, v(t 3 )  602.97

The values of the constants are found as:

b0 = 227.04; b1 = 27.148; b2 = 0.37660; b3 = 5.4347×10−3
18 CSE225 Numerical Methods
 Example
b0
t0  10 227.04 b1
27.148 b2
t1  15, 362.78 0.37660 b3
30.914 5.4347 103
t2  20, 517.35 0.44453
34.248
t3  22.5, 602.97

b0 = 227.04; b1 = 27.148; b2 = 0.37660; b3 = 5.4347×10−3

19 CSE225 Numerical Methods

 Example
Hence
v (t )  b0  b1 (t  t 0 )  b2 (t  t 0 )( t  t1 )  b3 (t  t 0 )( t  t1 )(t  t 2 )
 227.04  27.148( t  10)  0.37660(t  10)(t  15)
 5.4347 * 10 3 (t  10)( t  15)( t  20)
At t  16,
v (16)  227.04  27.148(16  10)  0.37660(16  10)(16  15)
 5.4347 * 10 3 (16  10)(16  15)(16  20)
 392.06 m/s
The absolute relative approximate error a obtained is
392.06  392.19
a  x100
392.06

= 0.033427 %
20 CSE225 Numerical Methods
 Comparison Table

Order of 1 2 3
Polynomial
v(t=16) 393.69 392.19 392.06
m/s
Absolute Relative ---------- 0.38502 % 0.033427 %
Approximate Error

21 CSE225 Numerical Methods

 Distance from Velocity Profile
Find the distance covered by the rocket from t=11s to
t=16s ?
v (t )  227.04  27.148(t  10)  0.37660( t  10)( t  15)
10  t  22.5
 5.4347 * 10 (t  10)( t  15)( t  20)
3

 4.2541  21.265t  0.13204t 2  0.0054347t 3 10  t  22.5

So
16

s16  s11   v t dt

11

16

  (  4.2541  21.265t  0.13204t 2  0.0054347t 3 ) dt

11

16
 t2 t3 t4 
  4.2541t  21.265  0.13204  0.0054347 
 2 3 4  11

22  1605 m CSE225 Numerical Methods

 Acceleration from Velocity Profile
Find the acceleration of the rocket at t=16s given that

v(t )  4.2541  21.265t  0.13204t 2  0.0054347t 3

a (t ) 
d
dt
v(t ) 
d

dt
 4.2541  21.265t  0.13204t 2  0.0054347t 3 
 21.265  0.26408t  0.016304t 2

a(16)  21.265  0.26408(16)  0.016304(16) 2

 29.664 m / s 2

23 CSE225 Numerical Methods

 THE END

24 CSE225 Numerical Methods