Multilevel decompositions and norms for negative order Sobolev spaces

We recall some results on multilevel norms from [32] adopted to the notation used in the present work. Let $(\mathcal{T}_{\ell})_{\ell\in\mathbb{N}_{0}}$ denote a sequence of uniformly refined simplicial meshes with mesh sizes $(h_{\ell})_{\ell\in\mathbb{N}_{0}}$. For the range $s\in(0,1/2)$ one gets from [32, Eq.(3)] that

where $\Pi^{0}_{\ell}$ denotes the $L^{2}(\Omega)$ orthogonal projection on the space of piecewise constants $\mathcal{P}^{0}(\mathcal{T}_{\ell})$. The multilevel norm can be efficiently evaluated if $\phi\in\mathcal{P}^{0}(\mathcal{T}_{L})$.

However, the latter equivalence does not include one of the arguably most important cases, $s=1/2$. It is shown ([32, Theorem 2]) that

and the factor $(L+1)^{2}$ can not be improved in general, thus, yielding suboptimal results.

Rather than using duality arguments to transfer results for positive order Sobolev spaces to negative order spaces (see e.g. [32, Section 2]), we exploit the deep connection between interpolation and approximation spaces where we view $H^{-s}(\Omega)$ as an intermediate space between $H^{-1}(\Omega)$ and $L^{2}(\Omega)$. At first glance this seems to further complicate the problem due to the necessity of handling the $H^{-1}(\Omega)$ norm. However, some ideas resp. results from our recent work [20] and the work at hand show how to define local decompositions in the $H^{-1}(\Omega)$ norm by using Haar-type functions that can be written as the divergence of Raviart–Thomas functions. Furthermore, we introduce and analyze locally defined projection operators in $H^{-1}(\Omega)$ onto the space of piecewise constant functions. We note that for problems of positive order the Sobolev space $H^{s}(\Omega)$ is an intermediate space between $L^{2}(\Omega)$ and $H^{t}(\Omega)$ for some $t\in(1,3/2)$. Together with stability of the canonical basis of piecewise affine and globally continuous functions in $L^{2}(\Omega)$ this yields optimality of the BPX preconditioner, see, e.g., [7, 6] and references therein for a detailed analysis.

Let us summarize two of our main results that can be found in Section 3 and are valid for uniform as well as adaptive meshes: Let $(\mathcal{T}_{\ell})_{\ell\in\mathbb{N}_{0}}$ denote a sequence of meshes with mesh-size functions $(h_{\ell})_{\ell\in\mathbb{N}_{0}}$ and facets $(\mathcal{E}_{\ell})_{\ell\in\mathbb{N}_{0}}$. For $\ell\in\mathbb{N}_{0}$, $E\in\mathcal{E}_{\ell}$ we define spaces $\mathcal{X}_{\ell,E}=\operatorname{span}\{\psi_{\ell,E}\}\in\mathcal{P}^{0}(\mathcal{T}_{\ell})$ where $\psi_{\ell,E}$ is supported on at most two elements of $\mathcal{T}_{\ell}$ (which share the facet $E$) and $\int_{\Omega}\psi_{\ell,E}\,\mathrm{d}x=0$ if $E\not\subset\partial\Omega$ (a precise definition is found in Section 2.3) and use subsets $\widetilde{}\mathcal{E}_{\ell}\subset\mathcal{E}_{\ell}$ that satisfy $\#\widetilde{}\mathcal{E}_{\ell}=\mathcal{O}(\#\mathcal{T}_{\ell}\setminus\mathcal{T}_{\ell-1})$.

• •

  Multilevel decomposition (Theorem 17):

  $\displaystyle\|\phi\|_{-s}^{2}\simeq\inf\big{\{}\sum_{\ell=0}^{L}\sum_{E\in\widetilde{}\mathcal{E}_{\ell}}\|\phi_{\ell,E}\|_{-s}^{2}\,:\,\phi_{\ell,E}\in\mathcal{X}_{\ell,E}\text{ such that }\phi=\sum_{\ell=0}^{L}\sum_{E\in\widetilde{}\mathcal{E}_{\ell}}\phi_{\ell,E}\big{\}}$

  for all $\phi\in\mathcal{P}^{0}(\mathcal{T}_{L})$.

