# Enhanced Error Estimates for Augmented Subspace Method with Crouzeix-Raviart
Element

Zhijin Guan111LSEC, ICMSEC, Academy of Mathematics and Systems Science,
Chinese Academy of Sciences, Beijing 100190, China, and School of Mathematical
Sciences, University of Chinese Academy of Sciences, Beijing 100049, China.
(guanzhijin@lsec.cc.ac.cn), Yifan Wang222LSEC, ICMSEC, Academy of Mathematics
and Systems Science, Chinese Academy of Sciences, Beijing 100190, China, and
School of Mathematical Sciences, University of Chinese Academy of Sciences,
Beijing 100049, China. (wangyifan@lsec.cc.ac.cn), Hehu Xie333LSEC, ICMSEC,
Academy of Mathematics and Systems Science, Chinese Academy of Sciences,
Beijing 100190, China, and School of Mathematical Sciences, University of
Chinese Academy of Sciences, Beijing 100049, China<EMAIL_ADDRESS>and
Chenguang Zhou444Department of Mathematics, Beijing University of Technology,
Beijing 100124, China. (Corresponding author<EMAIL_ADDRESS>
###### Abstract

In this paper, we present some enhanced error estimates for augmented subspace
methods with the nonconforming Crouzeix-Raviart (CR) element. Before the novel
estimates, we derive the explicit error estimates for the case of single
eigenpair and multiple eigenpairs based on our defined spectral projection
operators, respectively. Then we first strictly prove that the CR element
based augmented subspace method exhibits the second-order convergence rate
between the two steps of the augmented subspace iteration, which coincides
with the practical experimental results. The algebraic error estimates of
second order for the augmented subspace method explicitly elucidate the
dependence of the convergence rate of the algebraic error on the coarse space,
which provides new insights into the performance of the augmented subspace
method. Numerical experiments are finally supplied to verify these new
estimate results and the efficiency of our algorithms.

Keywords. eigenvalue problem, augmented subspace method, enhanced error
estimate, Crouzeix-Raviart element.

AMS subject classifications. 65N30, 65N25, 65L15, 65B99.

##  1 Introduction

Solving large-scale eigenvalue problems is a basic and challenging task in the
field of scientific and engineering computing. Compared with linear boundary
value problems, it is always more difficult to solve eigenvalue problems
because it requires more computational work and memory. In order to solve
these large-scale sparse eigenvalue problems, Krylov subspace type methods
(Implicitly Restarted Lanczos/Arnoldi Method (IRLM/IRAM) [25]), Preconditioned
INVerse ITeration (PINVIT) method [7, 15, 18], Locally Optimal Block
Preconditioned Conjugate Gradient (LOBPCG) method [19, 20], Jacobi-Davidson-
type techniques [3] and Generalized Conjugate Gradient Eigensolver (GCGE) [21,
32] have been developed. All these popular methods include the
orthogonalization steps during computing Rayleigh-Ritz problems which are
always the bottlenecks for designing efficient parallel schemes for
determining relatively many eigenpairs.

As one of the effective methods to solve eigenvalue problems, the two-grid
method has been proposed and analyzed in [31] for the linear eigenvalue
problem. This algorithm requires solving a small-scale eigenvalue problem on a
coarse mesh and a large-scale linear boundary value problem on a fine mesh.
When the mesh sizes of the coarse mesh ($H$) and the fine mesh ($h$) have an
appropriate proportional relation ($H=\sqrt{h}$), the optimal error estimate
for the approximate solution can be derived. However, owing to the strict
constraints on the ratio (i.e., $H=\sqrt{h}$), the two-grid method only
performs on two mesh levels and can not be used to design the eigensolver for
the algebraic eigenvalue problems which come from the finite element
discretization of the eigenvalue problems of the differential operators.

Recently, a type of augmented subspace methods and their multilevel correction
methods is proposed for solving eigenvalue problems in [10, 17, 23, 27, 26,
29, 30]. In this type of methods, there exists an augmented subspace which is
used in each correction step and constructed with the low dimensional finite
element space defined on the coarse grid. The idea of augmented subspace gives
birth to the type of augmented subspace methods which only needs the low
dimension finite element space on the coarse mesh and the final finite element
space on the finest mesh. The augmented subspace methods can transform the
solution of the eigenvalue problem on the final level of mesh to the solution
of linear boundary value problems on the final level of mesh and the solution
of the eigenvalue problem on the low dimensional augmented subspace. This type
of methods can also work even the coarse and finest meshes have no nested
property [14]. Based on the augmented subspace methods, the multilevel
correction methods give the ways to construct the multigrid methods for
eigenvalue problems [10, 17, 27, 26, 29], and also in [30], the authors design
an eigenpair-wise parallel eigensolver for the eigenvalue problems. This type
of parallel method avoids doing orthogonalization and inner-products in the
high dimensional space which accounts for a large portion of the wall time in
the parallel computation. The above references are mainly investigated based
on conforming finite element methods, and in [28, 16], the authors extend this
type of methods to the case of the nonconforming finite element methods for
the Laplace eigenvalue problem and the Steklov eigenvalue problem,
respectively.

In [28], the author first illustrates the error estimate of the solution
operator with respect to the eigenspace in Theorem 2.1. Then the augmented
subspace method and its multilevel correction method is presented based on the
nonconforming finite element method, and the algebraic error estimates are
evaluated by utilizing the finest mesh size in Corollary 5.2, which is called
“superclose” in Remark 5.3. However, these derived algebraic error estimates
only prove the first order convergence rate, while the second order algebraic
error accuracy is obtained in the numerical experiments.

Based on above, in this paper, we provide some new and enhanced error
estimates from the following two aspects:

  * •

In the spatial discretization of CR element, we separately derive the explicit
error estimates for the case of single eigenpair and multiple eigenpairs based
on our defined spectral projection operators. These estimates depict the
relationship between the errors of spectral projections of the eigenvalue
problem and the errors of finite element projection of the corresponding
linear boundary value problem with an explicit constant expression related to
the eigenvalues and their gap.

  * •

For the first time, we strictly prove that the augmented subspace method based
on the nonconforming CR element exhibits the second-order convergence rate
between the two augmented subspace iteration steps, which coincides with the
practical experimental results.

Our proposed algebraic error estimates are superior to the results in [28].
More importantly, these algebraic error estimates of second order for the
augmented subspace method explicitly elucidate the dependence of the
convergence rate on the coarse space, which provides new insights into the
performance of the augmented subspace method.

The overall structure of this paper goes as follows. In Section 2, we
introduce the nonconforming CR element method for the eigenvalue problem and
derive new error estimates based on our defined spectral projection operators.
The augmented subspace method and the algebraic error estimates of second
order will be given in Section 3. In Section 4, numerical experiments are
presented to validate the theoretical error estimates and the efficiency of
our algorithms. Some concluding remarks are provided in the last section.

##  2 CR element discretization for the eigenvalue problem

In our methodology description, we set the Laplace eigenvalue problem as an
example. The framework of the theoretical analysis of the method can also be
developed to other eigenvalue problems, for example, linear elasticity
eigenvalue problems. Additionally, it should be noted that the letter $C$
(with or without subscripts) denotes a generic positive constant which may be
different at its different occurrences throughout this paper.

Now, let us concern with the following Laplace eigenvalue problem: Find
$(\lambda,u)\in\mathbb{R}\times H_{0}^{1}(\Omega)$, such that

$\displaystyle\left\\{\begin{array}[]{rcl}-\Delta u&=&\lambda u,\ \ \ {\rm
in}\ \Omega,\\\ u&=&0,\ \ \ \ {\rm on}\ \partial\Omega,\\\
|u|_{1}^{2}&=&1,\end{array}\right.$ (2.4)

where $|\cdot|_{1}$ represents $H^{1}$-type semi-norm (cf. [1]) and
$\Omega\subset\mathbb{R}^{2}$ is a bounded and convex domain with Lipschitz
boundary $\partial\Omega$. Let $V=H_{0}^{1}(\Omega)$ and $W=L^{2}(\Omega)$.
Then the variational formulation of (2.4) is provided as: Find
$(\lambda,u)\in\mathbb{R}\times V$ such that $a(u,u)=1$ and

$\displaystyle a(u,v)=\lambda b(u,v),\quad\forall v\in V,$ (2.5)

where $a(\cdot,\cdot)$ and $b(\cdot,\cdot)$ are defined as follows

$\displaystyle a(u,v)=\int_{\Omega}\nabla u\cdot\nabla vd\Omega,$
$\displaystyle b(u,v)=\int_{\Omega}uvd\Omega.$

Based on the bilinear forms $a(\cdot,\cdot)$ and $b(\cdot,\cdot)$, we can
respectively define the norms on the spaces $V$ and $W$ as

$\displaystyle\left\|v\right\|_{a}=\sqrt{a(v,v)},\ \ \ \ \forall v\in V,$
(2.6)

and

$\displaystyle\left\|w\right\|_{b}=\sqrt{b(w,w)},\ \ \ \ \forall w\in W.$
(2.7)

We can find that the norms $\|\cdot\|_{a}$ and $\|\cdot\|_{b}$ defined in
(2.6) and (2.7) are equivalent to the $H^{1}$-type semi-norm $|\cdot|_{1}$ and
$L^{2}$ norm $\|\cdot\|_{0}$, respectively. It is well known that the
eigenvalue problem (2.5) has an eigenvalue sequence $\\{\lambda_{j}\\}$ (cf.
[2, 9])

$0<\lambda_{1}\leq\lambda_{2}\leq\cdots\leq\lambda_{k}\leq\cdots,\ \ \
\lim_{k\rightarrow\infty}\lambda_{k}=\infty.$

And the associated eigenfunctions are provided as

$u_{1},u_{2},\cdots,u_{k},\cdots.$

Here $a(u_{i},u_{j})=\delta_{ij}$ ($\delta_{ij}$ denotes the Kronecker
function).

Let $\mathcal{T}_{h}$ be a quasi-uniform triangulation of $\Omega$. Denote by
$\mathcal{E}_{h}$ the set of all edges of $\mathcal{T}_{h}$.
$\mathcal{E}_{h}=\mathcal{E}_{h}^{i}\cup\mathcal{E}_{h}^{b}$, where
$\mathcal{E}_{h}^{i}$ denotes the interior edge set and $\mathcal{E}_{h}^{b}$
denotes the edge set lying on the boundary $\partial\Omega$. The CR element
space $V_{h}$ is defined as

$\displaystyle V_{h}:=$ $\displaystyle\Big{\\{}v\in
L^{2}(\Omega):v|_{K}\in{\rm span}\\{1,x,y\\},\int_{\ell}v|_{K_{1}}{\rm
d}s=\int_{\ell}v|_{K_{2}}{\rm d}s,$ $\displaystyle\text{ when }K_{1}\cap
K_{2}=\ell\in\mathcal{E}_{h}^{i}\ \text{and }\int_{\ell}v|_{K}{\rm
d}s=0,\text{ if }\ \ell\in\mathcal{E}_{h}^{b}\Big{\\}},$ (2.8)

where $K,\ K_{1},\ K_{2}\in\mathcal{T}_{h}$.

The CR element approximation to (2.5) is defined as follows: Find
$(\bar{\lambda}_{h},\bar{u}_{h})\in\mathbb{R}\times V_{h}$ such that
$a_{h}(\bar{u}_{h},\bar{u}_{h})=1$ and

$\displaystyle
a_{h}(\bar{u}_{h},v_{h})=\bar{\lambda}_{h}b(\bar{u}_{h},v_{h}),\quad\forall
v_{h}\in V_{h},$ (2.9)

where $a_{h}(\cdot,\cdot)$ is defined as

$\displaystyle
a_{h}(w_{h},v_{h})=\sum\limits_{K\in\mathcal{T}_{h}}\int_{K}\nabla w_{h}\nabla
v_{h}{\rm d}K,\quad\forall w_{h},v_{h}\in V_{h}.$

The bilinear form $a_{h}(\cdot,\cdot)$ is $V_{h}$-elliptic on $V+V_{h}$.
Hence, we define the norms $\|\cdot\|_{a,h}$ and $\|\cdot\|_{b}$ on $V+V_{h}$
as

$\displaystyle\|v\|_{a,h}^{2}=a_{h}(v,v),\ \ \|v\|_{b}^{2}=b(v,v),\ \ \
\text{for}\ v\in V+V_{h}.$ (2.10)

For the eigenvalue problem (2.9), the Rayleigh quotient holds for the
eigenvalue $\bar{\lambda}_{h}$,

$\displaystyle\bar{\lambda}_{h}=\frac{a_{h}(\bar{u}_{h},\bar{u}_{h})}{b(\bar{u}_{h},\bar{u}_{h})}.$

Similarly, the discrete eigenvalue problem (2.9) also has an eigenvalue
sequence

$0<\bar{\lambda}_{1,h}\leq\bar{\lambda}_{2,h}\leq\cdots\leq\bar{\lambda}_{N_{h},h},$

and the corresponding discrete eigenfunction sequence

$\bar{u}_{1,h},\bar{u}_{2,h},\cdots,\bar{u}_{N_{h},h},$

with the property $a_{h}(\bar{u}_{i,h},\bar{u}_{j,h})=\delta_{ij},1\leq
i,j\leq N_{h}$, where $N_{h}$ is the dimension of $V_{h}$.

In order to state the error estimate for the eigenpair approximation by the CR
finite element method, we define the CR finite element projection
$\mathcal{P}_{h}:V\mapsto V_{h}$ as follows

$\displaystyle a_{h}(\mathcal{P}_{h}u,v_{h})=\lambda b(u,v_{h}),\ \ \ \
\forall v_{h}\in V_{h}.$ (2.11)

It is obvious that the finite element projection operator $\mathcal{P}_{h}$
has the following error estimates.

######  Lemma 2.1 ([8, 22]).

Assume the source equation corresponding to the eigenvalue problem has
$H^{2}(\Omega)$ regularity. Then the following error estimates hold

$\displaystyle\left\|u-\mathcal{P}_{h}u\right\|_{a,h}$ $\displaystyle\leq$
$\displaystyle C_{1}h\|u\|_{2},$ (2.12)
$\displaystyle\left\|u-\mathcal{P}_{h}u\right\|_{b}$ $\displaystyle\leq$
$\displaystyle C_{2}h^{2}\|u\|_{2}.$ (2.13)

Before stating error estimates of the CR finite element method for the
eigenvalue problem, we introduce the following lemma.

######  Lemma 2.2.

For any eigenpair $(\lambda,u)$ of (2.5), the following equality holds

$\displaystyle(\bar{\lambda}_{j,h}-\lambda)b(\mathcal{P}_{h}u,\bar{u}_{j,h})=\lambda
b(u-\mathcal{P}_{h}u,\bar{u}_{j,h}),\ \ \ j=1,\cdots,N_{h}.$

###### Proof.

Since $-\lambda b(\mathcal{P}_{h}u,\bar{u}_{j,h})$ appears on both sides, we
only need to prove that

$\displaystyle\bar{\lambda}_{j,h}b(\mathcal{P}_{h}u,\bar{u}_{j,h})=\lambda
b(u,\bar{u}_{j,h}).$

From (2.5), (2.9) and (2.11), the following equalities hold

$\displaystyle\bar{\lambda}_{j,h}b(\mathcal{P}_{h}u,\bar{u}_{j,h})=a_{h}(\mathcal{P}_{h}u,\bar{u}_{j,h})=\lambda
b(u,\bar{u}_{j,h}).$

Then the proof is completed. ∎

Now, let us consider the error estimates for the first $k$ eigenpair
approximations associated with
$\bar{\lambda}_{1,h}\leq\cdots\leq\bar{\lambda}_{k,h}$. For the following
analysis in this paper, we define $\mu_{i}=1/\lambda_{i}$ for $i=1,2,\cdots$,
and $\bar{\mu}_{i,h}=1/\bar{\lambda}_{i,h}$ for $i=1,\cdots,N_{h}$.

######  Theorem 2.1.

Let us define the spectral projection $\bar{F}_{k,h}:V_{h}+V\mapsto{\rm
span}\\{\bar{u}_{1,h},\cdots,\bar{u}_{k,h}\\}$ as follows

$\displaystyle a_{h}(\bar{F}_{k,h}w,\bar{u}_{i,h})=a_{h}(w,\bar{u}_{i,h}),\ \
\ i=1,\cdots,k\ \ {\rm for}\ w\in V_{h}+V.$ (2.14)

Then the associated exact eigenfunctions $u_{1},\cdots,u_{k}$ of eigenvalue
problem (2.5) have the following error estimates

$\displaystyle\left\|u_{i}-\bar{F}_{k,h}u_{i}\right\|_{a,h}\leq
2\|u_{i}-\mathcal{P}_{h}u_{i}\|_{a,h}+\frac{\sqrt{\bar{\mu}_{k+1,h}}}{\delta_{k,i,h}}\left\|u_{i}-\mathcal{P}_{h}u_{i}\right\|_{b},\
\ 1\leq i\leq k,$ (2.15)

where $\delta_{k,i,h}$ is defined as follows

$\displaystyle\delta_{k,i,h}=\min_{k<j\leq
N_{h}}\left|\frac{1}{\bar{\lambda}_{j,h}}-\frac{1}{\lambda_{i}}\right|.$
(2.16)

Furthermore, these $k$ exact eigenfunctions have the following error estimate
in $\left\|\cdot\right\|_{b}$-norm

$\displaystyle\left\|u_{i}-\bar{F}_{k,h}u_{i}\right\|_{b}\leq\left(2+\frac{\bar{\mu}_{k+1,h}}{\delta_{k,i,h}}\right)\left\|u_{i}-\mathcal{P}_{h}u_{i}\right\|_{b},\
\ \ 1\leq i\leq k.$ (2.17)

###### Proof.

Since $(I-\bar{F}_{k,h})\mathcal{P}_{h}u_{i}\in V_{h}$ and
$(I-\bar{F}_{k,h})\mathcal{P}_{h}u_{i}\in{\rm
span}\\{\bar{u}_{k+1,h},\cdots,\bar{u}_{N_{h},h}\\}$, the following orthogonal
expansion holds

$\displaystyle(I-\bar{F}_{k,h})\mathcal{P}_{h}u_{i}=\sum_{j=k+1}^{N_{h}}\alpha_{j}\bar{u}_{j,h},$
(2.18)

where $\alpha_{j}=a_{h}(\mathcal{P}_{h}u_{i},\bar{u}_{j,h})$. From Lemma 2.2,
we have

$\displaystyle\alpha_{j}$ $\displaystyle=$ $\displaystyle
a_{h}(\mathcal{P}_{h}u_{i},\bar{u}_{j,h})=\bar{\lambda}_{j,h}b\big{(}\mathcal{P}_{h}u_{i},\bar{u}_{j,h}\big{)}=\frac{\bar{\lambda}_{j,h}\lambda_{i}}{\bar{\lambda}_{j,h}-\lambda_{i}}b\big{(}u_{i}-\mathcal{P}_{h}u_{i},\bar{u}_{j,h}\big{)}$
(2.19) $\displaystyle=$
$\displaystyle\frac{1}{\mu_{i}-\bar{\mu}_{j,h}}b\big{(}u_{i}-\mathcal{P}_{h}u_{i},\bar{u}_{j,h}\big{)}.$

From the orthogonal property of eigenfunctions
$\bar{u}_{1,h},\cdots,\bar{u}_{N_{h},h}$, we acquire

$\displaystyle
1=a_{h}(\bar{u}_{j,h},\bar{u}_{j,h})=\bar{\lambda}_{j,h}b(\bar{u}_{j,h},\bar{u}_{j,h})=\bar{\lambda}_{j,h}\left\|\bar{u}_{j,h}\right\|_{b}^{2},$

which leads to the following property

$\displaystyle\left\|\bar{u}_{j,h}\right\|_{b}^{2}=\frac{1}{\bar{\lambda}_{j,h}}=\bar{\mu}_{j,h}.$
(2.20)

Because of (2.9) and the definitions of eigenfunctions
$\bar{u}_{1,h},\cdots,\bar{u}_{N_{h},h}$, we obtain the following equalities

$\displaystyle a_{h}(\bar{u}_{j,h},\bar{u}_{k,h})=\delta_{jk},\ \ \ \ \
b\left(\frac{\bar{u}_{j,h}}{\left\|\bar{u}_{j,h}\right\|_{b}},\frac{\bar{u}_{k,h}}{\left\|\bar{u}_{k,h}\right\|_{b}}\right)=\delta_{jk},\
\ \ 1\leq j,k\leq N_{h}.$ (2.21)

Then due to (2.18), (2.19), (2.20) and (2.21), we have the following estimates

$\displaystyle\left\|(I-\bar{F}_{k,h})\mathcal{P}_{h}u_{i}\right\|_{a,h}^{2}=\left\|\sum_{j=k+1}^{N_{h}}\alpha_{j}\bar{u}_{j,h}\right\|_{a,h}^{2}=\sum_{j=k+1}^{N_{h}}\alpha_{j}^{2}$
(2.22)
$\displaystyle=\sum_{j=k+1}^{N_{h}}\left(\frac{1}{\mu_{i}-\bar{\mu}_{j,h}}\right)^{2}b\big{(}u_{i}-\mathcal{P}_{h}u_{i},\bar{u}_{j,h}\big{)}^{2}$
$\displaystyle\leq\frac{1}{\delta_{k,i,h}^{2}}\sum_{j=k+1}^{N_{h}}\left\|\bar{u}_{j,h}\right\|_{b}^{2}b\left(u_{i}-\mathcal{P}_{h}u_{i},\frac{\bar{u}_{j,h}}{\left\|\bar{u}_{j,h}\right\|_{b}}\right)^{2}$
$\displaystyle=\frac{1}{\delta_{k,i,h}^{2}}\sum_{j=k+1}^{N_{h}}\bar{\mu}_{j,h}b\left(u_{i}-\mathcal{P}_{h}u_{i},\frac{\bar{u}_{j,h}}{\left\|\bar{u}_{j,h}\right\|_{b}}\right)^{2}$
$\displaystyle\leq\frac{\bar{\mu}_{k+1,h}}{\delta_{k,i,h}^{2}}\sum_{j=k+1}^{N_{h}}b\left(u_{i}-\mathcal{P}_{h}u_{i},\frac{\bar{u}_{j,h}}{\left\|\bar{u}_{j,h}\right\|_{b}}\right)^{2}$
$\displaystyle\leq\frac{\bar{\mu}_{k+1,h}}{\delta_{k,i,h}^{2}}\left\|u_{i}-\mathcal{P}_{h}u_{i}\right\|_{b}^{2},$

where the last inequality holds since
$\frac{\bar{u}_{1,h}}{\left\|\bar{u}_{1,h}\right\|_{b}}$, $\cdots$,
$\frac{\bar{u}_{j,h}}{\left\|\bar{u}_{j,h}\right\|_{b}}$ are the normal
orthogonal basis for the space $V_{h}$ in the sense of the inner product
$b(\cdot,\cdot)$.

From (2.22), the following inequality holds

$\displaystyle\left\|(I-\bar{F}_{k,h})\mathcal{P}_{h}u_{i}\right\|_{a,h}\leq\frac{\sqrt{\bar{\mu}_{k+1,h}}}{\delta_{k,i,h}}\left\|u_{i}-\mathcal{P}_{h}u_{i}\right\|_{b}.$
(2.23)

Since $\bar{F}_{k,h}$ is the spectral projection operator with respect to
$a_{h}(\cdot,\cdot)$, we write

$\|\bar{F}_{k,h}\|_{a,h}\leq 1$ (2.24)

From (2.23), (2.24) and the triangle inequality, it follows that

$\displaystyle\left\|u_{i}-\bar{F}_{k,h}u_{i}\right\|_{a,h}\leq\left\|u_{i}-\mathcal{P}_{h}u_{i}\right\|_{a,h}+\left\|(I-\bar{F}_{k,h})\mathcal{P}_{h}u_{i}\right\|_{a,h}+\left\|\bar{F}_{k,h}(\mathcal{P}_{h}-I)u_{i}\right\|_{a,h}$
$\displaystyle\leq\left\|u_{i}-\mathcal{P}_{h}u_{i}\right\|_{a,h}+\left\|(I-\bar{F}_{k,h})\mathcal{P}_{h}u_{i}\right\|_{a,h}+\left\|\bar{F}_{k,h}\right\|_{a,h}\left\|(\mathcal{P}_{h}-I)u_{i}\right\|_{a,h}$
$\displaystyle\leq
2\|u_{i}-\mathcal{P}_{h}u_{i}\|_{a,h}+\frac{\sqrt{\bar{\mu}_{k+1,h}}}{\delta_{k,i,h}}\left\|u_{i}-\mathcal{P}_{h}u_{i}\right\|_{b}.$

This is the desired result (2.15).

Similarly, with the help of (2.18), (2.19), (2.20) and (2.21), we have the
following estimates

$\displaystyle\left\|(I-\bar{F}_{k,h})\mathcal{P}_{h}u_{i}\right\|_{b}^{2}=\left\|\sum_{j=k+1}^{N_{h}}\alpha_{j}\bar{u}_{j,h}\right\|_{b}^{2}=\sum_{j=k+1}^{N_{h}}\alpha_{j}^{2}\left\|\bar{u}_{j,h}\right\|_{b}^{2}$
$\displaystyle=\sum_{j=k+1}^{N_{h}}\left(\frac{1}{\mu_{i}-\bar{\mu}_{j,h}}\right)^{2}b\big{(}u_{i}-\mathcal{P}_{h}u_{i},\bar{u}_{j,h}\big{)}^{2}\left\|\bar{u}_{j,h}\right\|_{b}^{2}$
$\displaystyle\leq\frac{1}{\delta_{k,i,h}^{2}}\sum_{j=k+1}^{N_{h}}\left\|\bar{u}_{j,h}\right\|_{b}^{4}\
b\left(u_{i}-\mathcal{P}_{h}u_{i},\frac{\bar{u}_{j,h}}{\left\|\bar{u}_{j,h}\right\|_{b}}\right)^{2}$
$\displaystyle=\frac{1}{\delta_{k,i,h}^{2}}\sum_{j=k+1}^{N_{h}}\bar{\mu}_{j,h}^{2}b\left(u_{i}-\mathcal{P}_{h}u_{i},\frac{\bar{u}_{j,h}}{\left\|\bar{u}_{j,h}\right\|_{b}}\right)^{2}\leq\frac{\bar{\mu}_{k+1,h}^{2}}{\delta_{k,i,h}^{2}}\left\|u_{i}-\mathcal{P}_{h}u_{i}\right\|_{b}^{2},$

which leads to the inequality

$\displaystyle\left\|(I-\bar{F}_{k,h})\mathcal{P}_{h}u_{i}\right\|_{b}\leq\frac{\bar{\mu}_{k+1,h}}{\delta_{k,i,h}}\left\|u_{i}-\mathcal{P}_{h}u_{i}\right\|_{b}.$
(2.25)

According to the definitions (2.10) of the norms $\|\cdot\|_{a,h}$ and
$\|\cdot\|_{b}$ and the reference [12], we know that the norm
$\|\cdot\|_{a,h}$ is relatively compact with respect to the norm
$\|\cdot\|_{b}$. Combined with (2.24), we get $\|\bar{F}_{k,h}\|_{b}\leq 1$.
And from (2.25) and the triangle inequality, we find the following error
estimates for the eigenfunction approximations in the
$\left\|\cdot\right\|_{b}$-norm

$\displaystyle\left\|u_{i}-\bar{F}_{k,h}u_{i}\right\|_{b}\leq\left\|u_{i}-\mathcal{P}_{h}u_{i}\right\|_{b}+\left\|(I-\bar{F}_{k,h})\mathcal{P}_{h}u_{i}\right\|_{b}+\left\|\bar{F}_{k,h}(\mathcal{P}_{h}u_{i}-u_{i})\right\|_{b}$
$\displaystyle\leq\left(1+\|\bar{F}_{k,h}\|_{b}\right)\left\|\mathcal{P}_{h}u_{i}-u_{i}\right\|_{b}+\left\|(I-\bar{F}_{k,h})\mathcal{P}_{h}u_{i}\right\|_{b}$
$\displaystyle\leq\left(2+\frac{\bar{\mu}_{k+1,h}}{\delta_{k,i,h}}\right)\left\|u_{i}-\mathcal{P}_{h}u_{i}\right\|_{b}.$

This is the second desired result (2.17) and the proof is completed. ∎

In order to make sense of the estimates (2.15) and (2.17), and for simplicity
of notation, we assume that the eigenvalue gap $\delta_{k,i,h}$ has a uniform
lower bound which is denoted by $\delta_{k,i}$ (which can be seen as the
“true” separation of the eigenvalues $\lambda_{1},\cdots,\lambda_{k}$ from the
unwanted eigenvalues) in the following parts of this paper. This assumption is
reasonable when the mesh size is small enough. Then we have the following
convergence order based on Theorem 2.1 and the convergence results of CR
finite element method for boundary value problems.

######  Corollary 2.1.

Under the conditions of Lemma 2.1, Theorem 2.1 and $\delta_{k,i,h}$ having a
uniform lower bound $\delta_{k,i}$, the following error estimates hold

$\displaystyle\left\|u_{i}-F_{k,h}u_{i}\right\|_{a,h}$ $\displaystyle\leq$
$\displaystyle C_{3}h\|u\|_{2},\ \ \ \ 1\leq i\leq k,$ (2.26)
$\displaystyle\left\|u_{i}-F_{k,h}u_{i}\right\|_{b}$ $\displaystyle\leq$
$\displaystyle C_{4}h^{2}\|u\|_{2},\ \ \ 1\leq i\leq k.$ (2.27)

The following theorem gives the error estimates for the one eigenpair
approximation and the proof is similar to that of Theorem 2.1.

######  Theorem 2.2.

Let $(\lambda,u)$ denote an exact eigenpair of the eigenvalue problem (2.5).
Assume the eigenpair approximation $(\bar{\lambda}_{i,h},\bar{u}_{i,h})$ has
the property that $\bar{\mu}_{i,h}=1/\bar{\lambda}_{i,h}$ is the closest to
$\mu=1/\lambda$. The corresponding spectral projector
$E_{i,h}:V_{h}+V\mapsto{\rm span}\\{\bar{u}_{i,h}\\}$ is defined as follows

$\displaystyle a_{h}(E_{i,h}w,\bar{u}_{i,h})=a_{h}(w,\bar{u}_{i,h}),\ \ \ \
{\rm for}\ w\in V_{h}+V.$

Then the following error estimate holds

$\displaystyle\left\|u-E_{i,h}u\right\|_{a,h}$ $\displaystyle\leq$
$\displaystyle
2\|u-\mathcal{P}_{h}u\|_{a,h}+\frac{\sqrt{\bar{\mu}_{1,h}}}{\delta_{\lambda,h}}\left\|u-\mathcal{P}_{h}u\right\|_{b},$
(2.28)

where $\delta_{\lambda,h}$ is defined as follows

$\displaystyle\delta_{\lambda,h}$ $\displaystyle:=$ $\displaystyle\min_{j\neq
i}|\bar{\mu}_{j,h}-\mu|=\min_{j\neq
i}\left|\frac{1}{\bar{\lambda}_{j,h}}-\frac{1}{\lambda}\right|.$ (2.29)

Furthermore, the eigenfunction approximation $\bar{u}_{i,h}$ has the following
error estimate in $\left\|\cdot\right\|_{b}$-norm

$\displaystyle\|u-E_{i,h}u\|_{b}$ $\displaystyle\leq$
$\displaystyle\left(2+\frac{\bar{\mu}_{1,h}}{\delta_{\lambda,h}}\right)\left\|u-\mathcal{P}_{h}u\right\|_{b}.$
(2.30)

###### Proof.

Since $(I-E_{i,h})\mathcal{P}_{h}u\in V_{h}$ and
$(I-E_{i,h})\mathcal{P}_{h}u\in{\rm
span}\\{\bar{u}_{1,h},\cdots,\bar{u}_{i-1,h},\bar{u}_{i+1,h},\cdots,\bar{u}_{N_{h},h}\\}$,
the following orthogonal expansion holds

$\displaystyle(I-E_{i,h})\mathcal{P}_{h}u=\sum_{j\neq
i}\alpha_{j}\bar{u}_{j,h},$ (2.31)

where $\alpha_{j}=a_{h}(\mathcal{P}_{h}u,\bar{u}_{j,h})$ has the same equality
(2.19).

Then due to (2.19), (2.20), (2.21) and (2.31), we have the following estimates

$\displaystyle\left\|(I-E_{i,h})\mathcal{P}_{h}u\right\|_{a,h}^{2}=\left\|\sum_{j\neq
i}\alpha_{j}\bar{u}_{j,h}\right\|_{a,h}^{2}=\sum_{j\neq i}\alpha_{j}^{2}$
$\displaystyle=\sum_{j\neq
i}\left(\frac{1}{\mu-\bar{\mu}_{j,h}}\right)^{2}b\big{(}u-\mathcal{P}_{h}u,\bar{u}_{j,h}\big{)}^{2}\leq\frac{1}{\delta_{\lambda,h}^{2}}\sum_{j\neq
i}\left\|\bar{u}_{j,h}\right\|_{b}^{2}b\left(u-\mathcal{P}_{h}u,\frac{\bar{u}_{j,h}}{\left\|\bar{u}_{j,h}\right\|_{b}}\right)^{2}$
$\displaystyle=\frac{1}{\delta_{\lambda,h}^{2}}\sum_{j\neq
i}\bar{\mu}_{j,h}b\left(u-\mathcal{P}_{h}u,\frac{\bar{u}_{j,h}}{\left\|\bar{u}_{j,h}\right\|_{b}}\right)^{2}$
$\displaystyle\leq\frac{\bar{\mu}_{1,h}}{\delta_{\lambda,h}^{2}}\sum_{j\neq
i}b\left(u-\mathcal{P}_{h}u,\frac{\bar{u}_{j,h}}{\left\|\bar{u}_{j,h}\right\|_{b}}\right)^{2}$
(2.32)
$\displaystyle\leq\frac{\bar{\mu}_{1,h}}{\delta_{\lambda,h}^{2}}\left\|u-\mathcal{P}_{h}u\right\|_{b}^{2},$
(2.33)

where the last inequality holds since
$\frac{\bar{u}_{1,h}}{\left\|\bar{u}_{1,h}\right\|_{b}}$, $\cdots$,
$\frac{\bar{u}_{j,h}}{\left\|\bar{u}_{j,h}\right\|_{b}}$ are the normal
orthogonal basis for the space $V_{h}$ in the sense of the inner product
$b(\cdot,\cdot)$.

From (2), the following inequality holds

$\displaystyle\left\|(I-E_{i,h})\mathcal{P}_{h}u\right\|_{a,h}\leq\frac{\sqrt{\bar{\mu}_{1,h}}}{\delta_{\lambda,h}}\left\|u-\mathcal{P}_{h}u\right\|_{b}.$
(2.34)

Since $E_{i,h}$ is the spectral projection operator with respect to
$a_{h}(\cdot,\cdot)$, we get $\|E_{i,h}\|_{a,h}\leq 1$. And from (2.34) and
the triangle inequality, it follows that

$\displaystyle\left\|u-E_{i,h}u\right\|_{a,h}\leq\left\|u-\mathcal{P}_{h}u\right\|_{a,h}+\left\|(I-E_{i,h})\mathcal{P}_{h}u\right\|_{a,h}+\left\|E_{i,h}(\mathcal{P}_{h}-I)u\right\|_{a,h}$
$\displaystyle\leq\left\|u-\mathcal{P}_{h}u\right\|_{a,h}+\left\|(I-E_{i,h})\mathcal{P}_{h}u\right\|_{a,h}+\left\|E_{i,h}\right\|_{a,h}\left\|(\mathcal{P}_{h}-I)u\right\|_{a,h}$
$\displaystyle\leq
2\|u-\mathcal{P}_{h}u\|_{a,h}+\frac{\sqrt{\bar{\mu}_{1,h}}}{\delta_{\lambda,h}}\left\|u-\mathcal{P}_{h}u\right\|_{b}.$

This is the desired result (2.28).

Similarly, with the help of (2.19), (2.20), (2.21) and (2.31), we have the
following estimates

$\displaystyle\left\|(I-E_{i,h})\mathcal{P}_{h}u\right\|_{b}^{2}=\left\|\sum_{j\neq
i}\alpha_{j}\bar{u}_{j,h}\right\|_{b}^{2}=\sum_{j\neq
i}\alpha_{j}^{2}\left\|\bar{u}_{j,h}\right\|_{b}^{2}$
$\displaystyle=\sum_{j\neq
i}\left(\frac{1}{\mu-\bar{\mu}_{j,h}}\right)^{2}b\big{(}u-\mathcal{P}_{h}u,\bar{u}_{j,h}\big{)}^{2}\left\|\bar{u}_{j,h}\right\|_{b}^{2}$
$\displaystyle\leq\frac{1}{\delta_{\lambda,h}^{2}}\sum_{j\neq
i}\left\|\bar{u}_{j,h}\right\|_{b}^{4}\
b\left(u-\mathcal{P}_{h}u,\frac{\bar{u}_{j,h}}{\left\|\bar{u}_{j,h}\right\|_{b}}\right)^{2}$
$\displaystyle\leq\frac{\bar{\mu}_{1,h}^{2}}{\delta_{\lambda,h}^{2}}\left\|u-\mathcal{P}_{h}u\right\|_{b}^{2},$

which leads to the inequality

$\displaystyle\left\|(I-E_{i,h})\mathcal{P}_{h}u\right\|_{b}\leq\frac{\bar{\mu}_{k+1,h}}{\delta_{k,i,h}}\left\|u-\mathcal{P}_{h}u\right\|_{b}.$
(2.35)

Due to the definitions (2.10) of the norms $\|\cdot\|_{a,h}$ and
$\|\cdot\|_{b}$, we illustrate that the norm $\|\cdot\|_{a,h}$ is relatively
compact with respect to the norm $\|\cdot\|_{b}$. And together with
$\|E_{i,h}\|_{a,h}\leq 1$, we obtain $\|E_{i,h}\|_{b}\leq 1$. From (2.35),
$\|E_{i,h}\|_{b}\leq 1$ and the triangle inequality, we find the following
error estimates for the eigenfunction approximations in the
$\left\|\cdot\right\|_{b}$-norm

$\displaystyle\left\|u-E_{i,h}u\right\|_{b}\leq\left\|u-\mathcal{P}_{h}u\right\|_{b}+\left\|(I-E_{i,h})\mathcal{P}_{h}u\right\|_{b}+\left\|E_{i,h}(\mathcal{P}_{h}u-u)\right\|_{b}$
$\displaystyle\leq\left(1+\|E_{i,h}\|_{b}\right)\left\|\mathcal{P}_{h}u-u\right\|_{b}+\left\|(I-E_{i,h})\mathcal{P}_{h}u\right\|_{b}\leq\left(2+\frac{\bar{\mu}_{1,h}}{\delta_{\lambda,h}}\right)\left\|u-\mathcal{P}_{h}u\right\|_{b}.$

This is the second desired result (2.30) and the proof is completed. ∎

Similarly, in order to make sense of the estimates (2.28) and (2.30), and for
simplicity of notation, we assume that the eigenvalue gap $\delta_{\lambda,h}$
defined by (2.29) has also a uniform lower bound which is denoted by
$\delta_{\lambda}$ (which can be seen as the “true” separation of the
eigenvalue $\lambda$ from others) in the following parts of this paper. This
assumption is also reasonable when the mesh size is small enough. Then we also
have the following convergence result based on Theorem 2.2 and the convergence
results of CR finite element method for boundary value problems.

######  Corollary 2.2.

Under the conditions of Lemma 2.1, Theorem 2.2 and $\delta_{\lambda,h}$ having
a uniform lower bound $\delta_{\lambda}$, the following error estimates hold

$\displaystyle\left\|u-E_{i,h}u\right\|_{a,h}$ $\displaystyle\leq$
$\displaystyle C_{5}h\|u\|_{2},$ (2.36)
$\displaystyle\left\|u-E_{i,h}u\right\|_{b}$ $\displaystyle\leq$
$\displaystyle C_{6}h^{2}\|u\|_{2}.$ (2.37)

##  3 Augmented subspace method and its error estimates

In this section, we first present the augmented subspace method for solving
the eigenvalue problem (2.5) based on CR element. This method contains solving
the auxiliary linear boundary value problem in the fine finite element space
$V_{h}$ and the eigenvalue problem on the augmented subspace $V_{H,h}$ which
is built by the coarse finite element space $V_{H}$ and a finite element
function in the fine finite element space $V_{h}$. In order to eliminate the
compatibility error of the CR element space $V_{H}$, we use the conforming
linear finite element space $W_{H}$ to construct the augmented subspace
$V_{H,h}$. Then, the new convergence analysis is given for this augmented
subspace method.

In order to design the augmented subspace method, we first generate a coarse
mesh $\mathcal{T}_{H}$ with the mesh size $H$ and the coarse linear finite
element space $W_{H}$ is defined on the mesh $\mathcal{T}_{H}$. For the
positive integer $\ell$ and some given eigenfunction approximations
$u_{1,h}^{(\ell)},\cdots,u_{k,h}^{(\ell)}$ which are the approximations for
the first $k$ eigenfunctions $\bar{u}_{1,h},\cdots,\bar{u}_{k,h}$ of (2.5), we
can do the following augmented subspace iteration step which is defined by
Algorithm 1 to improve the accuracy of
$u_{1,h}^{(\ell)},\cdots,u_{k,h}^{(\ell)}$, where the superscript with
parentheses denotes the number of iteration steps of the augmented subspace
method.

  1. 1.

For $\ell=1$, we define $\widehat{u}_{i,h}^{(\ell)}=u_{i,h}^{(\ell)}$,
$i=1,\cdots,k$, and the augmented subspace $V_{H,h}^{(\ell)}=W_{H}+{\rm
span}\\{\widehat{u}_{1,h}^{(\ell)},\cdots,\widehat{u}_{k,h}^{(\ell)}\\}$. Then
solve the following eigenvalue problem: Find
$(\lambda_{i,h}^{(\ell)},u_{i,h}^{(\ell)})\in\mathbb{R}\times
V_{H,h}^{(\ell)}$ such that $a_{h}(u_{i,h}^{(\ell)},u_{i,h}^{(\ell)})=1$ and

$a_{h}(u_{i,h}^{(\ell)},v_{H,h})=\lambda_{i,h}^{(\ell)}b(u_{i,h}^{(\ell)},v_{H,h}),\
\ \ \ \ \forall v_{H,h}\in V_{H,h}^{(\ell)},\ \ \ i=1,\cdots,k.$ (3.1)

  2. 2.

Solve the following linear boundary value problems: Find
$\widehat{u}_{i,h}^{(\ell+1)}\in V_{h}$ such that

$a_{h}(\widehat{u}_{i,h}^{(\ell+1)},v_{h})=\lambda_{i,h}^{(\ell)}b(u_{i,h}^{(\ell)},v_{h}),\
\ \forall v_{h}\in V_{h},\ \ \ i=1,\cdots,k.$ (3.2)

  3. 3.

Define the augmented subspace $V_{H,h}^{(\ell+1)}=W_{H}+{\rm
span}\\{\widehat{u}_{1,h}^{(\ell+1)},\cdots,\widehat{u}_{k,h}^{(\ell+1)}\\}$
and solve the following eigenvalue problem: Find
$(\lambda_{i,h}^{(\ell+1)},u_{i,h}^{(\ell+1)})\in\mathbb{R}\times
V_{H,h}^{(\ell+1)}$ such that $a_{h}(u_{i,h}^{(\ell+1)},u_{i,h}^{(\ell+1)})=1$
and

$a_{h}(u_{i,h}^{(\ell+1)},v_{H,h})=\lambda_{i,h}^{(\ell+1)}b(u_{i,h}^{(\ell+1)},v_{H,h}),\
\ \ \ \ \forall v_{H,h}\in V_{H,h}^{(\ell+1)},\ \ \ i=1,\cdots,k.$ (3.3)

Solve (3.3) to obtain
$(\lambda_{1,h}^{(\ell+1)},u_{1,h}^{(\ell+1)}),\cdots,(\lambda_{k,h}^{(\ell+1)},u_{k,h}^{(\ell+1)})$.

  4. 4.

Set $\ell=\ell+1$ and go to Step 2 for the next iteration until convergence.

Algorithm 1 Augmented subspace method for the first $k$ eigenpairs

It should be noted that, although $V_{h}$ is nonconforming, we can still get
the following nested relationship because of conforming linear finite element
space $W_{H}$,

$W_{H}\subset V_{H,h}\subset V_{h}.$ (3.4)

In order to derive the algebraic error estimates of Algorithm 1, we first
concern with the error estimates of the projection operator
$\mathcal{P}_{H,h}:V_{h}\rightarrow V_{H,h}$. The definition of
$\mathcal{P}_{H,h}$ is given as follows.

$a_{h}\left(\mathcal{P}_{H,h}v_{h},v_{H,h}\right)=a_{h}\left(v_{h},v_{H,h}\right),\quad\forall
v_{H,h}\in V_{H,h},\ \ \text{for}\ \ v_{h}\in V_{h}.$ (3.5)

From (3.4), it follows that

$\|v_{h}-\mathcal{P}_{H,h}v_{h}\|_{a,h}=\inf_{v_{H,h}\in
V_{H,h}}\|v_{h}-v_{H,h}\|_{a,h},$ (3.6)

and

$\displaystyle\|\bar{u}_{h}-\mathcal{P}_{H,h}\bar{u}_{h}\|_{b}$
$\displaystyle=\sup_{f\in
L^{2}(\Omega),\|f\|_{b}=1}b\left(\bar{u}_{h}-\mathcal{P}_{H,h}\bar{u}_{h},f\right)$
$\displaystyle=\sup_{f\in
L^{2}(\Omega),\|f\|_{b}=1}a_{h}\left(\bar{u}_{h}-\mathcal{P}_{H,h}\bar{u}_{h},T_{h}f\right)$
$\displaystyle=\sup_{f\in
L^{2}(\Omega),\|f\|_{b}=1}a_{h}\left(\bar{u}_{h}-\mathcal{P}_{H,h}\bar{u}_{h},T_{h}f-v_{H,h}\right),\quad\forall
v_{H,h}\in V_{H,h}.$

Thus,

$\|\bar{u}_{h}-\mathcal{P}_{H,h}\bar{u}_{h}\|_{b}\leq\eta_{a}\left(V_{H,h}\right)\|\bar{u}_{h}-\mathcal{P}_{H,h}\bar{u}_{h}\|_{a,h},$
(3.7)

where

$\eta_{a}\left(V_{H,h}\right)=\sup_{f\in
L^{2}(\Omega),\|f\|_{b}=1}\inf_{v_{H,h}\in V_{H,h}}\|T_{h}f-v_{H,h}\|_{a,h}.$
(3.8)

By virtue of (3.4), we provide

$\eta_{a}\left(V_{H,h}\right)\leq\eta_{a}\left(W_{H}\right).$ (3.9)

######  Theorem 3.1.

Let us define the spectral projection $F_{k,h}^{(m)}:V_{h}\mapsto{\rm
span}\\{u_{1,h}^{(m)},\cdots,u_{k,h}^{(m)}\\}$ for any integer $m\geq 1$ as
follows

$\displaystyle
a_{h}(F_{k,h}^{(m)}w_{h},u_{i,h}^{(m)})=a_{h}(w_{h},u_{i,h}^{(m)}),\ \ \
i=1,\cdots,k\ \ {\rm for}\ w_{h}\in V_{h}.$ (3.10)

Then the exact eigenfunctions $\bar{u}_{1,h},\cdots,\bar{u}_{k,h}$ of (2.9)
and the eigenfunction approximations $u_{1,h}^{(\ell+1)}$, $\cdots$,
$u_{k,h}^{(\ell+1)}$ from Algorithm 1 with the integer $\ell\geq 1$ have the
following error estimate

$\left\|\bar{u}_{i,h}-F_{k,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}\leq\bar{\lambda}_{i,h}\sqrt{1+\frac{\eta_{a}^{2}(W_{H})}{\lambda_{k+1}\big{(}\delta_{k,i}^{(\ell+1)}\big{)}^{2}}}\left(1+\frac{1}{\lambda_{k+1}\delta_{k,i}^{(\ell)}}\right)\eta_{a}^{2}(W_{H})\left\|\bar{u}_{i,h}-F_{k,h}^{(\ell)}\bar{u}_{i,h}\right\|_{a,h},$
(3.11)

where $\eta_{a}\left(W_{H}\right)$ is defined by (3.8). Furthermore, the
following $\left\|\cdot\right\|_{b}$-norm error estimate holds

$\displaystyle\left\|\bar{u}_{i,h}-F_{k,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{b}\leq\left(1+\frac{1}{\lambda_{k+1}\delta_{k,i}^{(\ell+1)}}\right)\eta_{a}(W_{H})\left\|\bar{u}_{i,h}-F_{k,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}.$
(3.12)

Here denote by $\delta_{k,i}^{(\ell+1)}$ the uniform lower bound of the
eigenvalue gap $\delta_{k,i,h}^{(\ell+1)}$, which is defined as

$\delta_{k,i,h}^{(\ell+1)}:=\min_{k<j\leq
N_{h}}\left|\dfrac{1}{\lambda_{j,h}^{(\ell+1)}}-\dfrac{1}{\lambda_{i}}\right|.$
(3.13)

###### Proof.

First, let us consider the error estimate
$\left\|\bar{u}_{i,h}-F_{k,h}^{(\ell)}\bar{u}_{i,h}\right\|_{b}$. Due to
Algorithm 1, we know that the approximations
$u_{1,h}^{(\ell)},\cdots,u_{k,h}^{(\ell)}$ come from (3.1) (the case that
$\ell=1$) or (3.3) (the case that $\ell>1$). Similarly with the derivation in
the case of the conforming finite element method (refer to Theorem 3.1 in
[13]), for both cases, there exist exact eigenfunctions
$\bar{u}_{1,h},\cdots,\bar{u}_{k,h}$ such that the following error estimates
for the eigenvector approximations $u_{1,h}^{(\ell)},\cdots,u_{k,h}^{(\ell)}$
hold for $i=1,\cdots,k$

$\displaystyle\left\|\bar{u}_{i,h}-F_{k,h}^{(\ell)}\bar{u}_{i,h}\right\|_{b}$
$\displaystyle\leq\left(1+\frac{\mu_{k+1}}{\delta_{k,i}^{(\ell)}}\right)\eta_{a}(V_{H,h}^{(\ell)})\left\|\bar{u}_{i,h}-F_{k,h}^{(\ell)}\bar{u}_{i,h}\right\|_{a,h}$
(3.14)
$\displaystyle\leq\left(1+\frac{\mu_{k+1}}{\delta_{k,i}^{(\ell)}}\right)\eta_{a}(W_{H})\left\|\bar{u}_{i,h}-F_{k,h}^{(\ell)}\bar{u}_{i,h}\right\|_{a,h},$

where we have used the inequality
$\eta_{a}(V_{H,h}^{(\ell)})\leq\eta_{a}(W_{H})$ since $W_{H}\subset
V_{H,h}^{(\ell)}$.

From the definition of the spectral projection $F_{k,h}^{(\ell)}$. Then there
exist $k$ real numbers $q_{1},\cdots,q_{k}\in\mathbb{R}$ such that
$F_{k,h}^{(\ell)}\bar{u}_{i,h}$ has the following expansion

$\displaystyle
F_{k,h}^{(\ell)}\bar{u}_{i,h}=\sum_{j=1}^{k}q_{j}u_{j,h}^{(\ell)}.$ (3.15)

From (3.5), we obtain the orthogonal property of the projection operator
$\mathcal{P}_{H,h}^{(\ell+1)}$, that is to say,

$a_{h}(\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h},v_{H,h})=0,\quad\forall
v_{H,h}\in V_{H,h}^{(\ell+1)}.$

Together with the definition of $V_{H,h}^{(\ell+1)}$ in Step 3 of Algorithm 1,
we supply

$\displaystyle\left\|\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}^{2}=a_{h}\left(\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h},\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right)$
$\displaystyle=a_{h}\left(\bar{u}_{i,h},\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right)$
$\displaystyle=a_{h}\left(\bar{u}_{i,h}-\sum_{j=1}^{k}\bar{\lambda}_{i,h}\frac{q_{j}}{\lambda_{j,h}^{(\ell)}}\widehat{u}_{j,h}^{(\ell+1)},\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right).$

