W EEK

3
Interpolation

Study Organiser

Before you begin this note, please check through your study organiser given below. It shows
the topics that we’ll be covering, the skills you need to acquire (the learning outcomes) and
the resources and activities you are given to help you acquire these skills.

Topics Learning Outcomes Learning Learning

Resources Activities
Interpolation - Find the Lagrange cardinal functions Readings - Section 3.1 Tutorial 3
Lagrange & and use it to construct the Lagrange Examples 3.2 - 3.4 Quiz 3
Newton forms. interpolating polynomial. Glossary 3
Construct the divided difference table Readings - Section 3.2-3.3 Homework 3
and use it to find the Newton Examples 3.5-3.10 Assignment 1
interpolating polynomial. Test 1

Introduction

Interpolation is the process whereby un-tabulated values of a function, tabulated only at cer-
tain values, are estimated.

Example: Consider the table given below. What would be the viscosity at the temperature
of 8◦ ?

Temperature 0◦ 5◦ 10◦ 15◦

Viscosity 1.79 1.52 1.31 1.14
2 W EEK 3

Solution: We can use interpolation to estimate a reasonable value for the viscosity at the
temperature of 8◦ .

Theorem on Polynomial Interpolation

If x0 , x1 , x2 , . . . , xn are distinct real numbers, then for arbitrary values y0 , y1 , y2 , . . . , yn , there
is a unique polynomial Pn of degree at most n such that

Pn (xi ) = yi for 0 ≤ i ≤ n.

Such a polynomial is said to interpolate the data.

Fitting a Polynomial to Data

Given the data (x0 , y0 ), (x1 , y1 ), . . . (xn , yn ), where the x’s are assumed to be distinct, we
want to find a polynomial

Pn (x) = a0 + a1 x + a2 x2 + · · · + an xn

that interpolates the given data. Since Pn (xi ) = yi , we get a system of linear equations:

a0 + a1 x0 + a2 x20 + · · · + an xn0 = y0
a0 + a1 x1 + a2 x21 + · · · + an xn1 = y1
..
.
a0 + a1 xn + a2 x2n + · · · + an xnn = yn

This is a system of (n + 1) linear equations in (n + 1) unknowns a0 , a1 , . . . , an . Solving the

system is equivalent to solving the polynomial interpolation problem.

Example 3.1. Find a polynomial that fits the given points: (−1, 3), (0, 1), (1, 1), (4, 58).

Solution
Since we are given 4 points, the interpolated polynomial will be of degree ≤ 3. (The max-
imum degree of the polynomial is always one less that the number of points.) Let P (x) =
ax3 + bx2 + cx + d, we can write four equations involving the unknown coefficients a, b, c,
and d:

a(−1)3 + b(−1)2 + c(−1) + d = 3

a(0)3 + b(0)2 + c(0) + d = 1
a(1)3 + b(1)2 + c(1) + d = 1
a(4)3 + b(4)2 + c(4) + d = 58

Solving these equation simultaneously gives us

a = 0.75, b = 1, c = −1.75, d=1

W EEK 3 3

and the polynomial is P (x) = 0.75x3 + x2 − 1.75x + 1.

This procedure is awkward, especially if we want a new polynomial that is also made to fit
at the point (5, -25), or if we want to see what difference it would make to use a quadratic in-
stead of a cubic. We now look at some better and simpler ways of finding such interpolating
polynomials. We will look at two forms of interpolating polynomials:

1. Lagrange Form
2. Newton Form

3.1 Lagrange Form of the Interpolation Polynomial

The Lagrange form expresses Pn in the form

n
X
Pn (x) = yi li (x)
i=0
= y0 l0 (x) + y1 l1 (x) + y2 l2 (x) + . . . + yn ln (x)
where l0 , l1 , l2 , . . . , ln are known as the Cardinal functions that depend on x0 , x1 , x2 , . . . , xn
but not on y0 , y1 , y2 , . . . , yn . Here,
n
Y x − xj
li (x) =
j=0
xi − xj
j6=i

Example 3.2. Give the Lagrange form of the interpolating polynomial for the given data:

x -2 0 1
y 0 1 -1