• •

  Multilevel norms (Theorem 19): There exist locally defined operators $P_{\ell}^{\prime}$ such that

  $\displaystyle\|\phi\|_{-s}^{2}\simeq\sum_{\ell=0}^{L}\|h_{\ell}^{s}(P_{\ell}^{\prime}-P_{\ell-1}^{\prime})\phi\|^{2}\quad\text{for all }\phi\in\mathcal{P}^{0}(\mathcal{T}_{L}).$

In particular, the constants are independent of the levels or the mesh-sizes. We note that the decomposition into one-dimensional subspaces implies that the associated preconditioner is of a multilevel diagonal scaling type.

In Section 2 we introduce notation and some basic results. In particular, Section 2.4 and Section 2.5 deal with the definition and analysis of local projection operators in negative order Sobolev spaces. In Section 3 we present our main results and their proofs are given in Section 4. Numerical experiments are presented in Section 5. The final Section 6 concludes this article with a discussion on applications and extensions including the case of higher-order polynomial spaces.

Throughout this work we write $a\lesssim b$ resp. $a\gtrsim b$ if there exists a constant $C>0$ such that $a\leq Cb$ resp. $a\geq Cb$. If both directions hold we write $a\simeq b$. In the main results dependencies on constants will be specified.

For a bounded Lipschitz domain $\omega\subset\mathbb{R}^{d}$ ($d\geq 2$) let

with norm $\|\cdot\|_{H^{1}(\omega)}=\big{(}\|\cdot\|_{\omega}^{2}+\|\nabla(\cdot)\|_{\omega}^{2}\big{)}^{1/2}$. Here, $\|\cdot\|_{\omega}$ denotes the $L^{2}(\omega)$ or $L^{2}(\omega)^{d}$ norm which is induced by the scalar product $(\cdot\hskip 1.42262pt,\cdot)_{\omega}$. Let $H_{0}^{1}(\omega)$ denote the closed subspace of $H^{1}(\omega)$ with vanishing traces and recall that $\|\nabla(\cdot)\|_{\omega}$ defines an equivalent norm on $H_{0}^{1}(\omega)$. The dual space $H^{-1}(\omega):=(H_{0}^{1}(\omega))^{\prime}$ is equipped with the dual norm

where the duality $\langle\cdot\hskip 1.42262pt,\cdot\rangle_{\omega}$ is understood with respect to the extended $L^{2}(\omega)$ inner product. Analogously, $\widetilde{H}^{-1}(\omega):=(H^{1}(\omega))^{\prime}$ with norm

Throughout this work we consider a connected Lipschitz domain $\emptyset\neq\Omega\subset\mathbb{R}^{d}$ with boundary $\Gamma:=\partial\Omega$ and skip indices in the notation of norms, e.g., we write $\|\cdot\|$ instead of $\|\cdot\|_{\Omega}$, $\|\cdot\|_{-1}$ instead of $\|\cdot\|_{-1,\Omega}$.

For $s\in(0,1)$ we define the intermediate spaces $H^{s}(\Omega)$ resp. $\widetilde{H}^{s}(\Omega)$ by real interpolation ($K$-method, see, e.g. [11, Section 4]), i.e.,

We recall that the dual spaces $\widetilde{H}^{-s}(\Omega):=(H^{s}(\Omega))^{\prime}$ resp. $H^{-s}(\Omega):=(\widetilde{H}^{s}(\Omega))^{\prime}$ can be written as interpolation spaces as well, i.e.,

for all $\theta\in(0,1)$, see, e.g., [30, Chapter 1, Theorem 6.2]. An extensive overview on interpolation between Hilbert spaces and, in particular, Sobolev spaces is found in [11].

The space of $L^{2}(\omega)^{d}$ fields with divergence in $L^{2}(\omega)$ is denoted by $\boldsymbol{H}({\rm div\,};\omega)$. Also note that ${\rm div\,}\colon L^{2}(\Omega)^{d}\to H^{-1}(\Omega)$ is a bounded operator.

