Interpolation and Approximation

This chapter is dedicated to find an approximation to a given function by a class of simpler

functions, mainly polynomials. The main uses of polynomial interpolation are

 Reconstructing the function when it is not given explicitly and only the values of 𝑓(𝑥)
and/or its certain order derivatives at a set of points, known as nodes/tabular
points/arguments are given.
 Replace the function 𝑓(𝑥) by an interpolating polynomial 𝑃(𝑥) so that many common
operations such as determination of roots, differentiation, and integration etc which are
intended for the function 𝑓(𝑥) may be performed using 𝑃 𝑥 .

Definition: A polynomial 𝑃(𝑥) is called interpolating polynomial if the values of 𝑃(𝑥) and/or its
certain order derivatives coincide with those of 𝑓(𝑥) and/or its same order derivatives at one or
more tabular points.

The reason behind choosing the polynomials ahead of any other functions is that polynomials
approximate continuous functions with any desired accuracy. That is, for any continuous
function 𝑓(𝑥) on an interval 𝑎 ≤ 𝑥 ≤ 𝑏 and error bound 𝛽 > 0 there is a polynomial 𝑝𝑛 (𝑥) (of
sufficiently large degree) such that 𝑓 𝑥 − 𝑝𝑛 𝑥 < 𝛽 for all 𝑥 ∈ 𝑎, 𝑏 . This is the famous
Weierstrass approximation theorem.

In this section we will be focusing on the following methods of interpolation

1. Lagrange’s interpolation
2. Newton’s divided difference interpolation
3. Newton’s forward and backward difference interpolation

1. Lagrange’s Interpolation
Assume that 𝑓 𝑥 is continuous on [𝑎, 𝑏] and further assume that we have 𝑛 + 1 distinct points
𝑎 ≤ 𝑥0 < 𝑥1 < 𝑥2 < ⋯ < 𝑥𝑛−1 < 𝑥𝑛 ≤ 𝑏. Let the values of the function 𝑓(𝑥) at these points are
known and are denoted by 𝑓0 = 𝑓 𝑥0 , 𝑓1 = 𝑓 𝑥1 , …, 𝑓𝑛 = 𝑓 𝑥𝑛 . We aim to find a polynomial
𝑃𝑛 𝑥 = 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥2 + ⋯ + 𝑎𝑛 𝑥𝑛 satisfying 𝑃𝑛 𝑥𝑖 = 𝑓 𝑥𝑖 , 𝑖 = 0,1, …, 𝑛.

Linear Interpolation
Let 𝑛 = 1. Then the nodes are 𝑥0 and 𝑥1 . The Lagrange linear interpolating polynomial is given
by

𝑃1 𝑥 = 𝑎0 + 𝑎1 𝑥,

where the coefficients 𝑎0 and 𝑎1 can be evaluated solving the equations

 𝑓0 = 𝑎0 + 𝑎1 𝑥0

𝑓1 = 𝑎0 + 𝑎1 𝑥1 .

The Lagrange linear interpolating polynomial is given by

𝑃1 𝑥 = 𝑙0 𝑥 𝑓0 + 𝑙1 𝑥 𝑓1,
𝑥−𝑥1 𝑥−𝑥0
where 𝑙0 𝑥 = and 𝑙1 𝑥 = are called Lagrange’s fundamental polynomials. The
𝑥0−𝑥1 𝑥1 −𝑥0
properties of the Lagrange fundamental polynomials are as follows:

(i) 𝑙0 𝑥 + 𝑙1 𝑥 = 1.
(ii) 𝑙0 𝑥0 = 1, 𝑙0 𝑥1 = 0; 𝑙1 𝑥0 = 0, 𝑙1 𝑥1 = 1.
(iii) The degrees of 𝑙0 (𝑥) and 𝑙1 𝑥 are one.

The error in linear interpolation is given by

1
𝐸1 𝑥, 𝑓 = 𝑥 − 𝑥0 𝑥 − 𝑥1 𝑓'' 𝜉 , 𝑥0 ≤ 𝜉 ≤ 𝑥1 .
2
The bound for the truncation error in linear interpolation is given by
2
𝑥1 − 𝑥0
𝐸1 𝑥, 𝑓 ≤ max |𝑓'' (𝑥)| .
8 𝑥0≤𝑥≤𝑥1

