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

n−1

x

n−1

+ ··· + a

0

,

and then solve the system of equations

f

i

= p(x

i

) = a

n

x

n

i

+ a

n−1

x

n−1

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.