Numerical Algorithms 8(1994)47-81 47 A hierarchically consistent, iterative sequence transformation Herbert H.H. Homeier Institut ffir Physikalische und Theoretische Chemie, Universitdt Regensburg, D-93040 Regensburg, Germany E-mail: [email protected]Received 10 December 1993; revised 29 April 1994 Communicated by C. Brezinski Recently, the author proposed a new nonlinear sequence transformation, the iterative J transformation, which was shown to provide excellent results in several applications (Homeier [15]). In the present contribution, this sequence transformation is derived by a hierarchically consistent iteration of some basic transformation. Hierarchical consistency is proposed as an approach to control the well-known problem that the basic transformation can be generalized in many ways. Properties of the J transformation are studied. It is of similar generality as the well-known E algorithm (Brezinski [3], H~vie [18]). It is shown that the J transformation can be implemented quite easily. In addition to the defining representa- tion, there are alternative algorithms for its computation based on generalized differences. The kernel of the J transformation is derived. The expression for the kernel is relatively compact and does not depend on any lower-order transforms. It is shown that several important other sequence transformations can be computed in an economical way using the J transformation. Keywords: Convergence acceleration, extrapolation, summation, hierarchical consistency,. model sequences, iterative transformations, Levin-type transformations, E algorithm, generalized difference schemes, operator method. AMS subject classification: AMS(MOS): 65B05, 65B10. 1. Introduction Sequences sn which converge very slowly to some limit s are abundant in mathematics and its applications in science and engineering. Thus, there is a need for methods to accelerate their convergence. Such sequences can be for instance partial sums of infinite series, or extrapolation problems depending on a discrete set of parameters. In other cases, divergent expansions occur which have to be summed to some finite number s if possible. Then, one calls s the antilimit. Hence, there are the problems of convergence acceleration, of extrapolation, and of summation. J.C. Baltzer AG, Science Publishers
Transcript
Numerical Algorithms 8(1994)47-81 47
A hierarchically consistent, iterative sequence transformation
E-mail: Herbert.Homeier @chemie.uni-regensburg.de Received 10 December 1993; revised 29 April 1994
Communicated by C. Brezinski
Recently, the author proposed a new nonlinear sequence transformation, the iterative J transformation, which was shown to provide excellent results in several applications (Homeier [15]). In the present contribution, this sequence transformation is derived by a hierarchically consistent iteration of some basic transformation. Hierarchical consistency is proposed as an approach to control the well-known problem that the basic transformation can be generalized in many ways. Properties of the J transformation are studied. It is of similar generality as the well-known E algorithm (Brezinski [3], H~vie [18]). It is shown that the J transformation can be implemented quite easily. In addition to the defining representa- tion, there are alternative algorithms for its computation based on generalized differences. The kernel of the J transformation is derived. The expression for the kernel is relatively compact and does not depend on any lower-order transforms. It is shown that several important other sequence transformations can be computed in an economical way using the J transformation.
Keywords: Convergence acceleration, extrapolation, summation, hierarchical consistency,. model sequences, iterative transformations, Levin-type transformations, E algorithm, generalized difference schemes, operator method.
Sequences sn which converge very slowly to some limit s are a b u n d a n t in m a t h e m a t i c s and its appl ica t ions in science and engineer ing. Thus , there is a need for m e t h o d s to accelera te their convergence . Such sequences can be for ins tance par t i a l sums o f infinite series, or ex t r ap o l a t i o n p rob lems depend ing on a discrete set o f pa ramete r s . In o the r cases, d ivergent expans ions occur which have to be s u m m e d to some finite n u m b e r s i f possible. Th en , one calls s the anti l imit . Hence , there are the p rob lems o f convergence accelera t ion, o f ex t r apo la t ion , and
It turns out that no single method is able to solve efficiently all such problems which arise in practice. There are numerous methods known. Good general introductions to these methods have been given by Wimp [26], Weniger [23], and by Brezinski and Redivo Zaglia [7].
Many of the methods mentioned above have been derived on the basis of so-called model sequences. In this approach, one constructs a method which is exact for some model sequence which is chosen in such a way that one can compute the limit or antilimit with a finite number of operations from a finite number of elements of the model sequence. In many cases, the model sequences depend linearly on some coefficients which are eliminated for the computation of the (anti)limit. Then, by construction, the model sequences form a linear space which is the kernel of the method. These methods can be applied to other sequences as well. In this case, they provide a sequence transformation. Such a sequence transformation is expected to yield good results if the kernel of the method is a good model for the sequence under consideration.
Consider a model sequence {sn} of the form
k
so=s+ - ajgj(n), n No, k N, (1) j= l
which involves the (anti)limit s, some constants aj and some functions gj(n). This is the model sequence of the E algorithm which was derived by several authors and has been studied in a general way by H~vie [18] and Brezinski [3]. It is also known as the Brezinski-H~vie protocol [26, chapter 10]. A good recent introduc- tion to this sequence transformation is also given in ref. [7, section 2.1]. See also ref. [8]. Numerous other sequence transformations are special cases of the E algo- rithm. It may be computed recursively either using the original approach of Brezinski [7, pp. 58f] or, more economically, by a different approach due to Ford and Sidi [12]. But still, these are computationally demanding algorithms. This is the price one has to pay if one tries to compute a large variety of different sequence transformations via a single, very general sequence transformation which is exact for the model sequence (1). For special choices of the gj(n), more economic algorithms are often available. Thus, it is worthwhile to use instead these special algorithms for the special cases in order to reduce the computational burden. For instance, for gj(n) = wn/(n + ]~)j--1 a famous transformation of Levin [19] results which can be computed very efficiently using recursive schemes which are simpler than those for the E algorithm. Here, w, r 0 is a remainder estimate and
> 0 is a constant. Thus, the E algorithm has a kernel which is formally very simple but the
recursive scheme is rather demanding computationally. The E algorithm is computationally valuable especially in cases where functions gj(n) can be found which are adapted to the problem under consideration, but for which no computationally simpler algorithm is available.
From the theoretical point of view, the E algorithm has the advantage that its
H . H . H . H o m e i e r / I t e r a t i v e s e q u e n c e t r a n s f o r m a t i o n 49
s(~') = f ( { s , } ) = s, -
The recursive scheme
kernel (1) is known. However, most problems arising in practice involve sequences which are not in the kernel of the transformation anyway. Thus, one only has the hope that the model (1) is "near" - in some sense - to the sequence to be acceler- ated. From this pragmatic point of view one knows in most cases only a pos ter ior i whether the model sequence is suitable for the problem sequence, i.e., it is well- chosen if computation shows that the corresponding sequence transformation is able to accelerate the convergence of the problem efficiently.
For many applications, the primary problem is to find functions gj(n) which allow to approximate the behavior of the investigated sequence by the model sequence (1), at least asymptotically for large n. Then, these functions are expected to provide good results. But even if a detailed analysis of the convergence type of the problem provides asymptotically suitable gj(n) , it is not certain a pr ior i whether subdominant terms, which are not well described by the gj(n) , might lead to a deterioration of the quality of the results.
Thus, it is not clear in practice which special case of the model sequence (1) is well-chosen for the problem sequence.
Alternatively, one can consider much more simple model sequences which correspond to very simple basic sequence transformations of the form
s~ 1) : f ( { s n } ) , n E N 0. (2)
Here, f is a simple function depending on a small number of elements s, of the original sequence, and {s~ 0} is the transformed sequence. Then, these basic transformations can be used iteratively by setting
s(k+l) = f({s(k)}). (3) n
A simple example is the iteration of the famous A 2 method of Aitken [1]. Here, we have
( s , + , - s , ) 2 (4)
Sn+ 2 - - 2Sn+ 1 -]- S n "
d ~ ") = s , , (5a)
r rd(n) (d~(kn+ 1) (n) 2 - ) ( S b )
~ k + l : ~ ~ __ 2O.k,~C(n+0 !'a- ~(n)k '
results. It has been studied by numerous researchers, and has been reviewed by several authors [26,23,7].
The ordering of the indices, i.e., whether n is an upper or lower index, is different in equations (3) and (5). The ordering in equation (3) is more consistent with the view that one has mappings or transformations between sequences, s~, s" = s,(, 0,
tt S(2) s, = , . . . , while the ordering in equation (5) is used in most of the literature for the iterated Aitken process. Here, and in the following, we use the ordering of equation (3) unless we discuss known sequence transformations. Then, the
50 H . H . H . H o m e i e r / I terat ive sequence t rans format ion
ordering of indices is used which prevails in the literature for this sequence trans- formation. We note that a similar notation rule seems to have been used by Wimp [26] who also uses both orderings (see, for instance, p. 73, equation (1) and p. 138, equation (1) of [26]).
It may be noted that Aitken's method (4) is exact for the following very simple model sequences of the form
s , = s + c ( s ~ + l - s ~ ) , nEN0. (6)
These model sequences involve an arbitrary constant c. Assume that the iterated Aitken transformation is able to accelerate the convergence of some given sequence {s,,}. Then, model sequences (6) should - for all stages k of the iteration - be a good model:
[ ,..A( n+l ) ~ ( k n ) = S + t . k k ~ k - - ~'(k ~)) + e(k ~), n E No. (7)
Here, e{k ") is some small error. If for some stage k of the iteration e(k "1 vanishes for all n then the iterated Aitken transformations ~r are exact for l > 1. However, in practice it is rather involved to prove such a result because closed form expressions for the transforms d(k n) for higher values of k are usually not available.
This shows that it is normally very difficult to obtain explicit expressions for the kernel of iterative algorithms. Compare also ref. [9]. In addition, there is some ambiguity in the construction of the iteration process from the basic transforma- tion (2). Instead of using the definition (3) to implement the iterated version one can also use an explicitly k-dependent rule
k N0, (8) where f0 = f holds. For instance, in the case of the iteration of Aitken's method one could construct modified iterative algorithms of the form
~ / (9a) = Sn,
- - ( n + l ) - - ( n ) 2
~ k+ 1 = - - X k ~(n'-~)) - - T - ' - ~ n - - ~ ~ "Z'-~A(n ) ' (9b) " ~ k - - " ~ k -t- -3~ k
with X0 = 1. One could choose for example Xk = (2k + 1)/(k + 1). These modified algorithms may or may not be useful for certain problems. This cannot be decided a priori. Some algorithms of a form which is very similar to equation (9) were treated in refs. [2] and [24]. Further ambiguities may arise in two cases:
(a) if there are different equivalent formulae to compute the basic transformation which, however, lead to different iterated algorithms, or
(b) if the basic transformation described by f involves n either directly or via some additional, auxiliary sequence.
Examples for such ambiguity problems can be found in ref. [24]. Iterative algorithms are often computationally simple. They are based on simple
models which are easy to construct and adapt to special problems. They can also
have simple convergence properties if one studies a single stage of the iteration, as exemplified by the simple kernel (6) and the discussion following this equation. But the construction of iterative algorithms is not free of ambiguities. Explicit kernels for the complete algorithms are difficult to find. In addition, convergence proofs for the complete iterated sequence transformation are much harder to find than for each separate stage.
Thus, with respect to the above properties, algorithms based on model sequence (1) behave more or less complementary to iterative algorithms.
Of course, one cannot find a universal sequence transformation which is able to accelerate the convergence of every given convergent sequence because this would contradict the theory of remanence as introduced by Delahaye and Germain- Bonne [11]. But still, the question arises whether it is possible to construct an iterative, computationally simple sequence transformation with a large range of applicability for which one can find the kernel explicitly. This would combine the advantages of the two approaches described above. An interesting candidate for such a sequence transformation is the J transformation that was recently introduced by the author [15]. This transformation proved to be able to accelerate quite efficiently a number of test sequences [15]. The computational effort to calculate it is low.
The derivation of the J transformation is treated in the following section. As in the case of other iterative sequence transformations, the starting point is a simple basic sequence transformation which is exact for some simple model sequence. Then, the problem is how the basic sequence transformation may be iterated. Its repeated application should be justified in some way. To do this, one may try to find out whether the transformed sequence is of a similar form as the model sequence for which the basic transformation is exact. A more formal approach would be to apply the basic sequence transformation to a generalization of the corresponding model sequence. Thus, one has in mind a hierarchy of model sequences. Models higher in the hierarchy are more complicated than the lower ones, and depend on more parameters than the latter.
Consider a sequence transformation that is based on the iteration of a basic sequence transformation which depends on some parameters. The iterated trans- formation is called "hierarchically consistent" or "consistent with the hierarchy" under the following conditions:
(a) The kernel of the basic sequence transformation is the model sequence which is lowest in hierarchy.
(b) The application of the basic sequence transformation to a model sequence which is higher in the hierarchy results in a new sequence which is of the form of some simpler model sequence which occurs lower in the hierarchy. The latter may depend on different parameters. These are called "renormalized parameters".
It is valid in the sense of this definition that the parameters of the basic sequence transformation may also be renormalized in each step of the iteration. Thus, the
application of such a sequence transformation to some model sequence of the hierarchy provides a mapping to a model sequence which is lower in the hierarchy, with renormalized parameters. Under these circumstances, one is justified to apply the basic transformation - normally with correspondingly renormalized parameters - again to this new sequence. Continuing iteratively, one descends further in hierarchy. Finally, the kernel will be obtained, and the process will stop yielding the exact result for the chosen hierarchy of model sequences.
We remark that it suffices that the above conditions are satisfied only asymp- totically for large n. That means that applying the basic sequence transformation to some member {s,} of the hierarchy of model sequences yields a new sequence {or'n} which is normally no t a model sequence lower in the hierarchy. One requires, however that {or',} approaches such a model sequence {s',} asymp- totically. Iterating then, one also descends in the hierarchy and is led to the kernel of the basic sequence transformation, but only asymptotically, for large n. Of course, analytical results are more difficult to obtain for iterative methods which satisfy only this weaker "asymptotical consistency with the hierarchy". Therefore, we restrict our attention in the present paper to the case that the hierarchical consistency is valid in the stronger sense.
The important feature of this "method of hierarchical consistency" is that the parameters occurring in the course of the iteration have to be chosen in some definite way in order to guarantee that the iterative sequence transformation is consistent with a given hierarchy. In this way, the ambiguity problem is eliminated for a given hierarchy. Of course, one now has to solve the problem of the proper choice of the hierarchy. But this can be discussed in a more formal manner.
We will see how the method of hierarchical consistency works by considering a simple example in the following section.
The J transformation which is derived along these lines depends on some I ~(k) -too auxiliary sequences l - , r for k ~ N0. These sequences are related to the
definition of the hierarchy of model sequences. For each choice of the auxiliary sequence a different hierarchy, and essentially a special sequence transformation with different numerical properties and range of applicability is obtained. The J transformation also depends on remainder estimates ~,. For these remainder estimates reasonable choices for different classes of problems are known. The different choices of % lead to several variants of each of the special sequence trans- formations. Thus, the J transformation is very flexible and general. Many special cases can be introduced in a rather natural manner.
The construction of the J transformation allows to discuss the question of proper choices of the remainder estimates independently from the question of proper choices of the hierarchy.
The derivation of the kernel and of recursive representations of the j trans- formation is given here. The expression for the kernel depends only on the elements r~ k) of the auxiliary sequences and the remainder estimates %, but not on low-order transforms.
H . H . H . H o m e i e r / l t e ra t i ve sequence t ra n s fo rma t io n 53
Elsewhere, some convergence results [16] and determinantal representations [17] for this general sequence transformation will be presented.
By using the method of hierarchical consistency, the ambiguity problem of the construction of iterative sequence transformations is put into a formal frame- work. Depending on the choice of the basic sequence transformation, more or less different classes of sequence transformations result which are of similar generality as the J transformation. Thus, the method of hierarchical consistency is of a rather general nature and, in the case of the j transformation, an approach which permits the discussion of properties of large classes of iterative sequence transformations simultaneously. For instance, for all sequence transformations which fit into the framework described above, one obtains expressions for their kernel, determinantal [17] and recursive representations, and some basic con- vergence theory [16] without too many additional considerations. In addition to the theoretical advantages of the J transformation, powerful new algorithms can be obtained by suitable choices of the hierarchy [15,16].
2. Heuris t ic der ivat ion o f the sequence t rans format ion
We study the very simple basic model sequence
s . = s + c w . , n E No. (10)
Here, s is the (anti)limit, w. are remainder estimates satisfying w. ~ 0 and/Xw. ~ 0, c is an unknown constant. The latter can be eliminated and, consequently, the limit s can be computed from the elements s. of the sequence:
As. (11) S : S . - - W . A W . "
Here, as usual the difference operator A defined by
A f ( n ) = f ( n + 1)- - f (n) , A g . = g . + , - - g . , (12)
acts on the index n only. The right hand side of equation (11) can also be applied to other sequences which differ in form from the model sequence (10). Then, equation (11) becomes a sequence transformation {s.} -~ {s'}:
, As. (13) S n ~ S n - - W n m w n "
In equation (10), w. can be any estimate - up to a constant - of the remainder. For instance, one can use the choices w. = As._1 or w. = (n + 3)As._1 in
analogy to the t and u transformations of Levin [19]. For the choice w. = As. which was proposed by Smith and Ford [21], equation (13) becomes the A 2 sequence transformation of Aitken [1]. Levin also proposed the choice W n ~ - - - / ~ S n A S n _ I / A 2 S n _ I . For any sequence transformation which is based on remainder estimates w., one obtains corresponding variants. These will be called
54 H . H . H . H o m e i e r / l t e r a t i v e s e q u e n c e t r a n s f o r m a t i o n
the t variant for w. = As._~, the u variant for w. = (n +/3)As,,_l, the 7 variant for w. = As.. and the v variant for w. = - A s . As,,_~/AZs._l. respectively.
One could also choose w. = (n +/3) -<~ for positive constants a and/7. In this way. the remainder estimates do not depend explicitly on the elements s. of the sequence whose convergence has to be accelerated, or which has to be summed in the case of divergence. For such choices, many sequence transformations become linear functions of the s.. An example is given by the transformation (13).
We remark that the sequence transformation (13) can be rewritten in the following ways which may result in possibly different numerical behaviour of computer implementations:
A s n s,', = s.+l - W.+l Aw. ' (14a)
__ S .+I Afa,,ln - taJn+ 1 ASh Am.
__ O')n+lSn - - Sn+l~,Un
AOJn
__ ~On+lSn - - Sn+lO3n
fMn+l - - COn
[ s . + , / < o . + , ] - [ l /w , ,+ , ] - [ l /w , , ]
(14b)
(14c)
(14d)
( 14e )
Similarly, there are many different representations in the case of Aitken's A 2 process as noted by Weniger [23, p. 223, equations (5.1-6)-(5.1-12)].
The transformation (13) is identical in form to the 0-type algorithm O(tn) associated to the sequence transformation t, = s, + w,, (compare p. 381 of ref. [4]).
Now, we address the question how the simple sequence transformation (13) may be iterated. The method of hierarchical consistency was discussed in the previous section. According to this method, one has to apply (13) to a generalization of equation (10). Thus, one has to choose a hierarchy of model sequences. First, we study a simple example:
A relatively natural generalization of the model sequence (10) would be
n No, (is) This corresponds to the first two terms of a Poincar&type asymptotic series instead of the constant c. Using the method of hierarchical consistency, we apply the sequence transformation (13) to this model sequence and have to find out whether the result is again of the form (10). We obtain
, 03nOdn+ 1 1 s ~ = s + c l Aw. ( n + ~ ) ( n + 1 3 + l ) " (16)
This is of the form (10) for redefined w.. The latter play the role of renormalized
, w,w,+l 1 w . - Aw,, ( n + / 3 ) ( n + / 3 + l ) " (17)
This shows that for higher stages of the iteration of the sequence transformation (13) one should choose different remainder estimates as compared to the first stage. One can also choose different values of the parameter /3 in the various stages of the iteration. Thus, in the case of the simple generalization (15) of the model sequence (10) the following algorithm for the iteration of the sequence transformation (13) suggests itself:
(18a)
(18b)
s" = s - cl w.w.+1 Ar . . / ~ o 3 n
This is of the form of equation (10) if we choose
' O')niMn+l Ar,. (22) t.d n - - m t M n
On every stage k of the iteration a different sequence {r(, k)} can be chosen which plays the role of the sequence (r,} in the last three equations. We use the definition
6(k) = At(, k). (23)
Then, the method of hierarchical consistency yields in the case of equations (10),
(21)
n
,(k) ,(k) 1 , ( k + l ) __ ~ n ~ n + l
[.M n Aw(~ k) (n +/3k)2 " (18C)
Here, (a), = 1-'(a +n)/F(a) is a Pochhammer symbol, and /30,/31,... are the elements of an auxiliary sequence of positive numbers. For instance, one could choose
/3k =/3 + k'7 (19)
for positive constants/3 and "7- It is also possible to choose a more general model sequence than equation (15).
This corresponds to a different hierarchy. Here, we propose to use the model sequence
s, = s + w,(c0 + cir,). (20)
The auxiliary sequence {r,} is supposed to converge to zero. In order to find out how the sequence transformation (13) can be iterated in a way consistent with this hierarchy, we apply the transformation (13) to equation (20) and find
Here, as well as in the following text, it is assumed that wn r 0, Aw. r 0, Aw~ k) r 0 and 6(. k) r 0 holds for all nonnegative integers n and k. Conditions for the validity of these assumptions will be discussed later more thoroughly.
We note that for the computation of J~k)({S.},{w.},{r~k)}) the sequence elements {S..}k=0, {a.+j}k=0, and {{6~j}~+l}k_52 are required:
For convenience, these ranges are assumed to be implicit in the notation used for the J transformation.
The sequence transformation (24) is the J transformation which has been introduced by the author [15]. We note that also in this context the different expressions of equation (14) can be used for equation (24b). The relative merits of these expressions can be studied numerically.
We also define the t variant of the J transformation as
3. Al ternat ive a lgor i thms for the J t r ans fo rma t ion
In addition to the recursive scheme (24) there exist alternative algorithms to compute the J transformation.
To derive the first of these algorithms, we define
D(k) = 1 w(k) , (32a)
N ( kl _ w~k/. (32b)
Using equation (14e) we can write
s(k+') _ / _ A N ? ) n A (1/w(nk)) AD~k ) . (33)
The right hand side of this equation may be set equal to s~ k+l) = N(k+l)/D (k+l)". It follows that D(k+l)= a~k)[AD~ k)] and N.ff+l)= a~k)[ANff )] holds with the same constants a~ k). To determine these constants, one observes that
holds which is a consequence of equation (24c). In this way, it follows that the quantities D (k) and N (k) both satisfy the 3-term recursion relation
x(k+,) _/xxp) 6(k) (35)
Recall that 6(~ k) is given by equation (23). Hence, an alternative algorithm to compute the J transformation is given by the equations
D(~ ~ = 1/w,, N(~ = s , /w, , (36a)
6~k) , (36b)
/ V ( k + l ) __ A N (k) 6(k) , (36c)
j~k)({s,}, {~,}, {r~k)}) -- D~k). (36d)
These results show that the J transformation is related to Levin-type algorithms [19] in the sense that numerator and denominator of the J trans- formation can be calculated separately using the recursive scheme (36). This is similar to the alternative implementation of the E algorithm as derived by Ford and Sidi [12].
58 H.H.H. Homeier I lterative sequence transformation
The J transformation can also be formulated in an operator language. Let
V~k) = 1 A (37)
be an operator acting on n dependent sequence elements f ( n ) . This operator can obviously be regarded as a generalization of the difference operator A. Using this kind of operator, one may write
~ ( k - 1 ) X-7(k-2) #l - - , "
as is obvious from equations (36).
. . .
�9 . . V~~ ' (38)
P ( f ( n ) ) = A k [ p k _ l ( n ) f ( n ) ] .
with operators P acting on sequences { f ( n ) } as
s~k) _ e(s , /w , ) (39) e(1 /w, ) '
(40)
Here, Pk-I (n) denotes a polynomial of degree k - 1 in n. It may be noted that for instance Levin's sequence transformation [19] fits into this scheme. It also may be related to the elaboration of the operator method of Weniger by Brezinski and coworkers [6,8,9].
There is a further algorithm to compute the J transformation. The quantities
~'~~ = X~~ (41a)
~ ( k ) = 6~0)6(l) . . . 6(k-l)x-(k) k E N, (41b)
satisfy the recursion relation
.r I ) _~. A.r~n(O), (42a)
~ ( O ) t ~ ( l ) . . . 6 ( k - l )
)~(k+l) = ~(v0) ~71) ;~(--~-1) ~,(+k~ _ .~(k), k E N, (42b) ~'n+l ~'n+l '-'n+l
if the X (k) satisfy equation (35). Thus, the J transformation can also be computed using the following algorithm
This may be compared to Weniger's operator approach [23, sections 7-9] who studied sequence transformations of the form
H . H . H . Home ier / I terat ive sequence transformation 5 9
/~Tn(k+l ) 6(n0)tS(n 1)'" "'SJ~ -l) ~(k) _ ~,(k), k E N, (43d) = ~ ~-wr_~/~,.+~
~ 'n+l L 'n+l " " " t ' n + l
y(k)({s.}, {w.}, {r~k)}) --/~(k) �9 (43e)
This shows that the J transformation can be defined entirely in terms of the ratios
fff) = 6~1/6~ k), k ~ No,
or their inverse products
~(o) = 1,
= [ f 2 7 7 ) . . . f ? - ' ) ] - ' , k E N .
(44)
(45)
Thus, according to equations (43), (44), and (45), the J transformation can be computed via the algorithms
~)(o) = 1/w. , ~(o) = s . /w . , (46a)
D(1)= Ab(o), )?~l)= A~r(O), (46b)
b ( k + l ) = 1 / ~ ( k ) __ b(nk) k E N, (46c) n /-(0) lc(l ) f ( k - i ) ~ ' n + l
Jn Jn " ' ' J n
~(k+l) = 1 ~(k) _ ~ff/, k E N, (46d) : (0 ) #-(1) : ( k - l ) ' ' n + l j n j n "" ".In
l?~ k) y(.k)({s.}, {w.}, {r(~k))) --/}(k), (46e)
and
1/<.., D ( k + l ) r l~(k) D(k)
n ~ ~ n z " n + l - -
/~n (k+ l ) = (~(k) ]Q(k) __ j~(n k) n n + l
R(k) {,x.,,<))) = '<)
1~o) = s , / w , , (47a)
k E No, (47b)
k E No, (47c)
(47d)
The alternative algorithms (46) and (47) allow the discussion of limiting trans- formations for n ~ c~. The latter are important in the formal theory of Germain-Bonne [13] on regularity and convergence of linear convergence which has been extended in ref. [23]. The application of this theory to the J transformation will be discussed elsewhere [16].
Let us remark that the various recursive schemes for numerators and denomina- tors that have been derived in this section, as well as the defining representation (24)
of the J algorithm are triangular recursion schemes of the form studied by Brezinski and Walz [10]
T ~ = T., (48a)
k ,-rk-1 T~ = A~T f-1 +#M~+l , k E N, (48b)
for integer u. The consequences of this observation, as for instance determinantal representations [10] for the J transformation, will be discussed elsewhere [17].
We note that the representation (36) shows that the numerical effort to compute the J transformation for given 6(k) can be regarded as virtually identical to that for the recursive computation of Levin's transformation as discussed for instance by Weniger [23, section 7.5]. This means that the J transformation is numerically very efficient in this respect. The use of the defining representation (24) seems to be a little more costly but turns out to be sometimes more stable numerically than the alternative algorithm (36).
4. General properties of the J transformation
It is easy to see that the J transformation is invariant to translation and homogeneous in s, and, hence, quasi-linear [5, 7, section 1.4]. We have the following theorems:
Theorem 1 The J transformation is quasi-linear, i.e.,
Proof This follows immediately from the fact that the J transformation can be calculated by algorithm (43) which depends only on the quantitiesf. Ck/defined in equation (44) since these quotients are invariant under the scaling r (k) ~ OLkr~ k). []
For the following, we assume that the auxiliary sequence {r~ k) } is given. Under this assumption, we will answer the question how one may choose the {w,} to obtain a properly defined J transformation.
Under the above assumption, the transformation j(k) depends on the (2k + 2) numbers {S.+j}k=0 and {w.+j}k=0,
Here, y(k) is a suitable subset of C k+l" Because the J transformation depends on the inverses of the remainder estimates w,, as may be seen from equations (36) or
62 H . H . H . H o m e i e r / I t e r a t i v e s e q u e n c e t r a n s f o r m a t i o n
(43), a necessary restriction on Y~*) is that no component of any vector in y~k) may vanish. Assuming this, it follows from representation (38) that j~k) is a continuous function of {%+j}~=0 if
v( f - ' )V( : -2) �9 .- V(~ [1/w,,] # 0 (57)
holds, i.e., if the denominator in equation (38) does not vanish. The operators V~ k/ function of are defined in equation (37). Equivalently, 1-'(, k) is a continuous
(Yl,..-,Yk+I) if
...... ..... # 0
holds. Thus, we define
C k+l k+l } y(k) = y E H YJ # 0 and (58) holds . j = l
(58)
(59)
Then, F (k) is defined and continuous on C k+l x y~k). Instead of relation (58) one may use the equivalent relation
We remark that /~k/ = ~n~(O)t~(l)''vn .~(k-l)l-)(k)v n --, are the denominators of algorithm (43). Thus, the allowed values of the {w,} are restricted in such a way that the denominators in the algorithm (43) do n o t vanish.
We recall that the J transformation can be computed using the algorithm (47) which depends on the quantities (I,}, k) defined in equation (45). If we assume that for all k E N the limits
~(0),,~(1) . . . 6 ~ k - l )
lim ~,~k/ = lim v, v, = ~k (62) n---,oo n ~ o o $(0) ~(1) . . . , g ( k - l )
" n + l Vn+l " n + I
exist (note e~ 0 = 1 according to equation (45)), one may define a limiting transformation J by the equations
~)~o) = I/w., ~(o) = s./%, (63a)
b(k+l) r A(k) /~k) k E No, (63b) n ~" ":VkL~n+l - - ,
~(k+tl ,r, ~r(k) _ ~k) , k E N0, (63c) = -.~k~Vn+ I
j~k)({s,}, {%}, {r~,k/}) -- b~k). (63d)
Since the coefficients in recursions (63b) and (63b) do not depend on n anymore, it is seen that ~k), ~k/, and )(k) depend on n only implicitly via s, and w,, but not
Thus, )~kl can be regarded as a function of the (2k + 2) numbers
(64)
and hence, as a function
rk : C k+l • ~'k
( (x , , . . . , Xk+l), (Y , , . . . , Yk+X))
,C,
' ~'k(Xl,... ,Xk+t lYl , . . . ,Yk+l)" (65)
Here, Yk is a suitable subset of ck+l: Condition (58) has to be replaced by
b~ k) I(~ ...... ~.+~)=(y, ..... yk+,) # 0.
Thus, Fk is defined and continuous on C k+l x Yk for
Yk = y ~ C k+l y / r 0 and (66) holds .
(66)
(67)
Numerators and denominators of the limiting transformation (63) satisfy the same recursion which may be regarded as a generalized difference relation. In addition, they are linear functions of the initial values for k = 0. It follows that they are represented by the same linear form on C k+l,
k+l
Lk(V) = Z lJklv/' v = (v,, . . . ,vk+l) E C k+l. (68) j=l
This form is applied to the vector (1/w, , . . . , 1/W,+k) in the case of the denomina- tors, and to the vector (s,/w,,, . . . , S,+k/W,+k) in the case of the numerators. We may write
Fk = Lk((Xl/yl,...,Xk+I/Yk+,)) (69) Lk((1/y l , . . . , l/yk+,))
Note that for rrk+l xlj=~ vj ~ 0 one can write
Lk((Vl,..-,Vk+l)) = b~k)](,, o ..... ~,k)=(l/v, ..... '/v~+,/" (70)
From equation (63), it follows that the coefficients l) k) depend only on the values of the limits O0,.-. , Ok-1 defined in equation (62).
From the representation (69), one obtains immediately that the limiting transformations Fk are exact for constant vectors, i.e.,
r'k(C,C,...,cly,,.--,Yk+,) = C, (71)
that Fk is a linear function of its first (k + 1) variables, and hence, a homogeneous function of degree one in these variables, and that Fk is multiplicatively invariant in its last (k + 1) variables, i.e., it is a homogeneous function of degree zero in these variables.
By a completely analogous reasoning based upon the recursive scheme (47), it is
seen that one may represent the F~ kl as a quotient of linear forms according to
r '(k) = L ( k ) ( ( x l / Y l ' " " 'Xk+l /Yk+l) ) (72)
L(~k)((1/yl,..., 1/yk+x))
Here, L~ k) involves n dependent coefficients l(k!, n,j
k + l
L~k)(v) = y ~ .n,/uj,l Ck)" v E C k+~ , (73) j=l
which are continuous functions of the ~(k) defined in equation (45). Hence, [,(k) is linear in its first (k + 1) variables. It also follows that it is exact on constant vectors, i.e.,
r~,kI(c,c, . . . ,CIyl,-- . ,Yk+a) = C. (74)
We note the limiting relations
lim l(k! : l~ k). (75) - n , . /
//----~ oo
They hold if the limits (62) exist for all k E N. Furthermore, the conditions (61) and (66) can equivalently be rephrased as
L~k)((1/Yl, . . . , 1/yk+a)) ~ 0 (76)
in the case of F~ k) and y,<k), and as
Lk((1/y l , . . . ,1 /yk+~)) ~ 0 (77)
in the case of Fk and ~'k- It follows from equation (75) that y. E Yk and y --= limn_ ~ yn imply y, E Yk for sufficiently large n. We remark that Yk and y~k) are open sets.
Thus, the following theorem is proved:
Theorem 5 (J-0) J ~ ) defined in equation (24) can be regarded as a continuous mapping F~ k)
on C k+l x y~k) where y~k) is defined in equation (59). (J-l) According to theorems 1 and 2, F~ k) is a homogeneous function of degree
one in its first (k + 1) variables and a homogeneous function of degree zero in its last ( k + 1) variables. Thus, for all vectors x E C k+l and y E y~k) and for all complex constants A and # ~ 0 we have
r k)(Axly) = Ar )(xly), (78)
F~k)(xl#y) : F~k)(xly). (79)
0-2) F~ k) is linear in its first (k + 1) variables. Consequently, for all vectors x E C k+l, x' E C k+l, a n d y E y~k), we have
For all constant vectors c = (c, c , . . . , c) E C k§ and all vectors y E y(k) we have
l"~k) (c ly)=C. (81)
If the limits (62) exist for all k E N there exists a limiting transformation Fk according to
Fg(x ly ) = l i m F(.~)(xly), x ~ C k+l, y ~ Y k , (82)
which is continuous on C k+l • Yk where Yk is defined in equation (67). Moreover, the limiting transformation I~k is also homogeneous and linear according to (J-l) and (J-2). It is also exact on constant vectors according to equation (81).
Now, we want to characterize the linear form Lk defined in equation (68) further. For any constant p ~ 0 we choose
bc.~ = p-". (83) Then, the direct application of the limiting algorithm (63b) yields
/ - I b~ t) = p-"-t H (q~j - p). (84)
j=0
This is shown easily by induction on l. From equation (70) we get
Proof It follows from equations (68) and (69) that
f'k O,a , . . . , a Z 1,q, . . . ,qk j=O
k+l j -2 / ( k+l ")
=a Z , j ( e ) q , - , Z q ~ / ~ Z ,)k)q,-jl (90a) j=2 /~=0 / t.j=l
a Z l) k)ql-](1 _ q j - l ) Z l) k)ql-j 1 q j=~ j=l
(90b)
a 1 - E l(k) l(k)q l-j . (90c) 1 - q j=~ .=
Because k+l
E / ( k ) = Lk((1, 1 , . . . , 1 ) ) = 0 j=l
is satisfied as a consequence of lemma l, equation (89) holds.
(91)
[]
With Levin-type transformations the J transformation shares the following property (see, for instance, lemma 1, p. 227, of ref. [21]):
Lemma 3 If, for a given sequence s, with limit s, the remainder estimates w, are exact up to a constant c ~ 0, i.e., w, = c(s, - s), then J(,k)({s,}, {w,}, {r(k)}) = s for all n and k > 0 .
The second term on the right-hand side vanishes as is evident from equation (38), in combinat ion with s. - s = w . / c . []
As a simple consequence we can prove that the t, t and v variants of the J trans- formation defined in equations (26) and (27) are exact for the geometric series. As is well-known this fact is important in the formal theory of Germain-Bonne [13] on regularity and convergence of linear convergence which has been extended in ref. [23].
T h e o r e m 6 The j t ransformation is exact for the geometric series if the sequence {to.} is chosen in such a way that s . = s + c w . holds with c r 0. This is satisfied for w. = As._~, for ta. = As., or for w. = - A s . A s . _ i / A 2 s . _ ~ . This implies that the t, the t, and the v variants of the J t ransformation are exact for the geometric series.
P r o o f
I f s . = s + c w . holds, the assertion follows from lemma 3. However, this equation holds in the case of the t, t, a n d v variants. This follows from the relations
As. = q.+l, A 2 s n : q n + l ( q _ 1), (93)
for the partial sums
s . = ~ qJ -- 1 - q.+l q n+ls A s n A s . _ l j=o f L S q - s - = s - s A s . = s - s q A s . _ l = s + A2s._I
of the geometric series
(94)
s = ~ q J - l _ q , [q[ <1" (95) j=0
Thus, in all considered cases (s , - s ) / w , is equal to a constant c. []
Here, and in the following, the notat ion
n > n I > hi+ I 2> "" 2> "l+k-!
n--I nl--1 nl+k-2--1
nl=O nl+l =0 nl+k-l=O
for positive k and l is used. Empty sums are assumed to be zero.
(96)
68 H . H . H . H o m e i e r / I tera t ive sequence t ransformat ion
Lemma 4 Assume that, for all n E No the ratio ( s . - s ) / w ~ can be expressed as a series of the form
o o S n - - S -- - co + ~ c : E : : ) . . . ~ j - l ) (97)
OJn j = l n>n l >n2 >... >nj vnl vn 2 nj
with Co # O. Then
S~ k) - - S o o
w~k-----T--= Ck + ~ cj ~ ~"k+,"#) 's(k+l)'' '6(J-l)~"k+2 ~, . (98) j = k + l n>nk+l >nk+2 >... >nj
P r o o f This follows by applying the operator vCk-l)vCf-2)... V~ ~ to ( s , - s ) / w , . Then, all terms involving the coefficients C o , . . . , Ck-1 vanish according to
�9 = (sO. k> . ,~Ck-,>~Ck-2) V~0) [ ( l /w . ) ] n - - ~ " " - - O J V n V n " " "
= s)D4 .
69
(101) []
5. The kernel of the J t r ans fo rma t ion
In this section, we study the kernel of the J transformation. Hence, the aim is to find all sequences {s,} for which the transformation produces the (anti)limit s exactly in a finite number of operations.
Theorem 7 The kernel of the transformation j(k): {Sn} ---+ {j(k)} is given by the sequences of the form
n - 1 n - I n 1 - ~
S n = S -J'- 0,) n C O -~- r ~ 6(0) -'{- (72 ~ 6(0) ~Cl) nl ~ nl ~n2
hi=0 hi=0 n2=0
Z " n > n l > n 2 > . . . > n k _ I
+ " " + Ck-1
with constants Co, �9 �9 �9 C k - l �9
P r o o f
(102)
If a sequence has the form (102) then equation (101) implies
( n-I n-1 ni-I
-- = ~7 n Vn . . . C0 .4- r vn I Z ~ nl ~ n2 hi=0 hi=0 n2=0
--~ . . . -~- C k _ 1 - n i v n 2 �9 . (103) n > n l >n2 > .,. > n k - i I )
Equation (99) implies that the term in curly braces vanishes, and hence, the J transformation is exact for the sequence (102) in view of equation (38):
s~ k) = J(k)({S.}, {W.}, {r(k)}) = S. (104)
Conversely, if equation (104) holds then equations (37) and (38) imply
V(k-3) "'" V(~ = sV("k-3)""" V(~ + Ck-I Z -'~-,'s(k-Z) 4- Ck-2. (108) nk- I =0
Similarly, all operators V}/) can be eliminated successively in the order of decreasing j. This finally leads to equation (102). []
Consider model sequences of the form
K - k - 1
s (k) = s + w~ k) ~ c) ~p),.,(k) (k) (109) j=0
(k) (k) lth (k) with w, r 0 and some auxiliary sequences ~p;, w" ~o 0 , = 1. For k = 0, the model �9 �9 �9 ~ ' ( 0 ) ' �9 sequences contain K independent coefficients cj . These model sequences will be
related to previous expressions for the kernel. Equation (32) implies that the sequences (109) can be written in the equivalent
form
K - k - 1 N('k) sD('k) + Z (k) (k) = c ) ~ o ) , . .
j=O
Performing one iterative step of algorithm (36). one obtains
K - k - I t , (k) / ~ qOj, n
K - k - 2 ^ (k)
6)+1 = sD~ k+l) + ~ 6~ k)
This is of the form of equation (110) if one sets
c~k+l) Ak)
^ ( k )
_(k+X) ~cP)+l., = w(k) ~(k) t['~j,n - - - ~ V n "~'j+l,n~
oh"
(110)
(111)
(l12a)
(l12b)
(compare also equation (37)) and if
^ (k) _(k+l) /XqOl,n
W0,, = 1-- 6(k) (113)
(k) (0) holds. Note that equation (112a) implies c) = c)+ k. (0) We remark that for given (pj,, the relations (112) and (113) amount to a definition
H . H . H . Homeier / l terative sequence transformation 71
of 6(~ k). More explicitly, one can write
~(k) A ^(k) = ~t[~l ,n~
A~--7(k-l) r~(k- 1) = - - n ~ 2 , n
A~-7(k- l) ~-7(k-2) ,~(k-2) ~--- ~ V n v n ' ~ 3 , n
A~7(k-l)~7(k-2) k-7(0) ,,(o) (114) = ~ - - n - - n " ' " " n "Vk+l,n"
One observes that one iterative step eliminates the leading coefficient c~ k) = C(k ~ of the expansion (110). Hence, we obtain
s=s K) (115)
for model sequences of the type (109) or (110), respectively. That means that the J t ransformation is exact for the model sequence
which can be proved with the help of equations (117) and (112). We remark that the model sequences (109) for different values of k define the
hierarchy for the J transformation, while the basic sequence transformation is given by equation (11), with suitably renormalized parameters w~ k), cJ k), and _(k) If equations (I 13) and (112) are satisfied, the preceding considerations show that the J transformation is consistent with this hierarchy in accordance with the definition given in section 1.
6. Re la t ion to other sequence transformations
Many known algorithms are exact for certain model sequences of the form
k - I
s. = n N0. (120) j = 0
Examples are treated later. These model sequences fit into the framework of the E algorithm for &(n) = w,~bj,, as may be seen by comparing equation (1). In most cases of interest the ~bj., are an asymptotic sequence for n + ~ according to ~bj+l, . = o(~j,,,). In order to see the relation of the J transformation to algorithms with kernels (120) one may try to find out whether it is possible to compute the 6(, k) which occur in the definition (24) of the J algorithm, from the
,, = ~/,j,, (121)
which can be regarded as initial conditions for the recursive scheme (112b). However, we want to stress that to start from model sequences (120) is not really
the intended way of application of the J transformation. Instead, the iterative application of much more simple model sequences is the aim. As shown in the heuristic derivation one can use from the beginning simple choices for the 6~ k) which correspond to rather complicated expressions for the ~bj,,. But this normally does not really matter because the sequences to be accelerated in practice are usually only approximated by model sequences like equation (120). Thus, the use of a many-term model sequence is not as a principle better than using simple
models iteratively. In addition, the new approach is flexible and numerically very efficient when used in the latter way.
Having stressed this important point we now return to the problem of the computation of the 6(~ k) from the ~bj,,.
This problem is solved in principle by equation (114). Thus, also for arbitrary !b j,, there is a general procedure how to use the J transformation for the computation of the corresponding sequence transformations. This means that the J transformation is a rather general framework as the E algorithm of Brezinski [3]. Also, there are many cross-relations to this algorithm. This will be discussed below.
However, it should be noted that the operators V! j) which are defined in equation (37), and which occur in equation (114), involve some (previously computed) 6~ k). Hence, equation (114) is not an explicit solution of the problem although it can be used for the numerical computation of all 6~ (k).
Thus, it would be interesting the 6(~ k) at least in s~ecial cases. functions ~bj,. = ~,~ for model
We note that equation (122c) is a special case x, = 1 / (n+f l ) . Also, equation (122a) is - apart independent of n - a special case of equation (122b).
to see whether one can obtain explicit solutions for There are several important families of asymptotic sequences of the form (120):
~bj,. = 1 / (n + f l) j , (122a)
(Tf12)J (122b) ~bj,. -- (Tn + f l ) j '
•j,. = 1 / ( n + fl)J, (122c)
Cj, , , = x/. (122d)
of equation (122d) for from a factor which is
The most simple case in this respect is given by equation (122a). Then, using
1 - j (123) A (ll -]- f l ) j - - (1l q- fl)j+l
together with equations (112) and (113), one obtains after some lengthy but straightforward algebra the solutions
qvJk) ( j + 1)k 1 (124) '" -- k! (n + fl + 2k)j
and
r(k) . (k) = (k + 1) : t ~ l , n 1 . ( 1 2 5 ) 1 6 ( k ) = _ ( k + l ) ( n + f l + 2 k ) 2 n + f l + 2 k '
Equation (122b) is a slight generalization of equation (122a), yielding the
74 H . H . H . Homeier / Iterative sequence transformation
following result
k
1-I(7(n + j ) +/3 + k - l)
= - ( k + 1)32-y 2 k+l
H ( ' Y ( n + j ) + 3 + k) j=O
= - ( k + 1)3 2 (n + 1 + (3 + k - 1)/'7) k -~-+ '(,~ 21 ? k3-/~ ) k-"~2 " (126)
This is proved by induction using equation (114). Now, we turn to the class (122d). Here, we have the result that the functions _(k) u
can be expressed in terms of divided differences. To formulate this result, we need some more notations.
The Ith divided difference of a function f ( x ) at the interpolation points x,, xn+l,...,x~+t is denoted by f [ x ~ , x , + l , . . . , x , + t ] . As is well-known [22, p. 38, equation (2.1.3.5)], divided differences can be computed recursively according to
f[x,,] = f ( x , ) , (127a)
f [x , , , x ,+ l , . . . , x,+t] = f [ x , + z , . . . , xn+t] - f [ x , , . . . , x,,+t.-i] , (127b) Xn+ I - - X n
for distinct interpolation points. In addition, divided differences are symmetric function of their arguments [22, p. 39, theorem (2.1.3.7)].
Defining gk(X) = X k, we now can state the result mentioned above:
Theorem 8 The solutions of the recursion relations (112) and (113) with initial conditions (121) are in the case of equation (122d) given by
,n = gj+k[Xn, " '" , Xn+k]" (128)
As a consequence we have
k
r(k) = Z X n + j , 6(k) = Xn+k+l - - X n . (129) j=0
P r o o f The proof is by induction. For k = 0, we have
~o) ,n = gj[xn] = x~. (130)
Assuming that equation (128) holds for given k > 0, we have to show that it also holds for k + 1. Taking differences with respect to n we obtain
Ord~k+l) = g J + k + l [ x n ' " " " , X n + k + l ]
,n gk+l [ X n , ' ' ' , Xn+k+l] (132)
The proof of equation (128) is completed by observing that gk[X,, . . . , X,+k] = 1 holds for all n and k (compare lemma 5).
The validity of equation (129) follows from the relation rC, k) ,,(k) ~r'l,n gl+k[Xn,..., Xn+k] , in combination with lemma 5. []
Lemma 5 For the function gk(X) = X k, k E N the following two relationships hold for its divided differences at the points x,+j, j = 0 , . . . , k:
(a) g k [ x , , . . . , x , , + k ] = 1. (b) gk[x,,. . . ,X,+k-,] = Y'~jks_~ X,+j.
Proof We have (compare [22, theorem (2.1.3.6), and proof of theorem (2.1.3.8)])
k-2 k-1
x k = gk[X,] + ' ' " + g k [ X , , . . . , X,+k_,] I I ( X -- X,+j) + g k [ X , , . . . ,X,+k] I I ( X - - X.+j) . j=0 j---0
(133)
Comparison of the coefficients of x k and x k-l on both sides of this equation completes the proof. []
A simple consequence of theorem 8 is that we can state the explicit solution for ~/Jk) in the case of equation (122c). Here, we consider a slightly more general case: ~n
Theorem 9 The solutions of the recursion relations (112) and (113) with initial conditions (121) are in the case of
~bj,, = (n + fl)-J~ (134)
given by
•oj(. k) ., = g i+k[(n + f l ) - " , . . . , (n + 13 + k)-'~]. (135)
As a consequence we have
k r(k)= ~~'(n +/5' + j ) -'~,
j =O
Ar(,k)=-- ( n + f l + k + l ) ~ - ( n + f l ) ~ (136) ( n + f l ) a ( n + f l + k + 1) ~
of Weniger (see [23, section 8]) based upon factorial series. We remind the reader that for established sequence transformations we use the ordering of indices as used in the literature.
The case (122b) yields - apart from irrelevant n-independent prefactors - for 3' = c~ and fl = a~ the model sequence for which the interpolating sequence transformation ff~)(a, (, s,, w,) of Weniger [25] is exact.
The case (122c) yields the model sequence which is the kernel of Levin's transformation [19].
The case (122d) yields the model sequence of the generalized Richardson extrapolation process introduced by Sidi [20]. It is also known as the W algorithm and was also studied by Weniger [23, section 7.4], and by Brezinski and Redivo Zaglia [7, pp. 71 f, pp. 116f]. The algorithm based on divided differences presented there turns out to be identical with the application of the algorithm (36) with the values (129) taken for 6~ k/. However, one should keep in mind that there is also the defining algorithm (24) which presents an alternative route to compute our transformation. But in a sense, this case shows that the general J transformation can also be regarded as a generalization of divided difference schemes.
The above results show that using the J transformation many known sequence transformations can be calculated via new computational schemes. In cases where one knows the 6~k/ (or chooses them appropriately), numerically attractive schemes result.
Now, we discuss the relation of the J transformation to the E-algorithm. The latter is exact for model sequences of the form (1). Its normal rules are
E~') = s~, g~l = gi(n), n E No, i E No, (139a)
~(n+0 Ek(./ = Ek(~l_ ~ k - I - - Ek(~x _(.) (139b) g(n+ l ) _(n) "gk-l ,k ,
k-l ,k -- ~k-l ,k
_ g ( n + l ) _ g(.) g(.) g(.) k-~,~ k-Li ..(.) i = k + 1 , k + 2 , (139c) k,i = k-l , i ~ 7 "rk- l ,k , . . . .
k-l ,k 6k-l ,k
H . H . H . H o m e i e r / I t e r a t i v e s e q u e n c e t r a n s f o r m a t i o n 7 7
Thus, this recursive scheme uses an auxiliary rule (139c). The calculation of the transforms Ek ("1 can be effected recursively and more economically also using the approach of Ford and Sidi [12]. This is usually presented in terms of quantities
U n . . . Un+ k
gl(n) " . g l ( n + k )
gk(n) . . . g k ( n + k ) �9 ~")(u) = (140)
gk+l(n) "'" gk+l (n+k)
gl(n) -.. g l ( n + k ) " . . :
gk(n) " " g k ( n + k )
defined for any sequence {u0, u l , . . .} where the g~(n) are kept the same even if they depend on the u, and the u, are changed. Then, one can compute the E algorithm according to
E~ n) - kv~)(s) (141)
while the �9 can be computed recursively via
k-Z , u ) - ~_) , (U) (142) �9 = , , , { . + , ) , _ , ,T, cn) ( g k + , )
~ : k - I ~ , g k + l ) - - X k - I
This computational structure is similar to the alternative algorithm (36)�9 The main differences are that no remainder estimates wn are involved directly and that the possibility is not taken into account that one can gain efficiency if the denomina- tors 6(k) are given from the beginning, and need not be computed as those in equation (142). It should be noted, however, that generalizations of the E algorithm involving remainder estimates w, ~ 1 are discussed in ref. [6].
Now, we want to relate the j transformation to some previous work on iterated sequence transformations.
Weniger [23,24] studied sequence transformations which can be obtained by the iteration of some basic transformation
"-'0 , . . . , ' - '0 j, n E N0, A E N, (143)
with O~ ") = sn. This can be iterated as
O(") PrA(") c~(~+l) A("+a)a k ,n E N0, (144) k + l ~ - - k " k ~ " ' k ~ " " " ~ " ' k 1~
or also, according to an explicitly k-dependent rule,
OCn) r. Ira(n} c~(~+0 ~(~+a)~ k ,n E NOr (145) k + l ~--- l k k V k ~ V k ~ " " " ~ ~.1 k / r
where F0 = F holds�9 Thus, there is usually no unique way to iterate a given basic
7 8 H . H . H . H o m e i e r / I terat ive sequence t rans format ion
sequence transformation. This is particularly evident in the more different case where F depends also explicitly on n. In such a situation, several different ways of iteration are possible leading to more general iterative algorithms
{") ~{")cA{") A( "+t} A{"+~)~ k, n E N 0. (146) k + l ~ "~k \ ' - ' k } V k ~ ' ' ' ~ " ' k 1}
Thus, it is difficult to find out which is the most "natural" way to iterate a given basic transformation. For instance, Weniger [24] gives three different algorithms which have been derived by iterating the basic transformation p~./. Two of these three methods seem to be computationally unattractive, and only the third variant has similar properties as the parent, Wynn's p algorithm.
We now show that the iterated Aitken process (5) corresponds to a particular choice of a hierarchy and, thus, it can be described within the framework of the J transformation. We rewrite the iterated Aitken process as
d { " ) = a(k")
k + l ~ " ~ k } A~2{k")
f~{") A ,,-~r k + l ~ "- '~~ k + l "
(147a)
(147b)
(147c)
This may be compared directly to the definition (24) of the J transformation. This shows that the iterated Aitken process corresponds to the choice
(n) 2 (n)
^ _.,(,)ira .~(,+l) l (148) /---x,~ k J [z,-x,-s'~ k j
in the J transformation upon the identifications As. = w., f~(k")= w~ k), and rick"/ = s~ k/. Since the kernel of the J transformation is known in terms of the 6~ k7 - see equation (102) - we immediately obtain an expression for the kernel of the iterated Aitke~/process. However, this expression depends on the values of the transforms ~r �9 In that respect our expression for the kernel is similar to that given by Hillion [14].
Interestingly, Weniger [24] considered the basic sequence transformation
[As.+,] g, = s,+l , (149)
0") .+2 - - 0")n+ 1
which, apart from a shift of indices, is identical to the basic transformation (13):
g. ' (150) Sn+ 1 .
The basic transformation (149) can be combined with the remainder estimate w. = As._~ which reproduces the A z method of Aitken (compare also equations (5.1-4) and (5.1-6) of [23]). With the alternative choice w. = (n +/3)As._1 in equa- tion (149), Weniger [24] derived several new iterative sequence transformations of
(n) (n+O O) o",,,(") ,,,,C"+~/ f~ (~)[.,'X.~.,, ] [ / "~k ] ~ k + l = ~ " k fk(.+0 (~)[A~Ck.+,) ] _ f~.) (r/)[A~(k.) ] . (151b)
Here, 77 > 0 is some parameter. By proceeding in the same way but using the basic transformation (13), we obtain slightly different algorithms of the form
Z~ ") = s., (152a)
(n) (.) (n) 7(") = Z(k")_ fk (~)[mZk ][AZk ] ~ k + 1 (n+l) _ \ rA , - / ( n + I ) I . (152b)
f~ ( . ) t ~ k I - f (n) (B)[AZ~ ") ]
This can be rewritten as
Z~ " / = s., ~./=f0~./(r/)[As.], (153a)
z("' = z ? k+l A~,~(n ) AZ~ "), (1538)
k+ l - -Jk+l
As in the case of the iterated Aitken process, one may compare this to the definition (24) of the J transformation. This shows that these slightly modified iterative sequence transformations Z~k ") correspond to the choice
r r(") (r/)AZ~+),] { fkC"+ 0 (Z/) [AZ~"+0] _ ~"/(r/) [AZCk"/] } •(k) ~ . t J k + l (154)
(n+l) _~ r A , 7 ( n + l ) l g-(n) 1 ~ r A T ( n ) 1 f~ (q)t ' '~k J.lk ~q)t' '~k J
in the J transformation upon the identifications f0 c") (~)[As.] = w., ~2Ck "/ = wC. kl, and Z/"l~ = s~ k/. Obviously, also for these modified iterative sequence transformations Ztk "/ the kernel is available but - as in the case of the iterated Aitken process - it depends on the transforms itself.
We remark that instead of modifying the algorithms to be in agreement with equation (13) one could have also developed modified J transformations based on other simple transformations like p~") [27] or equation (149) instead of equation (13) but using also the method of hierarchical consistency as a heuristic tool. Work along these lines is in progress.
The method of hierarchical consistency provides a new, more general approach to the construction and efficient use of iterative sequence transformations. It is hoped that - similarly to the concept of the perfect estimation of the error [4] - the notion of hierarchical consistency will provide additional insight regarding the concepts of convergence acceleration, extrapolation, and summation processes.
I t h a n k Dr . E.J. Wen ige r for m a n y useful discussions, and Prof . Dr . C. Brezinski fo r c o m m e n t s and several prepr in ts . I am gra teful to Prof . Dr . E.O. S te inborn for his s u p p o r t and the excel lent work ing cond i t ions at Regensburg . H e lp o f the s taff o f the c o m p u t i n g cent re o f the Univers i ty o f Regensburg , n o t a b l y o f the local T E X exper t M. Midd le ton , is thankfu l ly acknowledged .
References
[1] A.C. Aitken, On Bernoulli's numerical solution of algebraic equations, Proc. Roy. Soc. Edinburgh 46 (1926) 289-305.
[2] P. Bjorstad, G. Dahlquist and E. Grosse, Extrapolation of asymptotic expansions by a modified 62 formula, BIT 21 (1981) 56-65.
[3] C. Brezinski, A general extrapolation algorithm, Numer. Math. 35 (1980) 175-180. [4] C. Brezinski, A new approach to convergence acceleration methods, in: Nonlinear Numerical
Methods and Rational Approximation, ed. A. Cuyt (Reidel, Dordrecht, 1988) pp. 373-405. [5] C. Brezinski, Quasi-linear extrapolation processes, in: Numerical Mathematics, Singapore
1988, eds. R.P. Agarval et al., International Series of Numerical Mathematics, Vol. 86 (Birkh/iuser, Basel, 1988) pp. 373-405.
[6] C. Brezinski and A.C. Matos, A derivation of extrapolation algorithms based on error estimates, Publication ANO-319, Universit6 de Lille (1993), J. Comput. Appl. Math., to appear.
[7] C. Brezinski and M. Redivo Zaglia, Extrapolation Methods. Theory and Practice (North- Holland, Amsterdam, 1991).
[8] C. Brezinski and M. Redivo Zaglia, A general extrapolation procedure revisited, Publication ANO-306, Universit~ de Lille (1993), Adv. Comput. Math., to appear.
[9] C. Brezinski and M. Redivo Zaglia, On the kernel of sequence transformations, Publication ANO-309, Universit6 de Lille (1993), Appl. Numer. Math., to appear.
[10] C. Brezinski and G. Walz, Sequences of transformations and triangular recursion schemes, with applications in numerical analysis, J. Comput. Appl. Math. 34 (1991) 361-383.
[11] J.P. Delahaye and B. Germain-Bonne, Rrsultats n~gatifs en accrlrration de la convergence, Numer. Math. 35 (1980) 443-457.
[12] W.F. Ford and A. Sidi, An algorithm for a generalization of the Richardson extrapolation process, SIAM J. Numer. Anal. 24 (1988) 1212-1232.
[13] B. Germain-Bonne, Transformations de suites, Rev. Frangaise Automat. Rech. Operat. 7 (R-I) (1973) 84-90.
[14] P. Hillion, Mrthode d'Aitken itrrre pour les suites oscillantes d'approximations, C.R. Acad. Sci. Paris A 280 (1975) 1701-1704.
[15] H.H.H. Homeier, Some applications of nonlinear convergence accelerators, Int. J. Quantum Chem. 45 (1993) 545-562.
[16] H.H.H. Homeier, Analytical and numerical studies of the convergence behavior of the J transformation, J. Comput. Appl. Math., submitted.
[17] H.H.H. Homeier, Determinantal representations for the ag transformation, Numer. Math., submitted. [18] T. Havie, Generalized Neville type extrapolation schemes, BIT 19 (1979) 204-213. [19] D. Levin, Development of non-linear transformations for improving convergence of sequences,
Int. J. Comput. Math. B 3 (1973) 371-388. [20] A. Sidi, An algorithm for a special case of a generalization of the Richardson extrapolation
[21] D.A. Smith and W.F. Ford, Acceleration of linear and logarithmic convergence, SIAM J. Numer. Anal. 16 (1979) 223-240.
[22] J. Stoer, Einffihrung in die Numerische Mathematik I (Springer, Berlin, 1983). [23] E.J. Weniger, Nonlinear sequence transformations for the acceleration of convergence and the
summation of divergent series, Comput. Phys. Rep. 10 (1989) 189-373. [24] E.J. Weniger, On the derivation of iterated sequence transformations for the acceleration of
convergence and the summation of divergent series, Comput. Phys. Commun. 64 (1991) 19-45. [25] E.J. Weniger, Interpolation between sequence transformations, Numer. Algor. 3 (1992) 477-486. [26] J. Wimp, Sequence Transformations and Their Applications (Academic Press, New York, 1981). [27] P. Wynn, On a Procrustean technique for the numerical transformation of slowly convergent
sequences and series. Proc. Cambridge Phil. Soc. 52 (1956) 663-671.
