Interpolation

Contents:

o Introduction
o Errors in Polynomial Interpolation
o Interpolation with Equally Spaced Values
o Finite Difference Method
o Forward Difference Method
o Backward Difference Method
o Central Difference Method
o Difference of Polynomial
o Interpolation with Unequally Spaced Values
o Linear Interpolation Formula
o Lagrange Interpolation Formula
o Newton Interpolation Polynomial
o Inverse Interpolation
o Divided Differences
o Assignment 3
37
Page

Prepared By
Er. Shree Krishna Khadka
INTERPOLATION

If a function, say f(x) is constructed, such that it passes through all the set of data
points and then evaluating f(x) for the specified value of x is known as
interpolation. This method of constructing a function gives the estimation of values
at non tabular print. The functions are known as interpolation polynomials.

Most common form of nth order polynomials are:

1. P x = a0 + a1 x + a2 x 2 + ⋯ + an−1 x n−1 + an x n … (i), this is known as nth

order polynomial in Power Form.

2. P x = a0 + a1 x − c + a2 (x − c)2 + ⋯ + an−1 (x − c)n−1 + an (x − c)n …(ii),

this is known as nth order polynomial in Shifted Power Form, and

3. P x = a0 + a1 x − c1 + a2 x − c1 x − c2 + ⋯ + ( x − c1 x − c2 … x − cn )
...(iii), this is known as nth order polynomial in Newton Form, which reduces
to shifted power form, when c1 = c2 = c3 = … = cn and reduces to simple
power form, when ci = 0 for all i.

ERRORS IN POLYNOMIAL INTERPOLATION

Let the function y(x), defined by the (n+1) points (xi, yi), i = 0, 1, 2 … n, be the
continuous and differentiable (n+1) times and let y(x) be approximated by a
polynomial ∅(x) of degree not exceeding ‘n’ such that:

∅n xi = yi , i = 0, 1 … n

πn +1 x
Then error is given by: e = y x − ∅n x = y n+1 γ , x0 < γ < xn .
n+1 !

y n +1 γ
Where, πn+1 x = x − x0 x − x1 … . (x − xn ) and if L = then:
n+1 !

e = y x − ∅n x = L. πn+1 x … (i)

Since, y(x) is generally unknown and hence, we do not have any information
concerning y(n+1)(x). It is almost useless in practical computation. But, on the other
38

hand, it is extremely useful in theoretical work in different branches of numerical

Page

analysis. It is useful in determining errors in Newton Interpolating Formula.

Prepared By
Er. Shree Krishna Khadka
FINITE DIFFERENCES: INTERPOLATION WITH EQUALLY SPACED VALUES
Assume that, we have a table of values: (xi, yi), (i = 0, 1, 2, … n) of any function y
=f(x), the values of x being equally spaced, i.e. xi = x0 + ih, (i = 0, 1, 2, … n). The
method of finding the solution of f(x) for some ‘x’ in the range x0 ≤ x ≤ xn is based
on the concept of such finite differences.

Forward Difference:
If y0, y1, …. Yn denote a set of values of y at x0, x1, … xn respectively, then (y1 –
y0), (y2 – y1), …. (yn – yn-1) are called difference of y; i.e. ∆y0 = y1 − y0 ,
∆y1 = y2 − y1 , ….. ∆yn−1 = yn − yn−1 , where ∆ is the forward difference
operator. Usually, the functions are tabulated at equal intervals, i.e. x1 – x0 =
x2 – x1 = x3 – x2 …. xn – xn-1 = na. Here, with tabulation at equal intervals a
difference table for ‘n’ points may be expressed as shown below:
x f(x) ∆𝐟 ∆𝟐 𝐟 ∆𝟑 𝐟 ∆𝟒 𝐟 ….

