Interpolation

Interpolation

Dr. Sukanta Deb

Department of Physics, Cotton University

Panbazar, Guwahati (Assam)

Dr. Sukanta Deb Interpolation 1 / 32

 Interpolation

Outline of the Talk

1 Interpolation
Lagrange Interpolation
Newton-Gregory Interpolation

Dr. Sukanta Deb Interpolation 2 / 32

 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

Table of Contents

1 Interpolation
Lagrange Interpolation
Newton-Gregory Interpolation

Dr. Sukanta Deb Interpolation 3 / 32

 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

What is an Interpolation?

It refers to a curve that passes through all the given points.

Dr. Sukanta Deb Interpolation 4 / 32

 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

Linear Interpolation
Let us consider the interpolation of two data points (x0 , y0 ) and
(x1 , y1 ) using a linear equation of the form:
y =mx + c,
where m and c represent the slope and intercept of the line. Since
in interpolation, the curve must pass through all the data points,
we have
y0 =mx0 + c, y1 = mx1 + c.
Solving the above two equations, we get
y1 − y0
y1 − y0 =m(x1 − x0 ) ⇒ m = .
x1 − x0

y1 − y0 y0 (x1 − x0 ) − (y1 − y0 )x0

   
∴ c = y0 − mx0 = y0 − x0 =
x1 − x0 x1 − x0
Dr. Sukanta Deb Interpolation 5 / 32
 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

Linear Interpolation

x1 y0 − 
x00 − x 0 y1 + 
y x0
y
0 x 1 y0 − x 0 y1
c= = .
x1 − x0 x1 − x0
Therefore we have the linear interpolation

y =mx + c
y1 − y0 x 1 y0 − x 0 y1
 
⇒y= x+ .
x1 − x0 x1 − x0

Remember
Interpolation using polynomial of degree n requires exactly
(n+1) data points. Therefore interpolation using polynomial
of degree one (linear interpolation) requires exactly two data
points and so on.

Dr. Sukanta Deb Interpolation 6 / 32

 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

Table of Contents

1 Interpolation
Lagrange Interpolation
Newton-Gregory Interpolation

Dr. Sukanta Deb Interpolation 7 / 32

 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

Linear Lagrange Interpolation

Let us consider interpolation of two data points (x0 , y0 ) and
(x1 , y1 ) using a linear equation of the following form as proposed
by Joseph Louis Lagrange1 :
P1 (x) =a0 (x − x1 ) + a1 (x − x0 ) , y = P1 (x), (1)
where a0 and a1 are constants. The points x0 and x1 are called
the centers. Equation (1) written in such a way directly represents
the two interpolated points (x0 , y0 ) and (x1 , y1 ).
At (x0 , y0 ):
y0
y0 = a0 (x0 − x1 ) ⇒ a0 = .
x0 − x1
At (x1 , y1 ):
y1
y1 = a1 (x1 − x0 ) ⇒ a1 = .
x1 − x0
1
French mathematician
Dr. Sukanta Deb Interpolation 8 / 32
 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

Linear Lagrange Interpolation

Substituting the values of a0 and a1 in equation (1), we get

P1 (x) =a0 (x − x1 ) + a1 (x − x0 )
y0 y1
   
⇒ P1 (x) = (x − x1 ) + (x − x0 )
x0 − x1 x1 − x0
x − x1 x − x0
   
⇒ P1 (x) =y0 + y1 .
x0 − x1 x1 − x0
This is the form of the Linear Lagrange interpolating polynomial.

Dr. Sukanta Deb Interpolation 9 / 32

 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

Quadratic Lagrange Interpolation

The quadratic form of the Lagrange interpolating polynomial
interpolates three data points (x0 , y0 ), (x1 , y1 ) and (x2 , y2 ). Let
the form of the polynomial be given by

P2 (x) =a0 (x − x1 )(x − x2 ) + a1 (x − x0 )(x − x2 ) + a2 (x − x0 )(x − x1 ),

where y = P2 (x); a0 , a1 and a2 are constants; x0 , x1 and x2 are

centers.
At (x0 , y0 ):
y0
y0 = a0 (x0 − x1 )(x0 − x2 ) ⇒ a0 = .
(x0 − x1 )(x0 − x2 )
At (x1 , y1 ):
y1
y1 = a1 (x1 − x0 )(x1 − x2 ) ⇒ a1 = .
(x1 − x0 )(x1 − x2 )

