Interpolation with unevenly spaced points
Numerical Analysis-5
Dr. S.D. Purohit
Department of HEAS (Mathematics), RTU Kota
Dr. S.D. Purohit, UD, RTU, Kota B.Tech. III Semester (ME/P&I)
Interpolation with unevenly spaced points
We discuss, in the present section, Lagrange’s interpolation and Newton’s
general interpolation formulae.
Dr. S.D. Purohit, UD, RTU, Kota B.Tech. III Semester (ME/P&I)
Interpolation with unevenly spaced points
Lagrange’s interpolation formula:
Given the (n + 1) points (x0 , y0 ), (x1 , y1 ), · · · , (xn , yn ) where the values of x
need not necessarily be equally spaced. The Lagrange’s interpolating
polynomial passes through given data points is given as:
n
X
Pn (x) = `i (x) yi , yi = y(xi ) (1)
i=0
= `0 (x) y0 + `1 (x) y1 + `2 (x) y2 + · · · + `n (x) yn (2)
where
(x − x0 )(x − x1 ) · · · (x − xi−1 )(x − xi+1 ) · · · (x − xn )
`i (x) = .
(xi − x0 )(xi − x1 ) · · · (xi − xi−1 )(xi − xi+1 ) · · · (xi − xn )
Dr. S.D. Purohit, UD, RTU, Kota B.Tech. III Semester (ME/P&I)
Interpolation with unevenly spaced points
Interchanging x and y in Eq. (1), we obtain the inverse interpolation as
n
X
Pn (y) = `i (y) xi , xi = x(yi ) (3)
i=0
where
(y − y0 )(y − y1 ) · · · (y − yi−1 )(y − yi+1 ) · · · (y − yn )
`i (y) = .
(yi − y0 )(yi − y1 ) · · · (yi − yi−1 )(yi − yi+1 ) · · · (yi − yn )
Dr. S.D. Purohit, UD, RTU, Kota B.Tech. III Semester (ME/P&I)
Interpolation with unevenly spaced points
Example
Certain corresponding values of x and log10 x are (300, 2.4771),
(304, 2.4829), (305, 2.4843) and (307, 2.4871). Find log10 301.
Solution
Using Lagrange’s interpolation formula, we have
3
X
P3 (x) = `i (x) yi
i=0
(x − x1 )(x − x2 )(x − x3 )
= (y0 )
(x0 − x1 )(x0 − x2 )(x0 − x3 )
(x − x0 )(x − x2 )(x − x3 )
+ (y1 )
(x1 − x0 )(x1 − x2 )(x1 − x3 )
(x − x0 )(x − x1 )(x − x3 )
+ (y2 )
(x2 − x0 )(x2 − x1 )(x2 − x3 )
(x − x0 )(x − x1 )(x − x2 )
+ (y3 )
(x3 − x0 )(x3 − x1 )(x3 − x2 )
Dr. S.D. Purohit, UD, RTU, Kota B.Tech. III Semester (ME/P&I)
Interpolation with unevenly spaced points
Solution
According to given problem, we have
x0 x1 x2 x3
x 300 304 305 307
y 2.4771 2.4829 2.4843 2.4871
y y0 y1 y2 y3
Therefore,
(301 − 304)(301 − 305)(301 − 307)
P3 (301) = log10 301 = (2.4771)
(300 − 304)(300 − 305)(300 − 307)
(301 − 300)(301 − 305)(301 − 307)
+ (2.4829)
(304 − 300)(304 − 305)(304 − 307)
(301 − 300)(301 − 304)(301 − 307)
+ (2.4843)
(305 − 300)(305 − 304)(305 − 307)
(301 − 300)(301 − 304)(301 − 305)
+ (2.4871)
(307 − 300)(307 − 304)(307 − 305)
= 1.2739 + 4.9658 − 4.4717 + 0.7106
= 2.4786.
Dr. S.D. Purohit, UD, RTU, Kota B.Tech. III Semester (ME/P&I)
Interpolation with unevenly spaced points
Example
Interpolate by means of Lagrange’s interpoation formula and find the value
of f (5), from the following data
f (1) = 2, f (2) = 4, f (3) = 8, f (4) = 16, f (7) = 128.
Solution: 32.9333.
Example
The function y = f (x) is given at the points (7, 3), (8, 1), (9, 1) and (10, 9).
Find the value of y for x = 9.5 using Lagrange’s interpolation formula.
Solution: 3.625.
Example
If y(1) = −3, y(3) = 9, y(4) = 30 and y(6) = 132, find the four point
Lagrange’s interpolation polynomial that takes the same values as the
function y at the given points.
Solution: x3 − 3x2 + 5x − 6.
Dr. S.D. Purohit, UD, RTU, Kota B.Tech. III Semester (ME/P&I)
Interpolation with unevenly spaced points
Example
If y1 = 4, y3 = 12, y4 = 19 and yx = 7, find x.
Solution
According to given problem, we have
x0 x1 x2
x 1 3 4
y 4 12 19
y y0 y1 y2
And y = 7. Then, using inverse inperpolation formula, we obtain
2
X
x= `i (y) xi = `0 (y) x0 + `1 (y) x1 + `2 (y) x2
i=0
(7 − 12)(7 − 19) (7 − 4)(7 − 19) (7 − 4)(7 − 12)
x= (1) + (3) + (4)
(4 − 12)(4 − 19) (12 − 4)(12 − 19) (19 − 4)(19 − 12)
1 27 4 26
= + − = = 1.86
2 14 7 14
Dr. S.D. Purohit, UD, RTU, Kota B.Tech. III Semester (ME/P&I)
Interpolation with unevenly spaced points
Divided differences and their properties:
The Lagrange’s interpolation formula has the disadvantage that if another
interpolation point were added, then the interpolation coefficient `i (x) will
have to be recomputed. We therefore seek an interpolation polynomial
which has the property that a polynomial of higher order may be derived
from it by simply adding new terms. Newton’s general interpolation
formula is one such formula and it employs what are called divided
differences. It is our principal purpose in this section to define such
differences and discuss their properties.
Dr. S.D. Purohit, UD, RTU, Kota B.Tech. III Semester (ME/P&I)
Interpolation with unevenly spaced points
Let (x0 , y0 ), (x1 , y1 ), · · · , (xn , yn ) be the given (n + 1) data points. Then
the divided differences of order 1, 2, · · · , n are defined by the relations:
y1 − y0
[x0 , x1 ] = , (first divided difference);
x1 − x0
[x1 , x2 ] − [x0 , x1 ]
[x0 , x1 , x2 ] = , (second divided difference);
x2 − x0
..
.
[x1 , x2 , · · · , xn ] − [x0 , x1 , · · · , xn−1 ]
[x0 , x1 , · · · , xn ] = , (nth divided difference).
xn − x0
Note: The divided differences are symmetrical in their arguments.
Dr. S.D. Purohit, UD, RTU, Kota B.Tech. III Semester (ME/P&I)
Interpolation with unevenly spaced points
Even if the arguments are equal, the divided differences may still have a
meaning. We then set x1 = x0 + h so that
y(x0 + h) − y(x0 )
[x0 , x1 ] = lim [x0 , x0 + h] = lim
h→0 h→0 h
0
= y (x0 ), if y(x) is differenctiable.
Similarly,
y r (x0 )
[x0 , x0 , · · · , x0 ] = .
| {z } r!
(r+1) argumetnts
Dr. S.D. Purohit, UD, RTU, Kota B.Tech. III Semester (ME/P&I)
Interpolation with unevenly spaced points
Now let the arguments be equally spaced so that xn = x0 + nh, n = 1, 2, ..
Then we obtain
y1 − y0 1
[x0 , x1 ] = = ∆y0 ,
x1 − x0 h
[x1 , x2 ] − [x0 , x1 ] 1 ∆y1 ∆y0 1
[x0 , x1 , x2 ] = = − = 2 ∆2 y0 ,
x2 − x0 2h h h h 2!
and in general,
1
[x0 , x1 , · · · , xn ] = ∆n y0 . (4)
hn n!
Note: If the tabulated function is a polynomial of nth degree, then ∆n y0
would be a constant and hence the nth divided difference would also be a
constant.
Dr. S.D. Purohit, UD, RTU, Kota B.Tech. III Semester (ME/P&I)
Interpolation with unevenly spaced points
Newton’s general interpolation formula:
By definition, we have
y − y0
[x, x0 ] = ,
x − x0
so that
y = y0 + (x − x0 )[x, x0 ].
Again
[x, x0 ] − [x0 , x1 ]
[x, x0 , x1 ] =
x − x1
which gives
[x, x0 ] = [x0 , x1 ] + (x − x1 )[x, x0 , x1 ].
Substituting this value of [x, x0 ] in above equation, we obtain
y = y0 + (x − x0 )[x0 , x1 ] + (x − x0 )(x − x1 )[x, x0 , x1 ]
Dr. S.D. Purohit, UD, RTU, Kota B.Tech. III Semester (ME/P&I)
Interpolation with unevenly spaced points
Proceeding in this way, we obtain
y = y0 + (x − x0 )[x0 , x1 ] + (x − x0 )(x − x1 )[x0 , x1 , x2 ]
+ (x − x0 )(x − x1 )(x − x2 )[x0 , x1 , x2 , x3 ] + · · ·
+ (x − x0 )(x − x1 ) · · · (x − xn )[x, x0 , x1 , · · · , xn ]
This formula is called Newton’s general interpolation formula with
divided differences.
Dr. S.D. Purohit, UD, RTU, Kota B.Tech. III Semester (ME/P&I)
Interpolation with unevenly spaced points
Example
Construct a divided difference table for the following data:
x 1 2 4 7
f (x) 22 30 82 106
Solution
The divided difference table is
x f (x) 1st DD 2nd DD 3rd DD
1 22
30−22
2−1
=8
26−8
2 30 4−1
=6
82−30 −3.6−6
4−2
= 26 7−1
= −1.6
8−26
4 82 7−2
= −3.6
106−82
7−4
=8
7 106
Dr. S.D. Purohit, UD, RTU, Kota B.Tech. III Semester (ME/P&I)
Interpolation with unevenly spaced points
Example
Using the following table find f (x) as a polynomial in x:
x -1 0 3 6 7
f (x) 3 -6 39 822 1611
Solution
The divided difference table is
x f (x) 1st DD 2nd DD 3rd DD 4th DD
-1 3
-9
0 -6 6
15 5
3 39 41 1
261 13
6 822 132
789
7 1611
Using Newton’s general interpolation formula, we have
y = y0 + (x − x0 )[x0 , x1 ] + (x − x0 )(x − x1 )[x0 , x1 , x2 ]
+ (x − x0 )(x − x1 )(x − x2 )[x0 , x1 , x2 , x3 ]+
+ (x − x0 )(x − x1 )(x − x2 )(x − x3 )[x, x0 , x1 , x2 , x3 , x4 ]
Dr. S.D. Purohit, UD, RTU, Kota B.Tech. III Semester (ME/P&I)
Interpolation with unevenly spaced points
Solution
Therefore,
y = f (x) = 3 + (x + 1)(−9) + (x + 1)(x)(6) + (x + 1)(x)(x − 3)(5)
+ (x + 1)(x)(x − 3)(x − 6)(1)
= x − 3x3 + 5x2 − 6.
4
Dr. S.D. Purohit, UD, RTU, Kota B.Tech. III Semester (ME/P&I)
