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

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

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

Abstract

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

Section 1 Introduction

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.

Section 2

Transform Motivations and Properties

The Motivation of the e Transform

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 kth 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 kth order [5, p. 7]. This fact suggests that the sequence of 's (for some fixed k) might converge faster than the sequence itself. This sequence of kth order local bases is then defined as the -transform of the sequence [5, p. 8], [in fact, it is identical with as defined in the following discussion.]

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].

Properties of the e Transform

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 and if and only if satisfies a homogeneous linear difference equation of order k with constant coefficients (and no equation of lower order) and contains no terms that are purely algebraic..

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 S. Let , and suppose that the sequences converge to , respectively. The convergence of the series is said to be logarithmic if , linear if , and of higher order if [6, p. 224].

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.

The e Transform and the -Algorithm

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 r; then, if r is either totally monotone or totally oscillatory, then is regular for all even m [8, p. 139 and 141].

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 L and is a polymonial of degree at most M. The coeficients of the polynomials are chosen so that , where A(z) is the Taylor expansion of f(z) [6, p. 5]. If we require that Q and P have no common factors and that Q(0) = 1, then [L/M] is unique [1, p. 8].

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 Motivation of the Transform

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.

Properties of the Transform

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.