A two-grid discretization scheme for eigenvalue problems
By Jinchao Xu and Aihui Zhou
Abstract
A two-grid discretization scheme is proposed for solving eigenvalue problems, including both partial differential equations and integral equations. With this new scheme, the solution of an eigenvalue problem on a fine grid is reduced to the solution of an eigenvalue problem on a much coarser grid, and the solution of a linear algebraic system on the fine grid and the resulting solution still maintains an asymptotically optimal accuracy.
1. Introduction
The purpose of this paper is to present some discretization techniques based on two finite element spaces for solving eigenvalue problems, including both partial differential equations and integral equations.
The two-grid method used for discretization was first introduced by Xu Reference 13Reference 15Reference 16 for nonsymmertic and nonlinear elliptic problems. Later on, it was further investigated by many other authors, for instance, Axelsson and Layton Reference 2 for nonlinear elliptic problems, Dawson and Wheeler Reference 7 and Dawson, Wheeler and Woodward Reference 8 for finite difference scheme for parabolic equations, Layton and Lenferink Reference 9 and Utnes Reference 12 for Navier-Stokes equations, Marion and Xu Reference 11 for evolution equations, and Xu and Zhou Reference 17 for parallelization of two-grid discretizations.
In this paper we propose a two-grid discretization for eigenvalue problems. With the new proposed scheme, for example, solving an elliptic eigenvalue problem will not be much more difficult than the solution of some standard elliptic boundary value problem. A similar scheme can also be applied to solve integral eigenvalue problems. Our method is an iterative method, which is, in a way, related to that in Lin Reference 10. The method in this paper, however, is based on two finite element spaces with different scales.
The standard Galerkin approximation scheme for eigenvalue problems has been extensively investigated, see e.g., Babuska and Osborn Reference 3Reference 4, Chatelin Reference 5, and references cited therein, and some basic results in these papers are employed in our discussions.
In the remainder of this section, we would like to give a simple example to illustrate the main idea in this paper. Consider the following eigenvalue problem posed on a convex polygonal domain $\Omega \subset R^2$:
Let $S^H(\Omega )$ and $S^h(\Omega )$, satisfying $S^H(\Omega )\subset S^h(\Omega )\subset H^1_0(\Omega )$, be two linear finite element subspaces associated with a coarse grid $T^H(\Omega )$ and the refined grid $T^h(\Omega )$ (see Figure 1), respectively. We can employ the following algorithm to approximate the problem (Equation 1.1), say the first eigenvalue $\lambda$ with its corresponding eigenvector $u$ and $\|\nabla u\|_{L^2}=1$ (see Sections 4 and 5):
(1)
Solve an eigenvalue problem on a coarse grid: Find $\lambda _H\in R^1, u_H\in S^H(\Omega )$ such that $\|\nabla u_H\|_{L^2}=1$ and$$\begin{eqnarray*} \int _{\Omega }\nabla u_H\cdot \nabla v=\lambda _H\int _{\Omega }u_Hv, \quad \forall v\in S^H(\Omega ). \end{eqnarray*}$$
(2)
Solve one single linear problem on a fine grid: Find $u^h\in S^h(\Omega )$ such that$$\begin{eqnarray*} \int _{\Omega }\nabla u^h\cdot \nabla v=\lambda _H\int _{\Omega }u_Hv, \quad \forall v\in S^h(\Omega ). \end{eqnarray*}$$
(3)
Compute the Rayleigh quotient$$\begin{equation*} \lambda ^h=\frac{\|\nabla u^h\|^2_{L^2}}{\|u^h\|^2_{L^2}}. \end{equation*}$$
If, for example, $\lambda _H$ is the first eigenvalue of the problem at the first step, then we can establish the following results (see Sections 4 and 5)
These estimates mean that we can obtain asymptotically optimal errors by taking $H=O(\sqrt h)$.
2. Preliminaries
In this section, we shall describe some basic notation and properties of the standard finite element approximation.
Throughout this paper, we shall use the letter C (with or without subscripts) to denote a generic positive constant which may stand for different values at its different occurrences. For convenience, following Reference 14, the symbols $\lesssim , \gtrsim$ and $\eqsim$ will be used in this paper. The expressions $x_1\lesssim y_1$,$x_2\gtrsim y_2$ and $x_3\eqsim y_3,$ mean that $x_1\le C_1 y_1$,$x_2\ge c_2 y_2$ and $c_3 x_3\le y_3 \le C_3x_3$ for some constants $C_1, c_2, c_3$ and $C_3$ that are independent of the mesh parameters (and the exact eigenvalues).
Suppose that $(X, \|\cdot \|)$ is a real Hilbert space with inner product $(\cdot ,\cdot )$ and norm $\|\cdot \|$. Let $a(\cdot ,\cdot ), b(\cdot ,\cdot )$ be two symmetric bilinear forms on $X\times X$ satisfying
$$\begin{eqnarray} \|w\|^2\lesssim a(w, w),\nobreakspace\nobreakspace\nobreakspace\nobreakspace \forall w\in X\nobreakspace\nobreakspace \text{and}\nobreakspace\nobreakspace 0<b(w,w),\nobreakspace\nobreakspace\nobreakspace\nobreakspace \forall w\in X, w\not =0. \tag{2.2} \end{eqnarray}$$ We note that $\|\cdot \|_a\equiv a(\cdot , \cdot )^{1/2}$ and $\|\cdot \|$ are two equivalent norms on $X$. We assume that the norm $\|\cdot \|$ is relatively compact with respect to the norm
in the sense that from any sequence which is bounded in $\|\cdot \|$, one can extract a subsequence which is Cauchy with respect to $\|\cdot \|_b$. In the rest of this paper, we shall use $a(\cdot ,\cdot )$ and $\|\cdot \|_a$ as the inner product and norm on $X$, and denote this space by $X_a$. Set
$$\begin{equation*} X_b= \text{the completion of $X_a$ with respect to $\|\cdot \|_b$}. \end{equation*}$$
Thus $X_b$ is a Hilbert space with inner product $b(\cdot ,\cdot )$ and is compactly imbedded in $X_a$. Construct a “negative space” $X_{-a}= \text{the dual of $X_a$ with a norm $\|\cdot \|_{-a}$}$ given by
Then $X_b\subset X_{-a}$ compactly, and for $v\in X_a, b(w,v)$ has a continuous extension to $w\in X_{-a}$ so that $b(w,v)$ is continuous on $X_{-a}\times X_a$.
We assume that $S^h\subset X_a$ is a family of finite-dimensional spaces that satisfy the following assumption: For any $w\in X_a$,
We have the following results (see Lemmas 3.3 and 3.4 in Reference 3)
3. A standard discretization
A number $\lambda$ is called an eigenvalue of the form $a(\cdot ,\cdot )$ relative to the form $b(\cdot ,\cdot )$ if there is a nonzero vector $u\in X_a$, called an associated eigenvector, satisfying
In the sequence $\{\lambda _j\}$, the $\lambda _j$ are repeated according to geometric multiplicity.
A standard finite element scheme for (Equation 3.1) is: Find a pair $(\lambda _h, u_h)$, where $\lambda _h$ is a number and $0\not =u_h\in S^h$, satisfying
and use $\lambda _h$ and $u_h$ as approximations to $\lambda$ and $u$ (as $h \to 0$), respectively. One sees that (Equation 3.2) has a finite sequence of eigenvalues
$$\begin{equation*} \hspace{-1.5pc} M(\lambda _i)=\{w\in X_a: w\nobreakspace \text{is an eigenvector of (\xhref[disp-formula]{#eigen}{3.1}) corresponding to}\nobreakspace \lambda _i, \|w\|_a=1\}. \hspace{-1.5pc} \end{equation*}$$
The following results (see p. 699 of Reference 4 and Lemma 3.7 and (3.29b) of Reference 3, or cf. Reference 5) will be employed in the coming discussions.
4. A two-grid discretization
In this section, we propose a two-grid discretization for the eigenvalue problem. There is some superclose relationship between the Ritz-Galerkin projection of the eigenvector and the finite element approximation to the eigenvector:
Our analysis is based on the following crucial (but straightforward) property of eigenvalue and eigenvector approximation (see e.g. Lemma 3.1 of Reference 3 or Lemma 9.1 of Reference 4).
5. Examples
The general two-grid discretization scheme presented in this paper can be applied to a large class of eigenvalue problems. In this section, as an illustration, we give two examples, one for a partial differential operator and another for an integral operator. Let $\Omega \subset R^d$$(d=1,2,\cdots )$ be a bounded domain and $T^h(\Omega )$, consisting of shape-regular simplices, be a mesh of $\Omega$ of size $h$.
5.1. Second order elliptic operators
Let $b(\cdot ,\cdot )=(\cdot ,\cdot )$ be the standard inner product of $L^2(\Omega )$, and let
satisfying $a_{ij}\in W^{1,\infty }(\Omega )$ and $(a_{ij})$ is uniformly positive definite on $\Omega$.
Set $X_a=H^1_0(\Omega )$ and $X_b=L^2(\Omega )$. Define $S^h(\Omega )$ to be a space of continuous functions on $\Omega$ and vanishing at the boundary $\partial \Omega$, such that for $v\in S^h(\Omega ), v$ restricted to each $\tau$ is a polynomial of total degree $\le r$, namely
If $\Omega$ has $C^1$-smooth boundary, then better estimates can be obtained for Neumann boundary value problems (using $H^1(\Omega )/R^1$, boundary elements fitting $\partial \Omega$ exactly and $r>1$):
be the symmetric and positive definite Fredholm integral operator on $L^2(\Omega )$, where $k(x,y)\in C^{r+1}(\Omega \times \Omega )$. Set $a(\cdot ,\cdot )=(\cdot ,\cdot )$, the standard inner product of $L^2(\Omega ), b(\cdot ,\cdot )=(K\cdot ,\cdot ), X_a=L^2(\Omega )$ and $X_b=$ the completion of $X_a$ with respect to $\|\cdot \|_b$.
Define $S^h(\Omega )$ to be a space of continuous functions on $\Omega$ such that for $v\in S^h(\Omega ), v$ restricted to each $\tau$ is a polynomial of total degree $\le r$, namely
The approaches presented in the above can be applied to nonselfadjoint eigenvalue problems. We assume that $b(\cdot ,\cdot )$ is symmetric but $a(\cdot ,\cdot )$ may not be symmetric; then the following property of eigenvalue and eigenvector approximation can also be established for nonselfadjoint cases.
and $\|w-u\|_{1-r}\ll \|w-u\|_1$, when $r>1$ and $a(\cdot ,\cdot )$ is the bilinear form derived from a general elliptic problem of second order.
Hence, in this case, our approach will work well. In fact, other techniques for dealing with nonselfadjoint problems can also be employed, cf. Reference 16.
7. Numerical experiments
For illustration, in this section, we report some simple numerical experiments for a second order elliptic operator.
We consider the following eigenvalue problem:
$$\begin{eqnarray} \begin{array}{rcl} -\Delta u &=&\lambda u, \qquad \text{in}\nobreakspace \Omega ,\\u &=&0, \qquad \text{on}\nobreakspace \partial \Omega ,\\\end{array} \cssId{nueigen1}{\tag{7.1}} \end{eqnarray}$$
where $\Omega \subset R^2$ is the unit square domain $\Omega =(0, 1) \times (0, 1)$. The eigenvalues of (Equation 7.1) are easily seen to be given by
Now we apply the algorithm to solve the problem (Equation 7.1) using the fine meshes of sizes $h=2^{-j}$$(j=4, 6, 8, 10)$ and corresponding coarse meshes of size $H=\sqrt {h}$, and apply the algorithm as described in the introduction.
If $\lambda _H$ is the first eigenvalue of the problem, then by Theorem 4.3, we have
$$\begin{equation*} \|\nabla (u_h-u^h)\|_{L^2}=\mathcal{O}(H^2)\approx c h\nobreakspace\nobreakspace\nobreakspace \text{and}\nobreakspace\nobreakspace\nobreakspace |\lambda ^h-\lambda _h|=\mathcal{O}(H^4)\approx c h^2, \end{equation*}$$
where $(\lambda _h, u_h)$ is the standard first finite element eigenpair on $T^h$.
The results shown in Table 1 are consistent with the above estimates.
Acknowledgment
The authors wish to thank H. Kim for his assistance with numerical experiments.
$$\begin{eqnarray} \begin{array}{rcl} -\Delta u &=&\lambda u, \qquad \text{in}\nobreakspace \Omega ,\\u &=&0, \qquad \text{on}\nobreakspace \partial \Omega ,\\\end{array} \cssId{nueigen1}{\tag{7.1}} \end{eqnarray}$$
References
[1]
Adams R.A.(1975): Sobolev Spaces, Academic Press, New York. MR 56:9247
Reference [2]
Axelsson, O. and Layton, W.(1996): A two-level discretization of nonlinear boundary value problems, SIAM J. Numer. Anal., 33, 2359-2374. MR 98c:65181
Reference [3]
Babuska, I. and Osborn, J.E.(1989): Finite element-Galerkin approximation of the eigenvalues and eigenvectors of selfadjoint problems, Math. Comp., 52, 275-297. MR 89k:65132
Reference [4]
Babuska, I. and Osborn, J.E.(1991): Eigenvalue problems, Handbook of Numerical Analysis, Vol. II, Finite Element Methods (Part 1) (P.G. Ciarlet and J.L. Lions, eds.), Elsevier, 641-792. MR 92f:65001
Reference [5]
Chatelin, F.(1983): Spectral Approximations of Linear Operators, Academic Press, New York. MR 86d:65071
[6]
Ciarlet, P.G. and Lions J.L.(1991): Handbook of Numerical Analysis, Vol.II, Finite Element Methods (Part I), North-Holland. MR 92f:65001
Reference [7]
Dawson, C.N. and Wheeler, M.F.(1994): Two-grid methods for mixed finite element approximations of nonlinear parabolic equations, Contemp. Math., 180, 191-203. MR 95j:65117
Reference [8]
Dawson, C.N., Wheeler, M.F. and Woodward, C.S.(1998): A two-grid finite difference scheme for nonlinear parabolic equations, SIAM J. Numer. Anal.,35, 435-452. MR 99b:65097
Reference [9]
Layton, W. and Lenferink, W.(1995): Two-level Picard and modified Picard methods for the Navier-Stokes equations, Appl. Math. Comp., 69, 263-274. MR 95m:65191
Reference [10]
Lin, Q.(1979): Some problems concerning approximate solutions of operator equations, Acta Math. Sinica, 22, 219-230(Chinese). MR 80k:65056
Reference [11]
Marion, M. and Xu, J.(1995): Error estimates on a new nonlinear Galerkin method based on two-grid finite elements, SIAM J. Numer. Anal., 32, 1170-1184. MR 96f:65136
Reference [12]
Utnes, T.(1997): Two-grid finite element formulations of the incompressible Navier-Stokes equations, Comm. Numer. Methods Engrg., 34, 675-684. MR 98d:76110
Reference [13]
Xu, J.(1992): A new class of iterative methods for nonselfadjoint or indefinite problems, SIAM J. Numer. Anal., 29, 303-319. MR 92k:65063
Reference [14]
Xu, J.(1992): Iterative methods by space decomposition and subspace correction, SIAM Review, 34, 4, 581-613. MR 93k:65029
Reference [15]
Xu, J.(1994): A novel two-grid method for semilinear equations, SIAM J. Sci. Comput., 15, 231-237. MR 94m:65178
Reference [16]
Xu, J.(1996): Two-grid discretization techniques for linear and nonlinear PDEs, SIAM J. Numer. Anal., 33, 1759-1777. MR 97i:65169
Reference [17]
Xu, J. and Zhou, A.(1998): Local and parallel finite element algorithms based on two-grid discretizations, Math. Comp.(to appear).
This work was partially supported by NSF DMS-9706949, NSF ACI-9800244 and NASA NAG2-1236 through Penn State, and the Center for Computational Mathematics and Applications, The Pennsylvania State University, and by NSF ASC 9720257 through UCLA. The second author was also partially supported by National Science Foundation of China.
Journal Information
Mathematics of Computation, Volume 70, Issue 233, ISSN 1088-6842, published by the American Mathematical Society, Providence, Rhode Island.
Publication History
This article was received on , revised on , and published on .
Note. To explore an equation, focus it (e.g., by clicking on it) and use the arrow keys to navigate its structure. Screenreader users should be advised that enabling speech synthesis will lead to duplicate aural rendering.