<<

. 19
( 83 .)



>>

± 
 
k
Pk = cj z j | z ∈ C; (c0 ; : : : ; ck ) ∈ Kk+1
P:z’ : (17)
 
j=0

Sequences:
SK = {{{s0 ; s1 ; : : : ; sn ; : : :}} | sn ∈ K; n ∈ N0 }: (18)
Sequences with nonvanishing terms:
OK = {{{s0 ; s1 ; : : : ; sn ; : : :}} | sn = 0; sn ∈ K; n ∈ N0 }: (19)

2.1.2. Special functions and symbols
Gamma function [58, p. 1]:

t z’1 exp(’t) dt
(z) = (z ∈ R+ ): (20)
0

Factorial:
n
n! = (n + 1) = j: (21)
j=1
86 H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81“147


Pochhammer symbol [58, p. 2]:
n
(a + n)
(a)n = = (a + j ’ 1): (22)
(a) j=1

Binomial coe cients [1, p. 256, Eq. (6.1.21)]:
(z + 1)
z
= : (23)
w (w + 1) (z ’ w + 1)
Entier function:
<x= = max{j ∈ Z: j6x; x ∈ R}: (24)

2.2. Sequences, series and operators

2.2.1. Sequences and series
For Stieltjes series see Appendix A.
Scalar sequences with elements sn , tail Rn , and limit s:
{{sn }} = {{sn }}∞ = {{s0 ; s1 ; s2 ; : : :}} ∈ SK ; Rn = sn ’ s; lim sn = s: (25)
n=0 n’∞

If the sequence is not convergent but summable to s; s is called the antilimit. The nth element sn
of a sequence = {{sn }} ∈ SK is also denoted by n . A sequence is called a constant sequence,
if all elements are constant, i.e., if there is a c ∈ K such that sn = c for all n ∈ N0 , in which case
it is denoted by {{c}}. The constant sequence {{0}} is called the zero sequence.
Scalar series with terms aj ∈ K, partial sums sn , tail Rn , and limit=antilimit s:
∞ n ∞
s= aj ; sn = aj ; Rn = ’ aj = sn ’ s: (26)
j=0 j=0 j=n+1

We say that an are Kummer-related to the an with limit or antilimit s if an = sn’1 satisfy an ∼ an
ˆ ˆ ˆ ˆ ˆ
n
for n ’ ∞ and s is the limit (or antilimit) of sn = j=0 aj .
ˆ ˆ ˆ
Scalar power series in z ∈ C with coe cients cj ∈ K, partial sums fn (z), tail Rn (z), and
limit/antilimit f(z):
∞ n ∞
j j
cj z j = f(z) ’ fn (z):
f(z) = cj z ; fn (z) = cj z ; Rn (z) = (27)
j=0 j=0 j=n+1


2.2.2. Types of convergence
Sequences {{sn }} satisfying the equation
lim (sn+1 ’ s)=(sn ’ s) = (28)
n’∞

are called linearly convergent if 0 ¡ | | ¡ 1, logarithmically convergent for = 1 and hyperlinearly
convergent for = 0. For | | ¿ 1, the sequence diverges.
A sequence {{un }} accelerates a sequence {{vn }} to s if
lim (un ’ s)=(vn ’ s) = 0: (29)
n’∞

If {{vn }} converges to s then we also say that {{un }} converges faster than {{vn }}.
H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81“147 87


A sequence {{un }} accelerates a sequence {{vn }} to s with order ¿ 0 if
(un ’ s)=(vn ’ s) = O(n’ ): (30)
If {{vn }} converges to s then we also say that {{un }} converges faster than {{vn }} with order .

2.2.3. Operators
Annihilation operator: An operator A: SK ’ K is called an annihilation operator for a given
sequence {{ n }} if it satisÿes
for all {{sn }} ∈ SK ; {{tn }} ∈ SK ; z ∈ K;
A({{sn + ztn }}) = A({{sn }}) + zA({{tn }})
A({{ n }}) = 0: (31)
Forward di erence operator.
m g(m) = g(m + 1) ’ g(m); m gm = gm+1 ’ gm ;
k k’1
m= mm;

= n;
k
k
k
(’1)k’j
gn = gn+j : (32)
j
j=0

(k) (k)
Generalized di erence operator n for given quantities = 0:
n
(k) (k) ’1
n = ( n) : (33)
˜ (k) (k)
Generalized di erence operator  n for given quantities = 0:
n

˜ (k) (k) ’1 2
n = ( n) : (34)
(k) (k)
Generalized di erence operator n[ ] for given quantities = 0:
n
(k) (k) ’1
[ ]fn = ( n ) (fn+2 ’ 2 cos fn+1 + fn ): (35)
n
(k)
Generalized di erence operator @n [ ] for given quantities ˜ n = 0:
(k)

(k)
@n [ ]fn = ( ˜ n )’1 ( (2) (1) (0)
(k)
n+k fn+2 + n+k fn+1 + n+k fn ): (36)
Weighted di erence operators for given P (k’1) ∈ Pk’1 :
Wn = Wn [P (k’1) ] =
(k) (k) (k)
P (k’1) (n): (37)
(k)
k
Polynomial operators P for given P (k) ∈ P(k) : Let P (k) (x) = pj xj . Then put
j=0