Because of (2.9), (3.2) and $V_{H,h}^{(\ell+1)}\subset V_{h}$, we provide

$\displaystyle\left\|\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}^{2}=\bar{\lambda}_{i,h}b\left(\bar{u}_{i,h}-\sum_{j=1}^{k}\frac{q_{j}}{\lambda_{j,h}^{(\ell)}}\lambda_{j,h}^{(\ell)}u_{j,h}^{(\ell)},\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right)$
$\displaystyle=\bar{\lambda}_{i,h}b\left(\bar{u}_{i,h}-\sum_{j=1}^{k}q_{j}u_{j,h}^{(\ell)},\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right),$

combined with (3.15), then

$\displaystyle\left\|\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}^{2}=\bar{\lambda}_{i,h}b\left(\bar{u}_{i,h}-F_{k,h}^{(\ell)}\bar{u}_{i,h},\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right)$
$\displaystyle\leq\bar{\lambda}_{i,h}\left\|\bar{u}_{i,h}-F_{k,h}^{(\ell)}\bar{u}_{i,h}\right\|_{b}\left\|\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{b}.$

And considering (3.14), (3.7) and the inequality
$\eta_{a}(V_{H,h}^{(\ell+1)})\leq\eta_{a}(W_{H})$, we render

$\left\|\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}^{2}\leq\bar{\lambda}_{i,h}\left(1+\frac{1}{\lambda_{k+1}\delta_{k,i}}\right)\eta^{2}_{a}(W_{H})\left\|\bar{u}_{i,h}-F_{k,h}^{(\ell)}\bar{u}_{i,h}\right\|_{a,h}\left\|\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h},$