Example 1: Given that 𝑓 2 = 4, 𝑓 2.5 = 5.5. Find the linear interpolating polynomial using
Lagrange’s interpolation and hence find an approximate value of 𝑓 2.2 .

Answer: Given that 𝑥0 = 2, 𝑥1 = 2.5, 𝑓0 = 4, 𝑓1 = 5.5 . The Lagrange fundamental

polynomials are

𝑥 − 𝑥1 𝑥 − 2.5
𝑙0 𝑥 = = = 2 2.5 − 𝑥 = 5 − 2𝑥,
𝑥0 − 𝑥1 2 − 2.5

𝑥 − 𝑥0 𝑥−2
𝑙1 𝑥 = = = 2 𝑥 − 2 = 2𝑥 − 4.
𝑥1 − 𝑥0 2.5 − 2

The linear Lagrange interpolating polynomial is given by

𝑃1 𝑥 = 𝑙0 𝑥 𝑓0 + 𝑙1 𝑥 𝑓1 = 4 5 − 2𝑥 + 5.5 2𝑥 − 4 = 3𝑥 − 2.

An approximate value of 𝑓 2.2 ≈ 𝑃1 2.2 = 3 × 2.2 − 2 = 4.6.

Quadratic Interpolation
Here 𝑛 = 2. We need to find an interpolating polynomial of the form
 𝑃2 𝑥 = 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥2

where 𝑎0 , 𝑎1 and 𝑎2 are arbitrary constants which satisfies the condition 𝑃2 𝑥0 = 𝑓0 , 𝑃2 𝑥1 =

𝑓1 and 𝑃2 𝑥2 = 𝑓2 . That is, we need to solve the following system of equations:

𝑎0 + 𝑎1 𝑥0 + 𝑎2 𝑥20 = 𝑓0

𝑎0 + 𝑎1 𝑥1 + 𝑎2 𝑥22 = 𝑓1

𝑎0 + 𝑎1 𝑥2 + 𝑎2𝑥22 = 𝑓2 .

The Lagrange quadratic interpolating polynomial is given by

𝑃2 𝑥 = 𝑙0 𝑥 𝑓0 + 𝑙1 𝑥 𝑓1 + 𝑙2 𝑥 𝑓2

where 𝑙0 𝑥 , 𝑙1 (𝑥) and 𝑙2 (𝑥) are Lagrange’s fundamental polynomial and are defined by

𝑥 − 𝑥1 (𝑥 − 𝑥2 ) 𝑥 − 𝑥0 (𝑥 − 𝑥2 ) 𝑥 − 𝑥0 (𝑥 − 𝑥1 )
𝑙0 𝑥 = , 𝑙1 𝑥 = 𝑎𝑛𝑑 𝑙2 𝑥 = .
𝑥0 − 𝑥1 (𝑥0 − 𝑥2 ) 𝑥1 − 𝑥0 (𝑥1 − 𝑥2 ) 𝑥2 − 𝑥0 (𝑥2 − 𝑥1 )

The truncation error in Lagrange’s quadratic polynomial is given by

1
𝐸2 𝑥, 𝑓 = 𝑥 − 𝑥0 𝑥 − 𝑥1 𝑥 − 𝑥2 𝑓''' 𝜉 , 𝑥0 ≤ 𝜉 ≤ 𝑥2 .
3!
The bound for the quadratic Lagrange’s interpolating polynomial is

𝑀3
𝐸2 𝑥, 𝑓 ≤ max 𝑥 − 𝑥0 𝑥 − 𝑥1 𝑥 − 𝑥3 , 𝑀3 = max 𝑓''' 𝑥 .
6 0≤𝑥≤𝑥2
𝑥 𝑥0≤𝑥≤𝑥2

Example:

General Formula
The general Lagrange’s interpolating polynomial for 𝑛 + 1 nodes 𝑥0 , 𝑥1 , …, 𝑥𝑛 is given by
𝑛

𝑃𝑛 𝑥 = 𝑙𝑘 𝑥 𝑓𝑘 ,
𝑘=0

where the 𝑛-th degree Lagrange’s fundamental polynomial is given by

𝑥 − 𝑥0 𝑥 − 𝑥1 ⋯ 𝑥 − 𝑥𝑘−1 𝑥 − 𝑥𝑘+1 ⋯(𝑥 − 𝑥𝑛 )

