ñòð. 28 |

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 |