**THE
PERFORMANCE OF THE EPSILON AND THETA CONVERGENCE ACCELERATION ALGORITHMS**

A Paper

Submitted to the Graduate Faculty

of the

North Dakota State University

of Agriculture and Applied Science

By

Paul Scott Heidmann

In Partial Fulfillment of the Requirements

for the Degree of

MASTER OF SCIENCE

Major Department:

Mathematics

August 1992

Fargo, North Dakota

THE PERFORMANCE OF THE EPSILON AND THETA CONVERGENCE ACCELERATION ALGORITHMS

By

Paul Scott Heidmann

The Supervisory Committee certifies that this paper complies with North Dakota State University's regulations and meets the accepted standards for the degree of

MASTER OF SCIENCE

SUPERVISORY COMMITTEE:

___________________________________________________________________

Chair

___________________________________________________________________

___________________________________________________________________

___________________________________________________________________

Approved by Department Chair:

___________________ __________________________________

Date Signiture

Heidmann, Paul Scott, M.S., Department of Mathematics, College of Science and Mathematics, North Dakota State University, August 1992. The Performance of the Epsilon and Theta Convergence Acceleration Algorithms. Major Advisor: Associate Professor Davis Cope.

Motivations
for transforms are first presented, along with the derivation of both the _{}-algorithm and the _{}-algorithm. Known
properties are then presented, with a partial classification of the sets for
which the transforms are known to have accelerative properties.

Empirical
evidence is given illustrating the performance of the algorithms over a broad
set of test series. The _{}-algorithm was found to perform better than the _{}-algorithm on all but a few of the test cases
considered. No algorithm considered
demonstrated any evidence of producing an increase in the exponential rate of
convergence. No evidence of instability
was seen among the algorithms considered.

Abstract................................................................................................................................ iii

Section 1: Introduction........................................................................................................... 1

Section 2: Transform Motivations and Properties.................................................................... 4

The Motivation of the e Transform................................................................. 4

Properties of the e Transform......................................................................... 7

The e Transform and the -Algorithm........................................................... 10

The Motivation of the q Transform............................................................... 13

Properties of the q Transform....................................................................... 14

Section 3: Empirical and Related Results.............................................................................. 16

Details of the Test Program.......................................................................... 17

Details of Test Procedures........................................................................... 17

Transform Singularities................................................................................. 18

Empirical Results......................................................................................... 23

Group 1.......................................................................................... 23

Group 2.......................................................................................... 77

Group 3.......................................................................................... 80

Group 4.......................................................................................... 95

Group 5........................................................................................ 101

Group 6........................................................................................ 115

Group 7.....................................................................................117

Section 4: Summary........................................................................................................... 126

Bibliography...................................................................................................................... 127

This paper is concerned with the evaluation of the performance of the -algorithm and the -algorithm when applied to sequences of partial sums. Transform definitions and properties are first stated, followed by empirical examples illustrating the comparative performance of the algorithms on a wide variety of test problems.

The two transforms covered in this paper are recursive and operate on the set of complex valued nonconstant sequences. For broad classes of sequences, these algorithms are known to have accelerative properties.

Both algorithms are actually more accurately described as a hierarchy of transforms. That is, the algorithms provide a succession of transforms, with the higher order transforms typically providing greater rates of acceleration.

The
first of these algorithms, the -algorithm, is defined as
follows for any nonconstant sequence _{} [6, p. 225]:

_{}

_{}.

The
second algorithm considered in this paper is the -algorithm, defined as follows
for any nonconstant sequence _{} [6, p. 225]:

_{}

_{}

_{}

In most practical applications, a transform must have the properties of regularity and of convergence acceleration. This paper was concerned more with the latter than the former; however, both definitions will be required.

Definition: A transform *T* is said to be *regular*
for a convergent sequence *s _{n}*
if

_{}

Definition: A transform *T* is said to *accelerate*
the convergence of a sequence *s _{n}*
if

_{}

where *s* is the limit of the sequence *s _{n}*.

Intuitively, a transform accelerates the convergence of a sequence if the convergence of the transformed sequence is of higher order than that of the original sequence. Equivalently, a transform accelerates the convergence of a sequence if the error term of the transformed sequence asymptotically goes to zero with a higher order than the error term of the original sequence.

Section 2 of this paper summarizes the known properties of the transforms. The transforms are first motivated, and then theorems concerning each are presented.

Section 3 presents two new lemmas and presents the empirical research done in connection with this paper.

Section 4 summarizes the results reached in Section 3.