x0 𝐟𝟎
∆𝐟𝟎
x0 + h f1 ∆𝟐 𝐟𝟎
∆f1 ∆𝟑 𝐟𝟎
2
x0 + 2h f2 ∆ f1 ∆𝟒 𝐟𝟎 ….
3
∆f2 ∆ f1
x0 + 3h f3 ∆2 f2 …. ….
∆f3 …. …. ….
x0 + 4h f4 …. …. …. ….
…. …. …. …. …. ….

Here ‘h’ is the uniform difference in the value of ‘x’.

∆f0 = f1 − f0 , ∆f1 = f2 − f1 , ….
In general: (∆fi = fi+1 − fi ) , which is called first forward difference.
Similarly:
∆2 f0 = ∆ ∆f0 = ∆f1 − ∆f0 = f2 − f1 − f1 − f0 = f2 − 2f1 + f0
In general: (∆2 fi = fi+2 − 2fi+1 + fi ), which is called second forward
difference and so on.
For the polynomial that passes through a group of equidistant point i.e.
Newton Gregory Forward Polynomial, we write in terms of the index ‘s’, such
that s = (x-x0)/h.
∆f 0 ∆2 f 0 ∆3 f 0
∴ Pn x = f0 + s +s s−1 +s s−1 s−2 + …
1! 2! 3!

This equation for polynomial is called Newton Gregory Forward

39

Interpolation Formula. It is applied when the required point is close to the

Page

start of the table.

Prepared By
Er. Shree Krishna Khadka
Example:
For the given table, find the value of f(0.16).
x 0.1 0.2 0.3 0.4
f(x) 1.005 1.020 1.045 1.081

Solution:
x0 = 0.1, x1 = 0.2 … i.e. h = x1 – x0 = 0.2 – 0.1 = 0.1
We have given, x = 0.16. So: s = (x – x0)/h = (0.16 – 0.1)/0.1 = 0.6

Now, generating the Forward Difference Table:

x f(x) ∆𝐟 ∆𝟐 𝐟 ∆𝟑 𝐟

0.1 𝟏. 𝟎𝟎𝟓
𝟎. 𝟎𝟏𝟓
0.2 1.020 𝟎. 𝟎𝟏
0.025 𝟎. 𝟎𝟎𝟏
0.3 1.045 0.011
0.036
0.4 1.081

Now:
∆f 0 ∆2 f 0 ∆3 f 0
P3 x = f0 + s +s s−1 +s s−1 s−2
1! 2! 3!
0.01 0.001
P3 x = 1.005 + 0.6 × 0.015 + 0.6 0.6 − 1 + 0.6 0.6 − 1 0.6 − 2
2! 3!
P3 x = 1.0128

Backward Difference:
If the required point is close to the end of the table, we can use another
formula known as Newton Gregory Backward Difference Formula. Here, the
reference point is: ‘xn’ instead of x0. Therefore, s = (x – xn)/h.
So, the Newton Gregory Formula is given by:

∇f n ∇2 f n ∇3 f n
∴ Pn x = fn + s +s s+1 +s s+1 s+2 + …
1! 2! 3!

The table for the backward difference will be identical to the forward
difference table. However, the reference point will be below the point for
which the estimate is required. So, the value of ‘s’ will be negative for
40

backward interpolation. The backward difference table is shown below.

Page

Prepared By
Er. Shree Krishna Khadka
 x f(x) ∇𝐟 ∇𝟐 𝐟 ∇𝟑 𝐟 ∇𝟒 𝐟 ….

x0 f0
∇f1
x0 + h f1 ∇2 f2
∇f2 ∇3 f3
x0 + 2h f2 ∇2 f3 ∇4 f4 ….
3
∇f3 ∇ f4
2
x0 + 3h f3 ∇ f4 …. ….
…. ….
∇f4 ….
…. …. ….
x0 + 4h f4 …. …. ….
…. ….
…. ….

Where, ∇ is a backward difference operator, and

Here ‘h’ is the uniform difference in the value of ‘x’.

