Section 8.

3 Error in Polynomial Interpolation

· · · , xn in I. How well does pn (x) approximate f on the interval I? This question leads
to the analysis of interpolation error.
As we discussed at the beginning of Chapter 3 (Error Analysis), the error given by

MEn (x) = f (x) − pn (x). (8.17)

is the mathematical error involved in the interpolating polynomial. But, when we per-
form the calculations using finite precision floating-point arithmetic, then the polyno-
mial obtained, denoted by p̃n (x), need not be the same as the interpolating polynomial
pn (x). The error

AEn (x) = pn (x) − p̃n (x). (8.18)

is the arithmetic error involved in the interpolating polynomial.

The total error, denoted by TEn (x), involved in the polynomial interpolation is therefore
given by

TEn (x) = f (x) − p̃n (x) = (f (x) − pn (x)) + (pn (x) − p̃n (x)) = MEn (x) + AEn (x).

In Subsection 8.3.1, we derive the mathematical error involved in polynomial interpo-

lation. We analyze the effect of arithmetic error in Subsection 8.3.2.

8.3.1 Mathematical Error

The following theorem provides a formula for the interpolation error when we as-
sume that the necessary data are given exactly without any floating-point approxi-
mation.

Theorem 8.3.1 [Mathematical Error in Interpolation].

Let pn (x) be the polynomial interpolating a function f ∈ C n+1 [a, b] at the nodes
x0 , x1 , · · · , xn lying in I = [a, b]. Then for each x ∈ I, there exists a ξx ∈ (a, b) such
that n
f (n+1) (ξx ) !
MEn (x) = (x − xi ) (8.19)
(n + 1)! i=0

Proof.
If x is one of the nodes, then (8.19) holds trivially for any choice of ξx ∈ (a, b).
Therefore, it is enough to prove the theorem when x is not a node. The idea is to
obtain a function having at least n + 2 distinct zeros; and then apply Rolle’s theorem

139
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 8.3 Error in Polynomial Interpolation

n + 1 times to get the desired conclusion.

For a given x ∈ I with x #= xi (i = 0, 1, · · · , n), define a new function ψ on the
interval I by
! n
ψ(t) = f (t) − pn (t) − λ (t − xi ), t ∈ I, (8.20)
i=0

where λ is chosen so that ψ(x) = 0. This gives

f (x) − pn (x)
λ= n .
!
(x − xi )
i=0

Note that ψ(xi ) = 0 for each i = 0, 1, · · · , n. Thus, ψ has at least n + 2 distinct

zeros. By Rolle’s theorem, the function ψ ! has at least n + 1 distinct zeros in (a, b).
A repeated application of Rolle’s theorem n + 1 times to the function ψ gives that
ψ (n+1) has at least one zero in (a, b); call it ξx . Differentiating (8.20) (n + 1)-times
and noting that
" n
#(n+1)
!
p(n+1)
n (t) = 0, (t − xi ) = (n + 1)!, ψ (n+1) (ξx ) = 0,
i=0

we see that ξx satisfies

f (x) − pn (x)
0 = ψ (n+1) (ξx ) = f (n+1) (ξx ) − n (n + 1) !.
!
(x − xi )
i=0

Thus,
MEn (x)
f (n+1) (ξx ) − n (n + 1) ! = 0.
!
(x − xi )
i=0

The last equation yields (8.19).

The following theorem plays an important role in the error analysis of numerical inte-
gration. The idea behind the proof of this theorem is similar to the idea used in the
above theorem and is left as an exercise.

140
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 8.3 Error in Polynomial Interpolation

Theorem 8.3.2.
If f ∈ C n+1 [a, b] and if x0 , x1 , · · · , xn are distinct nodes in [a, b], then for any x #= xi ,
i = 0, 1, · · · , n, there exists a point ξx ∈ (a, b) such that

f (n+1) (ξx )
f [x0 , x1 , · · · , xn , x] = . (8.21)
(n + 1) !

