1Polynomial interpolation

IB Numerical Analysis

1.5 Error bounds for polynomial interpolation

The actual error bound is not too difficult as well. It turns out the error

e

=

f −p

n

is “like the next term in the Newton’s formula”. This vague sentence

is made precise in the following theorem:

Theorem.

Assume

{x

i

}

n

i=0

⊆

[

a, b

] and

f ∈ C

[

a, b

]. Let

¯x ∈

[

a, b

] be a non-

interpolation point. Then

e

n

(¯x) = f[x

0

, x

1

, ··· , x

n

, ¯x]ω(¯x),

where

ω(x) =

n

Y

i=0

(x − x

i

).

Note that we forbid the case where

¯x

is an interpolation point, since it is

not clear what the expression

f

[

x

0

, x

1

, ··· , x

n

, ¯x

] means. However, if

¯x

is an

interpolation point, then both

e

n

(

¯x

) and

ω

(

¯x

) are zero, so there isn’t much to

say.

Proof. We think of ¯x = x

n+1

as a new interpolation point so that

p

n+1

(x) − p

n

(x) = f[x

0

, ··· , x

n

, ¯x]ω(x)

for all

x ∈ R

. In particular, putting

x

=

¯x

, we have

p

n+1

(

¯x

) =

f

(

¯x

), and we get

the result.

Combining the two results, we find

Theorem.

If in addition

f ∈ C

n+1

[

a, b

], then for each

x ∈

[

a, b

], we can find

ξ

x

∈ (a, b) such that

e

n

(x) =

1

(n + 1)!

f

(n+1)

(ξ

x

)ω(x)

Proof.

The statement is trivial if

x

is an interpolation point — pick arbitrary

ξ

x

, and both sides are zero. Otherwise, this follows directly from the last two

theorems.

This is an exact result, which is not too useful, since there is no easy

constructive way of finding what

ξ

x

should be. Instead, we usually go for a

bound. We introduce the max norm

kgk

∞

= max

t∈[a,b]

|g(t)|.

This gives the more useful bound

Corollary. For all x ∈ [a, b], we have

|f(x) − p

n

(x)| ≤

1

(n + 1)!

kf

(n+1)

k

∞

|ω(x)|

Assuming our function

f

is fixed, this error bound depends only on

ω

(

x

),

which depends on our choice of interpolation points. So can we minimize

ω

(

x

)

in some sense by picking some clever interpolation points ∆ =

{x

i

}

n

i=0

? Here

we will have

n

fixed. So instead, we put ∆ as the subscript. We can write our

bound as

kf −p

∆

k

∞

≤

1

(n + 1)!

kf

(n+1)

k

∞

kω

∆

k

∞

.

So the objective is to find a ∆ that minimizes kω

∆

k

∞

.

For the moment, we focus on the special case where the interval is [

−

1

,

1].

The general solution can be obtained by an easy change of variable.

For some magical reasons that hopefully will become clear soon, the optimal

choice of ∆ comes from the Chebyshev polynomials.

Definition

(Chebyshev polynomial)

.

The Chebyshev polynomial of degree

n

on

[−1, 1] is defined by

T

n

(x) = cos(nθ),

where x = cos θ with θ ∈ [0, π].

So given an

x

, we find the unique

θ

that satisfies

x

=

cos θ

, and then find

cos

(

nθ

). This is in fact a polynomial in disguise, since from trigonometric

identities, we know

cos

(

nθ

) can be expanded as a polynomial in

cos θ

up to

degree n.

Two key properties of T

n

on [−1, 1] are

(i) The maximum absolute value is obtained at

X

k

= cos

πk

n

for k = 0, ··· , n with

T

n

(X

k

) = (−1)

k

.

(ii) This has n distinct zeros at

x

k

= cos

2k − 1

2n

π

.

for k = 1, ··· , n.

When plotted out, the polynomials look like this:

x

T

4

(x)

−1 1

1

−1

All that really matters about the Chebyshev polynomials is that the maximum

is obtained at

n

+ 1 distinct points with alternating sign. The exact form of the

polynomial is not really important.

Notice there is an intentional clash between the use of

x

k

as the zeros and

x

k

as the interpolation points — we will show these are indeed the optimal

interpolation points.

We first prove a convenient recurrence relation for the Chebyshev polynomials:

Lemma

(3-term recurrence relation)

.

The Chebyshev polynomials satisfy the

recurrence relations

T

n+1

(x) = 2xT

n

(x) − T

n−1

(x)

with initial conditions

T

0

(x) = 1, T

1

(x) = x.

Proof.

cos((n + 1)θ) + cos((n − 1)θ) = 2 cos θ cos(nθ).

This recurrence relation can be useful for many things, but for our purposes,

we only use it to show that the leading coefficient of T

n

is 2

n−1

(for n ≥ 1).

Theorem

(Minimal property for

n ≥

1)

.

On [

−

1

,

1], among all polynomials

p ∈ P

n

[

x

] with leading coefficient 1,

1

2

n−1

kT

n

k

minimizes

kpk

∞

. Thus, the

minimum value is

1

2

n−1

.

Proof.

We proceed by contradiction. Suppose there is a polynomial

q

n

∈ P

n

with leading coefficient 1 such that kq

n

k

∞

<

1

2

n−1

. Define a new polynomial

r =

1

2

n−1

T

n

− q

n

.

This is, by assumption, non-zero.

Since both the polynomials have leading coefficient 1, the difference must

have degree at most

n −

1, i.e.

r ∈ P

n−1

[

x

]. Since

1

2

n−1

T

n

(

X

k

) =

±

1

2

n−1

, and

|q

n

(

X

n

)

| <

1

2

n−1

by assumption,

r

alternates in sign between these

n

+ 1 points.

But then by the intermediate value theorem,

r

has to have at least

n

zeros. This

is a contradiction, since r has degree n − 1, and cannot be zero.

Corollary. Consider

w

∆

=

n

Y

i=0

(x − x

i

) ∈ P

n+1

[x]

for any distinct points ∆ = {x

i

}

n

i=0

⊆ [−1, 1]. Then

min

∆

kω

∆

k

∞

=

1

2

n

.

This minimum is achieved by picking the interpolation points to be the zeros of

T

n+1

, namely

x

k

= cos

2k + 1

2n + 2

π

, k = 0, ··· , n.

Theorem.

For

f ∈ C

n+1

[

−

1

,

1], the Chebyshev choice of interpolation points

gives

kf −p

n

k

∞

≤

1

2

n

1

(n + 1)!

kf

(n+1)

k

∞

.

Suppose

f

has as many continuous derivatives as we want. Then as we

increase

n

, what happens to the error bounds? The coefficients involve dividing

by an exponential and a factorial. Hence as long as the higher derivatives of

f

don’t blow up too badly, in general, the error will tend to zero as

n → ∞

, which

makes sense.

The last two results can be easily generalized to arbitrary intervals [

a, b

], and

this is left as an exercise for the reader.