Dr. Sukanta Deb Interpolation 10 / 32

 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

Quadratic Lagrange Interpolation

At (x2 , y2 ):
y2
y2 = a2 (x2 − x0 )(x2 − x1 ) ⇒ a2 = .
(x2 − x0 )(x2 − x1 )
y0
∴ P2 (x) = (x − x1 )(x − x2 )+
(x0 − x1 )(x0 − x2 )
y1
(x − x0 )(x − x2 )+
(x1 − x0 )(x1 − x2 )
y2
(x − x0 )(x − x1 )
(x2 − x0 )(x2 − x1 )
(x − x1 )(x − x2 ) (x − x0 )(x − x2 )
⇒ P2 (x) =y0 + y1
(x0 − x1 )(x0 − x2 ) (x1 − x0 )(x1 − x2 )
(x − x0 )(x − x1 )
y2
(x2 − x0 )(x2 − x1 )
⇒ P2 (x) =y0 l0 (x) + y1 l1 (x) + y2 l2 (x),
Dr. Sukanta Deb Interpolation 11 / 32
 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

Quadratic Lagrange Interpolation

where
(x − x1 )(x − x2 )
l0 (x) = ,
(x0 − x1 )(x0 − x2 )
(x − x0 )(x − x2 )
l1 (x) = ,
(x1 − x0 )(x1 − x2 )
(x − x0 )(x − x1 )
l2 (x) = .
(x2 − x0 )(x2 − x1 )
l0 , l1 and l2 are called Lagrange operators.
Remember
+ Lagrange interpolation does not require data points to
be equally spaced. That is, it is applicable to either
equal or unequal intervals.
+ The abscissae x0 , x1 , . . . , xn need not be in order.

Dr. Sukanta Deb Interpolation 12 / 32

 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

Lagrange Polynomial of Degree n

In general, the Lagrange polynomial of degree n produced from an
interpolation over a set of (n + 1) data points (xi , yi ),
i=0, 1, . . . , n is given by

Pn (x) =y0 l0 (x) + y1 l1 (x) + y2 l2 (x) + · · · + yn ln (x)

n
X
⇒ Pn (x) = yi li (x),
i=0

where li (x) is given by

n
Y x − xj
li (x) =
j=1
xi − xj
j,i

Dr. Sukanta Deb Interpolation 13 / 32

 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

1 Determine the value of y(301) given the following table:

x: 300 304 305 307
y: 2.4771 2.4829 2.4843 2.4871
Since there are 4 data points, Lagrange interpolating polynomial of
degree 3 can be fitted to the data:
3
X
P3 (x) = yi li = y0 l0 + y1 l1 + y2 l2 + y3 l3 ,
i=0

n
Y x − xj
li (x) = , i = 0, 1, 2, 3.
j=1
xi − xj
j,i
3
x− xj x − x1 x − x2 x − x3
Y    
∴ l0 = =
j=1
x0 − xj x0 − x1 x0 − x2 x0 − x3
j,0
301 − 304 301 − 305 301 − 307
   
= = 0.5143
300 − 304 300 − 305 300 − 307
Dr. Sukanta Deb Interpolation 14 / 32
 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

3
x− xj x − x0 x − x2 x − x3
Y    
l1 = = = 2.000,
j=1
x1 − xj x1 − x0 x1 − x2 x1 − x3
j,1
3
x− xj x − x0 x − x1 x − x3
Y    
l2 = = = −1.800,
j=1
x2 − xj x2 − x0 x2 − x1 x2 − x3
j,2
3
x− xj x − x0 x − x1 x − x2
Y    
l3 = = = 0.2857,
j=1
x3 − xj x3 − x0 x3 − x1 x3 − x2
j,3

∴ P3 (301) =2.4771 × (0.5143) + 2.4829 × (2.000)+

2.4843 × (−1.800) + 2.4871 × (0.2857)
=2.4786.

Dr. Sukanta Deb Interpolation 15 / 32

 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

Table of Contents

1 Interpolation
Lagrange Interpolation
Newton-Gregory Interpolation

Dr. Sukanta Deb Interpolation 16 / 32

 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