k
(k)
(k)
P[P ]gn = pj gn+j : (38)
j=0

Divided di erence operator. For given {{x n }} and k; n ∈ N0 , put
k k
1
(k) (k)
n [{{x n }}](f(x)) = n (f(x)) = f[x n ; : : : ; x n+k ] = f(x n+j ) ;
x n+j ’ x n+i
j=0 i=0
i=j
88 H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81“147

k k
1
(k) (k)
n [{{x n }}]gn = n gn = gn+j : (39)
x n+j ’ x n+i
j=0 i=0
i=j




3. Some basic sequence transformations

3.1. E Algorithm

Putting for sequences {{yn }} and {{gj (n)}}; j = 1; : : : ; k
yn · · · yn+k
g1 (n) · · · g1 (n + k)
(k)
En [{{yn }}; {{gj (n)}}] = ; (40)
. .
..
. .
.
. .
gk (n) · · · gk (n + k)
one may deÿne the sequence transformation
(k)
En [{{sn }}; {{gj (n)}}]
(k)
En ({{sn }}) = (k) : (41)
En [{{1}}; {{gj (n)}}]
(k)
As is plain using Cramer™s rule, we have En ({{ n }}) = if the n satisfy Eq. (10). Thus, the
sequence transformation yields the limit exactly for model sequences (10).
The sequence transformation E is known as the E algorithm or also as Brezinski“Havie“Protocol
[102, Section 10] after two of its main investigators, Havie [32] and Brezinski [9]. A good intro-
duction to this transformation is also given in the book of Brezinski and Redivo Zaglia [14, Section
2.1], cf. also Ref. [15].
(k)
Numerically, the computation of the En ({{sn }}) can be performed recursively using either the
algorithm of Brezinski [14, p. 58f ]
(n)
(0)
En ({{sn }}) = sn ; g0; i = gi (n); n ∈ N0 ; i ∈ N;
(k’1) (k’1)
E(n+1) ({{sn }}) ’ En ({{sn }}) (n)
(k) (k’1)
En ({{sn }}) = En ({{sn }}) ’ gk’1; k ;
(n+1) (n)
gk’1; k ’ gk’1; k
(n+1) (n)
gk’1; i ’ gk’1; i
(n) (n) (n)
gk; i = gk’1; i ’ gk’; 1; k ; i = k + 1; k + 2; : : : (42)
(n+1) (n)
gk’1; k ’ gk’; 1; k
or the algorithm of Ford and Sidi [22] that requires additionally the quantities gk+1 (n+j); j =0; : : : ; k
(k)
for the computation of En ({{sn }}). The algorithm of Ford and Sidi involves the quantities
(k)
En [{{un }}; {{gj (n)}}]
k; n (u) = (43)
(k)
En [{{gk+1 (n)}}; {{gj (n)}}]
for any sequence {{u0 ; u1 ; : : :}}, where the gi (n) are not changed even if they depend on the un and
the un are changed. Then we have
(n)
k (s)
(k)
En ({{sn }}) = (44)
(n)
k (1)
H.H.H. Homeier / Journal of Computational and Applied Mathematics 122 (2000) 81“147 89


and the are calculated recursively via
k’1; n+1 (u) ’ k’1; n (u)
k; n (u) = : (45)
k’1; n+1 (gk+1 ) ’ k’1; n (gk+1 )
Of course, for gj (n) = !n j’1 (n), i.e., in the context of sequences modelled via expansion (5),
the E algorithm may be used to obtain an explicit representation for any Levin-type sequence
transformation of the form (cf. Eq. (9))
(k)
Tn = T (sn ; : : : ; sn+k ; !n ; : : : ; !n+k ; j (n); : : : ; j (n + k)) (46)
as ratio of two determinants
(k)
En [{{sn =!n }}; {{ j’1 (n)}}]
(k)
Tn ({{sn }}; {{!n }}) = (k) : (47)
En [{{1=!n }}; {{ j’1 (n)}}]
This follows from the identity [14]
(k) (k)
En [{{sn }}; {{!n j’1 (n)}}] En [{{sn =!n }}; {{ j’1 (n)}}]
= (k) ; (48)
(k)
En [{{1}}; {{!n j’1 (n)}}] En [{{1=!n }}; {{ j’1 (n)}}]
that is an easy consequence of usual algebraic manipulations of determinants.

3.2. The d(m) transformations

As noted in the introduction, the d(m) transformations were introduced by Levin and Sidi [54] as
a generalization of the u variant of the Levin transformation [53]. We describe a slightly modiÿed
variant of the d(m) transformations [77]:
Let sr ; r = 0; 1; : : : be a real or complex sequence with limit or antilimit s and terms a0 = s0 and
ar = sr ’ sr’1 ; r = 1; 2; : : : such that sr = r aj ; r = 0; 1; : : : . For given m ∈ N and l ∈ N0 with
r=0
l ∈ N0 and 06 0 ¡ 1 ¡ 2 ¡ · · · and = (n1 ; : : : ; nm ) with nj ∈ N0 the d(m) transformation yields
a table of approximations s(m; j) for the (anti-)limit s as solution of the linear system of equations

<<

. 19
( 83 .)



>>