Solution
The cardinal functions are:
(x − 0)(x − 1) 1
l0 (x) = = x(x − 1)
(−2 − 0)(−2 − 1) 6
(x + 2)(x − 1) 1
l1 (x) = = − (x + 2)(x − 1)
(0 + 2)(0 − 1) 2
(x + 2)(x − 0) 1
l2 (x) = = (x + 2)x
(1 + 2)(1 − 0) 3
Thus Lagrange form of the interpolating polynomial is
P2 (x) = 0l0 (x) + 1l1 (x) − 1l2 (x)
1 1
= − (x + 2)(x − 1) − (x + 2)x
2 3
4 W EEK 3

Example 3.3. Find a polynomial of least degree that assumes the following values:

x 0 1 2 3
y -3 2 -4 5

Solution
The cardinal functions are:
(x − 1)(x − 2)(x − 3) 1
l0 (x) = = − (x − 1)(x − 2)(x − 3)
(0 − 1)(0 − 2)(0 − 3) 6
(x − 0)(x − 2)(x − 3) 1
l1 (x) = = x(x − 2)(x − 3)
(1 − 0)(1 − 2)(1 − 3) 2
(x − 0)(x − 1)(x − 3) 1
l2 (x) = = − x(x − 1)(x − 3)
(2 − 0)(2 − 1)(2 − 3) 2
(x − 0)(x − 1)(x − 2) 1
l3 (x) = = x(x − 1)(x − 2)
(3 − 0)(3 − 1)(3 − 2) 6
Thus Lagrange form of the interpolating polynomial is
P3 (x) = −3l0 (x) + 2l1 (x) − 4l2 (x) + 5l3 (x)
1
= (x − 1)(x − 2)(x − 3) + x(x − 2)(x − 3)
2
5
+2x(x − 1)(x − 3) + x(x − 1)(x − 2)
6

Example 3.4. Given that f (0) = 3, f (1) = 2, f (2) = 7, and f (4) = 5.

(a) Find the Lagrange interpolating polynomial P3 (x).

(b) Use P3 (x) to approximate f (3).
3
P
(c) Verify that li (x) = 1.
i=0

Solution

(a) The cardinal functions are:

(x − 1)(x − 2)(x − 4) 1
l0 (x) = = − (x − 1)(x − 2)(x − 4)
(0 − 1)(0 − 2)(0 − 4) 8
(x − 0)(x − 2)(x − 4) 1
l1 (x) = = x(x − 2)(x − 4)
(1 − 0)(1 − 2)(1 − 4) 3
(x − 0)(x − 1)(x − 4) 1
l2 (x) = = − x(x − 1)(x − 4)
(2 − 0)(2 − 1)(2 − 4) 4
(x − 0)(x − 1)(x − 2) 1
l3 (x) = = x(x − 1)(x − 2)
(4 − 0)(4 − 1)(4 − 2) 24
W EEK 3 5

Thus Lagrange form of the interpolating polynomial is

P3 (x) = 3l0 (x) + 2l1 (x) + 7l2 (x) + 5l3 (x)

3 2
= − (x − 1)(x − 2)(x − 4) + x(x − 2)(x − 4)
8 3
7 5
− x(x − 1)(x − 4) + x(x − 1)(x − 2)
4 24

(b) f (3) ≈ P3 (3) = 10.5.

3
X
(c) li (x) = l0 (x) + l1 (x) + l2 (x) + l3 (x)
i=0
1 1 1
= − (x3 − 7x2 + 14x − 8) + (x3 − 6x2 + 8x) − (x3 − 5x2 + 4x)
8 3 4
1 3 2
+ (x − 3x + 2x)
 24     
1 1 1 1 3 7 5 1 2 7 8 1
= − + − + x + −2+ − x + − + −1+ x+1
8 3 4 24 8 4 8 4 3 12
= 1

3.2 Newton Form of the Interpolation Polynomial

The Newton form expresses Pn in the form

n
X i−1
Y
Pn (x) = ci (x − xj )
i=0 j=0
= c0 + c1 (x − x0 ) + c2 (x − x0 )(x − x1 ) + · · ·
+cn (x − x0 )(x − x1 ) · · · (x − xn−1 )

The first few cases of Pn are

P0 (x) = c0
P1 (x) = c0 + c1 (x − x0 )
P2 (x) = c0 + c1 (x − x0 ) + c2 (x − x0 )(x − x1 )

and so on.

Example 3.5. Find the Newton interpolating polynomial of least degree for the following table.

x 1 2 0 3
y 3 2 -4 5
6 W EEK 3

Solution
We need to find P3 (x). Note that

