A two-grid discretization scheme for eigenvalue problems

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 131516 for nonsymmertic and nonlinear elliptic problems. Later on, it was further investigated by many other authors, for instance, Axelsson and Layton 2 for nonlinear elliptic problems, Dawson and Wheeler 7 and Dawson, Wheeler and Woodward 8 for finite difference scheme for parabolic equations, Layton and Lenferink 9 and Utnes 12 for Navier-Stokes equations, Marion and Xu 11 for evolution equations, and Xu and Zhou 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 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 34, Chatelin 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$:

$$\begin{eqnarray} \begin{array}{rcl} -\Delta u&=& \lambda u, \qquad \text{in}\nobreakspace \Omega , \\[5.69046pt] u&=& 0, \qquad \text{on}\nobreakspace \partial \Omega . \end{array} {\tag{1.1}} \end{eqnarray}$$

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 (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)

$$\begin{equation*} \|\nabla (u-u^h)\|_{L^2}=O(h+H^2)\nobreakspace\nobreakspace\nobreakspace \text{and}\nobreakspace\nobreakspace\nobreakspace |\lambda ^h-\lambda |=O(h^2+H^4). \end{equation*}$$

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 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} a(w,v)&\lesssim & \|w\|\|v\|,\nobreakspace\nobreakspace\nobreakspace\nobreakspace \forall w, v\in X, \tag{2.1} \end{eqnarray}$$

$$\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

$$\begin{equation*} \|w\|_b\equiv b(w,w)^{1/2} \end{equation*}$$

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

$$\begin{equation*} \|w\|_{-a}=\sup _{v\in X_a, \|v\|_a=1}b(w,v). \end{equation*}$$

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$,

$$\begin{eqnarray} \lim _{h\to 0}\inf _{v\in S^h}\|w-v\|_a=0. {\tag{2.3}} \end{eqnarray}$$

Let $P_h$ be the orthogonal projection of $X_a$ onto $S^h$ defined by

$$\begin{equation*} a(w-P_hw, v)=0,\nobreakspace\nobreakspace\nobreakspace\nobreakspace \forall w\in X_a, v\in S^h. \end{equation*}$$

Clearly,

$$\begin{equation} \|P_hw\|_{a}\le \|w\|_{a}, \quad \forall w\in X_a. {\tag{2.4}} \end{equation}$$

If $w\in X_a$, then, by (2.3)

$$\begin{eqnarray} \|w-P_hw \|_{a}= o(1), \quad \text{as}\nobreakspace h \rightarrow 0. {\tag{2.5}} \end{eqnarray}$$

Let $\eta _a(h)$ be defined by

$$\begin{eqnarray*} \eta _a(h)=\sup _{f\in X_a,\|f\|_a=1} \inf _{v\in S^h}\|L^{-1}f-v\|_{a}, \end{eqnarray*}$$

where $L^{-1}: X_{-a}\longrightarrow X_a$ satisfies

$$\begin{equation*} a(L^{-1}f, v)=b(f, v),\nobreakspace\nobreakspace\nobreakspace\nobreakspace \forall f\in X_{-a}, v\in X_a. \end{equation*}$$

We have the following results (see Lemmas 3.3 and 3.4 in 3)

Lemma 2.1.

$$\begin{equation*} \eta _{a}(h)=o(1)\nobreakspace\nobreakspace\nobreakspace\nobreakspace \text{as}\nobreakspace h\rightarrow 0, \end{equation*}$$

and

$$\begin{eqnarray} \|w-P_hw\|_{-a}\lesssim \eta _{a}(h)\|w-P_hw\|_{a}, \quad \forall w\in X_a. {\tag{2.6}} \end{eqnarray}$$

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

$$\begin{eqnarray} a(u,v)=\lambda b(u,v),\nobreakspace\nobreakspace\nobreakspace\nobreakspace \forall v\in X_a. {\tag{3.1}} \end{eqnarray}$$

It is known that (3.1) has a countable sequence of real eigenvalues

$$\begin{equation*} 0<\lambda _1\le \lambda _2\le \lambda _3\le \cdots \end{equation*}$$

and corresponding eigenvectors

$$\begin{equation*} u_1, u_2, u_3,\cdots , \end{equation*}$$

which can be assumed to satisfy

$$\begin{equation*} a(u_i, u_j)=\lambda _jb(u_i, u_j)=\delta _{ij}. \end{equation*}$$