∇f1 = f1 − f0 , ∇f2 = f2 − f1 , ….
In general: (∆fi = fi − fi−1 ) , which is called first backward difference.
Similarly:
∇2 f1 = ∇ ∇f1 = ∇f1 − ∇f0 = f2 − f1 − f1 − f0 = f2 − 2f1 + f0
In general: (∇2 fi = fi+1 − 2fi + fi−1 ), which is called second backward
difference and so on.

Example:
Estimate the value of sin(45o) using backward difference method with
the following set of data.
x 10 20 30 40 50
f(x)=sin(x) 0.1736 0.342 0.5 0.6428 0.768

Solution:
x0 = 10, x1 = 20 … i.e. h = x1 – x0 = 20 – 10 = 10
We have given, x = 45. So: s = (x – xn)/h = (45 – 50)/10 = -0.5

∇f 4 ∇2 f 4 ∇3 f 4
∴ P4 x = f4 + s +s s+1 +s s+1 s+2 + s s + 1 s + 2 (s −
1! 2! 3!
∇4 f 4
4) 4!

Where, the necessary data are fetched from the following Backward
Difference Table.
41
Page

Prepared By
Er. Shree Krishna Khadka
Backward Difference Table:

x f(x) ∇𝐟 ∇𝟐 𝐟 ∇𝟑 𝐟 ∇𝟒 𝐟

10 0.1736
0.1684
20 0.342 −0.0104
0.158 0.0048
30 0.5 −0.0152 0.0024
0.1428 0.0024
40 0.6428 −0.0176
0.1252
50 0.768

0.1252 (−0.0176 )
∴ P4 x = 0.768 − 0.5 × − 0.5 × −0.5 + 1 − 0.5 ×
1! 2!
0.0024 0.0024
−0.5 + 1 −0.5 + 2 − 0.5 × −0.5 + 1 −0.5 + 2 (−0.5 + 3)
3! 4!

∴ P4 x = 0.768 + 0.0022 − 0.00015 − 0.00009375 = 0.70735625

Difference of a polynomial:
As, we have discussed difference table by forward and backward difference
method. Let us analyse, what actually differs in the first, second and …
difference in their degrees.

If y(x) be a polynomial of nth degree:

i.e; y x = a0 x n + a1 x n−1 + a2 x n−2 + ⋯ an−1 x + an ,

Then we obtain:

n
y x + h − y x = a0 x + h − x n + a1 x + h n−1
− x n−1 + ⋯
′ x n −1
= a0 nh x n−1 + a1 + ⋯ + an ′

Where, a1’, a2’ … are new coefficients.

Then:
∆y x = a0 nh x n−1 + a′1 x n−1 + ⋯ + an ′
This shows that the first difference of polynomial of the nth degree is a
42

polynomial of degree (n-1) and so on.

Page

Prepared By
Er. Shree Krishna Khadka
Where;
Coefficient of xn-1 is a0(nh) in first difference.
Coefficient of xn-2 is a0n(n-1)h2 in second difference.
……………….. ….. … …………….. ………………………….
……………….. ….. …. …………….. …………………………..
Coefficient of x0 is a0n!hn in nth difference.

Newton’s Formula for Interpolation

We had used Newton Gregory Formula for two different methods:

a) Newton’s Gregory Formula for Forward Difference, and

∆f 0 ∆2 f 0 ∆3 f 0
Pn x = f0 + s +s s−1 +s s−1 s−2 + …
1! 2! 3!

Where, s = (x-x0)/h; ‘x’ is referred near to the start of the table and ‘h’ is a
interval constant

b) Newton’s Gregory Formula for Backward Difference

∇f n ∇2 f n ∇3 f n
Pn x = fn + s +s s+1 +s s+1 s+2 + …
1! 2! 3!

Where, s = (x-xn)/h; ‘x’ is referred near to the end of the table and ‘h’ is a
interval constant

Central Difference Method

If interpolation is desired near the beginning or end of the table, there is no
alternative to Newton’s Forward and Backward Difference Formula
respectively, simply because higher order differences do not exist at the
beginning or end of the table values.

