1Polynomial interpolation
IB Numerical Analysis
1.4 A useful property of divided differences
In the next couple of sections, we are interested in the error of polynomial inter-
polation. Suppose the data points come from
f
i
=
f
(
x
i
) for some complicated
f we want to approximate, and we interpolate f at n data points {x
i
}
n
i=1
with
p
n
. How does the error
e
n
(
x
) =
f
(
x
)
− p
n
(
x
) depend on
n
and the choice of
interpolation points?
At the interpolation point, the error is necessarily 0, by definition of interpo-
lation. However, this does not tell us anything about the error elsewhere.
Our ultimate objective is to bound the error
e
n
by suitable multiples of the
derivatives of
f
. We will do this in two steps. We first relate the derivatives to
the divided differences, and then relate the error to the divided differences.
The first part is an easy result based on the following purely calculus lemma.
Lemma.
Let
g ∈ C
m
[
a, b
] have a continuous
m
th derivative. Suppose
g
is zero
at m + ` distinct points. Then g
(m)
has at least ` distinct zeros in [a, b].
Proof.
This is a repeated application of Rolle’s theorem. We know that between
every two zeros of
g
, there is at least one zero of
g
0
∈ C
m−1
[
a, b
]. So by
differentiating once, we have lost at most 1 zeros. So after differentiating
m
times, g
(m)
has lost at most m zeros. So it still has at least ` zeros.
Theorem.
Let
{x
i
}
n
i=0
∈
[
a, b
] and
f ∈ C
n
[
a, b
]. Then there exists some
ξ ∈ (a, b) such that
f[x
0
, ··· , x
n
] =
1
n!
f
(n)
(ξ).
Proof.
Consider
e
=
f − p
n
∈ C
n
[
a, b
]. This has at least
n
+ 1 distinct zeros in
[
a, b
]. So by the lemma,
e
(n)
=
f
(n)
− p
(n)
n
must vanish at some
ξ ∈
(
a, b
). But
then p
(n)
n
= n!f[x
0
, ··· , x
n
] constantly. So the result follows.