Finite Differences
Forward Differences: Let y0 , y1 , y2 , . . . , yn denote a set of values of
y. Then y1 − y0 , y2 − y1 , . . . , yn − yn−1 are called the differences
of y. Denoting these differences by ∆y0 , ∆y1 , . . . , ∆yn−1 ,
respectively, we have
∆y0 =y1 − y0 , ∆y1 = y2 − y1 , . . . , ∆yn−1 = yn − yn−1 ,
where ∆ is called the forward difference operator and
∆y0 , ∆y1 , . . . are called the first forward differences. The
differences of the first forward differences are called second forward
differences and are denoted by ∆2 y0 , ∆2 y1 , . . . , . . . . Similarly, one
can define third forward differences, fourth forward differences, etc.
∴ ∆2 y0 =∆y1 − ∆y0 = (y2 − y1 ) − (y1 − y0 ) = y2 − 2y1 + y0 ,
∆3 y0 =∆2 (∆y0 ) = ∆2 y1 − ∆2 y0 = y3 − 2y2 + y1 − (y2 − 2y1 + y0 )
=y3 − 3y2 + 3y1 − y0 ,
Dr. Sukanta Deb Interpolation 17 / 32
 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

Finite Differences
∆4 y0 =∆3 (∆y0 ) = ∆3 y1 − ∆2 y0
=y4 − 3y3 + 3y2 − y1 − (y3 − 3y2 + 3y1 − y0 )
=y4 − 4y3 + 6y2 − 4y1 + y0 .
In this way, any higher order difference can be easily expressed in
terms of the ordinate (y) values, since the coefficients occurring on
the right hand side are the binomial coefficients.
Table: Forward difference table

x y ∆y ∆2 y ∆3 y ∆4 y
x0 y0
∆y0
x1 y1 ∆2 y0
∆y1 ∆ 3 y0
x2 y2 ∆2 y1 ∆4 y0
∆y2 ∆ 3 y1
x3 y3 ∆2 y2
∆y3
x4 y4
Dr. Sukanta Deb Interpolation 18 / 32
 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

Finite Differences
Backward Differences: Let y0 , y1 , y2 , . . . , yn denote a set of values
of y. Then y1 − y0 , y2 − y1 , . . . , yn − yn−1 are called the
differences of y. Denoting these differences by ∇y1 , ∇y2 , . . . , ∇yn ,
respectively, we have
∇y1 =y1 − y0 , ∇y2 = y2 − y1 , . . . , ∇yn = yn − yn−1 ,
where ∇ is called the backward difference operator and
∇y1 , ∇y2 , . . . are called the first backward differences. The
differences of the first backward differences are called second
backward differences and are denoted by ∇2 y1 , ∇2 y2 , . . . , . . . .
Similarly, one can define third backward differences, fourth
backward differences, etc.
∴ ∇2 y2 =∇y2 − ∇y1 = (y2 − y1 ) − (y1 − y0 ) = y2 − 2y1 + y0 ,
∇3 y3 =∇2 (∇y3 ) = ∇2 y3 − ∇2 y2 = y3 − 2y2 + y1 − (y2 − 2y1 + y0 )
=y3 − 3y2 + 3y1 − y0 ,
Dr. Sukanta Deb Interpolation 19 / 32
 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

Finite Differences
∇4 y4 =∇3 (∇y4 ) = ∇3 y4 − ∆2 y3
=y4 − 3y3 + 3y2 − y1 − (y3 − 3y2 + 3y1 − y0 )
=y4 − 4y3 + 6y2 − 4y1 + y0 .
In this way, any higher order difference can be easily expressed in
terms of the ordinate (y) values, since the coefficients occurring on
the right hand side are the binomial coefficients.
Table: Backward difference table

x y ∇y ∇2 y ∇3 y ∇4 y
x0 y0
x1 y1 ∇y1
x2 y2 ∇y2 ∇2 y2
x3 y3 ∇y3 ∇2 y3 ∇3 y3
x4 y4 ∇y4 ∇4 y2 ∆3 y4 ∇ 4 y4
Dr. Sukanta Deb Interpolation 20 / 32
 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

Newton-Gregory’s Forward Difference Interpolation

Let us consider a set of (n + 1) tabulated values (x0 , y0 ), (x1 , y1 ),

