3.3 The e-Algorithm and the rj-Algorithm

In this section we describe the e-algorithm for sequence transformations and show that one of its columns is the sequence of Aitken's A2 method. Then we describe the Tj-algorithm, which is the corresponding algorithm for series transformations.

The e-algorithm originates with Shanks [1955] and Wynn [1956]. It involves the two-dimensional array called the e-table (Table 1). The sub­script k of e[J) denotes the column, and the superscript j measures the progression down the column. The table is constructed iteratively from its first two elements. Define e(/\ to be zero and ej0) to be the given sequence, fory' = 0,1,2,.... Then all the other elements may be calculated from the

Table I. The £-Table.

 

e

e-algorithm, which is

(3.1)

To see more clearly how this rule should be applied, we note that it connects the elements in the rhombus pattern of Figure 1, which shows how the

Figure 1. A rhombus pattern.

right-hand member e[jl, is derived from the other three members. It is now plain that the e-algorithm allows the whole e-table to be calculated. It is further plain that if         + i.e. two successive members of the same

column are equal, the element does not exist. We assume, unless explicitly stated otherwise, that all elements exist. Otherwise the table is said to be degenerate. We will show that the sequence of the fourth column, namely 7 = 0,1,2,...}, is the same as that obtained from Aitken's A2 rule.

From (3.1),

vH^-e'oT'

;y)=e(o/+0 + [eO+i)_e(/)]

 

£

 

= S,     where A2S =AS1 + 1-AS,.

/ A2Sj  / J + l   I

This formula is precisely Aitken's A2 method (1.2) applied to the sequence {5^,7 = 0,1,2,...}, and is also the result of using the second row of the Pade table as a Pade method for sequence acceleration.

= [S> + 1-S>]-, = [AS>]-'.

e'

Again from (3.1),

After we have established Wynn's identity in Section 3.4, we then show in Section 3.5 that the e-table and the Padé table are identified by the formula

 

 

What we have just achieved is the proof of this result for k= 1 and 7 = 0,1,2,....

Table 2. Even Columns of an f-Table for tt.

 

 

Example I. We consider Gregory's notoriously slowly convergent series for tt.

 

 

In Table 2, we exhibit the even columns of the e-table for this series. The first column seems scarcely convergent, whereas the correctness of the final extrapolations is instantly recognizable.

Table 3. Even Columns of an e-Table for In 3.

 

 

Example 2. We consider a familiar divergent series, namely the one given by the Maclaurin series of ln(l+z) with z = 2:

 

 

This has a remarkable e-table, with even columns given by Table 3. For comparison, In3= 1.098612.... We see, by example, that the e-algorithm may be used to sum divergent series.

 

As an amusing paradox, we briefly mention Hardy's puzzle, which has an entirely straightforward solution. Let

(3.2)

Consider the domains ^D and & defined by provided

 

 

 

 

 

 

 

 

Figure 2. The r-plane. showing the domains and t>

 

 

Notice that (3.2) is a binomial series which converges if |2z|<|l + z2|. The boundary of convergence is given by

(zz*+iz*-iz-\)(zz*+iz-iz*~l) = 0 showing that (3.2) converges for z G6]) and zGS. Therefore

/(z)=j±^=g(z) if zG^j)

and

f(z)=^±± = -g(z) if zGS. z — 1

The puzzle is to decide what result is given by the e-algorithm for (3.2) with 2 = 2/. Does it converge to g(2/)= — f or —g(2/)= + f?

At this stage, since the expansion parameter is invariant under z —»1 /z, the correct answer should seem clear, and it can be empirically verified by calculating e(20), which is quite close. Proof of the veracity of this solution requires the technique of the theorem of Baker, Gammel, and Wills in Section 6.7.

As a final remark on the e-algorithm, we note the possibility that the sequence S= {e^0), k = 0,1,2,...} does not converge, and yet an iteration of the algorithm using the derived sequence S as a new initializing sequence {eg'7', 7 = 0,1,2,...} may lead to a convergent sequence {e^<0)}, e.g. as in Table 1 of Part II, Section 1.3. But no theoretical justification for iterating the e-algorithm is known yet.