Remark 8.3.3.
It is interesting to note that when all the nodes coincide, then (8.21) reduces to
(??).

Definition 8.3.4 [Infinity Norm].

If f is continuous on a closed interval I = [a, b], then the infinity norm of f ,
denoted by $f $∞,I , is defined as

$f $∞,I = max|f (x)|. (8.22)

x∈I

Example 8.3.5.
Let us obtain an upper bound of the mathematical error for the linear interpolat-
ing polynomial with respect to the infinity norm. As in Example 8.1.11, the linear
interpolating polynomial for f at x0 and x1 (x0 < x1 ) is given by

p1 (x) = f (x0 ) + f [x0 , x1 ](x − x0 ),

where f [x0 , x1 ] is given by (8.10). For each x ∈ I := [x0 , x1 ], using the formula (8.19),
the error ME1 (x) is given by

(x − x0 )(x − x1 ) !!
ME1 (x) = f (ξx ),
2
where ξx ∈ (x0 , x1 ) depends on x. Therefore,

$f !! $∞,I
|ME1 (x)| ≤ |(x − x0 )(x − x1 )| .
2
Note that the maximum value of |(x − x0 )(x − x1 )| as x varies in the interval [x0 , x1 ],

141
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 8.3 Error in Polynomial Interpolation

occurs at x = (x0 + x1 )/2. Therefore, we have

(x1 − x0 )2
|(x − x0 )(x − x1 )| ≤ .
4
Using this inequality, we get an upper bound

$f !! $∞,I
|ME1 (x)| ≤ (x1 − x0 )2 , for all x ∈ [x0 , x1 ].
8
Note that the above inequality is true for all x ∈ [x0 , x1 ]. In particular, this inequality
is true for an x at with the function |ME1 | attains its maximum. Thus, we have

$f !! $∞,I
$ME1 $∞,I ≤ (x1 − x0 )2 .
8
The right hand side quantity, which is a real number, is an upper bound for the
mathematical error in linear interpolation with respect to the infinity norm.

Example 8.3.6.
Let the function
f (x) = sin x
be approximated by an interpolating polynomial p9 (x) of degree less than or equal to
9 for f at the nodes x0 , x1 , · · · , x9 in the interval I := [0, 1]. Let us obtain an upper
bound for $ME9 $∞,I , where (from (8.19))
9
f (10) (ξx ) !
ME9 (x) = (x − xi ).
10! i=0

$9
Since |f (10) (ξx )| ≤ 1 and i=0 |x − xi | ≤ 1, we have

1
| sin x − p9 (x)| = |ME9 (x)| ≤ < 2.8 × 10−7 , for all x ∈ [0, 1].
10!
Since this holds for all x ∈ [0, 1], we have

$ME9 $∞,I < 2.8 × 10−7 .

The right hand side number is the upper bound for the mathematical error ME9 with
respect to the infinity norm on the interval I.

142
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 8.3 Error in Polynomial Interpolation

8.3.2 Arithmetic Error

Quite often, the polynomial interpolation that we compute is based on the function
data subjected to floating-point approximation. In this subsection, we analyze the
arithmetic error arising due to the floating-point approximation fl(f (xi )) of f (xi ) for
each node point xi , i = 0, 1, · · · , n in the interval I = [a, b]. All other computations are
assumed to be performed with infinite precision, for the sake of simplicity.
The Lagrange form of interpolating polynomial that uses the values fl(f (xi )) instead of
f (xi ), i = 0, 1, · · · , n is given by
n
%
p̃n (x) = fl(f (xi )) li (x).
i=0

We now analyze the arithmetic error. Denoting

