Polynomial Interpolation - Non-Vandermonde Solutions

Non-Vandermonde Solutions

We are trying to construct our unique interpolation polynomial in the vector space of polynomials of degree n. When using a monomial basis for we have to solve the Vandermonde matrix to construct the coefficients for the interpolation polynomial. This can be a very costly operation (as counted in clock cycles of a computer trying to do the job). By choosing another basis for we can simplify the calculation of the coefficients but then we have to do additional calculations when we want to express the interpolation polynomial in terms of a monomial basis.

One method is to write the interpolation polynomial in the Newton form and use the method of divided differences to construct the coefficients, e.g. Neville's algorithm. The cost is O operations, while Gaussian elimination costs O operations. Furthermore, you only need to do O extra work if an extra point is added to the data set, while for the other methods, you have to redo the whole computation.

Another method is to use the Lagrange form of the interpolation polynomial. The resulting formula immediately shows that the interpolation polynomial exists under the conditions stated in the above theorem. Lagrange formula is to be preferred to Vandermorde formula when we are not interested in computing the coefficients of the polynomial, but in computing the value of in a given x not in the original data set. In this case, we can reduce complexity to O.

The Bernstein form was used in a constructive proof of the Weierstrass approximation theorem by Bernstein and has nowadays gained great importance in computer graphics in the form of Bézier curves.