CS3414 Afterclass Notes --- 29 May, 2002

1. Introduction (last time)

2. Polynomial interpolation

   1. Facts (last time)

   2. Choosing basis functions
      1. Usually a bad idea: power basis
         • Use b_i(x) = x^i-1
         • Not usually a good idea because: the interpolant g(x) can be hard to evaluate accurately (stability problems, overflow); and constructin g(x) (i.e., finding the coefficients) is unnecessarily expensive and ill-conditioned.

      2. A slightly better idea: shifted power basis. The problem of evaluating g(x) accurately can be improved by using as basis functions b_i(x) = (x-c)^i-1, where c is a constant of roughly the same size as you expect x to be. This doesn't help improve the problems with constructing g(x) in the first place, however

      3. A slick idea: Lagrange basis functions
         • By choosing the basis functions cleverly, we can reduce the cost of finding constructing g(x) to zero.
         • See Section 4.1 for the formulas.
         • While construction of g(x) is trivial when Lagrange basis functions are used, manipulating g(x) (e.g., evaluating it, differentiating it, ...) is awkward. And adding new data points is definitely awkward.

      4. Another slick idea: Newton basis functions
         • Again, basis functions are chosen so that the cost of constructing g(x) is relatively cheap; this time O(n²), which is much better than the O(n³) which is needed to find the coefficients of the interpolant with respect to the power basis.
         • The Newton basis functions look like this:
           b_i(x) = (x-x₁) * (x-x₂) * ... * (x-x_i-1), with b₁(x) = 1.
         • The long discussion on "divided differences" in Chapter 4 is basically a slick way to compute the coefficents of g(x) with respect to the Newton basis.
         • Manipulating g(x) with these basis functions is relatively easy. But a clear advantage of the Newton approach is the ease with with new data can be encorporated into the interpolant.