CPNA Lecture 16 - Interpolation

Mridul Sankar Barik

Jadavpur University

January 17, 2022

Introduction I

I Suppose a function f (x) is not defined explicitly, but its value

at some finite number of points x0 , x1 , x2 , . . ., xn is given
x x0 x1 x2 ... xn
f (x) f (x0 ) f (x1 ) f (x2 ) ... f (xn )

I Interpolation: to find f (x) at x in the interval [x0 , xn ], if x is

not among the tabulated points
I Extrapolation: to find f (x) at x outside the interval [x0 , xn ]
with the assumption that behavior of f (x) outside the range
[x0 , xn ] is identical to that inside the range
Polynomial Interpolation I

I To find a polynomial φ(x), such that f (x) agree with φ(x) at

the given set of points
I If we have n + 1 data points then we can fit a nth degree
polynomial

φ(x) = a0 + a1 x + a2 x 2 + . . . + an x n
Linear Interpolation I

I Simplest form used when two data points are available

Linear Interpolation II

I Connect two data points with a straight line

f1 (x) − f (x0 ) f (x1 ) − f (x0 )

=
x − x0 x1 − x0
or,
f (x1 ) − f (x0 )
f1 (x) = f (x0 ) + (x − x0 ) (1)
x1 − x0
I As the interval decreases, a continuous function will be better
approximated by a straight line
I Exercise: Estimate the natural logarithm of 2 using linear
interpolation. First, perform the computation by interpolating
between ln 1 = 0 and ln 6 = 1.791759. Then, repeat the
procedure, but use a smaller interval from ln 1 to ln 4
(1.386294). Note that the true value of ln 2 is 0.6931472.
Linear Interpolation III

Solution: Using equation 1 in the interval x0 = 1, x1 = 6, we

get

f (6) − f (1) 1.791759 − 0

f1 (2) = f (1)+ (2−1) = 0+ = 0.3583519
6−1 5

Percentage error εp = 0.6931472−0.3583519

0.6931472 × 100% = 48.3%
Using the smaller interval x0 = 1, x1 = 4, we get

f (4) − f (1) 1.386294 − 0

f1 (2) = f (1)+ (2−1) = 0+ = 0.4620981
4−1 3
0.6931472−0.4620981
Percentage error now, εp = 0.6931472 × 100% =
33.3%
Linear Interpolation IV
Quadratic Interpolation I

I Use a second order polynomial when three data points are

available

f2 (x) = b0 + b1 (x − x0 ) + b2 (x − x0 )(x − x1 ) (2)

I Where,

b0 = f (x0 )
f (x1 ) − f (x0 )
b1 = (3)
x1 − x0
f (x2 ) − f (x1 ) f (x1 ) − f (x0 )
−
x2 − x1 x1 − x0
b2 =
x2 − x0
I Exercise: Estimate the value of ln 2 Using a second order
polynomial and the given three points
Quadratic Interpolation II

x x0 = 1 x1 = 4 x2 = 6
f (x) = ln x f (x0 ) = 0 f (x1 ) = 1.386294 f (x2 ) = 1.791759
I Solution: Using equation 3, we get
I b0 = f (x0 ) = f (1) = 0
b1 = f (xx11)−f
−x0
(x0 )
= f (4)−f
4−1
(1)
= 1.386294−0
3 = 0.4620981
f (x2 )−f (x1 ) f (x )−f (x ) f (6)−f (4) f (4)−f (1)
x2 −x1 − x1 −x 0 6−4 − 4−1
b2 = x2 −x0
1 0
= 6−1 =
1.791759−1.386294
− 1.386294−0
2
5 = −0.0518731
3

I Substituting these values into equation 2 yields the quadratic

formula
f2 (x) = 0 + 0.4620981(x − 1) − 0.0518731(x − 1)(x − 4)
I We evaluate f2 (x) at x = 2 for f2 (2) = 0.5658444
I Percentage error εp = 0.6931472−0.5658444
0.6931472 × 100% = 18.4%
Quadratic Interpolation III

I The curvature introduced by the quadratic formula improves

the interpolation compared with the result obtained using
straight lines
General Form of Newton’s Interpolating Polynomial I

I To fit an nth order polynomial to n + 1 data points

fn (x) = b0 + b1 (x − x0 ) + b2 (x − x0 )(x − x1 ) + . . .
+ bn (x − x0 )(x − x1 ) . . . (x − xn−1 )

I The coefficients are evaluated as

