# 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 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 :

Let and satisfying , be two linear finite element subspaces associated with a coarse grid , and the refined grid (see Figure 1), respectively. We can employ the following algorithm to approximate the problem (Equation 1.1), say the first eigenvalue with its corresponding eigenvector and (see Sections 4 and 5):

- (1)
Solve an eigenvalue problem on a coarse grid: Find such that and

- (2)
Solve one single linear problem on a fine grid: Find such that

- (3)
Compute the Rayleigh quotient

If, for example, 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 .

## 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 and will be used in this paper. The expressions , and mean that , and for some constants and that are independent of the mesh parameters (and the exact eigenvalues).

Suppose that is a real Hilbert space with inner product and norm Let . be two symmetric bilinear forms on satisfying

We note that and are two equivalent norms on We assume that the norm . is relatively compact with respect to the norm

in the sense that from any sequence which is bounded in one can extract a subsequence which is Cauchy with respect to , In the rest of this paper, we shall use . and as the inner product and norm on and denote this space by , Set .

Thus is a Hilbert space with inner product and is compactly imbedded in Construct a “negative space” . given by

Then compactly, and for has a continuous extension to so that is continuous on .

We assume that is a family of finite-dimensional spaces that satisfy the following assumption: For any ,

Let be the orthogonal projection of onto defined by

Clearly,

If then, by ( ,Equation 2.3)

Let be defined by

where satisfies

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

## 3. A standard discretization

A number is called an eigenvalue of the form relative to the form if there is a nonzero vector called an associated eigenvector, satisfying ,

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

and corresponding eigenvectors

which can be assumed to satisfy

In the sequence the , are repeated according to geometric multiplicity.

A standard finite element scheme for (Equation 3.1) is: Find a pair where , is a number and satisfying ,

and use and as approximations to and (as respectively. One sees that ( ),Equation 3.2) has a finite sequence of eigenvalues

and corresponding eigenvectors

which can be assumed to satisfy

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

Set

and

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 be a bounded domain and consisting of shape-regular simplices, be a mesh of , of size .

### 5.1. Second order elliptic operators

Let be the standard inner product of and let ,

satisfying and is uniformly positive definite on .

Set and Define . to be a space of continuous functions on and vanishing at the boundary such that for , restricted to each is a polynomial of total degree namely ,

where is the space of polynomials of degree not greater than a positive integer .

We assume that