ñòð. 37 |

156 K. Jbilou, H. Sadok / Journal of Computational and Applied Mathematics 122 (2000) 149â€“165

Note that

r(sj ) = r(sj ) =

Ëœ sj ; j=; 1; : : : :

As for linear problems, it is more useful to run some basic iterations before the application of an

extrapolation method for solving (2.20). Note also that the storage and the evaluation of the function

G increase with the iteration step k. So, in practice, it is recommended to restart the algorithms after

a Ã¿xed number of iterations. Another important remark is the fact that the extrapolation methods are

more e cient if they are applied to a preconditioned nonlinear system

Ëœ

G(x) = x; (2.22)

Ëœ

where the function G is obtained from G by some preconditioning nonlinear technique.

An extrapolation algorithm for solving the nonlinear problem (2.22) is summarized as follows:

1. k = 0, choose x0 and the integers p and m.

2. Basic iteration

set t0 = x0

w 0 = t0

Ëœ

wj+1 = G(wj ), j = 0; : : : ; p âˆ’ 1.

3. Extrapolation phase

s0 = wp ;

if ||s1 âˆ’ s0 || Â¡ stop;

Ëœ

otherwise generate sj+1 = G(sj ), j = 0; : : : ; m,

compute the approximation tm by RRE, MPE or MMPE;

4. set x0 = tm , k = k + 1 and go to 2.

As for systems of linear equations, e cient computation of the approximation tm produced by

RRE, MPE and MMPE have been derived in [32,19]. These implementations give as an estimation

of the residual norm at each iteration and it allows to stop the algorithms without having to compute

Ëœ

the true residual which requires an extra evaluation of the function G.

Important properties of vector extrapolation methods is the fact that they do not use the knowledge

Ëœ

of the Jacobian of the function G and have a quadratic convergence (when they are used in their

complete form).

We also note that the results of Theorem 1 are still valid for nonlinear problems by replacing in

the relations of this theorem the residual rk by the generalized residual r k .

Ëœ

Vector extrapolation methods such as MMPE can also be used for computing eigenelements of a

matrix [16].

3. The U-algorithms

3.1. The scalar -algorithm

Let (x n ) be a scalar sequence and consider the Hankel determinant

K. Jbilou, H. Sadok / Journal of Computational and Applied Mathematics 122 (2000) 149â€“165 157

xn : : : x n+kâˆ’1

. . .

. . .

Hk (x n ) = ; with H0 (x n ) = 0; âˆ€n:

. . .

x n+kâˆ’1 : : : x n+2kâˆ’2

Shanksâ€™s transformation [31] ek is deÃ¿ned by

Hk+1 (x n )

ek (x n ) = : (3.1)

Hk ( 2 x n )

For the kernel of the transformation ek , it was proved (see [6]) that

âˆ€n; ek (x n ) = x â‡” âˆƒa0 ; : : : ; ak with ak = 0 and a0 + Â· Â· Â· + ak = 0 such that âˆ€n;

k

ai (x n+i âˆ’ x) = 0:

i=0

To implement Shankâ€™s transformation without computing determinants, Wynn [39] discovered a

simple recursion called the scalar epsilon algorithm (SEA) deÃ¿ned by

(n) (n)

= 0; = x n ; n = 0; 1; : : : ;

âˆ’1 0

1

(n) (n+1)

k+1 = kâˆ’1 + (n+1) k; n = 0; 1; : : : :

(n)

âˆ’k

k

The scalar -algorithm is related to Shanksâ€™s transformation by

1

(n) (n)

= ek (x n ) and = :

2k 2k+1

ek ( x n )

For more details and properties of SEA, see [6] and the references therein. For vector sequences

(sn ), one can apply the scalar -algorithm to each component of sn . However, one disadvantage of

this technique is that it ignores the connexions between the components. Another problem is the fact

that some transformed components fail to exist or may be very large numerically. These drawbacks

