<< Ïðåäûäóùàÿ ñòð. 28(èç 83 ñòð.)ÎÃËÀÂËÅÍÈÅ Ñëåäóþùàÿ >>
This is, of course, a mathematically promising approach. A good example for the two-step approach
is the derivation of the d(m) transformations by Levin and Sidi [54] (cf. also Section 3.2).
But there are two di culties with this approach.
The Ã¿rst di culty is a practical one. In many cases, the problems to be treated in applications
are simply too complicated to allow to perform Step 1 of the two-step approach.
The second di culty is a more mathematical one. The optimal system of functions fj (n) used in
the asymptotic expansion
âˆž
sn âˆ’ s âˆ¼ cj fj (n) (233)
j=0

with fj+1 (n) = o(fj (n)), i.e., the optimal asymptotic scale [102, p. 2], is not clear a priori. For
instance, as the work of Weniger has shown, sequence transformations like the Levin transformation
that are based on expansions in powers of 1=n, i.e., the asymptotic scale j (n) = 1=(n + Ã¿) j , are not
always superior to, and even often worse than those based upon factorial series, like Wenigerâ€™s S
H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81â€“147 119

transformation that is based on the asymptotic scale j (n)=1=(n+Ã¿)j . To Ã¿nd an optimal asymptotic
scale in combination with nonlinear sequence transformations seems to be an open mathematical
problem.
Certainly, the proper choice of remainder estimates [50] is also crucial in the context of Levin-type

6. Properties of Levin-type transformations

6.1. Basic properties

Directly from the deÃ¿nition in Eqs. (65) and (66), we obtain the following theorem. The proof
is left to the interested reader.

Theorem 5. Any Levin-type sequence transformation T is quasilinear; i.e.; we have
(k) (k)
Tn ({{Asn + B}}; {{!n }}) = ATn ({{sn }}; {{!n }}) + B (234)
for arbitrary constants A and B. It is multiplicatively invariant in !n ; i.e.; we have
(k) (k)
Tn ({{sn }}; {{C!n }}) = Tn ({{sn }}; {{!n }}) (235)
for arbitrary constants C = 0.

deÃ¿ne the sets Yn(k) [ ] by
For a coe cient set
ï£± ï£¼
ï£² ï£½
k
(k)
Yn(k) [ ] = (x0 ; : : : ; xk ) âˆˆ Fk+1 n; j =xj =0 : (236)
ï£³ ï£¾
j=0

(k)
Since Tn ({{sn }}; {{!n }}) for given coe cient set depends only on the 2k+2 numbers sn ; : : : ; sn+k
and !n ; : : : ; !n+k , it may be regarded as a mapping
Un(k) : Ck+1 Ã— Yn(k) [ ] â‡’ C; (x; y) â†’ Un(k) (x | y) (237)
such that
Tn = Un(k) (sn ; : : : ; sn+k | !n ; : : : ; !n+k ):
(k)
(238)
The following theorem is a generalization of theorems for the J transformation [36, Theorem 5]
and the I transformation [44, Theorem 5].

Theorem 6. (I âˆ’ 0) The T(k) transformation can be regarded as continous mapping Un(k) on Ck+1 Ã—
Yn(k) [ ] where Yn(k) [ ] is deÃ¿ned in Eq. (236):
(I âˆ’ 1) According to Theorem 5; Un(k) is a homogeneous function of Ã¿rst degree in the Ã¿rst
(k + 1) variables and a homogeneous function of degree zero in the last (k + 1) variables. Hence;
for all vectors x âˆˆ Ck+1 and y âˆˆ Yn(k) [ ] and for all complex constants s and t = 0 the equations
Un(k) (sx | y) = sUn(k) (x | y);

Un(k) (x | ty) = Un(k) (x | y) (239)
120 H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81â€“147

hold.
(I âˆ’ 2) Un(k) is linear in the Ã¿rst (k + 1) variables. Thus; for all vectors x âˆˆ Ck+1 ; x âˆˆ Ck+1 ; und
y âˆˆ Yn(k) [ ]
Un(k) (x + x | y) = Un(k) (x | y) + Un(k) (x | y) (240)
holds.
(I âˆ’ 3) For all constant vectors c = (c; c; : : : ; c) âˆˆ Ck+1 and all vectors y âˆˆ Yn(k) [ ] we have
Un(k) (c | y) = c: (241)