$i := f (xi ) − fl(f (xi ); ||$||∞ = max{|$i | : i = 0, 1, · · · , n},

we have
& &
&%n ' ( & n
%
& &
|AEn (x)| = |pn (x) − p̃n (x)| = & f (xi ) − fl(f (xi )) li (x)& ≤ ||$||∞ ||li ||∞,I ,
& &
i=0 i=0

for all x ∈ I. Therefore,

n
%
$AEn $∞,I = $pn − p̃n $∞,I ≤ ||$||∞ ||li ||∞,I . (8.23)
i=0

The upper bound in (8.23) might grow quite large as n increases, especially when the
nodes are equally spaced as we will study now.
Assume that the nodes are equally spaced in the interval [a, b], with x0 = a and xn = b,
and xi+1 − xi = h for all i = 0, 1, · · · , n − 1. Note that h = (b − a)/n. We write

xi = a + ih, i = 0, 1, · · · , n.

Any x ∈ I can be written as

x = a + ηh,
where 0 ≤ η ≤ n. Here η is not necessarily an integer. Therefore, for any x ∈ I, we
have
!n n
!
(x − xi ) (η − i)
lk (x) = = , k = 0, · · · , n.
i=0
(xk − xi ) i=0 (k − i)
i%=k i%=k

143
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 8.3 Error in Polynomial Interpolation

(a) (b)
1.25 11

10

1.2 9

1.15 7
l(x)

l(x)
6

1.1 5

1.05 3

1 1
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
(c) x (d) x
3500 14000

3000 12000

2500 10000

2000 8000
l(x)

Mn
1500 6000

1000 4000

500 2000

0 0
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 2 4 6 8 10 12 14 16 18 20
x n

Figure 8.2: (a) to (c) depicts the graph of function l given by (8.24) for x ∈ [0, 1] when
n = 2, 8, and 18. (d) depicts the function n in the x-axis and Mn given by (8.25) in the
y-axis.

Clearly, the Lagrange polynomials are not dependent on the choice of a, b, and h. They
depend entirely on n and η (which depends on x). The Figure 8.2 (a), (b) and (c) shows
the graph of the function
n
%
l(x) = |li (x)| (8.24)
i=0

for n = 2, 8 and 18. It is observed that as n increases, the maximum of the function l
increases. In fact, as n → ∞, the maximum of l tends to infinity and it is observed in
Figure 8.2 (d) which depicts n in the x-axis and the function
n
%
Mn = ||li ||∞,I (8.25)
i=0

in the y-axis. This shows that the upper bound of the arithmetic error AEn given in
(8.23) tends to infinity as n → ∞. This gives the possibility that the arithmetic error
may tend to increase as n increases. Thus, as we increase the degree of the interpolating
polynomial, the approximation may go worser due to the presence of floating-point
approximation. In fact, this behavior of the arithmetic error in polynomial interpolation
can also be analyzed theoretically, but this is outside the scope of the present course.

144
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 8.3 Error in Polynomial Interpolation

8.3.3 Total Error

Let us now estimate the total error, which is given by
TEn (x) = f (x) − p̃n (x) = (f (x) − pn (x)) + (pn (x) − p̃n (x)). (8.26)
Taking infinity norm on both sides of the equation (8.26) and using triangle inequality,
we get
$TEn (x)$∞,I = ||f − p̃||∞,I ≤ ||f − pn ||∞,I + ||pn − p̃||∞,I ≤ ||f − pn ||∞,I + ||$||∞ Mn .
It is clear from the Figure 8.2 (d) that Mn increases exponentially with respect to n.
This implies that even if ||$||∞ is very small, a large enough n can bring in a significantly
large error in the interpolating polynomial.
Thus, for a given function and a set of equally spaced nodes, even if the mathematical
error is bounded, the presence of floating-point approximation in the given data can
lead to significantly large arithmetic error for larger values of n.

8.3.4 Runge Phenomenon

In the previous section, we have seen that even a small arithmetic error may lead to a
drastic magnification of total error as we go on increasing the degree of the polynomial.
This gives us a feeling that if the calculation is done with infinite precision (that is,
without any finite digit floating point arithmetic) and the function f is smooth, then we
always have a better approximation for a larger value of n. In other words, we expect
lim $f − pn $∞,I = 0.
n→∞

But this is not true in the case of equally spaced nodes. This was first shown by Carl
Runge, where he discovered that there are certain functions for which, as we go on
increasing the degree of interpolating polynomial, the total error increases drastically
and the corresponding interpolating polynomial oscillates near the boundary of the
interval in which the interpolation is done. Such a phenomenon is called the Runge
Phenomenon. This phenomenon is well understood by the following example given by
Carl Runge.

Example 8.3.7 [Runge’s Function].

Consider the Runge’s function defined on the interval [−1, 1] given by
1
f (x) = . (8.27)
1 + 25x2
The interpolating polynomials with n = 2, n = 8 and n = 18 are depicted in Figure
8.3. This figure clearly shows that as we increase the degree of the polynomial, the

145
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 8.3 Error in Polynomial Interpolation
(a) (b)
30
1

0.8 25

0.6
20
0.4

0.2
15
p n( x )

p n( x )
0

10
−0.2

−0.4
5
−0.6

−0.8 0

−1
−5
−1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1 −1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1
x x

Figure 8.3: Runge Phenomenon is illustrated. Figure (a) depicts the graph of the
function f given by (8.27) (blue solid line) along with the interpolating polynomial
of degree 2 (red dash line) and 8 (magenta dash dot line) with equally spaced nodes.
Figure (b) shows the graph of f (blue solid line) along with the interpolating polynomial
of degree 18 (red dash line) with equally spaced nodes.

interpolating polynomial differs significantly from the actual function especially, near
the end points of the interval.

In the light of the discussion made in Subsection 8.3.2, we may think that the Runge
phenomenon is due to the amplification of the arithmetic error. But, even if the cal-
culation is done with infinite precision (that is, without any finite digit floating point
arithmetic), we may still have the Runge phenomenon due to the amplification in
mathematical error. This can be observed by taking infinity norm on both sides of the
formula (8.19). This gives an upper bound of the infinity norm of MEn (x) as

(b − a)n+1 (n+1)
$MEn $∞,I ≤ $f $∞,I .
(n + 1)!

Although the first part, (b − a)n+1 /(n + 1)! in the upper bound tends to zero as n → ∞,
if the second part, $f (n+1) $∞,I increases significantly as n increases, then the upper
bound can still increase and makes it possible for the mathematical error to be quite
high.
A more deeper analysis is required to understand the Runge phenomenon more rigor-
ously.

8.3.5 Convergence of Sequence of Interpolating Polynomials

We end this section by stating without proof a negative result and a positive result
concerning the convergence of sequence of interpolating polynomials.

146
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 8.3 Error in Polynomial Interpolation

Theorem 8.3.8 [Faber].

For n ∈ N, let the sequence of nodes
(n) (n)
a ≤ x0 < x1 < · · · < x(n)
n ≤ b

be given. Then there exists a continuous function f defined on the interval [a, b] such
that the polynomials pn (x) that interpolate the function f at these nodes have the
property that $pn − f $∞,[a,b] does not tend to zero as n → ∞.

Example 8.3.9.
In fact, the interpolating polynomial pn (x) for the Runge’s function goes worser and
worser as shown in Figure 8.3 for increasing values of n with equally spaced nodes.
That is, $f − pn $∞,[−1,1] → ∞ as n → ∞ for any sequence of equally spaced nodes.

Let us now state a positive result concerning the convergence of sequence of interpo-
lating polynomials to a given continuous function.

Theorem 8.3.10.
Let f be a continuous function on the interval [a, b]. Then there exists a sequence of
nodes
n ≤ b, for n ∈ N,
(n) (n)
a ≤ x0 < x1 < · · · < x(n)
such that the polynomials pn (x) that interpolate the function f at these nodes satisfy
$pn − f $∞,[a,b] → 0 as n → ∞.

The Theorem 8.3.10 is very interesting because it implies that for the Runge’s function,
we can find a sequence of nodes for which the corresponding interpolating polynomial
yields a good approximation even for a large value of n.

Example 8.3.11.
For instance, define a sequence of nodes
) *
(2i + 1)π
(8.28)
(n)
xi = cos , i = 0, 1, · · · , n
2(n + 1)