For interpolation near the middle of the table, Stirling’s Formula gives the
1 1
most accurate result for − 4 ≤ P ≤ 4 and Bessel’s Formula is most efficient
1 1 3
near P = 2, say 4 ≤ P ≤ 4 . But in the case, where a series of calculations have
to made, it would be inconvenient to use both of these formulae and a choice
must be made between them. Everett’s Formula may be gainfully employed
for the aforesaid reason.
43
Page

Prepared By
Er. Shree Krishna Khadka
LINEAR Interpolation
The simplex form of interpolation is to approximate two data points by straight
line. Suppose, we are given two points, [x1, f(x1)] and [x2, f(x2)], these two points
can be connected linearly as shown in the figure below.

f(x)

f(x2)

f(x)

f(x1)

x
x1 x x2

Fig: Representation of Linear

Interpolation Method

Using the concept of similar triangle, we have:

f x −f(x 1 ) f x 2 −f(x 1 )
=
(x−x 1 ) (x 2 −x 1 )

Solving for f(x), we get:

f x 2 −f(x 1 )
f x = f x1 + (x − x1 ) … (i)
(x 2 −x 1 )

f x 2 −f(x 1 )
This equation is known as Linear Interpolation Formula, where,
(x 2 −x 1 )
represents the slope of the line. Comparing equation (i) with Newton form of
polynomial of first order given by: Pn(x) = a0 + a1(x-c1), we get:

f x 2 −f(x 1 )
C1 = x1, a0 = f(x1) and a1 =
(x 2 −x 1 )

Hence, the co-efficient ‘a1’ represent the first derivative of the given function.
44
Page

Prepared By
Er. Shree Krishna Khadka
 Example:
Given the table of data:

x 1 2 3 4 5
f(x) 1 1.4142 1.7321 2 2.2361

Determine the square root of 2.5.

Solution:
Since, the given value 2.5 lie in between the point 2 and 3. So, x1 = 2 and x2 = 3
whereas x=2.5.
Now:

f x 2 −f(x 1 )
f x = f x1 + (x − x1 )
(x 2 −x 1 )
f 3 −f(2)
i.e. f 2.5 = f 2 + (2.5 − 2) (3−2)
1.7321 −1.4142
i.e. f 2.5 = 1.4142 + 0.5 = 1.5732
1

Again, if we choose, x1 = 2 and x2 = 4, then we get: f(2.5) = 1.5607

Since, the true value of square root of 2.5 from calculator is 1.5811 so, error
produced on each cases will be:

Error_1 = |1.5811-1.5732| = 0.0079

Error_2 = |1.5811-1.5607| = 0.0204

Here, Error_2 > Error_1. Hence, it can be concluded that: smaller the interval
between the interpolation data points, the better will be the approximation.

LAGRANGE’S INTERPOLATION POLYNOMIAL FORMULA:

Let (x0, f0), (x1, f1), (x2, f2) … (xn, fn) be the (n+1) points. To derive the formula for
the polynomial of degree ‘n’, let us consider a second order polynomial of the form:
P2 x = b1 x − x0 x − x1 + b2 x − x1 x − x2 + b3 x − x2 x − x0 … (i)
If (x0, f0), (x1, f1) and (x2, f2) are three interpolations then:
P2 x0 = b2 x0 − x1 x0 − x2 = f0
P2 x1 = b3 x1 − x2 x1 − x0 = f1
P2 x2 = b1 x2 − x0 x2 − x1 = f2 ….. (ii)
45
Page

Substituting the values of b1, b2 and b3 from equation (iii) to equation (i), we get:

Prepared By
Er. Shree Krishna Khadka
 f2 f0
P2 x = x − x0 x − x1 + x − x1 x − x2 +
x 2 −x 0 x 2 −x 1 x 0 −x 1 x 0 −x 2
f1
x − x2 x − x0
x 1 −x 2 x 1 −x 0

x−x 1 x−x 2 x−x 2 x−x 0 x−x 0 x−x 1

