#### CS3414 Afterclass Notes --- 29 May, 2002

**Fitting Data** (parts of Chapters 4, 7, 10)
- Introduction (last time)

- Polynomial interpolation

- Facts (last time)

- Choosing basis functions
- 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.

- 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

- 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.

- 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
^{2}), which is much better than the
O(n^{3}) 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_{1}) * (x-x_{2}) * ... *
(x-x_{i-1}),
with b_{1}(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.