The e-algorithm may be regarded as a sequence-to-sequence transforma­tion: it is an algorithm for transforming the elements of the given series in the second column to the elements on the principal diagonal. Specifically, the sequence {e^, y = 0,1,2,...} is transformed to a new sequence {e^0), Af = 0,1,2,...}. Bauer's Tj-algorithm is the equivalent series-to-series transfor­mation.

The tj-algorithm [Bauer, 1959]. The series c,, / = 0,1,2,..., is given. The 7)-algorithm is initialized by assigning these values'to the second column of the 7)-table:

 

 

 

 

 

 

 

Table 1 of Part II, Section 1.3. But no theoretical justification for iterating the e-algorithm is known yet.

The e-algorithm may be regarded as a sequence-to-sequence transforma­tion: it is an algorithm for transforming the elements of the given series in the second column to the elements on the principal diagonal. Specifically,

 

 

 

 

7,<;>=c„ /=0,1,2,....     (3.3)

The elements of the first column of the Tj-table are defined by the artificial values

 

 

 

 

(3.4)

 

 

 

 

Figure 3. The rj-table.

 

 The recurrence scheme is defined by

 

(3-5)

 and

 

 

(3-6)

Equations (3.5), (3.6) are rhombus rules connecting the entries shown in Figure 4. These equations enable the rightmost entries of the rhombus to be

 

Figure 4. Rhombus rules for the rj- table.

Clements ot(5)            fclements ot (6)

 

 calculated; hence the entire 7]-table of Figure 3 can be constructed from its first two columns given by (3.3), (3.4). With these definitions (3.3)-(3.6), the 7)-algorithm defines a transformation of the series c; =t)<0'), / = 0,1,2,... to a new series c'i.=iff!\ k = 0,1,2,.... One purpose of this algorithm is the

 

which

 

of a new series

construction from a convergent series

 

converges faster to the same limit. As an empirical example of this we consider Gregory's series again:

(3.7)

Table 4. The rj-Table for Gregory's Series.

 

 

 

 

 

 

hold so long as the quantities involved are well defined.

 

 

Example 3. The second column of the 77-table is constructed from (3.3) using the terms of the series (3.7). The first column is artificial, and the other columns are constructed from the rhombus rules (3.5) and (3.6). From Table 4 we find that the series (3.7) has been transformed to

(3.8)

we have assumed that the transformed series converges to the same limit. From the figures quoted, the series (3.8) appears to converge faster than (3.7), as expected. To justify these manipulations, we will prove first that the e-algorithm and the Tj-algorithm are equivalent in the sense that

(3.9)

In the context of Example 3, this means that the odd partial sums of (3.8) yield the diagonal estimates of 77 given by the principal diagonal of Table 2, as is easily checked.

Theorem 3.3.1. The identitiesProof. As indicated in (3.10) and (3.11), we use the identity (3.1), which constitutes the e-algorithm, whenever necessary. Since either (3.5) and (3.6) or (3.10) and (3.11) uniquely define the Tj-table, our method of proof consists of using (3.10) and (3.11) to establish (3.5) and (3.6). It is convenient to extend the domain of definition by assigning

 

 For the third column of the table, (3.11) becomes (C-A) = (D-C)-(B-A) is interpreted by (3.10) and (3.11) as the second column. We show that the elements of the Tj-table defined by (3.10) and (3.11) are identical to those defined by (З.З)-(З.б). For the second column of the Tj-table, the definition (3.3) yields the same values as (3.10) with k = 0, because which yields the same values as are defined by (3.5) when k = 0. To justify (3.5) and (3.6) as defining equations for the fourth and subsequent columns, we consider an identity among elements in a rectangular array in the e-table. Let A, B, C, D be the elements shown in Figure 5. The identity (D~B)~

Hence and by summation

It only remains to observe that an immediate consequence of (3.10) and (3.11) is that. We have thereby established its equivalence to the e-algorithm as a sequence to sequence transformation.

For further details about the e-algorithm and Tj-algorithm, we refer to Bauer et al. [1963], Wynn [1960, 1961a], and Brezinski [1977]. For applica­tions of the e-algorithm to vector and matrix valued quantities, we refer to Wynn [1962b, 1964], McCleod [1971], Gekeler [1972], Mills [1975], and Brezinski [1977].

(3.11) as