<<

. 32
( 83 .)



>>



If all are positive then
k
k’1
+| |
j
(k)
lim = ¡∞ (318)
n
| j’ |
n’∞
j=0

holds.

As corollaries, we get the following results

Corollary 24. If the sequence !n+1 =!n possesses a limit according to
lim !n+1 =!n = ∈ {0; 1}; (319)
n’∞

the p J transformation for p ¿ 1 and ÿ ¿ 0 is S-stable and we have
k
k k’j
| |
j
j=0
(1 + | |)k
(k)
lim = = ¡ ∞: (320)
n
|1 ’ |k |1 ’ |k
n’∞



Corollary 25. If the sequence !n+1 =!n possesses a limit according to
lim !n+1 =!n = ∈ {0; 1}; (321)
n’∞

the Weniger S transformation [84; Section 8] for ÿ ¿ 0 is S-stable and we have
k k k’j
| | (1 + | |)k
j=0 j
(k)
lim n (S) = = ¡ ∞: (322)
|1 ’ |k |1 ’ |k
n’∞
134 H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81“147


Corollary 26. If the sequence !n+1 =!n possesses a limit according to
lim !n+1 =!n = ∈ {0; 1}; (323)
n’∞

the Levin L transformation [53; 84] is S-stable and we have
k k k’j
| | (1 + | |)k
j=0 j
(k)
lim n (L) = = ¡ ∞: (324)
|1 ’ |k |1 ’ |k
n’∞



Corollary 27. Assume that the elements of the sequence {tn }n∈N satisfy tn = 0 for all n and tn = tn
for all n = n . If the sequence tn+1 =tn possesses a limit
lim tn+1 =tn = with 0 ¡ ¡ 1 (325)
n’∞

and if the sequence !n+1 =!n possesses a limit according to
’1 ’k
lim !n+1 =!n = ∈ {0; 1; ;:::; ; : : :}; (326)
n’∞

then the generalized Richardson extrapolation process R introduced by Sidi [73] that is identical
(k)
to the J transformation with n = tn ’ tn+k+1 as shown in [36]; i.e.; the W algorithm is S-stable
and we have
˜(k) k’j |
k k’1
j=0 | j
j
1+ ||
(k)
lim n (R) = = ¡ ∞: (327)
k’1
|1 ’ j|
j =0 |
’j ’ |
n’∞
j =0

Here
k’1
(k)
˜ k’j
( )’m jm ;
= (’1) (328)
j
m=0
j0 + j1 + : : : + jk’1 = j;
j0 ∈ {0; 1}; : : : ; jk’1 ∈ {0; 1}

such that
k k’1 k’1
˜(k) k’j ’j ’k(k’1)=2 j
= ( ’ )= (1 ’ ): (329)
j
j=0 j=0 j=0


Note that the preceding corollary is essentially the same as a result of Sidi [78, Theorem 2:2] that
now appears as a special case of the more general Theorem 23 that applies to a much wider class
of sequence transformations. As noted above, Sidi has also derived conditions under which the d(1)
transformation is stable along the paths Pn = {(n; k)|k = 0; 1; : : :} for ÿxed n. For details and more
references see [78]. Analogous work for the J transformation is in progress.
An e cient algorithm for the computation of the stability index of the J transformation can be
given in the case n ¿ 0. Since the J transformation is invariant under n ’ (k) n for any
(k) (k) (k)
(k) (k)
= 0 according to Homeier [36, Theorem 4], n ¿ 0 can always be achieved if for given k, all
(k)
n have the same sign. This is the case, for instance, for the p J transformation [36,39].
H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81“147 135


Theorem 28. Deÿne
(k)
Fn = (’1)n |Dn |;
(0) (0) (k+1) (k) (k)
Fn = (Fn+1 ’ Fn )= (330)
n

ˆ (0) (0) ˆ (k) (0) (k’1) (k) (k)
and F n = Fn ; F n = ( ··· ) Fn . If all ¿ 0 then
n n n

1. Fn = (’1)n+k |Fn |;
(k) (k)
(k) (k)
2. n; j = (’1) j+k | n; j |; and
3.
(k)
ˆ (k)
|F n | |Fn |
(k)
n= = (k) : (331)
(k)
ˆ n | |Dn |
|D

This generalizes Sidi™s method for the computation of stability indices [78] to a larger class of
sequence transformations.


9. Application of Levin-type sequence transformations

9.1. Practical guidelines