147
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 8.3 Error in Polynomial Interpolation

(a) (b)
1.2 1.2

1 1

0.8 0.8

f ( x ) , p 1 8( x )
f ( x ) , p 4( x )

0.6 0.6

0.4 0.4

0.2 0.2

0 0

−0.2 −0.2
−1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1 −1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1
x x

(c) (d)
1.2 1.2

1 1

0.8 0.8
f ( x ) , p 3 2( x )

f ( x ) , p 6 4( x )

0.6 0.6

0.4 0.4

0.2 0.2

0 0

−0.2 −0.2
−1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1 −1 −0.8 −0.6 −0.4 −0.2 0 0.2 0.4 0.6 0.8 1
x x

Figure 8.4: Runge Phenomenon is illustrated with Chebyshev nodes. Figure (a) to (d)
shows the graph of the Runge function (blue solid line) and the interpolating polynomial
with Chebyshev nodes (red dash line) for n = 4, 18, 32 and 64 respectively. Note that
the two graphs in Figure (c) and (d) are indistinguishable.

148
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 8.4 Piecewise Polynomial Interpolation

for each n = 0, 1, 2, · · · . The nodes xi defined by (8.28) are called Chebyshev

(n)

nodes.
In particular, if n = 4, the nodes are
(4) (4)
x0 = cos(π/10), x1 = cos(3π/10),
(4) (4)
x2 = cos(5π/10), x3 = cos(7π/10), x44 = cos(9π/10).

