Inner and Outer Iterations for the Chebyshev Algorithm.
We analyze the preconditioned Chebyshev iteration in which at each step the linear system involving the preconditioner is solved inexactly by an inner iteration. We allow the  tolerance used in the inner iteration to decrease from one outer iteration to the next. When the tolerance converges to zero, the asymptotic convergence rate is the same as for the exact method. Motivated by this result, we seek the sequence of tolerance  values that yields the lowest  cost to achieve a specified accuracy. We find that among all sequences of slowly varying  tolerances, a constant one is optimal. Numerical calculations that verify our results are presented. Asymptotic methods, such as the W.K. B. method for linear recurrence equations, are used with an estimate of the accuracy  of the asymptotic result.
Introduction
The Chebyshev iterative algorithm [1] for solving linear systems of equations often requires
at each step the solution of a subproblem i.e. the solution of another linear system. We
assume that the subproblem is also solved iteratively by an "inner iteration". The term
"outer iteration" refers to a step of the basic algorithm. The cost of performing an outer
iteration is dominated by the cost of solving the subproblem, and it can be measured by the
number of inner iterations. A good measure of the total amount of work needed to solve
the original problem to some accuracy ffl is then, the total number of inner iterations. To
reduce the amount of work, one can consider solving the subproblems "inexactly" i.e. not
to full accuracy. Although this diminishes the cost of solving each subproblem, it usually
slows down the convergence of the outer iteration.
It is therefore interesting to study the effect of solving each subproblem inexactly on the
performance of the algorithm. We consider two measures of performance: the asymptotic
convergence rate and the total amount of work required to achieve a given accuracy ffl.
The accuracy to which the inner problem is solved may change from one outer iteration
to the next. First, we evaluate the asymptotic convergence rate when the tolerance values
converge to 0. Then, we seek the "optimal strategy", that is, the sequence of tolerance
values that yields the lowest possible cost for a given ffl.
The present results, contained in Giladi [2], extend those of Giladi [3]. The asymptotic
convergence rate of the inexact Chebyshev iteration, with a fixed tolerance for the inner
iteration, was derived in Golub and Overton [4] (see also [5], [6], [7], [8], [9], [10]). Previous
work has mainly concentrated on the convergence rate, whereas we emphasize the cost of
the algorithm.
In section 2, we review the Chebyshev method and present the basic error bound for
the inexact algorithm. Then, in section 3 we evaluate the asymptotic convergence rate
when the sequence of tolerance values gradually decreases to j - 0. In section 4 we seek
the "best strategy" i.e the one that yields the lowest possible cost. In section 5, we obtain
an asymptotic approximation for the error bound when the sequence of tolerance values
is slowly varying. In section 6 we analyze the error in this asymptotic approximation and
present a few numerical calculations that demonstrate it's accuracy. In section 7 we use
the analysis of section 5, to show that for the Chebyshev iteration, the optimal strategy is
constant tolerance. We also estimate the optimal constant. Then, in section 8 we present
a few numerical calculations that demonstrate the accuracy of the analysis of section 7. In
Section 9, we generalize this result to other iterative schemes.
iteration
Chebyshev iteration (see Manteuffel [11]) to solve the real n \Theta n system of linear equations
uses the splitting
It requires that the spectrum of M \Gamma1 A be contained in an ellipse, symmetric about the
real axis, in the open right half of the complex plane. We denote the foci of such an ellipse
by l and u. Furthermore, we assume that M \Gamma1 A is diagonalizable.
The exact Chebyshev method is defined by
where
c k+1 (-)
In (3), the initial iterate x 0 is given, and in (7), c k denotes the Chebyshev polynomial of
degree k.
The inexact Chebyshev method is obtained by solving (5) iteratively for z k . This results
in replacing (5) by
In the variable strategy scheme the tolerance ffi k tends to j - 0 as k increases, while in the
constant strategy scheme
is constant.
We denote the error at step k by
We also define K, V , \Sigma and oe j by
We use the same derivation as in [4] to show that when -oe
where ffi represents a sequence of tolerance values fffi k g 1
. In equation (11), ae is defined by
The function -(k; ffi) satisfies the recurrence equation
with initial conditions
The constant \Delta in (13) is given by
ae
The bound (11) is the product of two terms: ae k
and -(k; ffi). The former
is the bound for the exact algorithm and it is exponentially decaying. The latter is a
monotonically increasing term which accounts for the accumulation of errors introduced by
solving the inner problem inexactly. We shall obtain asymptotic approximations to -(k; ffi)
under various assumptions on the sequence ffi k in order to analyze the performance of the
inexact algorithm.
3 Asymptotic convergence rate
We shall now estimate the asymptotic convergence rate of the inexact Chebyshev algorithm
when the sequence of tolerance values for the inner iteration gradually decreases to 0. Our
goal is to show that then, the asymptotic convergence rate of the inexact algorithm is the
same as that of the exact scheme. This is in contrast to the case of constant tolerance for
which the asymptotic convergence rate of the inexact algorithm is lower than that of the
exact algorithm [4].
We base our analysis on the bound (11). Therefore, we wish to compute
ae k -(k; ffi)
In order to do so, we need to estimate the asymptotic behavior for large k of -(k; ffi). By
making mild assumptions on the rate at which ffi k ! 0, we will show that
lim
Upon using (17) in (16), we find that the asymptotic convergence rate of the algorithm is
lim
ae
where ae e is the asymptotic convergence rate of the exact algorithm.
Equation (17) holds for many sequences ffi k of tolerance values. In order to obtain a
general result, we shall assume only that
The positive constant C in (19) is arbitrary. Hence, if C AE 1 the sequence of tolerance
values can decay quite slowly.
We show that (17) holds under assumption (19) in two steps. First we show that -(k; ffi)
in (13), is bounded by the function oe(k; - ffi), where oe(k; -
replaced by
. Then, we show that lim k!1 oe(k; - ffi) 1=k = 1. As a first step, we prove the following
proposition
Proposition 1 Let -(k; ffi) be a solution to (13) and (14) and let oe(k; -
ffi) be the solution to
the same equation with replaced by -
. Assume that - and that oe(0; -
Then,
for all k.
We prove this proposition by induction. For we obtain from (14) that
Then, we assume that assertions (20) and (21) are true for all In view of
and
By the induction hypothesis, oe(N; -
-(N; ffi). Furthermore, -
so the right side of (23) is greater than or equal to the right
side of (24). We conclude that
and that oe(N
We shall now obtain the asymptotic behavior of oe(k; ffi) for large k from (13) with
. We use the method of [12].
We first replace -(k; ffi) by oe(k; -
ffi) in (13) and set -
C=k. Then we introduce the
stretched variables
to obtain
We seek for R(x) an asymptotic approximation valid for ffl - 1 of the form
The functions /(x), K are to be determined so that R(x) satisfies equation
(27). The constant c(ffl) is to be determined so that R(x) is independent of ffl. After
substituting (28) into (27), we express each side of the resulting expression in power series
in ffl 1=2 assuming that /(x 2ffl). can be expanded in
Taylor series in powers of ffl. Then, we equate the coefficients of each power of ffl 1=2 on the left
side of the resulting expression, to the same power of ffl 1=2 on the right side. The coefficients
of ffl and of ffl 3=2 , yield the following equations for /(x; ffi) and K 0 (x; ffi) respectively:
x
x
Upon solving (29) for / we find
2C \Deltax: (31)
Introducing the right side of (31) into (30) and solving the resulting equation for K 0 we
obtain
To find the constant D in (32) we could match (28) to another expansion which satisfies
the initial conditions (14). However, the value of D is unimportant for our purposes since
We substitute (31) for / and (32) for K 0 into (28) for R. Then, we use the change of
variables (26) to obtain
To make the right side of (33) independent of ffl, we require that and we obtain
Therefore,
lim
In a realistic numerical computation ffi k is bounded below by the machine precision j 0 .
Moreover, the analysis of the iteration with sufficiently small,
the performance of the inexact algorithm is for all practical purposes indistinguishable from
that of the exact algorithm. Indeed, solving (13) with
where
It follows from (16), (18) and (36) that the asymptotic convergence rate is
ae e e OE( -
The number N(ffl; - ffi) of outer iterations required to achieve an accuracy ffl with tolerance - ffi
is approximately
log ffl
log
'e:
Hence, if
the inexact scheme requires no more than one more iteration
per thousand than the exact scheme. The difference is undetectable when N(ffl;
This leads us to evaluate the asymptotic convergence rate when To
obtain the behavior of oe(k; ffi) in (13) for large k, when
into (13) to obtain (27) and seek an expansion for R(x) of the form
We introduce (40) into (27) to obtain, after some manipulation, equations for / and K
x
Then, we solve (41) and (42) and substitute the results into (40) to obtain, with \Phi(j)
defined in (37), and D a constant
Hence,
lim
In view of (38) and (44) the asymptotic convergence rate is the same as that with
The results (34) and (43) of this formal analysis can be made rigorous. We summarize
the above analysis in the following theorem:
Theorem 1 Assume that a linear system of equations is solved to accuracy ffl, using the
Chebyshev iteration, with a variable strategy fffi k g. Assume that
that positive constant C. Then, the asymptotic convergence
rate of the Chebyshev iteration with the variable tolerance is the same as the asymptotic
convergence rate of the scheme with the fixed tolerance j.
4 The optimal strategy problem
Motivated by the result of section 3, we now wish to find the "best" sequence of tolerance
values for the inner iterations. More precisely, we seek the sequence of tolerances that
yields the lowest possible cost for the algorithm.
To formalize this problem, we let
, be a sequence of tolerance values. The
jth component of ffi, is the tolerance, required in the solution of the subproblem at outer
iteration j. Therefore and the number of inner iterations at step j is d \Gamma log
e.
In this estimate, ae is the convergence factor of the method which is used in the solution of
the subproblem. Then, we define N(ffl;ffi) to be the number of outer iterations needed to
reduce the initial error by a factor ffl when the problem is solved with strategy ffi: It follows
that the total number of inner iterations required to achieve this accuracy ffl is proportional
to
log
Our objective is to minimize C(ffl; ffi ) with respect to ffi.
We consider the set S of slowly varying strategies
In (46), the function ffi(x) is assumed to be twice continuously differentiable and ffi 0 denotes
it's derivative. The condition
ensures that ffi(fik) varies slowly as a function of k
if fi - 1.
In order to simplify the analysis, we use the fact that
log
Z N(ffl;ffi)log ffi(fit)dt;
and redefine the cost as
Z N(ffl;ffi)log ffi(fit)dt: (47)
We can now restate the problem as follows. Find ffi   2 S such that
5 Error bound for slowly varying strategies
Now we shall approximate the error bound (11), under the assumption that ffi 2 S. First,
we obtain an asymptotic approximation for -(k; ffi), valid for fi - 1. To emphasize the fact
that -(k; ffi) depends on fi, we denote it -(k; ffi; fi).
To simplify the analysis we assume that the function ffi(x) is constant on [0; fi]. This
assumption is not very restrictive since it requires only that we change the value of ffi 0 to
equal . Moreover, since ffi k is slowly varying the impact of this change on the cost is
negligible.
The method we use is similar to the W.K.B method [13] for linear ordinary differential
equations with a small parameter, and the ray method Keller [14] for linear partial differential
equations with a small parameter. These methods have recently been adapted to
linear difference equations with small parameters [12], [15].
We now obtain an approximate solution to equation (13) when belongs to
S. Since we are looking for an asymptotic expansion of -(k; ffi; fi) for small fi, we introduce
the new scaled variables
Upon performing the change of variables (49) in (13), we obtain
We seek an asymptotic expression for R(x; ffi; fi) for small fi, in the form
The functions /(x; ffi), K(x; ffi), K 1 are to be determined to make R satisfy (50).
Substitution of (51) into (50), and multiplication by e \Gamma/=fi yields
e
We now express each side of (52) in powers of fi, assuming that /(x
etc. can be expanded in Taylor series in powers of fi. Then, we equate
coefficients of powers of fi. The coefficients of fi 0 and of fi 1 yield
tanh
Solving (53) for / x yields
with \Phi(ffi) given by (37). Integrating (55) yields, with a a constant of integration
We now rewrite (54) as
cosh / x
sinh / x
Integrating (57), with b a constant of integration, gives
Now, we use expression (55) for / x in (58) to obtain
To obtain the leading order term in -(k; ffi; fi), we substitute the two values (56) for /
into (51) for R and add the two terms. Then, we use the result in (49) and set x j fik to
find
R fik\Phi(ffi(t))dt
Here \Phi(ffi) is defined in (37) and K(x; ffi) is given by (59). The constants A and B are
determined to make (60) satisfy the initial conditions (14):
R fi
R fik\Phi(ffi(t))dt
Since ffi(x) is constant on [0; fi], (59) shows that K(0;
R fi
\Phi(ffi(0)). We substitute (61) into (60) to obtain, after some manipulation,
sinh
Z fik\Phi(ffi(t))dt
R fik\Phi(ffi(t))dt
When implies that / shows that K is also
constant. Hence, (62) simplifies to the exact solution (36) of (13) and (14) when
a constant.
The exponentially decaying term in (62) can be neglected after a few outer iterations.
Then we set in (62) and introduce the function
sinh
Now, we approximate -(k; ffi) by oe(k; ffi), and the bound for the error in the right hand side
of (11) becomes
In the next section, we shall analyze the validity of the approximation (64).
6 Validity of the asymptotic expansion
Now we shall show that the leading order expression for -(k; ffi), given by (62), is indeed
asymptotic to -(k; ffi) as fi ! 0. We denote this expression by - (k; ffi) and define the residual
associated with it by r(k; ffi):
To evaluate r(k; ffi) we substitute (60) for -(k; ffi) into (65) and then expand / and K in
Taylor series, with remainders up to order fi 3 and fi 2 , respectively. We use (59) and (56)
in the resulting expression to obtain, after some manipulation,
Here and is independent of k and fi.
The error in the asymptotic approximation, e(k;
This equation is obtained by subtracting (13) from (65). The initial conditions for e(k; ffi)
are
Our goal is to show that for any constant C and all k - C
To estimate the left side of (69), we obtain an explicit formula for e(k; ffi), by solving
(67) and (68). We use the method of reduction of order [13]. Specifically, we seek a solution
of the form
where -(k; ffi) is the solution to equation (13), (14) and x k is to be determined. Upon
substituting (70) into (69) we find that (69) will hold if
We obtain an expression for x k by substituting (70) for e(k; ffi) into (67). Then, we
eliminate from the resulting expression by using (13) and we find that
Now, we introduce
into (72) to obtain a linear first order equation for X k . The initial conditions (68) yield
The solution of (72) and (74) is
We take the absolute value of each side of (75) and use (66) to obtain
e
R k\Phi(ffi(fit))dt
Here \Phi(ffi) is defined in (37).
In lemma 1 we shall show that
is bounded by a constant independent on
k and fi. In lemma 2 we shall show that for a non-increasing strategy ffi(x) in S
e
where the constant P is independent of k and fi. We now use these bounds in the right
side of (76) and conclude that for all k - 1
where the constant C is independent of k and fi.
Equation (73) and the condition for x 1 in (74) determine x k through
To derive the bound (71) for jx k j, we take the absolute value of each side of (79) and use
(78) to obtain
We summarize the above analysis in the following theorem:
Theorem 2 Let -(k; ffi) satisfy (13) and (14). Let - (k; ffi; fi) be the expression on the right
side of (62). Assume that ffi(x) is a non-increasing strategy and that ffi(x) 2 S with S defined
in (46). Then, fi fi fi fi fi
Furthermore, the coefficient of fi 2 in (81) is bounded by a linear function of k.
We now briefly discuss the validity of the approximation (63). When
is constant,
(63) is exact up to an exponentially decaying term, and it is very accurate after a few
iterations. When ffi is not a constant, the approximation is based on (62), which is valid for
Therefore, the accuracy decreases as the number of outer iterations
k !1, and for a fixed k, increases as fi ! 0. At the end of this section we present a few
numerical calculations that demonstrate the accuracy of the expansion for a few variable
strategies in S. As we shall see, even for large values of k, it is very accurate.
and
Proof: Inequality (82) is shown by induction. For it follows from initial conditions
(14). Now assume by induction that (82) holds for all 1. Then from (13)
By the induction hypothesis
We use (85) in (84) to complete the induction.
In order to prove (83), we recall from (46) that ffi k - j and we use this bound in (82)
to obtain
Furthermore, we note that
Y
We use (86) in (87) to obtain
It follows that
Inequality (83) follows from inequality (89).
be a non-increasing strategy such that ffi(x) 2 S, with S defined in
(46). Then
e
R k\Phi(ffi(fit))dt
where the constant P is independent of k and fi.
Proof: We note that when ffi(x) is a non increasing function of x, it follows from the
monotonicity of \Phi(ffi) in (37) that
We introduce the right side of (91) into (90) and use (37) for \Phi(x), to obtain
e
R k\Phi(ffi(fit))dt
We now seek a lower bound on -(k; ffi). In view of the left condition in (14), we can
as the product
where
It follows from (13) and (14) that ae j satisfies the equation
with
To obtain a lower bound for the product in (93), we introduce the sequence ae
ae
The number ae
k is computed with the aid of the intermediate quantities ae
as follows:
ae
ae
We define
ae
In order to demonstrate (97), we show by induction on j that for all
ae
For it follows from (96), (98) and the fact that ffi(x) is non-increasing that
ae
Now, we assume that (101) is true for all it follows from (95), (99)
and the fact that ffi(x) is non-increasing that
ae
ae
ae
The next step in the proof is to evaluate ae
k explicitly and obtain a lower bound for
it. This is done by solving the non-linear recurrence equation (99) for ae
k;j , subject to the
initial condition (98). We solve this equation with a method analogous to the one described
in section 16.7 of [16] and obtain
ae
where
From equation so that
Furthermore, it follows from (105) and the definition of j in (46)
where the equality on the right defines the constant -. We use (107) and (106) in (104)
and obtain, in view of (100),
ae
Further manipulation of (108) yields
ae
Finally, we note that 1=(1 the latter
inequality follows from (105). We use these bounds in (109) and use (97) to get
We are now ready to prove the lemma. First, we substitute the right side of (93) for
-(k; ffi) in (92). Then, we use (110) and (96) to find
e
The infinite product
convergent because
1. Hence, the right side
of (111) is bounded by a number P which is independent of fi and k.
We now present a few numerical calculations that demonstrate the accuracy of the
expansion derived in section 5. First, we solve (13) for -(k; ffi; fi) by iteration and then we
compute the approximate solution oe(k; ffi) given by (63), for all 2 - k - 2000. We present
the relative error in this approximation.
We use strategies from the three parameter family
A
The minimal tolerance in (112) is In all our calculations ffi k AE j and for all
practical purposes j can be neglected. The value of parameters A and fl is fixed at 1. The
parameter B and the value of fi vary from one calculation to the other. The value of \Delta in
(13) is set to 37. We performed analogous calculations with larger values of \Delta and with
obtained similar results.
In table 1, we present the maximum with respect to k, of the absolute value of the
relative error in percent. Each entry in this table corresponds to a calculation with a
different strategy. The strategy is determined by the parameters B and fi. Figure 1 depicts
the relative error in percent between oe(k; ffi) and -(k; ffi; fi), for all 2 - k - 2000. Each graph
corresponds to different values of B and fi. We note that the approximation is accurate
even for large values of k.
Relative
error
in
20000.020.06Relative
error
in
-0.20.20.6Relative
error
in
-0.020.020.06Relative
error
in

Figure

1: The relative error j- (n; ffi; Each
graph corresponds to different values of B and fi.
1:01 0:74 0:05
1:50 0:74 0:05
2:00 0:73 0:05
5:00 0:72 0:07
10:00 0:71 0:07
100:00 0:70 0:11

Table

1: The maximum over 2 - n - 2000 of j- (n; ffi;
7 Constant strategy is optimal
using (47) and (64) we seek the optimal strategy for the Chebyshev iteration. The
numbers N(ffl; ffi) and C(ffl; ffi) in (47), are hard to determine precisely. Therefore, we introduce
the quantities NB (ffl; ffi) and CB (ffl; ffi), which are the number of outer iterations required to
reduce the error bound (64) to ffl and the associated cost, respectively. The following
theorem shows that a constant strategy is optimal.
Theorem 3 Suppose that a linear system of equations is solved to accuracy ffl by the Chebyshev
iteration using inner iterations with a sequence of tolerances fffi k g in S. There exists
a constant strategy - ffi(ffi; ffl), for which the cost is smaller, i.e.
Proof: Given the variable strategy ffi and the accuracy ffl used in the solution of the linear
system, we define the associated constant strategy -
R NB (ffl;ffi)
In Lemma 3, we show that NB (ffl; -
Therefore,
In Lemma 4, we show that
Using (115) in the right hand side of (114), proves the theorem.
Lemma 3
Proof: By definition of NB (ffl; ffi) the bound for the error B(k; ffi) in (64) satisfies
Therefore, to prove (116) it is sufficient to show that after NB (ffl; ffi) outer iterations, the
bound for the error associated with the variable strategy is greater than the one associated
with the constant strategy. Hence we need to show
We see from (64) that (117) is equivalent to the inequality
where oe is defined in (63). To prove (118) we begin by rewriting expression (63) for oe(k; ffi)
with
K(fiNB (ffl; ffi); ffi)
sinh
Then, we note from (37) that \Phi is monotonically increasing and that for all non-negative
(46). Therefore,
R NB (ffl;ffi)
Furthermore, we see that K(fiNB (ffl; ffi); ffi)=K(0; ffi) - 1 from equation (59). Using this and
(121) in the right hand side of (119) we obtain
sinh@ NB (ffl; ffi)\Phi\Phi \Gamma1@
R NB (ffl;ffi)
Lemma 4
Proof: The definition (37) of \Phi shows that \Phi
. Therefore,
strictly convex on the interval ffi)g. It follows
from Jensen's inequality that
log \Phi \Gamma1@
R NB (ffl;ffi)
R NB (ffl;ffi)
Multiplying (123) by NB (ffl; ffi) proves the lemma.
We now show how to estimate the optimal constant - ffi. We note from (64) that for any
iteration N
Then, by equating the right side of (124) to ffl and using (37), we obtain
log
Re(cosh
An estimate of the cost is then
Re(cosh
The right side of (126) can be minimized easily with respect to -
using a standard minimization
technique. The original variational problem (48) is thus reduced to a simple
optimization problem. Since B(N; -
ffi) approximates a bound for the error, the tolerance
obtained by this method will be a lower bound for the optimal tolerance. The estimation
of the optimal constant depends on the parameters - and ae in expression (126). These are
often determined adaptively while solving the system [17].
8 Numerical calculations
We now present a few numerical calculations that verify the analysis of section 7. In
each experiment, we solve a linear system with Chebyshev iteration to accuracy ffl, using a
variable strategy ffi. Then, we solve the same system with the associated constant strategy
defined in (113) with NB (ffl; ffi) replaced by N(ffl; ffi). We recall that N(ffl; ffi)
is the exact number of outer iterations required to achieve an accuracy ffl, when solving the
problem with strategy ffi. This number is obtained from our numerical experiment. Our
goal is to verify that the predictions of lemma 3 and theorem 3 hold in practice.
In section 4 we define the cost at outer iteration j by using
log
for the number of inner iterations required to achieve accuracy ffi j instead of d \Gamma log
e. Here,
ae is the convergence factor for the inner iteration. If ae is close to 1, then the relative error
in using (127) is usually small and the cost (45) is truly proportional to the total number
of inner iterations. In this case, we expect good agreement between the analysis and
the numerical calculations. Moreover, we expect some fluctuations around the predicted
behavior when ae - 1. We covered both cases in our experiments.
We solve the symmetric system
arising from the central difference discretization of the operator
in the interval [0; 1] with homogeneous Dirichlet boundary conditions. The right side b in
(128) is chosen at random. The splitting matrix M is obtained from the discretization of
the operator
with homogeneous Dirichlet boundary conditions. The mesh parameter in this discretization
is 1=100. The tolerance for the outer iteration is . The initial iterates
for both the inner and outer iterations are 0.
In all our experiments, we use strategies from the family (112). The values of fl and A
are fixed at 1. The parameter B and the value of fi vary from one experiment to the other.
For each variable strategy ffi, the associated constant strategy - ffi is computed using (113)
with NB (ffl; ffi) replaced by N(ffl; ffi). We note from (113) that \Phi depends on \Delta. We evaluate
exactly but find that - ffi is not very sensitive to the value of \Delta. We performed calculations
with various values of C in (129) and (130) and we shall report on a representative sample
obtained with
We use two methods for the inner iteration. The symmetric Gauss Seidel, with the
convergence factor 0:993, close to 1, and the symmetric successive over relaxation method
[18] (S.S.O.R) with the smaller convergence factor 0:925. In the S.S.O.R iteration, the
relaxation parameter ! is the optimal parameter !   of S.O.R. In each experiment, we
record the number of outer iterations and the total number of inner iterations for the
variable and constant strategy cases.

Tables

2-5 correspond to the case where the inner iteration is symmetric Gauss Seidel.
In table 2 we report the difference in the total number of inner iterations between the
variable strategy case and the associated constant strategy case. All entries in the table
are in (%) and are computed from
N in (ffl; ffi) \Gamma N in (ffl; - ffi)
N in (ffl; -
100: (131)
Here N in (ffl; ffi) is the total number of inner iterations performed when solving the system
to accuracy ffl with strategy ffi.
Each entry in table 2 corresponds to a different strategy. The strategy is determined
by the parameters B and fi. Note that not all strategies are slowly varying since fi 6- 1
in the two rightmost columns of that table. The important thing to note in table 2 is
that all entries are positive. Therefore, the number of inner iterations associated with
the variable strategy is greater than or equal to the number of inner iterations with the
constant strategy. Hence, there is agreement with Theorem 3.
In table 3, we present the difference in the number of outer iterations between the
variable strategy case and the constant strategy case i.e. N(ffl; We see that all
entries are non-negative and there is very good agreement with Lemma 3.
In table 4 we present the total number of inner iterations with the associated constant
strategy. The lowest number of inner iterations is found at the top left entry. This entry
corresponds to the lowest tolerance for the inner iteration. Table 5 presents the total
number of outer iterations. We see that the top left entry maximizes the number of outer
iterations. Hence, among all strategies considered in this table, the strategy which yields
the lowest convergence rate also yields the lowest cost.

Tables

6 and 7 present the difference in number of inner and outer iterations, respec-
tively, when the inner iteration is S.S.O.R. Since the convergence factor is not close to 1
some fluctuations from the predicted behavior are expected. Indeed, two entries in table
6 are negative. However, the fluctuations are small and the constant strategy performs
essentially as well as the variable one.
In our numerical calculations we have used both slowly varying strategies,
"rapidly" varying ones, Although our theory was developed for slowly varying
strategies, the conclusion of theorem 3 is found to hold for all the strategies considered.
9 Generalization to other iterative procedures
We now consider a general iterative algorithm in which, at iteration k, a subproblem is
solved by an inner iteration to accuracy ffi k . The norm of the error at step k, e k , satisfies

Table

2: The difference in number of inner iterations (N in (ffl; ffi) \Gamma N in (ffl; - ffi))=N in (ffl; -
ffi) in
(%). The tolerances ffi k and -
are defined by (112) and (113), respectively. Inner iteration
is symmetric Gauss Seidel.

Table

3: The difference in number of outer iterations N(ffl;
ffi). The tolerances
are defined by (112) and (113), respectively. Inner iteration is symmetric Gauss
Seidel.
1:50 4458 5144 5369 6203
2:00 4666 5143 5571 6324
5:00 5199 6208 6444 7447
10:00 5697 6722 7167 8093
100:00 8660 9423 10228 11137

Table

4: The number of inner iterations N in (ffl; -
ffi) with - ffi given in (113). Inner iteration is
symmetric Gauss Seidel.

Table

5: Number of outer iterations
given in (113). Inner iteration is
symmetric Gauss Seidel.
1:01 2:36 8:60 4:29 8:62
1:50 2:26 3:66 4:34 3:42
2:00 0:98 3:43 4:79 4:76
5:00 0:64 5:87 4:64 5:44
10:00 \Gamma0:77 \Gamma0:67 5:93 0:14
100:00 0:42 0:60 0:78 1:03

Table

The difference in number of inner iterations (N in (ffl; ffi) \Gamma N in (ffl; - ffi))=N in (ffl; -
ffi) in
(%). The tolerances ffi k and -
are defined by (112) and (113), respectively. Inner iteration
is S.S.O.R.

Table

7: The difference in number of outer iterations N(ffl;
and - ffi are defined by (112) and (113), respectively. Inner iteration is S.S.O.R.
the relation
In (132), ae(k; x convergence factor at step k, depends on the initial iterate x 0 and
on the sequence of tolerance values ffi. We assume that ae(k; x product
with
Hence, the only tolerance upon which ae(k; x the tolerance at outer
iteration k. Furthermore, the dependence of ae(k; x is the same at each iteration
of the algorithm. We can prove a result similar to the one of section 7 for an iteration
satisfying (133).
Theorem 4 Consider an iterative algorithm in which at step k, a subproblem is solved
by inner iteration to accuracy ffi k . Assume that the norm of the error satisfies (132), with
of the form (133). Assume that g(OE) is a convex non decreasing function. Let
be the reduction of the error after N outer iterations. Then, for any variable
strategy ffi and any number of outer iterations N , there exists a constant - ffi(N;
with the following properties.
1. After N outer iterations with the constant tolerance - ffi(N; ffi ) for the inner iteration,
the error is reduced by exactly ffl(N; ffi ).
2. The cost (45) of performing N outer iterations with the constant tolerance -
is lower than the cost of performing N outer iterations with the variable tolerance ffi.
In other words, for such an iteration a constant strategy is optimal.
Proof: From (132) and (133) we find that after N outer iterations of the algorithm with
the variable tolerance ffi, the error is reduced by
Let
and - ffi(N;
Then, it follows from equations (132) and (133) that after N iterations with the constant
strategy -
the error is reduced by
The right hand side of equation (137) is exactly ffl(N; ffi ).
Using (45) and (136) we find that the cost associated with N steps of the constant
tolerance iteration is
while the cost associated with the variable tolerance is
Now, the right side of (138) is no greater then the right side of (139) since g is convex.
The error bound (64) for the Chebyshev iteration is analogous to (135) with the sum
over g(OE) replaced by an integral and the term e
replaced by a function F (k; x 0 ),
independent of ffi. Hence, theorem 3 is essentially a continuous version of theorem 4. The
proof of the former is complicated by the presence of the amplitude term (59) in (63).

Acknowledgements

This work was supported in part by NSF under cooperative agreement no CCR-9120008
and grant CCR-9505393, ONR, and AFOSR.



--R

Chebyshev semi-iterative methods
Hybrid Numerical Asymptotic Methods.
On the interplay between inner and outer iterations for a class of iterative methods.
The convergence of inexact chebyshev and richardson iterative methods for solving linear systems.
On the local convergence of certain two step iterative procedures.
Accelerating the convergence of discretization algorithms.
On the convergence of two-stage iterative process for solving linear equa- tions

Inexact and preconditioned uzawa algorithms for saddle point problems.
The tchebyshev iteration for nonsymmetric linear systems.
Eulerian number asymptotics.
Advanced Mathematical Methods for Scientists and En- gineers
Rays, waves and asymptotics.
The wkb approximation to the g/m/m queue.
Ordinary Differential Equations.
Adaptive procedure for estimation of parameters for the nonsymmetric tchebychev iteration.
Matrix iterative analysis.
--TR
inexact iteration;iterative methods;inner iteration