Transform Motivations and Properties

The history
of the e transform is not altogether clear.
The general ideas which underlie this transform go at least as far back
as Jacobi. A special case of the *e* transform known as the _{}-process is usually attributed to Aitkin; however, this
technique can be traced back to Kummer (1837) [8, p. 120]. Apparently, it was developed independently by
several authors (although not always in its most general form): Delaunay, Samuelson, Shanks and Walton,
Hartee, and Isakson [5, p. 5].

The *e* transform has been motivated by two
distinct but similar sets of ideas.
Both begin with the recognition that many sequences in applied
mathematics and physics can be approximated by a limit together with
exponential transients:

_{}.

Here, it is assumed that none of the _{}'s are zero or one (if a transient were one, it would become
part of the limit *s*) and that the _{}'s are distinct. The
elemental idea is to develop a transform which will eliminate these exponential
transients.

The first
method of accomplishing this task was given by Shanks [5, p. 7-8] and is
summarized below. Observe that any
nonsingular sequence (definition follows) can be expressed as a *k*th order transient locally. Fix any *n*
larger than *k* and represent _{} as follows:

_{},

where the _{}'s are the respective limits, called the "*kth order local bases.*" Should one of the _{}, then the sequence will be singular.^{[1]} These bases will vary relatively little as
long as * _{}* is nearly

The
motivation for the *e* transform given
by Wimp [8, p. 121-123] also begins with the recognition that many sequences
from applied mathematics and physics behave as if they were a limit combined
with exponential transients. As above,
the *e* transform is then developed to
eliminate these transients; the technique by which the transform is developed,
however, differs significantly.

To begin
(as above), assume the sequence _{} has the form:

_{}.

To simplify notation, let:

_{}.

Since _{} is a linear
combination of *k* exponentials, there
is a linear difference operator of order *k*
that annihilates _{}:

_{} (_{} *not zero).*

Now, rewrite _{} as follows:

_{}.

Next, substitute into the difference equation, and solve for
_{}.^{[2]} Redefining constants gives:

_{}.

This is a homogeneous system of equations with a nonzero
solution _{}. Such a solution
will exist if and only if the following determinental equation is satisfied:

_{}.

For simplicity, define:

_{}.

Then, solving for s gives [8, p. 122]:

_{}.

While the above equation will only be valid for sequences
that can be represented as a combination of a limit and exponential transients,
it can nevertheless be used to define a transform useful for a much larger
class of sequences, which is written _{}.

While these two derivations are quite different, they are indeed equivalent [5, p. 2-3,7-8].

At this point, several questions naturally arise. Questions concerning the regularity of the transform, the accelerative properties, and optimality are especially significant. This section presents known results that address these questions.

The first
question that must be answered before the *e*
transform can be used in any application is whether or not the transform will
be regular for the sequences involved.
For many applications, this question will not be difficult to answer, as
the *e* transform can be shown to be
regular on broad classes of sequences.

The following theorem (accredited originally to Lubkin) is stated by Shanks [5, p. 13]:

Theorem: If _{} and _{}* *both converge, then

_{}.

Further regularity results are available for this transform
and are discussed in the _{}-algorithm section.

Closely
related to the question of regularity is the question of exactness. That is, for what class of sequences will
the *e* transform be exact (produce the
limit of the sequence in a finite number of steps)? This question is answered in part by the following theorem, given
by Shanks [5, p. 22]:

Theorem: Let *f(z)*
be a rational function, which when reduced to its lowest terms has a *q'*th degree numerator and a *p'*th degree denominator; then, if _{}

_{},

where _{} is the first *n* terms of the Taylor expansion for *f*.

* *

In fact, a closely related but stronger theorem has been given by Wimp [8, p. 125]:

Theorem: * _{}* is defined for
all

Finally,
questions of optimality and accelerative properties must be addressed. Here, while fewer results are known, it is
still possible to partially characterize sequences for which *e* is accelerative. A definition along with two helpful theorems
are stated:

Definition: Let _{} be the terms of a
convergent series with partial sums * _{}* and sum

The following two theorems are very useful for determining
whether or not the condition _{} is satisfied:

Theorem: If _{} is of constant sign,
then _{} [3, p. 26].

Theorem: If _{} with _{} and if *r* is not -1, then _{} [3, p. 26].