i.e.,

$\displaystyle\left\|\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}\leq\bar{\lambda}_{i,h}\left(1+\frac{1}{\lambda_{k+1}\delta_{k,i}}\right)\eta^{2}_{a}(W_{H})\left\|\bar{u}_{i,h}-F_{k,h}^{(\ell)}\bar{u}_{i,h}\right\|_{a,h}.$
(3.16)

Since $u_{1,h}^{(\ell+1)},\cdots,u_{k,h}^{(\ell+1)}$ only come from (3.3) and
the orthogonal property
$a_{h}((I-\mathcal{P}_{H,h}^{(\ell+1)})\bar{u}_{i,h},(I-F_{k,h}^{\ell})P_{H,h}^{(\ell+1)}\bar{u}_{i,h})=0$,
we have for $i=1,\cdots,k$

$\displaystyle\left\|\bar{u}_{i,h}-F_{k,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}^{2}$
$\displaystyle=$
$\displaystyle\left\|\bar{u}_{i,h}-\mathcal{P}_{k,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}^{2}+\left\|(I-F_{k,h}^{\ell})P_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}^{2}$
$\displaystyle\leq$
$\displaystyle\left(1+\frac{\eta_{a}^{2}(V_{H,h}^{(\ell+1)})}{\lambda_{k+1}\big{(}\delta_{k,i}^{(\ell+1)}\big{)}^{2}}\right)\left\|(I-\mathcal{P}_{H,h}^{(\ell+1)})\bar{u}_{i,h}\right\|_{a,h}^{2}$
$\displaystyle\leq$
$\displaystyle\left(1+\frac{\eta_{a}^{2}(W_{H})}{\lambda_{k+1}\big{(}\delta_{k,i}^{(\ell+1)}\big{)}^{2}}\right)\left\|(I-\mathcal{P}_{H,h}^{(\ell+1)})\bar{u}_{i,h}\right\|_{a,h}^{2}.$

