156 K. Jbilou, H. Sadok / Journal of Computational and Applied Mathematics 122 (2000) 149â€“165
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
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
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  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 ) that
âˆ€n; ek (x n ) = x â‡” âˆƒa0 ; : : : ; ak with ak = 0 and a0 + Â· Â· Â· + ak = 0 such that âˆ€n;
ai (x n+i âˆ’ x) = 0:
To implement Shankâ€™s transformation without computing determinants, Wynn  discovered a
simple recursion called the scalar epsilon algorithm (SEA) deÃ¿ned by
= 0; = x n ; n = 0; 1; : : : ;
k+1 = kâˆ’1 + (n+1) k; n = 0; 1; : : : :
The scalar -algorithm is related to Shanksâ€™s transformation by
= ek (x n ) and = :
ek ( x n )
For more details and properties of SEA, see  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  is to use the inverse deÃ¿ned by
z âˆ’1 = ; z âˆˆ RN :
Therefore, for vector sequences (sn ) the vector -algorithm of Wynn is deÃ¿ned by
= 0; = sn ; n = 0; 1; : : : ;
(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  that if âˆ€nÂ¿N0 ; k ai (sn+i âˆ’ s) = 0, with ak = 0
and a0 + Â· Â· Â· + ak = 0, then 2k = s; âˆ€nÂ¿N0 . This result has been proved by Graves-Morris  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
give the solution of the linear system (2.10) that is âˆ€n, 2N = xâˆ— , see . As will be seen in the last
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
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 , 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).
This approach consists in computing approximations ek (sn ) = tk of the limit or the anti-limit of
the sequence (sn ) such that
ai(n) sn+iâˆ’1 ;
tk = sn + nÂ¿0: (3.2)
We consider the new transformations tËœk; j , j = 1; : : : ; k deÃ¿ned by
ai(n) sn+i+jâˆ’1 ;
tËœk; j = sn+j + j = 1; : : : ; k:
We set tËœk; 0 = tk and deÃ¿ne the jth generalized residual as follows:
rj (tk ) = tËœk; j âˆ’ tËœk; jâˆ’1
= sn+jâˆ’1 + sn+i+jâˆ’2 ; j = 1; : : : ; k:
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
(y; r j (tk )) = 0; j = 1; : : : ; k: (3.3)
Hence the vector an = (a1 ; : : : ; ak )T is the solution of the k Ã— k linear system (3:3) which is written
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)
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);
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
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)
Using Schurâ€™s formula, tk can be expressed as a ratio of two determinants
sn Sk; n
tk = det(Tk; n ):
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
a0 + Â· Â· Â· + ak = 0 such that k ai (sn+i âˆ’ s) = 0, then âˆ€n, tk = s.
The vectors ek (sn ) = tk can be recursively computed by the topological -algorithm discovered
by Brezinski 
= 0; = sn ; n = 0; 1; : : : ;
= + ;
2k+1 2kâˆ’1 (n)
(y; 2k )
(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
(n) (n) (n)
= ek (sn ) = tk ; and 2k+1 = ; n; k = 0; 1; : : : :
(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
equal to (z; y). The order of vectors in the scalar product is important, and similar methods have
been studied in detail by Tan .
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)
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 :
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 :
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:
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
. Note that the kth approximation deÃ¿ned by TEA exists if and only if the k Ã— k matrix LT A Sk
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