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.