P3 (x) = c0 + c1 (x − x0 ) + c2 (x − x0 )(x − x1 ) + c3 (x − x0 )(x − x1 )(x − x2 )

= c0 + c1 (x − 1) + c2 (x − 1)(x − 2) + c3 (x − 1)(x − 2)x

Now

P3 (1) = 3, so c0 = 3.
P3 (2) = 2, so c0 + c1 (2 − 1) = 2 ⇒ 3 + c1 = 2 ⇒ c1 = −1.
P3 (0) = −4, so c0 + c1 (0 − 1) + c2 (0 − 1)(0 − 2) = −4
⇒ 3 − 1(−1) + c2 (−1)(−2) = −4 ⇒ c2 = −4.
P3 (3) = 5, so c0 + c1 (3 − 1) + c2 (3 − 1)(3 − 2) + c3 (3 − 1)(3 − 2)(3) = 5
⇒ 3 − 1(2) − 4(2)(1) + c3 (2)(1)(3) = 5 ⇒ c3 = 2.

Thus P3 (x) = 3 − (x − 1) − 4(x − 1)(x − 2) + 2(x − 1)(x − 2)x.

3.3 Divided Differences

Consider the Newton form of interpolating polynomial,

n
X i−1
Y
Pn (x) = ci (x − xj )
i=0 j=0
= c0 + c1 (x − x0 ) + c2 (x − x0 )(x − x1 ) + · · ·
+cn (x − x0 )(x − x1 ) · · · (x − xn−1 )

We need to find the values of c0 , c1 , . . . , cn (we have learnt the iterative method in the previ-
ous lecture and we will learn another simple method now).

We know that c0 depends only on f (x0 ), c1 depends on f (x0 ) and f (x1 ), . . ., cn depends on
f (x0 ), f (x1 ), . . . , f (xn ). To signify this dependency, let

cn = f [x0 , x1 , x2 , . . . , xn ].

The expression f [x0 , x1 , x2 , . . . , xn ] are called the divided differences of f . The constants
W EEK 3 7

c0 , c1 , c2 , c3 , . . . , cn can be written as

c0 = f [x0 ] = f (x0 )
f [x1 ] − f [x0 ]
c1 = f [x0 , x1 ] =
x1 − x0
f [x1 , x2 ] − f [x0 , x1 ]
c2 = f [x0 , x1 , x2 ] =
x2 − x0
f [x1 , x2 , x3 ] − f [x0 , x1 , x2 ]
c3 = f [x0 , x1 , x2 , x3 ] =
x3 − x0
..
.
f [x1 , x2 , . . . , xn ] − f [x0 , x1 , . . . , xn−1 ]
cn = f [x0 , x1 , x2 , . . . , xn ] =
xn − x0
Divided differences satisfy the equation
f [xi+1 , xi+2 , . . . , xi+j ] − f [xi , xi+1 , . . . , xi+j−1 ]
f [xi , xi+1 , xi+2 , . . . , xi+j ] =
xi+j − xi

If a table of function values (xi , f (xi )) is given we can construct from it a table of divided
differences. For example

x f [xi ] f [, ] f [, , ] f [, , , ]
x0 f (x0 )
f [x0 , x1 ]
x1 f (x1 ) f [x0 , x1 , x2 ]
f [x1 , x2 ] f [x0 , x1 , x2 , x3 ]
x2 f (x2 ) f [x1 , x2 , x3 ]
f [x2 , x3 ]
x3 f (x3 )

Example 3.6. Construct a divided difference table for these function values:

x 0 1 2 3
f (x) 3 -2 -4 5

Solution

xi f [xi ] f [, ] f [, , ] f [, , , ]
0 3
-5
3
1 -2 2
4
-2 3
11
2 -4 2
9
3 5
8 W EEK 3

Example 3.7. Find the Newton interpolating polynomial for the function values in the table given
in Example 4.1.

Solution

P3 (x) = c0 + c1 (x − x0 ) + c2 (x − x0 )(x − x1 ) + c3 (x − x0 )(x − x1 )(x − x2 )

3 4
= 3 − 5(x − 0) + (x − 0)(x − 1) + (x − 0)(x − 1)(x − 2)
2 3
3 4
= 3 − 5x + x(x − 1) + x(x − 1)(x − 2)
2 3

Example 3.8. Consider the following divided difference table:

x f [xi ] f [, ] f [, , ] f [, , , ]
0 -4
7
1 3 -6
-5 4
2 -2 6
7
3 5