𝑙𝑘 𝑥 = 𝑓𝑜𝑟 𝑘 = 0,1,2, …, 𝑛.
𝑥𝑘 − 𝑥0 𝑥𝑘 − 𝑥1 ⋯ 𝑥𝑘 − 𝑥𝑘−1 𝑥𝑘 − 𝑥𝑘+1 ⋯(𝑥𝑘 − 𝑥𝑛 )

The truncation error in Lagrange’s interpolation is

 𝑤 𝑥
𝐸𝑛 𝑥, 𝑓 = 𝑓 𝑛+1 𝜉 , 𝑥0 ≤ 𝜉 ≤ 𝑥𝑛 ,
𝑛+1 !

where 𝑤 𝑥 = 𝑥 − 𝑥0 𝑥 − 𝑥1 ⋯ 𝑥 − 𝑥𝑛 .

Example 2. Given that 𝑓 0 = 1, 𝑓 1 = 3 and 𝑓 3 = 55. Find the unique polynomial of

degree 2 or less, which fits the given data. Find the truncation error.

Answer: By hypothesis, 𝑥0 = 0, 𝑥1 = 1, 𝑥2 = 3 ; 𝑓0 = 1, 𝑓1 = 3, 𝑓2 = 55. The Lagrange

fundamental polynomials are

𝑥 − 1 (𝑥 − 3) 1
𝑙0 𝑥 = = 𝑥 − 1 (𝑥 − 3)
0 − 1 (0 − 3) 3

𝑥 − 0 (𝑥 − 3) 1 𝑥 − 0 (𝑥 − 1) 1
𝑙1 𝑥 = =− 𝑥 𝑥 − 3 , 𝑙2 𝑥 = = 𝑥 𝑥−1 .
1 − 0 (1 − 3) 2 3 − 0 (3 − 1) 6

The Lagrange quadratic interpolating polynomial is

1 3 55
𝑃2 𝑥 = 𝑙0 𝑥 𝑓0 + 𝑙1 𝑥 𝑓1 + 𝑙2 𝑥 𝑓2 = 𝑥−1 𝑥−3 − 𝑥 𝑥−3 + 𝑥 𝑥−1
3 2 6
= 8𝑥2 − 6𝑥 + 1

The truncation error is

