
Go to the first, previous, next, last section, table of contents.
Series AccelerationThe functions described in this chapter accelerate the convergence of a series using the Levin utransform. 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 utransform works for both convergent and divergent series, including asymptotic series. These functions are declared in the header file `gsl_sum.h'. Acceleration functionsThe following functions compute the full Levin utransform 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 The calculation of the error in the extrapolated value is an 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 O(N) must be computed and stored, but this does give a reliable error estimate. .
Acceleration functions without error estimationThe functions described in this section compute the Levin utransform 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 O(N) process and only requires 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 converge properties at highspeed. 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.
Example of accelerating a seriesThe following code calculates an estimate of \zeta(2) = \pi^2 / 6 using the series, \zeta(2) = 1 + 1/2^2 + 1/3^2 + 1/4^2 + ... After N terms the error in the sum is O(1/N), making direct summation of the series converge slowly. #include <stdio.h> #include <gsl/gsl_math.h> #include <gsl/gsl_sum.h> #define N 20 int main (void) { double t[N]; double sum_accel, err; double sum = 0; int n; gsl_sum_levin_u_workspace * w = gsl_sum_levin_u_alloc (N); const double zeta_2 = M_PI * M_PI / 6.0; /* terms for zeta(2) = \sum_{n=1}^{\infty} 1/n^2 */ for (n = 0; n < N; n++) { double np1 = n + 1.0; t[n] = 1.0 / (np1 * np1); sum += t[n]; } gsl_sum_levin_u_accel (t, N, w, &sum_accel, &err); printf("termbyterm sum = % .16f using %d terms\n", sum, N); printf("termbyterm sum = % .16f using %d terms\n", w>sum_plain, w>terms_used); printf("exact value = % .16f\n", zeta_2); printf("accelerated sum = % .16f using %d terms\n", sum_accel, w>terms_used); printf("estimated error = % .16f\n", err); printf("actual error = % .16f\n", sum_accel  zeta_2); gsl_sum_levin_u_free (w); return 0; } The output below shows that the Levin utransform is able to obtain an estimate of the sum to 1 part in 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. bash$ ./a.out termbyterm sum = 1.5961632439130233 using 20 terms termbyterm sum = 1.5759958390005426 using 13 terms exact value = 1.6449340668482264 accelerated sum = 1.6449340668166479 using 13 terms estimated error = 0.0000000000508580 actual error = 0.0000000000315785 Note that a direct summation of this series would require 10^10 terms to achieve the same precision as the accelerated sum does in 13 terms. References and Further ReadingThe algorithms used by these functions are described in the following papers,
The theory of the utransform was presented by Levin,
A review paper on the Levin Transform is available online,
Go to the first, previous, next, last section, table of contents. 