Find P3 (x). Hence find f (0.5) and f (1.5).

Solution

P3 (x) = c0 + c1 (x − x0 ) + c2 (x − x0 )(x − x1 ) + c3 (x − x0 )(x − x1 )(x − x2 )

= −4 + 7(x − 0) − 6(x − 0)(x − 1) + 4(x − 0)(x − 1)(x − 2)
= −4 + 7x − 6x(x − 1) + 4x(x − 1)(x − 2).

f (0.5) ≈ P3 (0.5) = 2.5.

f (1.5) ≈ P3 (1.5) = 0.5.

Example 3.9. Use divided differences to find the Newton interpolating polynomial of least degree for
the given values.

x 1 2 0 3
f (x) 3 2 -4 5

Solution
W EEK 3 9

xi f [xi ] f [, ] f [, , ] f [, , , ]
1 3
-1
2 2 -4
3 2
0 -4 0
3
3 5

P3 (x) = c0 + c1 (x − x0 ) + c2 (x − x0 )(x − x1 ) + c3 (x − x0 )(x − x1 )(x − x2 )

= 3 − 1(x − 1) − 4(x − 1)(x − 2) + 2(x − 1)(x − 2)(x − 0)
= 3 − (x − 1) − 4(x − 1)(x − 2) + 2(x − 1)(x − 2)x.

Example 3.10. More Examples:

1. If f (x) = g(x) + h(x), then show that

f [x0 , x1 ] = g[x0 , x1 ] + h[x0 , x1 ].
Solution:
f (x1 ) − f (x0 )
f [x0 , x1 ] =
x1 − x0
[g(x1 ) + h(x1 )] − [g(x0 ) + h(x0 )]
=
x1 − x0
g(x1 ) − g(x0 ) + h(x1 ) − h(x0 )
=
x1 − x0
g(x1 ) − g(x0 ) h(x1 ) − h(x0 )
= +
x1 − x0 x1 − x0
= g[x0 , x1 ] + h[x0 , x1 ].
1
2. If f (x) = where k is a constant, then show that
k−x
1
f [x0 , x1 ] = .
(k − x0 )(k − x1 )
Solution:
f (x1 ) − f (x0 )
f [x0 , x1 ] =
x1 − x0
1 1
k−x1 − k−x0
=
x1 − x0
(k − x0 ) − (k − x1 ) 1
= ·
(k − x0 )(k − x1 ) x1 − x0
x1 − x0 1
= ·
(k − x0 )(k − x1 ) x1 − x0
1
=
(k − x0 )(k − x1 )
10 W EEK 3

3. If f (x) = ax2 + bx + c where a, b and c are real constants, then show that

f [x0 , x1 ] = a(x1 + x0 ) + b.

Solution:
f (x1 ) − f (x0 )
f [x0 , x1 ] =
x1 − x0
(ax21 + bx1 + c) − (ax20 + bx0 + c)
=
x1 − x0
(ax1 + bx1 ) − (ax20 + bx0 )
2
=
x1 − x0
2 2
a(x1 − x0 ) + b(x1 − x0 )
=
x1 − x0
a(x21 − x20 ) b(x1 − x0 )
= +
x1 − x0 x1 − x0
a(x1 − x0 )(x1 + x0 )
= +b
x1 − x0
= a(x1 + x0 ) + b

4. Let P2 (x) be the Newton form of interpolating polynomial of degree 2. Show that
P2′′ (x) = 2f [x0 , x1 , x2 ].

Solution: Note that

P2 (x) = c0 + c1 (x − x0 ) + c2 (x − x0 )(x − x1 ),
P2′ (x) = c1 + c2 (x − x0 ) + c2 (x − x1 ),
P2′′ (x) = c2 + c2 = 2c2 = 2f [x0 , x1 , x2 ].

5. Show that if f is continuous on the closed interval [x0 , x1 ] and differentiable on the
open interval (x0 , x1 ), then f [x0 , x1 ] = f ′ (c) for some c in (x0 , x1 ). (Hint: Use the Mean
Value Theorem)

Solution: If f is continuous on the closed interval [x0 , x1 ] and differentiable on the

open interval (x0 , x1 ), then by Mean Value Theorem, there is a number c ∈ (x0 , x1 )
such that
f (x1 ) − f (x0 )
f ′ (c) = = f [x0 , x1 ]
x1 − x0