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.