Thus,

$\displaystyle\left\|\bar{u}_{i,h}-F_{k,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}$
$\displaystyle\leq$
$\displaystyle\sqrt{1+\frac{\eta_{a}^{2}(W_{H})}{\lambda_{k+1}\big{(}\delta_{k,i}^{(\ell+1)}\big{)}^{2}}}\left\|(I-\mathcal{P}_{H,h}^{(\ell+1)})\bar{u}_{i,h}\right\|_{a,h}.$

Together with (3.16), we arrive at

$\left\|\bar{u}_{i,h}-F_{k,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}\leq\bar{\lambda}_{i,h}\sqrt{1+\frac{\eta_{a}^{2}(W_{H})}{\lambda_{k+1}\big{(}\delta_{k,i}^{(\ell+1)}\big{)}^{2}}}\left(1+\frac{1}{\lambda_{k+1}\delta_{k,i}^{(\ell)}}\right)\eta_{a}^{2}(W_{H})\left\|\bar{u}_{i,h}-F_{k,h}^{(\ell)}\bar{u}_{i,h}\right\|_{a,h}.$

We have the following $\left\|\cdot\right\|_{b}$-error estimate

$\left\|\bar{u}_{i,h}-F_{k,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{b}\leq\left(1+\frac{\mu_{k+1}}{\delta_{k,i}^{(\ell+1)}}\right)\eta_{a}(W_{H})\left\|\bar{u}_{i,h}-F_{k,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}.$

The proof is completed. ∎

######  Remark 3.1.

The convergence result (3.11) in Theorem 3.1 means that the augmented subspace
methods have the second order convergence rate. In addition, in order to
accelerate the convergence rate, we should decrease the term $\eta_{a}(W_{H})$
which depends on the coarse space $W_{H}$. That is to say, enlarging the
subspace $W_{H}$ can speed up the convergence.

######  Remark 3.2.

In this paper, we are only concerned with the error estimates for the
eigenvector approximation since the error estimates for the eigenvalue
approximation can be deduced from the following error expansion (refer to
(4.9) in [28]),

$\displaystyle
0\leq\widehat{\lambda}_{i}-\bar{\lambda}_{i,h}=\frac{a_{h}(\bar{u}_{i,h}-\psi,\bar{u}_{i,h}-\psi)}{b(\psi,\psi)}-\bar{\lambda}_{i,h}\frac{b(\bar{u}_{i,h}-\psi,\bar{u}_{i,h}-\psi)}{b(\psi,\psi)}+2\frac{a_{h}(\bar{u}_{i,h},\psi)-b(\bar{\lambda}_{i,h}\bar{u}_{i,h},\psi)}{b(\psi,\psi)},$

where $\psi$ is the eigenvector approximation for the exact eigenvector
$\bar{u}_{i,h}$ and

$\displaystyle\widehat{\lambda}_{i}=\frac{a_{h}(\psi,\psi)}{b(\psi,\psi)}.$

It is obvious that the parallel computing method can be used for Step 2 of
Algorithm 1 since each linear equation can be solved independently. Thereout,
the augmented subspace method can be used to design a type of parallel schemes
for eigenvalue problems. Step 3 of Algorithm 1 is to solve the eigenvalue
problem (3.3). But in order to assemble the matrices for (3.3), we need to do
the inner products of the $k$ vectors in the high dimensional space $V_{h}$,
which is a very low scalable process for the parallel computing [21, 30]. That
is to say, the inner product computation of many high dimensional vectors is
indeed a bottleneck for parallel computing. In order to overcome this
essential bottleneck, we give another version of the augmented subspace method
for only one (may be not the smallest one) eigenpair which represents the
single process version of this type of parallel schemes. The corresponding
numerical method is defined by Algorithm 2. Here we will also give a sharper
error estimate for this type of the method.

In Algorithm 2, we assume that the given eigenpair approximation
$(\lambda_{i,h}^{(\ell)},u_{i,h}^{(\ell)})\in\mathbb{R}\times V_{h}$ with
different superscripts is the closest to an exact eigenpair
$(\bar{\lambda}_{i,h},\bar{u}_{i,h})$ of (2.9). Based on this setting, we can
give the following convergence result for the augmented subspace method
defined by Algorithm 2.

  1. 1.

For $\ell=1$, we define $\widehat{u}_{i,h}^{(\ell)}=u_{i,h}^{(\ell)}$, and the
augmented subspace $V_{H,h}^{(\ell)}=W_{H}+{\rm
span}\\{\widehat{u}_{i,h}^{(\ell)}\\}$. Then solve the following eigenvalue
problem: Find $(\lambda_{i,h}^{(\ell)},u_{i,h}^{(\ell)})\in\mathbb{R}\times
V_{H,h}^{(\ell)}$ such that $a_{h}(u_{i,h}^{(\ell)},u_{i,h}^{(\ell)})=1$ and

$a_{h}(u_{i,h}^{(\ell)},v_{H,h})=\lambda_{i,h}^{(\ell)}b(u_{i,h}^{(\ell)},v_{H,h}),\
\ \ \ \ \forall v_{H,h}\in V_{H,h}^{(\ell)}.$ (3.17)

  2. 2.

Solve the following linear boundary value problem: Find
$\widehat{u}_{i,h}^{(\ell+1)}\in V_{h}$ such that

$a(\widehat{u}_{i,h}^{(\ell+1)},v_{h})=\lambda_{i,h}^{(\ell)}b(u_{i,h}^{(\ell)},v_{h}),\
\ \forall v_{h}\in V_{h}.$ (3.18)

  3. 3.

Define the augmented subspace $V_{H,h}^{(\ell+1)}=W_{H}+{\rm
span}\\{\widehat{u}_{i,h}^{(\ell+1)}\\}$ and solve the following eigenvalue
problem: Find
$(\lambda_{i,h}^{(\ell+1)},u_{i,h}^{(\ell+1)})\in\mathbb{R}\times
V_{H,h}^{(\ell+1)}$ such that $a_{h}(u_{i,h}^{(\ell+1)},u_{i,h}^{(\ell+1)})=1$
and

$a_{h}(u_{i,h}^{(\ell+1)},v_{H,h})=\lambda_{i,h}^{(\ell+1)}b(u_{i,h}^{(\ell+1)},v_{H,h}),\
\ \ \ \ \forall v_{H,h}\in V_{H,h}^{(\ell+1)}.$ (3.19)

Solve (3.19) and the output $(\lambda_{i,h}^{(\ell+1)},u_{i,h}^{(\ell+1)})$ is
chosen such that $u_{i,h}^{(\ell+1)}$ has the largest component in ${\rm
span}\\{\widehat{u}_{i,h}^{(\ell+1)}\\}$ among all eigenfunctions of (3.19).

  4. 4.

Set $\ell=\ell+1$ and go to Step 2 for the next iteration until convergence.

Algorithm 2 Augmented subspace method for one eigenpair

######  Theorem 3.2.

For any integer $m\geq 1$, according to the eigenpair approximation
$(\lambda_{i,h}^{(m)},u_{i,h}^{(m)})\in\mathbb{R}\times V_{h}$, we define the
spectral projector $E_{i,h}^{(m)}:V_{h}\mapsto{\rm span}\\{u_{i,h}^{(m)}\\}$
as follows

$\displaystyle
a_{h}(E_{i,h}^{(m)}w_{h},u_{i,h}^{(m)})=a_{h}(w_{h},u_{i,h}^{(m)}),\ \ \ \
{\rm for}\ w_{h}\in V_{h}.$

Then the eigenpair approximation
$(\lambda_{i,h}^{(\ell+1)},u_{i,h}^{(\ell+1)})\in\mathbb{R}\times V_{h}$
produced by Algorithm 2 satisfies the following error estimates

$\displaystyle\left\|\bar{u}_{i,h}-E_{i,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}$
$\displaystyle\leq\bar{\lambda}_{i,h}\sqrt{1+\frac{\eta_{a}^{2}(W_{H})}{\lambda_{1}\big{(}\delta_{\lambda}^{(\ell+1)}\big{)}^{2}}}\left(1+\frac{1}{\lambda_{1}\delta_{\lambda}^{(\ell)}}\right)\eta_{a}^{2}(W_{H})\left\|\bar{u}_{i,h}-E_{i,h}^{(\ell)}\bar{u}_{i,h}\right\|_{a,h},$
$\displaystyle\left\|\bar{u}_{i,h}-E_{i,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{b}$
$\displaystyle\leq\left(1+\frac{1}{\lambda_{1}\delta_{\lambda}^{(\ell+1)}}\right)\eta_{a}(W_{H})\left\|\bar{u}_{i,h}-E_{i,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}.$

Here denote by $\delta^{(\ell+1)}_{\lambda}$ the uniform lower bound of the
eigenvalue gap $\delta^{(\ell+1)}_{\lambda,h}$, which is defined as

$\displaystyle\delta^{(\ell+1)}_{\lambda,h}$ $\displaystyle:=$
$\displaystyle\min_{j\neq
i}\left|\frac{1}{\lambda^{(\ell+1)}_{j,h}}-\frac{1}{\lambda}\right|.$

###### Proof.

First, let us consider the error estimate
$\left\|\bar{u}_{i,h}-E_{i,h}^{(\ell)}\bar{u}_{i,h}\right\|_{b}$. Because of
Algorithm 2, we understand that $u_{i,h}^{(\ell)}$ may stem from two places,
i.e., (3.17) for $\ell=1$ and (3.19) for $\ell>1$. Both cases present the
following error estimate for the eigenvector approximation $u_{i,h}^{(\ell)}$.
Similarly with the derivation process in the case of the conforming finite
element method (refer to Theorem 3.2 in [13]), we get

$\displaystyle\left\|\bar{u}_{i,h}-E_{i,h}^{(\ell)}\bar{u}_{i,h}\right\|_{b}$
$\displaystyle\leq$
$\displaystyle\left(1+\frac{1}{\lambda_{1}\delta_{\lambda}^{(\ell)}}\right)\eta_{a}(V_{H,h}^{(\ell)})\left\|\bar{u}_{i,h}-E_{i,h}^{(\ell)}\bar{u}_{i,h}\right\|_{a,h}$
(3.20) $\displaystyle\leq$
$\displaystyle\left(1+\frac{1}{\lambda_{1}\delta_{\lambda}^{(\ell)}}\right)\eta_{a}(W_{H})\left\|\bar{u}_{i,h}-E_{i,h}^{(\ell)}\bar{u}_{i,h}\right\|_{a,h},$

where we have used the inequality
$\eta_{a}(V_{H,h}^{(\ell)})\leq\eta_{a}(W_{H})$ since $W_{H}\subset
V_{H,h}^{(\ell)}$.

According to the orthogonal property of the projection operator
$\mathcal{P}_{H,h}^{(\ell+1)}$, i.e.,

$a_{h}(\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h},v_{H,h})=0,\quad\forall
v_{H,h}\in V_{H,h}^{(\ell+1)},$

and the definition of $V_{H,h}^{(\ell+1)}$ in Step 3 of Algorithm 2, we get

$\displaystyle\left\|\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}^{2}=a_{h}\left(\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h},\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right)$
$\displaystyle=a_{h}\left(\bar{u}_{i,h},\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right)$
$\displaystyle=a_{h}\left(\bar{u}_{i,h}-\frac{\bar{\lambda}_{i,h}}{\lambda_{i,h}^{(\ell)}}q\widehat{u}_{i,h}^{(\ell+1)},\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right)$
$\displaystyle=a_{h}\left(\bar{u}_{i,h},\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right)-\frac{\bar{\lambda}_{i,h}}{\lambda_{i,h}^{(\ell)}}qa_{h}\left(\widehat{u}_{i,h}^{(\ell+1)},\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right).$

