1Polynomial interpolation

IB Numerical Analysis



1.1 The interpolation problem
The idea of polynomial interpolation is that we are given
n
+ 1 distinct interpo-
lation points
{x
i
}
n
i=0
R
, and
n
+ 1 data values
{f
i
}
n
i=0
R
. The objective is
to find a p P
n
[x] such that
p(x
i
) = f
i
for i = 0, ··· , n.
In other words, we want to fit a polynomial through the points (x
i
, f
i
).
There are many situations where this may come up. For example, we may
be given
n
+ 1 actual data points, and we want to fit a polynomial through
the points. Alternatively, we might have a complicated function
f
, and want
to approximate it with a polynomial
p
such that
p
and
f
agree on at least that
n + 1 points.
The naive way of looking at this is that we try a polynomial
p(x) = a
n
x
n
+ a
n1
x
n1
+ ··· + a
0
,
and then solve the system of equations
f
i
= p(x
i
) = a
n
x
n
i
+ a
n1
x
n1
i
+ ··· + a
0
.
This is a perfectly respectable system of
n
+ 1 equations in
n
+ 1 unknowns.
From linear algebra, we know that in general, such a system is not guaranteed
to have a solution, and if the solution exists, it is not guaranteed to be unique.
That was not helpful. So our first goal is to show that in the case of polynomial
interpolation, the solution exists and is unique.