A robust multigrid method for discontinuous Galerkin discretizations of Stokes and linear elasticity equations

Abstract

We consider multigrid methods for discontinuous Galerkin $H({\text {div}},\Omega )$-conforming discretizations of the Stokes and linear elasticity equations. We analyze variable V-cycle and W-cycle multigrid methods with nonnested bilinear forms. We prove that these algorithms are optimal and robust, i.e., their convergence rates are independent of the mesh size and also of the material parameters such as the Poisson ratio. Numerical experiments are conducted that further confirm the theoretical results.

1 Introduction

In this paper we present a multigrid method for a family of discontinuous Galerkin (DG) $H({\text {div}},\Omega )$-conforming discretizations of the Stokes problem and the linear elasticity problem. The discretization for the Stokes problem preserves divergence-free velocity fields and was first introduced in [1]. The same method was also used in [2].

In general, the numerical discretization of the Stokes problem produces systems of linear algebraic equations of saddle-point type. Solving such systems has been the subject of extensive research work and at present several different approaches can be used to solve them efficiently (see [3] and references cited therein).

One widely used approach is to construct a block diagonal preconditioner with two blocks: one containing the inverse or a preconditioner of the stiffness matrix of a vector Laplacian and one containing the inverse of a lumped mass matrix for the pressure. The resulting preconditioned system can then be solved by means of the preconditioned MINRES (minimum residual) method.

Recently, an auxiliary space preconditioner for an $H({\text {div}},\Omega )$-conforming DG discretization of the Stokes problem was proposed in [4]. The auxiliary space preconditioning techniques were introduced in [5] as generalizations of the fictitious space methods (see [6]). Since the solution of the Stokes system has divergence-free velocity component, the problem can easily be reduced to a “second-order” problem in the space ${\text {Range}}({\text {curl}})$. In order to apply the preconditioner one needs to solve four elliptic problems, for details, see [4].

There are other multigrid methods which can roughly be classified into two categories: coupled and decoupled methods, cf. [7]. A well-known coupled approach is based on solving small saddle point systems at every grid point or on appropriate patches, cf. [8]. The Schur complement of each small saddle point system can be formed explicitly, and hence it is easy to solve the local problems. However, it is not straightforward to choose appropriate patches when the pressure is discretized by continuous elements. Further, when used as a smoothing iteration, this so-called Vanka method needs a proper damping parameter.

One classical decoupled approach is the augmented Uzawa method [9]. A crucial point in applying this method is the right choice of a damping parameter for solving the arising linear elasticity system. As proved in [9] the augmented Uzawa method is very efficient for solving the Stokes problem when the damping parameter is very large. In this case it is important to have a robust solver for the linear elasticity problem, that is, an iterative method that converges uniformly with respect to the Lamé parameters, or equivalently with respect to the Poisson ratio.

In [10], the author proposed and analyzed robust and optimal multigrid methods for the parameter dependent problem of nearly incompressible materials for the $P_2-P_0$ finite element scheme for the mixed system and for the corresponding non-conforming finite element scheme in primal variables. This approach relies on constructing a locally supported basis for the weakly divergence-free functions. In the present paper we construct suitable subspace decompositions of $H({\text {div}},\Omega )$, as suggested in [10], in order to design and analyze robust multigrid algorithms with nonnested (non-inherited) bilinear forms related to $H({\text {div}},\Omega )$-conforming DG discretizations. Similar ideas were used to build a robust subspace correction method for the system of linear algebraic equations arising from non-conforming finite element discretization based on reduced integration in [11]. An alternative approach is based on using augmented Lagrangian formulations for nearly singular systems, cf. [12].

We discretize the Stokes equation and the linear elasticity problem in a uniform mixed form by a DG method based on the $H({\text {div}},\Omega )$-conforming finite elements thereby introducing a parameter $\lambda$. We show that when $\lambda \rightarrow \infty$, the discrete solution of the linear elasticity problem converges to the discrete solution of the Stokes equation very quickly, i.e., with a convergence factor proportional to $\frac{1}{\lambda }$. We also establish a relationship to the convergence of the augmented Uzawa algorithm for the Stokes equation. In particular, this means that the approximate solution of the Stokes equation can be obtained with any accuracy if one solves the linear elasticity problem with a sufficiently large parameter $\lambda$. However, in this case an efficient multilevel solver is needed for the linear elasticity problem that is uniform with respect to the Lamé parameters. A key component of such a solver is an overlapping block-smoother which corresponds to an appropriate splitting of the space of divergence-free functions, cf. [13]. At the same time, noting that a truly divergence-free function on the coarse grid is also divergence-free on the fine grid, the transfer operator prolongating coarse-grid divergence-free functions to fine grid divergence-free functions is as simple as an inclusion operator. In this paper, we first show that the uniform discretization of the linear elasticity system and the Stokes problem is stable and optimal and then establish the approximation and smoothing properties necessary for the multigrid analysis [14, 15].

The layout of the paper is as follows. In Sect. 2 we state the Stokes and the linear elasticity problems. Their discontinuous Galerkin discretization is given in Sect. 3 along with a proof of its uniform stability and the optimality of the approximation. In Sect. 4, we propose a multigrid method and prove its robustness and optimal convergence. In Sect. 5, we present numerical results that confirm the robustness and optimal convergence of this multigrid method. Finally, we draw some conclusions in Sect. 6.

2 Problem formulation

In this section, we give the formulation of the Stokes and the linear elasticity problem. Let $\Omega \subset R^d~(d=2,3)$ be a polygonal domain with boundary $\partial \Omega$, $\varvec{f} \in L^2(\Omega )^d$, and $H^1_0(\Omega )=\{ u\in L^2(\Omega ):\nabla u \in L^2(\Omega ),u|_{\partial \Omega }=0 \}$. We also need the standard Sobolev spaces $L^2(\Omega ), H^1(\Omega ), H^2(\Omega )$, and the corresponding norms

$$\begin{aligned}&\Vert u\Vert =\left( \int _{\Omega } u^2dx\right) ^{1/2},\\&\Vert u\Vert _1=\left( \sum _{|\varvec{\alpha }|\le 1}\int _{\Omega }|\frac{\partial ^{\varvec{\alpha }} u}{\partial x^{\varvec{\alpha }}}|^2dx\right) ^{1/2},\\&\Vert u\Vert _2=\left( \sum _{|\varvec{\alpha }|\le 2}\int _{\Omega }|\frac{\partial ^{\varvec{\alpha }} u}{\partial x^{\varvec{\alpha }}}|^2dx\right) ^{1/2}. \end{aligned}$$

The variational formulation of the Stokes and the mixed formulation of the elasticity problem can be written as: Find $(\varvec{u},p) \in H^1_0(\Omega )^d\times L^2_0(\Omega )$ such that

