next up previous
Next: Model Sequences Up: OPEN PROBLEMS IN ASYMPTOTICS Previous: Introduction

The Construction of Sequence Transformations

The basic step in the construction of a sequence transformation is the assumption that the elements of the sequence to be transformed can for all indices be partitioned into a limit or antilimit s and a remainder according to

If a sequence satisfying this assumption converges, it is at least in principle possible to make the remainders negligible by increasing the index n as much as necessary. However, many sequences are known which converge so slowly that it is practically impossible to obtain sufficiently accurate approximations to their limits by increasing the index. Moreover, in the case of a divergent sequence, increasing n does not help at all since it normally only aggravates divergence.

As an alternative, one could try to improve the convergence of a sequence or to sum it in the case of divergence by computing sufficiently accurate approximations to the remainders , and to eliminate these approximations from the sequence elements.

The Euler-Maclaurin formula (see for instance section 13 of [8], section 8 of [36], or [37]) is an example for this approach: The remainder

 

of the partial sum (1.1) is replaced by an integral, for which asymptotic approximations as are derived. The resulting approximation to the remainder is then eliminated from the partial sum , yielding a better approximation to the limit s of the infinite series .

The major drawback of the Euler-Maclaurin formula is that it can only be applied if the terms of the series are known explicitly as functions of the index n, and if the resulting integral for the truncation error has a sufficiently simple structure to allow further manipulations. Consequently, it cannot be applied if only the numerical values of the terms of a series are known.

Sequence transformations also try to compute approximations to the remainders and to eliminate them from the sequence elements. However, they differ from the Euler-Maclaurin formula in one very essential respect: They require only relatively little knowledge about the n-dependence of the remainders of the sequence to be transformed. Consequently, they can be applied in situations in which apart from the numerical values of the sequence elements only comparatively little is known.

Since the Euler-Maclaurin formula utilizes a lot of information, it should in those cases, in which it can be applied, give better results than sequence transformations, which utilize much less information. This is a price which has to be paid for the fact that sequence transformations are much more general numerical tools which can be applied to a very wide range of problemsgif.

Normally, sequence transformations eliminate only approximations of the remainders. Thus, the elements of the transformed sequence can also be partitioned into the limit or antilimit s and a transformed remainder according to

The transformed remainders will in general be different from zero for all finite values of n. However, convergence is accelerated if the transformed remainders vanish more rapidly than the original remainders as according to

and a divergent sequence is summed if the transformed remainders vanish at all as .

As mentioned above, a sequence transformation tries to obtain a better approximation to the limit or antilimit s by eliminating as effectively as possible from . Of course, this is easier said than done. The remainders of a sequence are in general unknown, and their determination is normally not easier than the determination of the limit or antilimit s of this sequence.

Accordingly, the exact remainders are normally either unknown or not easily accessible, and a straightforward elimination is not possible. Nevertheless, at least some structural and asymptotic information about the dependence of the remainders on the index n is often available.

First, I will try to clarify by means of some simple examples the term structural and asymptotic information. As the most simple example, let us consider the geometric series. Its truncation error is given by

Another example is the Euler integral

 

and its associated asymptotic series, the Euler series

 

which diverges quite strongly for every . It can be shown that the truncation error of the Euler series satisfies (see for instance Theorem 13-1 of [23])

For , the integral on the right-hand side is positive and bounded in magnitude by the first term not included in the partial sum:

Thus, for the truncation error of both the geometric series and the Euler series possesses the same sign as the first term not included in the partial sum, and is bounded in magnitude by this term. As is well known, the first term not included in the partial sum is a simple estimate for the truncation error of a convergent series with strictly alternating terms (see p. 259 of [1]). Moreover, it is also the best simple estimate for the truncation error of a strictly alternating nonterminating hypergeometric series with , which diverges quite strongly for every (see Theorem 5.12-5 of [35]).

It will be shown later that powerful sequence transformations can be constructed on the basis of the assumption that the truncation error of the infinite series can be estimated by the first term not included in the partial sum.

The truncation error of the series for the Riemann zeta function, which is notorious for its bad convergence, satisfies (see p. 20 of [12])

 

where

   

Here, is a Bernoulli number. This representation of the truncation error can be obtained from the Euler-Maclaurin formula (compare example 3.2 on p. 292 of [36]).

In the case of the Riemann zeta function, the first term not included in the partial sum would not be suited as an estimate for the truncation error. However, the first term not included in the partial sum multiplied by would be a simple estimate for the truncation error (2.10) (see p. 382 of [38]).

Structural and asymptotic information on the n-dependence of the truncation errors, which need not be very detailed, can be used for the construction of sequence transformations. Since it would be futile to try to eliminate a remainder with a completely unknown and arbitrary n-dependence, a sequence transformation has to make either implicitly or explicitly some assumptions.

As a consequence, a sequence transformation will only work well if the actual behavior of the remainders is in sufficiently close agreement with the assumptions made.

Of course, this also implies that a sequence transformation, which makes specific and detailed assumptions about the remainders, may fail to accelerate convergence or to produce a convergent result in the case of divergence, if it is applied to a sequence with remainders of a sufficiently different behavior.

Thus, the efficiency of a sequence transformation for certain types of sequences and its inefficiency or even nonregularity in the case of other sequences are intimately related.



next up previous
Next: Model Sequences Up: OPEN PROBLEMS IN ASYMPTOTICS Previous: Introduction



Rob Corless
Wed Sep 13 12:04:01 PDT 1995