Proof. These are immediate consequences of the deÃ¿nitions.

6.2. The limiting transformation
â—¦
â—¦
We note that if a limiting transformation T [ ] exists, it is also of Levin-type, and thus, the
above theorems apply to the limiting transformation as well.
Also, we have the following result for the kernel of the limiting transformation:

Theorem 7. Suppose that for a Levin-type sequence transformation T(k) of order k there exists a
â—¦
â—¦
limiting transformation T (k) with characteristic polynomial âˆˆ Pk given by
k M
â—¦ â—¦ (k) j
(k) mâ€˜
(z) = jz = (z âˆ’ â€˜) ; (242)
j=0 â€˜=1

where the zeroes â€˜ = 0 have multiplicities mâ€˜ . Then the kernel of the limiting transformation
consists of all sequences {{sn }} with elements of the form
M
n
= + !n â€˜ Pâ€˜ (n); (243)
n
â€˜=1
â—¦
where Pâ€˜ âˆˆ Pmâ€˜ âˆ’1 are arbitrary polynomials and {{!n }} âˆˆY(k) .

Proof. This follows directly from the observation that for such sequences ( n âˆ’ )=!n is nothing
(k)
but a Ã¿nite linear combination of the solutions â€™n; â€˜; jâ€˜ = njâ€˜ â€˜ with â€˜ = 1; : : : ; M and jâ€˜ = 0; : : : ; mâ€˜ âˆ’ 1
n

of the recursion relation
k
â—¦ (k)
j vn+j =0 (244)
j=0

â—¦
(k)
and thus, it is annihilated by P[ ].

6.3. Application to power series

Here, we generalize some results of Weniger [88] that regard the application of Levin-type se-
quence transformations to power series.
H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81â€“147 121

We use the deÃ¿nitions in Eq. (27). Like PadÃƒ approximants, Levin-type sequence transformations
e
yield rational approximants when applied to the partial sums fn (z) of a power series f(z) with terms
aj =cj z j . These approximations o er a practical way for the analytical continuation of power series to
regions outside of their circle of convergence. Furthermore, the poles of the rational approximations
model the singularities of f(z). They may also be used to approximate further terms beyond the
last one used in constructing the rational approximant.
When applying a Levin-type sequence transformation T to a power series, remainder estimates
!n = mn z +n will be used. We note that t variants correspond to mn = cn , = 0, u variants correspond
to mn = cn (n + Ã¿), = 0, tËœ variants to mn = cn+1 , = 1. Thus, for these variants, mn is independent
of z (Case A). For v variants, we have mn = cn+1 cn =(cn âˆ’ cn+1 z), and = 1. In this case, 1=mn âˆˆ P(1)
is a linear function of z (Case B).
Application of T yields after some simpliÃ¿cation
(k)
n+k k
zâ€˜ j=max(0; kâˆ’â€˜) ( n; j =mn+j )câ€˜âˆ’(kâˆ’j)
(k)
Pn [T ](z)
â€˜=0
Tn ({{fn (z)}}; {{mn z +n }})
(k)
= = (k) ; (245)
(k)
k
j=0 ( n; j =mn+j )z Qn [T ](z)
kâˆ’j

where in Case A, we have Pn [T ] âˆˆ Pn+k , Qn [T ] âˆˆ Pk , and in Case B, we have Pn [T ] âˆˆ
(k) (k) (k)

Pn+k+1 ; Qn [T ] âˆˆ Pk+1 . One needs the k + 1 + partial sums fn (z); : : : ; fn+k+ (z) to compute these
(k)

rational approximants. This should be compared to the fact that for the computation of the PadÃƒ e
approximant [n + k + =k + ] one needs the 2k + 2 + 1 partial sums fn (z); : : : ; fn+2k+2 (z).
We show that Taylor expansion of these rational approximants reproduces all terms of power
series that have been used to calculate the rational approximation.