In the sequence $\{\lambda _j\}$, the $\lambda _j$ are repeated according to geometric multiplicity.

A standard finite element scheme for (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

$$\begin{eqnarray} a(u_h,v)=\lambda _h b(u_h,v),\nobreakspace\nobreakspace\nobreakspace\nobreakspace \forall v\in S^h, {\tag{3.2}} \end{eqnarray}$$

and use $\lambda _h$ and $u_h$ as approximations to $\lambda$ and $u$ (as $h \to 0$), respectively. One sees that (3.2) has a finite sequence of eigenvalues

$$\begin{equation*} 0<\lambda _{1,h}\le \lambda _{2,h}\le \cdots \le \lambda _{n_h,h},\nobreakspace\nobreakspace n_h=\text{dim}\nobreakspace S^h, \end{equation*}$$

and corresponding eigenvectors

$$\begin{equation*} u_{1,h}, u_{2,h},\cdots , u_{n_h,h}, \end{equation*}$$

which can be assumed to satisfy

$$\begin{equation*} a(u_{i,h}, u_{j,h})=\lambda _{j,h}b(u_{i,h}, u_{j,h})=\delta _{ij}. \end{equation*}$$

It follows directly from the minimum-maximum principle (see 4 or 5) that

$$\begin{equation*} \lambda _i\le \lambda _{i,h},\nobreakspace\nobreakspace\nobreakspace i=1,2,\cdots ,n_h. \end{equation*}$$

Set

$$\begin{equation*} \delta _h(\lambda _i)=\sup _{w\in M(\lambda _i)}\inf _{v\in S^h}\|w-v\|_{a} \end{equation*}$$

and

$$\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 4 and Lemma 3.7 and (3.29b) of 3, or cf. 5) will be employed in the coming discussions.

Proposition 3.1.

(i) For any $u_{i,h}$ of 3.2 $(i=1,2,\cdots ,n_h)$, there is an eigenvalue $u^i$ of 3.1 corresponding to $\lambda _{i}$ satisfying $\|u^i\|_a=1$ and

$$\begin{eqnarray} \|u^i-u_{i,h}\|_{a}\le C_i \delta _h(\lambda _i). {\tag{3.3}} \end{eqnarray}$$

Moreover,

$$\begin{eqnarray} \|u^i-u_{i,h}\|_{-a}\le C_i\eta _a(h)\|u^i-u_{i,h}\|_{a}. \tag{3.4} \end{eqnarray}$$

(ii) For eigenvalues,

$$\begin{eqnarray} \lambda _i\le \lambda _{i,h}\le \lambda _i+C_i\delta ^2_h(\lambda _i). {\tag{3.5}} \end{eqnarray}$$

Here and hereafter $C_i$ is some constant depending on $i$ but not depending on the mesh parameter $h$.

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:

Proposition 4.1.

$$\begin{eqnarray} \|P_hu^i-u_{i,h}\|_a\lesssim \lambda _{i,h}-\lambda _i+\lambda _i \|u^i-u_{i,h}\|_{-a}. \tag{4.1} \end{eqnarray}$$

Proof.

From the identity

$$\begin{equation*} a(P_hu^i-u_{i,h},v)=(\lambda _i-\lambda _{i,h})b(u_{i,h},v)+ \lambda _{i}b(u^i-u_{i,h},v),\nobreakspace\nobreakspace\nobreakspace \forall v\in S^h, \end{equation*}$$

we immediately obtain the result.

■

Our analysis is based on the following crucial (but straightforward) property of eigenvalue and eigenvector approximation (see e.g. Lemma 3.1 of 3 or Lemma 9.1 of 4).

Proposition 4.2.

Let $(\lambda , u)$ be an eigenvalue pair of 3.1. For any $w\in X_a\setminus \{0\}$,

$$\begin{eqnarray} \frac{a(w,w)}{b(w,w)}-\lambda =\frac{a(w-u, w-u)}{b(w,w)}- \lambda \frac{b(w-u,w-u)}{b(w,w)}. \tag{4.2} \end{eqnarray}$$

Algorithm 4.1.

(1)