$$\begin{aligned} \left\{ \begin{array}{l} a(\varvec{u},\varvec{v})+b(\varvec{v}, p)=(\varvec{f},\varvec{v}),\quad \text{ for } \text{ all }\quad \varvec{v} \in H^1_0(\Omega )^d,\\ b(\varvec{u},q)- (\delta p,q) =0,\quad \text{ for } \text{ all }\quad q \in L^2_0(\Omega ), \end{array} \right. \end{aligned}$$

(2.1)

Here, with the usual notation, $\varvec{u}$ is the velocity field (displacement in the case of elasticity), $p$ is the pressure, and $\varepsilon (\varvec{u})\in L^2(\Omega )^{d\times d}_{sym}$ is the symmetric (linearized) strain rate tensor defined by $\varepsilon (\varvec{u})=\frac{\nabla \varvec{u}+\nabla \varvec{u}^{T}}{2}$. For the Stokes equation, one takes $\delta =0$, and for elasticity equation, we have $\delta =\lambda ^{-1}$, with $\lambda$ being the Lamè parameter defined as $\lambda =\nu /(1-2\nu )$, $0\le \nu < \frac{1}{2}$ and $\nu$ is the Poisson ratio.

The bilinear forms $a(\cdot ,\cdot )$, $b(\cdot ,\cdot )$, and $(\cdot ,\cdot )$ are defined by

$$\begin{aligned} \begin{aligned} a(\varvec{u}, \varvec{v})&:=\int _{\Omega } \varepsilon (\varvec{u}):\varepsilon (\varvec{v})dx, \quad \text{ for } \text{ all }\quad \varvec{u},\varvec{v} \in H^1_0(\Omega )^d,\\ b(\varvec{u},q)&:=\int _{\Omega }q\,{\text {div}}\, \varvec{u}dx,\quad \text{ for } \text{ all }\quad \varvec{u} \in H^1_0(\Omega )^d, q\in L^2_0(\Omega ),\\ (p,q)&:=\int _{\Omega } pq\;dx, \quad \text{ for } \text{ all }\quad p,q\in L^2_0(\Omega ). \end{aligned} \end{aligned}$$

(2.2)

For the linear elasticity problem, we also have the corresponding primal formulation, which is: Find $\varvec{u}$ in $H^1_0(\Omega )^d$ such that

$$\begin{aligned} (\varepsilon ( \varvec{u}):\varepsilon (\varvec{v}))+\lambda ({\text {div}}\, \varvec{u},{\text {div}}\, \varvec{v})= (\varvec{f},\varvec{v}),\quad \text{ for } \text{ all }\quad \varvec{v}\in H^1_0(\Omega )^d. \end{aligned}$$

(2.3)

The conditions for the existence and uniqueness of the solution $(\varvec{u},p)$ of (2.1) are well known and understood, see, e.g. [16]. For the relationship between the inf-sup condition for the Stokes problem and the Korn’s inequality which guarantees the solvability of the elasticity equations see also [17]. For convenience, in this paper, we assume that the domain $\Omega$ is such that the following regularity estimate holds (see e.g. [18] for the limiting case of the Stokes equation and [19, Lemma 2.2] for the corresponding result in linear elasticity):

$$\begin{aligned} \Vert \varvec{u}\Vert _2+\Vert p\Vert _1\lesssim \Vert \varvec{f}\Vert . \end{aligned}$$

(2.4)

Here, in Eq. (2.4) and throughout the presentation that follows, the hidden constants in $\lesssim ,~\gtrsim$ and $\eqsim$ are independent of $\lambda$ and the mesh size $h$.

3 Discontinuous Galerkin discretization

In the preliminary considerations of this section we introduce some notation related to DG methods. Next, we derive a DG discretization of the Stokes problem and the equations of linear elasticity in a uniform mixed form. Finally, we analyze the stability and approximation properties of this discretization.

3.1 Preliminaries and notation

We denote by $T_h$ a shape-regular triangulation of mesh-size $h$ of the domain $\Omega$ into triangles $\{K\}$. We further denote by $E_h^{I}$ the set of all interior edges (or faces) of $T_h$ and by $E_h^{B}$ the set of all boundary edges (or faces); we set $E_h=E_h^{I}\cup E_h^{B}$.

For $s\ge 1$, we define

$$\begin{aligned} H^s(T_h)=\left\{ \phi \in L^2(\Omega ), \, \text{ such } \text{ that } \,\phi |_K\in H^s(K)\, \text{ for } \text{ all } \, K\in T_h \right\} . \end{aligned}$$

Vector functions are represented column-wise and we recall the definition of the space

$$\begin{aligned} H({\text {div}};\Omega ):=\left\{ \varvec{v} \in L^2(\Omega ): {\text {div}}\, \varvec{v}\in L^2(\Omega )\right\} , \end{aligned}$$

with the norm

$$\begin{aligned} \Vert \varvec{v}\Vert ^2_{H({\text {div}};\Omega )}:=\Vert \varvec{v}\Vert ^2+\Vert {\text {div}}\, \varvec{v}\Vert ^2. \end{aligned}$$

Next, as is usual in the construction of DG methods, we define certain trace operators. Let $e = \partial K_1 \cap \partial K_2$ be the common boundary (interface) of two subdomains $K_1$ and $K_2$ in $T_h$ , and $\varvec{n}_1$ and $\varvec{n}_2$ be unit normal vectors to $e$ pointing to the exterior of $K_1$ and $K_2$, respectively. For any edge (or face) $e \in E_h^{I}$ and a scalar $q\in H^1(T_h)$, vector $\varvec{v} \in H^1(T_h)^d$ and tensor $\varvec{\tau }\in H^1(T_h)^{d\times d}$, we define the averages

$$\begin{aligned} \{\varvec{v}\}= & {} \frac{1}{2}(\varvec{v}|_{\partial K_1\cap e}\cdot \varvec{n}_1-\varvec{v}|_{\partial K_2\cap e}\cdot \varvec{n}_2), \quad \{\varvec{\tau }\}=\frac{1}{2}(\varvec{\tau }|_{\partial K_1\cap e} \varvec{n}_1-\varvec{\tau }|_{\partial K_2\cap e} \varvec{n}_2), \end{aligned}$$

and jumps

$$\begin{aligned}&[q]=q|_{\partial K_1\cap e}-q|_{\partial K_2\cap e},\quad [\varvec{v}]=\varvec{v}|_{\partial K_1\cap e}-\varvec{v}|_{\partial K_2\cap e},\quad \nonumber \\&[\![\varvec{v}]\!]=\varvec{v}|_{\partial K_1\cap e}\odot \varvec{n}_1+\varvec{v}|_{\partial K_2\cap e}\odot \varvec{n}_2, \end{aligned}$$

where $\varvec{v} \odot \varvec{n}=\frac{1}{2}(\varvec{v} \varvec{n}^T+\varvec{n} \varvec{v}^T)$ is the symmetric part of the tensor product of $\varvec{v}$ and $\varvec{n}$.

When $e \in E_h^{B}$ then the above quantities are defined as

$$\begin{aligned} \{\varvec{v}\}=\varvec{v} |_{e}\cdot \varvec{n},\quad \{\varvec{\tau }\}=\varvec{\tau }|_{e}\varvec{n}, \quad [q]=q|_{e}, ~~ [\varvec{v}]=\varvec{v}|_{e}, \quad [\![\varvec{v}]\!]=\varvec{v}|_{e}\odot \varvec{n}. \end{aligned}$$

If $\varvec{n}_K$ is the outward unit normal to $\partial K$, it is easy to check that

$$\begin{aligned} \sum _{K\in T_h}\int _{\partial K}\varvec{v}\cdot \varvec{n}_K q ds=\sum _{e\in E_h}\int _{e}\{\varvec{v}\} [q] ds, \quad \text{ for } \text{ all }\quad \varvec{v}\in H({\text {div}};\Omega ), \quad q\in H^1(T_h).\quad \qquad \end{aligned}$$

(3.1)

Also, for $\varvec{\tau }\in H^1(\Omega )^{d\times d}$ and for all $\varvec{v}\in H^1(T_h)^d$, we have

$$\begin{aligned} \sum _{K\in T_h}\int _{\partial K}(\varvec{\tau }\varvec{n}_K)\cdot \varvec{v}ds=\sum _{e\in E_h}\int _{e}\{\varvec{\tau }\}\cdot [\varvec{v}] ds. \end{aligned}$$

(3.2)

The finite element spaces we are going to use are denoted by

$$\begin{aligned} \varvec{V}_h= & {} \left\{ \varvec{v} \in H({\text {div}};\Omega ):\varvec{v}|_K \in \varvec{V}(K),~K \in T_h;~ \varvec{v} \cdot \varvec{n}=0~\hbox {on}~\partial \Omega \right\} , \\ S_h= & {} \left\{ q \in L^2(\Omega ):q|_K \in Q(K),~K \in T_h; ~\int _{\Omega }q dx=0\right\} . \end{aligned}$$

For the DG method, we use the RT pair $RT_l(K)/P_l(K)$ or the BDM pair $BDM_l(K)/P_{l-1}(K)$ or the BDFM pair $BDFM_l(K)/P_{l-1}(K)$ as $\varvec{V}(K){/}Q(K)$ which satisfy ${\text {div}}\, \varvec{V}(K)=Q(K)$ and preserve the divergence-free velocity fields, (see [4]).

We recall the basic approximation properties of these spaces: for all $K\in T_h$ and for all $\varvec{v} \in H^s(K)^d$, there exists $\varvec{v}_I\in \varvec{V}(K)$ such that

$$\begin{aligned} \Vert \varvec{v}{-}\varvec{v}_I\Vert _{0,K}+h_K|\varvec{v}{-}\varvec{v}_I|_{1,K}+h_K^2|\varvec{v}{-}\varvec{v}_I|_{2,K} \lesssim h_K^s|\varvec{v}|_{s,K}, ~2\le s \le l\!+\!1. \end{aligned}$$

(3.3)

3.2 DG formulation

We note that according to the definition of $\varvec{V}_h$, the normal component of any $\varvec{v}\in \varvec{V}_h$ is continuous on the internal edges and vanishes on the boundary edges. Therfore, by splitting a vector $\varvec{v}\in \varvec{V}_h$ into its normal and tangential components $\varvec{v}_n$ and $\varvec{v}_t$

$$\begin{aligned} \varvec{v}_n:=(\varvec{v}\cdot \varvec{n})\varvec{n},\quad \varvec{v}_t:=\varvec{v}- \varvec{v}_n, \end{aligned}$$

(3.4)

we have for all $e\in E_h$

$$\begin{aligned} \int _e[\varvec{v}_n]\cdot \varvec{\tau }ds=0,\quad \text{ for } \text{ all }\quad \varvec{\tau }\in H^1(T_h)^d, \varvec{v}\in \varvec{V}_h, \end{aligned}$$

(3.5)

implying that

$$\begin{aligned} \int _e[\varvec{v}]\cdot \varvec{\tau }ds=\int _e[\varvec{v}_t]\cdot \varvec{\tau }ds=0, \quad \text{ for } \text{ all }\quad \varvec{\tau }\in H^1(T_h)^d,\varvec{v} \in V_h. \end{aligned}$$

(3.6)

A direct computation shows that

$$\begin{aligned}{}[\![\varvec{u}_t]\!]:[\![\varvec{v}_t]\!]=\frac{1}{2}[\varvec{u}_t] \cdot [\varvec{v}_t]. \end{aligned}$$

(3.7)

Therefore, the discretization of the variational formulation of problem (2.1) is given by: Find $(\varvec{u}_h ,p_h)\in \varvec{V}_h\times S_h$  such  that

$$\begin{aligned} \left\{ \begin{array}{l} a_h(\varvec{u}_h,\varvec{v}_h)+b_h(\varvec{v}_h,p_h)=(\varvec{f},\varvec{v}_h),\quad \text{ for } \text{ all }\quad \varvec{v}_h\in \varvec{V}_h, \\ b_h(\varvec{u}_h,q_h)-(\lambda ^{-1}p_h,q_h)=0,\quad \text{ for } \text{ all }\quad q_h\in S_h, \end{array} \right. \end{aligned}$$

(3.8)

where

$$\begin{aligned} a_h(\varvec{u},\varvec{v})= & {} \sum _{K \in T_h} \int _K \varepsilon (\varvec{u}) : \varepsilon (\varvec{v}) dx-\sum _{e \in E_h} \int _e \{\varepsilon (\varvec{u})\} \cdot [\varvec{v}_t] ds\nonumber \\&\!\!-\sum _{e \in E_h} \int _e \{\varepsilon (\varvec{v})\} \cdot [\varvec{u}_t]ds+\sum _{e \in E_h} \int _e \eta h_e^{-1}[ \varvec{u}_t] \cdot [\varvec{v}_t] ds,\end{aligned}$$

(3.9)

$$\begin{aligned} b_h(\varvec{u},q)= & {} \int _{\Omega }\nabla \cdot \varvec{u} q dx,~~~(\lambda ^{-1}p_h,q_h)=\lambda ^{-1}\int _{\Omega } p_h q_hdx, \end{aligned}$$

(3.10)

and $\eta$ is a properly chosen penalty parameter independent of the mesh size $h$ and so that $a_h(\cdot ,\cdot )$ is positive definite.

It is straightforward to see that the bilinear form (3.9) matches the bilinear form given in [1, 4]. Noting that ${\text {div}}\, \varvec{V}_h=S_h$, from the second equation of (3.8), we can obtain $p_h=\lambda \hbox {div}\varvec{u}_h$. Plugging $p_h=\lambda \hbox {div}\varvec{u}_h$ into the first equation of (3.8), we arrive in the discrete problem of the linear elasticity equation (2.3) which reads: Find $\varvec{u}_h\in \varvec{V}_h$ such that

$$\begin{aligned} A_h(\varvec{u}_h,\varvec{v}_h)=(\varvec{f},\varvec{v}_h),\quad \text{ for } \text{ all }\quad \varvec{v}_h\in \varvec{V}_h, \end{aligned}$$

(3.11)

where $A_h(\cdot ,\cdot )$ reads

$$\begin{aligned} A_h(\varvec{u}_h,\varvec{v}_h)= a_h(\varvec{u}_h,\varvec{v}_h)+\lambda ({\text {div}}\, \varvec{u}_h,{\text {div}}\, \varvec{v}_h), \end{aligned}$$

(3.12)

and $a_h(\varvec{u}_h,\varvec{v}_h)$ is defined by (3.9).

Hence we can solve (3.8) by solving (3.11) to get $\varvec{u}_h$ firstly and then obtain the pressure $p_h=\lambda \hbox {div}\varvec{u}_h$.

Remark 1

Noting that the application of the augmented Uzawa method to the Stokes equation with damping parameter $\lambda$ reads: given $(\varvec{u}^l_h,p^l)$, the new iterate $(\varvec{u}^{l+1}_h,p^{l+1})$ is obtained by solving the following system:

$$\begin{aligned} \left\{ \begin{array}{l} a_h(\varvec{u}_h^{l+1},\varvec{v}_h)+\lambda ({\text {div}}\, \varvec{u}_h^{l+1}, {\text {div}}\, \varvec{v}_h)=(\varvec{f},\varvec{v}_h)-b_h(\varvec{v}_h,p_h^{l}), \hbox { for all } \varvec{v}_h\in \varvec{V}_h, \\ p_h^{l+1}=p^l_h+\lambda {\text {div}}\, \varvec{u}^{l+1}_h, \end{array} \right. \nonumber \\ \end{aligned}$$

(3.13)

it is obvious that if we choose $l=0$ and $p_h^0=0$ then in the next step of augmented Uzawa iteration, the first equation of (3.13) coincides with (3.11) and the second equation of (3.13) is just $p_h=\lambda \hbox {div}\varvec{u}_h$. Convergence of the the augmented Uzawa iteration has been discussed in several works, see, e.g., [9, 12, 20, 21] indicating that for sufficiently large $\lambda$, the iterates converge rapidly to the solution of Stokes equation.

3.3 Approximation and stability properties

In this subsection, we analyze the approximation and stability properties of the discrete problems (3.8) and (3.11)–(3.12).

For any $\varvec{u}\in H^1(T_h)^d$, we now define the mesh dependent norms:

$$\begin{aligned} \Vert \varvec{u}\Vert _h^2= & {} \sum _{K \in T_h} \Vert \varepsilon (\varvec{u})\Vert _{0,K}^2+\sum _{e \in E_h} h_e^{-1}\Vert [ \varvec{u}_t]\Vert _{0,e}^2, \\ \Vert \varvec{u}\Vert _{1,h}^2= & {} \sum _{K \in T_h} \Vert \nabla \varvec{u}\Vert _{0,K}^2+\sum _{e \in E_h} h_e^{-1}\Vert [ \varvec{u}_t]\Vert _{0,e}^2, \end{aligned}$$

Next, for $\varvec{u}\in H^2(T_h)^d$, we define the “DG”-norm

$$\begin{aligned} \Vert \varvec{u}\Vert ^2_{DG}=\sum _{K \in T_h} \Vert \nabla \varvec{u}\Vert _{0,K}^2+\sum _{e \in E_h} h_e^{-1}\Vert [ \varvec{u}_t]\Vert _{0,e}^2+\sum _{K \in T_h}h_K^2|\varvec{u}|^2_{2,K}. \end{aligned}$$

(3.14)

We now summarize several results on well-posedness and approximation properties of the DG formulation.

• From the discrete version of the Korn’s inequality (see [22, Equation (1.12)]) we have that the norms $\Vert \cdot \Vert _{DG}$, $\Vert \cdot \Vert _h$, and $\Vert \cdot \Vert _{1,h}$ are equivalent on $\varvec{V}_h$, namely,

  $$\begin{aligned} \Vert \varvec{u}\Vert _{DG}\eqsim \Vert \varvec{u}\Vert _h\eqsim \Vert \varvec{u}\Vert _{1,h},\quad \text{ for } \text{ all }\quad ~\varvec{u} \in \varvec{V}_h . \end{aligned}$$

  (3.15)

• Both bilinear forms, $a_h(\cdot ,\cdot )$ and $b_h(\cdot ,\cdot )$, introduced above are continuous and we have

  $$\begin{aligned} |a_h(\varvec{u},\varvec{v})|\lesssim & {} \Vert \varvec{u} \Vert _{DG} \Vert \varvec{v} \Vert _{DG},\quad \text{ for } \text{ all }\quad \varvec{u},~\varvec{v}\in H^2(T_h)^d,\\ |b_h(\varvec{u},q)|\le & {} \Vert \varvec{u}\Vert _{1,h}\Vert q\Vert ,\quad \text{ for } \text{ all }\quad ~\varvec{u}\in H^1(T_h)^d, q\in L^2_0(\Omega ). \end{aligned}$$

• For our choice of the finite element spaces $\varvec{V}_h$ and $S_h$ we have the following inf-sup condition for $b_h(\cdot ,\cdot )$ (see, e.g., [4, 23])

  $$\begin{aligned} \inf _{q_h\in S_h}\sup _{\varvec{u}_h\in \varvec{V}_h}\frac{({\text {div}}\,\varvec{u}_h,q_h)}{\Vert \varvec{u}_h\Vert _{1,h}\Vert q_h\Vert }\ge \beta . \end{aligned}$$

  (3.16)

• We also have that $a_h(\cdot ,\cdot )$ is coercive, and the proof of this fact parallels the proofs of similar results in [4, 24].

  $$\begin{aligned} a_h(\varvec{u}_h,\varvec{u}_h)\gtrsim \Vert \varvec{u}_h\Vert ^2_h,\quad \text{ for } \text{ all }\quad ~\varvec{u}_h\in \varvec{V}_h. \end{aligned}$$

  (3.17)

The bilinear forms $a_h(\cdot ,\cdot )$ and $A_h(\cdot ,\cdot )$ define norms on $\varvec{V}_h$ denoted as follows

$$\begin{aligned} \Vert \varvec{u}\Vert _{a_h}^2 = a_h(\varvec{u},\varvec{u}), \quad \Vert \varvec{u}\Vert _{A_h}^2 = A_h(\varvec{u},\varvec{u}). \end{aligned}$$

Next, we introduce the canonical interpolation operators $\Pi _h^{{\text {div}}}:H^1(\Omega )^d\mapsto \varvec{V}_h$. We also denote the $L^2$-projection on $S_h$ by $Q_h$. The following Lemma summarizes some of the properties of $\Pi _h^{{\text {div}}}$ and $Q_h$ needed later and their proofs are either straightforward by the definition or well known (see, e.g. [25]).

Lemma 1

For all $\varvec{w} \in H^1(K)^d$ we have

$$\begin{aligned}&{\text {div}}\Pi _h^{{\text {div}}}=Q_h {\text {div}}\;;\quad |\Pi _h^{{\text {div}}} \varvec{w}|_{1,K} \lesssim |\varvec{w}|_{1,K};\\&\Vert \varvec{w}-\Pi _h^{{\text {div}}} \varvec{w}\Vert ^2_{0,\partial K}\lesssim h_K |\varvec{w}|^2_{1,K};\quad \Vert {\text {div}}(\varvec{w}-\Pi _h^{{\text {div}}} \varvec{w})\Vert _{-1}\lesssim h_K \Vert {\text {div}}\varvec{w}\Vert , \end{aligned}$$

where $\Vert r\Vert _{-1} = \sup _{\chi \in H^1}\frac{(\chi ,r)}{\Vert \chi \Vert _1}$.

The following result shows that the discrete problem we consider is well posed and the resulting approximation is optimal.

Theorem 1

Let $(\varvec{u}, p)$ be the solution of (2.1) and $(\varvec{u}_h, p_h)$ be the solution of (3.8). Then we have the following estimate

$$\begin{aligned}&\Vert \varvec{u}{-}\varvec{u}_h\Vert ^2_{DG}\!+\!\lambda ^{-1}\Vert p{-}p_h\Vert ^2\lesssim \inf _{\varvec{v}_h \in \varvec{V}_h, q_h\in S_h}\Big (\Vert \varvec{u}{-}\varvec{v}_h\Vert ^2_{DG}+\lambda ^{-1}\Vert p-q_h\Vert ^2\Big ),\end{aligned}$$

(3.18)

$$\begin{aligned}&\quad \Vert p-p_h\Vert ^2\lesssim \inf _{\varvec{v}_h \in \varvec{V}_h, q_h\in S_h}\Big (\Vert \varvec{u}-\varvec{v}_h\Vert ^2_{DG}+\Vert p-q_h\Vert ^2+\lambda ^{-1}\Vert p-q_h\Vert ^2\Big ). \end{aligned}$$

(3.19)

Proof

If $(\varvec{u},p)$ is the solution of the continuous problem (2.1) and $(\varvec{u}_h,p_h)$ is the solution of the discrete problem (3.8) we have that $p=\lambda {\text {div}}\, \varvec{u}$, and, since ${\text {div}}\, \varvec{V}_h=S_h$ we also have that $p_h=\lambda {\text {div}}\, \varvec{u}_h$. The left hand side of the first equation in (3.8) then is given by the bilinear form (3.12), and, since this discrete problem is consistent, we have

$$\begin{aligned} A_h(\varvec{u}-\varvec{u}_h,\varvec{v})=0, ~~\hbox {for all}~ \varvec{v}\in \varvec{V}_h. \end{aligned}$$

Consider now the interpolation $\Pi ^{{\text {div}}}_h \varvec{u}\in \varvec{V}_h$ of $\varvec{u}$ and we set $q=\lambda {\text {div}}\Pi ^{{\text {div}}}_h \varvec{u}$. Recall that $p=\lambda {\text {div}}\, \varvec{u}$, and $p_h=\lambda {\text {div}}\, \varvec{u}_h$ and hence (by Lemma 1) $q=\lambda Q_h{\text {div}}\varvec{u}=Q_hp$. We set $\varvec{e}_h = (\varvec{u}_h-\Pi ^{{\text {div}}}_h\varvec{u})$ and from the coercivity of $a_h(\cdot ,\cdot )$ we have

$$\begin{aligned}&\Vert \varvec{e}_h\Vert ^2_{1,h}+\lambda ^{-1} \Vert p_h-q\Vert ^2 =\Vert \varvec{e}_h\Vert ^2_{1,h}+\lambda \Vert {\text {div}}\, \varvec{e}_h\Vert ^2 \nonumber \\&\quad \lesssim A_h(\varvec{e}_h, \varvec{e}_h) = A_h(\varvec{u}-\Pi ^{{\text {div}}}_h\varvec{u}, \varvec{e}_h)\nonumber \\&\quad \lesssim \Vert \varvec{u}-\Pi ^{{\text {div}}}_h\varvec{u}\Vert _{DG} \Vert \varvec{e}_h\Vert _{1,h}+ \lambda ({\text {div}}(\varvec{u}-\Pi ^{{\text {div}}}_h\varvec{u}), {\text {div}}\, \varvec{e}_h)\nonumber \\&\quad =\Vert \varvec{u}-\Pi ^{{\text {div}}}_h\varvec{u}\Vert _{DG} \Vert \varvec{e}_h\Vert _{1,h}. \end{aligned}$$

(3.20)

The last identity above follows from ${\text {div}}(\varvec{u}-\Pi ^{{\text {div}}}_h\varvec{u})=(I-Q_h){\text {div}}\varvec{u}$ and ${\text {div}}\, \varvec{e}_h\in S_h$. By Lemma 1, we get

$$\begin{aligned} \Vert \varvec{u}_h-\Pi ^{{\text {div}}}_h\varvec{u}\Vert _{1,h}= \Vert \Pi ^{{\text {div}}}_h(\varvec{u}_h-\varvec{u})\Vert _{1,h}\lesssim \Vert \varvec{u}_h-\varvec{u}\Vert _{1,h}, \end{aligned}$$

(3.21)

and therefore, the right hand side of Eq. (3.20) is bounded by a multiple of $\Vert \varvec{u}-\Pi ^{{\text {div}}}_h\varvec{u}\Vert _{DG}\Vert \varvec{u}_h-\varvec{u}\Vert _{DG}$. As for any $\epsilon > 0$ we have $ab \le \epsilon a^2+ \epsilon ^{-1} b^2$ and using Lemma 1 we have for any $\varvec{v}_h\in \varvec{V}_h$ and any $q_h\in S_h$,

$$\begin{aligned}&\Vert \varvec{u}-\varvec{u}_h\Vert ^2_{DG}+\lambda ^{-1} \Vert p-p_h\Vert ^2\lesssim \Vert \varvec{u}-\Pi ^{{\text {div}}}_h\varvec{u}\Vert _{DG}^2+\lambda ^{-1} \Vert p-Q_h p\Vert ^2 \nonumber \\&\quad = \Vert \varvec{u}-\varvec{v}_h -\Pi ^{{\text {div}}}_h(\varvec{u}-\varvec{v}_h)\Vert _{DG}^2+\lambda ^{-1} \Vert p-q_h-Q_h (p-q_h)\Vert ^2. \end{aligned}$$

(3.22)

Using Lemma 1 and taking the infimum over $\varvec{v}_h$ and $q_h$ then gives (3.18).

Next by the inf-sup condition (3.16) and the continuity of $a_h(\cdot ,\cdot )$, we have

$$\begin{aligned} \Vert q_h-p_h\Vert\lesssim & {} \sup _{\varvec{\psi }_h\in \varvec{V}_h}\frac{({\text {div}}\,\varvec{\psi }_h,q_h-p_h)}{\Vert \varvec{\psi }_h\Vert _{1,h}}= \sup _{\varvec{\psi }_h\in \varvec{V}_h}\frac{({\text {div}}\,\varvec{\psi }_h,q_h-p+p-p_h)}{\Vert \varvec{\psi }_h\Vert _{1,h}}\nonumber \\= & {} \sup _{\varvec{\psi }_h\in \varvec{V}_h}\frac{({\text {div}}\,\varvec{\psi }_h,q_h{-}p)\!+\!a_h(\varvec{u}{-}\varvec{u}_h,\varvec{\psi }_h)}{\Vert \varvec{\psi }_h\Vert _{1,h}}\nonumber \\\lesssim & {} \Vert p{-}q_h\Vert \!+\!\Vert \varvec{u}{-}\varvec{u}_h\Vert _{DG}. \end{aligned}$$

(3.23)

Hence, using the triangle inequality and the estimate (3.18), we obtain

$$\begin{aligned} \Vert p-p_h\Vert ^2\lesssim & {} \Vert p-q_h\Vert ^2+\Vert q_h-p_h\Vert ^2\lesssim \Vert p-q_h\Vert ^2+ \Vert p-q_h\Vert ^2+\Vert \varvec{u}-\varvec{u}_h\Vert ^2_{DG}\nonumber \\\lesssim & {} \Vert p-q_h\Vert ^2+ \Vert \varvec{u}-\varvec{v}_h\Vert ^2_{DG}+\lambda ^{-1}\Vert p-q_h\Vert ^2. \end{aligned}$$

(3.24)

Again taking the infimum over $\varvec{v}_h$ and $q_h$ then completes the proof of (3.19).

Remark 2

Let $\varvec{u}$ be the solution of (2.3) and $\varvec{u}_h$ be the solution of (3.11)–(3.12). From Theorem 1 and the regularity estimate (2.4), we obtain the following estimate

$$\begin{aligned} \Vert \varvec{u}-\varvec{u}_h\Vert _{DG}\lesssim h \Vert \varvec{f}\Vert , \end{aligned}$$

(3.25)

which means the discretization (3.11)–(3.12) for the elasticity equation is locking-free.

Remark 3

When $\lambda \rightarrow \infty$, from Theorem 1 we conclude that the solution $(\varvec{u}_h,p_h)\in \varvec{V}_h\times S_h$ of the discrete problem (3.8) satisfies

$$\begin{aligned} \Vert \varvec{u}-\varvec{u}_h\Vert _{DG}\lesssim & {} \inf _{\varvec{v}_h \in \varvec{V}_h}\Vert \varvec{u}{-}\varvec{v}_h\Vert _{DG}, \quad \nonumber \\ \Vert p{-}p_h\Vert\lesssim & {} \inf _{\varvec{v}_h \in \varvec{V}_h, q_h\in S_h}\Big (\Vert p-q_h\Vert \!+\!\Vert \varvec{u}-\varvec{v}_h\Vert _{DG}\Big ), \end{aligned}$$

(3.26)

and $\hbox {div}~\varvec{u}_h=0$ where $(\varvec{u},p)$ is the solution of the Stokes equation.

Remark 4

Let us set

$$\begin{aligned} B_{\lambda }((\varvec{u}_h,p_h),(\varvec{v}_h,q_h))=a_h(\varvec{u}_h, \varvec{v}_h)-({\text {div}}\, \varvec{u}_h, q_h)-({\text {div}}\, \varvec{v}_h, p_h) -\lambda ^{-1}(p_h,q_h). \end{aligned}$$

Then for any given $(\varvec{u}_h,p_h)$, choosing $(\varvec{v}_h, q_h)=(\varvec{u}_h,-p_h)$, by the coercivity of $a_h(\cdot , \cdot )$, it is straightforward to show that the inf-sup condition for $B_{\lambda }(\cdot ,\cdot )$ holds, namely, for any $(\varvec{u}_h,p_h)\in \varvec{V}_h\times S_h$ we have

$$\begin{aligned} \sup _{(\varvec{v}_h, q_h)\in \varvec{V}_h\times S_h}\frac{B_{\lambda }((\varvec{u}_h,p_h),(\varvec{v}_h,q_h))}{\Vert \varvec{v}_h\Vert _{1,h}+ \lambda ^{-1/2} \Vert q_h\Vert }\gtrsim ( \Vert \varvec{u}_h\Vert _{1,h}+\lambda ^{-1/2} \Vert p_h\Vert ). \end{aligned}$$

(3.27)

For the Stokes equation, we have from [26, Theorem 8.2.1] and [27, 28] that

$$\begin{aligned} \sup _{(\varvec{v}_h, q_h)\in \varvec{V}_h\times S_h}\frac{B_{\infty }((\varvec{u}_h,p_h),(\varvec{v}_h,q_h))}{\Vert \varvec{v}_h\Vert _{1,h}+ \Vert q_h\Vert }\gtrsim \Vert \varvec{u}_h\Vert _{1,h} + \Vert p_h\Vert . \end{aligned}$$

(3.28)

4 Multigrid method

In this section, we design a multigrid algorithm to solve the discrete system (3.11)–(3.12). We will show that the algorithm is robust with respect to the parameter $\lambda$. Hence, by $p_h=\hbox {div} \varvec{u}_h$ we can also solve the discrete system (3.8) very efficiently.

4.1 Preliminaries

Let us denote by $\{T_k\}_{k=0}^{J}$ the partition on every level and denote the finest partition $T_h=T_J$. The edges (faces) of $T_k$ are denoted by $E_k$. We assume that all the partitions $\{T_k\}_{k=0}^{J}$ are quasi-uniform with characteristic mesh size $h_k$ and $h_k=\gamma h_{k-1}$, $\gamma \in (0,1)$ and $h_0=\mathcal {O}(1)$. We should note that the last term (the penalty term) in the bilinear form $a_h(\cdot ,\cdot )$ depends on the mesh size of the partition.

Thus, for every partition $T_k$ we have discretized the Eq. (2.3) and we need to specify the space $\varvec{V}_h$ on level $k$. A natural choice for $\varvec{V}_h$ on level $k$ is $\varvec{V}_k$ defined as follows:

$$\begin{aligned} \varvec{V}_k=\{\varvec{v} \in H({\text {div}}; \Omega ):\varvec{v}|_K \in \varvec{V}(K),~K \in T_k;~ \varvec{v} \cdot \varvec{n}=0~\hbox {on}~\partial \Omega \}. \end{aligned}$$

Moreover, we denote the pressure space $S_h$ on level $k$ by

$$\begin{aligned} S_k =\left\{ q \in L^2(\Omega ): q|_K \in Q(K),\quad K \in T_k; ~\int _{\Omega }q dx=0\right\} . \end{aligned}$$

Thus, corresponding to the set of refined triangulations $\{T_k\}_{k=0}^J$, we also have a sequence of nested $H({\text {div}},\Omega )$-conforming finite element vector spaces

$$\begin{aligned} \varvec{V}_0\subseteq \varvec{V}_1\subseteq \varvec{V}_2\subseteq \cdots \subseteq \varvec{V}_J\subseteq H({\text {div}},\Omega ). \end{aligned}$$

With every space we associate a bilinear form $a_k(\cdot ,\cdot )$ which discretizes the first term on the left hand side of (2.3) on $\varvec{V}_k$, i.e.,

$$\begin{aligned} a_k(\varvec{u},\varvec{v})= & {} \nonumber \sum _{K \in T_k} \int _K \varepsilon (\varvec{u}) : \varepsilon (\varvec{v}) dx-\sum _{e \in E_k} \int _e \{\varepsilon (\varvec{u})\} \cdot [\varvec{v_t}]ds\\&-\sum _{e \in E_k} \int _e \{\varepsilon (\varvec{v})\} \cdot [\varvec{u_t}] ds+ \sum _{e \in E_k} \int _e \eta h_k^{-1}[\varvec{u}_t ]\cdot [\varvec{v}_t ] ds. \end{aligned}$$

Adding the divergence term then gives the bilinear form used to discretize (2.3) on $\varvec{V}_k$, i.e.,

$$\begin{aligned} A_k(\varvec{u}, \varvec{v})=a_k(\varvec{u}, \varvec{v})+\lambda ({\text {div}}\, \varvec{u}, {\text {div}}\, \varvec{v}), \quad \text{ for } \text{ all }\quad \varvec{u},\varvec{v} \in \varvec{V}_k. \end{aligned}$$

Our goal is to analyze the variable V-cycle and W-cycle multigrid algorithms for the solution of the problem: Given $\varvec{f}\in \varvec{V}_J$, find $\varvec{v}\in \varvec{V}_J$ satisfying

$$\begin{aligned} A_J(\varvec{v},\varvec{\phi })=(\varvec{f},\varvec{\phi }), \quad \text{ for } \text{ all }\quad \varvec{\phi }\in \varvec{V}_J. \end{aligned}$$

(4.1)

To define the algorithm, we need several auxiliary notions. For $k=0,\ldots ,J$, define the operator $\mathbb {A}_k: \varvec{V}_k\rightarrow \varvec{V}_k$ by

$$\begin{aligned} (\mathbb {A}_k\varvec{w},\varvec{\phi })=A_k(\varvec{w},\varvec{\phi }), \quad \text{ for } \text{ all }\quad \varvec{\phi }\in \varvec{V}_k. \end{aligned}$$

The norms on $\varvec{V}_k$ induced by $A_k(\cdot ,\cdot )$ and $a_k(\cdot ,\cdot )$ are denoted by $\Vert \cdot \Vert ^2_{A_k}$, and $\Vert \cdot \Vert ^2_{a_k}$ respectively, i.e.,

$$\begin{aligned} \Vert \varvec{u}\Vert ^2_{A_k}=A_k(\varvec{u},\varvec{u}), \quad \Vert \varvec{u}\Vert ^2_{a_k}=a_k(\varvec{u},\varvec{u}), \quad \text{ for } \text{ all }\quad \varvec{u}\in \varvec{V}_k. \end{aligned}$$

We also need the $L^{2}$-orthogonal projections on $\varvec{V}_k$, and $S_k$, denoted by $\varvec{Q}_k\!:\!\varvec{L}^2(\Omega )\mapsto \varvec{V}_k$ and the operators $Q_k:\varvec{L}^2(\Omega )\mapsto S_k$ and the canonical interpolation $\Pi _k: [H_0^1(\Omega )]^2\mapsto \varvec{V}_k$. According to the notation of the previous section, $\Pi _k$ and $Q_k$ are just a shorthand for $\Pi _{h_k}^{{\text {div}}}$ and $Q_{h_k}$, and we recall that $Q_k{\text {div}}= {\text {div}}\Pi _k$. Further, we introduce the operators $P_{k-1}:~\varvec{V}_k\rightarrow \varvec{V}_{k-1}$ defined by

$$\begin{aligned} A_{k-1}(P_{k-1}\varvec{w},\varvec{\phi })=A_k(\varvec{w},\varvec{\phi }), \quad \text{ for } \text{ all }\quad \varvec{\phi }\in \varvec{V}_{k-1}. \end{aligned}$$

(4.2)

Finally, we denote the norm $\Vert \cdot \Vert _{1,h}$ on the level $k$ as $\Vert \cdot \Vert _{1,k}$.

To define the smoothing process, we require linear operators $R_k:\varvec{V}_k\rightarrow \varvec{V}_k$ for $k=1,\ldots ,J$. These operators may be symmetric or nonsymmetric with respect to the inner product $(\cdot ,\cdot )$. If $R_k$ is nonsymmetric, then we define $R_k^{t}$ to be its adjoint and set

$$\begin{aligned} R_k^{(l)}=\left\{ \begin{array}{l} R_k \quad \hbox {if}\,\,l\,\, \hbox {is odd},\\ R_k^{t}\quad \hbox {if} \,\,l \,\,\hbox {is even}. \end{array} \right. \end{aligned}$$

4.2 Multigrid algorithm

The multigrid operator $\mathbb {B}_k:\varvec{V}_k\rightarrow \varvec{V}_k$ is defined by induction and is given as follows, see, e.g., [15].

Multigrid algorithm. Set $\mathbb {B}_0=\mathbb {A}_0^{-1}$. Assume that $\mathbb {B}_{k-1}$ has been defined and define $\mathbb {B}_k\varvec{g}$ for $\varvec{g}\in \varvec{V}_k$ as follows:

• 1. Set $\varvec{x}^0=0$ and $\varvec{q}^0=0$.

• 2. Define $\varvec{x}^{l}$ for $l=1,\ldots , m(k)$ by

  $$\begin{aligned} \varvec{x}^{l}=\varvec{x}^{l-1}+R_k^{(l+m(k))}(\varvec{g}-\mathbb {A}_k\varvec{x}^{l-1}). \end{aligned}$$

  (4.3)

• 3. Define $\varvec{y}^{m(k)}=\varvec{x}^{m(k)}+ \varvec{q}^p$, where $\varvec{q}^i$ for $i=1,\ldots ,p$ is defined by

  $$\begin{aligned} \varvec{q}^i=\varvec{q}^{i-1}+\mathbb {B}_{k-1}[\varvec{Q}_{k-1}(\varvec{g}-\mathbb {A}_k\varvec{x}^{m(k)})-\mathbb {A}_{k-1}\varvec{q}^{i-1}]. \end{aligned}$$

  (4.4)

• 4. Define $\varvec{y}^l$ for $l=m(k)+1,\ldots , 2m(k)$ by

  $$\begin{aligned} \varvec{y}^l=\varvec{y}^{l-1}+R_k^{(l+m(k))}(\varvec{g}-\mathbb {A}_k\varvec{y}^{l-1}). \end{aligned}$$

• 5. Set $\mathbb {B}_k\varvec{g}=\varvec{y}^{2m(k)}$.

In this algorithm, $m(k)$ is a positive integer which may vary from level to level and determines the number of smoothing iterations on that level, $p$ is a positive integer. We shall study the cases $p=1$ and $p=2$, which correspond respectively to the symmetric $\mathcal {V}$ and $\mathcal {W}$ multigrid cycles.

4.3 Multigrid convergence

Set $K_k=I-R_k\mathbb {A}_k$, then $K_k^{*}=I-R_k^t\mathbb {A}_k$ is the adjoint with respect to $A_k(\cdot ,\cdot )$. Further, set

$$\begin{aligned} \widetilde{K}_k^{(m)}=\left\{ \begin{array}{ll} (K_k^*K_k)^{m/2} &{}\quad \hbox {if}\,\,l\,\, \hbox {is odd},\\ (K_k^*K_k)^{(m-1)/2}K_k^*&{}\quad \hbox {if} \,\,l \,\,\hbox {is even}, \end{array} \right. \end{aligned}$$

and denote by $(\widetilde{K}_k^{(m)})^*$ the adjoint of $\widetilde{K}_k^{(m)}$ with respect to $A_k(\cdot ,\cdot )$.

For convergence estimates, we shall make a priori assumptions. First we make the following basic assumption:

• (A0) The spectrum of $K_k^{*}K_k$ is in the interval $[0,1)$.

In order to analyze the approximation property and the smoothing property of the multigrid algorithm, we need to define a norm on level $k$ as follows (cf. [10]),

$$\begin{aligned} \Vert \varvec{u}\Vert _{k,0}^2 := \Vert \varvec{u}\Vert ^2+\lambda h_k^2\Vert {\text {div}}\, \varvec{u}\Vert ^2 +\lambda ^2h_k^{2} \Vert Q_{k-1}{\text {div}}\, \varvec{u}\Vert ^2, \quad \varvec{u}\in \varvec{V}_k. \end{aligned}$$

(4.5)

The second assumption is an approximation assumption in $\Vert \cdot \Vert _{k,0}$ norm (known as approximation and regularity assumption in [15]),

• (A1)   $\Vert (I-P_{k-1})\varvec{u}\Vert _{k,0}\lesssim h_k \Vert \varvec{u}\Vert _{A_{k}}$, for all $\varvec{u}\in \varvec{V}_k$.

The third assumption is a requirement on the smoother,

• (A2)   $\Vert (\widetilde{K}_k^{(m)})^*\varvec{u}\Vert _{A_{k}}\lesssim m^{-1/4} h_k^{-1}\Vert \varvec{u}\Vert _{k,0}$, for all $\varvec{u}\in \varvec{V}_k$.

Next Lemma is an analogue of a result given in Bramble, Pasciak, Xu [15, Lemma 4.1].

Lemma 2

Assume that (A0), (A1) and (A2) hold and let $\widetilde{\varvec{u}}=\widetilde{K}_k^{(m)}\varvec{u}$. Then we have the estimate

$$\begin{aligned} -A_k((I-P_{k-1})\widetilde{\varvec{u}}, \widetilde{\varvec{u}})\lesssim m^{-1/4}\Vert \varvec{u}\Vert _{A_k}^2,\quad \text{ for } \text{ all }\quad \varvec{u} \in \varvec{V}_k. \end{aligned}$$

Proof

By the Cauchy–Schwarz inequality and assumption (A2), we have

$$\begin{aligned} -A_k((I-P_{k-1})\widetilde{\varvec{u}}, \widetilde{\varvec{u}})= & {} -A_k((I-P_{k-1})\widetilde{K}_k^{(m)}{\varvec{u}}, \widetilde{K}_k^{(m)}{\varvec{u}})\\= & {} -A_k((\widetilde{K}_k^{(m)})^*(I-P_{k-1})\widetilde{K}_k^{(m)}{\varvec{u}}, {\varvec{u}})\\\le & {} \Vert (\widetilde{K}_k^{(m)})^*(I-P_{k-1})\widetilde{\varvec{u}}\Vert _{A_k}\Vert \varvec{u}\Vert _{A_k}\\\lesssim & {} m^{-1/4}h_k^{-1} \Vert (I-P_{k-1})\widetilde{\varvec{u}} \Vert _{k,0}\Vert \varvec{u}\Vert _{A_k}. \end{aligned}$$

Next, by assumptions (A1) and (A0) (applied in that order) we have

$$\begin{aligned} -A_k((I-P_{k-1})\widetilde{\varvec{u}}, \widetilde{\varvec{u}})\lesssim & {} m^{-1/4} h_k^{-1}\Vert (I-P_{k-1})\widetilde{\varvec{u}} \Vert _{k,0}\Vert \varvec{u}\Vert _{A_k}\\\lesssim & {} m^{-1/4} \Vert \widetilde{\varvec{u}}\Vert _{A_k}\Vert \varvec{u}\Vert _{A_k} \lesssim m^{-1/4} \Vert \varvec{u}\Vert ^2_{A_k}. \end{aligned}$$

The estimate in Lemma 2 provides the prerequisite to apply the general theory in [15]. Indeed, according to [15], assumptions (A0), (A1) and (A2) and Lemma 2 are sufficient to show spectral equivalence for the variable V-cycle multigrid preconditioner (Theorem 2) and uniform convergence of the W-cycle multigrid method (Theorem 3). The first result is just a restatement of [15, Theorem 6] with full regularity.

Theorem 2

(Theorem 6 in [15]) Assume that (A0), (A1) and (A2) hold and define $\mathbb {B}_j$ in Algorithm 4.2 with $p=1$. Further assume that the number of smoothing steps $m(k)$ satisfies $\beta _0 m(k)\le m(k-1)\le \beta _1 m(k)$ with $\beta _0\ge 1$ and $\beta _1> 1$ independent of $k$. Then the following spectral equivalence holds

$$\begin{aligned} \eta _0A_k(\varvec{u},\varvec{u})\le A_k(\mathbb {B}_k\mathbb {A}_k\varvec{u},\varvec{u})\le \eta _1A_k(\varvec{u},\varvec{u}) ~~\hbox {for all}~~ \varvec{u}\in \varvec{V}_k \end{aligned}$$

(4.6)

with constants $\eta _0$ and $\eta _1$ such that

$$\begin{aligned} \eta _0\ge \frac{m(k)^{\alpha }}{M+m(k)^{\alpha }} \quad \hbox {and}\quad \eta _1\le \frac{M+m(k)^{\alpha }}{m(k)^{\alpha }}, \end{aligned}$$

where $M$ is independent of $\lambda$ and $h$, and $\alpha$ denotes the regularity index.

The convergence of the $W$-cycle is also obtained via the analysis in [15].

Theorem 3

(Theorem 4 in [15]) Assume that (A0), (A1) and (A2) hold and that the number of smoothing steps $m(k)=m$ is constant for all $k$. Then, for sufficiently large $m$, $\mathbb {B}_k$ defined via the W-cycle algorithm satisfies

$$\begin{aligned} |A_k((I-\mathbb {B}_k\mathbb {A}_k)\varvec{u},\varvec{u})|\le \frac{M}{M+m^{\alpha }} \Vert \varvec{u}\Vert ^2_{A_k}\quad \text{ for } \text{ all }\quad \varvec{u} \in \varvec{V}_k \end{aligned}$$

with $M$ independent of $\lambda$ and $h$, and $\alpha$ denoting the regularity index.

We remark here that modifying assumption (A1) one can prove the results above for the case of less than full elliptic regularity. For details we refer to Bramble, Pasciak and Xu [15].

As we have seen, the estimates in Theorems 2, 3 are valid if assumptions (A0), (A1) and (A2) are verified. In the next subsections we show that these assumptions hold in our case.

4.4 Approximation property

In this subsection, we verify (A1). One of the difficulties in the analysis is that the bilinear forms $A_k(\cdot ,\cdot ), k=1,\ldots ,J$ are not nested. We now prove a simple relation between $A_{k}(\cdot ,\cdot )$ and $A_{k-1}(\cdot ,\cdot )$.

Lemma 3

If $h_k=\gamma h_{k-1}$, $\gamma \in (0,1)$, then

$$\begin{aligned} \Vert \varvec{u} \Vert ^2_{A_{k-1}}\le \Vert \varvec{u}\Vert _{A_k}^2\lesssim \Vert \varvec{u} \Vert ^2_{A_{k-1}}, \quad \text{ for } \text{ all }\quad \varvec{u} \in \varvec{V}_{k-1}. \end{aligned}$$

(4.7)

Proof

Let $\varvec{u}\in \varvec{V}_{k-1}$. Observe that $[\varvec{u}_t ]_e=0$ for edges (faces) $e\in E_{k}$ which are interior to the elements in $T_{k-1}$, because $\varvec{u}$ is a continuous, in fact a polynomial, function in each element from $T_{k-1}$. Hence,

$$\begin{aligned} \sum _{e \in E_{k-1}} \int _e \eta \gamma ^{-1}h_{k-1}^{-1}|[\varvec{u}_t]|^2 ds =\sum _{e \in E_{k}} \int _e \eta h_{k}^{-1}|[\varvec{u}_t ]|^2 ds, \quad \text{ for } \text{ all }\quad \varvec{u} \in \varvec{V}_{k-1} \end{aligned}$$

and we have

$$\begin{aligned} A_k(\varvec{u},\varvec{u})= & {} A_{k-1}(\varvec{u},\varvec{u}) +\sum _{e \in E_k} \int _e \eta h_k^{-1}|[\varvec{u}_t ]|^2 ds -\sum _{e \in E_{k-1}} \int _e \eta h_{k-1}^{-1}|[\varvec{u}_t ]|^2 ds\\= & {} A_{k-1}(\varvec{u},\varvec{u}) +(\gamma ^{-1}-1)\sum _{e \in E_{k-1}} \int _e \eta h_{k-1}^{-1} |[\varvec{u}_t ]|^2ds. \end{aligned}$$

The estimates in (4.7) then easily follow from the identity above.

Remark 5

From Lemma 3, for any given $\varvec{u}\in \varvec{V}_k$, we also have

$$\begin{aligned} \Vert P_{k-1}\varvec{u}\Vert ^2_{A_{k-1}}\le & {} \Vert P_{k-1}\varvec{u}\Vert ^2_{A_k}=A_{k}(\varvec{u}, P_{k-1}\varvec{u}) \le \Vert \varvec{u}\Vert _{A_k}\Vert P_{k-1}\varvec{u}\Vert _{A_k}\\\lesssim & {} \Vert \varvec{u}\Vert _{A_k}\Vert P_{k-1}\varvec{u}\Vert _{A_{k-1}}, \end{aligned}$$

namely,

$$\begin{aligned} \Vert P_{k-1}\varvec{u}\Vert _{A_{k-1}} \lesssim \Vert \varvec{u}\Vert _{A_k}. \end{aligned}$$

(4.8)

We now introduce the dual problem (which is the same as the primal one in (2.3) because the bilinear form is symmetric): Find $\varvec{w}\in H_0^1(\Omega )^d$ such that

$$\begin{aligned} (\varepsilon ( \varvec{v}):\varepsilon (\varvec{w}))+\lambda ({\text {div}}\, \varvec{v},{\text {div}}\, \varvec{w})=(\varvec{g},\varvec{v}),\quad \text{ for } \text{ all } \quad \varvec{v}\in H^1_0(\Omega )^d. \end{aligned}$$

(4.9)

From the definitions of the bilinear forms $A_{k-1}(\cdot ,\cdot )$ and $A_{k}(\cdot ,\cdot )$ we have the following simple identity for the solution $\varvec{w}$ of (4.9):

$$\begin{aligned} A_k(\varvec{v}, \varvec{w})=A_{k-1}(\varvec{v}, \varvec{w}),~ \text{ for } \text{ all }\quad \varvec{v} \in \varvec{V}_{k-1}. \end{aligned}$$

(4.10)

This follows immediately, since both $A_{k-1}(\cdot ,\cdot )$ and $A_{k}(\cdot ,\cdot )$ are consistent. Indeed, for any $\varvec{v} \in \varvec{V}_{k-1}\subset \varvec{V}_k$ we have $A_{k}(\varvec{v}, \varvec{w})=(\varvec{g},\varvec{v}) = A_{k-1}(\varvec{v}, \varvec{w})$, which proves (4.10).

The next lemma provides estimates on the interpolation error.

Lemma 4

Let $\varvec{w}\in H^{l+1}(\Omega )^d$, $l=0,1$, and $\Pi _{k-1}\varvec{w}$ be the interpolant of $\varvec{w}$ in $\varvec{V}_{k-1}$, then

$$\begin{aligned}&\Vert \varvec{w}-\Pi _{k-1}\varvec{w}\Vert ^2_{A_{k-1}}\lesssim h_{k-1}^{2l}( |\varvec{w}|_{l+1}^2+\lambda |{\text {div}}\, \varvec{w}|_l^2 ),\nonumber \\&\quad \Vert \varvec{w}-\Pi _{k-1}\varvec{w}\Vert ^2_{A_{k}}\lesssim h_{k-1}^{2l}( |\varvec{w}|_{l+1}^2+\lambda |{\text {div}}\, \varvec{w}|_l^2 ). \end{aligned}$$

(4.11)

Proof

By the continuity of $a_k(\cdot ,\cdot )$, the trace theorem and the interpolation error estimate (3.3), we have

$$\begin{aligned} \Vert \varvec{w}-\Pi _{k-1}\varvec{w}\Vert ^2_{a_{k-1}}\lesssim \Vert \varvec{w}-\Pi _{k-1}\varvec{w}\Vert _{DG}^2\lesssim h_{k-1}^{2l} |\varvec{w}|_{l+1}^2. \end{aligned}$$

Noting ${\text {div}}\Pi _{k-1}\varvec{w}=Q_{k-1}{\text {div}}\, \varvec{w}$, by the standard approximation error estimate of the projection $Q_{k-1}$, we have

$$\begin{aligned} \Vert {\text {div}}(\varvec{w}-\Pi _{k-1}\varvec{w})\Vert ^2&=\Vert {\text {div}}\, \varvec{w}-Q_{k-1}{\text {div}}\, \varvec{w}\Vert ^2\lesssim h_{k-1}^{2l}|{\text {div}}\, \varvec{w}|_l^2. \end{aligned}$$

Combining the above two inequalities and noting the definition of the norm $\Vert \cdot \Vert _{A_{k-1}}$, we get the first inequality in (4.11). The proof of the second inequality in (4.11) is carried out in a similar fashion.

We now prove a two-level estimate in $L^2$.

Theorem 4

For all $\varvec{u} \in \varvec{V}_k$ the following estimate holds

$$\begin{aligned} \Vert (I- P_{k-1})\varvec{u}\Vert \lesssim h_k \Vert \varvec{u}\Vert _{A_k}. \end{aligned}$$

(4.12)

Proof

We estimate $\Vert (I- P_{k-1})\varvec{u}\Vert$ using a standard duality argument. Let $\varvec{w}\in H_0^1(\Omega )^d$ be the solution of the dual problem (4.9) with $\varvec{g}=\varvec{u}-P_{k-1}\varvec{u}$. Since, $A_k(\cdot ,\cdot )$ is a consistent bilinear form, we have

$$\begin{aligned} A_k(\varvec{w},\varvec{v})= (\varvec{u}- P_{k-1}\varvec{u},\varvec{v}),\quad \text{ for } \text{ all }\quad ~\varvec{v}\in \varvec{V}_k. \end{aligned}$$

Now let $\varvec{v}=\varvec{u}- P_{k-1}\varvec{u}$ and $\Pi _{k-1}\varvec{w}$ be the interpolant of $\varvec{w}$ in $\varvec{V}_{k-1}$. Noting that $A_k(\cdot ,\cdot ),k=1,\ldots ,J$ are symmetric, (4.10) and the definition of the operator $P_{k-1}$, we have

$$\begin{aligned} \Vert \varvec{u}- P_{k-1}\varvec{u}\Vert ^2= & {} A_k(\varvec{w},\varvec{u}- P_{k-1}\varvec{u})\nonumber \\= & {} A_k(\varvec{u},\varvec{w})-A_k(\varvec{w},P_{k-1}\varvec{u})=A_k(\varvec{u},\varvec{w})-A_{k-1}(\varvec{w},P_{k-1}\varvec{u})\nonumber \\= & {} A_k(\varvec{u},\varvec{w})-A_{k-1}(P_{k-1}\varvec{u},\varvec{w}-\Pi _{k-1}\varvec{w})-A_{k-1}(P_{k-1}\varvec{u},\Pi _{k-1}\varvec{w})\nonumber \\= & {} A_k(\varvec{u},\varvec{w})-A_{k-1}(P_{k-1}\varvec{u},\varvec{w}-\Pi _{k-1}\varvec{w})-A_{k}(\varvec{u},\Pi _{k-1}\varvec{w})\nonumber \\= & {} A_k(\varvec{u},\varvec{w}-\Pi _{k-1}\varvec{w})-A_{k-1}(P_{k-1}\varvec{u},\varvec{w}-\Pi _{k-1}\varvec{w}). \end{aligned}$$

(4.13)

Applying the Cauchy–Schwarz inequality to the right hand side of the identity above and using the approximation estimates given in (4.11), the inequality (4.8) and the regularity estimate (2.4) then lead to

$$\begin{aligned} \Vert \varvec{u}- P_{k-1}\varvec{u}\Vert ^2\le & {} \Vert \varvec{u}\Vert _{A_k}\Vert \varvec{w}-\Pi _{k-1}\varvec{w}\Vert _{A_k} +\Vert P_{k-1}\varvec{u}\Vert _{A_{k-1}}\Vert \varvec{w}-\Pi _{k-1}\varvec{w}\Vert _{A_{k-1}}\\\lesssim & {} h_{k-1}(\Vert \varvec{u}\Vert _{A_k} +\Vert P_{k-1}\varvec{u}\Vert _{A_{k-1}})( |\varvec{w}|_2^2+\lambda |{\text {div}}\, \varvec{w}|_1^2 )^{1/2} \\\lesssim & {} h_{k-1}\Vert \varvec{u}\Vert _{A_k} ( |\varvec{w}|_2^2+\lambda |{\text {div}}\, \varvec{w}|_1^2 )^{1/2} \lesssim h_{k-1}\Vert \varvec{u}\Vert _{A_k}\Vert \varvec{u}- P_{k-1}\varvec{u}\Vert \end{aligned}$$

which completes the proof.

The next two Lemmas verify the approximation property (A1).

Lemma 5

For all $\varvec{u} \in \varvec{V}_k$ we have the estimate

$$\begin{aligned} \lambda \Vert Q_{k-1} {\text {div}}(\varvec{u} -P_{k-1}\varvec{u})\Vert \lesssim \Vert \varvec{u}\Vert _{A_k}. \end{aligned}$$

(4.14)

Proof

For any given $\varvec{u} \in \varvec{V}_k$ and any $\varvec{v} \in \varvec{V}_{k-1}$, from the definition of $P_{k-1}$ in (4.2), we have

$$\begin{aligned} a_{k-1}(P_{k-1}\varvec{u}, \varvec{v})+ \lambda ({\text {div}}(P_{k-1}\varvec{u}), {\text {div}}\varvec{v} )= a_{k}(\varvec{u}, \varvec{v})+\lambda ({\text {div}}\varvec{u}, {\text {div}}\varvec{v}), \end{aligned}$$

or, equivalently,

$$\begin{aligned}&\lambda (Q_{k} {\text {div}}\varvec{u}, Q_{k-1}{\text {div}}\varvec{v} ) -\lambda (Q_{k-1} {\text {div}}(P_{k-1}\varvec{u}), Q_{k-1}{\text {div}}\varvec{v})\nonumber \\&\quad =a_{k}(\varvec{u}, \varvec{v})-a_{k-1}(P_{k-1}\varvec{u}, \varvec{v}). \end{aligned}$$

By the properties of the $L^2$-projections on $S_k$ and $S_{k-1}$ and the fact that $S_{k-1}\subset S_k$ we have $Q_{k-1}Q_{k}=Q_{k-1}$ and $Q^2_{k-1}=Q_{k-1}$. Therefore,

$$\begin{aligned} (Q_{k-1} {\text {div}}(\varvec{u} -P_{k-1}\varvec{u}), {\text {div}}\varvec{v} ) =\lambda ^{-1}(a_{k}(\varvec{u}, \varvec{v})-a_{k-1}(P_{k-1}\varvec{u}, \varvec{v})). \end{aligned}$$

(4.15)

Note that the continuity of the bilinear form $a_k(\cdot ,\cdot )$ implies that $\Vert \varvec{v}\Vert _{a_k}\lesssim \Vert \varvec{v}\Vert _{1,k-1}$ and $\Vert \varvec{v}\Vert _{a_{k-1}}\lesssim \Vert \varvec{v}\Vert _{1,k-1}$. Using now the trivial bound $a_{k-1}(\varvec{w},\varvec{w})\le A_{k-1}(\varvec{w},\varvec{w})$, which holds for all $\varvec{w}\in \varvec{V}_{k-1}$, and the inequality (4.8) for the right hand side of (4.15) we obtain

$$\begin{aligned} a_{k}(\varvec{u}, \varvec{v})-a_{k-1}(P_{k-1}\varvec{u}, \varvec{v})\lesssim & {} (\Vert \varvec{u}\Vert _{a_k}+\Vert P_{k-1}\varvec{u}\Vert _{a_{k-1}})\Vert \varvec{v}\Vert _{1,k-1}\\\lesssim & {} \Vert \varvec{u}\Vert _{A_k}\Vert \varvec{v}\Vert _{1,k-1}. \end{aligned}$$

The inf-sup condition (3.16) and the inequality above then show that

$$\begin{aligned} \Vert Q_{k-1} {\text {div}}(\varvec{u}-P_{k-1}\varvec{u})\Vert\lesssim & {} \sup _{\varvec{v}\in \varvec{M}_{k-1}}\frac{(Q_{k-1} {\text {div}}(\varvec{u}-P_{k-1}\varvec{u}),{\text {div}}\, \varvec{v})}{\Vert \varvec{v}\Vert _{1,k-1}}\\= & {} \lambda ^{-1} \sup _{\varvec{v}\in \varvec{V}_{k-1}}\frac{a_{k}(\varvec{u}, \varvec{v})- a_{k-1}(P_{k-1}\varvec{u}, \varvec{v})}{\Vert \varvec{v}\Vert _{1,k-1}}\\\lesssim & {} \lambda ^{-1}\Vert \varvec{u}\Vert _{A_k}. \end{aligned}$$

The proof is complete.

The next lemma estimates the last term in the definition of $\Vert \varvec{u} -P_{k-1}\varvec{u}\Vert _{k,0}$.

Lemma 6

If $\lambda \gtrsim 1$, then the following estimate holds for all $\varvec{u} \in \varvec{V}_k$,

$$\begin{aligned} \lambda \Vert {\text {div}}(\varvec{u}-P_{k-1}\varvec{u})\Vert ^2\lesssim \Vert \varvec{u}\Vert _{A_k}^2. \end{aligned}$$

(4.16)

Proof

We observe that $Q_{k-1}{\text {div}}P_{k-1} \varvec{u} = {\text {div}}P_{k-1} \varvec{u}$ and then, by the triangle inequality and Lemma 5, we have

$$\begin{aligned} \Vert {\text {div}}(\varvec{u}-P_{k-1}\varvec{u})\Vert\le & {} \Vert {\text {div}}\, \varvec{u}-Q_{k-1} {\text {div}}\varvec{u}\Vert +\Vert Q_{k-1} {\text {div}}(\varvec{u} -P_{k-1}\varvec{u})\Vert \\\lesssim & {} \Vert {\text {div}}\, \varvec{u}\Vert +\lambda ^{-1} \Vert \varvec{u}\Vert _{A_k}. \end{aligned}$$

The proof is completed by first squaring both sides, then multiplying by $\lambda$ and finally using the inequality $(a+b)^2\le 2(a^2+b^2)$ and the fact that $\lambda \gtrsim 1$. We have,

$$\begin{aligned} \lambda \Vert {\text {div}}(\varvec{u}-P_{k-1}\varvec{u})\Vert ^2\lesssim & {} \lambda \Vert {\text {div}}\varvec{u}\Vert ^2+\lambda ^{-1} \Vert \varvec{u}\Vert _{A_k}^2 \lesssim \Vert \varvec{u}\Vert ^2_{A_k}. \end{aligned}$$

Combining the $L^2$-estimate (4.12), and the estimates given in Lemma 5, and Lemma 6, we obtain the following theorem, which verifies (A1).

Theorem 5

The following approximation estimate holds for $\lambda \gtrsim 1$ and for all $\varvec{u}\in \varvec{V}_k$.

$$\begin{aligned} \Vert (I-P_{k-1})\varvec{u}\Vert _{k,0}\lesssim h_k\Vert \varvec{u}\Vert _{A_k}. \end{aligned}$$

4.5 Smoothing property

In this subsection, we verify the smoothing property (A2). We only consider the 3-dimensional case because the 2-dimensional case is similar and simpler. We denote by $\mathcal {V}_{k}$, and $\mathcal {E}_k$ the sets of vertices and edges, respectively, of the partition $T_k$. For $\nu \in \mathcal {V}_k\cup \mathcal {E}_k$ we define

$$\begin{aligned} T_k^{\nu }=\{K\in T_k:\nu \subset K\},~~\bar{\Omega }_k^{\nu }=\cup _{ K \in T_k^{\nu }}\bar{K},~~\Omega _k^{\nu }=\hbox {interior}(~\bar{\Omega }_k^{\nu }). \end{aligned}$$

Thus $\Omega _k^{\nu }$ is the subdomain of $\Omega$ formed by the patch of elements meeting at $\nu$, and $T_k^{\nu }$ is the restriction of the mesh partition $T_k$ to $\Omega _k^{\nu }$.

We now consider the decomposition of these spaces as sums of spaces supported in small patches of elements. Define

$$\begin{aligned} \varvec{V}_k^{\nu }=\left\{ \varvec{r}\in \varvec{V}_k: \hbox {supp}\,\varvec{r} \subset \bar{\Omega }_k^{\nu }\right\} , ~\nu \in \mathcal {V}_k\cup \mathcal {E}_k. \end{aligned}$$

Then

$$\begin{aligned} \varvec{V}_k=\sum _{i\in \mathcal {V}_k} \varvec{V}_k^{i}=\sum _{e\in \mathcal {E}_k} \varvec{V}_k^{e}. \end{aligned}$$

For each of these decompositions there is a corresponding estimate on the sum of the squares of the $L^2$-norms of the summands. For example, we can decompose an arbitrary element $\varvec{u}\in \varvec{V}_k$ as $\varvec{u} = \sum _{i\in \mathcal {V}_k} \varvec{u}^{i}$ with $\varvec{u}^i\in \varvec{V}^i_{k}$ so that the estimate

$$\begin{aligned} \sum _{i\in \mathcal {V}_k} \Vert \varvec{u}^{i}\Vert ^2\lesssim \Vert \varvec{u}\Vert ^2 \end{aligned}$$

(4.17)

holds with a constant depending only on the shape regularity of the mesh.

Since the kernel basis functions of the operator ${\text {div}}$ are captured by the above subspaces $\varvec{V}^i_{k}$, we must use a block damped Jacobi smoother or a block Gauss–Seidel smoother where the blocks correspond to one of the above $L^2$-decompositions in order to preserve the structure of the kernel. For example, we can use a vertex block damped Jacobi smoother, a vertex block Gauss–Seidel smoother, an edge block damped Jacobi smoother, or an edge block Gauss–Seidel smoother.

Remark 6

We should point out that the block Gauss–Seidel smoother satisfies the assumption (A0). But for the block damped Jacobi smoother, we need to choose the damping parameter such that the basic assumption (A0) is satisfied. A damped Richardson smoother $I-\tau A_k$ would need a damping parameter $\tau$ proportional to $\lambda ^{-1}$. Thus the components of the error in the kernel of $A_k$ would be smoothed out very slow as $\lambda$ is large. We should also point out that in the 2-dimensional case, we can only use vertex block smoothers.

In the rest of this subsection, we only consider the vertex block damped Jacobi smoother since the others are similar, and define the operator $P_{k,i}: \varvec{V}_k \rightarrow \varvec{V}_k^{i} ~ \hbox {for}~i\in \mathcal {V}_k$ by

$$\begin{aligned} A_k(P_{k,i}\varvec{u},\varvec{v}_i)=A_k(\varvec{u},\varvec{v}_i)\,\, \text{ for } \text{ all }\quad \varvec{u} \in \varvec{V}_k, \varvec{v}_i\in \varvec{V}_k^{i}. \end{aligned}$$

We use exact local solves and hence the block damped Jacobi smoother $R_k$ is given by $R_k=\tau \sum _{i\in \mathcal {V}_k}P_{k,i}A_k^{-1} :=\tau D_k^{-1}$, where $\tau$ is the damping parameter such that (A0) is satisfied. In this case, $K_k^*=K_k$ and $\widetilde{K}_k^{(m)}=K_k^{m}$. By the assumption (A0), the estimate

$$\begin{aligned} \Vert K_k^{m}\varvec{u}\Vert ^2_{A_k}=(D_k^{-1}A_kK_k^{2m}\varvec{u}, \varvec{u})_{D_k}\lesssim m^{-1}\Vert \varvec{u}\Vert _{D_k}^2 \end{aligned}$$

(4.18)

is well known in multigrid theory (see e.g. Hackbusch [14]).

By additive Schwarz techniques [29, 30] the induced norm $\Vert \varvec{u}\Vert _{D_k}=(D_k\varvec{u},\varvec{u})^{1/2}$ can be written as

$$\begin{aligned} \Vert \varvec{u}\Vert _{D_k}^2=\inf _{\varvec{u}=\sum \varvec{u}_k^i} \sum _{i\in \mathcal {V}_k} \Vert \varvec{u}_k^i\Vert ^2_{A_k}. \end{aligned}$$

(4.19)

Remark 7

If the estimate $\Vert \varvec{u}\Vert _{D_k} \lesssim h_k^{-1}\Vert \varvec{u}\Vert _{k,0}$ would be true, the assumption (A2) would be proved. Unfortunately, the proof of Lemma 11 suggests that it is not true.

On the other hand, choosing $\tau$ sufficiently small it is obvious that $\Vert K_k^{m}\varvec{u}\Vert _{A_k}\le \Vert \varvec{u}\Vert _{A_k}$ (the assumption (A0) holds). Then an interpolation between this estimate and the estimate (4.18) gives

$$\begin{aligned} \Vert K_k^{m}\varvec{u}\Vert _{A_k}\lesssim m^{-1/4} \Vert \varvec{u}\Vert _{[D_k,A_k]}, \end{aligned}$$

where $\Vert \varvec{u}\Vert _{[D_k,A_k]}$ is the interpolation norm between $\Vert \cdot \Vert _{D_k}$ and $\Vert \cdot \Vert _{A_k}$ with parameter $1/2$. Thus, one way to verify assumption (A2), is to show that

$$\begin{aligned} \Vert \varvec{u}\Vert _{[D_k,A_k]}\lesssim h_k^{-1}\Vert \varvec{u}\Vert _{k,0}, \end{aligned}$$

(4.20)

and the rest of this section is devoted to this.

4.6 An a priori estimate and a stable decomposition

In this subsection, we first prove an a priori estimate on the $L_2$ norm of the solution of a discrete problem on level $k$. Then using the a priori estimate, we can prove the decomposition introduced in [10] is stable.

We consider the finite element spaces on level $k$ introduced earlier: $\varvec{V}_k\subset H({\text {div}};\Omega )$ and $S_k\subset L^2_0(\Omega )$. Let $\varvec{w}_1\in \varvec{V}_k$ and $\varvec{w}_2\in \varvec{V}_k$ be given and let $\widetilde{\varvec{u}}\in \varvec{V}_k, \widetilde{p}\in S_k$ solve the discrete problem

$$\begin{aligned}&a_k(\widetilde{\varvec{u}}, \varvec{v}) - ({\text {div}}\, \varvec{v},\widetilde{p}) = a_k(\varvec{w}_1, \varvec{v}), \quad \text{ for } \text{ all } \quad \varvec{v} \in \varvec{V}_k,\nonumber \\&\quad ({\text {div}}\widetilde{\varvec{u}}, q) = ({\text {div}}{\varvec{w}}_2, q),\quad \text{ for } \text{ all } \quad q \in S_k. \end{aligned}$$

(4.21)

We note that the inf-sup condition given in (3.28) implies that

$$\begin{aligned} \Vert \widetilde{\varvec{u}}\Vert _{1,k} + \Vert \widetilde{p} \Vert\lesssim & {} \sup _{(\varvec{v},q)\in \varvec{V}_k\times S_k} \frac{a_k(\widetilde{\varvec{u}},\varvec{v}) - ({\text {div}}\varvec{v},\widetilde{p})-({\text {div}}\widetilde{\varvec{u}},q) }{\Vert \varvec{v}\Vert _{1,k} +\Vert q\Vert }\nonumber \\= & {} \sup _{(\varvec{v},q)\in \varvec{V}_k\times S_k} \frac{a_k(\varvec{w}_1,\varvec{v}) -({\text {div}}\, \varvec{w}_2,q) }{\Vert \varvec{v}\Vert _{1,k} +\Vert q\Vert }\nonumber \\\lesssim & {} \Vert \varvec{w}_1\Vert _{1,k}+\Vert {\text {div}}\, \varvec{w}_2\Vert . \end{aligned}$$

(4.22)

Lemma 7

For the solution of (4.21) we have the following estimate:

$$\begin{aligned} \Vert \widetilde{\varvec{u}}\Vert \lesssim \Vert \varvec{w}_1\Vert + \Vert {\text {div}}{\varvec{w}}_2\Vert _{-1}. \end{aligned}$$

(4.23)

Proof

We consider the following dual problem: Find $\varvec{\phi }\in (H_{0}^1(\Omega ))^d$ and $\theta \in L_0^2(\Omega )$ such that

$$\begin{aligned}&a(\varvec{v}, \varvec{\phi }) - ({\text {div}}\, \varvec{v},\theta ) = (\widetilde{\varvec{u}}, \varvec{v}), \quad \hbox {for all} \quad \varvec{v} \in (H_0^1(\Omega ))^d,\nonumber \\&\quad ({\text {div}}\, \varvec{\phi }, q) = 0, \quad \hbox {for all} \quad q \in S_k. \end{aligned}$$

(4.24)

Recall that ${\text {div}}\varvec{\phi } =0$ and hence $({\text {div}}\Pi _k\varvec{\phi },\widetilde{p}) =0$. From Eq. (4.21) we then have

$$\begin{aligned} 0= & {} a_k(\varvec{w}_1, \Pi _k\varvec{\phi }) - a_k(\widetilde{\varvec{u}}, \Pi _k\varvec{\phi }) + ({\text {div}}\Pi _k\varvec{\phi },\widetilde{p}) \nonumber \\= & {} a_k(\varvec{w}_1,\varvec{\phi }) - a_k(\varvec{w}_1, \varvec{\phi }-\Pi _k \varvec{\phi }) - a_k(\widetilde{\varvec{u}}, \Pi _k\varvec{\phi }). \end{aligned}$$

(4.25)

Observing that $a(\varvec{\phi },\varvec{v}) = a_k(\varvec{\phi },\varvec{v})$ for all $\varvec{v}\in \varvec{V}_k$, from (4.24) and (4.25) we obtain

$$\begin{aligned} \Vert \widetilde{\varvec{u}}\Vert ^2= & {} a_k(\varvec{\phi },\widetilde{\varvec{u}}) - ({\text {div}}\widetilde{\varvec{u}},\theta )\nonumber \\&+ a_k(\varvec{w}_1,\varvec{\phi }) - a_k(\varvec{w}_1, \varvec{\phi }-\Pi _k \varvec{\phi }) - a_k(\widetilde{\varvec{u}}, \Pi _k\varvec{\phi }). \end{aligned}$$

(4.26)

Combining the first and the last term, using the triangle inequality and the continuity of $a_h(\cdot ,\cdot )$ then shows that

$$\begin{aligned} \Vert \widetilde{\varvec{u}}\Vert ^2\le & {} |({\text {div}}\widetilde{\varvec{u}},\theta )| + |a_k(\varvec{w}_1,\varvec{\phi })| \\&+ |a_k(\varvec{w}_1, \varvec{\phi }-\Pi _k \varvec{\phi })| + |a_k(\widetilde{\varvec{u}}, \varvec{\phi } - \Pi _k\varvec{\phi })|\\\lesssim & {} |({\text {div}}\widetilde{\varvec{u}},\theta )| + |a_k(\varvec{w}_1,\varvec{\phi })| + (\Vert \varvec{w}_1\Vert _{1,k}+\Vert \widetilde{\varvec{u}}\Vert _{1,k})\Vert \varvec{\phi } - \Pi _k\varvec{\phi }\Vert _{1,k}. \end{aligned}$$

As we have that ${\text {div}}\widetilde{\varvec{u}}={\text {div}}\, \varvec{w}_2$ for the first term on the right side we get

$$\begin{aligned} |({\text {div}}\widetilde{\varvec{u}},\theta )| = |({\text {div}}\, \varvec{w}_2,\theta )| \le \Vert \theta \Vert _1 \sup _{\chi \in H^1}\frac{({\text {div}}\, \varvec{w}_2,\chi )}{\Vert \chi \Vert _1} =\Vert {\text {div}}\, \varvec{w}_2\Vert _{-1}\Vert \theta \Vert _1. \end{aligned}$$

For the second term, by the regularity estimate (2.4) we have that $\varvec{\phi }\in (H^2(\Omega ))^d$, and, thus, $\varvec{\phi }$ is continuous and $[\varvec{\phi }]=0$. Now, integrating by parts and combining the interface terms from neighboring elements shows that

$$\begin{aligned} a_k(\varvec{\phi },\varvec{w}_1)= & {} \sum _{K \in T_k} \int _K \varepsilon (\varvec{\phi }) : \varepsilon (\varvec{w}_1) dx-\sum _{e \in E_k} \int _e \{\varepsilon (\varvec{\phi })\} \cdot [(\varvec{w}_1)_t] ds\\&-\sum _{e \in E_k} \int _e \{\varepsilon (\varvec{w}_1)\} \cdot [\varvec{\phi }_t]ds+\sum _{e \in E_k} \int _e \eta h_e^{-1}[ \varvec{\phi }_t] \cdot [(\varvec{w}_1)_t] ds\\= & {} \sum _{K \in T_k} \int _K \varepsilon (\varvec{\phi }) : \varepsilon (\varvec{w}_1) dx-\sum _{e \in E_k} \int _e \{\varepsilon (\varvec{\phi })\} \cdot [(\varvec{w}_1)_t] ds\\= & {} -\; \sum _{K\in T_k}\int _K{\text {div}}\varepsilon (\varvec{\phi })\cdot \varvec{w}_1 \le \Vert \varvec{\phi }\Vert _2\Vert \varvec{w}_1\Vert . \end{aligned}$$

Finally, the desired result follows from the interpolation estimates in Lemma 4, the regularity estimate $\Vert \varvec{\phi }\Vert _2+\Vert \theta \Vert _1\lesssim \Vert \widetilde{\varvec{u}}\Vert$, inequality (4.22) and the inverse inequalities $\Vert \varvec{w}_1\Vert _{1,k}\lesssim h_k^{-1} \Vert \varvec{w}_1\Vert ~\text{ and }~ \Vert {\text {div}}\varvec{w}_2\Vert \lesssim h_k^{-1}\Vert {\text {div}}\, \varvec{w}_2\Vert _{-1}$.

We now define a decomposition of $\varvec{u}\in \varvec{V}_k$ which is stable in $\Vert \cdot \Vert _{k,0}$ norm and then show the estimates.

We consider three solutions of problem (4.21) defined as follows:

$$\begin{aligned}&(\varvec{u}_1,p_1)\ \hbox {is the solution of}\ (4.21)\ \hbox {with}\ \varvec{w}_1 = \varvec{u}, \varvec{w}_2=0. \end{aligned}$$

(4.27)

$$\begin{aligned}&(\varvec{u}_2,p_2)\ \hbox {is the solution of}\ (4.21)\ \hbox {with}\ \varvec{w}_1 = 0, \varvec{w}_2= \varvec{u} - \varvec{\Pi }_{k-1} \varvec{u}. \end{aligned}$$

(4.28)

$$\begin{aligned}&(\varvec{u}_3,p_3)\ \hbox {is defined as the solution of}\ (4.21)\ \hbox {with}\ \varvec{w}_1 = 0, \varvec{w}_2=\Pi _{k-1} \varvec{u}.\quad \end{aligned}$$

(4.29)

It is straightforward to check that $\varvec{u}-\varvec{u}_1-\varvec{u}_2-\varvec{u}_3$ and $p_1+p_2+p_3$ satisfy the Eq. (4.21) with $\varvec{w}_1=0$ and $\varvec{w}_2 = 0$ and therefore $\varvec{u}_1 + \varvec{u}_2 + \varvec{u}_3=\varvec{u}$. With these settings in hand, we have the following stability result.

Lemma 8

For the decomposition given in (4.27)–(4.29) we have

$$\begin{aligned}&\Vert \varvec{u}_1\Vert _{k,0}+\Vert \varvec{u}_2\Vert _{k,0}+\Vert \varvec{u}_3\Vert _{k,0} \lesssim \Vert \varvec{u}\Vert _{k,0},\end{aligned}$$

(4.30)

$$\begin{aligned}&\Vert \varvec{u}_2\Vert \lesssim \lambda ^{-1} \Vert \varvec{u}\Vert _{k,0}. \end{aligned}$$

(4.31)

Proof

Computing $\Vert \cdot \Vert _{k,0}$ for the components $\varvec{u}_1$ and $\varvec{u}_2$ shows that

$$\begin{aligned}&\Vert \varvec{u}_1\Vert _{k,0} = \Vert \varvec{u}_1\Vert , \end{aligned}$$

(4.32)

$$\begin{aligned}&\Vert \varvec{u}_2\Vert _{k,0} \le \Vert \varvec{u}_2\Vert + \lambda h_k \Vert {\text {div}}(\varvec{u}-\Pi _{k-1} \varvec{u})\Vert . \end{aligned}$$

(4.33)

The rest of the proof is a direct consequence of the definitions of the components (4.27)–(4.28), the definition of the $\Vert \cdot \Vert _{k,0}$ norm, Lemma 7 and Lemma 1. Finally, the estimate for $\Vert \varvec{u}_3\Vert _{k,0}$ follows immediately by applying the triangle inequality.

4.7 Smoothing property via interpolation

Define the $H({\text {curl}};\Omega )$-conforming finite element space on level $k$ (see, e.g., [13])

$$\begin{aligned} \varvec{W}_k=\{\varvec{w}\in H( {\text {curl}},\Omega ): \varvec{w}|_K\in \varvec{W}(K), K\in T_k, \varvec{w}\times \varvec{n}|_{\partial \Omega }=0\}, \end{aligned}$$

then the three spaces $\varvec{V}_k, S_k$ and $\varvec{W}_k$ are related by the exact sequences ([13])

$$\begin{aligned} {0\longrightarrow \varvec{W}_k \xrightarrow { {\text {curl}}} \varvec{V}_k\xrightarrow {{\text {div}}} S_k\longrightarrow 0}. \end{aligned}$$

Furthermore, we define

$$\begin{aligned} \varvec{W}_k^{\nu }=\left\{ \varvec{r}\in \varvec{W}_k: \hbox {supp}\,\varvec{r} \subset \bar{\Omega }_k^{\nu }\right\} , ~\nu \in \mathcal {V}_k\cup \mathcal {E}_k. \end{aligned}$$

Then

$$\begin{aligned} \varvec{W}_k=\sum _{i\in \mathcal {V}_k} \varvec{W}_k^{i}=\sum _{e\in \mathcal {E}_k} \varvec{W}_k^{e}. \end{aligned}$$

Note that for any $\varvec{v}\in \varvec{V}_k$, we have that $\Vert \varvec{v}\Vert _{A_k}\lesssim \Vert \varvec{v}\Vert _{D_k}$ and $\Vert \varvec{v}\Vert _{D_k}\le \Vert \varvec{v}\Vert _{D_k}$ and this implies that

$$\begin{aligned} \Vert \varvec{v}\Vert _{[D_k,A_k]} \lesssim \Vert \varvec{v}\Vert _{D_k}. \end{aligned}$$

(4.34)

The next two lemmas bound only the $\Vert \cdot \Vert _{D_k}$-norm, which is sufficient in view of (4.34).

Lemma 9

Let $\varvec{u}_1$ be defined as in (4.27). Then

$$\begin{aligned} \Vert \varvec{u}_1\Vert _{D_k}\lesssim h_k^{-1}\Vert \varvec{u}_1\Vert _{k,0}. \end{aligned}$$

(4.35)

Proof

Since ${\text {div}}\, \varvec{u}_1=0$, we have $\varvec{u}_1= {\text {curl}}\varvec{w}_k$ (see [13]), where $\varvec{w}_k\in \varvec{W}_k$.

Noting that $\varvec{w}_k=\sum _{i\in \mathcal {V}_k} \varvec{w}_k^i$, where $\varvec{w}_k^i\in \varvec{W}_k^i$ and ${\text {curl}}\varvec{w}_k^i\in \varvec{V}_k^i$, by identity (4.19) and inequality (4.17), we have

$$\begin{aligned} \Vert \varvec{u}_1\Vert _{D_k}^2= & {} \inf _{\varvec{u}_1=\sum \varvec{u}_1^i}\sum _{i\in \mathcal {V}_k}\Vert \varvec{u}_1^i\Vert _{A_k}^2\le \sum _{i\in \mathcal {V}_k}\Vert {\text {curl}}\varvec{w}_k^i\Vert _{A_k}^2=\sum _{i\in \mathcal {V}_k}\Vert {\text {curl}}\varvec{w}_k^i\Vert _{a_k}^2\\= & {} \sum _{i\in \mathcal {V}_k}\Vert \varvec{u}_1^i\Vert _{a_k}^2\lesssim h_k^{-2} \sum _{i\in \mathcal {V}_k}\Vert \varvec{u}_1^i\Vert ^2\lesssim h_k^{-2} \Vert \varvec{u}_1\Vert ^2=h_k^{-2} \Vert \varvec{u}_1\Vert _{k,0}^2. \end{aligned}$$

The proof of the lemma is complete.

Lemma 10

Let $\varvec{u}_2$ be defined as in (4.28). Then

$$\begin{aligned} \Vert \varvec{u}_2\Vert _{D_k}\lesssim h_k^{-1} \Vert \varvec{u}\Vert _{k,0}. \end{aligned}$$

(4.36)

Proof

By the identity (4.19) and Lemma 8, we have

$$\begin{aligned}&\Vert \varvec{u}_2\Vert _{D_k}^2= \inf _{\varvec{u}_2=\sum \varvec{u}_2^i}\sum _{i\in \mathcal {V}_k}\Vert \varvec{u}_2^i\Vert _{A_k}^2\lesssim \sum _{i\in \mathcal {V}_k}h_k^{-2}\lambda \Vert \varvec{u}_2^i\Vert ^2\lesssim h_k^{-2}\lambda \Vert \varvec{u}_2\Vert ^2\lesssim h_k^{-2} \Vert \varvec{u}\Vert _{k,0}^2. \end{aligned}$$

The proof is complete.

Corollary 1

From the inequality (4.34) and the Lemmas 9 and 10, we immediately have

$$\begin{aligned}&\Vert \varvec{u}_1\Vert _{[D_k,A_k]}\lesssim h_k^{-1} \Vert \varvec{u}_1\Vert _{k,0},\nonumber \\&\Vert \varvec{u}_2\Vert _{[D_k,A_k]}\lesssim h_k^{-1} \Vert \varvec{u}\Vert _{k,0}. \end{aligned}$$

(4.37)

Lemma 11

Let $\varvec{u}_3$ be defined as in (4.29). Then

$$\begin{aligned} \Vert \varvec{u}_3\Vert _{[D_k,A_k]}\lesssim h_k^{-1} \Vert \varvec{u}\Vert _{k,0}. \end{aligned}$$

(4.38)

Proof

By the inf-sup condition (4.22) we have $\Vert \varvec{u}_3\Vert _{1,k}+\Vert p_3\Vert \lesssim \Vert Q_{k-1}{\text {div}}\, \varvec{u}\Vert$. Furthermore, ${\text {div}}\, \varvec{u}_3=Q_{k-1}{\text {div}}\, \varvec{u}$ by definition. These together with the identity (4.19) give

$$\begin{aligned} \Vert \varvec{u}_3\Vert _{A_k}^2&\lesssim (\Vert \varvec{u}_3\Vert _{1,k}^2+\lambda \Vert {\text {div}}\, \varvec{u}_3\Vert ^2) \\&\lesssim \Vert Q_{k-1}{\text {div}}\, \varvec{u}\Vert ^2+ \lambda \Vert Q_{k-1}{\text {div}}\, \varvec{u}\Vert ^2 \lesssim \lambda ^{-1} h_k^{-2} \Vert \varvec{u}\Vert _{k,0}^2. \end{aligned}$$

On the other hand, we have

$$\begin{aligned} \Vert \varvec{u}_3\Vert _{D_k}^2&=\inf _{\varvec{u}_3=\sum \varvec{u}_3^i}\sum _{i\in \mathcal {V}_k}\Vert \varvec{u}_3^i\Vert _{A_k}^2 \lesssim \sum _{i\in \mathcal {V}_k}h_k^{-2}\lambda \Vert \varvec{u}_3^i\Vert ^2 \lesssim h_k^{-2}\lambda \Vert \varvec{u}_3\Vert ^2\\&\lesssim \lambda h_k^{-2} \Vert \varvec{u}_3\Vert _{k,0}^2\lesssim \lambda h_k^{-2} \Vert \varvec{u}\Vert _{k,0}^2. \end{aligned}$$

A standard interpolation argument, see, e.g., [31], concludes the proof.

We close this subsection by the following theorem which verifies (A2).

Theorem 6

The following estimate holds for all $\varvec{u}\in \varvec{V}_k$.

$$\begin{aligned} \Vert (\widetilde{K}_k^{(m)})^*\varvec{u}\Vert _{A_k} \lesssim m^{-1/4}h_k^{-1} \Vert \varvec{u}\Vert _{k,0}. \end{aligned}$$

(4.39)

Proof

By Lemma 8, inequalities (4.37) and (4.38), we obtain the smoothing property (4.39).

5 Numerical experiments

To test the performance of the multigrid algorithms that we have proposed we present three sets of numerical tests solving Eq. (2.3).

For simplicity, we take as computational domain $\Omega =[0,1]\times [0,1]$ and discretize equation (2.1) and (2.3) by $H({\text {div}},\Omega )$-conforming $BDM_1$ finite elements ($BDM_1(K)/P_{0}(K)$ pair for Stokes equation) on a uniform mesh using the DG method described in Sect. 3. Our tests are aimed at confirming the theoretical results on the convergence of the multigrid algrithms for the linear system (3.11). We have tabulated the results obtained with the multigrid method for meshes with mesh sizes $h_J= 2^{-J}$ where $J=2,\ldots ,6$. In addition, we have varied the Lamé parameter $\lambda =1/(1-2\nu )$, where $\nu$ is the Poisson ratio and we have taken values of $\nu$ close to the critical value of $1/2$.

For the multigrid $\mathcal {V}(1,1)$, $\mathcal {W}(1,1)$ and $\mathcal {W}(2,2)$ cycles we have used a vertex block Gauss–Seidel smoother. In order to approximate the error reduction factor of the multigrid iteration, i.e. the number $\rho = \Vert \mathbb {E}_J\Vert _{\mathbb {A}_J} :=\Vert I-\mathbb {B}_J\mathbb {A}_J \Vert _{\mathbb {A}_J}$, we have set $\varvec{e}_i=\mathbb {E}_J\varvec{e}_{i-1}$ with a random initial guess $\varvec{e}_0$ and computed the ratio $\rho _{i}:=\frac{(A_J\varvec{e}_i, \varvec{e}_i)}{(A_J\varvec{e}_{i-1}, \varvec{e}_{i-1})}$ for large enough $i$.

In all tables $J$ denotes the level of the finest discretization and $N$ denotes the number of degrees of freedom for the displacement component (for $BDM_1$ elements, $N$ is twice the number of edges).

The data in Table 1 verifies the convergence result in Theorem 2 and the data in Tables 2, 3 verifies the result shown in Theorem 3. We want to emphasize that although Theorem 3 requires that the number of smoothing steps is sufficiently large, the results shown in Table 2 indicate that one smoothing step is sufficient for a uniform convergence of the $W$-cycle MG method. Furthermore, the results in Table 3 show that using two smoothing steps further improves $\rho$.

Table 1 Convergence rate $\Vert \mathbb {E}_J\Vert _{\mathbb {A}_J}$ of the $\mathcal {V}(1,1)$-cycle method

Table 2 Convergence rate $\Vert \mathbb {E}_J\Vert _{\mathbb {A}_J}$ of the $\mathcal {W}(1,1)$-cycle method

Table 3 Convergence rate $\Vert \mathbb {E}_J\Vert _{\mathbb {A}_J}$ of the $\mathcal {W}(2,2)$-cycle method

As predicted by the theory, the results presented in Tables 1, 2, 3 show uniform convergence independent of both $\lambda$ and $h$.

Finally, to test the augmented Uzawa iteration we have set the right hand side of the Stokes equation to

$$\begin{aligned} \varvec{f}=\left( \begin{matrix} (1-6x+6x^2)(y-3y^2+2y^3)+(x^2-2x^3+x^4)(-3+6y)\\ -(1-6y+6y^2)(x-3x^2+2x^3)-(y^2-2y^3+y^4)(-3+6x) \end{matrix} \right) . \end{aligned}$$

and used the corresponding exact solution of the sub-problem for the displacement $\varvec{u}$ [see (3.13)]. The iteration has been initialized with $\varvec{u}_h^0=\varvec{0}$ and $p_h^0= 0$ and terminated after a reduction of the error of the velocity in energy norm by a factor of $10^{8}$. The results in Table 4 confirm the convergence result for the augmented Uzawa iteration, which is given in (3.13) (see also [12]).

Table 4 Iteration count of the augmented Uzawa method

6 Conclusions

We have presented a multigrid algorithm for discontinuous Galerkin $H({\text {div}},\Omega )$-conforming discretizations of the Stokes and linear elasticity equations. A variable V-cycle and a W-cycle have been designed to solve the linear elasticity problem in the present situation of nonnested bilinear forms. The convergence rate of the algorithm has been proved to be independent of the Lamé parameters (or, equivalently, the Poisson ratio) and of the mesh size, which shows that the multigrid method is robust and optimal. Numerical experiments have been presented that confirm the theoretical results.