Here, we address shortly the following questions:
When should one try to use sequence transformations? One can only hope for good convergence
acceleration, extrapolation, or summation results if (a) the sn have some asymptotic structure for
large n and are not erratic or random, (b) a su ciently large number of decimal digits is available.
Many problems can be successfully tackled if 13“15 digits are available but some require a much
larger number of digits in order to overcome some inevitable rounding errors, especially for the
acceleration of logarithmically convergent sequences. The asymptotic information that is required for
a successful extrapolation is often hidden in the last digits of the problem data.
How should the transformations be applied? The recommended mode of application is that one
computes the highest possible order k of the transformation from the data. In the case of triangular
recursive schemes like that of the J transformation and the Levin transformation, this means that
(n)
one computes as transformed sequence {T0 }. For L-shaped recursive schemes as in the case of the
<n=2=
H, I, and K transformations, one usually computes as transformed sequence {{Tn’2<n=2= }}. The
error of the current estimate can usually be approximated a posteriori using sums of magnitudes
of di erences of a few entries of the T table, e.g.,
(n) (n) (n’1) (n)
≈ |T1 ’ T0 | + |T0 ’ T0 | (332)
for transformations with triangular recursive schemes. Such a simple approach works surprisingly
well in practice. The loss of decimal digits can be estimated computing stability indices. An example
is given below.
What happens if one of the denominator vanishes? The occurrence of zeroes in the D table for
speciÿc combinations of n and k is usually no problem since the recurrences for numerators and
denominators still work in this case. Thus, no special devices are required to jump over such singular
points in the T table.
136 H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81“147


Which transformation and which variant should be chosen? This depends on the type of con-
vergence of the problem sequence. For linearly convergent sequences, t, t˜, u and v variants of the
Levin transformation, or the p J transformation, especially the 2 J transformation are usually a good
choice [39] as long as one is not too close to a singularity or to a logarithmically convergent prob-
lem. Especially well behaved is usually the application to alternating series since then, the stability
is very good as discussed above. For the summation of alternating divergent sequences and series,
usually the t and the t˜ variants of the Levin transformation, the 2 J and the Weniger S and M
transformations provide often surprisingly accurate results. In the case of logarithmic convergence,
t and t˜ variants become useless, and the order of acceleration is dropping from 2k to k when the
transformation is used columnwise. If a Kummer-related series is available (cf. Section 2.2.1), then
K and lu variants leading to linear sequence transformations can be e cient [50]. Similarly, linear
variants can be based on some good asymptotic estimates asy !n , that have to be obtained via a
separate analysis [50]. In the case of logarithmcic convergence, it pays to consider special devices
like using subsequences {{s n }} where the n grow exponentially like n = < n’1 = + 1 like in the
d transformations. This choice can be also used in combination with the F transformation. Alter-
natively, one can use some other transformations like the condensation transformation [51,65] or
interpolation to generate a linearly convergent sequence [48], before applying an usually nonlinear
sequence transformation. A somewhat di erent approach is possible if one can obtain a few terms
an with large n easily [47].
What to do near a singularity? When extrapolating power series or, more generally, sequences
depending on certain parameters, quite often extrapolation becomes di cult near the singularities of
the limit function. In the case of linear convergence, one can often transform to a problem with a
larger distance to the singularity: If Eq. (28) holds, then the subsequence {{s n }} satisÿes
lim (s (n+1) ’ s)=(s n ’ s) = : (333)
n’∞

This is a method of Sidi that has can, however, be applied to large classes of sequence transformations
[46].
What to do for more complicated convergence type? Here, one should try to rewrite the problem
sequence as a sum of sequences with more simple convergence behavior. Then, nonlinear sequence
transformations are used to extrapolate each of these simpler series, and to sum the extrapolation
results to obtain an estimate for the original problem. This is for instance often possible for (gener-
alized) Fourier series where it leads to complex series that may asymptotically be regarded as power
series. For details, the reader is referred to the literature [14,35,40 “ 45,77]. If this approach is not
possible one is forced to use more complicated sequence transformations like the d(m) transformations
or the (generalized) H transformation. These more complicated sequence transformations, however,
do require more numerical e ort to achieve a desired accuracy.

9.2. Numerical examples

In Table 3, we present results of the application of certain variants of the F transformation and
the W algorithm to the series
j’1

1
j
S(z; a) = 1 + z (334)
ln(a + ˜)
j=1 ˜=0
H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81“147 137

Table 3
Comparison of the F transformation and the W algorithm for series (334)a

n An Bn Cn Dn

14 13.16 13.65 7.65 11.13
16 15.46 15.51 9.43 12.77
18 18.01 17.84 11.25 14.43
20 21.18 20.39 13.10 16.12
22 23.06 23.19 14.98 17.81
24 25.31 26.35 16.89 19.53
26 27.87 28.17 18.83 21.26
28 30.83 30.59 20.78 23.00
30 33.31 33.19 22.76 24.76

n En Fn Gn Hn

14 14.07 13.18 9.75 10.47
16 15.67 15.49 11.59 12.05
18 17.94 18.02 13.46 13.66
20 20.48 20.85 15.37 15.29
22 23.51 23.61 17.30 16.95
24 25.66 25.63 19.25 18.62
26 27.89 28.06 21.23 20.31
28 30.46 30.67 23.22 22.02
29 31.82 32.20 24.23 22.89
30 33.43 33.45 25.24 23.75
a

<<

. 32
( 83 .)



>>