Figure 8.4 depicts pn (x) for n = 4, 18, 32, and 64 along with the Runge’s function.
From these figures, we observe that the interpolating polynomial pn (x) agrees well
with the Runge’s function.

8.4 Piecewise Polynomial Interpolation

Quite often polynomial interpolation will be unsatisfactory as an approximation tool.
This is true if we insist on letting the order of the polynomial get larger and larger.
However, if we keep the order of the polynomial fixed, and use different polynomials
over different intervals, with the length of the intervals getting smaller and smaller, then
the resulting interpolating function approximates the given function more accurately.
Let us start with linear interpolation over an interval I = [a, b] which leads to
f (b) − f (a) x−b x−a
p1 (x) = f (a) + f [a, b](x − a) = f (a) + (x − a) = f (a) + f (b),
b−a a−b b−a
where the nodes are x0 = a, x2 = b. In addition to these two nodes, we now choose one
more point x1 such that x0 < x1 < x2 . With these three nodes, can obtain a quadratic
interpolation polynomial. Instead, we can interpolate the function f (x) in [x0 , x1 ] by
a linear polynomial with nodes x0 and x1 , and in [x1 , x2 ] by another linear polynomial
with nodes x1 and x2 . Such polynomials are given by
x − x1 x − x0 x − x2 x − x1
p1,1 (x) := f (x0 ) + f (x1 ), p1,2 (x) := f (x1 ) + f (x2 )
x0 − x1 x1 − x0 x1 − x2 x2 − x1
and the interpolating function is given by
+
p1,1 (x) , x ∈ [x0 , x1 ]
s(x) = .
p1,2 (x) , x ∈ [x1 , x2 ]

Note that s(x) is a continuous function on [x0 , x2 ], which interpolates f (x) and is
linear in [x0 , x1 ] and [x1 , x2 ]. Such an interpolating function is called piecewise linear
interpolating function.
In a similar way as done above, we can also obtain piecewise quadratic, cubic interpo-
lating functions and so on.

149
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 8.4 Piecewise Polynomial Interpolation

0.8

0.6

0.4

0.2

0
y

−0.2

−0.4

−0.6

−0.8

−1
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
x

