htswanalysis/MACS/lib/gsl/gsl-1.11/doc/bspline.texi

   1 @cindex basis splines, B-splines
   2 @cindex splines, basis
   3
   4 This chapter describes functions for the computation of smoothing
   5 basis splines (B-splines). The header file @file{gsl_bspline.h}
   6 contains prototypes for the bspline functions and related declarations.
   7
   8 @menu
   9 * Overview of B-splines::
  10 * Initializing the B-splines solver::
  11 * Constructing the knots vector::
  12 * Evaluation of B-spline basis functions::
  13 * Example programs for B-splines::
  14 * References and Further Reading::
  15 @end menu
  16
  17 @node Overview of B-splines
  18 @section Overview
  19 @cindex basis splines, overview
  20
  21 B-splines are commonly used as basis functions to fit smoothing
  22 curves to large data sets. To do this, the abscissa axis is
  23 broken up into some number of intervals, where the endpoints
  24 of each interval are called @dfn{breakpoints}. These breakpoints
  25 are then converted to @dfn{knots} by imposing various continuity
  26 and smoothness conditions at each interface. Given a nondecreasing
  27 knot vector
  28 @c{$t = \{t_0, t_1, \dots, t_{n+k-1}\}$}
  29 @math{t = @{t_0, t_1, @dots{}, t_@{n+k-1@}@}},
  30 the @math{n} basis splines of order @math{k} are defined by
  31 @tex
  32 \beforedisplay
  33 $$
  34 B_{i,1}(x) = \left\{\matrix{1, & t_i \le x < t_{i+1}\cr
  35                             0, & else}\right.
  36 $$
  37 $$
  38 B_{i,k}(x) = \left[(x - t_i)/(t_{i+k-1} - t_i)\right] B_{i,k-1}(x) +
  39              \left[(t_{i+k} - x)/(t_{i+k} - t_{i+1})\right] B_{i+1,k-1}(x)
  40 $$
  41 \afterdisplay
  42 @end tex
  43 @ifinfo
  44
  45 @example
  46 B_(i,1)(x) = (1, t_i <= x < t_(i+1)
  47              (0, else
  48 B_(i,k)(x) = [(x - t_i)/(t_(i+k-1) - t_i)] B_(i,k-1)(x) + [(t_(i+k) - x)/(t_(i+k) - t_(i+1))] B_(i+1,k-1)(x)
  49 @end example
  50
  51 @end ifinfo
  52 for @math{i = 0, @dots{}, n-1}. The common case of cubic B-splines
  53 is given by @math{k = 4}. The above recurrence relation can be
  54 evaluated in a numerically stable way by the de Boor algorithm.
  55
  56 If we define appropriate knots on an interval @math{[a,b]} then
  57 the B-spline basis functions form a complete set on that interval.
  58 Therefore we can expand a smoothing function as
  59 @tex
  60 \beforedisplay
  61 $$
  62 f(x) = \sum_{i=0}^{n-1} c_i B_{i,k}(x)
  63 $$
  64 \afterdisplay
  65 @end tex
  66 @ifinfo
  67
  68 @example
  69 f(x) = \sum_i c_i B_(i,k)(x)
  70 @end example
  71
  72 @end ifinfo
  73 given enough @math{(x_j, f(x_j))} data pairs. The @math{c_i} can
  74 be readily obtained from a least-squares fit.
  75
  76 @node Initializing the B-splines solver
  77 @section Initializing the B-splines solver
  78 @cindex basis splines, initializing
  79
  80 @deftypefun {gsl_bspline_workspace *} gsl_bspline_alloc (const size_t @var{k}, const size_t @var{nbreak})
  81 This function allocates a workspace for computing B-splines of order
  82 @var{k}. The number of breakpoints is given by @var{nbreak}. This
  83 leads to @math{n = nbreak + k - 2} basis functions. Cubic B-splines
  84 are specified by @math{k = 4}. The size of the workspace is
  85 @math{O(5k + nbreak)}.
  86 @end deftypefun
  87
  88 @deftypefun void gsl_bspline_free (gsl_bspline_workspace * @var{w})
  89 This function frees the memory associated with the workspace @var{w}.
  90 @end deftypefun
  91
  92 @node Constructing the knots vector
  93 @section Constructing the knots vector
  94 @cindex knots
  95
  96 @deftypefun int gsl_bspline_knots (const gsl_vector * @var{breakpts}, gsl_bspline_workspace * @var{w})
  97 This function computes the knots associated with the given breakpoints
  98 and stores them internally in @code{w->knots}.
  99 @end deftypefun
 100
 101 @deftypefun int gsl_bspline_knots_uniform (const double a, const double b, gsl_bspline_workspace * @var{w})
 102 This function assumes uniformly spaced breakpoints on @math{[a,b]}
 103 and constructs the corresponding knot vector using the previously
 104 specified @var{nbreak} parameter. The knots are stored in
 105 @code{w->knots}.
 106 @end deftypefun
 107
 108 @node Evaluation of B-spline basis functions
 109 @section Evaluation of B-splines
 110 @cindex basis splines, evaluation
 111
 112 @deftypefun int gsl_bspline_eval (const double @var{x}, gsl_vector * @var{B}, gsl_bspline_workspace * @var{w})
 113 This function evaluates all B-spline basis functions at the position
 114 @var{x} and stores them in @var{B}, so that the @math{i}th element
 115 of @var{B} is @math{B_i(x)}. @var{B} must be of length
 116 @math{n = nbreak + k - 2}. This value may also be obtained by calling
 117 @code{gsl_bspline_ncoeffs}.
 118 It is far more efficient to compute all of the basis functions at
 119 once than to compute them individually, due to the nature of the
 120 defining recurrence relation.
 121 @end deftypefun
 122
 123 @deftypefun size_t gsl_bspline_ncoeffs (gsl_bspline_workspace * @var{w})
 124 This function returns the number of B-spline coefficients given by
 125 @math{n = nbreak + k - 2}.
 126 @end deftypefun
 127
 128 @node Example programs for B-splines
 129 @section Example programs for B-splines
 130 @cindex basis splines, examples
 131
 132 The following program computes a linear least squares fit to data using
 133 cubic B-spline basis functions with uniform breakpoints. The data is
 134 generated from the curve @math{y(x) = \cos{(x)} \exp{(-x/10)}} on
 135 @math{[0, 15]} with gaussian noise added.
 136
 137 @example
 138 @verbatiminclude examples/bspline.c
 139 @end example
 140
 141 The output can be plotted with @sc{gnu} @code{graph}.
 142
 143 @example
 144 $ ./a.out > bspline.dat
 145 chisq/dof = 1.118217e+00, Rsq = 0.989771
 146 $ graph -T ps -X x -Y y -x 0 15 -y -1 1.3 < bspline.dat > bspline.ps
 147 @end example
 148
 149 @iftex
 150 @sp 1
 151 @center @image{bspline,3.4in}
 152 @end iftex
 153
 154 @node References and Further Reading
 155 @section References and Further Reading
 156
 157 Further information on the algorithms described in this section can be
 158 found in the following book,
 159
 160 @itemize @asis
 161 C. de Boor, @cite{A Practical Guide to Splines} (1978), Springer-Verlag,
 162 ISBN 0-387-90356-9.
 163 @end itemize
 164
 165 @noindent
 166 A large collection of B-spline routines is available in the
 167 @sc{pppack} library available at @uref{http://www.netlib.org/pppack}.