Let $\mathcal{T}$ denote a regular mesh of $\Omega$ consisting of open simplices, i.e., $\overline{\Omega}=\bigcup_{T\in\mathcal{T}}\overline{T}$. With $h_{T}:=\mathrm{diam}(T)$ we define the mesh-size function $h_{\mathcal{T}}$ by $h_{\mathcal{T}}|_{T}:=h_{T}$. The set of all $d-1$ facets of an element $T\in\mathcal{T}$ is denoted by $\mathcal{E}(T)$. For our studies we also use the sets

The set of vertices of an element $T\in\mathcal{T}$ is denoted with $\mathcal{N}(T)$, and

In this work we consider sequences of meshes $(\mathcal{T}_{\ell})_{\ell\in\mathbb{N}_{0}}$ where we assume that $\mathcal{T}_{\ell+1}$ is generated from $\mathcal{T}_{\ell}$ by refining certain (or all) elements. A common type of mesh refinement is, e.g., newest vertex bisection, see, e.g., [39] and references therein. The generation $\operatorname{gen}(T)$ of an element $T\in\bigcup_{\ell\in\mathbb{N}_{0}}\mathcal{T}_{\ell}$ denotes the number of iterated refinements (bisections) to obtain $T\in\mathcal{T}_{\ell}$ from a father element $T^{\prime}\in\mathcal{T}_{0}$. We assume, given a suitable initial mesh $\mathcal{T}_{0}$, that the sequence $\mathcal{T}_{0},\mathcal{T}_{1},\dots$ generated by the mesh refinement strategy satisfies:

1. (A1)

   Shape regularity: There exists a constant $C_{\mathrm{reg}}>0$ such that

   $\displaystyle\sup_{\ell\in\mathbb{N}_{0}}\sup_{T\in\mathcal{T}_{\ell}}\frac{\mathrm{diam}(T)^{d}}{|T|}\leq C_{\mathrm{reg}}.$

2. (A2)

   There exists $q_{\mathrm{ref}}\in(0,1)$ and $C_{\mathrm{ref}}>0$ such that

   $\displaystyle C_{\mathrm{ref}}^{-1}h_{T}\leq q_{\mathrm{ref}}^{\operatorname{gen}(T)}\leq C_{\mathrm{ref}}h_{T}\quad\text{for all }T\in\bigcup_{\ell\in\mathbb{N}_{0}}\mathcal{T}_{\ell}.$

3. (A3)

   There exists a constant $k_{\mathrm{ref}}\in\mathbb{N}$ such that for all $\ell\in\mathbb{N}_{0}$ and all $T\in\mathcal{T}_{\ell+1}\setminus\mathcal{T}_{\ell}$ with unique father element $T_{F}\in\mathcal{T}_{\ell}$,

   $\displaystyle 1\leq|\operatorname{gen}(T)-\operatorname{gen}(T_{F})|\leq k_{\mathrm{ref}}.$

These assumptions are satisfied for, e.g., the newest vertex bisection, see [39] and [22].

We say that $(\mathcal{T}_{m})_{m\in\mathbb{N}_{0}}$ is a sequence of uniform meshes if (besides the assumptions from above)

• •

  $\mathcal{T}_{m+1}\setminus\mathcal{T}_{m}=\mathcal{T}_{m+1}$ and $\operatorname{gen}(T)=\operatorname{gen}(T^{\prime})$ for all $T,T^{\prime}\in\mathcal{T}_{m}$ and $m\in\mathbb{N}_{0}$.

Moreover, we assume that for a sequence of meshes $(\mathcal{T}_{\ell})_{\ell\in\mathbb{N}_{0}}$ there exists a sequence of uniform meshes $(\widehat{}\mathcal{T}_{m})_{m\in\mathbb{N}_{0}}$ with $\widehat{}\mathcal{T}_{0}=\mathcal{T}_{0}$ satisfying (A1)–(A3) with the same constants.

From the assumptions given in this section we can interpret the mesh-size functions of uniform meshes as constants.

Let $\mathcal{T}$ be a regular mesh. Element patches are given by

The corresponding domains are denoted with $\Omega_{\mathcal{T}}(S)$ and $\Omega_{\mathcal{T}}(z)$. Higher-order patches are denoted with an additional superscript, e.g., $\omega_{\mathcal{T}}^{(2)}(S)=\omega_{\mathcal{T}}(\Omega_{\mathcal{T}}(S))$.

