1Polynomial interpolation

IB Numerical Analysis

1.2 The Lagrange formula

It turns out the problem is not too hard. You can probably figure it out yourself

if you lock yourself in a room for a few days (or hours). In fact, we will come up

with two solutions to the problem.

The first is via the Lagrange cardinal polynomials. These are simple to

state, and it is obvious that these work very well. However, practically, this is

not the best way to solve the problem, and we will not talk about them much.

Instead, we use this solution as a proof of existence of polynomial interpolations.

We will then develop our second method on the assumption that polynomial

interpolations exist, and find a better way of computing them.

Definition

(Lagrange cardinal polynomials)

.

The Lagrange cardinal polynomials

with respect to the interpolation points {x

i

}

n

i=0

are, for k = 0, ··· , n,

`

k

(x) =

n

Y

i=0,i6=k

x −x

i

x

k

− x

i

.

Note that these polynomials have degree exactly

n

. The significance of these

polynomials is we have

`

k

(

x

i

) = 0 for

i 6

=

k

, and

`

k

(

x

k

) = 1. In other words, we

have

`

k

(x

j

) = δ

jk

.

This is obvious from definition.

With these cardinal polynomials, we can immediately write down a solution

to the interpolation problem.

Theorem. The interpolation problem has exactly one solution.

Proof. We define p ∈ P

n

[x] by

p(x) =

n

X

k=0

f

k

`

k

(x).

Evaluating at x

i

gives

p(x

j

) =

n

X

k=0

f

k

`

k

(x

j

) =

n

X

k=0

f

k

δ

jk

= f

j

.

So we get existence.

For uniqueness, suppose

p, q ∈ P

n

[

x

] are solutions. Then the difference

r

=

p − q ∈ P

n

[

x

] satisfies

r

(

x

j

) = 0 for all

j

, i.e. it has

n

+ 1 roots. However, a

non-zero polynomial of degree

n

can have at most

n

roots. So in fact

p − q

is

zero, i.e. p = q.

While this works, it is not ideal. If we one day decide we should add one more

interpolation point, we would have to recompute all the cardinal polynomials,

and that is not fun. Ideally, we would like some way to reuse our previous

computations when we have new interpolation points.