<<

. 28
( 83 .)



>>

adapted to the problem.
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
sequence transformations. See also Section 9.


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



>>