Multigrid Methods for Nearly Singular Linear Equations and Eigenvalue Problems.
The purpose of this paper is to develop a convergence theory for multigrid methods applied to nearly singular linear elliptic partial differential equations of the type produced from a positive definite system by a shift with the identity. One of the important aspects of this theory is that it allows such shifts to vary anywhere in the multigrid scheme, enabling its application to a wider class of eigenproblem solvers. The theory is first applied to a method for computing eigenvalues and eigenvectors that consists of multigrid iterations with zero right-hand side and updating the shift from the Rayleigh quotient before every cycle. It is then applied to the Rayleigh quotient multigrid (RQMG) method, which is a more direct multigrid procedure for solving eigenproblems. Local convergence of the multigrid V-cycle and global convergence for a full  multigrid version of both methods is obtained.
Introduction
. In this paper, we consider the solution of the generalized
eigenvalue problem based in an abstract finite-dimensional Hilbert space V with inner
product (\Delta; \Delta): Find - 2 R and 0 6= such that
Here, A and B are linear continuous symmetric operators defined on V , A is positive
definite, and B is positive semidefinite.
We will consider two multigrid approaches for finding the smallest eigenvalue for
(1.1) based on a sequence of subspaces. One uses multigrid as an inner loop solver for
an outer loop inverse iteration type process, which has been studied by many authors
(cf. the early work in [1] and [7]). The other is the Rayleigh quotient multigrid method
(RQMG [5, 8]), which is a more direct approach based on minimizing the Rayleigh
quotient at each stage of the multigrid processing. We will analyze convergence of
these two multigrid methods by developing and applying a general convergence theory
for singular or nearly singular linear problems: Given f 2 V and a scalar - 2 R, find
such that
Previous convergence results for multigrid algorithms applied to (1.2) were obtained
by Bank [1]. In order to establish norm estimates for the rate of convergence,
the shift - was assumed to be bounded away from the smallest eigenvalue of (1.1) in
Department of Mathematics, University of Southern California, Los Angeles, CA 90089-1113.
y Center for Computational Mathematics, University of Colorado at Denver, Denver, CO 80217-
3364. Supported by the National Science Foundation under grant number ASC-9121431.
z Program in Applied Mathematics, University of Colorado at Boulder, Boulder, CO 80309-0526.
Supported by the Air Force Office of Scientific Research under grant number AFOSR-91-0156 and
by the National Science Foundation under grant number DMS-8704169
[1]. In contrast, our analysis is based on an error decomposition into the eigenspace
associated with the smallest eigenvalue of (1.1) and its orthogonal complement. We
will not attempt to solve (1.2) in the usual sense; instead, our aim is to preserve the
approximate magnitude of the components in the eigenspace of the smallest eigenvalue
of (1.1) while attenuating error components in its orthogonal complement. In
our analysis, the shift - will be assumed to lie in a small neighborhood of the smallest
eigenvalue of (1.1).
The outline of the remainder of this paper is as follows. In Section 2, we formulate
the problems, establish notation, and define a multigrid algorithm for the nearly
singular problem. In Section 3, we develop a convergence theory for this multigrid
algorithm. The theory is first applied in Section 4 to a method for computing eigen-values
and eigenvectors that uses multigrid as an inner loop solver for an outer loop
iteration type process. It is then applied in Section 5 to RQMG. The final
section develops global convergence results for full multigrid V-cycle versions of both
methods.
2. Preliminaries. Let V be a real linear space, on which are given inner products
a(\Delta; \Delta) and (\Delta; \Delta), with corresponding induced norms denoted by jjj \Delta jjj and k \Delta k.
Let b(\Delta; \Delta) be a continuous, symmetric, nonnegative bilinear form on V \Theta V . Consider
the eigenvalue problem : Find - 2 R and 0 6= such that
If (2.1) corresponds to the eigenvalue problem for a self-adjoint elliptic partial
differential operator, it will typically admit an infinite set of nondecreasing eigenval-
ues. Without loss of such generality, let the (possibly multiple) eigenvalues of (2.1)
In particular, we note that - 1 is the minimum of the Rayleigh quotient over
where the Rayleigh quotient is defined by
We will consider multigrid methods for finding the smallest eigenvalue for (2.1),
based on a sequence of finite-dimensional subspaces. To this end, let
be a nested family of finite-dimensional subspaces of V . Let (\Delta; \Delta) k be a given inner
product on V k , k \Delta k k its induced norm, and h the mesh parameter associated
with the corresponding finite-dimensional problem (2.1) on V k is :
Find such that
Let the (possibly multiple) eigenvalues of (2.5) satisfy
Note that - kis the minimum of the Rayleigh quotient over
In order to analyze convergence of the multigrid algorithm for the eigenvalue
problem (2.5), we will first study the behavior of multigrid applied to the following
singular or nearly singular problem : Given a source term f l in the dual space
and a scalar - 2 R, find 0 6= u l 2 V l such that
The shift - is assumed to satisfy
The reader is strongly advised to keep in mind that all of the following estimates
allow for - to change any time during multigrid processing, provided it continues
to satisfy the bounds in (2.8). This allowance for a floating shift is one of the key
distinguishing points of the theory developed here, and it is just what enables treatment
of the nonlinear scheme RQMG below.
For any u; v 2 V , define the bilinear forms c - (\Delta; \Delta) and c(\Delta; \Delta) on V \Theta V by
\Delta) be a bilinear form on V k \Theta V k . We will use this
form to define the smoothing step in the multigrid algorithm defined below. Define
the operators A
requiring
for all u and v in V k . Note that
In practice, the operator Q k will be constructed to "approximately invert" C k
- in some
sense. The basic idea is that we want Q k to satisfy the condition that it is an
adequate approximate inverse of C k
- on oscillatory vectors in V k . We will be precise
about this condition in Section 3.3.
Denote the eigenspace associated with - k
1 by
and its a-orthogonal complement by
For any u 2 V k , define the a-orthogonal projection operators P k
1 and
and
Consider the following multigrid algorithm for "solving" (2.7); more precisely, this
algorithm attempts to reduce the error in V lonly, while keeping the V lapproximation
component essentially unchanged. Note that MG=as it is posed here uses a direct
solver for the coarsest grid problem (l = 0). Later we will allow for approximate
solvers.
MG=Algorithm. Let an initial approximation u l and a right-hand side
f l be given. Then the new approximation u l ) is defined recursively
as follows:
a) If l = 0, then compute u l so that
b) If l ? 0, then perform the following:
1. Coarse-grid correction step. Denote the current residual by r l;0
its restriction to V
f . Then set
2. Smoothing step. Define w l 2 V l by
where r l;1
3. Convergence of a Multigrid Method for Nearly Singular Linear
Equations. In this section, we will analyze convergence of multigrid for the nearly
singular linear problem (2.7). Our analysis is based on an error decomposition introduced
in Section 3.2, which is based on an interpretation of solution and error
that takes into account the objective of using (2.7) to solve the eigenvalue problem
We have therefore not attempted to solve (2.7) in the usual sense;
instead, our aim is to preserve the approximate magnitude of the components in the
eigenspace associated with - lwhile attenuating error components in its a-orthogonal
complement. Based on this error decomposition, we establish a smoothing property of
relaxation in Section 3.3 and a reduced approximation property of the discretization
in Section 3.4, which are combined in Section 3.5. A V-cycle estimate will be developed
in Section 3.7 that follows from the recursive estimates developed in Section 3.6.
Again, the reader is strongly advised to keep in mind that the shift - is floating in
the sense that it is allowed to vary anywhere in the multigrid process, provided it
remains within the bounds expressed by (2.8).
3.1. Preliminaries and Assumptions. Fix k 2 f0; lg. For any u 2
the a-orthogonal projections P kand P kyield the unique decomposition
Remark 3.1. Note that V k
are also b-orthogonal:
In this paper, C ? 0 will denote a generic constant that does not depend on the
number of levels l or any of the mesh sizes h k .
Assumption 3.1. The norms jj \Delta jj and jj \Delta jj k are uniformly equivalent on all V k ,
that is, for any v 2 V k ,C
Assumption 3.2. Assume that the following approximation properties hold:
1) For any u 2 V k, there exists
1 such that
1 , there exists
1 such that
Remark 3.2. Under the usual full regularity assumptions and subspace proper-
ties, standard finite element theory (cf. [9]) concludes that, for any 0 6=
minimizes RQ(u) over V , there exists l such that
then follows using the triangle inequality and this estimate with l = k and
analogous argument based on a corresponding estimate can be used to
establish (3.5). The eigenvalue estimate in our first lemma below also follows from
standard finite element theory.
Lemma 3.1. [Eigenvalue approximation property]
Proof. The left inequality follows from noting that - iis the minimum of RQ(u i )
To prove the right inequality, note, for
any u 2 V kand
1 , that
Hence,
The lemma then follows from Assumption 3.2 and the fact that -
bounded by a constant independent of h k .
Remark 3.3. A similar argument shows that
Together with (2.8), this implies that
Lemma 3.2 (Norm equivalence). It holds, for any v 2 V k
2 , that
and, for all sufficiently small h 0 , that
Proof. It suffices to prove (3.8) since (3.7) may be proved in a similar way.
The left inequality follows immediately from the fact that the bilinear form b(\Delta; \Delta) is
nonnegative. To prove the right inequality, note that since V kis the a-orthogonal
complement of V k
Thus,
Standard "mini-max" arguments (cf. [9]) show that - 2 - k- 0, from which follows
The proof is concluded using (2.8).
We may thus define new norms on the spaces V which are
uniformly equivalent to the norm jjj \Delta jjj, by
Remark 3.4. jj \Delta jj c is a seminorm on V k . It is, in fact, a norm provided
3.2. Decomposition. The following concept of error decomposition will
be the basis of our analysis. Because we consider algorithms for the nearly singular
problem (2.7) with the ultimate objective of solving (2.5) with l, the usual
concepts of solution and error are not really relevant here. Indeed, we will not attempt
to solve the problem per se, but only to attenuate "error components" in the subspace
lwhile preserving the approximate magnitude of the components in V l. The purpose
of this section is to make this precise. The main point to note here is that we cannot
measure error in the usual direct sense because - and, hence, what we even mean by
the "solution", are floating: the error component in V lis more or less well defined
because - l, so we will use a direct error norm to measure it; however, the error
component in V lis elusive, so instead of a direct measure we will use a residual norm
that is easier to pinpoint and bound.
Lemma 3.3 (An invariant subspace property). Let f k
2 be a continuous
linear functional on V k that vanishes on V k
1 . Then, for sufficiently small h 0 , there
exists a unique U
2 such that
Proof. It follows from the definition of the subspace V kand from (2.8) that the
bilinear form c - (\Delta; \Delta) is positive definite on V k. By the Lax-Milgram lemma, there
exists a unique solution, U 2 V k, of the variational problem
The proof is completed by noting that U is orthogonal to V kwith respect to the
bilinear form c - (\Delta; \Delta).
Let u be an approximation to the solution of the following problem : Find u
such that
for a given functional We then define the residual r as the functional
on V k given by
Suppose that we are given a decomposition
2 vanishes on V k
1 . By Lemma 3.3, there exists a U
2 such that (3.9) holds.
Write
Then
where
and
with
We define the size of the error to be the pair
where kr 1 k is defined as the functional norm
Remark 3.5. Note that the decomposition (3.12), and therefore the definition of
the size of the error, is not unique. We allow this freedom to accommodate a general
theory, but will specify the decomposition later to suit our purposes.
3.3. Smoothing Properties of Relaxation. Recall that the smoothing step
in the linear multigrid algorithm is defined as the replacement of the current approximation
with the correction w defined using q k as a preconditioner:
where r is the residual functional defined in (3.11). Here we assume that r is decomposed
according to (3.14) for some given decomposition of f according to (3.12). To
analyze the smoother, we will need two additional assumptions.
Assumption 3.3 (Properties of the forms a and b). Assume for all
Remark 3.6. Letting ae(\Delta) denote spectral radius, then (3.19)-(3.22) are equivalent
to the respective inequalities
In view of Assumption 3.1, we also have the equivalent respective assumptions
which are naturally satisfied by a wide class of discrete elliptic problems.
Assumption 3.4 (Smoother). Assume that w 2 V k is defined uniquely by
(3.18) and that
Further, suppose there exist a constant oe ? 0 such that
Remark 3.7. (3.25) is equivalent to the inequality
is self-adjoint in the inner product (\Delta; \Delta) and D k and L k
decompose C k
- according to C k
for some appropriate constant j ? 0. (Self-adjoint operators E and F are said to
satisfy the relation E - F if nonnegative definite.) Then (3.26) and (3.27)
are easily verified for this choice of Q k . This shows that Assumption 3.4 is natural for
Gauss-Seidel relaxation applied to linear equations that satisfy (3.28), which is easily
verified for Poisson's equation on a uniform grid, for example. For further discussion,
cf. [6]. Note also that the choice Q
and (3.27) under these
assumptions which corresponds to damped Jacobi relaxation.
Lemma 3.4 (Properties of the smoother).
as the solution of the problem
Then
as the solution of the problem
Then
and, for sufficiently small h 0 ,
c
oe
Proof. (i) (3.30) immediately follows from (3.19) and (3.25).
(ii) We first prove (3.32). From (3.16) we have r
It therefore
follows from (3.7) and (3.19) that
Hence,
Write
y. Using the fact that y
1 and relations (3.2), (3.21),
(3.25), and (3.34), we get
which is just (3.32).
To prove (3.33), note that
First note that, by (3.26), we have
oe
(3.35) and the inequality c - (e k
imply that
On the other hand, by (3.32) and (3.7), we have
We can thus conclude from the above two inequalities that
which with (2.8) gives (3.33) for all sufficiently small h 0 .
3.4. Properties of Coarse Grid Correction. Define the projection operator
2 by
Further, define the projection onto the c-orthogonal complement of V k\Gamma1by
Remark 3.8. For any v 2 V k , we have
and, consequently,
Lemma 3.5 (Stability of S k ).
Proof. (3.39) follows immediately from (3.7) and (3.38).
Lemma 3.6 (Eigenvector approximation properties).
and
Proof. Let k\Gamma1guaranteed by (3.4) to satisfy
Then
which establishes (3.40). A similar argument proves (3.41).
Lemma 3.7 (Eigenvector approximation property).
Proof. This is an immediate consequence of (3.40), (3.39), and (3.7).
The following standard approximation assumption follows from H 2 elliptic regularity
of the bilinear form a(\Delta; \Delta). See, for example, [6].
Assumption 3.5 (Standard approximation property). There exists a
constant there exists a w 2 V k\Gamma1 so that
Theorem 3.1 (Reduced approximation property). There exists a constant
Proof. Let
. According to the Cauchy-Schwarz inequality, Assumption 3.1,
(3.20), and (3.8), we have
Hence,
which, together with (3.21), (3.20), and (3.8), implies that
Let ~
be the a-orthogonal projection operator. Then, by Assumption
3.5 and (3.43), there exists a constant ffi ? 0 such that
Let
1 be such that (3.5) holds for v replaced by P k\Gamma1~
Pv. Then
Hence,
where we used (3.43). Now from this, (3.7), (3.44), and (3.23), we have
c
This completes the proof.
3.5. Combined Smoothing and Approximation Properties.
Lemma 3.8 (Reduced approximation property). Let w 2 V k be the solution
of the problem
Then, for sufficiently small h 0 ,
with
oe
where oe is given in (3.26) and ffi 0 is given in (3.42).
Proof. Let z and y be the solutions of the problems (3.29) and (3.31), respectively,
so that y. The triangle inequality and (3.7) then imply that
The proof of the lemma now follows from (3.33), (3.30), Theorem 3.1, and (3.37).
Before we estimate the error in the multigrid algorithm, we need to estimate
the error quantities just before the coarse grid correction. To this end, recall, in the
correction step of MG=, that the functional f is the restriction of the
residual functional r k; 0 to
f
Now
A given decomposition of f k according to (3.12) yields a decomposition of r k; 0 according
to
where
r k;
and U kis the solution of the problem (3.9). For any v 2 V
r k;
We are therefore led to choose
and
This provides a legitimate coarse grid decomposition according to (3.12) because the
functional f k\Gamma1vanishes on V k\Gamma1and
Let U k\Gamma12 V k\Gamma1be the solution of the problem
has a corresponding decomposition according
to
Lemma 3.9 (Initial coarse grid error estimates). The initial coarse grid
error satisfies
and
Proof. (3.48) follows immediately from the definitions of MG= k , e k\Gamma1; 0
2.
(3.49) follows from using (3.47), (3.46), the Cauchy-Schwarz inequality, (3.38),
(3.21), (3.20), and (3.7), to conclude that
By (3.46) and (3.47), we have
c(U
Choosing follows from (3.21), (3.20), (3.7), and (3.38).
To prove (3.51), let arbitrary. Then from (3.45), the
Cauchy-Schwarz inequality, (3.21), and (3.7), we have
Choosing kaccording to (3.5) with P
in place of v, it follows from (3.8)
that
Now since -
implies that
The above two inequalities imply (3.51).
3.6. Recursive Estimate. For convenience in what follows, we define the re-
lation
r
s
to mean that p - r and q - s. For
let
Theorem 3.2 (Recursive estimate). Assume that there is a constant C 0
such that MG=
with
and
with
and
Proof. From (3.53), (3.49), (3.51), and (3.38), we have
and
jje k\Gamma1;2
Letting
then it follows from (3.48) and (3.41) that
and
Now (3.13), (3.7), and (3.49) (noting that imply that
which, together with (3.40), gives
By definition, u . For any v 2 V k , decomposing r k; 1
according to (3.14) - (3.16) yields
r k;
Hence, by the Cauchy-Schwarz inequality, (3.21), and (3.20), we get
Letting ~
and, because u
we obtain
u:
From this, (3.38), and (3.50), we get
We can similarly conclude that
and
To estimate the size of e k; 2= U k\Gamma P k
note that Lemma 3.8 implies that
c
By using (3.59) - (3.69), (3.54), and (3.55), a lengthy computation shows that
3 and fi k satisfying (3.57).
It remains to estimate jjju k; 2
We have from (3.30) and (3.32) that
It thus follows from (3.64), (3.67), (3.61), (3.63), (3.65), (3.59), and (3.60) that
which completes the proof.
3.7. Linear V -cycle Estimate.
Theorem 3.3 (Linear V-cycle estimate). Suppose that MG= 0 satisfies@
jjr 0; 0jj
independently of h 0 and of the choice of the decomposition f
positive constants " 0
MG= l satisfies@
with
and
Proof. This follows directly from recursion on Theorem 3.2.
Lemma 3.10 (Direct solver). Let MG= 0 be defined by (2.9). Then (3.70)
holds constant independent of h 0 .
Proof. (2.9) is equivalent to assuming that u
defined by
Clearly, then,
that is, " decomposition according to (3.12) and
0be the solution of (3.50) with
which, together with (3.7), (3.8), and (3.20), implies that
Hence,
3 is a constant independent of h 0 . This completes the proof.
Remark 3.9. Since (3.70) holds with certainly holds with
Lemma 3.11 (Approximate solver). Let MG= 0 in the definition of MG=
be replaced by a mapping
such that, for any f 0 ,
and, for any f 0
2 that vanishes on V 0
where U 0 is defined by (3.9) with
and fi 0 from (3.75).
Proof. We have
From (3.74) and the fact that f 0= r 0; 0, we conclude that
It follows from (3.74) and the definition of U 0 that
The above inequalities imply that " 0
2. Since e 0; 2
, from (3.75) and (3.74) we have
This completes the proof.
4. Convergence of a Linearized Multigrid Method for Eigenvalue Prob-
lems. Here we apply the theory developed in the previous section to a linearized
multigrid method for solving the eigenvalue problem (2.5) with l. This method
uses an outer loop iterative process, which replaces the given approximate eigenfunction
old l by the new approximation u l
new l that is computed by applying
MG= to the problem
Assume for simplicity that MG= uses an exact coarsest-grid solver.
Here we are considering a conventional linearized multigrid method applied to
the eigenvalue problem, so the shift - is now considered to be fixed throughout each
multigrid cycle, allowed to change only between cycles via (4.1). However, the reader
should note that changes could be allowed anywhere within the multigrid cycles and
the proof of our next theorem would still apply. We will use this observation in proving
our theorem on RQMG. The reader should also note that this linearized algorithm
relies on the fact that no multigrid cycle will produce the exact solution of (4.2) (i.e.,
we will show that u l
new
LMG=Algorithm. Given an initial approximation u l
old
l to an eigenvector
for (2.5) belonging to - l such that jjju l
old
then the new approximation u l
new
LMG= l (u l
old
is defined as follows:
1. MG inner solver. Perform one step of MG= l applied to (4.2) using the
initial approximation u
old
and the shift
old
2. Normalization. Set
new
To analyze the convergence of LMG=, we define the error in an approximation
to an eigenvector of (2.5) belonging to - l
1 by
Note that - l-
Theorem 4.1 (Convergence of linearized multigrid). LMG= l converges
according to the estimate
new
old
for sufficiently small h 0 .
Proof. First note that the definition of - yields
Thus, writing u
which can be rewritten
Letting l, then from this relation and (2.8) we can conclude for
sufficiently small h 0 that
and that
Now let f l lcertainly vanishes on
l
and, noting that l, we apply Theorem 3.3, the Cauchy-Schwarz
inequality, and (4.5) to conclude that
kvk
kvk
Similarly, we apply Theorem 3.3 and (4.6) to obtain
From (4.7) we can conclude that
(4.8) and (4.9) now yield
new k c -
old
The proof now follows from (3.6).
Remark 4.1. The theory here for MG= assumes an exact coarsest-grid solver.
In fact, the theory holds if we assume only that the coarsest-grid solver is effective
enough that it does not contaminate the estimates in (3.71) and (3.72). In any event,
this theorem shows that the LMG= worst-case convergence factor is arbitrarily close
to the multigrid factor for standard well-posed linear elliptic equations provided (2.8)
holds. We will show in Section 6 that (2.8) can be guaranteed by the use of a full
multigrid or nested iteration process.
5. Convergence of RQMG for Eigenvalue Problems. In this section, we
apply the theory of Section 3 to RQMG, which is a direct multigrid method for (2.5)
involving minimization of the Rayleigh quotient over level k corrections to the fine-
grid eigenvector approximation. The approximate eigenvalue is the Rayleigh quotient
of the eigenvector approximation incorporating all current corrections, so it changes
during each level k correction. The main point in establishing RQMG convergence is
simply to recognize that the proof of Theorem 4.1 made no use of the fact that the
shift - was assumed to be fixed in the multigrid cycles.
Following is the definition of RQMG=, which (as MG was) is posed with an
exact coarsest-grid solver and a general smoother. To accommodate recursion, we
have defined RQMG= in terms of a given vector which should be interpreted
as the finest-level eigenvector approximation.
RQMG=Algorithm. Given an initial correction u l for the approximate
eigenvector then the new correction u defined as
follows:
a) If l = 0, then compute u l so that
b) If l ? 0, then perform the following:
1. Coarse-grid correction step. Set u
2. Smoothing step. Let l by
Then set u
Remark 5.1. The RQMG coarsest-grid correction step posed here is in the
spirit of our analysis in the sense that the V 0error component is guaranteed to be
unchanged. This is in contrast to the significant changes that can happen in the more
natural RQMG scheme of determining an optimal correction from the coarsest grid,
which would be much more difficult to analyze. However, the coarsest-grid solver used
here is no less practical because it can be implemented using projections onto V 0and
V 0, which are obtained naturally in the full multigrid process. That is, the eigenvector
approximation computed initially on the coarse grid can be used to implement the
coarsest-grid RQMG solver efficiently.
Theorem 5.1 (RQMG convergence). Suppose that the current eigenvector
approximation u l
old is in V l n f0g. Let u
old ). (Here we assume
that any nonzero initial correction has already been added into
old
.) Define the
new eigenvector approximation by u l
new
old
. Define the errors e l
old
and e l
new
in the respective approximations u l
old
and u l
new
as in (4.3). Then RQMG= l converges
according to the estimate
new
old
Proof. The coarsest-grid solver satisfies the assumptions of Lemma 3.11. Indeed,
setting to zero the Fr'echet derivative of RQ(u l
old
with respect to v 2 V 0,
we get
old
Hence,@
This proof is now completed by noting that
the proof of Theorem 4.1 did not rely on fixing the shift -, so it applies here without
modification.
6. Full Multigrid for Eigenvalue Problems. The theory developed in this
paper applies to the eigenvalue problem (2.1), but only in a local sense: the multigrid
convergence factors are guaranteed to be optimal (i.e., bounded uniformly above by a
constant less than one) only in a relatively small region about the eigenspace. More
precisely, if - 1 ) is the current approximation to the eigenvalue on level l, then
to obtain this optimality we need an estimate like (2.8).
Our purpose in this section is to show that this localness can be ensured by a full
multigrid procedure, which is an outer loop iteration that uses the basic multigrid
cycle first on coarser grids to obtain good initial guesses to the fine grid problem. We
will use this scheme to guarantee that the error on each level satisfies
which will suffice to prove (2.8) and, therefore, the optimality of the relevant multigrid
solver.
The full multigrid procedure will be posed in terms of a generic multigrid method
for solving the level l eigenvalue problem defined by (2.5). We write this generic
scheme in the form
new
old
which we assume converges in the sense of Theorems 4.1 and 5.1 with a factor bounded
above by the constant sufficiently
small. The following definition of the full multigrid process uses - 1 cycles of EMG
on progressively finer levels, but makes no use of an initial approximation.
FMG=Algorithm. The final approximation u l is defined as follows:
a) If l = 0, then compute u l 2 V l so that the error satisfies (2.8) and (6.1) for
b) If l ? 0, then perform the following:
1. Coarse grid solution. Set u
2. Multigrid step. Perform - steps of EMG= applied to (2.5) using the
initial approximation u
Note that the coarsest-grid (l = 0) step can be done by computing an accurate
approximation to u 0
1 . This follows from an estimate for the error measure that
we obtain in the proof of our last theorem. (See (6.2) and (6.3) below.)
Theorem 6.1 (Global convergence). Let sufficiently
small h 0 and large -, (2.8) and (6.1) are satisfied for all l - 0.
Proof. The case l = 0 is true by definition. Suppose for induction purposes that
(2.8) and (6.1) are true for l \Gamma 1. Writing u
first note
that
c
as in (4.3). With the analogous decomposition u
defining
1 , then by (3.8) and (3.5) it follows that
jjjP l
jjjP l
For sufficiently small h 0 , we therefore have that
kP l
jjjP l
(2.8) and (6.1) for l now follow from (6.2), (6.3), and the definition of fl that implies
jjjP l



--R

Analysis of a multilevel inverse iteration procedure for eigenvalue problems
Multigrid methods for differential eigenproblems
Multigrid solutions to linear and nonlinear eigenvalue problems for integral and differential equations
On the computation of approximate eigenvalues and eigenfunctions by means of a multigrid method
A multilevel variational method for Au
Variational multigrid theory
A mesh refinement method for Ax
Multilevel adaptive methods for elliptic eigenproblems: a two-level convergence theory
An analysis of the finite element method
--TR
singular equations;rayleigh quotient;multigrid;eigenvalue problem