. . . , (xn , yn ) of x and y. The problem is to find a interpolating
polynomial of nth degree, Pn (x) such that y and Pn (x) match at
the tabulated points. Let us consider the values of x to be
equidistant, i.e.,

xi = x0 + ih, i = 0, 1, . . . , n.

Let the interpolating polynomial Pn (x) be of the form

Pn (x) =a0 + a1 (x − x0 ) + a2 (x − x0 )(x − x1 ) + · · · +

an (x − x0 ) . . . (x − xn−1 ), (2)

where the constants a0 , a1 , . . . , an can be determined as follows:

Dr. Sukanta Deb Interpolation 21 / 32

 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

Newton-Gregory’s Forward Difference Interpolation

For x = x0 , a0 = y0
y1 − y0 ∆y0
For x = x1 , a1 = =
x1 − x0 h
y2 − 2y1 + y0 ∆ 2 y0
For x = x2 , a2 = =
h2 2! h2 2!
..
.
∆ n y0
For x = xn , an =
hn n!
Let us set
x = x0 + ph.

Dr. Sukanta Deb Interpolation 22 / 32

 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

Newton-Gregory’s Forward Difference Interpolation

∴ x − x0 =ph
x − x1 = (x0 + ph) − x0 − h = h(p − 1)
x − x2 = (x0 + ph) − x0 − 2h = h(p − 2)
..
.
x − xn−1 = (x0 + ph) − x0 − (n − 1)h = h(p − n + 1)

Substituting these values into the equation (2), we get

p(p − 1) 2 p(p − 1)(p − 2) 3
Pn (x) =y0 + p∆y0 + ∆ y0 + ∆ y0 + · · · +
2! 3!
p(p − 1)(p − 2) . . . (p − n + 1) n
∆ y0
n!
This is known as the Newton-Gregory’s forward difference
interpolation formula. This formula is particularly useful for
interpolation near the beginning of a set of tabulated values.
Dr. Sukanta Deb Interpolation 23 / 32
 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

2 Determine the value of y(0.12) given the following table:

x: 0.10 0.15 0.20 0.25 0.30

y: 0.1003 0.1511 0.2027 0.2553 0.3093

To find y(0.12) we use Newton’s forward interpolation formula.

The forward difference table from the given data can be
constructed as follows:

x y ∆y ∆2 y ∆3 y ∆4 y
0.10 0.1003
0.0508
0.15 0.1511 0.0008
0.0516 0.0002
0.20 0.2027 0.0010 0.0002
0.0526 0.0004
0.25 0.2553 0.0014
0.0540
0.30 0.3093

Dr. Sukanta Deb Interpolation 24 / 32

 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

Here h = 0.05, x0 = 0.1, x = 0.12. So the value of p is

x − x0 0.12 − 0.1
p= = = 0.4.
h 0.05
Applying the Newton Gregory’s forward difference interpolation
formula, we have
p(p − 1) 2 p(p − 1)(p − 2) 3
y(x) =y0 + p∆y0 + ∆ y0 + ∆ y0 +
2! 3!
p(p − 1)(p − 2)(p − 3) 4
∆ y0
4!
0.4(0.4 − 1)
⇒ y(0.12) =0.1003 + 0.4(0.0508) + (0.0008)+
2
0.4(0.4 − 1)(0.4 − 2)
(0.0002)+
6
0.4(0.4 − 1)(0.4 − 2)(0.4 − 3)
(0.0002)
24
⇒ y(0.12) =0.1205.
Dr. Sukanta Deb Interpolation 25 / 32
 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

Newton-Gregory’s Backward Difference Interpolation

Let us consider a set of (n + 1) tabulated values (x0 , y0 ), (x1 , y1 ),

. . . , (xn , yn ) of x and y. The problem is to find a interpolating
polynomial of nth degree, Pn (x) such that y and Pn (x) match at
the tabulated points. Let us consider the values of x to be
equidistant, i.e.,

xi = x0 + ih, i = 0, 1, . . . , n.

Let the interpolating polynomial Pn (x) be of the form

Pn (x) =a0 + a1 (x − xn ) + a2 (x − xn )(x − xn−1 )+

· · · + an (x − xn ) . . . (x − x1 ), (3)

where the constants a0 , a1 , . . . , an can be determined as follows:

