CS3414 Afterclass Notes --- 31 May, 2002

Fitting Data
  1. Piecewise Polynomials

    1. Intro

      • Basic idea, picture, and definition.

      • Key questions:
        • Where are the knots?
        • What degree for each piece?
        • How much continuity between pieces?

    2. Splines

      • Def: a spline is a degree k piecewise polynomial with k-1 continuous derivatives, i.e., it's as smooth as it can be.

      • Piecewise linear spline interpolation: just ``connect-the-dots''.

      • Quadratic splines are not used as often as cubic splines because cubic splines look a little better and they can be constructed for little more work.

      • Cubic spline interpolation: the most common case.

      • Some theory. There are theorems which show that the accuracy of spline interpolation is better than polynomial interpolation in the sense that the interpolant more closely matches the (unknown) function from which the data is derived, across the interval where the data lies. For example, see Equation (2) on page 164 of our text (error estimate for polynomial interpolation) and the theorem on linear splines on page 322 of the text.

        The bottom line is that, for sufficiently smooth functions f(x), the maximum difference between f(x) and the piecewise linear (spline) goes to zero like O(h2), where h is the interval size. We can make no similar statement about the error shrinking as n grows for polynomial interpolation (it may not even shrink at all, in some cases). For cubic splines, the corresponding theorem says the error shrinks like O(h4).