I b0 = f (x0 )
I b1 = f (xx11)−f
−x0
(x0 )
= ∆d f0
∆d f1 −∆d f0
I b2 = x2 −x0 = ∆2d f0
I ...
∆n−1 f1 −∆n−1 f0
I bn = d
xn −x0
d
= ∆nd f0
General Form of Newton’s Interpolating Polynomial II

I In general, if we have (n + 1) data points ranging from

(x0 , f (x0 )) to (xn , f (xn ))
I 1st finite divided difference ∆d fi = (f (x(xi+1 )−f (xi ))
i+1 −xi )
, for i = 0 to
(n − 1)
d fi+1 −∆d fi )
I 2nd finite divided difference ∆2d fi = (∆(x 2+i −xi )
, for i = 0 to
(n − 2)
(∆2d fi+1 −∆2d fi )
I 3rd finite divided difference ∆3d fi = (x3+i −xi ) , for i = 0 to
(n − 3)
(∆3d fi+1 −∆3d fi )
I 4th finite divided difference ∆4d fi = (x4+i −xi ) , for i = 0 to
(n − 4)
I ...
(∆n−1 fi+1 −∆n−1 fi )
I nth finite divided difference ∆nd fi = d d
(xn+i −xi ) , for i = 0
to (n − n)
General Form of Newton’s Interpolating Polynomial III

I Divided difference table (for five data points)

x f (x) ∆d f ∆2d f ∆3d f ∆4d f
x0 f (x0 )
∆d f0
x1 f (x1 ) ∆2d f0
∆d f1 ∆3d f0
x2 f (x2 ) ∆2d f1 ∆4d f0
∆d f2 ∆3d f1
x3 f (x3 ) ∆2d f2
∆d f3
x4 f (x4 )
General Form of Newton’s Interpolating Polynomial IV
I Newton’s divided difference interpolating polynomial

f (x) = f (x0 ) + ∆d f0 (x − x0 ) + ∆2d f0 (x − x0 )(x − x1 )

+ . . . + ∆nd f0 (x − x0 )(x − x1 ) . . . (x − xn−1 )

where,
(∆dn−1 f1 − ∆dn−1 f0 )
∆nd f0 =
(xn − x0 )
I Exercise: Estimate the value of ln 2 Using a third order
polynomial and the given four points
x x0 = 1 x1 = 4 x2 = 5 x3 = 6
f (x) = ln x 0 1.386294 1.609438 1.791759
I Solution: Divided difference table for the given four data
points
General Form of Newton’s Interpolating Polynomial V
x f (x) ∆d f ∆2d f ∆3d f
x0 = 1 0
0.462098
x1 = 4 1.386294 −0.0597385
0.223144 0.0078654
x2 = 5 1.609438 −0.0204115
0.182321
x3 = 6 1.791759
I General form of Newton’s divided difference third order
formula is
f (x) = f (x0 )+∆d f0 (x −x0 )+∆2d f0 (x −x0 )(x −x1 )+∆3d f0 (x −x0 )(x −x1 )(x −x2 )

I Substituting values of respective divided differences, we get

f (x) = 0.462098(x −1)−0.0597385(x −1)(x −4)+0.0078654(x −1)(x −4)(x −5)
General Form of Newton’s Interpolating Polynomial VI

I Putting x = 2, we get
f (2) = 0.462098(2−1)−0.0597385(2−1)(2−4)+0.0078654(2−1)(2−4)(2−5) =
0.462098 + 0.119477 + 0.0471924 = 0.6287674
0.6931472−0.6287674
I Percentage error εp = 0.6931472 × 100% = 9.29%
General Form of Newton’s Interpolating Polynomial VII
Algorithm 1 Algorithm for Newton’s Divided Difference Interpolat-
ing Polynomial
Input: Array x and y contains n + 1 numbers of x and f (x) values respectively, xi is
the point where the value of the function f has to be interpolated
Output: The value of f (xi)
1: /*fdd is an (n + 1) × (n + 1) array which stores the finite divided differences*/
2: for i = 0 to n in steps of 1 do
fdd[i][0] = y [i]
3: end for
4: /*computation of finite divided differences*/
5: for j = 1 to n in steps of 1 do
6: for i = 0 to n − j in steps of 1 do
fdd[i][j] = (fdd[i + 1][j − 1] − fdd[i][j − 1])/(x[i + j] − x[i])
7: end for
8: end for
9: /*computation of the value of the function at the point xi */
10: xterm = 1
11: yint[0] = fdd[0][0]
12: for order = 1 to n in steps of 1 do
13: xterm = xterm ∗ (xi − x[order − 1])
14: yint[order ] = yint[order − 1] + fdd[0][order ] ∗ xterm
15: end for
Lagrange Interpolation I
I Evaluation of polynomial coefficients become simpler when
the following form is considered

f (x) = c0 (x − x1 )(x − x2 ) . . . (x − xn )
+ c1 (x − x0 )(x − x2 ) . . . (x − xn )
...
+ cn (x − x0 )(x − x1 ) . . . (x − xn−1 )

where,
f (x0 )
c0 =
(x0 − x1 )(x0 − x2 ) . . . (x0 − xn )
f (x1 )
c1 =
(x1 − x0 )(x1 − x2 ) . . . (x1 − xn )
..
.
f (xn )
cn =
(xn − x0 )(xn − x1 ) . . . (xn − xn−1 )
Lagrange Interpolation II

I This is known as Lagrange Polynomial, general form of which

is as follows
n n
X Y (x − xj )
f (x) = f (xi )
(xi − xj )
i=0 j=0,j6=i

I It is easier to program in a computer

I Difficult for hand calculation
Lagrange Interpolation III

Algorithm 2 Algorithm for Lagrange Polynomial Interpolation

Input: Array x and y contains n + 1 numbers of x and f (x) values respectively, xi is
the point where the value of the function f has to be interpolated
Output: The value of f (xi)
1: sum = 0
2: for i = 0 to n in steps of 1 do
3: prod = 1
4: for j = 0 to n in steps of 1 do
5: if j 6= i then
6: prod = prod ∗ (xi − x[j])/(x[i] − x[j])
7: end if
8: end for
9: sum = sum + f [i] ∗ prod
10: end for
11: Write xi, sum
Lagrange Interpolation IV
I Exercise: Estimate the value of ln 2 Using first and second
order Lagrange polynomial and the given three points

x x0 = 1 x1 = 4 x2 = 6
f (x) = ln x f (x0 ) = 0 f (x1 ) = 1.386294 f (x2 ) = 1.791759
I Solution:
I The first order Lagrange polynomial
x − x1 x − x0
f1 (x) = f (x0 ) + f (x1 )
x0 − x1 x1 − x0
x −4 x −1
=0× + 1.386294 ×
1−4 4−1

2−1
f1 (2) = 1.386294 × = 0.462098
4−1
Lagrange Interpolation V

I The second order Lagrange polynomial

(x − x1 )(x − x2 ) (x − x0 )(x − x2 )
f2 (x) = f (x0 ) + f (x1 )
(x0 − x1 )(x0 − x2 ) (x1 − x0 )(x1 − x2 )
(x − x0 )(x − x1 )
+ f (x2 )
(x2 − x0 )(x2 − x1 )
(x − 1)(x − 6) (x − 1)(x − 4)
= 1.386294 × + 1.791759 ×
(4 − 1)(4 − 6) (6 − 1)(6 − 4)

(2 − 1)(2 − 6) (2 − 1)(2 − 4)
f2 (2) = 1.386294 × + 1.791759 ×
(4 − 1)(4 − 6) (6 − 1)(6 − 4)
2 1
= 1.386294 × − 1.791759 × = 0.924196 − 0.3583518 = 0.5658442
3 5
Differences of a Polynomial I
I Let f (x) be a polynomial of nth degree
f (x) = a0 + a1 x + a2 x 2 + . . . + an x n
I Then we obtain
f (x+h)−f (x) = a1 [x+h−x]+a2 [(x+h)2 −x 2 ]+. . .+an [(x+h)n −x n ]
or
f = f (x + h) − f (x) = a1 h + a20 x + . . . + an−1
0
x n−1
I This is a polynomial of order (n − 1)
I By repeated application we get
I ∆2 f is a polynomial of degree (n − 2)
I ∆3 f is a polynomial of degree (n − 3)
......
I ∆n f is a constant
I Thus by inspecting the difference table we can decide the
order of the polynomial to be chosen
Newton’s Forward Difference Formula I

I Given a table of values (xi , yi ), i = 0, 1, 2, . . . , n of any

function y = f (x), and the value of x being equally spaced,
i.e., xi = xo + ih, i = 0, 1, 2, . . . , n
I We are required to find values of f (x) [or derivative of f (x)]
in the range x0 ≤ x ≤ xn
I Forward Differences
I ∆: forward difference operator
I First forward difference: differences in y values
I ∆f0 = f (x1 ) − f (x0 ), ∆f1 = f (x2 ) − f (x1 ), . . . , ∆fn−1 =
f (xn ) − f (xn−1 )
I Second forward difference: differences in first forward
differences
I ∆2 f (x0 ) = ∆f (x1 ) − ∆f (x0 ), ∆2 f (x1 ) =
∆f (x2 ) − ∆f (x1 ), . . . , ∆2 f (xn−2 ) = ∆f (xn−1 ) − ∆f (xn−2 )
I Similarly we can define third forward difference, fourth
forward difference etc.
Newton’s Forward Difference Formula II
x f (x) ∆ ∆2 ∆3 ∆4 ∆5
x0 f (x0 )
∆f0
x1 f (x1 ) ∆2 f0
∆f1 ∆3 f0
2
x2 f (x2 ) ∆ f1 ∆4 f0
3
∆f2 ∆ f1 ∆5 f0
2 4
x3 f (x3 ) ∆ f2 ∆ f1
∆f3 ∆3 f2
x4 f (x4 ) ∆2 f3
∆f4
x5 f (x5 )
Table 1: Forward Difference Table

I For equal spaced intervals i.e. xi = x0 + ih, i = 0, 1, 2, . . . , n,

the divided differences become
f (x1 )−f (x0 ) ∆f0
I ∆d f0 = (x1 −x0 ) = h
∆f1 ∆f0
∆d f1 −∆d f0 h − h ∆2 f0
I ∆2d f0 = (x2 −x0 ) = 2h = 2!h2
Newton’s Forward Difference Formula III
∆2 f1 ∆2 f
∆2d f1 −∆2d f0 − 20 ∆3 f0
I ∆3d f0 = (x3 −x0 ) = 2!h2
3h
2!h
= 3!h3
......
∆n f0
I ∆nd f0 = n!hn
I Newton’s divided difference interpolating polynomial thus
becomes
∆f0 ∆2 f0
f (x) = f (x0 ) + (x − x0 ) + (x − x0 )(x − x1 )
h 2!h2
n
∆ f0
+ ... + (x − x0 )(x − x1 ) . . . (x − xn−1 )
n!hn
where,
(∆dn−1 f1 − ∆dn−1 f0 )
∆nd f0 =
nh
I The above form is known as Newton’s forward difference
interpolating polynomial
I This polynomial can be expressed more concisely by
considering x = x0 + uh, so
Newton’s Forward Difference Formula IV
I x − x0 = uh
I x − x1 = (x0 + uh) − (x0 + h) = h(u − 1)
I x − x2 = x − (x1 + h) = h(u − 1) − h = h(u − 2)
......
I x − xn−1 = h(u − n − 1)
I Substituting above into the polynomial we get

∆ 2 f0
f (x0 + uh) = f (x0 ) + ∆f0 u + u(u − 1)
2!
∆ n f0
+ ... + u(u − 1)(u − 2) . . . (u − n − 1)
n!
I This is known as Newton Gregory Forward Interpolation
Formula
I In general, Newton’s forward difference formula is used to
compute the approximate value of f (x) when the value of x is
near to x0 of the given table. But, if the value of x is at the
end of the table, then this formula gives more error. In this
case, Newton’s backward formula is used.
Newton’s Forward Difference Formula V

Exercise: If f (x) is known at the following data points, then find

f (0.5) and f (1.5) using Newton’s forward difference formula

x 0 1 2 3 4
f (x) 1 7 23 55 109

Solution: The given data satisfies f (x) = x 3 + 2x 2 + 3x + 1. It is

a degree three polynomial. Hence, third forward differences are
constant. Although, from the given five data points, we can fit a
degree four polynomial. It is sufficient to approximate the function
using a degree three polynomial.
Newton’s Forward Difference Formula VI

x f (x) ∆f ∆2 f ∆3 f ∆4 f
0 1
6
1 7 10
16 6
2 23 16 0
32 6
3 55 22
54
4 109
Table 2: Forward Difference Table
Newton’s Forward Difference Formula VII

Newton’s forward difference formula for a degree three polynomial

is

∆2 f0 ∆ 3 f0
f (x0 + uh) = f (x0 ) + ∆f0 u + u(u − 1) + u(u − 1)(u − 2)
2! 3!

At, x = 0.5, u = x−x

h =
0 0.5−0
1 = 0.5
0.5×(0.5−1)×10
f (0.5) = 1+0.5×6+ 2 + 0.5×(0.5−1)×(0.5−2)×6
6 = 3.125

At, x = 1.5, u = x−x

h =
0 1.5−0
1 = 1.5
1.5×(1.5−1)×10 1.5×(1.5−1)×(1.5−2)×6
f (1.5) = 1+1.5×6+ 2 + 6 = 13.375
Newton’s Backward Difference Formula I

I Backward Differences
I ∇: backward difference operator
I First backward difference: differences in f (x) values
I ∇fn = f (xn ) − f (xn−1 ), ∇fn−1 = f (xn−1 ) − f (xn−2 ), . . . , ∇f2 =
f (x2 ) − f (x1 ), ∇f1 = f (x1 ) − f (x0 )
I Second backward difference: differences in first backward
differences
I ∇2 fn = ∇fn − ∇fn−1 , ∇2 fn−1 = ∇fn−1 − ∇fn−2 , . . . , ∇2 f3 =
∇f3 − ∇f2 , ∇2 f2 = ∇f2 − ∇f1
I Similarly we can define third backward difference, fourth
backward difference etc.
Newton’s Backward Difference Formula II

x f (x) ∇ ∇2 ∇3 ∇4 ∇5
x0 f (x0 )
∇f1
x1 f (x1 ) ∇2 f2
∇f2 ∇ f3
x2 f (x2 ) ∇2 f3 ∇4 f4
∇f3 ∇3 f4 ∇5 f5
x3 f (x3 ) ∇2 f4 ∇4 f5
∇f4 ∇3 f5
x4 f (x4 ) ∇2 f5
∇f5
x5 f (x5 )
Table 3: Backward Difference Table
Newton’s Backward Difference Formula III

I The generic nth order polynomial to fit n + 1 data points can

also be chosen as

fn (x) = b0 + b1 (x − xn ) + b2 (x − xn )(x − xn−1 ) + . . .

+ bn (x − xn )(x − xn−1 ) . . . (x − x1 )

I f (x) and fn (x) must agree at given n + 1 points

I The coefficients are evaluated as
I b0 = f (xn )
I b1 = f (xxnn)−f (xn−1 )
−xn−1 = ∇fn
h
∇fn ∇fn−1
h − ∇2 fn
I b2 = h
xn −xn−2 = 2!h2
I ...
∇n−1 fn ∇n−1 fn−1
−
(n−1)!hn−1 (n−1)!hn−1 ∇n fn
I bn = xn −x0 = n!hn
Newton’s Backward Difference Formula IV
I Thus, the polynomial can be written as

∇fn ∇ 2 fn
fn (x) = f (xn ) + (x − xn ) + (x − xn )(x − xn−1 ) + . . .
h 2!h2
n
∇ fn
+ (x − xn )(x − xn−1 ) . . . (x − x1 )
n!hn
I This polynomial can be expressed more concisely by
considering x = xn + uh, so
I x − xn = uh
I x − xn−1 = (xn + uh) − (xn − h) = h(u + 1)
I x − xn−2 = x − (xn−1 − h) = h(u + 1) + h = h(u + 2)
......
I x − x1 = h(u + n − 1)
I Substituting above into the polynomial we get

u(u + 1) 2
fn (x) = f (xn ) + u∇fn + ∇ fn + . . .
2!
∇ n fn
+ u(u + 1) . . . (u + n − 1)
n!
Newton’s Backward Difference Formula V

I Backward difference formula is used to interpolate values of

the function f nearer to the end of the tabular values
I Exercise: Population (in millions) of a city is given in the
following table
x 1971 1981 1991 2001 2011
f (x) 46 66 81 93 101
Determine the population in the year 2005.
I Solution:
Newton’s Backward Difference Formula VI

x f (x) ∇f ∇2 f ∇3 f ∇4 f
1971 46
20
1981 66 -5
15 2
1991 81 -3 -3
12 -1
2001 93 -4
8
2011 101
Table 4: Backward Difference Table
Newton’s Backward Difference Formula VII
Newton’s backward difference formula for a degree four
polynomial is

u(u + 1) 2 u(u + 1)(u + 2) 3

f (x) = f (xn ) + u∇fn + ∇ fn + ∇ fn
2! 3!
u(u + 1)(u + 2)(u + 3) 4
+ ∇ fn
4!
x−xn 2005−2011
At, x = 2005, u = h = 10 = −0.6

−0.6(−0.6 + 1)
f (2005) = 101 + −0.6 × 8 + × −4
2
−0.6(−0.6 + 1)(−0.6 + 2)
+ × −1
6
−0.6(−0.6 + 1)(−0.6 + 2)(−0.6 + 3)
+ × −3
24
= 101 − 4.8 + 0.48 + 0.056 + 0.1008 = 96.8368