1
𝐸2 𝑥 = 𝑥 𝑥 − 1 𝑥 − 3 𝑓''' 𝜉 , 0 ≤ 𝜉 ≤ 3.
6

Newton’s Divided Difference Interpolation

Let 𝑓(𝑥) be a function defined on the interval [𝑎, 𝑏]. Let 𝑎 = 𝑥0 < 𝑥1 < 𝑥2 < ⋯ < 𝑥𝑛 = 𝑏 be a
partition of [𝑎, 𝑏] . The divided difference of 𝑓 𝑥 at 𝑥0 , written as 𝑓 𝑥0 , is the value of the
function at 𝑥0 . That is,

𝑓 𝑥0 = 𝑓 𝑥0 = 𝑓0 .

The first order divided difference at the nodes 𝑥0 and 𝑥1 is defined as

𝑓1 − 𝑓0
𝑓 𝑥0, 𝑥1 = .
𝑥1 − 𝑥0

The second order divided difference at the nodes 𝑥0, 𝑥1 , 𝑥2 is defined by

 𝑓 𝑥1 , 𝑥2 − 𝑓[𝑥0 , 𝑥1 ]
𝑓 𝑥0 , 𝑥1 , 𝑥2 =
𝑥2 − 𝑥0
𝑓0 𝑓1 𝑓2
= + +
𝑥0 − 𝑥1 (𝑥0 − 𝑥2 ) 𝑥1 − 𝑥0 (𝑥1 − 𝑥2 ) 𝑥2 − 𝑥0 (𝑥2 − 𝑥1 )

The 𝑛-th order divided difference is defined by

𝑛
𝑓𝑖
𝑓 𝑥0 , 𝑥1, ⋯, 𝑥𝑛 = 𝑛 .
∏𝑗=0,𝑗≠𝑖 (𝑥𝑖 − 𝑥𝑗 )
𝑖=0

Divided difference table:

Nodes Functional Values 1st order Div. Diff. 2nd order Div. Diff.

𝑥0 𝑓[𝑥0 ]

𝑥1 𝑓[𝑥1 ] 𝑓[𝑥0 , 𝑥1 ]
𝑥2 𝑓[𝑥2 ] 𝑓[𝑥1 , 𝑥2 ] 𝑓[𝑥0 , 𝑥1 , 𝑥2 ]

The Newton divided difference interpolating polynomial 𝑃𝑛 (𝑥) interpolating at 𝑛 + 1 points

𝑥0 , 𝑥1 , …, 𝑥𝑛 is given by

𝑃𝑛 𝑥 = 𝑓 𝑥0 + 𝑥 − 𝑥0 𝑓 𝑥0 , 𝑥1 + 𝑥 − 𝑥0 𝑥 − 𝑥1 𝑓 𝑥0 , 𝑥1 , 𝑥2 + ⋯
+ 𝑥 − 𝑥0 ⋯ 𝑥 − 𝑥𝑛−1 𝑓 𝑥0 , 𝑥1 , ⋯, 𝑥𝑛 .

Hence find the interpolating polynomial and an approximation to the value 𝑓(7).

Answer: The divided difference table is given by

Finite Difference Operators
Let the nodes 𝑥0, 𝑥1 , …, 𝑥𝑛 be equally spaced. That is, 𝑥𝑖 = 𝑥0 + 𝑖ℎ, 𝑖 = 0,1, …, 𝑛. We now define
the following operators:

The Shift Operator: 𝐸 𝑓 𝑥𝑖 = 𝑓 𝑥𝑖 + ℎ .

The forward difference Operator: ∆𝑓 𝑥𝑖 = 𝑓 𝑥𝑖 + ℎ − 𝑓 𝑥𝑖 .

The backward difference operator: ∇ 𝑓 𝑥𝑖 = 𝑓 𝑥𝑖 − 𝑓 𝑥𝑖 − ℎ .

ℎ ℎ
The central difference operator: 𝛿 𝑓 𝑥𝑖 = 𝑓 𝑥𝑖 + − 𝑓 𝑥𝑖 − .
2 2
 1 ℎ ℎ
The average operator: 𝜇 𝑓 𝑥𝑖 = 𝑓 𝑥𝑖 +
2
+ 𝑓 𝑥𝑖 −
2
.
2

Repeated application of the difference operators lead to the following higher order differences.

The forward and backward difference tables can be computed as follows:

Interpolating polynomials using the forward difference operator
The Gregory-Newton forward difference interpolating polynomial is given by

𝑥 − 𝑥0 𝑥 − 𝑥0 (𝑥 − 𝑥1 ) 2 𝑥 − 𝑥0 ⋯ 𝑥 − 𝑥𝑛−1 𝑛
𝑃𝑛 𝑥 = 𝑓0 + ∆𝑓0 + ∆ 𝑓0 + ⋯ + ∆ 𝑓0 .
ℎ 2! ℎ2 𝑛! ℎ𝑛

Putting 𝑢 = (𝑥 − 𝑥0 )/ℎ, the interpolating polynomial using forward difference operator becomes
𝑛
𝑢 𝑖
𝑃𝑛 𝑥 = ∆ 𝑓0 ,
𝑖
𝑖=0

With the error

𝑢 𝑢 − 1 ⋯(𝑢 − 𝑛) 𝑛+1 𝑛+1

𝐸𝑛 𝑥, 𝑓 = ℎ 𝑓 𝜉 , 𝑥0 ≤ 𝜉 ≤ 𝑥𝑛 .
𝑛+1 !

Interpolating polynomials using the backward difference operator

𝑥−𝑥𝑛
Let 𝑢 = ℎ
. The Gregory-Newton backward difference interpolating polynomial is given by

𝑢(𝑢 + 1) 2 𝑢 𝑢+1 ⋯ 𝑢+𝑛−1 𝑛

𝑃𝑛 𝑥 = 𝑓𝑛 + 𝑢 ∇ 𝑓𝑛 + ∇ 𝑓𝑛 + ⋯ + ∇ 𝑓𝑛 .
2! 𝑛!
The truncation error becomes

𝑢 𝑢 + 1 ⋯(𝑢 + 𝑛) 𝑛+1 𝑛+1

𝐸𝑛 𝑥, 𝑓 = ℎ 𝑓 𝜉 , 𝑥0 ≤ 𝜉 ≤ 𝑥𝑛 .
𝑛+1 !
Example 4: For the following data calculate the differences, obtain the forward and backward
difference polynomials. Interpolate at 𝑥 = 0.25 and 𝑥 = 0.35.

Solution: The forward difference table is obtained as