Numerical

Analysis
Lecture 20
 Chapter 5
Interpolation
Finite
Finite Difference
Difference Operators
Operators
Newton’s
Newton’s Forward
Forward Difference
Difference
Interpolation
Interpolation Formula
Formula
Newton’s
Newton’s Backward
Backward Difference
Difference
Interpolation
Interpolation Formula
Formula
Lagrange’s
Lagrange’s Interpolation
Interpolation
Formula
Formula
Divided
Divided Differences
Differences
Interpolation
Interpolation in
in Two
Two Dimensions
Dimensions
Cubic
Cubic Spline
Spline Interpolation
Interpolation
Introduction
Finite
Finite differences
differences play
play an
an
important
important role
role in
in numerical
numerical
techniques,
techniques, where
where
tabulated
tabulated values
values of
of the
the
functions
functions are
are available.
available.
For
For instance,
instance, consider
consider aa
function
function
y  f ( x).
As
As xx takes
takes values
values

x0 , x1 , x2 , , xn ,
let
let the
the corresponding
corresponding values
values
of
of yy be
be

y0 , y1 , y2 , , yn .
That is, for given a table of
values,
( xk , yk ), k 0,1, 2, , n;

the process of estimating

the value of y, for any
intermediate value of x, is
called interpolation.
The method of computing
the value of y, for a given
value of x, lying outside
the table of values of x is
known as extrapolation.
Finite
Finite Difference
Difference Operators
Operators

Forward
Forward Differences
Differences

Backward
Backward Differences
Differences

Central
Central Difference
Difference
To be explicit, we write
y0  y1  y0
y1  y2  y1
  
yn  1  yn  yn  1
Similarly, the differences of
the first differences are
called second differences,
defined by
2 2
 y0 y1  y0 ,  y1 y2  y1

Thus, in general
2
 yi yi 1  yi
 2
Here  is called the second
difference operator. Thus,
continuing, we can define,
r-th difference of y, as

r r 1 r 1
 yi  yi 1   yi
Backward
Differences
yi  yi  yi  1i n, (n  1), ,1

y1  y1  y0
OR y2  y2  y1
  
yn  yn  yn  1
The differences of these
differences are called second
differences and they are
denoted by 2 y , 2 y , , 2 y .
2 3 n

That is 2
 y1 y2  y1
2
 y2 y3  y2
  
2
 yn yn  yn  1
Thus, in general, the second
backward differences are
2
 yi yi  yi  1 , i n, (n  1),..., 2

while the k-th backward

differences are given as
k k1 k1
 yi  yi   yi  1 , i n, (n  1),..., k
 y1 2  y1  y0 ,  y3 2  y2  y1 ,
In general
 yi  yi (1 2)  yi  (1 2)
Higher order differences are
defined as follows:
 yi  yi (1 2)   yi  (1 2)
2

n 1 n 1
 yi 
n
yi (1 2)   yi  (1 2)
Thus
y x  yx h  yx  f ( x  h)  f ( x)
2
 y x y x h  yx
Similarly
y x  y x  y x  h  f ( x)  f ( x  h)
 h  h
 yx  y x ( h / 2)  y x  ( h / 2) f x  f x 
 2  2
Shift operator, E
Let y = f (x) be a function of x,
and let x takes the consecutive
values x, x + h, x + 2h, etc. We
then define an operator having
the property

E f ( x )  f ( x  h)
Thus, when E operates on f (x),
the result is the next value of
the function. Here, E is called
the shift operator. If we apply
the operator E twice on f (x),
we get
2
E f ( x) E[ E f ( x)]
E[ f ( x  h)]  f ( x  2h)
Thus, in general, if we apply the
operator ‘E’ n times on f (x), we get
n
E f ( x)  f ( x  nh)
or
n
E y x  y x nh
Ey0  y1 , E 2 y0  y 2 , E 4 y0  y 4 , , E 2 y2  y4
The inverse operator E -1

