(last update: 01.05.2013)
As we have shown, using equally spaced interpolation points can lead to polynomials growing wildly at the end-points of the interval. Another problem we must deal with is the fact that the monomial basis is not ideal for interplation purposes. First, we recall that every polynomial can be written as a linear combination of the monomial basis . The problem with this basis is that its elements grow increasingly closer, which is evident from the attached figure.
From linear algebra we know that is a basis for , but we could just as well use as a basis. Any two independent vectors in form a basis of , but they are not all equally good considering computation with finite-precision arithmetic.
If we wanted to write the vector as a linear combination of the first basis we would simply add the basis vectors, . On the other hand, writing the same vector using the second basis gives, . The reason why this is a problem is that if we make a small change to the vector we wish to expand as a linear combination of the basis vectors, the coefficients will change by a huge amount, which may lead to a lot of problem when working with finite-precision arithmetic.
This simple example illustrates the importance of a good basis.