Theorem 8. We have
(k) +n
}}) âˆ’ f(z) = O(z n+k+1+ );
Tn ({{fn (z)}}; {{mn z (246)

where =0 for t and u variants corresponding to mn =cn ; =0; or mn =cn (n+Ã¿); =0; respectively;
while = 1 holds for the v variant corresponding to mn = cn+1 cn =(cn âˆ’ cn+1 z); = 1; and for the tËœ
variants corresponding to mn = cn+1 ; = 1; one obtains = 1 if T is convex.

Proof. Using the identity
(k) +n (k) +n
Tn ({{fn (z)}}; {{mn z }}) = f(z) + Tn ({{fn (z) âˆ’ f(z)}}; {{mn z }}) (247)

that follows from Theorem 5, we obtain after some easy algebra
(k)
âˆž k
â€˜
â€˜=0 z j=0 ( n; j =mn+j )câ€˜+n+j+1
(k) +n
}}) âˆ’ f(z) = z n+k+1
Tn ({{fn (z)}}; {{mn z : (248)
(k)
k
( n; j =mn+j )z kâˆ’j
j=0

This shows that the right-hand side is at least O(z n+k+1 ) since the denominator is O(1) due to
(k) (k)
k
Ëœ (k)
n; k = 0. For the t variant, the term corresponding to â€˜ = 0 in the numerator is j=0 n; j = n (1)
(k)
that vanishes for convex T. For the v variant, that term is k j=0 n; j (cn+j âˆ’cn+j+1 z)=cn+j that simpliÃ¿es
(k)
to (âˆ’z) k j=0 n; j cn+j+1 =cn+j for convex T. This Ã¿nishes the proof.
122 H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81â€“147

7. Convergence acceleration results for Levin-type transformations

7.1. General results

We note that Germain-Bonne [23] developed a theory of the regularity and convergence accelera-
tion properties of sequence transformations that was later extended by Weniger [84, Section 12; 88,
Section 6] to sequence transformations that depend explicitly on n and on an auxiliary sequence of
remainder estimates. The essential results of this theory apply to convergence acceleration of linearly
convergent sequences. Of course, this theory can be applied to Levin-type sequence transformations.
However, for the latter transformations, many results can be obtained more easily and also, one may
obtain results of a general nature that are also applicable to other convergence types like logarith-
mic convergence. Thus, we are not going to use the Germainâ€“Bonneâ€“Weniger theory in the present
article.
Here, we present some general convergence acceleration results for Levin-type sequence transfor-
mations that have a limiting transformation. The results, however, do not completely determine which
transformation provides the best extrapolation results for a given problem sequence since the results
are asymptotic in nature, but in practice, one is interested in obtaining good extrapolation results
from as few members of the problem sequence as possible. Thus, it may well be that transformations
with the same asymptotic behavior of the results perform rather di erently in practice.
Nevertheless, the results presented below provide a Ã¿rst indication which results one may expect
for large classes of Levin-type sequence transformations.
First, we present some results that show that the limiting transformation essentially determines for
which sequences Levin-type sequence transformations are accelerative. The speed of convergence
will be analyzed later.

Theorem 9. Assume that the following asymptotic relations hold for large n:
â—¦ (k) â—¦ (k)
(k)
âˆ¼ j; = 0; (249)
n; j k

A
sn âˆ’ s â—¦
n (k)
âˆ¼ c ; c = 0; ( ) = 0; (250)
!n =1

!n+1 â—¦
(k)
âˆ¼ = 0; (1= ) = 0: (251)
!n
(k)
Then; {{Tn }} accelerates {{sn }} to s; i.e.; we have
(k)
Tn âˆ’ s
lim = 0: (252)
nâ†’âˆž sn âˆ’ s

Proof. Rewriting
(k)
k
n; j (sn+j âˆ’ s)=!n+j
(k)
Tn âˆ’ s !n j=0
= : (253)
(k)
k
 << Ïðåäûäóùàÿ ñòð. 28(èç 83 ñòð.)ÎÃËÀÂËÅÍÈÅ Ñëåäóþùàÿ >>