i.e. P2 x = f0 + f1 + f2 … (iii)
x 0 −x 1 x 0 −x 2 x 1 −x 2 x 1 −x 0 x 2 −x 0 x 2 −x 1

Now, equation (iii) may be represented as:

P2 x = f0 l0 x + f1 l1 x + f2 l2 (x) … (iv)

Where:

x−x 1 x−x 2 x−x 2 x−x 0 x−x 0 x−x 1

l0 x = , l1 x = , l2 x =
x 0 −x 1 x 0 −x 2 x 1 −x 2 x 1 −x 0 x 2 −x 0 x 2 −x 1

Equation (iv) second degree Lagrange’s Polynomial. For Lagrange’s Polynomial

of nth degree, we should have given (n+1) interpolating points. Then the
polynomial will be:

Pn x = f0 l0 x + f1 l1 x + f2 l2 x + … . +fn−1 ln−1 x + fn ln (x) … (iv)

This can be generally expressed as:

n
Pn x = i=0 fi li (x) … (v)

Where;

n x−x j
li x = j=0,j≠i x −x … (vi)
i j

Here, equation (v) is called Lagrange’s Interpolation Polynomial of degree ‘n’

and then equation (vi) is called Lagrange’s Basic Polynomial.
46
Page

Prepared By
Er. Shree Krishna Khadka
Example:

Find the Lagrange’s Interpolation Polynomial to fit the following data. Use
polynomial to estimate the value of e1.5.

i 0 1 2 3
xi 0 1 2 3
ex i − 1 0 1.7183 6.3891 19.0855

Solution:
x−1 x−2 x−3 x 3 −6x 2 +11x−6
l0 x = =
0−1 0−2 0−3 −6

x−2 x−3 x−0 x 3 −5x 2 +6x

l1 x = =
1−2 1−3 1−0 2

x−3 x−0 x−1 x 3 −4x 2 +3x

l2 x = =
2−3 2−0 2−1 −2

x−0 x−1 x−2 x 3 −3x 2 +2x

l3 x = =
3−0 3−1 3−2 6

P3 x = f0 l0 x + f1 l1 x + f2 l2 x + f2 l2 x

x 3 −5x 2 +6x x 3 −4x 2 +3x x 3 −3x 2 +2x

= 0 + 1.7183 +6.3891 + 19.0855
2 −2 6

P3 x = 0.84455x 3 − 1.0604x 2 + 1.9331x ; This is the required polynomial.

P3 1.5 = 0.84455(1.5)3 − 1.0604(1.5)2 + 1.9331 1.5 = 3.3677

Now:

e1.5 = P(1.5) + 1 = 3.3677 + 1 = 4.3677

Concept of Inverse Interpolation

For a given set of values of x and y, the process of finding the value of x for a
certain value of y is called inverse interpolation. When the values of x are at
unequal intervals, the way of performing inverse interpolation is by
interchanging x and y in Lagrange’s method.
Inverse interpolation is meaningful only if the function is single valued in the
47

interval. When the values of x are equally spaced, the method of successive
Page

approximation is used.

Prepared By
Er. Shree Krishna Khadka
Divided Differences
The Lagrange’s Interpolation Formula has the disadvantage that if another
interpolation point were added, then the interpolation coefficients li(x) will
have to be recomputed; we therefore seek an interpolation polynomial which
has the property that a polynomial of higher degree may be derived from it by
simply adding new terms.

Newton general interpolation formula is one such formula, which employs what
are called divided differences. It is our principle purpose to define sch
differences and discuss certain of their properties to obtain the basic formula.

We have Newton’s form of polynomial as:

f x = a0 + a1 x − x0 + a2 x − x0 x − x1 + ⋯ . +an−1 x − x0 x − x1 … (x − xn−1 )

In this polynomial, coefficients can be calculated using divided difference table

as given below.

i xi f(xi) IDD IIDD IIIDD IVDD