'π (
Figure 8.5: The function f (x) = sin (blue line), p2 (x) (green bash line) and
ex
2
the piecewise linear interpolation s(x) (red dash and dot line) are shown. Blue dots
represent the given data, blue ‘x’ symbol indicates the value of f (0.25) and f (0.75),
green ‘+’ symbol indicates the value of p2 (0.25) and p2 (0.75), and the red ‘O’ symbol
represents the value of s(0.25) and s(0.75).

Example 8.4.1.
Consider the Example 8.1, where we have obtained the quadratic interpolating poly-
nomial for the function 'π (
f (x) = sin ex .
2
The piecewise linear polynomial interpolating function for the data
x 0 0.5 1
f (x) 1.0000 0.5242 −0.9037
is given by
+
1 − 0.9516 x , x ∈ [0, 0.5]
s(x) =
1.9521 − 2.8558 x , x ∈ [0.5, 1].

The following table shows the value of the function f at x = 0.25 and x = 0.75 along

150
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 8.5 Exercises

with the values of p2 (x) and s(x) with relative errors.

x f (x) p2 (x) s(x) Er (p2 (x)) Er (s(x))
0.25 0.902117 0.881117 0.762105 0.023278 0.155203
0.75 -0.182750 -0.070720 -0.189732 0.613022 0.038204
Figure 8.5 depicts the graph of f , p2 (x) and s(x). In this figure, we observe that the
quadratic polynomial p2 (x) agrees well with f (x) than s(x) for x ∈ [0, 0.5], whereas
s(x) agrees well with f (x) than p2 (x) for x ∈ [0.5, 1].

8.5 Exercises
Polynomial Interpolation
1. Let x0 , x1 , · · · , xn be distinct nodes. If p(x) is a polynomial of degree less than or
equal to n, then show that
n
%
p(x) = p(xi )li (x),
i=0

where li (x) is the ith Lagrange polynomial.

2. Show that the polynomial 1 + x + 2x2 is an interpolating polynomial for the data
x 0 1 2
.
y 1 4 11
Find an interpolating polynomial for the new data
x 0 1 2 3
.
y 1 4 11 -2
Does there exist a quadratic polynomial that satisfies the new data? Justify your
answer.
3. The quadratic polynomial p2 (x) = 34 x2 + 14 x + 12 interpolates the data
x −1 0 1
.
y 1 12 32
Find a node x3 (x3 ∈ / {−1, 0, 1}), and a real number y3 such that the polynomial
p3 (x) interpolating the data
x −1 0 1 x3
y 1 1/2 3/2 y3
is a polynomial of degree less than or equal to 2.
4. Let p(x), q(x), and r(x) be interpolating polynomials for the three sets of data
x 0 1 x 0 2 x 1 2 3
, , and
y y0 y1 y y0 y2 y y1 y2 y3
respectively. Let s(x) be the the interpolating polynomial for the data
x 0 1 2 3
.
y y0 y1 y2 y3

151
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 8.5 Exercises

If
p(x) = 1 + 2x, q(x) = 1 + x, and r(2.5) = 3,
then find the value of s(2.5).
5. Obtain Lagrange form of interpolating polynomial for equally spaced nodes.
6. Find the Largrange form of interpolating polynomial for the data:
x -2 -1 1 3
y -1 3 -1 19
7. Find the Lagrange form of interpolating polynomial p2 (x) that interpolates the
function f (x) = e−x at the nodes x0 = −1, x1 = 0 and x2 = 1. Further, find the
2

value of p2 (−0.9) (use 6-digit rounding). Compare the value with the true value
f (−0.9) (use 6-digit rounding). Find the percentage error in this calculation.

Newton’s Divided Difference Formula

8. For the particular function f (x) = xm (m ∈,N), show that
1 if n = m
f [x0 , x1 , · · · , xn ] =
0 if n > m
$n
9. Let x0 , x1 , · · · , xn be nodes, and f be a given function. Define w(x) = i=0 (x −
%n
xi ). Prove that f [x0 , x1 , · · · , xn ] =
f (xi )
.
w ! (x )
i=0 i