And by virtue of (2.9), (3.18) and $V_{H,h}^{(\ell+1)}\subset V_{h}$, we have

$\left\|\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}^{2}=\bar{\lambda}_{i,h}b\left(\bar{u}_{i,h},\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right)-\bar{\lambda}_{i,h}b\left(qu_{i,h}^{(\ell)},\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right).$

Since the spectral projection $E_{i,h}^{(\ell)}$ satisfies

$E_{i,h}^{(\ell)}\bar{u}_{i,h}=qu_{i,h}^{(\ell)},$

combined with (3.20), (3.7) and the inequality
$\eta_{a}(V_{H,h}^{(\ell+1)})\leq\eta_{a}(W_{H})$, we obtain

$\displaystyle\left\|\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}^{2}=\bar{\lambda}_{i,h}b\left(\bar{u}_{i,h}-E_{i,h}^{(\ell)}\bar{u}_{i,h},\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right)$
$\displaystyle\leq\bar{\lambda}_{i,h}\left\|\bar{u}_{i,h}-E_{i,h}^{(\ell)}\bar{u}_{i,h}\right\|_{b}\left\|\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{b}$
$\displaystyle\leq\bar{\lambda}_{i,h}\left(1+\frac{1}{\lambda_{1}\delta_{\lambda}^{(\ell)}}\right)\eta_{a}(W_{H})\left\|\bar{u}_{i,h}-E_{i,h}^{(\ell)}\bar{u}_{i,h}\right\|_{a,h}\eta_{a}(V_{H,h}^{(\ell+1)})\left\|\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}$
$\displaystyle\leq\bar{\lambda}_{i,h}\left(1+\frac{1}{\lambda_{1}\delta_{\lambda}^{(\ell)}}\right)\eta_{a}^{2}(W_{H})\left\|\bar{u}_{i,h}-E_{i,h}^{(\ell)}\bar{u}_{i,h}\right\|_{a,h}\left\|\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}.$
(3.21)