Find $\lambda _{i,H}\in R^1$ and $u_{i,H}\in S^H$ $(i=1,2,\cdots ,n_H)$ such that $\|u_{i,H}\|_a=1$ and$$\begin{equation*} a(u_{i,H},v)=\lambda _{i,H}b(u_{i,H}, v),\nobreakspace\nobreakspace\nobreakspace \forall v\in S^H; \end{equation*}$$

(2)

Find $u^{i,h}\in S^h$ $(i=1,2,\cdots ,n_H)$ such that$$\begin{equation*} a(u^{i,h}, v)=\lambda _{i,H}b(u_{i,H}, v),\nobreakspace\nobreakspace\nobreakspace \forall v\in S^h; \end{equation*}$$

(3)

Set$$\begin{equation*} \lambda ^{i,h}=\frac{a(u^{i,h},u^{i,h})}{b(u^{i,h},u^{i,h})},\nobreakspace\nobreakspace\nobreakspace i=1,2,\cdots ,n_H. \end{equation*}$$

Theorem 4.3.

Assume that $(\lambda ^{i,h}, u^{i,h})$ $(i=1,2,\cdots ,n_H)$ are obtained by Algorithm 4.1. If $S^H\subset S^h$, then

$$\begin{eqnarray} \|u^i-u^{i,h}\|_{a}\lesssim \lambda _{i,H}-\lambda _i+ \lambda _i\|u^i-u_{i,H}\|_{-a} +\|u^i-P_hu^i\|_{a} {\tag{4.3}} \end{eqnarray}$$

and

$$\begin{eqnarray} |\lambda ^{i,h}-\lambda _i|\le C_i((\lambda _{i,H}-\lambda _i)^2+ \|u^i-u_{i,H}\|^2_{-a} +\|u^i-P_hu^i\|^2_{a}). {\tag{4.4}} \end{eqnarray}$$

Consequently,

$$\begin{eqnarray} \|u^i-u^{i,h}\|_{a}\le C_i(\delta _H^2(\lambda _i)+ \eta _a(H)\delta _H(\lambda _i) +\delta _h(\lambda _i)) {\tag{4.5}} \end{eqnarray}$$

and

$$\begin{eqnarray} |\lambda ^{i,h}-\lambda _i|\le C_i(\delta _H^4(\lambda _i) +\eta ^2_a(H)\delta ^2_H(\lambda _i)+\delta ^2_h(\lambda _i)). {\tag{4.6}} \end{eqnarray}$$

Proof.

From the identity

$$\begin{equation*} a(P_hu^i-u^{i,h},v)=(\lambda _i-\lambda _{i,H})b(u_{i,H},v)+ \lambda _{i}b(u^i-u_{i,H},v),\nobreakspace\nobreakspace\nobreakspace \forall v\in S^h, \end{equation*}$$

we immediately obtain (4.3). And (4.4) follows from (4.3) and Proposition 4.2. Finally, the last two conclusions are obtained from Proposition 3.1.

■

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

$$\begin{equation*} a(u, v)=\int _{\Omega } \sum ^d_{i,j=1} a_{ij}\frac{\partial u}{\partial x_i}\frac{\partial v}{\partial x_j}, \end{equation*}$$

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

$$\begin{eqnarray} S^h(\Omega )=\{v\in C(\bar{\Omega })\cap H^1_0(\Omega ): v\mid _{\tau }\in P^r_{\tau }, \forall \tau \in T^h(\Omega )\}, \tag{5.1} \end{eqnarray}$$

where $P^r_{\tau }$ is the space of polynomials of degree not greater than a positive integer $r$.

We assume that $M(\lambda _i)\subset H^{r+1}(\Omega )$. If $\Omega$ is polygonal and convex, then

$$\begin{eqnarray} \eta _a(h)=O(h),\nobreakspace\nobreakspace\nobreakspace\nobreakspace\nobreakspace \delta _h(\lambda _i)\le C_ih^r. \tag{5.2} \end{eqnarray}$$

Hence

$$\begin{eqnarray} \|u^i-u^{i,h}\|_{a}\le C_i(H^{r+1}+h^r) \tag{5.3} \end{eqnarray}$$

and

$$\begin{eqnarray} |\lambda ^{i,h}-\lambda _i|\le C_i(H^{2r+2}+h^{2r}). \tag{5.4} \end{eqnarray}$$

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$):

$$\begin{eqnarray} \eta _a(h)=O(h^2),\nobreakspace\nobreakspace\nobreakspace\nobreakspace \delta _h(\lambda _i)\le C_ih^r. \tag{5.5} \end{eqnarray}$$

