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.