Since the approximation $u_{i,h}^{(\ell+1)}$ only comes from (3.19), we have

$\displaystyle\left\|\bar{u}_{i,h}-E_{i,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}$
$\displaystyle\leq$
$\displaystyle\sqrt{1+\frac{\eta_{a}^{2}(V_{H,h}^{(\ell+1)})}{\lambda_{1}\big{(}\delta_{\lambda}^{(\ell+1)}\big{)}^{2}}}\left\|(I-\mathcal{P}_{H,h}^{(\ell+1)})\bar{u}_{i,h}\right\|_{a,h}$
$\displaystyle\leq$
$\displaystyle\sqrt{1+\frac{\eta_{a}^{2}(W_{H})}{\lambda_{1}\big{(}\delta_{\lambda}^{(\ell+1)}\big{)}^{2}}}\left\|(I-\mathcal{P}_{H,h}^{(\ell+1)})\bar{u}_{i,h}\right\|_{a,h}.$

From (3), there holds

$\displaystyle\left\|\bar{u}_{i,h}-\mathcal{P}_{H,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}\leq\bar{\lambda}_{i,h}\left(1+\frac{1}{\lambda_{1}\delta_{\lambda}^{(\ell)}}\right)\eta_{a}^{2}(W_{H})\left\|\bar{u}_{i,h}-E_{i,h}^{(\ell)}\bar{u}_{i,h}\right\|_{a,h}.$
(3.22)