limit the application of SEA to vector sequences.

3.2. The vector -algorithm

In order to generalize the scalar -algorithm to the vector case, we have to deÃ¿ne the inverse of

a vector. One possibility that was considered by Wynn [40] is to use the inverse deÃ¿ned by

z

z âˆ’1 = ; z âˆˆ RN :

||z||2

Therefore, for vector sequences (sn ) the vector -algorithm of Wynn is deÃ¿ned by

(n) (n)

= 0; = sn ; n = 0; 1; : : : ;

âˆ’1 0

(n) (n+1) (n+1) (n) âˆ’1

= +[ âˆ’ k] ; k; n = 0; 1; : : : :

k+1 kâˆ’1 k

For the real case, it was proved by McLeod [23] that if âˆ€nÂ¿N0 ; k ai (sn+i âˆ’ s) = 0, with ak = 0

i=0

(n)

and a0 + Â· Â· Â· + ak = 0, then 2k = s; âˆ€nÂ¿N0 . This result has been proved by Graves-Morris [13] in

the complex case.

158 K. Jbilou, H. Sadok / Journal of Computational and Applied Mathematics 122 (2000) 149â€“165

When applied to the vector sequence generated by (2.12), the scalar and the vector -algorithms

(n)

give the solution of the linear system (2.10) that is âˆ€n, 2N = xâˆ— , see [6]. As will be seen in the last

(n)

section, the intermediate quantities 2k , k Â¡ N , are approximations of the solution xâˆ— .

We note also that the vector -algorithm has been used for solving nonlinear problems by applying

it to the nonlinear sequence deÃ¿ned by (2.21); see [7,12].

However, the vector -algorithm requires higher work and storage as compared to the vector

(n)

polynomial methods described in Section 2. In fact, computing the approximation 2k needs the terms

sn ; : : : ; sn+2k which requires a storage of 2k + 1 vectors of RN while the three methods (RRE, MPE

and MMPE) require only k + 2 terms sn ; : : : ; sn+k+1 . Computational work and storage requirements

are given in Section 4.

3.3. The topological -algorithm

In [3], Brezinski proposed another generalization of the scalar -algorithm for vector sequences

which is quite di erent from the vector -algorithm and was called the topological -algorithm (TEA).

(n)

This approach consists in computing approximations ek (sn ) = tk of the limit or the anti-limit of

the sequence (sn ) such that

k

(n)

ai(n) sn+iâˆ’1 ;

tk = sn + nÂ¿0: (3.2)

i=1

We consider the new transformations tËœk; j , j = 1; : : : ; k deÃ¿ned by

k

(n)

ai(n) sn+i+jâˆ’1 ;

tËœk; j = sn+j + j = 1; : : : ; k:

i=1

(n) (n)

We set tËœk; 0 = tk and deÃ¿ne the jth generalized residual as follows:

(n) (n)

Ëœ (n)

rj (tk ) = tËœk; j âˆ’ tËœk; jâˆ’1

k

ai(n) 2

= sn+jâˆ’1 + sn+i+jâˆ’2 ; j = 1; : : : ; k:

i=1

(n)

Therefore, the coe cients involved in expression (3.2) of tk are computed such that each jth

generalized residual is orthogonal to some chosen vector y âˆˆ RN , that is

Ëœ (n)

(y; r j (tk )) = 0; j = 1; : : : ; k: (3.3)

(n) (n)

Hence the vector an = (a1 ; : : : ; ak )T is the solution of the k Ã— k linear system (3:3) which is written

as

T

Tk; n an = Sk; n y; (3.4)

where Tk; n is the matrix whose columns are 2 Sk; n y; : : : ; 2 Sk; n+kâˆ’1 y (assumed to be nonsingular)

T T

and j Sk; n , j = 1; 2 are the N Ã— k matrices whose columns are j sn ; : : : ; j sn+kâˆ’1 , j = 1; 2.

