Lecture 20
Polynomial interpolation with the Lagrange
basis
Today we saw that we can use the Lagrange
basis for polynomial interpolation. The Lagrange basis is not likely to cause
numerical errors as is the case when using the monomial basis for polynomial
interpolation. However, it is more expensive to do polynomial evaluation with
the Lagrange basis,
O(n2)
versus O(n) when using the monomial basis and the nested evaluation algorithm
(Horner's method). You can find material on the Lagrange basis in Recktenwald
section 10.2.2, and in the Ellis notes class
10.
I also gave a justification
to the claim that the interpolating polynomial is unique. The argument hinges
on the fact that any non-zero polynomial of degree n-1 has at most n
roots.
Posted: Thu - October 28, 2004 at 10:03 AM