10. The following data correspond to a polynomial P (x) of unknown degree

x 0 1 2
.
P (x) 2 −1 4
Determine the coefficient of x in the polynomial P (x) if all the third order divided
differences are 1.

Error in Polynomial Interpolation

11. Let pn (x) be a polynomial of degree less than or equal to n that interpolates a
function f at a set of distinct nodes x0 , x1 , · · · , xn . If x ∈
/ { x0 , x1 , · · · , xn }, then
show that the error is given by
n
!
f (x) − pn (x) = f [x0 , x1 , · · · , xn , x] (x − xi ).
i=0

12. If f ∈ C n+1 [a, b] and if x0 , x1 , · · · , xn are distinct nodes in [a, b], then show that
there exists a point ξx ∈ (a, b) such that

f (n+1) (ξx )
f [x0 , x1 , · · · , xn , x] =
(n + 1) !

152
S. Baskar and S. Sivaji Ganesh Spring 2022-23
 Section 8.5 Exercises

13. Let N be a natural number. Let p1 (x) denote the linear interpolating polynomial
on the interval [N , N +1] interpolating the function f (x) = x2 at the nodes N and
N + 1. Find an upper bound for the mathematical error ME1 using the infinity
norm on the interval [N , N + 1] (i.e., $ME1 $∞, [N ,N +1] ).

14. Let p3 (x) denote a polynomial of degree less than or equal to 3 that interpolates
the function f (x) = ln x at the nodes x0 = 1, x1 = 43 , x2 = 53 , x3 = 2. Find a
lower bound on the absolute value of mathematical error |ME3 (x)| at the point
x = 32 , using the formula for mathematical error in interpolation.

15. Let f : [0, π6 ] → R be a given function. The following is the meaning for the
Cubic interpolation in a table of function values
x x0 x1 ··· xN
f (x) f (x0 ) f (x1 ) · · · f (xN )
The values of f (x) are tabulated for a set of equally spaced points in [a, b], say
xi for i = 0, 1, · · · , N with x0 = 0, xN = π6 , and h = xi+1 − xi > 0 for every
i = 0, 1, · · · , N − 1. For an x̄ ∈ [0, π6 ] at which the function value f (x̄) is not
tabulated, the value of f (x̄) is taken to be the value of p3 (x̄), where p3 (x) is the
polynomial of degree less than or equal to 3 that interpolates f at the nodes
xi , xi+1 , xi+2 , xi+3 where i is the least index such that x ∈ [xi , xi+3 ].
Take f (x) = sin x for x ∈ [0, π6 ]; and answer the following questions.
i) When x̄ and p3 are as described above, then show that |f (x̄) − p3 (x̄)| ≤ h48 .
4

ii) If h = 0.005, then show that cubic interpolation in the table of function
values yields the value of f (x̄) with at least 10 decimal-place accuracy.
16. Let x0 , x1 , · · · , xn be n + 1 distinct nodes, and f be a function. For each
i = 0, 1, · · · , n, let fl (f (xi )) denote the floating point approximation of f (xi ) ob-
tained by rounding to 5 decimal places (note this is different from using 5-digit
rounding). Assume that 0.1 ≤ f (xi ) < 1 for all i = 0, 1, · · · , n. Let pn (x) de-
note the Lagrange form of interpolating polynomial corresponding to the data
{(xi , f (xi )) : i = 0, 1, · · · , n}. Let p̃n (x) denote the Lagrange form of interpolat-
ing polynomial corresponding to the data {(xi , fl (f (xi ))) : i = 0, 1, · · · , n}. Show
that the arithmetic error at a point x̃ satisfies the inequality
n
1 −5 %
|pn (x̃) − p̃n (x̃)| ≤ 10 |lk (x̃)|.
2 k=0

153
S. Baskar and S. Sivaji Ganesh Spring 2022-23