For $T\in\mathcal{T}$ we denote with $\mathcal{P}^{p}(T)$ the space of polynomials of degree $\leq p\in\mathbb{N}_{0}$ and set

Furthermore,

The space $\mathcal{S}^{1}(\mathcal{T})$ is equipped with the common basis $\big{\{}\eta_{\mathcal{T},z}\,:\,z\in\mathcal{N}_{\mathcal{T}}\big{\}}$ where $\eta_{\mathcal{T},z}(z^{\prime})=\delta_{z,z^{\prime}}$ for all $z,z^{\prime}\in\mathcal{N}_{\mathcal{T}}$. Here, $\delta_{z,z^{\prime}}$ denotes the Kronecker-$\delta$ symbol.

We make use of the $L^{2}(\Omega)$ orthogonal projection $\Pi^{p}_{\mathcal{T}}\colon L^{2}(\Omega)\to\mathcal{P}^{p}(\mathcal{T})$ and the $H^{-1}(\Omega)$ orthogonal projection $\Pi^{(-1)}_{\mathcal{T}}\colon H^{-1}(\Omega)\to\mathcal{P}^{0}(\mathcal{T})$ resp. the $\widetilde{H}^{-1}(\Omega)$ orthogonal projection $\Pi^{(-1),\sim}_{\mathcal{T}}\colon\widetilde{H}^{-1}(\Omega)\to\mathcal{P}^{0}(\mathcal{T})$. It is well-known that these operators satisfy the approximation properties

for all $\phi\in L^{2}(\Omega)$, which follow from duality and Poincaré inequalities.

Recall the inverse estimates

for all $\phi\in\mathcal{P}^{p}(\mathcal{T})$ and $s\in[0,1]$, see, e.g., [23, Theorem 3.6], as well as the local variant

which follows from a scaling argument. For a uniform mesh (recall that $h_{\mathcal{T}}$ is constant) the interpolation inequality [30, Chapter 1, Proposition 2.8] and the inverse estimate (2) show

for all $\phi\in\mathcal{P}^{p}(\mathcal{T})$.

For the decompositions we use Haar-type functions which can be written as the divergence of Raviart–Thomas functions. Let $\mathcal{RT}^{p}(\mathcal{T})$ denote the space of Raviart–Thomas functions of order $p\in\mathbb{N}_{0}$. For each $E\in\mathcal{E}_{\mathcal{T}}^{\Omega}$ there exist unique elements $T_{E}^{\pm}\in\mathcal{T}$ with $E={\rm int}(\overline{T}_{E}^{+}\cap\overline{T}_{E}^{-})$. For each $E\in\mathcal{E}_{\mathcal{T}}^{\Gamma}$ there exists a unique element $T_{E}^{+}\in\mathcal{T}$ with $E={\rm int}(\overline{T}_{E}^{+}\cap\Gamma)$ and we set $T_{E}^{-}:=\emptyset$. Let $\chi_{T}$ denote the characteristic function of an element $T\in\mathcal{T}$ and let $\big{\{}{\boldsymbol{\psi}}_{\mathcal{T},E}\,:\,E\in\mathcal{T}\big{\}}$ be the canonical local basis of $\mathcal{RT}^{0}(\mathcal{T})$ with $\operatorname{supp}{\boldsymbol{\psi}}_{\mathcal{T},E}\subseteq\overline{T}^{+}\cup\overline{T}^{-}$, vanishing normal trace on $\mathcal{E}\setminus\{E\}$ and

Here, $|E|$ denotes the surface measure of the facet $E\in\mathcal{E}_{\mathcal{T}}$ and we set $1/|T_{E}^{-}|=0$ for $E\in\mathcal{E}_{\mathcal{T}}^{\Gamma}$. From [20, Lemma 1] we recall some scaling properties, where $h_{E}:=\mathrm{diam}(E)$.

Let $s\in(0,1)$. Lemma 2 together with interpolation and inverse estimates from above show that

