1 files changed, 186 insertions, 0 deletions
diff --git a/gsl-1.9/doc/sum.texi b/gsl-1.9/doc/sum.texi
new file mode 100644
index 0000000..9b11675
--- /dev/null
+++ b/gsl-1.9/doc/sum.texi
@@ -0,0 +1,186 @@
+@cindex acceleration of series
+@cindex summation, acceleration
+@cindex series, acceleration
+@cindex u-transform for series
+@cindex Levin u-transform
+@cindex convergence, accelerating a series
+
+The functions described in this chapter accelerate the convergence of a
+series using the Levin @math{u}-transform.  This method takes a small number of
+terms from the start of a series and uses a systematic approximation to
+compute an extrapolated value and an estimate of its error.  The
+@math{u}-transform works for both convergent and divergent series, including
+asymptotic series.
+
+These functions are declared in the header file @file{gsl_sum.h}.
+
+@menu
+* Acceleration functions::      
+* Acceleration functions without error estimation::  
+* Example of accelerating a series::  
+* Series Acceleration References::  
+@end menu
+
+@node Acceleration functions
+@section Acceleration functions
+
+The following functions compute the full Levin @math{u}-transform of a series
+with its error estimate.  The error estimate is computed by propagating
+rounding errors from each term through to the final extrapolation. 
+
+These functions are intended for summing analytic series where each term
+is known to high accuracy, and the rounding errors are assumed to
+originate from finite precision. They are taken to be relative errors of
+order @code{GSL_DBL_EPSILON} for each term.
+
+The calculation of the error in the extrapolated value is an
+@math{O(N^2)} process, which is expensive in time and memory.  A faster
+but less reliable method which estimates the error from the convergence
+of the extrapolated value is described in the next section.  For the
+method described here a full table of intermediate values and
+derivatives through to @math{O(N)} must be computed and stored, but this
+does give a reliable error estimate.
+
+@deftypefun {gsl_sum_levin_u_workspace *} gsl_sum_levin_u_alloc (size_t @var{n})
+This function allocates a workspace for a Levin @math{u}-transform of @var{n}
+terms.  The size of the workspace is @math{O(2n^2 + 3n)}.
+@end deftypefun
+
+@deftypefun void gsl_sum_levin_u_free (gsl_sum_levin_u_workspace * @var{w})
+This function frees the memory associated with the workspace @var{w}.
+@end deftypefun
+
+@deftypefun int gsl_sum_levin_u_accel (const double * @var{array}, size_t @var{array_size}, gsl_sum_levin_u_workspace * @var{w}, double * @var{sum_accel}, double * @var{abserr})
+This function takes the terms of a series in @var{array} of size
+@var{array_size} and computes the extrapolated limit of the series using
+a Levin @math{u}-transform.  Additional working space must be provided in
+@var{w}.  The extrapolated sum is stored in @var{sum_accel}, with an
+estimate of the absolute error stored in @var{abserr}.  The actual
+term-by-term sum is returned in @code{w->sum_plain}. The algorithm
+calculates the truncation error (the difference between two successive
+extrapolations) and round-off error (propagated from the individual
+terms) to choose an optimal number of terms for the extrapolation.  
+All the terms of the series passed in through @var{array} should be non-zero.
+@end deftypefun
+
+
+@node Acceleration functions without error estimation
+@section Acceleration functions without error estimation
+
+The functions described in this section compute the Levin @math{u}-transform of
+series and attempt to estimate the error from the ``truncation error'' in
+the extrapolation, the difference between the final two approximations.
+Using this method avoids the need to compute an intermediate table of
+derivatives because the error is estimated from the behavior of the
+extrapolated value itself. Consequently this algorithm is an @math{O(N)}
+process and only requires @math{O(N)} terms of storage.  If the series
+converges sufficiently fast then this procedure can be acceptable.  It
+is appropriate to use this method when there is a need to compute many
+extrapolations of series with similar convergence properties at high-speed.
+For example, when numerically integrating a function defined by a
+parameterized series where the parameter varies only slightly. A
+reliable error estimate should be computed first using the full
+algorithm described above in order to verify the consistency of the
+results.
+
+@deftypefun {gsl_sum_levin_utrunc_workspace *} gsl_sum_levin_utrunc_alloc (size_t @var{n})
+This function allocates a workspace for a Levin @math{u}-transform of @var{n}
+terms, without error estimation.  The size of the workspace is
+@math{O(3n)}.
+@end deftypefun
+
+@deftypefun void gsl_sum_levin_utrunc_free (gsl_sum_levin_utrunc_workspace * @var{w})
+This function frees the memory associated with the workspace @var{w}.
+@end deftypefun
+
+@deftypefun int gsl_sum_levin_utrunc_accel (const double * @var{array}, size_t @var{array_size}, gsl_sum_levin_utrunc_workspace * @var{w}, double * @var{sum_accel}, double * @var{abserr_trunc})
+This function takes the terms of a series in @var{array} of size
+@var{array_size} and computes the extrapolated limit of the series using
+a Levin @math{u}-transform.  Additional working space must be provided in
+@var{w}.  The extrapolated sum is stored in @var{sum_accel}.  The actual
+term-by-term sum is returned in @code{w->sum_plain}. The algorithm
+terminates when the difference between two successive extrapolations
+reaches a minimum or is sufficiently small. The difference between these
+two values is used as estimate of the error and is stored in
+@var{abserr_trunc}.  To improve the reliability of the algorithm the
+extrapolated values are replaced by moving averages when calculating the
+truncation error, smoothing out any fluctuations.
+@end deftypefun
+
+
+@node Example of accelerating a series
+@section Examples
+
+The following code calculates an estimate of @math{\zeta(2) = \pi^2 / 6}
+using the series,
+@tex
+\beforedisplay
+$$
+\zeta(2) = 1 + 1/2^2 + 1/3^2 + 1/4^2 + \dots
+$$
+\afterdisplay
+@end tex
+@ifinfo
+
+@example
+\zeta(2) = 1 + 1/2^2 + 1/3^2 + 1/4^2 + ...
+@end example
+
+@end ifinfo
+@noindent
+After @var{N} terms the error in the sum is @math{O(1/N)}, making direct
+summation of the series converge slowly.
+
+@example
+@verbatiminclude examples/sum.c
+@end example
+
+@noindent
+The output below shows that the Levin @math{u}-transform is able to obtain an 
+estimate of the sum to 1 part in 
+@c{$10^{10}$}
+@math{10^10} using the first eleven terms of the series.  The
+error estimate returned by the function is also accurate, giving
+the correct number of significant digits. 
+
+@example
+$ ./a.out 
+@verbatiminclude examples/sum.out
+@end example
+
+@noindent
+Note that a direct summation of this series would require 
+@c{$10^{10}$}
+@math{10^10} terms to achieve the same precision as the accelerated 
+sum does in 13 terms.
+
+@node Series Acceleration References
+@section References and Further Reading
+
+The algorithms used by these functions are described in the following papers,
+
+@itemize @asis
+@item
+T. Fessler, W.F. Ford, D.A. Smith,
+@sc{hurry}: An acceleration algorithm for scalar sequences and series
+@cite{ACM Transactions on Mathematical Software}, 9(3):346--354, 1983.
+and Algorithm 602 9(3):355--357, 1983.
+@end itemize
+
+@noindent
+The theory of the @math{u}-transform was presented by Levin,
+
+@itemize @asis
+@item
+D. Levin,
+Development of Non-Linear Transformations for Improving Convergence of
+Sequences, @cite{Intern.@: J.@: Computer Math.} B3:371--388, 1973.
+@end itemize
+
+@noindent
+A review paper on the Levin Transform is available online,
+@itemize @asis
+@item
+Herbert H. H. Homeier, Scalar Levin-Type Sequence Transformations,
+@uref{http://arxiv.org/abs/math/0005209}.
+@end itemize