Convergence of a Multigrid Method for Elliptic Equations with Highly Oscillatory Coefficients.
Standard multigrid methods are not so effective for equations with highly oscillatory coefficients. New coarse grid operators based on homogenized operators are introduced to restore the fast convergence rate of multigrid methods. Finite difference approximations are used for the discretization of the equations. Convergence analysis is based on the homogenization theory. Proofs are given for a two-level multigrid method with the homogenized coarse grid operator for two classes of two-dimensional elliptic equations with Dirichlet boundary conditions.
Introduction
Consider the multigrid method arising from the finite difference approximations to elliptic
equations with highly oscillatory coefficients of the following type
@
a ffl
where a ffl
strictly positive, continuous and 1-periodic in
each component of y. Also, the operator L ffl is uniformly elliptic. That is, there exist two
positive constants q and Q independent of ffl, such that
for any - i is assumed to be very small, representing the length of the
oscillations. These equations have important practical applications, for example, in the
study of elasticity and heat conduction for composite materials. One major mathematical
technique to deal with these equations is homogenization theory. The theory associates the
original equation with its microstructure to some macrostructure effective equation that
does not have oscillatory coefficients [2]. By homogenization, as ffl gets small, the solution
of (1.1) will converge to the solution u(x) of the following homogenized equation,
are constants, given by the following expressions,
)dy:
Here - j (y) is 1-periodic in y and satisfies
@
@
a ik (y):
Also, the homogenized operator L - retains the ellipticity property of the operator L ffl .
Multigrid methods are usually not so effective when applied to (1.1). Standard construction
of coarse grid operators may produce operators with different properties than those
of the fine grid operators [1, 3, 12]. In order to restore the high efficiency of the multigrid
method, a new operator for the coarser grid operator is developed [5, 6]. This operator is
called a homogenized coarse grid operator, based on the homogenized form of the equa-
tion. For full multigrid or with more general coefficients, the homogenized operator can be
numerically calculated from the finer grids based on the local solution of the so called cell
problem [5]. For numerical examples on model problems and on the approximation of heat
conduction in composite materials [6].
One difficulty for these problems is that the smaller eigenvalues do not correspond to
very smooth eigenfunctions. It is thus not easy to represent these eigenfunctions on the
coarser grids. After classical smoothing iterations on the fine grid, we know that the high
frequency eigenmodes of the errors are reduced, and only the low frequency eigenmodes are
significant. Partially following [8], one may realize that the low frequency eigenmodes can
be approximated by the corresponding homogenized eigenmodes. This is the reason why
effective or homogenized operators are useful when defining the coarse grid operator.
In this paper, using homogenized coarse grid operators, the convergence of the two
level method applied to two classes of (1.1) with Dirichlet boundary conditions is analyzed.
In chapter 2, we consider the equation with coefficient oscillatory in x direction In
chapter 3, we consider the equation with coefficient oscillatory diagonally. We show that
as both ffl and h go to zeros, our two level multigrid method converges when the number
of smoothing iteration fl is large enough as a function of h. We also require the ratio h=ffl
not to belong to a small resonance set. More precisely the convergence is proved under the
following conditions:
ffl For the first case in chapter 2,
ffl For the second case in chapter 3,
if h belongs to the set S(ffl; h 0 ) of Diophantine number,
kh
In [4], Engquist
called it the convergence essentially independent of ffl.
The purpose of this paper is to present new analysis in order to give a theoretical
explanation of the computational results presented in [5, 6]. The bounds on fl given above
are overly pessimistic compared to the numerical experiments but the h dependence in fl
exists also in the computations [5, 6]. The effect of not requiring h 2 S is also seen in the
numerical tests [5, 9].
If the coarse grid operator is defined, i.e., by direct arithmetic averaging an eigenmode
analysis of the type given in section 2 and 3 produces the estimate
difference between the correctly homogenized coarse grid operators and other operators is
qualitatively consistent with the computational results of [5, 6]. The O(h \Gamma2 ) estimate means
that there is no multigird effect and the convergence is only produced by the smoothing
iterations.
The l 2 difference between the inverse of the analytic operator L ffl and that of the corresponding
homogenized operator L - is of the order O(ffl) [2]. This indicates that an eigenmode
analysis of the type used in this paper cannot give estimates better than
This is close to the estimate in one space dimension fl - Ch \Gamma6=5 ln h in [9].
In special cases, it is possible to design prolongation, restriction and coarse grid operators
under that the resulting method corresponds to a direct solver [7]. This type of
algorithm and methods based on special discretizations with built in a priori knowledge of
the oscillatory behavior is outside the scope of this paper.
Since in the sequel of the paper the following lemma is often cited, we introduce it here
first.
Lemma 1.1 [4] Suppose g(x; y) 2 C 3 ([0; 1] \Theta [0; 1]) and is 1-periodic in y. Let x
We always denote the domain [0; 1] \Theta [0; 1] by -
(0; 1) by \Omega\Gamma and
-\Omega =\Omega by @ We
discretize the domain by the same number of grid points N with equal step size
both in x- and y-directions. The step size h is chose to belong to the set of S(ffl; h 0 ). And,
the ratio of h to the wavelength ffl is fixed to be an strictly irrational number.
-\Omega h denotes
the set of grid points (ih; jh) 2 -
\Omega\Gamma\Omega h for (ih; jh) 2 \Omega\Gamma and
@\Omega h for (ih; jh) 2 @
present some constants, independent of ffl and h. D i
are standard forward and
backward finite difference operators in x direction; D j
are for y direction. k \Delta k h
represents the discrete L 2 \Gammanorm, indexed from 1 to N \Gamma 1.
Oscillation Along a Coordinate Direction
2.1 Model Equation
Consider a special case of (1.1), a two-dimensional elliptic problem with coefficients oscillatory
in x-direction only,
@
@x a ffl (x) @OE ffl
@
@y a ffl (x) @OE ffl
@y
where a ffl (x) is a strictly positive continuous function, and a ffl
the operator satisfies the property of (1.2). From (1.3), the corresponding homogenized
equation of (2.1) is:
\Gamma-
0 a(x)dx are the harmonic and arithmetical averages
respectively.
As ffl goes to zero, we know that the solution OE ffl of (2.1) converges to the solution OE of
(2.2).
Now, consider a corresponding discretized equation of (2.1),
where a
Denote the discretization of the homogenized operator \Gamma- @ 2
a @ 2
in (2.2) by
The operator of the two level method by using
the homogenized coarse grid operator [5, 6] can be expressed as
For simplicity, in the sequel of the paper, I H
h and I h
H always denote the weighting restriction
and bilinear interpolation respectively, and the smoothing operator S,
where ff is the inverse of the largest eigenvalue of L ffl;h , has order of h \Gamma2 . LH is taken to be
the corresponding homogenized operator L -;H .
2.2 Convergence Analysis
Instead of the operator M , we consider a simplified operator, denoted by M 1 ,
Theorem 2.1 If the ratio of h to ffl is fixed, h belongs to the set of Diophantine number
defined in (1.6), then there exist two constants C and ae 0 such that
whenever
Let's introduce some lemmate first, which are used in the proof of Theorem 2.1.
Lemma 2.1 Assume
Then, Z i is bounded, and satisfies
Proof. By Lemma 1.1, taking
Z 11
a(y)
Hence,
Z 11
a(y)
Z 11
a(y)
Z i is bounded for satisfies the following equation,
a
Proof. Directly applying Lemma 1.1, we can establish the result. 2
Lemma 2.3 Assume U ij satisfies
where
ij ) is a normalized eigenpair of L ffl;h . That is,
Then,
(D i
Proof. Multiplied by U ij ,
added by parts, (2.9) then follows.
For (2.10), note first for any grid function U ij , vanishing on
@\Omega h , we have
(D i
(D i
(D i
Multiply D i
both sides of (2.8), and take summation,
Then, we can establish
for some constant C. Analogously, we can get
(2.11), (2.12) and (2.13) complete the proof. 2
Lemma 2.4 Assume OE h
are defined in Lemma 2.3. Then,
Proof. Introduce the following discrete function
where Z i is defined in Lemma 2.1. Such G ij vanishes at boundary, i.e.,
By calculation, we have
where (i;
2\Omega h , and j i is defined in Lemma 2.2. Multiply G ij on both sides, and take
summation,
a
a
(D i
(D j
(D j
\Theta
(D i
By Lemma 2.3, we have
(D i
Hence, v u u u t
(D i
By Poincare inequality,
By Lemma 2.1 and Lemma 2.3,
Hence,
Meanwhile, the inequality tells us that
The proof of lemma is completed. 2
We are now able to show Theorem 2.1.
Proof of Theorem 2.1. Denote the eigenvalues of L ffl;h and \Delta h (Laplacian operator) by - ffl
respectively, where by dividing the set of eigenvalues into
two subsets, say f-
we can split the complete eigenspace of L ffl;h into two orthogonal subspaces. Namely, the
space of low frequency expanded by the eigenfunctions whose corresponding eigenvalues
belong to the first set, and that of high frequency expanded by the eigenfunctions whose
corresponding eigenvalues belong to the second set. By minimax principle of eigenvalues,
it is easy to see that
for some constants c and C.
For any normalized vector - such that
where
Thus,
In the following analysis, we consider (2.17) in two steps.
Step 1: Low frequency subspace.
I
-;h L ffl;h )OE ffl
By Lemma 2.4,
-;h L ffl;h )OE ffl
The corresponding eigenvalue of Laplacian operator \Delta h can be explicitly expressed as
By Taylor expansion, it follows that
Hence,
I
By the constraint \Sigma
I
Since the ratio of h to ffl is fixed to be an irrational number, h has the same order as ffl. We
have
I 1 - Chk 3
Therefore, in order to make I 1 ! 1, it's sufficient to have
Step 2: High frequency subspace.
I
-;h L 1ffl;h )k h kL2
-;h L2
I
r
k 2), we have
I
For I 2 - 1, it is sufficient to have
Combining (2.21) and (2.24), we have
The proof is completed. 2
Now, we are ready to show the main result.
Theorem 2.2 There exists constant C, the operator M defined by (2.5) satisfies
whenever h belongs to the set S(ffl; h 0 ) of Diophantine number, and
Before we carry out the proof, we need the following lemma. Let
Lemma 2.5 For some constant C,
Proof. Since L -;h and are the homogenized operators defined respectively on
fine and coarser grid with constant coefficients, they are well behaved [11, 12]. Furthermore,
Therefore,
(2.26)Proof of Theorem 2.2. Note that
Therefore,
Since ae(M) - kMk h , by Theorem 2.1 and Lemma 2.5, the rest of the proof can easily
Oscillation Along the Diagonal Direction
3.1 Model Equation
Consider another special case of (1.1), a two-dimensional elliptic problem with coefficients
oscillatory diagonally,
@
@x
a ffl
@
@y
a ffl
@y
where a ffl (x) is a strictly positive continuous function, and a ffl
Also, the operator has the property of (1.2). From (1.3), the corresponding homogenized
equation of (3.1) is:
As ffl goes to zero, we know that the solution OE ffl of (3.1) converges to the solution OE of
(3.2).
Now, consider a corresponding discretized equation of (3.1),
where
Here, we assume the discretized coefficients have the following property,
a
Denote the discretization of the homogenized operator
a
in (3.2) by
(D i
(D i
k=1a k0
k=1 a k0 .
The operator of the two level method can be expressed as
where ff is the inverse of the largest eigenvalue of L ffl;h , has order of h \Gamma2 . And
3.2 Convergence Analysis
We still first consider the simplified operator M 1 defined in (2.6).
Theorem 3.1 If the ratio of h to ffl is strictly irrational, h belongs to the set of Diophantine
number defined in (1.6), then there exist two constants C and ae 0 such that
whenever
In order to prove Theorem 3.1, we introduce the following lemmate first.
Lemma 3.1 Define two discrete functions on
k=1a kj
k=1a k0
are bounded, and satisfy
for (i;
2\Omega h .
Proof. Notice that by the assumption of the coefficients,
a kj
Applying the operator L ffl;h to Z 1
ij as follows,
k=1a kj
By Lemma 1.1,
k=1a kj
Hence, Z 1
ij is bounded for (i;
-\Omega h , and satisfies
The result can be deduced similarly for Z 2
ij . We can also show that Z 2
ij , and satisfies
This proves the lemma. 2
Remark. The explicit forms of Z 1
ij and Z 2
ij depend on a ffl being a function of x \Gamma y.
For the general angular dependences a ffl (ffx + fiy), these forms would not be possible.
Lemma 3.2 Assume discrete function defined as
a
bounded, and has the following properties
Proof. Using the symmetric properties of the coefficients, we can establish the results
similarly as in Lemma 3.1. 2
Lemma 3.3 Assume U ij satisfies
(3.
where
ij ) is a normalized eigenpair of L ffl;h . Then, we have
and
Proof. First, we observe that
Applying U ij to the following equation and taking summation, we have
then follows. For (3.12), since U ij vanishes at the boundary, it satisfies2
(D i
(D i
(D i
Multiplying D i
to (3.10), we get
(D i
(D i
(D i
(D i
By the uniformly ellipticity property of the homogenized operator (3.4), we have
An similar argument gives
(3.13), (3.14) and (3.15) complete the proof of lemma. 2
Lemma 3.4 Assume that U ij defined in Lemma 3.3 satisfies the following boundary conditions

Then,
(D i
(D i
Proof. Since
we have
(D i
(D i
Then,
(D i
(D i
(D i
Combined (3.12) with the following relation,
the rest of the proof follows. 2
Theorem 3.2 Assume OE h
are defined in Lemma 3.3 and Lemma 3.4. Then,
Proof. First, we introduce the following discrete functions
for (i;
\Omega h . By the assumption (3.16), G ij vanishes at boundary, i.e.,
For
ij , we have
(D i
(D j
Then,
For
ij , we establish similarly
(D i
(D j
Then,
a
a
(b ij+1 Z 2
For simplicity, we introduce another two operators, L 1 and L by
(D i
and
a
a
Observe that
from (3.19), (3.20) and (3.21), we get
(b ij+1 Z 2
Meanwhile, by Lemma 3.2, taking summations by parts, we have
(D j
\Gammaffl
\Gammaffl
By the symmetric property of the coefficients, a
Proceeding in the same way as before, we obtain
Combining (3.23), (3.24), (3.25) and (3.26), we get
(D j
Further,
[a
(D i
(D i
(D i
(D i
The exact same order for the last three terms in (3.22) can be established similarly. Con-
sequently, from (3.27) and (3.28),
(D i
By Poincare inequality,
By Lemma 3.1 and Lemma 3.3,
which implies,
We hence complete the proof. 2
Remark. The result in (3.18) here is consistent with the result established in [8] for the
continuous case.
Proof of Theorem 3.1. The procedure is exactly the same as that in Theorem 2.1, except
different inequalities estimated. By Theorem 3.2, we have
I
instead of (2.20). Therefore, in order to make I 1 ! 1, we set
instead of (2.21). For I 2 - 1, it is sufficient to have
Combining (3.31) and (3.32), we have
what we have done in previous section, we consequently establish the following main
Theorem.
Theorem 3.3 There exists constant C, the operator M defined by (2.5) satisfies
whenever the step size h belongs to the set S(ffl; h 0 ) of Diophantine numbers, and
The analysis of the proof strongly indicates us the role of homogenization, which plays in
the convergence process. If, for example, the coarse grid operator is replaced by its averaged
operator in one dimensional problem [5], the direct estimate for multigrid convergence rate
is not asymptotically better than just using the damped Jacobi smoothing operator. This
follows from the effect of the oscillations on the low eigenmodes. The homogenized coarse
grid operator reduces the number of smoothing operation from O(h \Gamma2 ) to O(h \Gamma6=5 ln h),
when the step size h belongs to the set S(ffl; h 0 ) of Diophantine numbers. In [9], it has
also been shown that the number of smoothing iteration needed for the convergence of
the multigird method with the average coarse grid operator guarantees the one with the
homogenized coarse grid operator.
The theoretical results established in this paper seem a little bit disappointing. From a
number of numerical experiments [5, 6], we can get much faster convergence rate in practice
than that required in the theoretical results. However, numerical results do indicate that
the convergent rate depends on the grid size h for these types of equations with oscillatory
coefficients [5, 6].
There are some inequalities in the implementation of the proof, which are potential to
be improved so that a sharper convergent rate is possible. One of them is to enlarge the
space of low eigenmodes, which can be approximated by the corresponding homogenized
eigenmodes. Such as to improve (3.18) to (2.14), which we think is the sharpest inequality
one can establish. We established the same inequality for the one dimensional case as
in the two dimensional case oscillatory along a coordinate direction [9]. However,
the portion of the eigenmodes that can be approximated by the homogenized ones in later
case is relatively much smaller than the previous one. That's why we obtain O(h \Gamma4=3 ln h)
for the number of smoothing iterations instead of O(h \Gamma6=5 ln h) for the later case, although
there have the same inequality (2.14) for the space of low eigenmodes.
Nevertheless, from the analysis of homogenization, we understand that there always
exists a boundary layer [2, 10], which makes it hard to get the first lower order correction
of the eigenfunctions. The case we discussed in chapter 2, which is equivalently to one
dimensional problem, doesn't have such a boundary layer. We hence get an estimate
as in (2.14). For the case in chapter 3, all we can establish is (3.18), which consists of
the result established in [8] for the continuous case. And, it also defines us a smaller
low eigenspace. However, numerical examples tells us that there are also some difference
between these two cases. That a complete understanding of the first lower order correction
for the eigenfunctions is required to further improve the estimates.



--R

The Multi-Grid Method for the Diffusion Equation with Strongly Discontinuous Coefficients
Asymptotic Analysis for Periodic Structure

Computation of Oscillatory Solutions for Partial Differential Equations
Multigrid Methods For Differential Equations With Highly Oscillatory Coefficients.
New Coarse Grid Operators of Multigrid Methods for Highly Oscillatory Coefficient Elliptic Problems.
Grid Transfer Operators for Highly Variable Coefficient Problems.
Homogenization of Elliptic Eigenvalue Problems: Part 1
Multigrid Method for Elliptic Equation with Oscillatory Coefficients.
First Order Corrections to the Homogenized Eigenvalues of a Periodic Composite Medium.
New York: springer- Verlag
Multigrid Methods
--TR
convergence;oscillation;homogenization theory;elliptic equation;finite difference;multigrid method