In the recent work [16] a local projection operator onto the Raviart–Thomas space has been defined that does not rely on regularity assumptions (the canonical Raviart–Thomas projection requires that ${\boldsymbol{\sigma}}\in H^{t}(\Omega)^{d}\cap\boldsymbol{H}({\rm div\,};\Omega)$ with some $t>1/2$ so that the normal trace ${\boldsymbol{\sigma}}\cdot{\boldsymbol{n}}|_{E}$ is well-defined in $L^{2}(E)$).

Finally, for a sequence $(\mathcal{T}_{\ell})_{\ell\in\mathbb{N}_{0}}$ we use the indices $\ell$ instead of $\mathcal{T}_{\ell}$ in the notation of the corresponding operators, patches etc., e.g., $\Pi^{0}_{\ell}$ instead of $\Pi^{0}_{\mathcal{T}_{\ell}}$ and $\omega_{\ell}(z)$ instead of $\omega_{\mathcal{T}_{\ell}}(z)$. Furthermore, we define operators with negative indices to be trivial, e.g., $\Pi^{0}_{k}:=0$ for $k<0$.

In this section we define a local projection operator $Q_{\mathcal{T}}\colon H^{-1}(\Omega)\to\mathcal{P}^{0}(\mathcal{T})$ which plays a crucial role in the stability analysis that follows. We give a brief overview of the basic idea: First, we consider a Fortin operator based on the quasi-interpolation operator [36]. Then, we study its adjoint operator and, finally, we use the canonical $L^{2}(\Omega)$ projection (on piecewise constants) to define $Q_{\mathcal{T}}$.

We consider the following variant: For each $z\in\mathcal{N}_{\mathcal{T}}$ let $\emptyset\neq\gamma_{z}\subseteq\omega_{\mathcal{T}}(z)$ and set

where $\psi_{T,z}\in\mathcal{P}^{1}(T)$ is the unique element with $(\psi_{T,z}\hskip 1.42262pt,\eta_{\mathcal{T},z^{\prime}})_{T}=\delta_{z,z^{\prime}}$ for all $z,z^{\prime}\in\mathcal{N}(T)$. Some comments are in order:

For the remainder of this work we use $\gamma_{z}=\omega_{\mathcal{T}}(z)$ in the definition of $J_{\mathcal{T}}$. The next lemma collects some well-known results on $J_{\mathcal{T}}$ (see [47, Lemma 3.2–3.6]):

Let $\mathcal{S}^{b}(\mathcal{T})\subset H_{0}^{1}(\Omega)$ denote the space of bubble functions with basis functions $\eta_{b,T}=\prod_{z\in\mathcal{N}(T)}\eta_{\mathcal{T},z}$ for $T\in\mathcal{T}$ and set $\mathcal{S}_{0}^{1,b}=\mathcal{S}_{0}^{1}(\mathcal{T})\oplus\mathcal{S}^{b}(\mathcal{T})$. The operator defined in the next result is a Fortin-type operator (below this is called orthogonality property).

With $P_{\mathcal{T}}^{\prime}\colon L^{2}(\Omega)\to L^{2}(\Omega)$ we denote the adjoint of $P_{\mathcal{T}}$. Writing $P_{\mathcal{T}}=J_{\mathcal{T}}+B_{\mathcal{T}}(1-P_{\mathcal{T}})$ we see

where

Note that by Remark 4 we have that $\varphi_{\mathcal{T},z}=1/|\Omega_{\mathcal{T}}(z)|(\alpha\eta_{\mathcal{T},z}+\beta)$ on $\Omega_{\mathcal{T}}(z)$ and $0$ otherwise. From this explicit representation it is thus straightforward to see that $P_{\mathcal{T}}^{\prime}\phi\in\mathcal{P}^{1}(\mathcal{T})$ for all $\phi\in L^{2}(\Omega)$. We will use this fact in order to apply (local) inverse estimates, e.g. $\|h_{\mathcal{T}}P_{\mathcal{T}}^{\prime}\phi\|\lesssim\|P_{\mathcal{T}}^{\prime}\phi\|_{-1}$. Moreover, note that $P_{\mathcal{T}}$ is bounded in $H_{0}^{1}(\Omega)$ so that $P_{\mathcal{T}}^{\prime}\colon H^{-1}(\Omega)\to\mathcal{P}^{1}(\mathcal{T})$ is well-defined.

The next result follows more or less immediately from the properties described in Lemma 6.