And considering (3.22), we have the following estimate

$\displaystyle\left\|\bar{u}_{i,h}-E_{i,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}\leq\bar{\lambda}_{i,h}\sqrt{1+\frac{\eta_{a}^{2}(W_{H})}{\lambda_{1}\big{(}\delta_{\lambda}^{(\ell+1)}\big{)}^{2}}}\left(1+\frac{1}{\lambda_{1}\delta_{\lambda}^{(\ell)}}\right)\eta_{a}^{2}(W_{H})\left\|\bar{u}_{i,h}-E_{i,h}^{(\ell)}\bar{u}_{i,h}\right\|_{a,h}.$
(3.23)

The following $\left\|\cdot\right\|_{b}$-error estimate holds

$\displaystyle\left\|\bar{u}_{i,h}-E_{i,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{b}\leq\left(1+\frac{1}{\lambda_{1}\delta_{\lambda}^{(\ell+1)}}\right)\eta_{a}(W_{H})\left\|\bar{u}_{i,h}-E_{i,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}.$
(3.24)

From (3.23) and (3.24), the proof is completed. ∎

######  Corollary 3.1.

Under the conditions of Theorem 3.2, the eigenfunction approximation
$u_{i,h}^{(\ell+1)}$ has the following error estimates

$\displaystyle\left\|\bar{u}_{i,h}-E_{i,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}$
$\displaystyle\leq$
$\displaystyle\big{(}\gamma(\bar{\lambda}_{i,h})\big{)}^{\ell}\
\left\|\bar{u}_{i,h}-E_{i,h}^{(1)}\bar{u}_{i,h}\right\|_{a,h},$ (3.25)
$\displaystyle\left\|\bar{u}_{i,h}-E_{i,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{b}$
$\displaystyle\leq$
$\displaystyle\left(1+\frac{1}{\lambda_{1}\delta_{\lambda}^{(\ell+1)}}\right)\eta_{a}(W_{H})\left\|\bar{u}_{i,h}-E_{i,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h},$
(3.26)

where

$\displaystyle\gamma(\bar{\lambda}_{i,h})=\bar{\lambda}_{i,h}\sqrt{1+\frac{\eta_{a}^{2}(W_{H})}{\lambda_{1}\big{(}\delta_{\lambda}^{(\ell+1)}\big{)}^{2}}}\left(1+\frac{1}{\lambda_{1}\delta_{\lambda}^{(\ell)}}\right)\eta_{a}^{2}(W_{H}).$
(3.27)

The error estimate for the eigenvalue approximation $\lambda_{i,h}^{(\ell)}$
can be deduced from Theorem 3.2 and Remark 3.2.

##  4 Numerical experiments

In this section, numerical experiments are presented to validate our
theoretical results. Here, we are concerned with the Laplace eigenvalue
problem (2.4), where the computing domain is set to be the unit square
$\Omega=(0,1)\times(0,1)$. $W_{H}$ and $V_{h}$ are chosen as the conforming
linear element and the CR element spaces defined on the coarse mesh
$\mathcal{T}_{H}$ and the fine mesh $\mathcal{T}_{h}$, respectively. The fine
mesh $\mathcal{T}_{h}$ is obtained from the coarse mesh $\mathcal{T}_{H}$ by
the regular refinement of uniform triangular mesh.

Since the coarse space $W_{H}$ is the conforming linear finite element space
defined on the coarse mesh $\mathcal{T}_{H}$, together with the theories of
the error estimates of CR element and conforming linear element [8, 11], it is
known that the following estimate holds when the mesh size $h<H$,

$\displaystyle\eta_{a}(W_{H})$ $\displaystyle\leq\sup_{f\in
L^{2}(\Omega),\|f\|_{b}=1}\left\\{\|Tf-T_{h}f\|_{a,h}+\inf_{v_{H}\in
W_{H}}\|Tf-v_{H}\|_{a}\right\\}$ $\displaystyle\leq CH,$

where the constant $C$ depends on shape of the meshes $\mathcal{T}_{H}$ and
$\mathcal{T}_{h}$.

Based on Theorems 3.1 and 3.2, the convergence results can be concluded with
the following inequalities

$\displaystyle\left\|\bar{u}_{i,h}-F_{k,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}\leq
C\big{(}CH\big{)}^{2\ell}\left\|\bar{u}_{i,h}-F_{k,h}^{(1)}\bar{u}_{i,h}\right\|_{a,h},\
\ \ \ i=1,\cdots,k,$ (4.1)
$\displaystyle\left\|\bar{u}_{i,h}-F_{k,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{b}\leq
CH\left\|\bar{u}_{i,h}-F_{k,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h},\ \ \ \
i=1,\cdots,k,$ (4.2)

and

$\displaystyle\left\|\bar{u}_{i,h}-E_{i,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}$
$\displaystyle\leq$ $\displaystyle
C\big{(}CH\big{)}^{2\ell}\left\|\bar{u}_{i,h}-E_{i,h}^{(1)}\bar{u}_{i,h}\right\|_{a,h},$
(4.3)
$\displaystyle\left\|\bar{u}_{i,h}-E_{i,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{b}$
$\displaystyle\leq$ $\displaystyle
CH\left\|\bar{u}_{i,h}-E_{i,h}^{(\ell+1)}\bar{u}_{i,h}\right\|_{a,h}.$ (4.4)

One of the purposes of this section is to check the overall error estimates
and algebraic error estimates (4.1)-(4.4) of our proposed methods. It should
be noted that the exact finite element eigenfunction is obtained by solving
the eigenvalue problem directly on the fine space $V_{h}$, which is the CR
element space defined on the fine mesh $\mathcal{T}_{h}$. To make it more
intuitive, in all the following figures, the notations with and without “dir”
superscript stand for the exact finite element eigenfunctions and the
augmented subspace approximations, respectively. The other purpose of this
section is to carry out the numerical tests for the computational complexity
by comparing Algorithms 1 and 2 with the Krylov-Schur method directly applied
on the final mesh without coarsening to verify the advantage of our
algorithms.

We should note that all the following numerical tests are accomplished on
LSSC-IV in the State Key Laboratory of Scientific and Engineering Computing,
Academy of Mathematics and Systems Science, Chinese Academy of Sciences, where
each computing node has two $18$-core Intel Xeon Gold $6140$ processors at
$2.3$ GHz and $192$ GB memory. The linear equations (3.2) in Algorithm 1 and
(3.18) in Algorithm 2 are solved by the package PETSc [4, 5, 6] with the
geometric multigrid method. The eigenvalue problems (3.1) and (3.3) in
Algorithm 1 and (3.17) and (3.19) in Algorithm 2 are solved by the Krylov-
Schur algorithm from SLEPc [24]. The single processor is adopted for the
convergence tests and $36$ processors for the computational complexity tests.

###  4.1 Tests for overall error estimates and computational efficiency

In this subsection, we carry out numerical examples to check the overall error
estimates and the computational complexity of our algorithms. In the tests of
error and computational efficiency, we fix the coarse mesh sizes
$H=\sqrt{2}/8$ and $H=\sqrt{2}/32$, respectively, and divide the fine mesh
$\mathcal{T}_{h}$. The initial eigenfunction approximations are obtained in
two steps: (1) The initial coarse eigenfunction approximations are produced by
solving the eigenvalue problem (2.4) on the coarse space $V_{H}$; (2) The
interpolation matrix is used to project the initial coarse eigenfunction
approximations onto the space $V_{h}$ to get the initial eigenfunction
approximations $u_{1,h}^{(1)},\cdots,u_{k,h}^{(1)}$. Then we do the iteration
steps by the augmented subspace method defined by Algorithms 1 and 2.

For comparison, we conduct the tests that the SLEPc solver (Krylov-Schur
method) is applied directly on the mesh $\mathcal{T}_{h}$ without coarsening,
which we also call the single level solver. Figure 1 gives the overall errors
for the first $4$ eigenvalues $2\pi^{2}$, $5\pi^{2}$, $5\pi^{2}$, $8\pi^{2}$
and their corresponding eigenfunctions by our algorithms and the single level
solver with $H=\sqrt{2}/8$, and Figure 2 shows the CPU time for computing the
first and the smallest $4$ eigenpair approximations with $H=\sqrt{2}/32$.

From Figure 1, it follows that the error convergence orders of the first $4$
eigenvalues and their corresponding eigenfunctions by our algorithms are
$O(h^{2})$ and $O(h)$, respectively. Furthermore, from the left subfigure of
Figure 1, we can find that the augmented subspace method can also obtain the
lower bound approximations of the eigenvalues.

As for the computational efficiency, from Figures 1 and 2, it can be seen that
the augmented subspace method provides almost the same results as the single
level solver but with smaller computational work.

Figure 1: Errors for the eigenpair approximations by our algorithms and the
single level solver for the first $4$ eigenvalues $2\pi^{2}$, $5\pi^{2}$,
$5\pi^{2}$, $8\pi^{2}$ and their corresponding eigenfunctions with
$H=\sqrt{2}/8$.

Figure 2: CPU time for our algorithms and the single level solver with
$H=\sqrt{2}/32$: The left subfigure shows the CPU time for the first eigenpair
approximation and the right subfigure shows the CPU time for the smallest $4$
eigenpair approximations.

###  4.2 Tests for algebraic error estimates

In this subsection, we check the algebraic error estimates of our proposed
algorithms, which is also one of the main contributions of this paper. In the
following numerical example, we set the fine mesh size $h=\sqrt{2}/512$ for
testing the convergence. The initial eigenfunction approximation is produced
by solving the eigenvalue problem (2.4) on the coarse space $W_{H}$. Then we
do the iteration steps by the augmented subspace method defined by Algorithms
1 and 2.

In order to validate the convergence results stated in (4.1)-(4.4), we check
the numerical errors corresponding to the linear finite element space $W_{H}$
with different sizes $H$. The aim is to check the dependence of the
convergence rate on the mesh size $H$.

Figure 3 shows the convergence behaviors for the first eigenfunction by the
augmented subspace methods corresponding to the coarse mesh size
$H=\sqrt{2}/8$, $\sqrt{2}/16$, $\sqrt{2}/32$ and $\sqrt{2}/64$, respectively.
The convergence rates related with $\|\cdot\|_{a,h}$ and $\|\cdot\|_{b}$ are
$0.048503$, $0.013692$, $0.0035433$ and $0.00089758$, and $0.052093$,
$0.014819$, $0.0038451$ and $0.001132$, separately. These results show that
the augmented subspace method defined by Algorithms 1 and 2 have the second
order convergence speed which also validates the results (4.1)-(4.4).

Figure 3: The convergence behaviors for the first eigenfunction by Algorithm 1
corresponding to the coarse mesh size $H=\sqrt{2}/8$, $\sqrt{2}/16$,
$\sqrt{2}/32$ and $\sqrt{2}/64$, respectively.

Then, we check the performance of Algorithm 1 for computing the smallest $4$
eigenpairs. Figure 4 shows the corresponding convergence behaviors for the
smallest $4$ eigenfunctions by Algorithm 1 with the coarse space being the
linear finite element space on the mesh with size $H=\sqrt{2}/8$,
$\sqrt{2}/16$, $\sqrt{2}/32$ and $\sqrt{2}/64$, respectively. Taking the
$4$-th eigenfunction for example, we can find that the corresponding
convergence rates are $0.52894$, $0.14163$, $0.033235$ and $0.0084715$, which
states the second order convergence speed of the method defined by Algorithm
1. Furthermore, from Figure 4, we can find the convergence rate for the $4$-th
eigenfucntion is slower than that for the $1$-st eigenfunction which is
consistent with Theorem 3.1.

Figure 4: The convergence behaviors for the smallest $4$ eigenfunctions by
Algorithm 1 with the coarse space being the linear finite element space on the
mesh with size $H=\sqrt{2}/8$, $\sqrt{2}/16$, $\sqrt{2}/32$ and $\sqrt{2}/64$,
respectively.

The final task is to check the performance of Algorithm 2 for computing the
only $4$-th eigenpair. Figure 5 shows the corresponding convergence behaviors
for the only $4$-th eigenfunction by Algorithm 2 with the coarse space being
the linear finite element space on the mesh with size $H=\sqrt{2}/8$,
$\sqrt{2}/16$, $\sqrt{2}/32$ and $\sqrt{2}/64$, respectively. The convergence
rates corresponding to $\|\cdot\|_{a,h}$ and $\|\cdot\|_{b}$ shown in Figure 5
are $0.5321$, $0.14456$, $0.033682$ and $0.0085807$, and $0.35757$, $0.12384$,
$0.034523$ and $0.0089362$, separately. These results show that the augmented
subspace method defined by Algorithm 2 has the second order convergence speed
which validates the results (4.3)-(4.4).

Figure 5: The convergence behaviors for the only $4$-th eigenfunction by
Algorithm 2 with the coarse space being the linear finite element space on the
mesh with size $H=\sqrt{2}/8$, $\sqrt{2}/16$, $\sqrt{2}/32$ and $\sqrt{2}/64$,
respectively.

##  5 Concluding remarks

In this paper, some enhanced error estimates for the CR element based
augmented subspace method are deduced for solving eigenvalue problems. Before
the new estimates, the explicit error estimates for single eigenpair and
multiple eigenpairs based on our defined spectral projection operators are
derived, respectively. Then we prove the second order algebraic error
convergence rate of the augmented subspace method. Based on the new algebraic
error results, we can also produce the corresponding sharper error estimates
for the multigrid or multilevel methods which are designed based on the
augmented subspace method and the sequence of grids.

## Acknowledgements

This work was partly supported by the Beijing Natural Science Foundation (No.
Z200003), the National Natural Science Foundation of China (No. 1233000214,
12301465), the National Center for Mathematics and Interdisciplinary Science,
Chinese Academy of Sciences, and by the Research Foundation for Beijing
University of Technology New Faculty (No. 006000514122516).

## Declarations

### Conflict of interest

All authors declare that they have no conflict of interest.

### Data availability

All data generated or analysed during the current study are available from the
corresponding author on reasonable request.

## References

  * [1] Adams, R. A., 1975. Sobolev spaces. Pure and Applied Mathematics, Vol. 65. Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London.
  * [2] Babuška, I., Osborn, J. E., 1989. Finite element-Galerkin approximation of the eigenvalues and eigenvectors of selfadjoint problems. Math. Comp. 52 (186), 275–297.
  * [3] Bai, Z., Demmel, J., Dongarra, J., Ruhe, A., van der Vorst, H., eds., 2000. Templates for the solution of algebraic eigenvalue problems: a practical guide. Society for Industrial and Applied Math., Philadelphia.
  * [4] Balay, S., Abhyankar, S., Adams, M. F., Brown, J., Brune, P., Buschelman, K., Dalcin, L., Dener, A., Eijkhout, V., Gropp, W. D., Karpeyev, D., Kaushik, D., Knepley, M. G., May, D. A., McInnes, L. C., Mills, R. T., Munson, T., Rupp, K., Sanan, P., Smith, B. F., Zampini, S., Zhang, H., Zhang, H., 2019. PETSc Web page.  https://www.mcs.anl.gov/petsc.
  * [5] Balay, S., Abhyankar, S., Adams, M. F., Brown, J., Brune, P., Buschelman, K., Dalcin, L., Dener, A., Eijkhout, V., Gropp, W. D., Karpeyev, D., Kaushik, D., Knepley, M. G., May, D. A., McInnes, L. C., Mills, R. T., Munson, T., Rupp, K., Sanan, P., Smith, B. F., Zampini, S., Zhang, H., Zhang, H., 2020. PETSc users manual. Tech. Report ANL-95/11 - Revision 3.14, Argonne National Laboratory.
  * [6] Balay, S., Gropp, W. D., McInnes, L. C., Smith, B. F., 1997. Efficient management of parallelism in object oriented numerical software libraries, in Modern Software Tools in Scientific Computing. Arge, E., Bruaset, A. M., Langtangen, H. P., eds., Birkhäuser Press, pp. 163–202.
  * [7] Bramble, J. H., Pasciak, J. E., Knyazev, A. V., 1996. A subspace preconditioning algorithm for eigenvector/eigenvalue computation. Adv. Comput. Math. 6 (2), 159–189 (1997).
  * [8] Brenner, S. C., Scott, L. R., 2008. The mathematical theory of finite element methods, 3rd Edition. Vol. 15 of Texts in Applied Mathematics. Springer, New York.
  * [9] Chatelin, F., 1983. Spectral approximation of linear operators. Computer Science and Applied Mathematics. Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York, with a foreword by P. Henrici, With solutions to exercises by Mario Ahués.
  * [10] Chen, H., Xie, H., Xu, F., 2016. A full multigrid method for eigenvalue problems. J. Comput. Phys. 322, 747–759.
  * [11] Ciarlet, P. G., 1978. The finite element method for elliptic problems. Studies in Mathematics and its Applications, Vol. 4. North-Holland Publishing Co., Amsterdam-New York-Oxford.
  * [12] Conway, J., 1990. A course in functional analysis. Springer-Verlag.
  * [13] Dang, H., Wang, Y., Xie, H., Zhou, C., 2023a. Enhanced error estimates for augmented subspace method. J. Sci. Comput. 94 (2), Paper No. 40, 24.
  * [14] Dang, H., Xie, H., Zhao, G., Zhou, C., 2023b. A nonnested augmented subspace method for elliptic eigenvalue problems with curved interfaces. J. Sci. Comput. 94 (2), Paper No. 34, 20.
  * [15] D’yakonov, E. G., Orekhov, Y. M., 1980. Minimization of the computational labor in determining the first eigenvalues of differential operators. Math. Notes 27, 382–391.
  * [16] Han, X., Li, Y., Xie, H., 2015. A multilevel correction method for Steklov eigenvalue problem by nonconforming finite element methods. Numer. Math. Theory Methods Appl. 8 (3), 383–405.
  * [17] Hong, Q., Xie, H., Xu, F., 2018. A multilevel correction type of adaptive finite element method for eigenvalue problems. SIAM J. Sci. Comput. 40 (6), A4208–A4235.
  * [18] Knyazev, A. V., 1998. Preconditioned eigensolvers—an oxymoron? Vol. 7. pp. 104–123, large scale eigenvalue problems (Argonne, IL, 1997).
  * [19] Knyazev, A. V., 2001. Toward the optimal preconditioned eigensolver: locally optimal block preconditioned conjugate gradient method. Vol. 23. pp. 517–541, copper Mountain Conference (2000).
  * [20] Knyazev, A. V., Neymeyr, K., 2003. Efficient solution of symmetric eigenvalue problems using multigrid preconditioners in the locally optimal block conjugate gradient method. Vol. 15. pp. 38–55, tenth Copper Mountain Conference on Multigrid Methods (Copper Mountain, CO, 2001).
  * [21] Li, Y., Xie, H., Xu, R., You, C., Zhang, N., 2020. A parallel generalized conjugate gradient method for large scale eigenvalue problems. CCF Trans. HPC 2, 111–122.
  * [22] Lin, Q., Xie, H., 2012. The asymptotic lower bounds of eigenvalue problems by nonconforming finite element methods. Math. Pract. Theory 42 (11), 219–226.
  * [23] Lin, Q., Xie, H., 2015. A multi-level correction scheme for eigenvalue problems. Math. Comp. 84 (291), 71–88.
  * [24] Roman, J. E., Campos, C., Romero, E., Tomǎs, A.. Slepc users manual–scalable library for eigenvalue problem computations. Tech. Report 3.14, Universitat Polit‘ecnica de Valencia, Spain.
  * [25] Sorensen, D. C., 1997. Implicitly restarted Arnoldi/Lanczos methods for large scale eigenvalue calculations. In: Parallel numerical algorithms (Hampton, VA, 1994). Vol. 4 of ICASE/LaRC Interdiscip. Ser. Sci. Eng. Kluwer Acad. Publ., Dordrecht, pp. 119–165.
  * [26] Xie, H., 2014. A multigrid method for eigenvalue problem. J. Comput. Phys. 274, 550–561.
  * [27] Xie, H., 2014. A type of multilevel method for the Steklov eigenvalue problem. IMA J. Numer. Anal. 34 (2), 592–608.
  * [28] Xie, H., 2015. A type of multi-level correction scheme for eigenvalue problems by nonconforming finite element methods. BIT 55 (4), 1243–1266.
  * [29] Xie, H., Zhang, L., Owhadi, H., 2019. Fast eigenpairs computation with operator adapted wavelets and hierarchical subspace correction. SIAM J. Numer. Anal. 57 (6), 2519–2550.
  * [30] Xu, F., Xie, H., Zhang, N., 2020. A parallel augmented subspace method for eigenvalue problems. SIAM J. Sci. Comput. 42 (5), A2655–A2677.
  * [31] Xu, J., Zhou, A., 2001. A two-grid discretization scheme for eigenvalue problems. Math. Comp. 70 (233), 17–25.
  * [32] Zhang, N., Li, Y., Xie, H., Xu, R., You, C., 2021. A generalized conjugate gradient method for eigenvalue problems (in Chinese). Scientia Sinica Mathematica 51, 1297–1320.