0 x0 f(x0)
f(x0, x1)
1 x1 f(x1) f(x0, x1, x2)
f(x1, x2) f(x0, x1, x2,x3)
2 x2 f(x2) f(x1, x2, x3) f(x0, x1, x2,x3,x4)…
f(x2, x3) f(x1, x2, x3, x4)
3 x3 f(x3) f(x2, x3, x4)
f(x3, x4)
4 x4 f(x4)
…

If (x0,y0), (x1,y1)…. (xn,yn) be the given (n+1) points, then the divided difference
of order 1, 2, … n are defined by the relation>

f(x0) = a0

f x 1 −f x 0 f x 2 −f(x 1 )
f(x0, x1) = = a1 f(x1, x2) = …..
x 1 −x 0 x 2 −x 1

f x 2 −f(x 1 ) f x 1 −f(x 0 ) f x 3 −f(x 2 ) f x 2 −f(x 1 )

− −
x 2 −x 1 x 1 −x 0 x 3 −x 2 x 2 −x 1
f(x0, x1, x2) = = a2 f(x0, x1, x2) = ….
x 2 −x 0 x 3 −x 1
48
Page

Prepared By
Er. Shree Krishna Khadka
 Example:
A table of polynomial is given below. Fit the polynomial and find the value
of f(x) at x = 2.5. Use divided difference table.

x -3 -1 0 3 5
f(x) -30 -22 -12 330 3458

Solution:

Let’s build up the divided difference table as follow:

i xi f(xi) IDD IIDD IIIDD IVDD

0 -3 -30
4
1 -1 -22 2
10 4
2 0 -12 26 5
114 44
3 3 330 290
1564
4 5 3458
…

From table, a0 = -30, a1 = 4, a2 = 2, a3 = 4 and a4 = 5

Therefore,
f(x) = -30+4(x+3)+2(x+3)(x+1)+4(x+3)(x+1)(x-0)+5(x+3)(x+1)(x-0)(x-3)
i.e. f(2.5)= -30+4(2.5+3)+2(2.5+3)(2.5+1)+4(2.5+3)(2.5+1)(2.5-0)+5(2.5+3)(2.5+1)(
2.5-0)( 2.5-3)

Example:2 (Home Work)

Given the following set of data points, obtain the table of divided
differences. Use the table to estimate the value of f(1.5)

i 0 1 2 3 4
xi 1 2 3 4 5
f(xi) 0 7 26 63 124

Solution:
a0 = 0, a1 = 7, a2 = 6, a3 = 1 and a4 = 0
49

f(1.5) = 2.375
Page

Prepared By
Er. Shree Krishna Khadka
Assignment: 3
Full Marks: 40
Pass Marks: 20

1. From the following table of values of x and f(x), determine

(a) f(0.23) [5]

(b) f(0.29) [5]

x 0.20 0.22 0.24 0.26 0.28 0.30

f(x) 1.6596 1.6698 1.6804 1.6912 1.7024 1.7139

2. Use linear interpolation method to calculate the square root of 4.5 from
following table.

(a) Take two initial values as 4 and 5 [5]

(b) Take two initial values as 3 and 6
Compare the result of (a) and (b).

x 1 2 3 4 5 6
f(x) 1 1.4142 1.7321 2 2.2361 2.4494

3. Applying Lagrange’s Interpolation Formula, find a cubic polynomial

which approximates the following data. [10]

x -2 -1 2 3
f(x) -12 -8 3 5

Also find the polynomial values at -2.5 and 2.5.

4. Given the table of values

x 50 52 54 56
3
f(x)= 𝑥 3.684 3.732 3.779 3.825

Use Lagrange Interpolation to find x when 𝑥 = 3.756

3 [10]
(Example: Inverse Interpolation)

5. Given the following set of data points. Obtain the table of divided
difference and use that table to estimate the value of f(1.5), f(3.45) & [5]
(4.2)3.

x 1 2 3 4 5
f(x)=x3-1 0 7 26 63 124
50
Page

Prepared By
Er. Shree Krishna Khadka