Note that the k Ã— k matrix Tk; n is also given by the formula

Tk; n = Sk; n (IN âŠ— y);

2T 2T

where Sk; n is the k Ã— Nk matrix whose block columns are Sk; n ; : : : ; Sk; n+kâˆ’1 .

K. Jbilou, H. Sadok / Journal of Computational and Applied Mathematics 122 (2000) 149â€“165 159

(n)

Invoking (3.2) and (3:4), tk can be expressed in a matrix form as

(n) âˆ’1 T

tk = sn âˆ’ Sk; n Tk; n Sk; n y: (3.5)

(n)

Using Schurâ€™s formula, tk can be expressed as a ratio of two determinants

sn Sk; n

(n)

tk = det(Tk; n ):

T

Sk; n y Tk; n

For the kernel of the topological -algorithm it is easy to see that if âˆ€n; âˆƒa0 ; : : : ; ak with ak = 0 and

(n)

a0 + Â· Â· Â· + ak = 0 such that k ai (sn+i âˆ’ s) = 0, then âˆ€n, tk = s.

i=0

(n)

The vectors ek (sn ) = tk can be recursively computed by the topological -algorithm discovered

by Brezinski [3]

(n) (n)

= 0; = sn ; n = 0; 1; : : : ;

âˆ’1 0

y

(n) (n+1)

= + ;

2k+1 2kâˆ’1 (n)

(y; 2k )

(n)

(n) (n+1) 2k

= + n; k = 0; 1; : : : :

2k+2 2k (n) (n)

( 2k+1 ; 2k )

The forward di erence operator acts on the superscript n and we have

y

(n) (n) (n)

= ek (sn ) = tk ; and 2k+1 = ; n; k = 0; 1; : : : :

2k

(y; ek ( sn ))

We notice that, for the complex case, we can use the product (y; z) = N yi z i , hence (y; z) is not

i=1

equal to (z; y). The order of vectors in the scalar product is important, and similar methods have

been studied in detail by Tan [37].

3.4. Application of VEA and TEA to linear and nonlinear systems

Consider again the system of linear equations (2.10) and let (sn ) be the sequence of vectors

generated by the linear process (2.12).

Using the fact that 2 sn+i = B 2 sn+iâˆ’1 , the matrix Tk; n has now the following expression:

Tk; n = âˆ’LT A Sk; n ; (3.6)

k

kâˆ’1

where Lk is the N Ã— k matrix whose columns are y; BT y; : : : ; BT y. As n will be a Ã¿xed integer,

we set n = 0 for simplicity and denote Tk; 0 by Tk and Sk; 0 by Sk .

On the other hand, it is not di cult to see that

Sk y = LT r0 :

T

(3.7)

k

Therefore, using (3.6), (3.7) with (3.5), the kth residual produced by TEA is given by

rk = r0 âˆ’ A Sk (LT A Sk )âˆ’1 LT r0 :

tea

(3.8)

k k

Let Ek denotes the oblique projector onto the Krylov subspace Kk (A; Ar0 ) and orthogonally to the

Krylov subspace Kk (BT ; y) = Kk (AT ; y). Then from (3.8) the residual generated by TEA can be

written as follows:

tea

rk = r0 âˆ’ Ek r0 : (3.9)

160 K. Jbilou, H. Sadok / Journal of Computational and Applied Mathematics 122 (2000) 149â€“165

This shows that the topological -algorithm is mathematically equivalent to the method of Lanczos

[4]. Note that the kth approximation deÃ¿ned by TEA exists if and only if the k Ã— k matrix LT A Sk

k

is nonsingular.

The following result gives us some relations satisÃ¿ed by the residual norms in the case where

y = r0 .

Theorem 2. Let â€™k be the acute angle between r0 and Ek r0 and let y = r0 . Then we have the

following relations:

tea

ñòð. 37 |