Given distinct real numbers , and real numbers , we wish to find a polynomial (where is the degree), such that . The polynomial must be of at most degree since we have constraints. The real numbers could be function values, or table values. Given a function , we can write the constraints as, .

The most intuitive approach is to start with a general th degree polynomial of the form,

which is a linear combination of the *basis functions* . They form a basis for the space of all polynomials of degree or less, which we denote as . Because we are using a monomial basis of to construct the interpolating polynomial, we say that the polynomial is *constructed in the monomial basis*.

Explicitly writing out all constraints gives the following system of equations,

which we can write in matrix notation as,

We can solve this system using the QR-decomposition, Gaussian elimination or even specialised algorithms that exploit the Vandermonde structure.

In one of his lecture notes, Mark Embree and the University of Rice poses the following six questions that numerical analysts seek answers too;

1. Does such a polynomial exist?

2. If so, is it *unique*?

3. Does behave like at points when for ?

4. How can we compute *efficiently* on a computer?

5. How can we compute *accurately* on a computer (with floating point arithmetic)?

6. How should the interpolation points be chosen?

We could answer questions 1 and 2 using properties of Linear Algebra, but to avoid that we will leave them open for now. The other questions deserve their own posts, and we will deal with them eventually.

## 2 comments

Comments feed for this article

January 12, 2011 at 06:54

Interpolation – Monomial Basis (code and example) « DaFeda's Blog[...] 2011 in expository articles | Tags: code, interpolation, numerical analysis, vandermonde matrix We have seen how easy it is to come up with a interpolating polynomial in the monomial basis. The technique does [...]

January 13, 2011 at 07:25

Lagrange polynomials (introduction) « DaFeda's Blog[...] We already know how to solve this problem in the monomial basis, and we also know that the monomial basis is not particularly suited for the job. [...]