Dr. Sukanta Deb Interpolation 26 / 32

 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

Newton-Gregory’s Backward Difference Interpolation

For x = xn , a 0 = yn
yn − yn−1 ∇yn
For x = xn−1 , a1 = =
xn − xn−1 h
yn−2 − 2yn−1 + yn ∇2 yn
For x = xn−2 , a2 = =
h2 2! h2 2!
..
.
∇ n yn
For x = x0 , an =
hn n!
Let us set
x = xn + ph.

Dr. Sukanta Deb Interpolation 27 / 32

 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

Newton-Gregory’s Backward Difference Interpolation

∴ x − xn =ph
x − xn−1 = (xn + ph) − xn + h = h(p + 1)
x − xn−2 = (xn + ph) − xn + 2h = h(p + 2)
..
.
x − x0 = (xn + ph) − xn + (n − 1)h = h(p + n − 1)

Substituting these values into the equation (3), we get

p(p + 1) 2 p(p + 1)(p + 2) 3
Pn (x) =yn + p∇yn + ∇ yn + ∇ yn +
2! 3!
p(p + 1)(p + 2) . . . (p + n − 1) n
··· + ∇ yn
n!
This is known as the Newton-Gregory’s backward difference
interpolation formula. This formula is particularly useful for
interpolation near the end of a set of tabulated values.
Dr. Sukanta Deb Interpolation 28 / 32
 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

3 Determine the value of y(0.26) given the following table:

x: 0.10 0.15 0.20 0.25 0.30

y: 0.1003 0.1511 0.2027 0.2553 0.3093

To determine y(0.26) we use Newton’s backward interpolation

formula. The backward difference table from the given data can be
constructed as follows:

x y ∇y ∇2 y ∇3 y ∇4 y
0.10 0.1003
0.15 0.1511 0.0508
0.20 0.2027 0.0516 0.0008
0.25 0.2553 0.0526 0.0010 0.0002
0.30 0.3093 0.0540 0.0014 0.0004 0.0002

Dr. Sukanta Deb Interpolation 29 / 32

 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

Here h = 0.05, x0 = 0.1, xn = x4 = 0.30, x = 0.26. So the value

of p is:
x − xn 0.26 − 0.30
p= = = −0.8.
h 0.05
Applying the Newton Gregory’s backward difference interpolation
formula, we have
p(p + 1) 2 p(p + 1)(p + 2) 3
y(x) =y4 + p∇y4 + ∇ y4 + ∇ y4 +
2! 3!
p(p + 1)(p + 2)(p + 3) 4
∆ y4
4!
(−0.8)(−0.8 + 1)
⇒ y(0.26) =0.3093 − 0.8(0.0540) + (0.0014)+
2
(−0.8)(−0.8 + 1)(−0.8 + 2)
(0.0004)+
6
(−0.8)(−0.8 + 1)(−0.8 + 2)(−0.8 + 3)
(0.0002)
24
⇒ y(0.26) =0.2662.
Dr. Sukanta Deb Interpolation 30 / 32
 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

Assignment
1 Find a polynomial that interpolates the following data points
using the Lagrange method. Hence find P (2.5).
x : −1 0 2 5
y: 2 3 −1 1
2 Find a polynomial that interpolates the following data points
using the Newton’s forward-difference method. Hence find
P (−1).
x : −2 0 2 4
y: 2 3 −1 1
3 Find a polynomial that interpolates the following data points
using the Newton’s backward-difference method. Hence find
P (2.5).
x : −2 0 2 4
y: 2 3 −1 1
Dr. Sukanta Deb Interpolation 31 / 32
 Lagrange Interpolation
Interpolation
Newton-Gregory Interpolation

Contact Me?
QPPPPPPRQPPPPPPRQPPPPPPRQPPPPPPRQPPPPPPRQPPPPPPRQPPPPPPRQPPPPPPRQPPPPPPR

THANK YOU!

For any queries, suggestions:

k sukantodeb@[Link]

T 9810362087

Í [Link]

QPPPPPPRQPPPPPPRQPPPPPPRQPPPPPPRQPPPPPPRQPPPPPPRQPPPPPPRQPPPPPPRQPPPPPPR
Dr. Sukanta Deb Interpolation 32 / 32