<<

. 37
( 83 .)



>>

sj+1 = G(sj ); j = 0; 1; : : : : (2.21)
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
( 83 .)



>>