The Chebyshev iteration revisited.
Compared to Krylov space methods based on orthogonal or oblique projection, the Chebyshev iteration does not require inner products and is therefore particularly suited for massively parallel computers with high communication cost. Here, six different algorithms that implement this method are presented and compared with respect to roundoff effects, in particular, the ultimately achievable accuracy. Two of these algorithms replace the three-term recurrences by more accurate coupled two-term recurrences and seem to be new. It is also shown that, for real data, the classical three-term Chebyshev iteration is never seriously affected by roundoff, in contrast to the corresponding version of the conjugate gradient method. Even for complex data, strong roundoff effects are seen to be limited to very special situations where convergence is anyway slow.The Chebyshev iteration is applicable to symmetric definite linear systems and to nonsymmetric matrices whose eigenvalues are known to be confined to an elliptic domain that does not include the origin. Also considered is a corresponding stationary 2-step method, which has the same asymptotic convergence behavior and is additionally suitable for mildly nonlinear problems.
Introduction
The Chebyshev iteration [2{4] has been one of the favorite Krylov space methods
for solving a large sparse linear system of equations in a parallel environ-
ment, since, unlike methods based on orthogonalization (such as the conjugate
gradient (CG) and biconjugate gradient (BiCG) methods and GMRes|to
name a few), it does not require to compute communication-intensive inner
products for the determination of the recurrence coecients. Only the monitoring
of the convergence, that is, the determination of the norm of the residuals
requires inner products, and even this norm needs to be evaluated only
occasionally because its time-dependence, that is, the convergence rate, can
be forecast reliably.
The Chebyshev iteration, which in the older literature has often been referred
to as Chebyshev semiiterative method, requires some preliminary knowledge
about the spectrum (A) of the coecient matrix A: an elliptic domain E
(A) with 0 62 E is normally assumed to be known in advance. Denote the
center of the ellipse by , its foci by   c, and the lengths of the large and
the small semi-axes by a and b. When the elliptic domain turns into
a straight line segment (or, c]. At this point, both
and c may be complex. Manteuel [1] devised a technique to determine a
suitable ellipse from a given nonsymmetric matrix.
Mathematically the method can be dened by translating the Chebyshev polynomials
T n from the interval [ 1; 1] to the interval I and scaling them so that
their value at 0 is 1. On R the Chebyshev polynomials are dened by 3
T n is even or odd if n is even or odd, respectively. All three formulas are valid
when we extend the denition to the complex plane, which we will indicate
by using the variable . For example, we may dene
The translated and scaled residual polynomials p n that characterize the Cheby-
3 Denitions are marked by the symbol :, while := is used for algorithmic assign-
ments; often either one of the symbols could be used.
shev iteration are
c
c
If we let x 0 be an initially chosen approximation of the solution of the linear
system b that has to be solved, and if r denotes the
corresponding residual, then, by denition, the nth approximation and residual
The classical case for applying the method is when A is symmetric positive
denite (spd)|as assumed in CG|and, therefore, the interval I lies on the
positive real axis and contains the spectrum of A. In this case Chebyshev iteration
is known to be optimal in the sense that it yields, for every n, the smallest
nth maximum residual if the maximum is taken over all normal matrices with
spectrum on I; see [2{4].
Due to a wrong claim in [5] it has often been assumed that this optimality
also holds for the class of matrices with spectrum inside or on an ellipse
whose foci lie on the positive real axis, but Fischer and Freund [6,7] have
shown that this is not true in general; the exceptional cases are rather ill-
conditioned, however. In any case, for any elliptic compact set not containing
0 the correspondingly chosen Chebyshev iteration is asymptotically optimal,
as its recurrence coecients approach those of a second order Richardson iter-
ation, which is a stationary 2-step method based on conformal mapping [8{11]
and can be viewed as the limit of the Chebyshev iteration; see our discussion
in Section 6.
Of course, in practice we need an algorithm that generates the approximations
recursively. The usual approach is to derive a three-term recurrence from
the standard recursion for the Chebyshev polynomials. However, as has recently
been shown by Gutknecht and Strakos [12], Krylov space methods based
on three-term recursions for iterates and residuals may suer from a large gap
between recursively computed residuals r n and true residuals b Ax n , and,
therefore, may stagnate early with relatively large true residuals. In other
words, the ultimately achievable accuracy may be quite low. In particular,
this eect may even occur when CG is applied to an spd problem.
We will show here that the Chebyshev iteration, even in this implementation,
is not seriously aected by roundo. Moreover, we will discuss ve other implementations
that produce even more accurate solutions, that is, stagnate
ultimately with smaller true residuals. We also point out that the aforementioned
stationary second order Richardson iteration can as well be realized by
six analogous dierent algorithms.
We note that similar analytical techniques have been applied by Golub and
Overton [13] for the analysis of the behavior of the Chebyshev iteration when
a preconditioner is applied inexactly.
iteration with three-term recursion
Recursions for the residuals r n and the iterates x n of the Chebyshev iteration
are easily found from the standard three-term recursions for the classical
Chebyshev polynomials T n ,
The following rst realization of the method results.
Algorithm 1 (Three-term Chebyshev iteration) For solving
choose x 0 and let r 0 := b Ax 0 . Also set r 1 := x 1 := o. Choose the
parameters  and c so that the spectrum of A lies on the straight line segment
c] or on an elliptical domain E with foci   c that does not
contain
and compute, for
r n+1 :=
We cannot expect that a solver produces ultimately a much smaller residual
than what we get when we insert (the machine approximation of) the exact
solution into the denition of the residual: k
(b Ax ? )k. However,
due to the accumulation of rounding errors the achievable accuracy might be
perhaps much lower. Actually, the ultimate accuracy of Algorithm 1 (and
many others) is determined by the size of the gap f n between the updated
(or, recursively computed) residual r n and the true (or, explicitly computed)
residual b Ax
Here x n and r n denote the vectors computed in
oating-point arithmetic from
and (7). In fact, if A satises the spectral assumption, then, normally,
even in
oating-point arithmetic. Thus,
(b Ax n )k  kf n k for large
A general result on this gap for methods updating residuals by three-term
recurrences was given in [12].
Theorem 1 ([12]) Assume iterates and residuals are updated according to
r n+1 :=
where
Then the gap f to
denotes the machine epsilon),
l 0
l 0
. (10)
l 0
l n 1
l
where
is the local error whose components come from
In (10) and (11) the quantities x k , r k ,  k ,  k 1 , and
are those computed in
oating-point arithmetic. If we assume that each row of A contains at most
nonzero elements and that matrix-vector products with A are computed in
the standard way, then for the local error holds componentwise
jbj (j
But more important than the size of the local errors is the size of the potentially
large factors  k
k and of their products in (10). In Algorithm 1, the
factors and their products are (in exact arithmetic)
(0  k <
Strictly speaking, we should consider here the values of  k 1 and
k that are
obtained in
oating-point arithmetic. Then the three relations (12a){(12c) are
only correct up to a roundo error of order O(). However, because we are free
to compute the recurrence coecients at little extra cost in multiple-precision
arithmetic, and since we are only concerned about quotients that are very
large, it seems well justied to neglect these errors here. Otherwise we would
have to analyze the roundo errors in the recursions (4) and (5), or in any
other formulas used to calculate  n 1 and
n .
(as in the case when A is spd), so that  < 1 and jT k
cosh(k arcosh(jj)), we have, since cosh is monotone increasing on the positive
real axis,
and therefore all the factors in (10) are less than 1 if the recurrence coecients
are computed accurately enough. Since l k appears in n k
it may still get amplied by a factor smaller than this is not
too serious, in particular since typically most of the factors are rather small.
Of course, (13) does not hold in general unless  < 1 or  > 1: for example,
we have, for  purely imaginary and of suciently small absolute
value, jT 2k ()j > jT 2n+1 ()j for all k; n 2 N with k; n  m, since jT 2k (0)j 6= 0
but jT 2n+1 in (12b) the index dierence between the numerator
and denominator polynomials is 2 and hence this argument is not applicable.
We show next that also in the other case relevant for real-valued problems,
namely when  2 R but c is purely imaginary (so that the ellipse is still
centered on and symmetric about the real axis), the quotients (12a){(12c) are
all of absolute value smaller than 1.
For any  2 C n[ 1; 1], we let # be the larger solution of the quadratic equation2
Note that the solutions come in pairs # 1 and that implies that
which is excluded by assumption.
Therefore, we may assume that j#j > 1 here. The mapping # 7!  of (14)
is the well-known Joukowski transformation, which allows us to express the
Chebyshev polynomials simply as
In fact, if we let
so that e  clearly, e #, and therefore, if   1,
relation can be seen to be
valid for any  2 C . Consequently, the single factors from (12b) can be written
as
Obviously, these factors are rational functions of both  and #.
It is well-known that T n+1 has n+1 simple zeros in (
(after cancellation of the pole and zero at is even) has at most n+1
poles, and they lie all on ( 1; 1). If considered as a function of #, the quotient
has at most 2(n poles, and they all lie on the unit circle. Clearly, if we
choose  close enough to a pole, but not on [ 1; 1], the quotient can be made
as large as we want. Consequently, as claimed, the factors are in general not
all of absolute value less than 1. So, amplication of a local error is possible.
If 0 < c < , we have seen already that (13) holds, and, by symmetry, the
same is true for 0 > c > . If  is still real, say  > 0, but c 2
since the Joukowski transformation maps the part
above i of the imaginary axis on the positive imaginary axis, we have
with  > 1. Then, from (16) and by setting
e
so that e
the Joukowski transformation maps [1; 1) onto itself),
we obtain
n+1  (n+1)
U
if
Here, U n is the nth Chebyshev polynomial of the second kind. For e
can be expressed as
Noting that sinh is monotone increasing, we can conclude that U n+1 (e ) >
1. As we have seen before, also T n+1 (e
e
> 1. Therefore, also in this situation, the factors
n have an absolute
value smaller than 1. Summarizing, we have proved the following result.
Theorem 2 For an interval [ c;  or an ellipse with foci   c
symmetric about the real axis and not containing the origin, the factors (12a){
(12c), which appear in (10), are of absolute value less than 1 if the recurrence
coecients  k 1 and
k have been computed with sucient accuracy.
In Section 8 we will come back to the question of the size of the factors (12a){
(12c) in the case where the assumptions of this theorem do not hold, that is
when the linear system to be solved is complex and does not have a spectrum
symmetric about the real axis.
Finally we note that a simple way to avoid the residual gap in the Chebyshev
iteration is to replace the recursively computed residuals by explicitly
computed residuals:
Algorithm 2 (Three-term recursion, explicitly computed residuals)
Same as Algorithm 1 except that the recursion (7) for computing r n+1 is replaced
by
This remedy could be applied in many Krylov solvers in order to increase
the ultimate accuracy. However, explicitly computed residuals are known to
slow down the convergence of projection methods like CG and BiCG due to
stronger roundo eects in the Krylov space generation process [14], as they
destroy the local (bi)orthogonality of the bases created. But here, unlike in
these methods, the recurrence coecients ,  n 1 , and
n do not depend on
r n , and therefore the error of r n will only have little in
uence on xm (m > n)
and the convergence of the method.
3 Rutishauser's Chebyshev iteration by updating corrections
The recursions (6) and (7) are of the form (8){(9) with the consistency condition
which implies that r
Subtracting x n and r n , respectively, on both sides of (8) and (9),
using the consistency condition, and setting
yields
This leads to the following reformulation of Algorithm 1.
Algorithm 3 (Chebyshev iteration by updating x n and r n ) Same
as Algorithm 1 except that the recursions (6) and (7) for computing x n+1 and
r n+1 are replaced by (19){(20) and
This is how Rutishauser [4] formulated the Chebyshev iteration and other
Krylov space solvers (which he called \gradient methods"). It is easy to also
modify this scheme so that the residuals are computed explicitly:
Algorithm 4 (Updating x n and explicitly computing r n ) Same as
Algorithm 1 except that the recursions (6) and (7) for computing x n+1 and
r n+1 are replaced by (19), (21), and (18), that is,
Algorithms based on coupled two-term recurrences
For Krylov space solvers based on two-term updates for x n and r n (involving
additionally direction vectors v n ) [15,16],
the gap between updated and true residuals is known to be often much smaller
than for those that update the residuals with three-term recurrences of the
form (8){(9) or even longer ones. It does not matter whether the recursion
long or just two-term as in
because the same possibly inaccurate v n is used in (24) and (25). Examples for
algorithms of the form (24){(25) with (26) are the standard Hestenes-Stiefel
or OMin version of CG and the standard BiOMin version of BiCG.
The above claim about the higher ultimate accuracy of algorithms with two-term
updates (24){(25) is based on a comparison between Theorem 1 and
the following result of Greenbaum [17], which improves on previous similar
statements in [19] and [18]. It explains why the gap between updated and true
residuals is relatively small: here, the gap is just a sum of local errors; these
are not multiplied by any potentially large factors.
Theorem 3 ([17]) Assume iterates and residuals are updated according (24){
(25). Then the gap f between the true and the updated residual
where
is the local error whose components come from
In particular,
where  denotes the machine epsilon,
with m the maximum number
of nonzeros in a row of A, N the order of A, and
kn
5 Chebyshev iteration based on coupled two-term recurrences
Theorem 3 suggest to search for a coupled-two term recursion as an alternative
realization of the Chebyshev method. Recursions (24){(25) call for the
following \Ansatz" in a polynomial formulation:
with
To determine ! n and n we insert (27)
into (28), make use of (28) with n replaced by n 1, and then compare the
result with the polynomial reformulation of (7): if n  1,
| {z }
| {z }
| {z }
We obtain
(n  1);
(n  0); (29)
(n  1); (30)
and, conversely,
(n
(n  0): (31)
just
Like  n 1 and
n we can express ! n and n 1 in terms of the Chebyshev
polynomials and derive recursions for them. First, inserting the left-hand side
equations from (4) and (5) into (31) we see that

Then, inserting the right-hand side equations from (4) and (5) we get
(if n  2);
and
Summarizing we obtain the following coupled two-term Chebyshev iteration
[20].
Algorithm 5 (Coupled two-term Chebyshev iteration) For solving
choose x 0 and let r 0 := b Ax 0 . Choose the parameters  and
c so that the spectrum of A lies on the straight line segment I
or on an elliptical domain E with foci   c that does not contain 0. Then let
and compute, for


(n  2); (36)
Also in Algorithm 5 we can avoid the residual gap by replacing the recursively
computed residuals by explicitly computed residuals.
Algorithm 6 (Two-term recursions and explicitly computed residu-
als) Same as Algorithm 5 except that the recursion (39) for computing r n+1
is replaced by r n+1 := b Ax n+1 .
6 The second order Richardson iteration as limiting case
For any  2 C n[ 1; 1] we have according to (15) in terms of # dened by (14)
and j#j > 1
as n !1. We can conclude that for any admissible value of  the coecients
of both the three-term and the two-term Chebyshev iterations converge:
as
(The dependence on the center  of the ellipse or interval is hidden in #.)
This gives rise to six additional related algorithms that are analogous to Algorithms
1{6 but use the limit values of the coecients. For example, for the
iterates hold the three-term recurrences
and the coupled two-term recurrences
These additional six algorithms are dierent implementations of the second-order
Euler method that can be associated with the ellipse E . This method
belongs to the class of iterative methods based on conformal mappings, introduced
by Kublanovskaya in 1959; see [8{11]. It is, at least in the case where the
ellipse E collapses to an interval I, better known as stationary second-order
Richardson iteration; see [3]. It can easily be generalized for mildly non-linear
systems of equations, and for those it seems more suitable than the nonlinear
Chebyshev iteration; see [21,22]. Note that
Therefore, for the three-term version of the second-order Richardson iteration,
all the multiplicative factors in (10) of Theorem 1 are actually smaller than 1
if  and
are computed with sucient accuracy.
The conformal map associated with the recursion (43) is 4
In view of (46) f maps a neighborhood of the unit disk one-to-one onto the
exterior of an ellipse with the foci   c. In particular, the disk D ^  around
0 with radius b
mapped onto the exterior of the interval
or line segment [ c;
, the disk D  is mapped onto the
exterior of a confocal ellipse, and if all the eigenvalues of A lie in this ellipse,
the iteration converges asymptotically at least with the rate 1=. If all the
eigenvalues lie on [ c;  + c], the asymptotic rate is 1=b . These asymptotic
rates are the same for the Chebyshev iteration.
7 Numerical results
We consider rst real matrices of order 500 whose eigenvalues are randomly
chosen as complex conjugate pairs in an ellipse with foci   c and longer
semi-axis a. These matrices have been constructed by unitarily transforming
a block-diagonal matrix (with 2  2 blocks) with these randomly chosen
In [9{11,21,22] the mapping p related to f by
instead.
eigenvalues. Note that these matrices are not very ill-conditioned as long as
the ellipse does not come very close to the origin: they are normal and their
condition number is bounded by the quotient of the distances from the origin
of the farthest point and the closest point. However, if we considered very
ill-conditioned matrices instead, the rate of convergence would be very slow.
We report the number n 12 of iterations needed to reduce the residual norm by
a factor of 10 12 and the ultimate relative accuracy where the residual norm
stagnates. Table 1 summarizes the results for four such matrices for the three-
term, two-term, and Rutishauser versions of the Chebyshev iteration using
recursively computed residuals. Table 2 contains the corresponding results if
explicitly computed residuals are used instead. We see that in these examples
the number of iterations needed to reach relative accuracy 10 12 is not aected
by the choice of the version. The ultimate accuracy is worst for the three-term
version with updated residuals, and by replacing them by explicitly computed
residuals we gain nearly up to two orders of magnitude. In other words, for
the three-term version with updated residuals the loss of accuracy is notable,
but not really serious. This re
ects what we can expect from Theorem 2. For
all the other versions, the ultimate accuracy is higher than 10 14 .

Table
Comparison of the three-term, two-term, and Rutishauser versions of the Chebyshev
iteration using recursively computed residuals. Normal matrices with eigenvalues in
the ellipse with foci   c and semi-axis a.
matrix 3-term 2-term Rutishauser
c a ult.acc. n 12 ult.acc. n 12 ult.acc. n 12
100 50 90 1.6e-14 195 1.6e-15 195 2.1e-15 195
100 70 90 5.9e-15 159 1.7e-15 159 2.3e-15 159
100 90 99 1.1e-13 1040 3.1e-15 1040 5.7e-15 1040

Table
Comparison of the three-term, two-term, and Rutishauser versions of the Chebyshev
iteration using explicitly computed residuals. Normal matrices with eigenvalues in
the ellipse with foci   c and semi-axis a.
matrix 3-term 2-term Rutishauser
c a ult.acc. n 12 ult.acc. n 12 ult.acc. n 12
100 50 90 9.2e-16 195 1.0e-15 195 9.1e-16 195
100 70 90 9.1e-16 159 9.5e-16 159 9.3e-16 159
100 90 99 1.8e-15 1040 1.9e-15 1040 1.7e-15 1040
In

Figures

1{3 we show for the rst example with
90 the residual histories for the two three-term versions, the two two-term
versions, and the two Rutishauser versions, respectively. For the algorithms
with residual recursions, both the true residuals and the recursively updated
residuals are plotted. Needless to say that for the algorithms using explicitly
computed residuals there is no dierence between those and the true residuals
and thus only one curve is shown.
Iteration Number
Normalized
Residual
Norms
Chebyshev 3 w/rec.res.: rec residual
Chebyshev 3 w/rec.res.: true residual
Chebyshev 3 w/expl.res.: (true) residual
Fig. 1. Chebyshev iteration with three-term recursions
Iteration Number
Normalized
Residual
Norms
Chebyshev 2x2 w/rec.res.: rec residual
Chebyshev 2x2 w/rec.res.: true residual
Chebyshev 2x2 w/expl.res.: (true) residual
Fig. 2. Chebyshev iteration with coupled two-term recursions
Iteration Number
Normalized
Residual
Norms
Chebyshev rut w/rec.res.: rec residual
Chebyshev rut w/rec.res.: true residual
Chebyshev rut w/expl.res.: (true) residual
Fig. 3. Chebyshev iteration with Rutishauser's recursions for updating corrections
8 Discussion of the potential roundo amplication in the three-term
Chebyshev algorithm in the case of complex data
Now we want to try to construct an example with much stronger degradation of
the ultimate accuracy in case of the three-term version with updated residuals.
We know that the in
uence of the roundo hinges in this case mainly on the
factors (12a){(12c) in (10). Clearly, the absolute value of the factor (12c),
(which simplies to the absolute value of (12b) if
if the absolute value of the denominator is very small, that is if  is close to a
zero of T n or T n+1 . These zeros all lie in the interval ( 1; 1), while jT n ()j > 1
if  > 1 or  < 1. Hence we need a complex  to get a small denominator.
In

Figure

4 we display this factor for as a function of  in
the domain 0 < Re   2, 0  Im   0:5. The poles of the function at the
three positive zeros of T 3 and T 4 are well visible, although the values of the
function on Re (where the poles are) are not plotted; the zero of T 3 at
with the one of T 1 . Clearly, we can make the fraction as large
as we want by choosing  close enough to a pole. Then at least one term in
will be large.
However, if  is close to such a pole (and, hence, to a point in the interval
Fig. 4. The factor ( 1  2 )=(
in (10) as a
function of
say to a zero of T n , then the residual polynomial p n of (1) is large
at some points of the prescribed, necessarily very
at elliptic domain. (Recall
that the straight line segment determined by the foci of the ellipse must come
very close to the origin, but the ellipse must not contain the origin. If the
ellipse were not
at, the quotient would not be close to a point
in the interval (-1,1) unless the ellipse would contain the origin.) Therefore,
the residual r n of a system with a matrix whose spectrum is spread in this
ellipse or on the straight line segment will most likely have some eigensystem
components that have not been damped or have even been amplied. It is not
of importance whether the matrix is diagonalizable or not.
There is the question what happens with the other quotients in (10). To explore
that, we show in Figures 5 and 6 the factors (48) for 0  k  n 1 < 100
when 0:001i, respectively. In the rst
case, the plot shows a clear ridge where
of n, the quotient j
remains smaller than one.
In fact, since
(see (41)), and since the asymptotic
convergence rate
j is bounded by 1 (see (46)), this is what we must expect.
Moreover, this asymptotic rate is also the asymptotic convergence factor of
both the Chebyshev iteration and the second order Richardson iteration if the
eigenvalues of A lie on the straight line segment [ c;  rate close to
1 means that, in general (that is, when the eigenvalues of A can be anywhere
on the line segment), the iteration will converge very slowly. In Figure 5 this
rate is around 0:83. Away from the ridge, the factors (48) quickly decay.
The second plot shows a few very high peaks and a regular pattern of many
Fig. 5. The factors (48) in (10) for 0:05i as a function of k and n.2060100
Fig. 6. The factors (48) in (10) for 0:001i as a function of k and n.
smaller peaks that are still higher than 1. (Note the new scale of the vertical
axis!) But, in view of what we just said, this can only mean that on the line
the quotients are still far away from their asymptotic value, which is
around 0:996 here. So, in an example with a matrix with this kind of spectrum
we might notice a serious in
uence of roundo propagation on the ultimate
accuracy, but the method would converge so slowly that we rather do not
want to apply it. In the initial phase the residuals may strongly increase in
this situation, because some of the residual polynomials are large on the line
segment.
9 Conclusions
We have compared six dierent implementations of Chebyshev iteration with
respect to convergence speed and ultimate accuracy attained. Several conclusions
can be drawn from both theoretical and experimental investigations.
The same theoretical conclusions also hold, and the same experimental ones
can be expected to hold, for the related stationary method, the second order
Richardson iteration.
In our fairly well-conditioned examples, the number of iterations needed to
reduce the residual norm by 10 12 did not depend on which of the six versions
is applied.
The ultimate accuracy turned out worst for the classical 3-term recursion
with recursively computed residuals, as had to be expected from theoretical
results.
Explicitly computed residuals yield the higher ultimate accuracy, and, for
all three types of iterations, roughly the same.
In contrast to CG, BiCG, and related methods, explicitly computed residuals
do not cause a slowdown of convergence. They also do not have higher
computational cost. Therefore they should be preferred.
If the (standard) three-term recursion for the residuals is applied nevertheless,
the ultimate accuracy is still likely to be quite high, and this for the following
reasons:
If the Chebyshev iteration is applied to a matrix with spectrum on an
interval or an ellipse with foci  c symmetric about the
real axis, then, in contrast to CG and BiCG, the loss of ultimate accuracy is
never very pronounced, because the multiplicative factors in (10) in front of
the local errors in the expression for the residual gap are all of absolute value
smaller than one if the recurrence coecients are computed with sucient
accuracy.
If the Chebyshev iteration is applied to an ellipse whose foci   c do not
lie on the real axis, but for which the line segment [ c;
close to the origin (which implies that the ellipse must be very
at or must
collapse to an interval), then some local errors may amplify dramatically and
might cause a large residual gap, so that the ultimate accuracy deteriorates.
However, this can only happen when the Chebyshev iteration converges very
slowly.

Acknowledgment

. The authors are grateful to Zdenek Strakos for pointing out
several misprints and suggesting a number of improvements.



--R


Numerical determination of fundamental modes
successive overrelaxation iterative methods
Theory of gradient methods
Further results on polynomials having least maximum modulus over an ellipse in the complex plane
On the constrained Chebyshev approximation problem on ellipses
Chebyshev polynomials are not always optimal
Computational Methods of Linear Algebra
Iterationsverfahren und allgemeine Euler-Verfahren
The analysis of k-step iterative methods for linear systems from summability theory
A study of semiiterative methods for nonsymmetric systems of linear equations

The convergence of inexact Chebyshev and Richardson iterative methods for solving linear systems

Generalized conjugate-gradient acceleration of nonsymmetrizable iterative methods
Changing the norm in conjugate gradient type algorithms
Estimating the attainable accuracy of recursively computed residual methods
BiCGstab(l) and other hybrid Bi-CG methods
Accuracy of computed solutions from conjugate-gradient-like methods


Stationary and almost stationary iterative (k
--TR
K-step iterative methods for solving nonlinear systems of equations
The convergence of inexact Chebyshev and Richardson iterative methods for solving linear systems
On the constrained Chebyshev approximation problem on ellipses
Chebyshev polynomials are not always optimal
Predicting the behavior of finite precision Lanczos and conjugate gradient computations
Changing the norm in conjugate gradient type algorithms
Estimating the Attainable Accuracy of Recursively Computed Residual Methods
Accuracy of Two Three-term and Three Two-term Recurrences for Krylov Space Solvers
coupled two-term recurrences;chebyshev iteration;second-order Richardson iteration;sparse linear systems;roundoff error analysis