is defined as
1
E f ( x )  f ( x  h)
Similarly,

n
E f ( x)  f ( x  nh)
 Average Operator, 
1  h  h 
 f ( x)   f x  f  x  
2  2  2 
1
  y x ( h / 2)  y x  ( h / 2) 
2
Differential Operator, D

d 
Df ( x)  f ( x)  f ( x) 
dx 
2 
d 
2


D f ( x)  2 f ( x)  f ( x)
dx 
Important Results
Using

, ,  , E , 
y x  y x h  y x Ey x  y x
( E  1) y x

  E  1
 1
y x  y x  y x  h  y x  E y x
1
(1  E ) y x

E1 1
  1  E 
E
 yx  yx ( h / 2)  yx  ( h / 2)
1/ 2  1/ 2
E yx  E yx
1/ 2  1/ 2
( E  E ) yx

 1/ 2
 E 1/ 2
 E
The definition of  and E
similarly yields
1
 yx   yx ( h / 2)  yx  ( h / 2) 
2
1 1/ 2  1/ 2
 ( E  E ) yx
2
1 1/ 2  1/ 2
   (E  E )
2
We know that
Ey x  y x h  f ( x  h)
h2
Ey x  f ( x)  hf ( x)  f ( x) 
2!
h2 2
 f ( x)  hDf ( x)  D f ( x) 
2!
 hD h 2 D 2  hD
 1      f ( x) e y x
 1! 2! 

Thus, hD log E
Example
Prove
Prove that
that
hD log(1   )
 log(1  )
1
sinh (  )
Solution
Using the standard relations we
have hD log E

log(1   )
1
 log E
 log(1  )
Also 1  1/ 2  1/ 2
  ( E  E )( E  E )
1/ 2 1/ 2

2
1 1
 (E  E )
2
1 hD  hD
 (e  e )
2
sinh(hD)
1
 hD sinh 
Example Prove that
2
(i)    2
1     1  
2 2

 2 
(ii) 
E 1/ 2
 
2
(iii)  2
   1  ( / 4)
2

2
Cont! Prove that
1
(iv) E 
  
2 2
(v)  
 
2
Solution
Solution
From
From the
the definition,
definition, we
we have:
have:
1 1/ 2  1/ 2  1/ 2 1 1
  ( E  E )( E  E )  ( E  E )
1/ 2

2 2

1 2 2 1 1 2
 1    1  ( E  2  E )  ( E  E )
2 2

4 4

 2
1 1/ 2  1/ 2 2 1 1 2
1 1  ( E  E )  ( E  E )
2 2 2
(ii) Now
  ( / 2)
1 1/ 2  1/ 2 1/ 2  1/ 2 1/ 2
 (E  E  E  E ) E
2
Thus, the second result is
proved.
(iii)
(iii) We
We can
can write
write
1 1/ 2
  E  1  E  E 
1/ 2  1/ 2  1/ 2 2
2
  1  ( 2 / 4) 
 E 1/ 2
 E  1/ 2 2  E
4
2 2 1

E  2  E  1 1 1/ 2
  ( E  E  1/ 2 )( E1/ 2  E  1/ 2 )
2 2
1 1
E  2E E E
 
2 2

E  1 
(iv)
(iv) We
We have
have
1 1/ 2 1
  ( E  E )( E  E )  ( E  E  1 )
 1/ 2 1/ 2  1/ 2

2 2

1 1  1 1
 (1    E )   (1  E )
2 2 2
 1  E  1  
    
2 2  E  2 2E
(v)
(v) We
We can
can write
write
1 1/ 2  1/ 2  1/ 2
  ( E  E )( E  E )
1/ 2

2
1 1
 (E  E )
2

1 1
 (1    1  )  (  )
2 2
Example
Show
Show that
that the
the
operations
operations  and
and E
E
commute.
commute.
E   E
Numerical
Analysis
Lecture 20