Wimp has
shown [8, p. 104] that _{} will accelerate all
linearly convergent series. More
interesting, however, are the results produced by Delahaye. Three basic results concerning the
optimality of the _{} transform (Aitkin's _{} process) on the
family of linearly convergent series are presented [4, p. 213]:

1. The _{} transform is
algebraically optimal; that is, it is not possible to find an algebraically
simpler transform to accelerate the family of linearly convergent series.

2. It is impossible to accelerate the linear
family with degree^{[3]}
greater than 1, the degree of acceleration achieved with the _{} transform.

3. The linear family cannot be enlarged into
another accelerable family. That is,
there does not exist a family of sequences containing the linear family for
which _{} can be shown to have
the above properties.

Delahaye then interprets these facts [4, p. 213]:

These results do not mean that the _{} is the best algorithm
of acceleration. They only mean that
concerning the family Lin, it is impossible to find a simpler or a more
efficient algorithm of acceleration.
This does not contradict the existence of subfamilies of Lin accelerable
with degree 2, nor does it contradict the existence of algorithms less simple
but equally efficient on Lin.

When first
developed, the *e* transform was merely
a curiosity. It had little practical
value, as calculating the large order determinants inherent to the transform
was computationally prohibitive. This changed
in 1956 when Wynn produced the following theorem [9, p. 91]:

Theorem: If

_{}

and

_{},

then

_{}

provided that none of the quantities _{} becomes infinite.

With this algorithm, it is now possible to compute the *e* transform easily and efficiently. Study of the -algorithm has also
facilitated much knowledge of the *e*
transform.

One such result is due to Wimp. However, before stating this result, two definitions are required :

Definition: A sequence **s** is totally monotone (written _{}) if

_{}.

Definition: A sequence **s** is totally oscillatory (written _{}) if

_{} [8, p. 12].

Theorem: Let the sequence ** s** have remainder terms

While the
algorithm is regular for large classes of sequences, this is not the only
concern. Computing the transform involves
repeated divisions by what can be very small quantities. This seems to suggest that the transforms
will be prone to numerical instability.
However, the empirical results presented in this paper suggest that the _{}-algorithm is far more stable than appears at first.

Theoretical
analysis of the stability of the _{}-algorithm has not yet been fully developed. However, Wynn has presented a paper that
begins to deal with this issue [10].
The results presented suggest that the _{}-algorithm can be unstable for certain monotonic sequences
[10, p. 110-112] and unconditionally stable for certain oscillating sequences
[10, p. 112-115]. These theoretical
results can be seen intuitively, simply by examining the transform. Oscillating sequences have adjacent terms
opposite in sign. This tends to make
the denominator in the defining recurrence relation larger. Monotonic sequences have terms of like sign,
which in turn tends to make the denominator smaller.

Finally,
the _{}-algorithm can be shown to be closely related to the Padé
table. The Padé table for an analytic
function *f* is a two dimensional table
of rational approximations of *f*. The [L,M] entry of the Padé table is
typically denoted [L/M] and is defined as follows [1, p. 5]:

_{},

where **_{}** is a polynomial of
degree at most

The _{}-algorithm produces certain entries in the Padé table. The following theorem then is due to Wynn
[10, p. 93]:

Theorem: If the _{}-algorithm is applied to the initial values

_{},

then

_{}.

The transform was developed by Brezinski as a means of accelerating the convergence of logarithmically converging sequences. Its motivation began with the observation that the algorithm fails to accelerate convergence on large classes of logarithmically converging sequences. However, rather than developing a completely new transform, Brezinski opted to modify the algorithm, adding an optimizing parameter.

Define _{}. Then it is known
that a set of sequences with logarithmic convergence having the property

_{}

may be accelerated by the algorithm modified with a "parameter of acceleration" [2, p. 727], specifically, with the following transform:

_{}

_{}

_{}^{[4]}

A necessary and sufficient condition for _{} to converge faster
than _{} is to take

_{}

However, calculating all of the _{} parameters can be
prohibitive. It was at this point that
Brezinski took his departure from what was then known. His idea was to replace _{} with the following
approximation [2, p. 729]:

_{}

The transform then results.

A property important in the application of any transform is regularity. Brezinski has characterized this property with the following theorem [2, p. 730]:

Theorem: For real valued sequences, a necessary and sufficient condition for

_{}

is that

_{}

As to the transform's accelerative properties, two theorems are given here. The first, and less general theorem, results from Germain-Bonne's theorem and is given by Smith and Ford [6, p. 225]:

Theorem: _{} accelerates linear
convergence.

The second theorem, due to Brezinski [2, p. 730], is much farther reaching:

Theorem: If is regular and if _{} exists and is finite,
then _{} converges faster than
_{}.

Finally,
the question of exactness is addressed by a theorem due to Cordellier and
stated by Smith and Ford [6, p. 229].
It should be noted that this theorem characterizes only those sequences
for which _{} is exact in one term.

Theorem: _{} for _{} if and only if the
sequence _{} is one of the
following three types:

1. _{} *where *_{}

2. _{} *where _{} and neither _{} is a positive
integer.*

3. _{} and d is not a positive integer.

Empirical and Related Results

This
section describes the empirical research done in connection with this
paper. Many series^{[5]}
were computed, and the transforms were applied to the sequences of their
partial sums. The error terms for the
sequences of partial sums, as well as the transformed sequences, were
plotted. This allowed observations to
be made concerning acceleration rates, stability, and unusual behavior (where
it occurred).

Special software was constructed as arbitrary precision proved to be necessary. The high amount of precision was required for different reasons. Many of the transforms achieved upwards of 35 places of precision in only 30 terms. Other series were chosen to be very close to singular values for the transforms. Also, the high precision allowed elimination of numerical problems, so the properties of the transforms could be easily studied.

This section describes the program used to perform the calculations involved in constructing the many examples presented in this paper.

As many precision problems can arise during the calculation of these transforms, arbitrary precision was necessary for the observation of the behavior of the transforms considered in this paper.

The storage of arbitrary length numbers was accomplished using linked lists. Specifically, the numbers were stored as linked lists of bytes, each byte containing two digits. Also, since the transforms operate on sequences, it was necessary to store sequences of these arbitrarily long numbers. This was accomplished in a similar manner, using linked lists. Finally, subroutines were added to perform arithmetic functions and transforms on these arbitrarily long sequences of arbitrarily long numbers.

Following are several graphs illustrating the results of the empirical research done. All graphs are plots of the log (base 10) of the absolute value of the error. This configuration allows the approximate number of digits accurately calculated to be viewed at a glance.

The graphs contain two types of information. First, there is the size of the error term for each of the series and their transforms. Secondly, the rate of exponential acceleration can be seen in the slope of the corresponding line.

The actual value that any series under consideration converges to must be known. For those series which proved to have a reasonable rate of convergence, this limit was computed simply by summing the series out to several hundred terms before the transforms were computed. For those series with slower rates of convergence, Kummer acceleration was used to arrive at the limit. Several series had to be eliminated from the test set because their limit could not be computed.

Many
of the series contained a term _{}. Where it was found,
this modifier was defined as follows:

_{}.

The * _{}'s* provided a nonrational factor that did not change the
value of

In this section, two lemmas are given that demonstrate that it is possible for the transforms to have singularities. Two illustrations are also be given to demonstrate the behavior of the transforms near a singularity.

Lemma:
Apply the _{}-algorithm to the sequence _{}. Then, _{} is undefined if _{}.

Proof: From the defining equations,

_{}.

However, since _{} is a sequence of
partial sums,

_{}

Combining the above,

_{}.

This will be
undefined whenever _{}.

Remarks:

1. If the
sequence in question is a power series of the form _{}, then _{} will be undefined at _{}.

2. This result
may be generalized to an arbitrary sequence _{}. The *n ^{th}* term of

The
following graph illustrates the above lemma.
The numeric value used here was chosen to be very near to the value that
would cause _{} to be undefined. As can easily be seen, this sort of behavior
cannot be ignored in practical applications of this algorithm.

_{}

Analogously, a similiar lemma can be proven for the algorithm:

Lemma:
Apply the _{}-algorithm to the sequence _{}. Then, _{} is undefined if _{}.

Proof: From the defining equations,

_{}.

This will be
undefined when _{}.

_{}

Remarks:

1. If the
sequence of partial sums is a power series of the form _{}, then _{} is undefined at _{}.

2. This result
may be generalized to an arbitrary sequence _{}. In this case, _{} is undefined if _{} where _{}.

The following chart illustrates the
above lemma. The numeric value used
here was chosen to be very close to the value that would make _{} undefined. As before, this behavior cannot be ignored
if the algorithm is to be used in practice.

_{}

Other examples of how these singularities affect the behavior of the transforms have been computed, but they are not included here as the behavior is the same in all examples considered.

This
set consists of those series for which the following order of performance can
be clearly seen (from best to worst): _{}. This is by far the
largest group, suggesting that the _{}-algorithm generally outperforms the _{}-algorithm.

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

The anomoly in this graph is due to
the fact that _{} is nearly undefined
(as discussed at the end of Section 3).

_{}

Note: Calculations made with 50 places of precision.

_{}

Note: Calculations made with 50 places of precision.

_{}

Note: Calculations made with 50 places of precision.

_{}

_{}

_{}

_{}

_{}

Note : The graphs of the transforms of this function have a significantly larger slope than the original series. This indicates a change in the exponential rate of convergence.

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

**Group 2**

This
group contains series for which _{} is exact. These series can all be shown to be a
combination of a limit and two exponential transients. Notice that, for all of these series, the
order of performance (from best to worst) is _{}.

_{}

_{}

This
group contains series for which _{} eventually
outperforms _{}, but otherwise the results are unclear. All series in this group contain the
nonrational modifier _{}.

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

This
group contains the series for which the following order of performance is
observed (from best to worst): _{}. For all but the
first series in this group, the _{}-algorithm will eventually be exact.

_{}

_{}

This sequence can
be shown to be a combination of its limit and three exponential
transients. The epsilon algorithm will
then be exact by the sixth iteration.
Notice here that the epsilon algorithm outperforms the theta
algorithm. This is due to the fact that
this is exactly the type of sequence that the *e* transform was designed to accelerate.

_{}

This and the next
three series are included to demonstrate the effect of singularities on the
transforms. All terms of both the _{}-algorithm and the _{}-algorithm are undefined at *1*. The inclusion of the
successive terms *0.9, 0.99, * and *0.999*
illustrates the continuing degradation of the algorithms as the singularities
are approached.

_{}

_{}

This
group of series bears the following peculiar attribute: only _{} achieves any
acceleration.

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

Note: For the above function, _{} does not exist, but _{}.

_{}

_{}

Note: For this series, _{}, but _{} does not exist.

This group consists of a single
series which none of the algorithms considered accelerated.

_{}

Note: For this series, _{}, but _{}.

For
this group of series, the following order of performance is observed (from best
to worst): _{}.

_{}

_{}

_{}

_{}

_{}

_{}

_{}

_{}

Summary

Several conclusions have been reached in this paper; this section summarizes these results. The two lemmas presented in Section 3 are worthy of special mention here. In any practical application of the algorithms addressed in this paper, it is critical to be aware of any anomalies that might occur. The graphs associated with the lemmas illustrated the profound effect a singularity can have on a transform.

In
the series considered, _{} outperformed _{} except for a few
cases.

There
did not appear to be a change in the exponential rate of convergence between _{} and _{} unless otherwise
noted.

No evidence of numeric instability was observed in any of the transforms considered (only in the case where a transform was nearly undefined could any instability be seen).

[1] Baker, George A., Jr.

*Essentials of Padé Approximants*

Academic Press, New York, 1975

[2] Brezinski, Claude.

*Acceleration de suites a convergence
logarithmique.*

C. R. Acad. Sc. Paris, 18 October 1971, p. 727-730.

[3] Clark, W. D., Gray, H. L., Adams, J. E.

*A Note on the T-Transformation of Lubkin.*

Journal of Research of the National Bureau of Standards, B. Mathematical Sciences, Vol 73B, No. 1, January - March 1969, p. 25-29.

[4] Delahaye, Jean-Paul.

*Sequence Transformations.*

Springer-Verlag, 1980.

[5] Shanks, Daniel.

*Non-Linear Transformations of Divergent and
Slowly Convergent Sequences.*

Journal of Mathematics and Physics, Vol 34, 1955, p. 1-42.

[6] Smith, David A., Ford, William F.

*Acceleration of Linear and Logarithmic
Convergence.*

Journal of Numerical Analysis, Vol 10, No. 2, April 1979, p. 223-240.

[7] Smith, David A., Ford, William F.

*Numerical Comparisons of Nonlinear
Convergence Accelerators.*

Mathematics of Computation, Vol. 38, No. 158, p. 481-499.

[8] Wimp, Jet.

*Sequence Transformations and Their
Applications.*

Academic Press, 1981, p. 120-147.

[9] Wynn, P.

*On a Device for Computing the e _{m}(S_{n})
Transformation.*

Mathematical Aids to Computation, Vol. 10, 1956, p. 91-96.

[10] Wynn, P.

*On the Convergence and Stability of the
Epsilon Algorithm.*

Siam Journal of Numerical Analysis, Vol. 3, No. 1, 1966, p. 91-122.

^{[4]}Brezinski
calls this transform the transform and calls what we
know as the transform the _{}-transform. I have
interchanged this notation to avoid confusion.

^{[6]}Where
the _{}'s are the coefficients of the series in question.