Hence

$$\begin{eqnarray} \|u^i-u^{i,h}\|_{a}\le C_i(H^{\min \{r+2, 2r\}}+h^r) \tag{5.6} \end{eqnarray}$$

and

$$\begin{eqnarray} |\lambda ^{i,h}-\lambda _i|\le C_i(H^{2\min \{r+2, 2r\}}+h^{2r}). \tag{5.7} \end{eqnarray}$$

5.2. Fredholm integral operators

Let

$$\begin{equation*} (Kw)(x)=\int _{\Omega }k(x,y)w(y)dy \end{equation*}$$

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

$$\begin{eqnarray} S^h(\Omega )=\{v\in C(\bar{\Omega }): v\mid _{\tau }\in P^r_{\tau }, \forall \tau \in T^h(\Omega )\}. \tag{5.8} \end{eqnarray}$$

In this case, we have

$$\begin{eqnarray} \eta _a(h)=O(h^{r+1}),\nobreakspace\nobreakspace\nobreakspace\nobreakspace \delta _h(\lambda _i)\le C_ih^{r+1}, \tag{5.9} \end{eqnarray}$$

and hence

$$\begin{eqnarray} \|u^i-u^{i,h}\|_{a}\le C_i(H^{2r+2}+h^{r+1}) \tag{5.10} \end{eqnarray}$$

and

$$\begin{eqnarray} |\lambda ^{i,h}-\lambda _i|\le C_i(H^{4r+4}+h^{2r+2}). \tag{5.11} \end{eqnarray}$$

6. Nonselfadjoint problems

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.

Proposition 6.1.

Let $(\lambda , u)$ be an eigenvalue pair of 3.1. For any $w\in X_a\setminus \{0\}$,

$$\begin{eqnarray*} \frac{a(w,w)}{b(w,w)}-\lambda &=&\frac{a(w-u, w-u)}{b(w,w)}- \lambda \frac{b(w-u,w-u)}{b(w,w)}\\[5.69046pt] & &\nobreakspace\nobreakspace +\frac{a(w-u,u)-a(u,w-u)}{b(w,w)}. \end{eqnarray*}$$

Note that, for instance,

$$\begin{equation*} \mid a(w-u,u)-a(u,w-u)\mid \lesssim \|w-u\|_{1-r} \end{equation*}$$

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. 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} {\tag{7.1}} \end{eqnarray}$$

where $\Omega \subset R^2$ is the unit square domain $\Omega =(0, 1) \times (0, 1)$. The eigenvalues of (7.1) are easily seen to be given by

$$\begin{equation*} \lambda _{k,l}=(k^2+l^2)\pi ^2, \end{equation*}$$

and are associated with the eigenvectors

$$\begin{equation*} u_{k,l}=\sin (k\pi (x-1))\sin (l\pi (y-1)),\nobreakspace\nobreakspace\nobreakspace k,l=1,2, \cdots . \end{equation*}$$

Set a uniform triangulation $T^h(\Omega )=\{\tau \}$ (see Figure 2) and piecewise linear finite element space as follows:

$$\begin{equation*} S^h(\Omega )=\{v\in H^1_0(\Omega ): v\mid _{\tau }\nobreakspace \text{is linear},\nobreakspace \forall \tau \in T^h(\Omega )\}. \end{equation*}$$

Now we apply the algorithm to solve the problem (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.

Figure 1.

Two grids

Figure 2.

A triangulation

Table 1.

A two-grid algorithm for elliptic eigenvalue problems

$h$	$\|\nabla (u_h - u^h)\|_{L^2}$	$\displaystyle \frac{\|\nabla (u_{4h} - u^{4h})\|_{L^2}}{\|\nabla ( u_{h} - u^{h})\|_{L^2}}$	$|\lambda _h - \lambda ^h|$	$\displaystyle \frac{|\lambda _{4h}-\lambda ^{4h}|}{|\lambda _{h}- \lambda ^{h}|}$
$2^{-4}$	0.7401E-01		0.1255E-01
$2^{-6}$	0.2026E-01	3.6527	0.9028E-03	13.8980
$2^{-8}$	0.5183E-02	3.9090	0.5997E-04	15.0572
$2^{-10}$	0.1303E-02	3.9767	0.3811E-05	15.7322