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

   1 @cindex Chebyshev series
   2 @cindex fitting, using Chebyshev polynomials
   3 @cindex interpolation, using Chebyshev polynomials
   4
   5 This chapter describes routines for computing Chebyshev approximations
   6 to univariate functions.  A Chebyshev approximation is a truncation of
   7 the series @math{f(x) = \sum c_n T_n(x)}, where the Chebyshev
   8 polynomials @math{T_n(x) = \cos(n \arccos x)} provide an orthogonal
   9 basis of polynomials on the interval @math{[-1,1]} with the weight
  10 function @c{$1 / \sqrt{1-x^2}$}
  11 @math{1 / \sqrt@{1-x^2@}}.  The first few Chebyshev polynomials are,
  12 @math{T_0(x) = 1}, @math{T_1(x) = x}, @math{T_2(x) = 2 x^2 - 1}.
  13 For further information see Abramowitz & Stegun, Chapter 22.
  14
  15 The functions described in this chapter are declared in the header file
  16 @file{gsl_chebyshev.h}.
  17
  18 @menu
  19 * Chebyshev Definitions::
  20 * Creation and Calculation of Chebyshev Series::
  21 * Chebyshev Series Evaluation::
  22 * Derivatives and Integrals::
  23 * Chebyshev Approximation examples::
  24 * Chebyshev Approximation References and Further Reading::
  25 @end menu
  26
  27 @node Chebyshev Definitions
  28 @section Definitions
  29
  30 A Chebyshev series  is stored using the following structure,
  31
  32 @example
  33 typedef struct
  34 @{
  35   double * c;   /* coefficients  c[0] .. c[order] */
  36   int order;    /* order of expansion             */
  37   double a;     /* lower interval point           */
  38   double b;     /* upper interval point           */
  39   ...
  40 @} gsl_cheb_series
  41 @end example
  42
  43 @noindent
  44 The approximation is made over the range @math{[a,b]} using
  45 @var{order}+1 terms, including the coefficient @math{c[0]}.  The series
  46 is computed using the following convention,
  47 @tex
  48 \beforedisplay
  49 $$
  50 f(x) = {c_0 \over 2} + \sum_{n=1} c_n T_n(x)
  51 $$
  52 \afterdisplay
  53 @end tex
  54 @ifinfo
  55
  56 @example
  57 f(x) = (c_0 / 2) + \sum_@{n=1@} c_n T_n(x)
  58 @end example
  59
  60 @end ifinfo
  61 @noindent
  62 which is needed when accessing the coefficients directly.
  63
  64 @node Creation and Calculation of Chebyshev Series
  65 @section Creation and Calculation of Chebyshev Series
  66
  67 @deftypefun {gsl_cheb_series *} gsl_cheb_alloc (const size_t @var{n})
  68 This function allocates space for a Chebyshev series of order @var{n}
  69 and returns a pointer to a new @code{gsl_cheb_series} struct.
  70 @end deftypefun
  71
  72 @deftypefun void gsl_cheb_free (gsl_cheb_series * @var{cs})
  73 This function frees a previously allocated Chebyshev series @var{cs}.
  74 @end deftypefun
  75
  76 @deftypefun int gsl_cheb_init (gsl_cheb_series * @var{cs}, const gsl_function * @var{f}, const double @var{a}, const double @var{b})
  77 This function computes the Chebyshev approximation @var{cs} for the
  78 function @var{f} over the range @math{(a,b)} to the previously specified
  79 order.  The computation of the Chebyshev approximation is an
  80 @math{O(n^2)} process, and requires @math{n} function evaluations.
  81 @end deftypefun
  82
  83 @node Chebyshev Series Evaluation
  84 @section Chebyshev Series Evaluation
  85
  86 @deftypefun double gsl_cheb_eval (const gsl_cheb_series * @var{cs}, double @var{x})
  87 This function evaluates the Chebyshev series @var{cs} at a given point @var{x}.
  88 @end deftypefun
  89
  90 @deftypefun int gsl_cheb_eval_err (const gsl_cheb_series * @var{cs}, const double @var{x}, double * @var{result}, double * @var{abserr})
  91 This function computes the Chebyshev series @var{cs} at a given point
  92 @var{x}, estimating both the series @var{result} and its absolute error
  93 @var{abserr}.  The error estimate is made from the first neglected term
  94 in the series.
  95 @end deftypefun
  96
  97 @deftypefun double gsl_cheb_eval_n (const gsl_cheb_series * @var{cs}, size_t @var{order}, double @var{x})
  98 This function evaluates the Chebyshev series @var{cs} at a given point
  99 @var{n}, to (at most) the given order @var{order}.
 100 @end deftypefun
 101
 102 @deftypefun int gsl_cheb_eval_n_err (const gsl_cheb_series * @var{cs}, const size_t @var{order}, const double @var{x}, double * @var{result}, double * @var{abserr})
 103 This function evaluates a Chebyshev series @var{cs} at a given point
 104 @var{x}, estimating both the series @var{result} and its absolute error
 105 @var{abserr}, to (at most) the given order @var{order}.  The error
 106 estimate is made from the first neglected term in the series.
 107 @end deftypefun
 108
 109 @comment @deftypefun double gsl_cheb_eval_mode (const gsl_cheb_series * @var{cs}, double @var{x}, gsl_mode_t @var{mode})
 110 @comment @end deftypefun
 111
 112 @comment @deftypefun int gsl_cheb_eval_mode_err (const gsl_cheb_series * @var{cs}, const double @var{x}, gsl_mode_t @var{mode}, double * @var{result}, double * @var{abserr})
 113 @comment Evaluate a Chebyshev series at a given point, using the default
 114 @comment order for double precision mode(s) and the single precision
 115 @comment order for other modes.
 116 @comment @end deftypefun
 117
 118
 119 @node Derivatives and Integrals
 120 @section Derivatives and Integrals
 121
 122 The following functions allow a Chebyshev series to be differentiated or
 123 integrated, producing a new Chebyshev series.  Note that the error
 124 estimate produced by evaluating the derivative series will be
 125 underestimated due to the contribution of higher order terms being
 126 neglected.
 127
 128 @deftypefun int gsl_cheb_calc_deriv (gsl_cheb_series * @var{deriv}, const gsl_cheb_series * @var{cs})
 129 This function computes the derivative of the series @var{cs}, storing
 130 the derivative coefficients in the previously allocated @var{deriv}.
 131 The two series @var{cs} and @var{deriv} must have been allocated with
 132 the same order.
 133 @end deftypefun
 134
 135 @deftypefun int gsl_cheb_calc_integ (gsl_cheb_series * @var{integ}, const gsl_cheb_series * @var{cs})
 136 This function computes the integral of the series @var{cs}, storing the
 137 integral coefficients in the previously allocated @var{integ}.  The two
 138 series @var{cs} and @var{integ} must have been allocated with the same
 139 order.  The lower limit of the integration is taken to be the left hand
 140 end of the range @var{a}.
 141 @end deftypefun
 142
 143 @node Chebyshev Approximation examples
 144 @section Examples
 145
 146 The following example program computes Chebyshev approximations to a
 147 step function.  This is an extremely difficult approximation to make,
 148 due to the discontinuity, and was chosen as an example where
 149 approximation error is visible.  For smooth functions the Chebyshev
 150 approximation converges extremely rapidly and errors would not be
 151 visible.
 152
 153 @example
 154 @verbatiminclude examples/cheb.c
 155 @end example
 156
 157 @noindent
 158 The output from the program gives the original function, 10-th order
 159 approximation and 40-th order approximation, all sampled at intervals of
 160 0.001 in @math{x}.
 161
 162 @iftex
 163 @sp 1
 164 @center @image{cheb,3.4in}
 165 @end iftex
 166
 167 @node Chebyshev Approximation References and Further Reading
 168 @section References and Further Reading
 169
 170 The following paper describes the use of Chebyshev series,
 171
 172 @itemize @asis
 173 @item
 174 R. Broucke, ``Ten Subroutines for the Manipulation of Chebyshev Series
 175 [C1] (Algorithm 446)''. @cite{Communications of the ACM} 16(4), 254--256
 176 (1973)
 177 @end itemize