src/parsec/disk-image/parsec/parsec-benchmark/pkgs/libs/gsl/src/doc/cheb.texi - public/gem5-resources - Git at Google

 @cindex Chebyshev series
 @cindex fitting, using Chebyshev polynomials
 @cindex interpolation, using Chebyshev polynomials

 This chapter describes routines for computing Chebyshev approximations
 to univariate functions.  A Chebyshev approximation is a truncation of
 the series @math{f(x) = \sum c_n T_n(x)}, where the Chebyshev
 polynomials @math{T_n(x) = \cos(n \arccos x)} provide an orthogonal
 basis of polynomials on the interval @math{[-1,1]} with the weight
 function @c{$1 / \sqrt{1-x^2}$}
 @math{1 / \sqrt@{1-x^2@}}.  The first few Chebyshev polynomials are,
 @math{T_0(x) = 1}, @math{T_1(x) = x}, @math{T_2(x) = 2 x^2 - 1}.
 For further information see Abramowitz & Stegun, Chapter 22.

 The functions described in this chapter are declared in the header file
 @file{gsl_chebyshev.h}.

 @menu
 * Chebyshev Definitions::
 * Creation and Calculation of Chebyshev Series::
 * Chebyshev Series Evaluation::
 * Derivatives and Integrals::
 * Chebyshev Approximation examples::
 * Chebyshev Approximation References and Further Reading::
 @end menu

 @node Chebyshev Definitions
 @section Definitions

 A Chebyshev series  is stored using the following structure,

 @example
 typedef struct
 @{
   double * c;   /* coefficients  c[0] .. c[order] */
   int order;    /* order of expansion             */
   double a;     /* lower interval point           */
   double b;     /* upper interval point           */
   ...
 @} gsl_cheb_series
 @end example

 @noindent
 The approximation is made over the range @math{[a,b]} using
 @var{order}+1 terms, including the coefficient @math{c[0]}.  The series
 is computed using the following convention,
 @tex
 \beforedisplay
 $$
 f(x) = {c_0 \over 2} + \sum_{n=1} c_n T_n(x)
 $$
 \afterdisplay
 @end tex
 @ifinfo

 @example
 f(x) = (c_0 / 2) + \sum_@{n=1@} c_n T_n(x)
 @end example

 @end ifinfo
 @noindent
 which is needed when accessing the coefficients directly.

 @node Creation and Calculation of Chebyshev Series
 @section Creation and Calculation of Chebyshev Series

 @deftypefun {gsl_cheb_series *} gsl_cheb_alloc (const size_t @var{n})
 This function allocates space for a Chebyshev series of order @var{n}
 and returns a pointer to a new @code{gsl_cheb_series} struct.
 @end deftypefun

 @deftypefun void gsl_cheb_free (gsl_cheb_series * @var{cs})
 This function frees a previously allocated Chebyshev series @var{cs}.
 @end deftypefun

 @deftypefun int gsl_cheb_init (gsl_cheb_series * @var{cs}, const gsl_function * @var{f}, const double @var{a}, const double @var{b})
 This function computes the Chebyshev approximation @var{cs} for the
 function @var{f} over the range @math{(a,b)} to the previously specified
 order.  The computation of the Chebyshev approximation is an
 @math{O(n^2)} process, and requires @math{n} function evaluations.
 @end deftypefun

 @node Chebyshev Series Evaluation
 @section Chebyshev Series Evaluation

 @deftypefun double gsl_cheb_eval (const gsl_cheb_series * @var{cs}, double @var{x})
 This function evaluates the Chebyshev series @var{cs} at a given point @var{x}.
 @end deftypefun

 @deftypefun int gsl_cheb_eval_err (const gsl_cheb_series * @var{cs}, const double @var{x}, double * @var{result}, double * @var{abserr})
 This function computes the Chebyshev series @var{cs} at a given point
 @var{x}, estimating both the series @var{result} and its absolute error
 @var{abserr}.  The error estimate is made from the first neglected term
 in the series.
 @end deftypefun

 @deftypefun double gsl_cheb_eval_n (const gsl_cheb_series * @var{cs}, size_t @var{order}, double @var{x})
 This function evaluates the Chebyshev series @var{cs} at a given point
 @var{n}, to (at most) the given order @var{order}.
 @end deftypefun

 @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})
 This function evaluates a Chebyshev series @var{cs} at a given point
 @var{x}, estimating both the series @var{result} and its absolute error
 @var{abserr}, to (at most) the given order @var{order}.  The error
 estimate is made from the first neglected term in the series.
 @end deftypefun

 @comment @deftypefun double gsl_cheb_eval_mode (const gsl_cheb_series * @var{cs}, double @var{x}, gsl_mode_t @var{mode})
 @comment @end deftypefun

 @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})
 @comment Evaluate a Chebyshev series at a given point, using the default
 @comment order for double precision mode(s) and the single precision
 @comment order for other modes.
 @comment @end deftypefun


 @node Derivatives and Integrals
 @section Derivatives and Integrals

 The following functions allow a Chebyshev series to be differentiated or
 integrated, producing a new Chebyshev series.  Note that the error
 estimate produced by evaluating the derivative series will be
 underestimated due to the contribution of higher order terms being
 neglected.

 @deftypefun int gsl_cheb_calc_deriv (gsl_cheb_series * @var{deriv}, const gsl_cheb_series * @var{cs})
 This function computes the derivative of the series @var{cs}, storing
 the derivative coefficients in the previously allocated @var{deriv}.
 The two series @var{cs} and @var{deriv} must have been allocated with
 the same order.
 @end deftypefun

 @deftypefun int gsl_cheb_calc_integ (gsl_cheb_series * @var{integ}, const gsl_cheb_series * @var{cs})
 This function computes the integral of the series @var{cs}, storing the
 integral coefficients in the previously allocated @var{integ}.  The two
 series @var{cs} and @var{integ} must have been allocated with the same
 order.  The lower limit of the integration is taken to be the left hand
 end of the range @var{a}.
 @end deftypefun

 @node Chebyshev Approximation examples
 @section Examples

 The following example program computes Chebyshev approximations to a
 step function.  This is an extremely difficult approximation to make,
 due to the discontinuity, and was chosen as an example where
 approximation error is visible.  For smooth functions the Chebyshev
 approximation converges extremely rapidly and errors would not be
 visible.

 @example
 @verbatiminclude examples/cheb.c
 @end example

 @noindent
 The output from the program gives the original function, 10-th order
 approximation and 40-th order approximation, all sampled at intervals of
 0.001 in @math{x}.

 @iftex
 @sp 1
 @center @image{cheb,3.4in}
 @end iftex

 @node Chebyshev Approximation References and Further Reading
 @section References and Further Reading

 The following paper describes the use of Chebyshev series,

 @itemize @asis
 @item
 R. Broucke, ``Ten Subroutines for the Manipulation of Chebyshev Series
 [C1] (Algorithm 446)''. @cite{Communications of the ACM} 16(4), 254--256
 (1973)
 @end itemize
	@cindex Chebyshev series
	@cindex fitting, using Chebyshev polynomials
	@cindex interpolation, using Chebyshev polynomials

	This chapter describes routines for computing Chebyshev approximations
	to univariate functions. A Chebyshev approximation is a truncation of
	the series @math{f(x) = \sum c_n T_n(x)}, where the Chebyshev
	polynomials @math{T_n(x) = \cos(n \arccos x)} provide an orthogonal
	basis of polynomials on the interval @math{[-1,1]} with the weight
	function @c{$1 / \sqrt{1-x^2}$}
	@math{1 / \sqrt@{1-x^2@}}. The first few Chebyshev polynomials are,
	@math{T_0(x) = 1}, @math{T_1(x) = x}, @math{T_2(x) = 2 x^2 - 1}.
	For further information see Abramowitz & Stegun, Chapter 22.

	The functions described in this chapter are declared in the header file
	@file{gsl_chebyshev.h}.

	@menu
	* Chebyshev Definitions::
	* Creation and Calculation of Chebyshev Series::
	* Chebyshev Series Evaluation::
	* Derivatives and Integrals::
	* Chebyshev Approximation examples::
	* Chebyshev Approximation References and Further Reading::
	@end menu

	@node Chebyshev Definitions
	@section Definitions

	A Chebyshev series is stored using the following structure,

	@example
	typedef struct
	@{
	double * c; /* coefficients c[0] .. c[order] */
	int order; /* order of expansion */
	double a; /* lower interval point */
	double b; /* upper interval point */
	...
	@} gsl_cheb_series
	@end example

	@noindent
	The approximation is made over the range @math{[a,b]} using
	@var{order}+1 terms, including the coefficient @math{c[0]}. The series
	is computed using the following convention,
	@tex
	\beforedisplay
	$$
	f(x) = {c_0 \over 2} + \sum_{n=1} c_n T_n(x)
	$$
	\afterdisplay
	@end tex
	@ifinfo

	@example
	f(x) = (c_0 / 2) + \sum_@{n=1@} c_n T_n(x)
	@end example

	@end ifinfo
	@noindent
	which is needed when accessing the coefficients directly.

	@node Creation and Calculation of Chebyshev Series
	@section Creation and Calculation of Chebyshev Series

	@deftypefun {gsl_cheb_series *} gsl_cheb_alloc (const size_t @var{n})
	This function allocates space for a Chebyshev series of order @var{n}
	and returns a pointer to a new @code{gsl_cheb_series} struct.
	@end deftypefun

	@deftypefun void gsl_cheb_free (gsl_cheb_series * @var{cs})
	This function frees a previously allocated Chebyshev series @var{cs}.
	@end deftypefun

	@deftypefun int gsl_cheb_init (gsl_cheb_series * @var{cs}, const gsl_function * @var{f}, const double @var{a}, const double @var{b})
	This function computes the Chebyshev approximation @var{cs} for the
	function @var{f} over the range @math{(a,b)} to the previously specified
	order. The computation of the Chebyshev approximation is an
	@math{O(n^2)} process, and requires @math{n} function evaluations.
	@end deftypefun

	@node Chebyshev Series Evaluation
	@section Chebyshev Series Evaluation

	@deftypefun double gsl_cheb_eval (const gsl_cheb_series * @var{cs}, double @var{x})
	This function evaluates the Chebyshev series @var{cs} at a given point @var{x}.
	@end deftypefun

	@deftypefun int gsl_cheb_eval_err (const gsl_cheb_series * @var{cs}, const double @var{x}, double * @var{result}, double * @var{abserr})
	This function computes the Chebyshev series @var{cs} at a given point
	@var{x}, estimating both the series @var{result} and its absolute error
	@var{abserr}. The error estimate is made from the first neglected term
	in the series.
	@end deftypefun

	@deftypefun double gsl_cheb_eval_n (const gsl_cheb_series * @var{cs}, size_t @var{order}, double @var{x})
	This function evaluates the Chebyshev series @var{cs} at a given point
	@var{n}, to (at most) the given order @var{order}.
	@end deftypefun

	@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})
	This function evaluates a Chebyshev series @var{cs} at a given point
	@var{x}, estimating both the series @var{result} and its absolute error
	@var{abserr}, to (at most) the given order @var{order}. The error
	estimate is made from the first neglected term in the series.
	@end deftypefun

	@comment @deftypefun double gsl_cheb_eval_mode (const gsl_cheb_series * @var{cs}, double @var{x}, gsl_mode_t @var{mode})
	@comment @end deftypefun

	@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})
	@comment Evaluate a Chebyshev series at a given point, using the default
	@comment order for double precision mode(s) and the single precision
	@comment order for other modes.
	@comment @end deftypefun


	@node Derivatives and Integrals
	@section Derivatives and Integrals

	The following functions allow a Chebyshev series to be differentiated or
	integrated, producing a new Chebyshev series. Note that the error
	estimate produced by evaluating the derivative series will be
	underestimated due to the contribution of higher order terms being
	neglected.

	@deftypefun int gsl_cheb_calc_deriv (gsl_cheb_series * @var{deriv}, const gsl_cheb_series * @var{cs})
	This function computes the derivative of the series @var{cs}, storing
	the derivative coefficients in the previously allocated @var{deriv}.
	The two series @var{cs} and @var{deriv} must have been allocated with
	the same order.
	@end deftypefun

	@deftypefun int gsl_cheb_calc_integ (gsl_cheb_series * @var{integ}, const gsl_cheb_series * @var{cs})
	This function computes the integral of the series @var{cs}, storing the
	integral coefficients in the previously allocated @var{integ}. The two
	series @var{cs} and @var{integ} must have been allocated with the same
	order. The lower limit of the integration is taken to be the left hand
	end of the range @var{a}.
	@end deftypefun

	@node Chebyshev Approximation examples
	@section Examples

	The following example program computes Chebyshev approximations to a
	step function. This is an extremely difficult approximation to make,
	due to the discontinuity, and was chosen as an example where
	approximation error is visible. For smooth functions the Chebyshev
	approximation converges extremely rapidly and errors would not be
	visible.

	@example
	@verbatiminclude examples/cheb.c
	@end example

	@noindent
	The output from the program gives the original function, 10-th order
	approximation and 40-th order approximation, all sampled at intervals of
	0.001 in @math{x}.

	@iftex
	@sp 1
	@center @image{cheb,3.4in}
	@end iftex

	@node Chebyshev Approximation References and Further Reading
	@section References and Further Reading

	The following paper describes the use of Chebyshev series,

	@itemize @asis
	@item
	R. Broucke, ``Ten Subroutines for the Manipulation of Chebyshev Series
	[C1] (Algorithm 446)''. @cite{Communications of the ACM} 16(4), 254--256
	(1973)
	@end itemize