Introduction
Least Squares Formulations
Well-posedness of a (formal) linear operator equation
B u = f (1) Bu=f \tag*{(1)} B u = f (1)
is inevitably tied to the specification of a (linear) trial space U U U - often a Hilbert space - that is supposed to accommodate a unique solution u ∗ ∈ U u^* \in U u ∗ ∈ U , and a test space V V V , whose dual V ′ V' V ′ then determines the admissible range for the source f f f . Existence of a solution for all f ∈ V ′ f \in V' f ∈ V ′ , its uniqueness and continuous dependence on the data f f f then means that B : U → V ′ B: U \to V' B : U → V ′ is a norm-isomorphism. This is well known to be equivalent to the fact that the bilinear form b ( u , v ) : = ( B u ) ( v ) b(u,v):=(Bu)(v) b ( u , v ) := ( B u ) ( v ) , that takes U × V U \times V U × V into R \mathbb{R} R , satisfies the conditions of the Babuška-Nečas Theorem (see § 2.1 for more details). This, in turn means that there exist constants 0 < c b ≤ C b < ∞ 0<c_b\le C_b<\infty 0 < c b ≤ C b < ∞ such that
c b ∥ u − u ∗ ∥ U ≤ ∥ f − B u ∥ V ′ ≤ C b ∥ u − u ∗ ∥ U ∀ u ∈ U . (2) c_b\lVert u-u^*\rVert_U\le\lVert f-Bu\rVert_{V'}\le C_b\lVert u-u^*\rVert_U\quad\forall u\in U. \tag*{(2)} c b ∥ u − u ∗ ∥ U ≤ ∥ f − B u ∥ V ′ ≤ C b ∥ u − u ∗ ∥ U ∀ u ∈ U . (2)
Thus, on the one hand, the residual in V ′ V' V ′ is a reliable and efficient error estimator, and on the other hand, the exact solution u ∗ u^* u ∗ as well as an approximation to u ∗ u^* u ∗ from some subspace U n U_n U n , can be found as the minimizer of the respective (squared) residual.
When (1) is a homogeneous second order elliptic Dirichlet problem, one finds U = H 0 1 ( Ω ) = V U=H^1_0(\Omega)=V U = H 0 1 ( Ω ) = V and V ′ = ( H 0 1 ( Ω ) ) ′ = H − 1 ( Ω ) V'=(H^1_0(\Omega))'=H^{-1}(\Omega) V ′ = ( H 0 1 ( Ω ) ) ′ = H − 1 ( Ω ) . This has triggered the development of an art to derive computable equivalent expressions for ∥ f − B u ∥ H − 1 ( Ω ) \lVert f-Bu\rVert_{H^{-1}(\Omega)} ∥ f − B u ∥ H − 1 ( Ω ) in terms of so-called dual residual a posteriori error indicators, [26 ] or, from a different angle, approaches based on the hyper-circle principle, see e.g. [11 ] . This has by now led to a rich theory of Adaptive Finite Element Methods (AFEM) and a mature understanding of the convergence and complexity properties of AFEM, see e.g. [3 , 16 , 18 , 20 , 22 , 24 , 25 ] for a rather incomplete list, referring to [10 ] for a state-of-the-art overview and further references. Specifically, the essential structure of convergence and complexity proofs have been abstracted in [16 ] , providing a roadmap for treating a wide spectrum of application scenarios.
While in the above context a central challenge (systematically taken up first in [26 ] ) has been to evaluate the dual norm ∥ f − B u ∥ V ′ \|f-\mathcal{B}u\|_{\mathbb{V}'} ∥ f − B u ∥ V ′ . This issue disappears when V = V ′ \mathbb{V}=\mathbb{V}' V = V ′ happens to be self-dual, hence some kind of an L 2 L_2 L 2 -space (e.g. L 2 ( Ω ; R q ) L_2(\Omega;\mathbb{R}^q) L 2 ( Ω ; R q ) for some q ∈ N q\in\mathbb{N} q ∈ N ). In fact, computing a residual in L 2 L_2 L 2 (up to data-oscillation) is conceptually much simpler than in a non-trivial dual space. In other words, reliable and efficient error estimators are for free, when B \mathcal{B} B happens to be an isomorphism whose range is some L 2 L_2 L 2 -space.
Specializing (2) , the solution u ∗ u^* u ∗ of (1) is in this case characterized by
u ∗ = argmin u ∈ U ∥ f − B u ∥ L 2 2 . (3) u^*=\underset{u\in\mathbb{U}}{\operatorname{argmin}}\ \|f-\mathcal{B}u\|_{L_2}^2. \tag*{(3)} u ∗ = u ∈ U argmin ∥ f − B u ∥ L 2 2 . (3)
coining the term least squares method . Regarding the scope of its applicability, the paper [4 ] has marked an important breakthrough in proving that a specific weak first order formulation of second order elliptic problems is indeed well-posed and equivalent to (3) , see also [9 ] and the literature cited there. This has meanwhile been extended to other important PDE models, including first order formulations of the system for linear elasticity, of the Stokes system, as well as, more recently, space-time first order formulations of parabolic problems and of the acoustic wave equation, [6 , 7 , 19 ] .
Such L 2 L_2 L 2 -minimum residual methods have by now not only proven meritious in classical finite element settings but more recently also in the context of operator learning, [1 , 8 , 21 ] .
It should not surprise that, given the local error indicators η K ( u ) : = ∫ K ∣ f ( x ) − B u ( x ) ∣ 2 d x \eta_K(u):=\int_K|f(x)-\mathcal{B}u(x)|^2\,\mathrm{d}x η K ( u ) := ∫ K ∣ f ( x ) − B u ( x ) ∣ 2 d x for free, where K K K is an element of a current mesh (assuming a sufficiently accurate evaluations of such integrals for the moment), corresponding adaptive least squares methods (ALSM) have been lately attracting considerable attention, last but not least, because, empirically, they indeed turn out to perform well, see e.g. [14 ] for an overview.
Why Is there a Challenge for Adaptivity?
It may surprise though that the theoretical underpinning of ALSM is by far less mature than for AFEM. Specifically, the central issue, namely the question whether (4) entails the reduction of the current error by a fixed factor less than one (which is usually also the basis for proving optimal convergence/complexity rates), appears to be wide open. The only exception is [15 ] where for special lowest order discretizations for the FOSLS formulation of Poisson’s equation convergence could be quantified by emulating conventional techniques for elliptic problems. Unfortunately, this doesn’t seem to lead to any approach that works for more general discretizations and a wider spectrum of problems.
On a superficial level the main obstruction is simple. The considerable body of literature and expertise concerning standard AFEM for problems of elliptic type makes essential use of the fact that corresponding local error indicators involve explicit local mesh-size factors when proving that for each adaptive cycle
MARK ⟶ REFINE ⟶ SOLVE , (4) \operatorname{MARK}\ \longrightarrow\ \operatorname{REFINE}\ \longrightarrow\ \operatorname{SOLVE}, \tag*{(4)} MARK ⟶ REFINE ⟶ SOLVE , (4)
the current error is reduced by a fixed factor ρ < 1 \rho<1 ρ < 1 , see e.g. [16 ] . As mentioned earlier, this linear convergence is the indispensable first step for eventually proving, in a second step, that the convergence is even optimal over natural classes of approximation spaces, see e.g. [3 , 10 , 22 , 24 ] . Least squares residuals and resulting error indicators do not involve such mesh-size factors.
Contribution
The central objective of this paper is therefore to shed light on whether nevertheless suitable versions of (4) give rise to a fixed error reduction per cycle also for ALSM. We do so not for a specific PDE but on an abstract level for (1) when it is well-posed for a self-dual test space V = V ′ \mathbb{V}=\mathbb{V}' V = V ′ of L 2 L_2 L 2 -type.
To destill the essential mechanisms, we analyze first the convergence of (4) under idealized assumptions. In essence, this means that integrals can be computed and linear systems are solved exactly. This already brings out a notion of data visibility that governs error reduction. It should be stressed that this new notion, despite some similarities with what is commonly referred to as data-oscillation , differs in essential ways. Among other things, it is not only concerned with the ability to evaluate data exactly but is intimately tied to the current refinement region, made up by the refined cells within a given cycle (4) . In particular, its role stresses the fact that without any further condition on the right hand side - beyond membership in an L 2 L_2 L 2 -type space - convergence performance cannot be quantified. Data-visibility in the present context can be seen as a structural alignment property of f f f . Beeing of higher order relative to the residual is not merely a consequence of smoothness.
These findings become most transparent and convenient to handle when working with a specific norm for the trial space, which is often referred to as optimal trial norm .
Once linear error reduction has been established, which is the central issue in this paper, following the reasoning in [22 ] , more practical variants can be handled by perturbation arguments, leading then to (optimal) complexity estimates.
In view of the envisaged level of generality, there must remain though some level of idealization when assessing the complexity of such methods. We focus here only on reducing the level of idealization by facilitating the evaluation of residuals via piecewise polynomial approximations to the load f f f for the following reasons. First, including this form of perturbing problem data , is essential to understand error reduction through the previously mentioned notion of data visibility. Once, this scenario is under control, further perturbation effects, like inexact solves or consistency errors due to operator-coefficient approximations, can be handled in essentially the same way as for classical AFEM, see e.g. [22 ] . We therefore dispense here with repeating this machinery. Therefore, we confine the “complexity” discussion to the growth of partitions which represent the growth of the number of unknowns in adaptive discretizations. Further complexity estimates would require, in the preset generality, just making assumptions because e.g. solver performance will depend on the nature of a specific problem at hand. The second reason is that perturbing just f f f suffices to bring out those parts of the reasoning that deviate from the complexity arguments, used in classical AFEM.
A third reason for discussing at least the present light version of a complexity analysis (rather than just referring to the many similarities) is the following noteworthy distinction between respective results. While in classical AFEM analysis, linear convergence can typically be established under no restrictions on the bulk parameter θ ∈ ( 0 , 1 ) \theta\in(0,1) θ ∈ ( 0 , 1 ) in Dörfler marking (other than being less than one), the complexity analysis requires imposing “smallness” conditions on the bulk parameter θ \theta θ . This doesn’t seem to be necessary for ALSM.
Layout of the Paper
In Section 2 we describe the abstract problem setting so as to cover the instances mentioned above. We briefly recall as a prototype example the FOSLS case [4 ] . We also formulate the notion of optimal trial norm in the present context since it will turn out to simplify the convergence analysis. Section 3 is devoted to collecting the main ingredients of an ALSM and to setting corresponding notation. We then proceed formulating a scheme under certain idealized assumptions, focusing on what we call adaptive increment . Its discussion reveals the key obstruction to linear error reduction which leads to the aforementioned notion of data visibility . This is made precise in a first main result whose proof is given in the remainder of Section 3.
In Section 4 we reduce the idealizing assumptions on the right hand side data because this already brings out the essence of quantifiable convergence under more practical assumptions. In brief, quantifying piecewise polynomial approximability of the right hand side, allows one to quantify the performance of the ALSM under canonical assumptions on the trial spaces. These findings are collected in the second main result Theorem 4.1. Finally, in Section 5 we analyze the complexity and convergence under an approximability assumption on the right hand side in terms of the growth of adaptively generated partitions and hence the number of degrees of freedom.
Problem Setting
FOSLS
Let U \mathbb{U} U be a real Hilbert space with norm ∥ ⋅ ∥ \|\cdot\| ∥ ⋅ ∥ and B ∈ L ( U , V ) \mathcal{B} \in\mathcal{L}(\mathbb{U},\mathbb{V}) B ∈ L ( U , V ) where L ( U , V ) \mathcal{L}(\mathbb{U},\mathbb{V}) L ( U , V ) is the space of linear operators from U \mathbb{U} U to V \mathbb{V} V . The Babuška-Nečas Theorem states that B \mathcal{B} B is an isomorphism (boundedly invertible) if and only if the bilinear form b ( u , v ) : = ( B u ) ( v ) : U × V → R b(u,v):=(\mathcal{B}u)(v):\mathbb{U}\times\mathbb{V}\to\mathbb{R} b ( u , v ) := ( B u ) ( v ) : U × V → R is continuous and satisfies (see e.g. [12 , 17 ] )
inf u ∈ U sup v ∈ V b ( u , v ) ∥ u ∥ ∥ v ∥ V ≥ c b , sup u ∈ U sup v ∈ V b ( u , v ) ∥ u ∥ ∥ v ∥ V ≤ C b , (5) \inf_{u\in\mathbb{U}}\sup_{v\in\mathbb{V}}\frac{b(u,v)}{\|u\|\|v\|_{\mathbb{V}}}\ge c_b,\qquad\sup_{u\in\mathbb{U}}\sup_{v\in\mathbb{V}}\frac{b(u,v)}{\|u\|\|v\|_{\mathbb{V}}}\le C_b, \tag*{(5)} u ∈ U inf v ∈ V sup ∥ u ∥∥ v ∥ V b ( u , v ) ≥ c b , u ∈ U sup v ∈ V sup ∥ u ∥∥ v ∥ V b ( u , v ) ≤ C b , (5)
for v ∈ V v\in\mathbb{V} v ∈ V there exists a w v ∈ U w_v\in\mathbb{U} w v ∈ U such that b ( w v , v ) ≠ 0 b(w_v,v)\ne0 b ( w v , v ) = 0 .
This means that
∥ B ∥ L ( U , V ′ ) ≤ C b , ∥ B − 1 ∥ L ( V ′ , U ) ≤ c b − 1 , (6) \|\mathcal{B}\|_{\mathcal{L}(\mathbb{U},\mathbb{V}')} \le C_b,\qquad\|\mathcal{B}^{-1}\|_{\mathcal{L}(\mathbb{V}',\mathbb{U})}\le c_b^{-1}, \tag*{(6)} ∥ B ∥ L ( U , V ′ ) ≤ C b , ∥ B − 1 ∥ L ( V ′ , U ) ≤ c b − 1 , (6)
which in turn says that for any f ∈ V ′ f\in\mathbb{V}' f ∈ V ′ , B u = f \mathcal{B}u=f B u = f , in the sense that
b ( u , v ) = f ( v ) , v ∈ V , (7) b(u,v)=f(v),\qquad v\in\mathbb{V}, \tag*{(7)} b ( u , v ) = f ( v ) , v ∈ V , (7)
has a unique solution u ∗ u^* u ∗ which is stable,
C b − 1 ∥ f ∥ V ′ ≤ ∥ u ∗ ∥ ≤ c b − 1 ∥ f ∥ V ′ . (8) C_b^{-1}\|f\|_{\mathbb{V}'}\le\|u^*\|\le c_b^{-1}\|f\|_{\mathbb{V}'}. \tag*{(8)} C b − 1 ∥ f ∥ V ′ ≤ ∥ u ∗ ∥ ≤ c b − 1 ∥ f ∥ V ′ . (8)
Unless (7) arises through an energy minimization, where U = V \mathbb{U}=\mathbb{V} U = V is the natural choice and coercivity implies the inf-sup and surjectivity condition, identifying such stable pairs U , V \mathbb{U},\mathbb{V} U , V , may be part of the problem, and one may have to accept the fact that (5) can only hold for U ≠ V \mathbb{U}\ne\mathbb{V} U = V .
In fact, in what follows, we focus on this latter scenario when V = L 2 \mathbb{V}=\mathbb{L}_2 V = L 2 is an L 2 L_2 L 2 -type space , generally being of the form L 2 ( Ω ; R q ) L_2(\Omega;\mathbb{R}^q) L 2 ( Ω ; R q ) for some q ∈ N q\in\mathbb{N} q ∈ N (related to the spatial dimension d d d of the computational domain Ω ⊂ R d \Omega\subset\mathbb{R}^d Ω ⊂ R d ) hence is self-dual L 2 = L 2 ′ \mathbb{L}_2=\mathbb{L}_2' L 2 = L 2 ′ . We postpone describing instances where this is the case and point out first its relevance.
For convenience we denote in what follows by ( ⋅ , ⋅ ) Ω : L 2 × L 2 → R (\cdot,\cdot)_\Omega:\mathbb{L}_2\times\mathbb{L}_2\to\mathbb{R} ( ⋅ , ⋅ ) Ω : L 2 × L 2 → R the canonical inner product on L 2 \mathbb{L}_2 L 2 but prefer to refer to the domain Ω \Omega Ω , as a subscript, as this will change at times. Accordingly, we write
∥ g ∥ L 2 = ∥ g ∥ Ω = ( g , g ) Ω 1 / 2 , \|g\|_{\mathbb{L}_2}=\|g\|_\Omega=(g,g)_\Omega^{1/2}, ∥ g ∥ L 2 = ∥ g ∥ Ω = ( g , g ) Ω 1/2 ,
because such norms will sometimes be taken with respect to subdomains of Ω \Omega Ω .
We will make repeated use of the following facts which are in essence known, but stated in the following form for the convenience of the reader.
Proposition 2.1. Let U \mathbb{U} U be a real Hilbert space of functions defined on a computational domain Ω ⊂ R d \Omega\subset\mathbb{R}^d Ω ⊂ R d . We assume that U ⊂ L 2 \mathbb{U}\subset\mathbb{L}_2 U ⊂ L 2 is a continuous embedding. If B \mathcal{B} B has closed range the following are equivalent:
(i) B : U → L 2 \mathcal{B}:\mathbb{U}\to\mathbb{L}_2 B : U → L 2 is an isomorphism, i.e., (5) holds for V = L 2 = L 2 ′ \mathbb{V}=\mathbb{L}_2=\mathbb{L}_2' V = L 2 = L 2 ′ , i.e., there exists a unique solution u ∗ ∈ U u^*\in\mathbb{U} u ∗ ∈ U , satisfying
b ( u , v ) = ( B u ) ( v ) = ( f , v ) Ω , v ∈ L 2 . (9) b(u,v)=(\mathcal{B}u)(v)=(f,v)_\Omega,\qquad v\in\mathbb{L}_2. \tag*{(9)} b ( u , v ) = ( B u ) ( v ) = ( f , v ) Ω , v ∈ L 2 . (9) (ii) For any f ∈ L 2 f\in\mathbb{L}_2 f ∈ L 2 there exists a unique minimizer
u ∗ = argmin u ∈ U ∥ f − B u ∥ Ω 2 , (10) u^*=\underset{u\in\mathbb{U}}{\operatorname{argmin}}\|f-\mathcal{B}u\|_\Omega^2, \tag*{(10)} u ∗ = u ∈ U argmin ∥ f − B u ∥ Ω 2 , (10) that satisfies the following error-residual relation
c b ∥ u ∗ − u ∥ ≤ ∥ f − B u ∥ Ω ≤ C b ∥ u ∗ − u ∥ , u ∈ U , (11) c_b\|u^*-u\|\le\|f-\mathcal{B}u\|_\Omega\le C_b\|u^*-u\|,\qquad u\in\mathbb{U}, \tag*{(11)} c b ∥ u ∗ − u ∥ ≤ ∥ f − B u ∥ Ω ≤ C b ∥ u ∗ − u ∥ , u ∈ U , (11) for some constants 0 < c b ≤ C b < ∞ 0<c_b\le C_b<\infty 0 < c b ≤ C b < ∞ .
(iii) The symmetric problem
B ( u , v ) = ( B u , B v ) Ω = ( f , B v ) Ω , v ∈ U , (12) B(u,v)=(\mathcal{B}u,\mathcal{B}v)_\Omega=(f,\mathcal{B}v)_\Omega,\qquad v\in\mathbb{U}, \tag*{(12)} B ( u , v ) = ( B u , B v ) Ω = ( f , B v ) Ω , v ∈ U , (12) is elliptic over U \mathbb{U} U with coercivity and continuity constants c b 2 , C b 2 c_b^2,C_b^2 c b 2 , C b 2 , respectively.
Proof: Although the essence of the underlying reasoning is known we briefly sketch the short arguments which are actually instructive.
(i) ⇒ \Rightarrow ⇒ (ii): By the Babuška-Nečas Theorem, b ( ⋅ , ⋅ ) b(\cdot,\cdot) b ( ⋅ , ⋅ ) satisfies (5) for some positive constants c b , C b c_b,C_b c b , C b and hence (6) . Clearly the solution u ∗ u^* u ∗ of (9) minimizes ∥ f − B u ∥ Ω \lVert f-\mathcal{B}u\rVert_{\Omega} ∥ f − B u ∥ Ω and, due to its uniqueness, no other u ~ \widetilde{u} u can minimize ∥ f − B u ∥ L 2 \lVert f-\mathcal{B}u\rVert_{L_2} ∥ f − B u ∥ L 2 . Moreover, since ∥ f − B u ∥ Ω = ∥ B ( u ∗ − u ) ∥ Ω \lVert f-\mathcal{B}u\rVert_{\Omega}=\lVert\mathcal{B}(u^*-u)\rVert_{\Omega} ∥ f − B u ∥ Ω = ∥ B ( u ∗ − u ) ∥ Ω , (11) follows from (6) .
(ii) ⇒ \Rightarrow ⇒ (iii): The unique minimizer u ∗ u^* u ∗ of 1 2 ∥ f − B u ∥ Ω 2 \frac{1}{2}\lVert f-\mathcal{B}u\rVert_{\Omega}^2 2 1 ∥ f − B u ∥ Ω 2 must be a zero of the first variation of
( f − B u , f − B u ) Ω = ∥ f ∥ Ω 2 + ( B u , B u ) Ω − 2 ( f , B u ) Ω , (f-\mathcal{B}u,f-\mathcal{B}u)_{\Omega}=\lVert f\rVert_{\Omega}^2+(\mathcal{B}u,\mathcal{B}u)_{\Omega}-2(f,\mathcal{B}u)_{\Omega}, ( f − B u , f − B u ) Ω = ∥ f ∥ Ω 2 + ( B u , B u ) Ω − 2 ( f , B u ) Ω ,
and hence a solution of the normal equation (12) . Finally, every u ∈ U u\in\mathrm{U} u ∈ U can be written as u ∗ − u ′ u^*-u' u ∗ − u ′ for some u ′ ∈ U u'\in\mathrm{U} u ′ ∈ U . Thus, (11) says
c b ∥ u ∥ Ω ≤ ∥ B u ∥ , ∥ B u ∥ Ω ≤ C b ∥ u ∥ , c_b\lVert u\rVert_{\Omega}\leq\lVert\mathcal{B}u\rVert,\qquad\lVert\mathcal{B}u\rVert_{\Omega}\leq C_b\lVert u\rVert, c b ∥ u ∥ Ω ≤ ∥ B u ∥ , ∥ B u ∥ Ω ≤ C b ∥ u ∥ ,
which implies (iii) by definition of B ( ⋅ , ⋅ ) B(\cdot,\cdot) B ( ⋅ , ⋅ ) .
(iii) ⇒ \Rightarrow ⇒ (i): (iii) readily implies injectivity of B \mathcal{B} B . Suppose, B \mathcal{B} B was not surjective. Since B \mathcal{B} B has closed range, there must exist a g ∈ L 2 g\in L_2 g ∈ L 2 such that ( g , B u ) = 0 (g,\mathcal{B}u)=0 ( g , B u ) = 0 for all u ∈ U u\in\mathrm{U} u ∈ U . On the other hand, Lax-Milgram ensures that there exists a u g ∈ U ∖ { 0 } u_g\in\mathrm{U}\setminus\{0\} u g ∈ U ∖ { 0 } such that ( B u g , B v ) Ω = ( g , B v ) Ω (\mathcal{B}u_g,\mathcal{B}v)_{\Omega}=(g,\mathcal{B}v)_{\Omega} ( B u g , B v ) Ω = ( g , B v ) Ω for all v ∈ U v\in\mathrm{U} v ∈ U , whence c b 2 ∥ u g ∥ U ≤ ∥ B u g ∥ Ω = ( g , u g ) Ω = 0 c_b^2\lVert u_g\rVert_{\mathrm{U}}\leq\lVert\mathcal{B}u_g\rVert_{\Omega}=(g,u_g)_{\Omega}=0 c b 2 ∥ u g ∥ U ≤ ∥ B u g ∥ Ω = ( g , u g ) Ω = 0 , a contradiction. Hence, B \mathcal{B} B is surjective and thus bijective. By continuity of B ( ⋅ , ⋅ ) B(\cdot,\cdot) B ( ⋅ , ⋅ ) , B \mathcal{B} B is bounded. By the open mapping theorem, B − 1 : L 2 → U \mathcal{B}^{-1}:L_2\to\mathrm{U} B − 1 : L 2 → U is also bounded, whence (i) follows from the Babuška-Nečas Theorem. □ \square □
Remark 2.1. For convenience we have formulated (1) or (7) as a linear operator equation, i.e., the trial space U \mathrm{U} U already incorporates homogeneous essential boundary conditions. Depending on the specific problem at hand, inhomogeneous boundary conditions, can be either reduced to such a case by modifying the right hand side or by enlarging the operator by trace components when these traces map into an L 2 L_2 L 2 -space.
Proposition 2.1 offers, in principle, three ways of numerically solving B u = f \mathcal{B}u=f B u = f . Since normal equations square condition numbers, the first order formulation may be tempting. But since it is unsymmetric a discretization requires for any trial space U h ⊂ U U_h\subset\mathrm{U} U h ⊂ U a judiciously chosen test space V h ⊂ L 2 V_h\subset L_2 V h ⊂ L 2 . In the present case the optimal test space (in the sense that it inherits the inf-sup constant from the infinite dimensional formulation) is simply V h : = B U h V_h:=\mathcal{B}U_h V h := B U h so that one ends up with (12) .
A Classical Example
Let us briefly recall a by now familiar scenario where the above considerations apply, namely the classical Poisson problem: for g ∈ H − 1 ( Ω ) = ( H 0 1 ( Ω ) ) ′ g\in H^{-1}(\Omega)=(H_0^1(\Omega))' g ∈ H − 1 ( Ω ) = ( H 0 1 ( Ω ) ) ′ find u ∗ ∈ H 0 1 ( Ω ) u^*\in H_0^1(\Omega) u ∗ ∈ H 0 1 ( Ω ) such that
( ∇ u ∗ , ∇ v ) Ω = g ( v ) , v ∈ H 0 1 ( Ω ) , (13) (\nabla u^*,\nabla v)_{\Omega}=g(v),\qquad v\in H_0^1(\Omega), \tag*{(13)} ( ∇ u ∗ , ∇ v ) Ω = g ( v ) , v ∈ H 0 1 ( Ω ) , (13)
which is the weak formulation of − div ( a ∇ u ) = g -\operatorname{div}(a\nabla u)=g − div ( a ∇ u ) = g in Ω \Omega Ω with u ∣ ∂ Ω = 0 u|_{\partial\Omega}=0 u ∣ ∂ Ω = 0 . Of course, this prohibits taking an L 2 L_2 L 2 -type space as test space. But this changes when rewriting this second order equation as a first-order system. To that end, decomposing a general g ∈ H − 1 ( Ω ) = ( H 0 1 ( Ω ) ) ′ g\in H^{-1}(\Omega)=(H_0^1(\Omega))' g ∈ H − 1 ( Ω ) = ( H 0 1 ( Ω ) ) ′ as g = f 0 + div ζ g=f_0+\operatorname{div}\zeta g = f 0 + div ζ for some f 0 ∈ L 2 ( Ω ) f_0\in L_2(\Omega) f 0 ∈ L 2 ( Ω ) , ζ ∈ L 2 ( Ω ; R d ) \zeta\in L_2(\Omega;\mathbb{R}^d) ζ ∈ L 2 ( Ω ; R d ) , the second order equation can be written as a system of first order equations
σ − ∇ u = ζ , − div σ = f 0 . (14) \sigma-\nabla u=\zeta,\qquad-\operatorname{div}\sigma=f_0. \tag*{(14)} σ − ∇ u = ζ , − div σ = f 0 . (14)
Now one can seek u ∗ = [ σ ∗ , u ∗ ] ∈ U = H ( div ; Ω ) × H 0 1 ( Ω ) u^*=[\sigma^*,u^*]\in\mathrm{U}=H(\operatorname{div};\Omega)\times H_0^1(\Omega) u ∗ = [ σ ∗ , u ∗ ] ∈ U = H ( div ; Ω ) × H 0 1 ( Ω ) such that for f = [ ζ , f 0 ] ∈ L 2 ( Ω ; R d ) × L 2 ( Ω ) = L 2 f=[\zeta,f_0]\in L_2(\Omega;\mathbb{R}^d)\times L_2(\Omega)=L_2 f = [ ζ , f 0 ] ∈ L 2 ( Ω ; R d ) × L 2 ( Ω ) = L 2
( B u ∗ ) ( v ) = b ( u ∗ , v ) = b ( [ σ ∗ , u ∗ ] , [ τ , v ] ) : = ( σ ∗ − ∇ u ∗ , τ ) Ω − ( div σ ∗ , v ) Ω = ( f 0 , v ) Ω + ( ζ , τ ) Ω , ∀ v = [ τ , v ] ∈ L 2 , (15) \begin{aligned}
(\mathcal{B}u^*)(v)&=b(u^*,v)=b([\sigma^*,u^*],[\tau,v])\\
&:=(\sigma^*-\nabla u^*,\tau)_{\Omega}-(\operatorname{div}\sigma^*,v)_{\Omega}=(f_0,v)_{\Omega}+(\zeta,\tau)_{\Omega},\\
&\qquad\forall v=[\tau,v]\in L_2, \tag*{(15)}
\end{aligned} ( B u ∗ ) ( v ) = b ( u ∗ , v ) = b ([ σ ∗ , u ∗ ] , [ τ , v ]) := ( σ ∗ − ∇ u ∗ , τ ) Ω − ( div σ ∗ , v ) Ω = ( f 0 , v ) Ω + ( ζ , τ ) Ω , ∀ v = [ τ , v ] ∈ L 2 , (15)
i.e.,
B u ∗ = ( σ ∗ − ∇ u ∗ − div σ ∗ ) = ( ζ f 0 ) = : f . (16) \mathcal{B}u^*=\begin{pmatrix}\sigma^*-\nabla u^*\\-\operatorname{div}\sigma^*\end{pmatrix}=\begin{pmatrix}\zeta\\f_0\end{pmatrix}=:\mathbf{f}. \tag*{(16)} B u ∗ = ( σ ∗ − ∇ u ∗ − div σ ∗ ) = ( ζ f 0 ) =: f . (16)
In fact, it is shown in [4 ] that (ii) in Proposition 2.1 holds and hence, by Proposition 2.1, isomorphy of B : U → L 2 \mathcal{B}:\mathbb{U}\to L_2 B : U → L 2 , as well as the minimum residual characterization.
The solutions of (15) and the original problem (13) agree in the following sense. For the solution u ∗ ∈ H 0 1 ( Ω ) u^*\in H^1_0(\Omega) u ∗ ∈ H 0 1 ( Ω ) of (13) σ ∗ : = ∇ u ∗ \sigma^*:=\nabla u^* σ ∗ := ∇ u ∗ , u ∗ = u ∗ u^*=u^* u ∗ = u ∗ solves (15) , and conversely, see [4 , 9 ] .
As a key point, the setting considered in Section 2.1 is viable when dealing with first order systems. In fact, very similar results have meanwhile been established for first order formulations of linear elasticity, for the Stokes system, as well as for space-time formulations of the heat or wave equation, [6 , 7 ] which motivates the discussion on the proposed more general level.
Optimal Trial Norm
We adhere to the above notation and assume from now on that for a given Hilbert space U \mathbb{U} U , B ∈ L ( U , L 2 ) \mathcal{B}\in\mathcal{L}(\mathbb{U},L_2) B ∈ L ( U , L 2 ) is bijective so that all items in Proposition 2.1 are valid. We will make use of either of them whenever convenient. Thus, given f ∈ L 2 \mathbf{f}\in L_2 f ∈ L 2 , there exists then a unique u ∗ ∈ U u^*\in\mathbb{U} u ∗ ∈ U such that
B u ∗ = f (17) \mathcal{B}u^*=\mathbf{f} \tag*{(17)} B u ∗ = f (17)
in the sense of (9) . We are interested in devising an adaptive procedure for approximately solving (17) . Convergence analysis will be greatly simplified when working with one specific (equivalent) norm on U \mathbb{U} U which, of course, implies then convergence in any other equivalent norm. To be specific, due to (6) ,
∥ u ∥ U : = ∥ B u ∥ L 2 , u ∈ U , (18) \lVert u\rVert_{\mathbb{U}}:=\lVert\mathcal{B}u\rVert_{L_2},\qquad u\in\mathbb{U}, \tag*{(18)} ∥ u ∥ U := ∥ B u ∥ L 2 , u ∈ U , (18)
is an equivalent norm on U \mathbb{U} U , sometimes referred to as optimal trial norm , see e.g. [17 ] . Specifically, well-posedness of (15) is equivalent to saying that in this case
∥ [ σ , u ] ∥ H ( div ; Ω ) × H 0 1 ( Ω ) 2 = ∥ σ ∥ L 2 ( Ω ; R d ) 2 + ∥ div σ ∥ L 2 ( Ω ) 2 + ∥ ∇ u ∥ L 2 ( Ω ) 2 \lVert[\sigma,u]\rVert^2_{H(\operatorname{div};\Omega)\times H^1_0(\Omega)}
=\lVert\sigma\rVert^2_{L_2(\Omega;\mathbb{R}^d)}+\lVert\operatorname{div}\sigma\rVert^2_{L_2(\Omega)}+\lVert\nabla u\rVert^2_{L_2(\Omega)} ∥[ σ , u ] ∥ H ( div ; Ω ) × H 0 1 ( Ω ) 2 = ∥ σ ∥ L 2 ( Ω ; R d ) 2 + ∥ div σ ∥ L 2 ( Ω ) 2 + ∥ ∇ u ∥ L 2 ( Ω ) 2
≅ ∥ B [ σ , u ] ∥ L 2 ( Ω ; R d + 1 ) 2 = ∥ σ − a ∇ u ∥ L 2 ( Ω ; R d ) 2 + ∥ div σ ∥ L 2 ( Ω ) 2 , \cong\lVert\mathcal{B}[\sigma,u]\rVert^2_{L_2(\Omega;\mathbb{R}^{d+1})}
=\lVert\sigma-a\nabla u\rVert^2_{L_2(\Omega;\mathbb{R}^d)}+\lVert\operatorname{div}\sigma\rVert^2_{L_2(\Omega)}, ≅ ∥ B [ σ , u ] ∥ L 2 ( Ω ; R d + 1 ) 2 = ∥ σ − a ∇ u ∥ L 2 ( Ω ; R d ) 2 + ∥ div σ ∥ L 2 ( Ω ) 2 ,
holds for all [ σ , u ] ∈ H ( div ; Ω ) × H 0 1 ( Ω ) [\sigma,u]\in H(\operatorname{div};\Omega)\times H^1_0(\Omega) [ σ , u ] ∈ H ( div ; Ω ) × H 0 1 ( Ω ) . The reason for calling (18) optimal is that for this norm one has by definition ∥ B ∥ L ( U , L 2 ) = 1 \lVert\mathcal{B}\rVert_{\mathcal{L}(\mathbb{U},L_2)}=1 ∥ B ∥ L ( U , L 2 ) = 1 while also
inf u ∈ U sup v ∈ L 2 b ( u , v ) ∥ u ∥ U ∥ v ∥ L 2 = inf u ∈ U sup v ∈ L 2 ( B u , v ) Ω ∥ B u ∥ L 2 ∥ v ∥ L 2 = inf u ∈ U ∥ B u ∥ L 2 ∥ B u ∥ L 2 = 1 , \inf_{u\in\mathbb{U}}\sup_{v\in L_2}\frac{b(u,v)}{\lVert u\rVert_{\mathbb{U}}\lVert v\rVert_{L_2}}
=\inf_{u\in\mathbb{U}}\sup_{v\in L_2}\frac{(\mathcal{B}u,v)_{\Omega}}{\lVert\mathcal{B}u\rVert_{L_2}\lVert v\rVert_{L_2}}
=\inf_{u\in\mathbb{U}}\frac{\lVert\mathcal{B}u\rVert_{L_2}}{\lVert\mathcal{B}u\rVert_{L_2}}
=1, u ∈ U inf v ∈ L 2 sup ∥ u ∥ U ∥ v ∥ L 2 b ( u , v ) = u ∈ U inf v ∈ L 2 sup ∥ B u ∥ L 2 ∥ v ∥ L 2 ( B u , v ) Ω = u ∈ U inf ∥ B u ∥ L 2 ∥ B u ∥ L 2 = 1 ,
i.e., c b = C b = 1 c_b=C_b=1 c b = C b = 1 . Thus, B \mathcal{B} B is even an isometry (condition number equals one) and we have a tight error-residual relation
∥ u ∗ − u ∥ U = ∥ f − B u ∥ L 2 , u ∈ U . (19) \lVert u^*-u\rVert_{\mathbb{U}}=\lVert\mathbf{f}-\mathcal{B}u\rVert_{L_2},\qquad u\in\mathbb{U}. \tag*{(19)} ∥ u ∗ − u ∥ U = ∥ f − B u ∥ L 2 , u ∈ U . (19)
While the equivalence of the “optimal trial norm” (18) with an “original generic trial” ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ on U \mathbb{U} U - in the example from Section 2.2 ∥ [ σ , u ] ∥ 2 = ∥ σ ∥ H ( div ; Ω ) 2 + ∥ u ∥ H 1 ( Ω ) 2 \lVert[\sigma,u]\rVert^2=\lVert\sigma\rVert^2_{H(\operatorname{div};\Omega)}+\lVert u\rVert^2_{H^1(\Omega)} ∥[ σ , u ] ∥ 2 = ∥ σ ∥ H ( div ; Ω ) 2 + ∥ u ∥ H 1 ( Ω ) 2 - follows from well-posedness in the above sense, corresponding equivalence constants may strongly depend on the range of coefficients in B \mathcal{B} B or on near-degeneracies of the domain Ω \Omega Ω and may suggest specific scaling weights in different terms of the L 2 L_2 L 2 -residual. However, that does not affect the principal question of error reduction of cycles like (4) . Again, on the current level of generality, we cannot and don’t have to address this issue in what follows.
An Idealized Setting
Core Ingredients of an Adaptive Cycle
We denote by T \mathcal{T} T a generic partition of a given computational domain Ω \Omega Ω , subject to certain admissibility constraints, common in finite element methods. The precise specification of such conditions may depend on the underlying PDE model. They may require geometric conformity, meaning the intersection of the closure of adjacent cells must be a common facet of both cells. Admissibility may also allow for hanging nodes whose number per element facet may, however, be uniformly bounded. When viewing T \mathcal{T} T as an element of a collection T \mathbb{T} T of partitions, a typical further constraint is that the T \mathcal{T} T in T \mathbb{T} T are uniformly shape regular. We focus on nested hierarchies T = { T j } j ∈ N 0 \mathbb{T}=\{\mathcal{T}_j\}_{j\in\mathbb{N}_0} T = { T j } j ∈ N 0
T 0 ≺ T 1 ≺ ⋯ ≺ T n ≺ ⋯ (20) \mathcal{T}_0 \prec\mathcal{T}_1 \prec\cdots\prec\mathcal{T}_n \prec\cdots \tag*{(20)} T 0 ≺ T 1 ≺ ⋯ ≺ T n ≺ ⋯ (20)
where T j ≺ T j + 1 \mathcal{T}_j\prec\mathcal{T}_{j+1} T j ≺ T j + 1 means that T j + 1 \mathcal{T}_{j+1} T j + 1 arises from T j \mathcal{T}_j T j by subdividing some cells in T j \mathcal{T}_j T j according to a specific rule, possibly followed by closing refinements so as to preserve admissibility , see below for further comments in this regard. We use T ∈ T \mathcal{T}\in\mathbb{T} T ∈ T synonymously with saying T \mathcal{T} T is T \mathbb{T} T -admissible. We always assume that the specific partition T 0 j \mathcal{T}_0^j T 0 j , obtained by a j j j -fold subdivision of all cells in T 0 \mathcal{T}_0 T 0 , is T \mathbb{T} T -admissible. A prototype example is newest vertex bisection (or longest-edge-bisection ), see [3 , 23 ] .
With each T ∈ T \mathcal{T}\in\mathbb{T} T ∈ T we associate a finite element trial space U T ⊂ U \mathbb{U}_{\mathcal{T}}\subset\mathbb{U} U T ⊂ U . In the example of § 2.2 one would use H ( div ) H(\operatorname{div}) H ( div ) - and H 1 H^1 H 1 -conforming finite elements, see e.g. [12 , 13 ] . This gives then rise to a hierarchy of nested finite elements spaces
U T 0 ⊂ U T 1 ⊂ ⋯ ⊂ U T j ⊂ ⋯ . \mathbb{U}_{\mathcal{T}_0}\subset\mathbb{U}_{\mathcal{T}_1}\subset\cdots\subset\mathbb{U}_{\mathcal{T}_j}\subset\cdots. U T 0 ⊂ U T 1 ⊂ ⋯ ⊂ U T j ⊂ ⋯ .
For each T ∈ T \mathcal{T}\in\mathbb{T} T ∈ T let
u T = argmin u ∈ U T 1 2 ∥ f − B u ∥ Ω 2 , (21) u_{\mathcal{T}}=\underset{u\in\mathbb{U}_{\mathcal{T}}}{\operatorname{argmin}}\ \frac{1}{2}\lVert f-Bu\rVert_{\Omega}^{2}, \tag*{(21)} u T = u ∈ U T argmin 2 1 ∥ f − B u ∥ Ω 2 , (21)
which (by Proposition 2.1) is the solution of
( B u T , B v ) Ω = ( f , B v ) Ω , v ∈ U T . (22) (Bu_{\mathcal{T}},Bv)_{\Omega}=(f,Bv)_{\Omega},\quad v\in\mathbb{U}_{\mathcal{T}}. \tag*{(22)} ( B u T , B v ) Ω = ( f , B v ) Ω , v ∈ U T . (22)
For T = T j \mathcal{T}=\mathcal{T}_j T = T j we briefly write at times u j : = u T j u_j:=u_{\mathcal{T}_j} u j := u T j .
Denoting for any closed subspace U ^ ⊂ U \widehat{\mathbb{U}}\subset\mathbb{U} U ⊂ U by P U ^ P_{\widehat{\mathbb{U}}} P U the U \mathbb{U} U -orthogonal projection with respect to the optimal trial norm ∥ ⋅ ∥ U = ∥ B ⋅ ∥ Ω \lVert\cdot\rVert_{\mathbb{U}}=\lVert B\cdot\rVert_{\Omega} ∥ ⋅ ∥ U = ∥ B ⋅ ∥ Ω , (22) means in particular
u T = P U T u ∗ , (23) u_{\mathcal{T}}=P_{\mathbb{U}_{\mathcal{T}}}u^*, \tag*{(23)} u T = P U T u ∗ , (23)
where u ∗ u^* u ∗ consistently denotes the exact solution to (17) . We formalize this by the routine
Solve[ f , T ] → u T = u T ( f ) [f,\mathcal{T}]\to u_{\mathcal{T}}=u_{\mathcal{T}}(f) [ f , T ] → u T = u T ( f )
that generates the exact solution of the discrete system (22) .
This is a first instance of a strong “idealization” that will be adopted in a first version of an adaptive algorithm. In practice, neither can we solve (22) exactly nor can we generally compute the matrix and load vector in (22) exactly. It would be more realistic to talk about Solve[ f , T , δ ] [f,\mathcal{T},\delta] [ f , T , δ ] meaning that we only insist on solving the system within a prescribed tolerance δ > 0 \delta>0 δ > 0 , see e.g. [22 ] . We prefer to suppress such aspects for the moment for the sake of simplicity and clarity of exposition. Instead we refer to corresponding existing strategies e.g. to [22 ] , that apply in the present context as well.
We proceed formally specifying the ingredients of (4) as “routines”, beginning with marking the cells to be refined.
Mark[ T , u T , f , θ ] → K θ ( T , u T , f ) = K θ [\mathcal{T},u_{\mathcal{T}},f,\theta]\to\mathcal{K}_{\theta}(\mathcal{T},u_{\mathcal{T}},f)=\mathcal{K}_{\theta} [ T , u T , f , θ ] → K θ ( T , u T , f ) = K θ
We adopt in what follows Dörfler marking as the way to determine a subset K ⊂ T \mathcal{K}\subset\mathcal{T} K ⊂ T that should be refined. Namely fix θ ∈ ( 0 , 1 ) \theta\in(0,1) θ ∈ ( 0 , 1 ) and let K θ = K θ ( T ) \mathcal{K}_{\theta}=\mathcal{K}_{\theta}(\mathcal{T}) K θ = K θ ( T ) be a minimal subset of T \mathcal{T} T such that
∑ K ∈ K θ ∥ f − B u T ∥ K 2 ≥ θ ∥ f − B u T ∥ Ω 2 . (24) \sum_{\mathcal{K}\in\mathcal{K}_{\theta}}\lVert f-Bu_{\mathcal{T}}\rVert_{\mathcal{K}}^{2}\geq\theta\lVert f-Bu_{\mathcal{T}}\rVert_{\Omega}^{2}. \tag*{(24)} K ∈ K θ ∑ ∥ f − B u T ∥ K 2 ≥ θ ∥ f − B u T ∥ Ω 2 . (24)
Again, at this point this is an idealization because the element-residuals ∥ f − B u T ∥ K 2 \lVert f-Bu_{\mathcal{T}}\rVert_{\mathcal{K}}^{2} ∥ f − B u T ∥ K 2 are computed exactly. We call K θ \mathcal{K}_{\theta} K θ to be minimal if, up to a fixed multiplicative factor, # K θ ( T ) \#\mathcal{K}_{\theta}(\mathcal{T}) # K θ ( T ) is minimal among all collections satisfying (24) .
Clearly, abbreviating
Ω K : = interior ( ⋃ K ∈ K K ‾ ) , \Omega_{\mathcal K} := \operatorname{interior}\left(\bigcup_{K\in\mathcal K}\overline{K}\right), Ω K := interior ( K ∈ K ⋃ K ) ,
(24) implies
∥ f − B u T ∥ Ω K 2 ≥ θ ∥ f − B u T ∥ Ω 2 . (25) \lVert f-\mathcal{B}u_{\mathcal T}\rVert_{\Omega_{\mathcal K}}^2 \ge\theta\lVert f-\mathcal{B}u_{\mathcal T}\rVert_{\Omega}^2. \tag*{(25)} ∥ f − B u T ∥ Ω K 2 ≥ θ ∥ f − B u T ∥ Ω 2 . (25)
Once K θ \mathcal K_\theta K θ has been identified, the subsequent mesh refinement is based on several further ingredients.
Subd [ T , K ] → T K \operatorname{Subd}[\mathcal T,\mathcal K]\to\mathcal T_{\mathcal K} Subd [ T , K ] → T K
subdivides for a fixed number ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 times all cells in K ⊂ T \mathcal K\subset\mathcal T K ⊂ T according to the rule underlying T \mathcal T T . Since ℓ \ell ℓ remains fixed we suppress any notational reference.
The partition T ∨ T K \mathcal T\vee\mathcal T_{\mathcal K} T ∨ T K may not be admissible yet and may need to be closed in T \mathcal T T to restore admissibility.
The routine
Refine [ T , K ] → T r e f ( T , K ) , \operatorname{Refine}[\mathcal T,\mathcal K]\to\mathcal T_{\mathrm{ref}}(\mathcal T,\mathcal K), Refine [ T , K ] → T ref ( T , K ) ,
generates the smallest admissible refinement of T \mathcal T T that contains Subd [ T , K ] \operatorname{Subd}[\mathcal T,\mathcal K] Subd [ T , K ] . In particular, this gives rise to the refinement region
Ω r e f = Ω r e f ( T , K ) = interior ( ⋃ { K : K ∈ T r e f ∖ T } ) . \Omega_{\mathrm{ref}}=\Omega_{\mathrm{ref}}(\mathcal T,\mathcal K)=\operatorname{interior}\left(\bigcup\{K:K\in\mathcal T_{\mathrm{ref}}\setminus\mathcal T\}\right). Ω ref = Ω ref ( T , K ) = interior ( ⋃ { K : K ∈ T ref ∖ T } ) .
which is the union of subdivided cells in T \mathcal T T . Whenever T , K \mathcal T,\mathcal K T , K are clear from the context we briefly write Ω r e f \Omega_{\mathrm{ref}} Ω ref .
ALSM - an Idealized Version
We adhere to the above idealizing assumptions and abbreviate at times for convenience for any v ∈ U T v\in\mathbb U_{\mathcal T} v ∈ U T
R T ( v , f ) : = f − B v , and in particular R T : = R T ( u T , f ) . \mathcal R_{\mathcal T}(v,f):=f-\mathcal Bv,\qquad\text{and in particular}\qquad\mathcal R_{\mathcal T}:=\mathcal R_{\mathcal T}(u_{\mathcal T},f). R T ( v , f ) := f − B v , and in particular R T := R T ( u T , f ) .
To be concise we formalize (4) as follows:
Alsm-Ideal [ B , f , θ , ε ] → T ε , u ε ∈ U T ε : \operatorname{Alsm\text{-}Ideal}[\mathcal B,f,\theta,\varepsilon]\to\mathcal T_\varepsilon,\ u_\varepsilon\in\mathbb U_{\mathcal T_\varepsilon}: Alsm - Ideal [ B , f , θ , ε ] → T ε , u ε ∈ U T ε :
(A0) Choose T 0 \mathcal T_0 T 0 , fix θ , ε ∈ ( 0 , 1 ) \theta,\varepsilon\in(0,1) θ , ε ∈ ( 0 , 1 ) , ε > 0 \varepsilon>0 ε > 0 ; set 0 → u ˉ 0\to\bar u 0 → u ˉ , T 0 → T \mathcal T_0\to\mathcal T T 0 → T ;
(A1) compute ∥ f − B u ˉ ∥ Ω \lVert f-\mathcal B\bar u\rVert_\Omega ∥ f − B u ˉ ∥ Ω ; while ∥ f − B u ˉ ∥ Ω > ε \lVert f-\mathcal B\bar u\rVert_\Omega>\varepsilon ∥ f − B u ˉ ∥ Ω > ε apply Mark [ T , f , u ˉ , θ ] → K θ \operatorname{Mark}[\mathcal T,f,\bar u,\theta]\to\mathcal K_\theta Mark [ T , f , u ˉ , θ ] → K θ ; else, output T ε = T \mathcal T_\varepsilon=\mathcal T T ε = T , u ε = u ˉ u_\varepsilon=\bar u u ε = u ˉ ;
(A2) apply Refine [ T , K θ ] → T r e f \operatorname{Refine}[\mathcal T,\mathcal K_\theta]\to\mathcal T_{\mathrm{ref}} Refine [ T , K θ ] → T ref ;
(A3) Solve [ f , T r e f ] → u T r e f \operatorname{Solve}[f,\mathcal T_{\mathrm{ref}}]\to u_{\mathcal T_{\mathrm{ref}}} Solve [ f , T ref ] → u T ref ; set T r e f → T \mathcal T_{\mathrm{ref}}\to\mathcal T T ref → T , u T r e f → u ˉ u_{\mathcal T_{\mathrm{ref}}}\to\bar u u T ref → u ˉ and go to (A1).
Obviously, if the scheme terminates the output satisfies ∥ u ∗ − u ε ∥ U = ∥ f − B u T ε ∥ Ω ≤ ε \lVert u^*-u_\varepsilon\rVert_{\mathbb U}=\lVert f-\mathcal B u_{\mathcal T_\varepsilon}\rVert_\Omega\le\varepsilon ∥ u ∗ − u ε ∥ U = ∥ f − B u T ε ∥ Ω ≤ ε . Understanding whether or under which circumstances Alsm-Ideal terminates and how a corresponding convergence can be quantified, will pave the way to formulating and analyzing subsequent more practical versions.
What Can be Expected?
Error reduction and the “adaptive update”
We begin with the (very well-known) Galerkin orthogonality and its simple manifestation in the current setting
∥ u ∗ − u T r e f ∥ U 2 = ∥ u ∗ − u T ∥ U 2 − ∥ u T r e f − u T ∥ U 2 ≥ 0. (26) \lVert u^*-u_{\mathcal T_{\mathrm{ref}}}\rVert_{\mathbb U}^2=\lVert u^*-u_{\mathcal T}\rVert_{\mathbb U}^2-\lVert u_{\mathcal T_{\mathrm{ref}}}-u_{\mathcal T}\rVert_{\mathbb U}^2\ge0. \tag*{(26)} ∥ u ∗ − u T ref ∥ U 2 = ∥ u ∗ − u T ∥ U 2 − ∥ u T ref − u T ∥ U 2 ≥ 0. (26)
Hence for some s ∈ [ 0 , 1 ] s\in[0,1] s ∈ [ 0 , 1 ] one must have
∥ w T ∥ U 2 = s ∥ u ∗ − u T ∥ U 2 ⟺ ∥ u ∗ − u T r e f ∥ U 2 = ( 1 − s ) ∥ u ∗ − u T ∥ U 2 . (27) \lVert w_{\mathcal T}\rVert_{\mathbb U}^2=s\lVert u^*-u_{\mathcal T}\rVert_{\mathbb U}^2
\quad\Longleftrightarrow\quad
\lVert u^*-u_{\mathcal T_{\mathrm{ref}}}\rVert_{\mathbb U}^2=(1-s)\lVert u^*-u_{\mathcal T}\rVert_{\mathbb U}^2. \tag*{(27)} ∥ w T ∥ U 2 = s ∥ u ∗ − u T ∥ U 2 ⟺ ∥ u ∗ − u T ref ∥ U 2 = ( 1 − s ) ∥ u ∗ − u T ∥ U 2 . (27)
We record the following immediate consequence of (27) .
Remark 3.1. Adhering to the above notation, one has
∥ u ∗ − u T r e f ∥ U ≤ ρ ∥ u ∗ − u T ∥ U ⟺ ∥ u T − u T r e f ∥ U ≥ 1 − ρ 2 ∥ u ∗ − u T ∥ U . (28) \lVert u^* - u_{T_{\mathrm{ref}}} \rVert_U \le\rho\lVert u^* - u_T \rVert_U
\Longleftrightarrow
\lVert u_T - u_{T_{\mathrm{ref}}} \rVert_U \ge\sqrt{1-\rho^2}\lVert u^* - u_T \rVert_U. \tag*{(28)} ∥ u ∗ − u T ref ∥ U ≤ ρ ∥ u ∗ − u T ∥ U ⟺ ∥ u T − u T ref ∥ U ≥ 1 − ρ 2 ∥ u ∗ − u T ∥ U . (28)
In other words, the better the “adaptive update”
w T = w T ( f , T r e f ) : = u T r e f − u T (29) w_T = w_T(f,T_{\mathrm{ref}}) := u_{T_{\mathrm{ref}}} - u_T \tag*{(29)} w T = w T ( f , T ref ) := u T ref − u T (29)
aligns with u ∗ − u T u^* - u_T u ∗ − u T , the better the error reduction.
We’ll make repeated use of the relations
w T ⊥ U u ∗ − u T r e f , w T ⊥ U U T , (30) w_T \perp_U u^* - u_{T_{\mathrm{ref}}}, \qquad w_T \perp_U U_T, \tag*{(30)} w T ⊥ U u ∗ − u T ref , w T ⊥ U U T , (30)
which follow from the fact that, as solutions to (22) , u T u_T u T , u T r e f u_{T_{\mathrm{ref}}} u T ref , are the U-orthogonal projections of u ∗ u^* u ∗ to U T U_T U T , U T r e f U_{T_{\mathrm{ref}}} U T ref , respectively, see (23) .
The key is to understand under which circumstances ∥ w T ∥ U = ∥ B w T ∥ Ω \lVert w_T\rVert_U = \lVert Bw_T\rVert_\Omega ∥ w T ∥ U = ∥ B w T ∥ Ω captures a “substantial part” of the residual ∥ f − B u T ∥ Ω = ∥ u ∗ − u T ∥ U \lVert f-Bu_T\rVert_\Omega= \lVert u^*-u_T\rVert_U ∥ f − B u T ∥ Ω = ∥ u ∗ − u T ∥ U . To that end, the second relation in (30) suggests decomposing the refined space U T r e f = U T , T r e f ( K ) U_{T_{\mathrm{ref}}}=U_{T,T_{\mathrm{ref}}}(\mathcal{K}) U T ref = U T , T ref ( K ) as
U T r e f = U T ⊕ U W ℓ U_{T_{\mathrm{ref}}}=U_T\oplus_U W^\ell U T ref = U T ⊕ U W ℓ
where
W ℓ = W ℓ ( T ; T r e f ) : = P U T ⊥ U T r e f : = ( I − P U T ) U T r e f ⊥ U U T . (31) W^\ell= W^\ell(T;T_{\mathrm{ref}}) := P_{U_T}^{\perp}U_{T_{\mathrm{ref}}} := (I-P_{U_T})U_{T_{\mathrm{ref}}}\perp_U U_T. \tag*{(31)} W ℓ = W ℓ ( T ; T ref ) := P U T ⊥ U T ref := ( I − P U T ) U T ref ⊥ U U T . (31)
Notice further that, since U T ⊆ U T r e f U_T\subseteq U_{T_{\mathrm{ref}}} U T ⊆ U T ref , so that P U T P_{U_T} P U T and P U T r e f P_{U_{T_{\mathrm{ref}}}} P U T ref commute, i.e.,
( I − P U T ) U T r e f = ( I − P U T ) P U T r e f U = P U T r e f ( I − P U T ) P U T r e f U = ( P U T r e f − P U T ) U , (I-P_{U_T})U_{T_{\mathrm{ref}}}=(I-P_{U_T})P_{U_{T_{\mathrm{ref}}}}U=P_{U_{T_{\mathrm{ref}}}}(I-P_{U_T})P_{U_{T_{\mathrm{ref}}}}U=(P_{U_{T_{\mathrm{ref}}}}-P_{U_T})U, ( I − P U T ) U T ref = ( I − P U T ) P U T ref U = P U T ref ( I − P U T ) P U T ref U = ( P U T ref − P U T ) U ,
we see that P U T r e f − P U T P_{U_{T_{\mathrm{ref}}}}-P_{U_T} P U T ref − P U T is also a projector. Hence, we have
W ℓ = ( P U T r e f − P U T ) U = : P W ℓ U . (32) W^\ell=(P_{U_{T_{\mathrm{ref}}}}-P_{U_T})U=:P_{W^\ell}U. \tag*{(32)} W ℓ = ( P U T ref − P U T ) U =: P W ℓ U . (32)
Two Ways to look at the adaptive update w T w_T w T
First, it follows that
w T = ( P U T r e f − P U T ) u ∗ = ( P U T r e f − P U T ) ( I − P U T ) u ∗ = P W ℓ u ∗ , (33) w_T=(P_{U_{T_{\mathrm{ref}}}}-P_{U_T})u^*=(P_{U_{T_{\mathrm{ref}}}}-P_{U_T})(I-P_{U_T})u^*=P_{W^\ell}u^*, \tag*{(33)} w T = ( P U T ref − P U T ) u ∗ = ( P U T ref − P U T ) ( I − P U T ) u ∗ = P W ℓ u ∗ , (33)
that is, w T w_T w T is the U-projection of u ∗ u^* u ∗ to W ℓ W^\ell W ℓ .
On the other hand, it is at times convenient to interpret the update w T w_T w T as the solution to a variational problem, posed in W ℓ W^\ell W ℓ .
Remark 3.2. The correction w T ∈ W ℓ ⊂ U T r e f w_T\in W^\ell\subset U_{T_{\mathrm{ref}}} w T ∈ W ℓ ⊂ U T ref solves
( B w T , B v ) Ω = ( R T , B v ) Ω , v ∈ U T r e f , (34) (Bw_T,Bv)_\Omega=(R_T,Bv)_\Omega,\qquad v\in U_{T_{\mathrm{ref}}}, \tag*{(34)} ( B w T , B v ) Ω = ( R T , B v ) Ω , v ∈ U T ref , (34)
so that (see (31) and the second relation in (30) )
( B w T , B v T ) Ω = 0 , v T ∈ U T , (35) (Bw_T,Bv_T)_\Omega=0,\qquad v_T\in U_T, \tag*{(35)} ( B w T , B v T ) Ω = 0 , v T ∈ U T , (35)
and therefore
( B w T , B w ) Ω = ( f , B w ) Ω , w ∈ W ℓ . (36) (Bw_T,Bw)_\Omega=(f,Bw)_\Omega,\qquad w\in W^\ell. \tag*{(36)} ( B w T , B w ) Ω = ( f , B w ) Ω , w ∈ W ℓ . (36)
In particular
∥ w T ∥ U 2 = ( R T , B w T ) Ω = ( f , B w T ) Ω = ( u ∗ , w T ) U . (37) \lVert w_T\rVert_U^2=(R_T,Bw_T)_\Omega=(f,Bw_T)_\Omega=(u^*,w_T)_U. \tag*{(37)} ∥ w T ∥ U 2 = ( R T , B w T ) Ω = ( f , B w T ) Ω = ( u ∗ , w T ) U . (37)
Thus, how well B w T Bw_T B w T aligns with the residual in L 2 L_2 L 2 is equivalent to its alignment with just the data f f f .
Remark 3.3. It follows from (37) that whenever f f f happens to be L 2 \mathrm{L}_2 L 2 -orthogonal to B W T \mathcal{B}W_{\mathcal{T}} B W T , there is no error reduction at all. Since W ℓ W^\ell W ℓ is finite dimensional, this already shows that without any further condition on f ∈ L 2 f \in\mathrm{L}_2 f ∈ L 2 , one cannot exclude that for any finite subdivision depth ℓ ∈ N \ell\in\mathbb{N} ℓ ∈ N in Subdiv \operatorname{Subdiv} Subdiv , the “extreme” case
f ⊥ L 2 B W ℓ (38) f \perp_{\mathrm{L}_2} \mathcal{B}W^\ell \tag*{(38)} f ⊥ L 2 B W ℓ (38)
could happen preventing any error reduction. By the same token, error reduction can be arbitrarily weak when the angle between f f f and B W ℓ \mathcal{B}W^\ell B W ℓ is small which may be the case even when f f f is pointwise very smooth.
Data-Visibility
Intuitively, one expects that (38) won’t happen, or that the angle between f f f and W ℓ W^\ell W ℓ eventually gets smaller, if ℓ \ell ℓ - hence W ℓ W^\ell W ℓ - is sufficiently large. To put this thought into proper perspective, we introduce certain subspaces of U \mathbb{U} U , associated with subdomains Ω ′ ⊂ Ω \Omega' \subset\Omega Ω ′ ⊂ Ω (typically unions of cells in some partition from T \mathcal{T} T ). Specifically, we denote by U ( Ω ′ ) \mathbb{U}(\Omega') U ( Ω ′ ) the following closed subspace of U = U ( Ω ) \mathbb{U} = \mathbb{U}(\Omega) U = U ( Ω ) :
U ( Ω ′ ) : = { u ∈ U : χ Ω ′ u ∈ U } . (39) \mathbb{U}(\Omega') := \{u \in\mathbb{U} : \chi_{\Omega'}u \in\mathbb{U}\}. \tag*{(39)} U ( Ω ′ ) := { u ∈ U : χ Ω ′ u ∈ U } . (39)
In other words, U ( Ω ′ ) \mathbb{U}(\Omega') U ( Ω ′ ) is comprised of those u ∈ U u \in\mathbb{U} u ∈ U whose trivial extension by zero to Ω ∖ Ω ′ \Omega\setminus\Omega' Ω ∖ Ω ′ still belongs to U \mathbb{U} U . We call a subdomain Ω ′ ⊂ Ω \Omega' \subset\Omega Ω ′ ⊂ Ω regular if (12) is well-posed on U ( Ω ′ ) \mathbb{U}(\Omega') U ( Ω ′ ) for any g ∈ L 2 ( Ω ′ ) g \in\mathrm{L}_2(\Omega') g ∈ L 2 ( Ω ′ ) , e.g. for g = f ∣ Ω ′ g = f|_{\Omega'} g = f ∣ Ω ′ when f ∈ L 2 f \in\mathrm{L}_2 f ∈ L 2 . In particular, simply connected unions of cells in T \mathcal{T} T or disjoint unions of such connected subdomains are regular.
In addition, for any partitions T ≺ T ′ \mathcal{T} \prec\mathcal{T}' T ≺ T ′ in T \mathcal{T} T we will frequently work with the subspaces
U ( Ω ′ ; T ′ ) : = U ( Ω ′ ) ∩ U T ′ , U T ( Ω ′ ) : = U T + U ( Ω ′ ) , \mathbb{U}(\Omega';\mathcal{T}') := \mathbb{U}(\Omega') \cap\mathbb{U}_{\mathcal{T}'}, \qquad\mathbb{U}_{\mathcal{T}}(\Omega') := \mathbb{U}_{\mathcal{T}} + \mathbb{U}(\Omega'), U ( Ω ′ ; T ′ ) := U ( Ω ′ ) ∩ U T ′ , U T ( Ω ′ ) := U T + U ( Ω ′ ) ,
U T ( Ω ′ ; T ′ ) = U T + U ( Ω ′ ; T ′ ) . (40) \mathbb{U}_{\mathcal{T}}(\Omega';\mathcal{T}') = \mathbb{U}_{\mathcal{T}} + \mathbb{U}(\Omega';\mathcal{T}'). \tag*{(40)} U T ( Ω ′ ; T ′ ) = U T + U ( Ω ′ ; T ′ ) . (40)
Specifically, we can write in these terms
U T r e f = U T ⊕ U W ℓ = U T + U ( Ω r e f ; T r e f ) = U T ( Ω r e f ; T r e f ) . (41) \mathbb{U}_{\mathcal{T}_{\mathrm{ref}}} = \mathbb{U}_{\mathcal{T}} \oplus_{\mathbb{U}} W^\ell= \mathbb{U}_{\mathcal{T}} + \mathbb{U}(\Omega_{\mathrm{ref}};\mathcal{T}_{\mathrm{ref}}) = \mathbb{U}_{\mathcal{T}}(\Omega_{\mathrm{ref}};\mathcal{T}_{\mathrm{ref}}). \tag*{(41)} U T ref = U T ⊕ U W ℓ = U T + U ( Ω ref ; T ref ) = U T ( Ω ref ; T ref ) . (41)
which is obviously contained in
U T + U ( Ω r e f ) = U T ( Ω r e f ) , (42) \mathbb{U}_{\mathcal{T}} + \mathbb{U}(\Omega_{\mathrm{ref}}) = \mathbb{U}_{\mathcal{T}}(\Omega_{\mathrm{ref}}), \tag*{(42)} U T + U ( Ω ref ) = U T ( Ω ref ) , (42)
This latter space can be formally viewed as resulting form letting the refinement depth ℓ \ell ℓ tend to infinity on Ω r e f \Omega_{\mathrm{ref}} Ω ref . Now, in analogy to (31) , let
W ∞ : = ( I − P T ) U T ( Ω r e f ) = ( P U T ( Ω r e f ) − P U T ) U = ( I − P T ) U ( Ω r e f ) , (43) W^\infty:= (I-P_{\mathcal{T}})\mathbb{U}_{\mathcal{T}}(\Omega_{\mathrm{ref}}) = (P_{\mathbb{U}_{\mathcal{T}}(\Omega_{\mathrm{ref}})} - P_{\mathbb{U}_{\mathcal{T}}})\mathbb{U} = (I-P_{\mathcal{T}})\mathbb{U}(\Omega_{\mathrm{ref}}), \tag*{(43)} W ∞ := ( I − P T ) U T ( Ω ref ) = ( P U T ( Ω ref ) − P U T ) U = ( I − P T ) U ( Ω ref ) , (43)
which obviously contains W ℓ W^\ell W ℓ for every ℓ ∈ N \ell\in\mathbb{N} ℓ ∈ N .
We are now prepared, to introduce a notion that quantifies how “visible” f f f - hence the residual f − B u T f-\mathcal{B}u_{\mathcal{T}} f − B u T - is by B W ℓ \mathcal{B}W^\ell B W ℓ :
vis T ( f , W ℓ ) : = sup u ∈ U ( f , B ( P W ∞ − P W ℓ ) u ) Ω ∥ B u ∥ Ω = ∥ ( P W ∞ − P W ℓ ) B ′ f ∥ U ′ . (44) \operatorname{vis}_{\mathcal{T}}(f,W^\ell) := \sup_{u\in\mathbb{U}} \frac{(f,\mathcal{B}(P_{W^\infty}-P_{W^\ell})u)_\Omega}{\|\mathcal{B}u\|_\Omega} = \|(P_{W^\infty}-P_{W^\ell})\mathcal{B}'f\|_{\mathbb{U}' }. \tag*{(44)} vis T ( f , W ℓ ) := u ∈ U sup ∥ B u ∥ Ω ( f , B ( P W ∞ − P W ℓ ) u ) Ω = ∥ ( P W ∞ − P W ℓ ) B ′ f ∥ U ′ . (44)
Obviously, vis T ( f , W ℓ ) \operatorname{vis}_{\mathcal{T}}(f,W^\ell) vis T ( f , W ℓ ) is large when ( P W ℓ ′ B ′ f ) ( w ) = ( f , B w ) Ω (P_{W^\ell}'\mathcal{B}'f)(w)=(f,\mathcal{B}w)_\Omega ( P W ℓ ′ B ′ f ) ( w ) = ( f , B w ) Ω is small for each w ∈ W ℓ w\in W^\ell w ∈ W ℓ .
There is an obvious alternate characterization of vis T ( f , W ℓ ) \operatorname{vis}_{\mathcal{T}}(f,W^\ell) vis T ( f , W ℓ ) as a projection error.
Lemma 3.1. One has
vis T ( f , W ℓ ) = ∥ ( P W ∞ − P W ℓ ) u ∗ ∥ U = ( R T , B ( P W ∞ − P W ℓ ) u ∗ ) Ω ∥ ( P W ∞ − P W ℓ ) u ∗ ∥ U . (45) \operatorname{vis}_{\mathcal{T}}(f,W^\ell) = \|(P_{W^\infty}-P_{W^\ell})u^*\|_{\mathbb{U}} = \frac{(\mathcal{R}_{\mathcal{T}},\mathcal{B}(P_{W^\infty}-P_{W^\ell})u^*)_\Omega}{\|(P_{W^\infty}-P_{W^\ell})u^*\|_{\mathbb{U}}}. \tag*{(45)} vis T ( f , W ℓ ) = ∥ ( P W ∞ − P W ℓ ) u ∗ ∥ U = ∥ ( P W ∞ − P W ℓ ) u ∗ ∥ U ( R T , B ( P W ∞ − P W ℓ ) u ∗ ) Ω . (45)
Proof. For each u ∈ U u\in\mathbb{U} u ∈ U one has
( f , B ( P W ∞ − P W ℓ ) u ) Ω ∥ u ∥ U = ( u ∗ , ( P W ∞ − P W ℓ ) u ) U ∥ u ∥ U ≤ ( u ∗ , ( P W ∞ − P W ℓ ) u ) U ∥ ( P W ∞ − P W ℓ ) u ∥ U , \frac{(f,\mathcal{B}(P_{W^\infty}-P_{W^\ell})u)_\Omega}{\|u\|_{\mathbb{U}}}
=
\frac{(u^*,(P_{W^\infty}-P_{W^\ell})u)_{\mathbb{U}}}{\|u\|_{\mathbb{U}}}
\le
\frac{(u^*,(P_{W^\infty}-P_{W^\ell})u)_{\mathbb{U}}}{\|(P_{W^\infty}-P_{W^\ell})u\|_{\mathbb{U}}}, ∥ u ∥ U ( f , B ( P W ∞ − P W ℓ ) u ) Ω = ∥ u ∥ U ( u ∗ , ( P W ∞ − P W ℓ ) u ) U ≤ ∥ ( P W ∞ − P W ℓ ) u ∥ U ( u ∗ , ( P W ∞ − P W ℓ ) u ) U ,
which shows that vis T ( f , W ℓ ) ≤ ∥ ( P W ∞ − P W ℓ ) u ∗ ∥ U \operatorname{vis}_{T}(f,\mathbb{W}^{\ell}) \le\lVert(P_{\mathbb{W}^{\infty}}-P_{\mathbb{W}^{\ell}})u^{*}\rVert_{\mathbb{U}} vis T ( f , W ℓ ) ≤ ∥( P W ∞ − P W ℓ ) u ∗ ∥ U . On the other hand, by similar arguments
sup u ∈ U ( f , B ( P W ∞ − P W ℓ ) u ) Ω ∥ u ∥ U ≥ ( f , B ( P W ∞ − P W ℓ ) u ∗ ) Ω ∥ ( P W ∞ − P W ℓ ) u ∗ ∥ U = ∥ ( P W ∞ − P W ℓ ) u ∗ ∥ U , \sup_{u\in\mathbb{U}}\frac{(f,B(P_{\mathbb{W}^{\infty}}-P_{\mathbb{W}^{\ell}})u)_{\Omega}}{\lVert u\rVert_{\mathbb{U}}}\geq\frac{(f,B(P_{\mathbb{W}^{\infty}}-P_{\mathbb{W}^{\ell}})u^{*})_{\Omega}}{\lVert(P_{\mathbb{W}^{\infty}}-P_{\mathbb{W}^{\ell}})u^{*}\rVert_{\mathbb{U}}}=\lVert(P_{\mathbb{W}^{\infty}}-P_{\mathbb{W}^{\ell}})u^{*}\rVert_{\mathbb{U}}, u ∈ U sup ∥ u ∥ U ( f , B ( P W ∞ − P W ℓ ) u ) Ω ≥ ∥( P W ∞ − P W ℓ ) u ∗ ∥ U ( f , B ( P W ∞ − P W ℓ ) u ∗ ) Ω = ∥( P W ∞ − P W ℓ ) u ∗ ∥ U ,
proving the claim since ( f , B ( P W ∞ − P W ℓ ) u ) Ω = ( R T , B ( P W ∞ − P W ℓ ) u ) Ω (f,B(P_{\mathbb{W}^{\infty}}-P_{\mathbb{W}^{\ell}})u)_{\Omega}=(\mathcal{R}_{T},B(P_{\mathbb{W}^{\infty}}-P_{\mathbb{W}^{\ell}})u)_{\Omega} ( f , B ( P W ∞ − P W ℓ ) u ) Ω = ( R T , B ( P W ∞ − P W ℓ ) u ) Ω .
The quantity vis T ( f , W ℓ ) \operatorname{vis}_{T}(f,\mathbb{W}^{\ell}) vis T ( f , W ℓ ) formally resembles what one may call data-oscillation of f f f . It is, however, closely tied to the current refinement region Ω r e f \Omega_{\mathrm{ref}} Ω ref .
An Idealized Convergence Result
The scheme Alsm-Ideal from § 3.2 gives rise to a sequence of quantities which are denoted throughout the remainder of this section as follows:
( T j ) j ∈ N 0 (\mathcal{T}_{j})_{j\in\mathbb{N}_{0}} ( T j ) j ∈ N 0 : hierarchy of nested partitions;
u j = u T j ∈ U j : = U T j u_{j}=u_{\mathcal{T}_{j}}\in\mathbb{U}_{j}:=\mathbb{U}_{\mathcal{T}_{j}} u j = u T j ∈ U j := U T j : associated discrete solutions, ( T j = T → T r e f = T j + 1 ) (\mathcal{T}_{j}=\mathcal{T}\to\mathcal{T}_{\mathrm{ref}}=\mathcal{T}_{j+1}) ( T j = T → T ref = T j + 1 ) , j ∈ N 0 j\in\mathbb{N}_{0} j ∈ N 0 ;
W j ℓ : = W ℓ ( T j , T j + 1 ) \mathbb{W}^{\ell}_{j}:=\mathbb{W}^{\ell}(\mathcal{T}_{j},\mathcal{T}_{j+1}) W j ℓ := W ℓ ( T j , T j + 1 ) , see (31) .
Theorem 3.2. We adhere to previous notation.
(a) Given θ ∈ ( 0 , 1 ) \theta\in(0,1) θ ∈ ( 0 , 1 ) , then, the output u T r e f u_{\mathcal{T}_{\mathrm{ref}}} u T ref of a single cycle of Alsm-Ideal satisfies
∥ u ∗ − u T r e f ∥ U 2 ≤ ( 1 − θ ) 1 / 2 ∥ u ∗ − u T ∥ U 2 + vis T ( f , W ℓ ) 2 (46) \lVert u^{*}-u_{\mathcal{T}_{\mathrm{ref}}}\rVert_{\mathbb{U}}^{2}\leq(1-\theta)^{1/2}\lVert u^{*}-u_{\mathcal{T}}\rVert_{\mathbb{U}}^{2}+\operatorname{vis}_{\mathcal{T}}(f,\mathbb{W}^{\ell})^{2} \tag*{(46)} ∥ u ∗ − u T ref ∥ U 2 ≤ ( 1 − θ ) 1/2 ∥ u ∗ − u T ∥ U 2 + vis T ( f , W ℓ ) 2 (46) (b) If there exists a constant C 0 < ∞ C_{0}<\infty C 0 < ∞ for which
∑ j = k ∞ vis T j ( W j ℓ ; f ) 2 ≤ C 0 ∥ R T k ∥ Ω 2 , k ∈ N 0 , (47) \sum_{j=k}^{\infty}\operatorname{vis}_{\mathcal{T}_{j}}(\mathbb{W}^{\ell}_{j};f)^{2}\leq C_{0}\lVert\mathcal{R}_{\mathcal{T}_{k}}\rVert_{\Omega}^{2},\qquad k\in\mathbb{N}_{0}, \tag*{(47)} j = k ∑ ∞ vis T j ( W j ℓ ; f ) 2 ≤ C 0 ∥ R T k ∥ Ω 2 , k ∈ N 0 , (47) holds uniformly in k ∈ N 0 k\in\mathbb{N}_{0} k ∈ N 0 , then there exists a fixed m ∈ N m\in\mathbb{N} m ∈ N and a ρ ∈ ( 0 , 1 ) \rho\in(0,1) ρ ∈ ( 0 , 1 ) , depending only on θ \theta θ , ℓ \ell ℓ , and C 0 C_{0} C 0 such that
∥ u ∗ − u j + m ∥ U ≤ ρ ∥ u ∗ − u j ∥ U , j ∈ N 0 . (48) \lVert u^{*}-u_{j+m}\rVert_{\mathbb{U}}\leq\rho\lVert u^{*}-u_{j}\rVert_{\mathbb{U}},\qquad j\in\mathbb{N}_{0}. \tag*{(48)} ∥ u ∗ − u j + m ∥ U ≤ ρ ∥ u ∗ − u j ∥ U , j ∈ N 0 . (48) Of course, (48) can be rephrased as: there exists a constant C 1 C_{1} C 1 , depending only on m , ρ m,\rho m , ρ such that for ρ ~ = ρ 1 / m < 1 \widetilde{\rho}=\rho^{1/m}<1 ρ = ρ 1/ m < 1
∥ u ∗ − u n ∥ U ≤ C 1 ρ ~ n ∥ f ∥ Ω , n ∈ N . (49) \lVert u^{*}-u_{n}\rVert_{\mathbb{U}}\leq C_{1}\widetilde{\rho}^{n}\lVert f\rVert_{\Omega},\qquad n\in\mathbb{N}. \tag*{(49)} ∥ u ∗ − u n ∥ U ≤ C 1 ρ n ∥ f ∥ Ω , n ∈ N . (49) Remark 3.4. The linear error reduction, up to the data-visibility term, (46) is in this form unsatisfactory because it is not clear yet that vis T ( f , W ℓ ) \operatorname{vis}_{T}(f,\mathbb{W}^{\ell}) vis T ( f , W ℓ ) is small when f f f is smooth. So the question is under which assumptions on f f f is vis T ( f , W ℓ ) \operatorname{vis}_{T}(f,\mathbb{W}^{\ell}) vis T ( f , W ℓ ) dominated by the residual, which motivates the subsequent reasoning.
Proof of Theorem 3.2
We proceed collecting a few technical prerequisites.
Further elementary properties of vis T ( f , W ℓ ) \operatorname{vis}_{T}(f,\mathbb{W}^{\ell}) vis T ( f , W ℓ )
Note that for any w ∈ W ∞ w\in\mathbb{W}^{\infty} w ∈ W ∞ one has ( R T , B w ) Ω = ( f , B w ) Ω = ( u ∗ , w ) U (\mathcal{R}_{T},Bw)_{\Omega}=(f,Bw)_{\Omega}=(u^{*},w)_{\mathbb{U}} ( R T , B w ) Ω = ( f , B w ) Ω = ( u ∗ , w ) U . The definition (43) of W ∞ \mathbb{W}^{\infty} W ∞ suggests then considering the “infinite-counterpart” of w T w_{T} w T , namely the projection of u ∗ u^{*} u ∗ to W ∞ \mathbb{W}^{\infty} W ∞
w T ∗ : = ( I − P U T ) P U T ( Ω r e f ) u ∗ = P U T ( Ω r e f ) ( I − P U T ) u ∗ = P W ∞ u ∗ ∈ W ∞ . (50) w_{T}^{*}:=(I-P_{\mathbb{U}_{T}})P_{\mathbb{U}_{T}(\Omega_{\mathrm{ref}})}u^{*}=P_{\mathbb{U}_{T}(\Omega_{\mathrm{ref}})}(I-P_{\mathbb{U}_{T}})u^{*}=P_{\mathbb{W}^{\infty}}u^{*}\in\mathbb{W}^{\infty}. \tag*{(50)} w T ∗ := ( I − P U T ) P U T ( Ω ref ) u ∗ = P U T ( Ω ref ) ( I − P U T ) u ∗ = P W ∞ u ∗ ∈ W ∞ . (50)
This gives rise to the following analog to Remark 3.2.
Remark 3.5. Adhering to the above notation, w T ∗ w_{T}^{*} w T ∗ solves the variational problem in U T ( Ω r e f ) \mathbb{U}_{T}(\Omega_{\mathrm{ref}}) U T ( Ω ref ) :
( B w T ∗ , B v ) Ω = ( R T , B v ) Ω , v ∈ U T ( Ω r e f ) . (51) (Bw_{T}^{*},Bv)_{\Omega}=(\mathcal{R}_{T},Bv)_{\Omega},\qquad v\in\mathbb{U}_{T}(\Omega_{\mathrm{ref}}). \tag*{(51)} ( B w T ∗ , B v ) Ω = ( R T , B v ) Ω , v ∈ U T ( Ω ref ) . (51)
Moreover, one has
∥ w T ∗ ∥ U 2 = ∥ B w T ∗ ∥ Ω 2 = ( R T , B w T ∗ ) Ω = ∥ P W ∞ u ∗ ∥ U 2 , (52) \lVert w_{T}^{*}\rVert_{\mathbb{U}}^{2}=\lVert Bw_{T}^{*}\rVert_{\Omega}^{2}=(\mathcal{R}_{T},Bw_{T}^{*})_{\Omega}=\lVert P_{\mathbb{W}^{\infty}}u^{*}\rVert_{\mathbb{U}}^{2}, \tag*{(52)} ∥ w T ∗ ∥ U 2 = ∥ B w T ∗ ∥ Ω 2 = ( R T , B w T ∗ ) Ω = ∥ P W ∞ u ∗ ∥ U 2 , (52)
i.e. the U \mathbb{U} U -energy of the “infinitely refined update agrees with the one of the projection of u ∗ u^{*} u ∗ to W ∞ \mathbb{W}^{\infty} W ∞ .
Proof. Regarding (51) ,
( R T , B v ) Ω = ( u ∗ − u T , v ) U = ( u ∗ , ( I − P U T ) P U T ( Ω r e f ) v ) U = (3.24) ( u ∗ , P W ∞ v ) U = ( P W ∞ u ∗ , v ) U = ( B w T ∗ , B v ) Ω , v ∈ U T ( Ω r e f ) , \begin{aligned}
(\mathcal{R}_T,\mathcal{B}v)_\Omega=(u^*-u_T,v)_U=(u^*,(I-P_{U_T})P_{U_T(\Omega_{\mathrm{ref}})}v)_U={}^{\text{(3.24)}}(u^*,P_{\mathbb{W}^\infty}v)_U \\
&=(P_{\mathbb{W}^\infty}u^*,v)_U=(\mathcal{B}w_T^*,\mathcal{B}v)_\Omega,\qquad v\in U_T(\Omega_{\mathrm{ref}}),
\end{aligned} ( R T , B v ) Ω = ( u ∗ − u T , v ) U = ( u ∗ , ( I − P U T ) P U T ( Ω ref ) v ) U = (3.24) ( u ∗ , P W ∞ v ) U = ( P W ∞ u ∗ , v ) U = ( B w T ∗ , B v ) Ω , v ∈ U T ( Ω ref ) ,
which also gives (52) upon taking v = w T ∗ ∈ W ∞ ⊂ U T ( Ω r e f ) v=w_T^*\in\mathbb{W}^\infty\subset U_T(\Omega_{\mathrm{ref}}) v = w T ∗ ∈ W ∞ ⊂ U T ( Ω ref ) .
Data visibility and residuals
The quantity vis T ( f , W ℓ ) \operatorname{vis}_T(f,W^\ell) vis T ( f , W ℓ ) always bounds the current residual, hence the error, from below.
To see this, recall from Lemma 3.1 that
vis T ( f , W ℓ ) = ∥ ( P W ∞ − P W ℓ ) u ∗ ∥ U = ( R T , B ( I − P W ℓ ) P W ∞ u ∗ ) Ω ∥ ( P W ∞ − P W ℓ ) u ∗ ∥ U ≤ ∥ R T ∥ Ω , \begin{aligned}
\operatorname{vis}_T(f,W^\ell)=\lVert(P_{\mathbb{W}^\infty}-P_{W^\ell})u^*\rVert_U=\frac{(\mathcal{R}_T,\mathcal{B}(I-P_{W^\ell})P_{\mathbb{W}^\infty}u^*)_\Omega}{\lVert(P_{\mathbb{W}^\infty}-P_{W^\ell})u^*\rVert_U} \\
&\leq\lVert\mathcal{R}_T\rVert_\Omega,
\end{aligned} vis T ( f , W ℓ ) = ∥( P W ∞ − P W ℓ ) u ∗ ∥ U = ∥( P W ∞ − P W ℓ ) u ∗ ∥ U ( R T , B ( I − P W ℓ ) P W ∞ u ∗ ) Ω ≤ ∥ R T ∥ Ω ,
whence the assertion follows.
The key to strict error reduction lies in tightening (54) .
Lemma 3.3. Every z ∈ U T ( Ω r e f ) ⊥ z\in U_T(\Omega_{\mathrm{ref}})^\perp z ∈ U T ( Ω ref ) ⊥ must satisfy
supp B z ⊆ Ω r e f ‾ c . (55) \operatorname{supp}\mathcal{B}z\subseteq\overline{\Omega_{\mathrm{ref}}}^{\,c}. \tag*{(55)} supp B z ⊆ Ω ref c . (55) Proof. Every u ~ ∈ U T ( Ω r e f ) \widetilde{u}\in U_T(\Omega_{\mathrm{ref}}) u ∈ U T ( Ω ref ) can be written as u ~ = v T + u Ω r e f \widetilde{u}=v_T+u_{\Omega_{\mathrm{ref}}} u = v T + u Ω ref , where v T ∈ U T v_T\in U_T v T ∈ U T and u Ω r e f ∈ U ( Ω r e f ) u_{\Omega_{\mathrm{ref}}}\in U(\Omega_{\mathrm{ref}}) u Ω ref ∈ U ( Ω ref ) . Since z ∈ U T ( Ω r e f ) ⊥ z\in U_T(\Omega_{\mathrm{ref}})^\perp z ∈ U T ( Ω ref ) ⊥ , meaning that z ⊥ W ∞ z\perp\mathbb{W}^\infty z ⊥ W ∞ and z ⊥ U T z\perp U_T z ⊥ U T , one obtains
0 = ( z , u ~ ) U = ( z , u Ω r e f ) U = ( B z , B u Ω r e f ) Ω . 0=(z,\widetilde{u})_U=(z,u_{\Omega_{\mathrm{ref}}})_U=(\mathcal{B}z,\mathcal{B}u_{\Omega_{\mathrm{ref}}})_\Omega. 0 = ( z , u ) U = ( z , u Ω ref ) U = ( B z , B u Ω ref ) Ω . Since Ω r e f \Omega_{\mathrm{ref}} Ω ref is a regular polygonal domain B \mathcal{B} B maps U ( Ω r e f ) U(\Omega_{\mathrm{ref}}) U ( Ω ref ) onto L 2 ( Ω r e f ) L_2(\Omega_{\mathrm{ref}}) L 2 ( Ω ref ) , which confirms the claim.
We are now prepared to establish the following key facts.
Proposition 3.8. Given θ ∈ ( 0 , 1 ) \theta\in(0,1) θ ∈ ( 0 , 1 ) , let ξ = ξ ( θ ) \xi=\xi(\theta) ξ = ξ ( θ ) be defined by
ξ : = ( 1 − ( 1 − θ ) 1 / 2 ) 1 / 2 . (56) \xi:=\left(1-(1-\theta)^{1/2}\right)^{1/2}. \tag*{(56)} ξ := ( 1 − ( 1 − θ ) 1/2 ) 1/2 . (56) Then
∥ B w T ∗ ∥ Ω ≥ ξ ∥ R T ∥ Ω , (57) \lVert\mathcal{B}w_T^*\rVert_\Omega\geq\xi\lVert\mathcal{R}_T\rVert_\Omega, \tag*{(57)} ∥ B w T ∗ ∥ Ω ≥ ξ ∥ R T ∥ Ω , (57) while
∥ B w T ∥ Ω 2 ≥ ξ 2 ∥ R T ∥ Ω 2 − vis T ( f , W ℓ ) 2 . (58) \lVert\mathcal{B}w_T\rVert_\Omega^2\geq\xi^2\lVert\mathcal{R}_T\rVert_\Omega^2-\operatorname{vis}_T(f,W^\ell)^2. \tag*{(58)} ∥ B w T ∥ Ω 2 ≥ ξ 2 ∥ R T ∥ Ω 2 − vis T ( f , W ℓ ) 2 . (58)
Note that, while the alignment of the “infinite increment” w T ∗ w_T^* w T ∗ with u ∗ − u T u^*-u_T u ∗ − u T depends only on the bulk constant θ \theta θ , the alignment of the adaptive update w T w_T w T with u ∗ − u T u^*-u_T u ∗ − u T , which is our primary concern, depends also on vis T ( f , W ℓ ) \operatorname{vis}_T(f,W^\ell) vis T ( f , W ℓ ) .
Proof. Abbreviate e T ∗ : = u ∗ − u T e_T^*:=u^*-u_T e T ∗ := u ∗ − u T and recall from (50) that
w T ∗ : = ( I − P U T ) P U T ( Ω r e f ) u ∗ = P U T ( Ω r e f ) e T ∗ ∈ W ∞ . (59) w_T^*:=(I-P_{U_T})P_{U_T(\Omega_{\mathrm{ref}})}u^*=P_{U_T(\Omega_{\mathrm{ref}})}e_T^*\in\mathbb{W}^\infty. \tag*{(59)} w T ∗ := ( I − P U T ) P U T ( Ω ref ) u ∗ = P U T ( Ω ref ) e T ∗ ∈ W ∞ . (59)
Thus,
e T ∗ − w T ∗ = ( I − P U T ( Ω r e f ) ) e T ∗ ∈ U T ( Ω r e f ) ⊥ , (60) e_T^*-w_T^*=(I-P_{U_T(\Omega_{\mathrm{ref}})})e_T^*\in U_T(\Omega_{\mathrm{ref}})^\perp, \tag*{(60)} e T ∗ − w T ∗ = ( I − P U T ( Ω ref ) ) e T ∗ ∈ U T ( Ω ref ) ⊥ , (60)
which gives
∥ e T ∗ − w T ∗ ∥ U = sup z ∈ U T ( Ω r e f ) ⊥ ( e T ∗ − w T ∗ , z ) U ∥ z ∥ U = sup z ∈ U T ( Ω r e f ) ⊥ ( e T ∗ , z ) U ∥ z ∥ U . (61) \lVert e_T^* - w_T^* \rVert_U = \sup_{z \in U_T(\Omega_{\mathrm{ref}})^\perp} \frac{(e_T^* - w_T^*,z)_U}{\lVert z\rVert_U} = \sup_{z \in U_T(\Omega_{\mathrm{ref}})^\perp} \frac{(e_T^*,z)_U}{\lVert z\rVert_U}. \tag*{(61)} ∥ e T ∗ − w T ∗ ∥ U = z ∈ U T ( Ω ref ) ⊥ sup ∥ z ∥ U ( e T ∗ − w T ∗ , z ) U = z ∈ U T ( Ω ref ) ⊥ sup ∥ z ∥ U ( e T ∗ , z ) U . (61)
Invoking Lemma 3.3 , yields
∥ e T ∗ − w T ∗ ∥ U = sup z ∈ U T r e f ∞ ⊥ ( B e T ∗ , B z ) Ω r e f c ∥ z ∥ U ≤ ∥ B e T ∗ ∥ Ω r e f c = ∥ R T ∥ Ω r e f c ≤ ( 1 − θ ) 1 / 2 ∥ R T ∥ Ω = ( 1 − θ ) 1 / 2 ∥ e T ∗ ∥ U . (62) \begin{aligned}
\lVert e_T^* - w_T^* \rVert_U
&= \sup_{z \in U_{T\mathrm{ref}}^\infty{}^\perp} \frac{(B e_T^*,Bz)_{\Omega_{\mathrm{ref}}^c}}{\lVert z\rVert_U}
\le\lVert B e_T^* \rVert_{\Omega_{\mathrm{ref}}^c}
= \lVert\mathcal{R}_T \rVert_{\Omega_{\mathrm{ref}}^c} \\
&\le(1-\theta)^{1/2}\lVert\mathcal{R}_T \rVert_{\Omega}
= (1-\theta)^{1/2}\lVert e_T^* \rVert_U. \tag*{(62)}
\end{aligned} ∥ e T ∗ − w T ∗ ∥ U = z ∈ U T ref ∞ ⊥ sup ∥ z ∥ U ( B e T ∗ , B z ) Ω ref c ≤ ∥ B e T ∗ ∥ Ω ref c = ∥ R T ∥ Ω ref c ≤ ( 1 − θ ) 1/2 ∥ R T ∥ Ω = ( 1 − θ ) 1/2 ∥ e T ∗ ∥ U . (62)
Moreover, since w T ∗ ∈ U T ( Ω r e f ) w_T^* \in U_T(\Omega_{\mathrm{ref}}) w T ∗ ∈ U T ( Ω ref ) , and thus
( e T ∗ − w T ∗ , w T ∗ ) U = ( ( I − P U T ( Ω r e f ) ) e T ∗ , w T ∗ ) U = ( e T ∗ , ( I − P U T ( Ω r e f ) ) w T ∗ ) U = 0 , (e_T^* - w_T^*,w_T^*)_U = ((I-P_{U_T(\Omega_{\mathrm{ref}})})e_T^*,w_T^*)_U = (e_T^*,(I-P_{U_T(\Omega_{\mathrm{ref}})})w_T^*)_U = 0, ( e T ∗ − w T ∗ , w T ∗ ) U = (( I − P U T ( Ω ref ) ) e T ∗ , w T ∗ ) U = ( e T ∗ , ( I − P U T ( Ω ref ) ) w T ∗ ) U = 0 ,
we conclude, upon using that B e T ∗ = R T B e_T^* = \mathcal{R}_T B e T ∗ = R T ,
( e T ∗ , w T ∗ ) U = ( B e T ∗ , B w T ∗ ) Ω = ( R T , B w T ∗ ) Ω = ( 3.33 ) ∥ B w T ∗ ∥ Ω 2 . (63) (e_T^*,w_T^*)_U = (B e_T^*,B w_T^*)_\Omega= (\mathcal{R}_T,Bw_T^*)_\Omega\overset{(3.33)}{=} \lVert B w_T^* \rVert_\Omega^2. \tag*{(63)} ( e T ∗ , w T ∗ ) U = ( B e T ∗ , B w T ∗ ) Ω = ( R T , B w T ∗ ) Ω = ( 3.33 ) ∥ B w T ∗ ∥ Ω 2 . (63)
On the other hand,
( e T ∗ , w T ∗ ) U = ∥ e T ∗ ∥ U 2 + ( e T ∗ , w T ∗ − e T ∗ ) U = ∥ R T ∥ Ω 2 + ( R T , B ( w T ∗ − e T ∗ ) ) Ω ≥ ∥ R T ∥ Ω 2 − ∥ R T ∥ Ω ∥ e T ∗ − w T ∗ ∥ U ≥ ( 1 − ( 1 − θ ) 1 / 2 ) ∥ R T ∥ Ω 2 , \begin{aligned}
(e_T^*,w_T^*)_U
&= \lVert e_T^* \rVert_U^2 + (e_T^*,w_T^* - e_T^*)_U \\
&= \lVert\mathcal{R}_T \rVert_\Omega^2 + (\mathcal{R}_T,B(w_T^* - e_T^*))_\Omega\\
&\ge\lVert\mathcal{R}_T \rVert_\Omega^2 - \lVert\mathcal{R}_T \rVert_\Omega\lVert e_T^* - w_T^* \rVert_U \\
&\ge(1-(1-\theta)^{1/2})\lVert\mathcal{R}_T \rVert_\Omega^2,
\end{aligned} ( e T ∗ , w T ∗ ) U = ∥ e T ∗ ∥ U 2 + ( e T ∗ , w T ∗ − e T ∗ ) U = ∥ R T ∥ Ω 2 + ( R T , B ( w T ∗ − e T ∗ ) ) Ω ≥ ∥ R T ∥ Ω 2 − ∥ R T ∥ Ω ∥ e T ∗ − w T ∗ ∥ U ≥ ( 1 − ( 1 − θ ) 1/2 ) ∥ R T ∥ Ω 2 ,
where we have used (62) in the last step. This latter inequality together with (63) provides
∥ B w T ∗ ∥ Ω 2 ≥ ( 1 − ( 1 − θ ) 1 / 2 ) ∥ R T ∥ Ω 2 . \lVert B w_T^* \rVert_\Omega^2 \ge(1-(1-\theta)^{1/2})\lVert\mathcal{R}_T \rVert_\Omega^2. ∥ B w T ∗ ∥ Ω 2 ≥ ( 1 − ( 1 − θ ) 1/2 ) ∥ R T ∥ Ω 2 .
which, in view of the definition, ξ : = ( 1 − ( 1 − θ ) 1 / 2 ) 1 / 2 \xi:= (1-(1-\theta)^{1/2})^{1/2} ξ := ( 1 − ( 1 − θ ) 1/2 ) 1/2 from (56) , confirms (57) .
Regarding (58) , observe that
∥ B w T ∥ Ω 2 = ( 3.18 ) ( R T , B w T ) Ω = ( R T , B w T ∗ ) Ω − ( f , B ( w T ∗ − w T ) ) Ω . (64) \lVert B w_T \rVert_\Omega^2 \overset{(3.18)}{=} (\mathcal{R}_T,Bw_T)_\Omega= (\mathcal{R}_T,Bw_T^*)_\Omega- (f,B(w_T^* - w_T))_\Omega. \tag*{(64)} ∥ B w T ∥ Ω 2 = ( 3.18 ) ( R T , B w T ) Ω = ( R T , B w T ∗ ) Ω − ( f , B ( w T ∗ − w T ) ) Ω . (64)
Now, recall from (45) in Lemma 3.1 that ( f , B ( w T ∗ − w T ) ) Ω = vis T ( f , W ℓ ) 2 (f,B(w_T^* - w_T))_\Omega= \operatorname{vis}_T(f,W^\ell)^2 ( f , B ( w T ∗ − w T ) ) Ω = vis T ( f , W ℓ ) 2 . Combining this with (64) , yields
∥ B w T ∥ Ω 2 = ( 3.18 ) ( R T , w T ) Ω = ( R T , B w T ∗ ) Ω − vis T ( f , W ℓ ) 2 = ( 3.34 ) ∥ B w T ∗ ∥ Ω 2 − vis T ( f , W ℓ ) 2 ≥ ( 3.39 ) ξ 2 ∥ R T ∥ Ω 2 − vis T ( f , W ℓ ) 2 . \begin{aligned}
\lVert B w_T \rVert_\Omega^2
&\overset{(3.18)}{=} (\mathcal{R}_T,w_T)_\Omega= (\mathcal{R}_T,Bw_T^*)_\Omega- \operatorname{vis}_T(f,W^\ell)^2 \\
&\overset{(3.34)}{=} \lVert B w_T^* \rVert_\Omega^2 - \operatorname{vis}_T(f,W^\ell)^2 \\
&\overset{(3.39)}{\ge} \xi^2\lVert\mathcal{R}_T \rVert_\Omega^2 - \operatorname{vis}_T(f,W^\ell)^2.
\end{aligned} ∥ B w T ∥ Ω 2 = ( 3.18 ) ( R T , w T ) Ω = ( R T , B w T ∗ ) Ω − vis T ( f , W ℓ ) 2 = ( 3.34 ) ∥ B w T ∗ ∥ Ω 2 − vis T ( f , W ℓ ) 2 ≥ ( 3.39 ) ξ 2 ∥ R T ∥ Ω 2 − vis T ( f , W ℓ ) 2 .
as claimed.
Proof of Theorem 3.2, (a)
Note that, in view of (58) ,
∥ u ∗ − u r e f T ∥ U 2 = ∥ u ∗ − u T ∥ U 2 − ∥ w T ∥ U 2 ≤ ∥ u ∗ − u T ∥ U 2 − ξ 2 ∥ u ∗ − u T ∥ U 2 + vis T ( f , W ℓ ) . \lVert u^* - u_{\mathrm{ref}}^T \rVert_U^2 = \lVert u^* - u_T \rVert_U^2 - \lVert w_T \rVert_U^2
\le\lVert u^* - u_T \rVert_U^2 - \xi^2\lVert u^* - u_T \rVert_U^2 + \operatorname{vis}_T(f,W^\ell). ∥ u ∗ − u ref T ∥ U 2 = ∥ u ∗ − u T ∥ U 2 − ∥ w T ∥ U 2 ≤ ∥ u ∗ − u T ∥ U 2 − ξ 2 ∥ u ∗ − u T ∥ U 2 + vis T ( f , W ℓ ) .
part (a) of Theorem 3.2 follows from (56) .
Proof of Theorem 3.2, (b)
To complete the proof of Theorem 3.2 we need one further technical preliminary.
Lemma 3.4. Given ξ \xi ξ , C 0 C_0 C 0 according to (56) , (47) , respectively. Then there exist a ρ < 1 \rho< 1 ρ < 1 and some m ∈ N m \in\mathbb{N} m ∈ N such that
ρ 2 { ξ 2 ( 1 − ρ 2 ( m − 1 ) ) 1 − ρ 2 + 1 } ≥ C 0 + 1. (65) \rho^2\left\{\frac{\xi^2(1-\rho^{2(m-1)})}{1-\rho^2}+1\right\}\ge C_0+1. \tag*{(65)} ρ 2 { 1 − ρ 2 ξ 2 ( 1 − ρ 2 ( m − 1 ) ) + 1 } ≥ C 0 + 1. (65)
Proof: Define
G ( ρ , ξ ) : = ρ 2 { ξ 2 2 ( 1 − ρ 2 ) + 1 } . G(\rho,\xi):=\rho^2\left\{\frac{\xi^2}{2(1-\rho^2)}+1\right\}. G ( ρ , ξ ) := ρ 2 { 2 ( 1 − ρ 2 ) ξ 2 + 1 } .
Clearly, G ( 1 , ξ ) = ∞ G(1,\xi)=\infty G ( 1 , ξ ) = ∞ and G ( 0 , ξ ) = 0 G(0,\xi)=0 G ( 0 , ξ ) = 0 . By monotonicity, there exists a unique ρ = ρ ( ξ ) \rho=\rho(\xi) ρ = ρ ( ξ ) such that G ( ρ , ξ ) = C 0 + 1 G(\rho,\xi)=C_0+1 G ( ρ , ξ ) = C 0 + 1 . For this ρ \rho ρ pick m ∈ N m\in\mathbb{N} m ∈ N such that ρ 2 ( m − 1 ) < 1 / 2 \rho^{2(m-1)}<1/2 ρ 2 ( m − 1 ) < 1/2 . Then
ρ 2 { ξ 2 ( 1 − ρ 2 ( m − 1 ) ) 1 − ρ 2 + 1 } ≥ G ( ρ , ξ ) = C 0 + 1 , \rho^2\left\{\frac{\xi^2(1-\rho^{2(m-1)})}{1-\rho^2}+1\right\}\ge G(\rho,\xi)=C_0+1, ρ 2 { 1 − ρ 2 ξ 2 ( 1 − ρ 2 ( m − 1 ) ) + 1 } ≥ G ( ρ , ξ ) = C 0 + 1 ,
as claimed. □ \square □
Proof of Theorem 3.2, (b): We adhere to the notation (3.27). That is, let T = T k \mathcal{T}=\mathcal{T}_k T = T k , T k + 1 = T r e f ( K θ , k ) \mathcal{T}_{k+1}=\mathcal{T}_{\mathrm{ref}}(\mathcal{K}_{\theta,k}) T k + 1 = T ref ( K θ , k ) , Ω r e f k \Omega_{\mathrm{ref}}^k Ω ref k , the refinement region in T k \mathcal{T}_k T k , and denote by u k u_k u k the solutions of (22) in U k = U T k U_k=U_{\mathcal{T}_k} U k = U T k . Now consider m m m refinement cycles, giving
u k + j , T k + j , w k + j = u k + j + 1 − u k + j , R k + j = f − B u k + j , j = 0 , … , m − 1. u_{k+j},\ \mathcal{T}_{k+j},\ w_{k+j}=u_{k+j+1}-u_{k+j},\ \mathcal{R}_{k+j}=f-\mathcal{B}u_{k+j},\qquad j=0,\ldots,m-1. u k + j , T k + j , w k + j = u k + j + 1 − u k + j , R k + j = f − B u k + j , j = 0 , … , m − 1.
By orthogonality
∥ u ∗ − u k + m ∥ U 2 = ∥ u ∗ − u k ∥ U 2 − ∥ w k + m − 1 ∥ U 2 − ⋯ − ∥ w k ∥ U 2 . (66) \|u^*-u_{k+m}\|_U^2=\|u^*-u_k\|_U^2-\|w_{k+m-1}\|_U^2-\cdots-\|w_k\|_U^2. \tag*{(66)} ∥ u ∗ − u k + m ∥ U 2 = ∥ u ∗ − u k ∥ U 2 − ∥ w k + m − 1 ∥ U 2 − ⋯ − ∥ w k ∥ U 2 . (66)
Fix ρ ˉ < 1 \bar{\rho}<1 ρ ˉ < 1 and suppose that for some m > l ≥ 1 m>l\ge1 m > l ≥ 1 one has ∥ R T k + m − l ∥ Ω ≤ ρ ˉ ∥ R T k + m − l − 1 ∥ Ω \|\mathcal{R}_{\mathcal{T}_{k+m-l}}\|_\Omega\le\bar{\rho}\|\mathcal{R}_{\mathcal{T}_{k+m-l-1}}\|_\Omega ∥ R T k + m − l ∥ Ω ≤ ρ ˉ ∥ R T k + m − l − 1 ∥ Ω . Then
∥ u ∗ − u k + m ∥ U ≤ ∥ u ∗ − u k + m − l ∥ U = ∥ R T k + m − l ∥ Ω ≤ ρ ˉ ∥ R T k + m − l − 1 ∥ Ω = ρ ˉ ∥ u ∗ − u k + m − l − 1 ∥ U ≤ ρ ˉ ∥ u ∗ − u k ∥ U , \begin{aligned}
\|u^*-u_{k+m}\|_U\le\|u^*-u_{k+m-l}\|_U=\|\mathcal{R}_{\mathcal{T}_{k+m-l}}\|_\Omega\le\bar{\rho}\|\mathcal{R}_{\mathcal{T}_{k+m-l-1}}\|_\Omega\\
&=\bar{\rho}\|u^*-u_{k+m-l-1}\|_U\le\bar{\rho}\|u^*-u_k\|_U,
\end{aligned} ∥ u ∗ − u k + m ∥ U ≤ ∥ u ∗ − u k + m − l ∥ U = ∥ R T k + m − l ∥ Ω ≤ ρ ˉ ∥ R T k + m − l − 1 ∥ Ω = ρ ˉ ∥ u ∗ − u k + m − l − 1 ∥ U ≤ ρ ˉ ∥ u ∗ − u k ∥ U ,
which is the claimed error reduction by a factor ρ ˉ < 1 \bar{\rho}<1 ρ ˉ < 1 . Suppose therefore that
∥ R T k + m − l ∥ Ω > ρ ˉ ∥ R T k + m − l − 1 ∥ Ω , ∀ 1 ≤ l < m . (67) \|\mathcal{R}_{\mathcal{T}_{k+m-l}}\|_\Omega>\bar{\rho}\|\mathcal{R}_{\mathcal{T}_{k+m-l-1}}\|_\Omega,\qquad\forall\,1\le l<m. \tag*{(67)} ∥ R T k + m − l ∥ Ω > ρ ˉ ∥ R T k + m − l − 1 ∥ Ω , ∀ 1 ≤ l < m . (67)
From (58) and the above observations we know that with W k + m − j ℓ : = W ℓ ( T k + m − j ; T k + m + 1 − j ) W^\ell_{k+m-j}:=W^\ell(\mathcal{T}_{k+m-j};\mathcal{T}_{k+m+1-j}) W k + m − j ℓ := W ℓ ( T k + m − j ; T k + m + 1 − j )
∑ j = 1 m ∥ w k + m − j ∥ U 2 ≥ ∑ j = 1 m ξ 2 ∥ R k + m − j ∥ Ω 2 − vis T k + m − j ( f , W k + m − j ℓ ) 2 ≥ ξ 2 ( ρ ˉ 2 + ⋯ + ρ ˉ 2 ( m − 1 ) ) ∥ R T k ∥ Ω 2 − ∑ j = 1 m vis T k + m − j ( f , W k + m − j ℓ ) 2 ≥ ξ 2 ( ρ ˉ 2 + ⋯ + ρ ˉ 2 ( m − 1 ) ) ∥ R T k ∥ Ω 2 − C 0 ∥ R T k ∥ Ω 2 = { ρ ˉ 2 ξ 2 ( 1 − ρ ˉ 2 ( m − 1 ) ) 1 − ρ ˉ 2 − C 0 } ∥ R T k ∥ Ω 2 . (68) \begin{aligned}
\sum_{j=1}^{m}\|w_{k+m-j}\|_U^2
&\ge\sum_{j=1}^{m}\xi^2\|\mathcal{R}_{k+m-j}\|_\Omega^2-\operatorname{vis}_{\mathcal{T}_{k+m-j}}(f,W^\ell_{k+m-j})^2\\
&\ge\xi^2(\bar{\rho}^2+\cdots+\bar{\rho}^{2(m-1)})\|\mathcal{R}_{\mathcal{T}_k}\|_\Omega^2-\sum_{j=1}^{m}\operatorname{vis}_{\mathcal{T}_{k+m-j}}(f,W^\ell_{k+m-j})^2\\
&\ge\xi^2(\bar{\rho}^2+\cdots+\bar{\rho}^{2(m-1)})\|\mathcal{R}_{\mathcal{T}_k}\|_\Omega^2-C_0\|\mathcal{R}_{\mathcal{T}_k}\|_\Omega^2\\
&=\left\{\frac{\bar{\rho}^2\xi^2(1-\bar{\rho}^{2(m-1)})}{1-\bar{\rho}^2}-C_0\right\}\|\mathcal{R}_{\mathcal{T}_k}\|_\Omega^2. \tag*{(68)}
\end{aligned} j = 1 ∑ m ∥ w k + m − j ∥ U 2 ≥ j = 1 ∑ m ξ 2 ∥ R k + m − j ∥ Ω 2 − vis T k + m − j ( f , W k + m − j ℓ ) 2 ≥ ξ 2 ( ρ ˉ 2 + ⋯ + ρ ˉ 2 ( m − 1 ) ) ∥ R T k ∥ Ω 2 − j = 1 ∑ m vis T k + m − j ( f , W k + m − j ℓ ) 2 ≥ ξ 2 ( ρ ˉ 2 + ⋯ + ρ ˉ 2 ( m − 1 ) ) ∥ R T k ∥ Ω 2 − C 0 ∥ R T k ∥ Ω 2 = { 1 − ρ ˉ 2 ρ ˉ 2 ξ 2 ( 1 − ρ ˉ 2 ( m − 1 ) ) − C 0 } ∥ R T k ∥ Ω 2 . (68)
Thus, whenever m , ρ ˉ m,\bar{\rho} m , ρ ˉ satisfy for some $\eta>0
ρ ˉ 2 ξ 2 ( 1 − ρ ˉ 2 ( m − 1 ) ) 1 − ρ ˉ 2 ≥ C 0 + η . (69) \frac{\bar{\rho}^2\xi^2(1-\bar{\rho}^{2(m-1)})}{1-\bar{\rho}^2}\ge C_0+\eta. \tag*{(69)} 1 − ρ ˉ 2 ρ ˉ 2 ξ 2 ( 1 − ρ ˉ 2 ( m − 1 ) ) ≥ C 0 + η . (69)
We infer from (66) , (68) , and Remark 3.1 that
∥ u ∗ − u k + m ∥ U ≤ 1 − η ∥ u ∗ − u k ∥ U . \|u^*-u_{k+m}\|_U\le\sqrt{1-\eta}\|u^*-u_k\|_U. ∥ u ∗ − u k + m ∥ U ≤ 1 − η ∥ u ∗ − u k ∥ U .
On account of the above alternative, we have
∥ u ∗ − u k + m ∥ U ≤ max { ρ ˉ , 1 − η } ∥ u ∗ − u k ∥ U . \|u^*-u_{k+m}\|_U\le\max\{\bar{\rho},\sqrt{1-\eta}\}\|u^*-u_k\|_U. ∥ u ∗ − u k + m ∥ U ≤ max { ρ ˉ , 1 − η } ∥ u ∗ − u k ∥ U .
Now, choosing η = 1 − ρ ˉ 2 \eta= 1 - \bar{\rho}^{2} η = 1 − ρ ˉ 2 , (69) takes the form
ρ ˉ 2 { ξ 2 ( 1 − ρ ˉ 2 ( m − 1 ) ) 1 − ρ ˉ 2 + 1 } ≥ C 0 + 1. \bar{\rho}^{2}\left\{\frac{\xi^{2}(1-\bar{\rho}^{2(m-1)})}{1-\bar{\rho}^{2}}+1\right\}\geq C_{0}+1. ρ ˉ 2 { 1 − ρ ˉ 2 ξ 2 ( 1 − ρ ˉ 2 ( m − 1 ) ) + 1 } ≥ C 0 + 1.
By Lemma 3.4 , there indeed exist ρ = ρ ˉ ( m ) < 1 \rho=\bar{\rho}(m)<1 ρ = ρ ˉ ( m ) < 1 , m ∈ N m\in\mathbb{N} m ∈ N such that this inequality holds, which completes the proof. □ \square □
Towards a Practical Scheme
The obvious remaining essential question is for which f f f does (47) hold? This is intimately tied to the perhaps main idealization in the previously discussed scheme, namely the assumption of having exact access to f f f and resulting quantities like residuals. These quantities are subject to quadrature errors. We re-interpret the entailed perturbation of quantities, involving f f f , as resulting from an exact integration with f f f replaced by a piecewise polynomial approximation. We therefore also assume in what follows that the coefficients in B \mathcal{B} B are piecewise polynomial on the current partition. We suppress for simplicity of exposition a correspondingly extended perturbation analysis, taking piecewise polynomial approximations of such coefficients into account, e.g. absorbed by inexact solves that can be handled along the lines in [22 ] .
So, let us proceed under the working assumption that
( f ~ , B v ) Ω , ∥ R T ( v , f ~ ) ∥ Ω ′ , R T ( v , f ~ ) : = f ~ − B v , v ∈ U T , (70) (\tilde{f},Bv)_{\Omega},\quad\lVert\mathcal{R}_{T}(v,\tilde{f})\rVert_{\Omega'},\quad\mathcal{R}_{T}(v,\tilde{f}):=\tilde{f}-Bv,\quad v\in\mathcal{U}_{T}, \tag*{(70)} ( f ~ , B v ) Ω , ∥ R T ( v , f ~ ) ∥ Ω ′ , R T ( v , f ~ ) := f ~ − B v , v ∈ U T , (70)
can be computed exactly and that Solve [ f ~ , T ] → u ~ T \operatorname{Solve}[\tilde{f},T]\to\tilde{u}_{T} Solve [ f ~ , T ] → u ~ T can be carried out exactly when f ~ \tilde{f} f ~ is a piecewise polynomial.
Piecewise Polynomial Loads and a Reduction Block
Computing a piecewise polynomial approximation to a given f ∈ L 2 f\in L_{2} f ∈ L 2 would, of course also require the ability to evaluate f f f in some way, e.g. to employ sufficiently accurate quadrature. Proposing a concrete procedure depends again on the specific case at hand. We will therefore work here under the following specified assumption analogous to [22 ] .
Given f ∈ L 2 f\in L_{2} f ∈ L 2 and a partition T ∈ T \mathcal{T}\in\mathbb{T} T ∈ T we have at hand a routine
Appr [ f , T , δ ] ⟶ ( f δ , T δ f ) \operatorname{Appr}[f,\mathcal{T},\delta]\longrightarrow(f_{\delta},\mathcal{T}_{\delta}^{f}) Appr [ f , T , δ ] ⟶ ( f δ , T δ f )
where T δ f ∈ T \mathcal{T}_{\delta}^{f}\in\mathbb{T} T δ f ∈ T is a refinement of T \mathcal{T} T , and f δ f_{\delta} f δ is a piecewise polynomial on T δ f \mathcal{T}_{\delta}^{f} T δ f such that
∥ f − f δ ∥ Ω ≤ δ . (71) \lVert f-f_{\delta}\rVert_{\Omega}\leq\delta. \tag*{(71)} ∥ f − f δ ∥ Ω ≤ δ . (71)
Here T δ f \mathcal{T}_{\delta}^{f} T δ f is obtained from T \mathcal{T} T through a finite number of calls of Subd [ T , ⋅ , 1 ] \operatorname{Subd}[\mathcal{T},\cdot,1] Subd [ T , ⋅ , 1 ] , followed by a closing step to restore T \mathbb{T} T -compliance.
For a given piecewise polynomial load, it will be useful to view a certain fixed number of successive cycles in ALSM-Ideal \operatorname{ALSM\text{-}Ideal} ALSM - Ideal as a single refinement block which we formulate as the following sub-routine.
Reduce [ T , f ~ , u ~ , θ , ρ ] ⟶ T r e f , u ˉ T r e f ∈ U T r e f \operatorname{Reduce}[\mathcal{T},\tilde{f},\tilde{u},\theta,\rho]\longrightarrow\mathcal{T}_{\mathrm{ref}},\bar{u}_{\mathcal{T}_{\mathrm{ref}}}\in\mathcal{U}_{\mathcal{T}_{\mathrm{ref}}} Reduce [ T , f ~ , u ~ , θ , ρ ] ⟶ T ref , u ˉ T ref ∈ U T ref
Input: T ∈ T \mathcal{T}\in\mathbb{T} T ∈ T , f ~ \tilde{f} f ~ piecewise polynomial on T \mathcal{T} T , u ~ = Solve [ f ~ , T ] \tilde{u}=\operatorname{Solve}[\tilde{f},\mathcal{T}] u ~ = Solve [ f ~ , T ] , θ ∈ ( 0 , 1 ) \theta\in(0,1) θ ∈ ( 0 , 1 ) , ρ < 1 \rho<1 ρ < 1 ;
Set T ~ = T \tilde{\mathcal{T}}=\mathcal{T} T ~ = T ;
do:
Mark [ T ~ , u ~ , f ~ , θ ] ⟶ K \operatorname{Mark}[\tilde{\mathcal{T}},\tilde{u},\tilde{f},\theta]\longrightarrow\mathcal{K} Mark [ T ~ , u ~ , f ~ , θ ] ⟶ K ;
Refine [ T ~ , K ] ⟶ T \operatorname{Refine}[\tilde{\mathcal{T}},\mathcal{K}]\longrightarrow\mathcal{T} Refine [ T ~ , K ] ⟶ T ;
Solve [ f ~ , T ] ⟶ u ˉ \operatorname{Solve}[\tilde{f},\mathcal{T}]\longrightarrow\bar{u} Solve [ f ~ , T ] ⟶ u ˉ ;
while
∥ f ~ − B u ˉ ∥ Ω > ρ ∥ f ~ − B u ~ ∥ Ω , (72) \lVert\tilde{f}-B\bar{u}\rVert_{\Omega}>\rho\lVert\tilde{f}-B\tilde{u}\rVert_{\Omega}, \tag*{(72)} ∥ f ~ − B u ˉ ∥ Ω > ρ ∥ f ~ − B u ~ ∥ Ω , (72)
repeat; else, output T r e f = T \mathcal{T}_{\mathrm{ref}}=\mathcal{T} T ref = T , u ˉ r e f = u ˉ \bar{u}_{\mathrm{ref}}=\bar{u} u ˉ ref = u ˉ .
By construction, whenever Reduce terminates, one has
∥ f ~ − B u ˉ T r e f ∥ Ω ≤ ρ ∥ f ~ − B u ~ ∥ Ω . (73) \left\|\widetilde{f}-B\bar{u}_{\mathrm{T}_{\mathrm{ref}}}\right\|_{\Omega}\leq\rho\left\|\widetilde{f}-B\widetilde{u}\right\|_{\Omega}. \tag*{(73)} f − B u ˉ T ref Ω ≤ ρ f − B u Ω . (73)
It will be shown later below that when f f f is piecewise polynomial on a current partition, Reduce indeed terminates within a fixed finite number m m m of inner calls of Refine where m m m satisfies (65) .
ALSM and the Main Result
To formulate the main adaptive scheme let m ∈ N m\in\mathbb{N} m ∈ N , ρ < 1 \rho<1 ρ < 1 satisfy (65) and choose ω ∈ ( 0 , 1 ) \omega\in(0,1) ω ∈ ( 0 , 1 ) such that
ρ ^ : = ω + ρ 1 − ω < 1. (74) \widehat{\rho}:=\frac{\omega+\rho}{1-\omega}<1. \tag*{(74)} ρ := 1 − ω ω + ρ < 1. (74)
Remark 4.1. We have to keep in mind that ρ \rho ρ from (65) , hence ρ ^ \widehat{\rho} ρ , depend on θ \theta θ (through ξ ( θ ) \xi(\theta) ξ ( θ ) ) but exist for any θ < 1 \theta<1 θ < 1 . If this dependence matters, we write ρ = ρ ( θ ) \rho=\rho(\theta) ρ = ρ ( θ ) , ρ ^ = ρ ^ ( θ ) \widehat{\rho}=\widehat{\rho}(\theta) ρ = ρ ( θ ) .
The idea behind the following scheme is: first generate a piecewise polynomial approximation to the load f f f by refining the current partition until the approximation error is dominated by the residual of the Galerkin solution on the updated partition: then apply a reduction block Reduce which is then guaranteed to terminate after at most m m m calls of Refine.
ALSM [ B , f , θ , ε ] → T ε , u ε ∈ U T ε \operatorname{ALSM}[\mathcal{B},f,\theta,\varepsilon]\to\mathcal{T}_{\varepsilon},u_{\varepsilon}\in\mathbb{U}_{\mathcal{T}_{\varepsilon}} ALSM [ B , f , θ , ε ] → T ε , u ε ∈ U T ε :
(A0) Set ε > 0 \varepsilon>0 ε > 0 ; choose θ < 1 \theta<1 θ < 1 , ρ \rho ρ , ω \omega ω according to (65) , (74) , respectively; choose T 0 \mathcal{T}_0 T 0 , u 0 = 0 u_0=0 u 0 = 0 , ℓ ∈ N \ell\in\mathbb{N} ℓ ∈ N , k = 0 k=0 k = 0 ; fix δ 0 = ∥ f ∥ Ω \delta_0=\|f\|_{\Omega} δ 0 = ∥ f ∥ Ω , δ 0 → δ \delta_0\to\delta δ 0 → δ ;
(A1) set T k → T \mathcal{T}_k\to\mathcal{T} T k → T , δ k → δ \delta_k\to\delta δ k → δ ; Appr [ f , T , δ ] → [ f δ , T ~ k ] \operatorname{Appr}[f,\mathcal{T},\delta]\to[f_{\delta},\widetilde{\mathcal{T}}_k] Appr [ f , T , δ ] → [ f δ , T k ] ; Solve [ f δ , T ~ k ] → u ˉ δ \operatorname{Solve}[f_{\delta},\widetilde{\mathcal{T}}_k]\to\bar{u}_{\delta} Solve [ f δ , T k ] → u ˉ δ ;
while
δ + ∥ f δ − B u ˉ δ ∥ Ω > ε , (75) \delta+\left\|f_{\delta}-B\bar{u}_{\delta}\right\|_{\Omega}>\varepsilon, \tag*{(75)} δ + ∥ f δ − B u ˉ δ ∥ Ω > ε , (75)
while
δ > ω ∥ f δ − B u ˉ δ ∥ Ω ; (76) \delta>\omega\left\|f_{\delta}-B\bar{u}_{\delta}\right\|_{\Omega}; \tag*{(76)} δ > ω ∥ f δ − B u ˉ δ ∥ Ω ; (76)
δ / 2 → δ k \delta/2\to\delta_k δ /2 → δ k , T ~ k → T k \widetilde{\mathcal{T}}_k\to\mathcal{T}_k T k → T k , and go to (A1); f k = f δ f_k=f_{\delta} f k = f δ , u ˉ k = u ˉ δ \bar{u}_k=\bar{u}_{\delta} u ˉ k = u ˉ δ , δ k = δ \delta_k=\delta δ k = δ , go to (A2); stop and set T ε = T ~ k \mathcal{T}_{\varepsilon}=\widetilde{\mathcal{T}}_k T ε = T k , u ε = u ˉ δ u_{\varepsilon}=\bar{u}_{\delta} u ε = u ˉ δ ;
(A2) Reduce [ T ~ k , f k , u ˉ k , θ , ρ ] → T k + 1 , u k + 1 \operatorname{Reduce}[\widetilde{\mathcal{T}}_k,f_k,\bar{u}_k,\theta,\rho]\to\mathcal{T}_{k+1},u_{k+1} Reduce [ T k , f k , u ˉ k , θ , ρ ] → T k + 1 , u k + 1 ; while δ k + ∥ f k − B u k + 1 ∥ Ω > ε \delta_k+\|f_k-Bu_{k+1}\|_{\Omega}>\varepsilon δ k + ∥ f k − B u k + 1 ∥ Ω > ε ; set k + 1 → k k+1\to k k + 1 → k and goto (A1); stop and accept T ε = T k + 1 \mathcal{T}_{\varepsilon}=\mathcal{T}_{k+1} T ε = T k + 1 , u ε = u k + 1 u_{\varepsilon}=u_{k+1} u ε = u k + 1 as the output.
The analysis of the above scheme hinges on the validity of the following standard approximation properties of the trial spaces, see [13 Section 2.5.2] for known relevant scenarios.
Assumption CAP: (Canonical Approximation Property) For Ω r e f ⊂ Ω \Omega_{\mathrm{ref}}\subset\Omega Ω ref ⊂ Ω as above we assume that the trial spaces enjoy canonical approximation properties in the sense that the following localized Bramble–Hilbert Lemma holds: if f ∈ H s ( Ω ; R q ) f\in H^s(\Omega;\mathbb{R}^q) f ∈ H s ( Ω ; R q ) for some s > 0 s>0 s > 0 , there exists a constant C C A P C_{\mathrm{CAP}} C CAP , independent of Ω r e f \Omega_{\mathrm{ref}} Ω ref , f f f , such that
inf v ∈ U ( Ω r e f ; T r e f ) ∥ B ( u Ω ′ ∗ − v ) ∥ Ω r e f ≤ C C A P ∑ K ∈ T r e f K ⊂ Ω r e f h K s ∥ f ∥ H s ( K ; R q ) . (77) \inf_{v\in\mathbb{U}(\Omega_{\mathrm{ref}};\mathcal{T}_{\mathrm{ref}})}
\left\|B(u_{\Omega'}^*-v)\right\|_{\Omega_{\mathrm{ref}}}
\leq C_{\mathrm{CAP}}
\sum_{\substack{K\in\mathcal{T}_{\mathrm{ref}}\\K\subset\Omega_{\mathrm{ref}}}}
h_K^s\left\|f\right\|_{H^s(K;\mathbb{R}^q)}. \tag*{(77)} v ∈ U ( Ω ref ; T ref ) inf ∥ B ( u Ω ′ ∗ − v ) ∥ Ω ref ≤ C CAP K ∈ T ref K ⊂ Ω ref ∑ h K s ∥ f ∥ H s ( K ; R q ) . (77)
Theorem 4.1. Under Assumption (CAP), one has:
(a) The output of Alsm meets the target tolerance ∥ u ∗ − u ε ∥ U ≤ ε \lVert u^* - u_\varepsilon\rVert_U \le\varepsilon ∥ u ∗ − u ε ∥ U ≤ ε .
(b) Reduce terminates in each of its calls within at most m m m inner calls of Refine, where m , ρ m,\rho m , ρ are related by (65) .
(c) For ρ ^ < 1 \hat{\rho}<1 ρ ^ < 1 as in (74) the sequence u k , T k u_k,\mathcal{T}_k u k , T k produced by Alsm[ B , f , θ , ε ] [\mathcal{B},f,\theta,\varepsilon] [ B , f , θ , ε ] satisfies, as long as u k + 1 ≠ u ε u_{k+1}\ne u_\varepsilon u k + 1 = u ε ,
∥ u ∗ − u k + 1 ∥ U ≤ ρ ^ ∥ u ∗ − u k ∥ U . (78) \lVert u^* - u_{k+1}\rVert_U \le\hat{\rho}\lVert u^* - u_k\rVert_U. \tag*{(78)} ∥ u ∗ − u k + 1 ∥ U ≤ ρ ^ ∥ u ∗ − u k ∥ U . (78) Hence, the scheme terminates after O ( ∣ log ε ∣ ) O(\lvert\log\varepsilon\rvert) O (∣ log ε ∣) number of calls of Reduce.
Note that (A1) is the only step in Alsm where the termination of the inner loop is not quantified. In order to branch into (A2) the piecewise polynomial approximation error to f f f must be smaller than a certain fraction of the current residual. Without any further assumption of f f f , it might happen that (75) fails before (76) does, in which case the scheme also terminates and, as shown below, also meets the target tolerance. Thus, the theorem asserts a linear error reduction with regard to the calls of Reduce but so far cannot quantify the refinements required to resolve f f f sufficiently well by piecewise polynomial approximations.
Proof of Theorem 4.1:
Our first step is to show that when the input load is a piecewise polynomial on T \mathcal{T} T the routine Reduce indeed terminates for an appropriate ρ \rho ρ after a uniformly bounded finite number of steps, provided that the trial spaces U T , T ∈ T U_{\mathcal{T}},\ \mathcal{T}\in\mathbb{T} U T , T ∈ T have a canonical approximation property.
We make frequent use of the following:
Proof. By definition,
( P U ( Ω r e f ) u , v ) U = ( u , v ) U ∀ v ∈ U ( Ω r e f ) . (81) (P_{U(\Omega_{\mathrm{ref}})}u,v)_{\mathbb{U}}=(u,v)_{\mathbb{U}}\quad\forall\,v\in U(\Omega_{\mathrm{ref}}). \tag*{(81)} ( P U ( Ω ref ) u , v ) U = ( u , v ) U ∀ v ∈ U ( Ω ref ) . (81)
The left hand side of (81) agrees, by definition, with
( B P U ( Ω r e f ) u , B v ) Ω = ( B P U ( Ω r e f ) u , B v ) Ω r e f , ( since v ∈ U ( Ω r e f ) ) (BP_{U(\Omega_{\mathrm{ref}})}u,Bv)_{\Omega}=(BP_{U(\Omega_{\mathrm{ref}})}u,Bv)_{\Omega_{\mathrm{ref}}},\qquad(\text{since }v\in U(\Omega_{\mathrm{ref}})) ( B P U ( Ω ref ) u , B v ) Ω = ( B P U ( Ω ref ) u , B v ) Ω ref , ( since v ∈ U ( Ω ref ))
while the right hand side of (81) can be rewritten as
( u , v ) U = ( B u , B v ) Ω = ( B u , B v ) Ω r e f , (u,v)_{\mathbb{U}}=(Bu,Bv)_{\Omega}=(Bu,Bv)_{\Omega_{\mathrm{ref}}}, ( u , v ) U = ( B u , B v ) Ω = ( B u , B v ) Ω ref ,
again since v ∈ U ( Ω r e f ) v\in U(\Omega_{\mathrm{ref}}) v ∈ U ( Ω ref ) . By well-posedness of (79) , we must have u Ω r e f = P U ( Ω r e f ) u u_{\Omega_{\mathrm{ref}}}=P_{U(\Omega_{\mathrm{ref}})}u u Ω ref = P U ( Ω ref ) u , as claimed. □ \square □
We show next that vis T ( f , W ℓ ) \operatorname{vis}_{\mathcal{T}}(f,W^\ell) vis T ( f , W ℓ ) can be bounded by a best approximation error.
Lemma 4.3. Adhering to the above notation, we have
vis T ( f , W ℓ ) ≤ inf u ~ ∈ U ( Ω r e f ; T r e f ) ∥ P U ( Ω r e f ) ( u ∗ − v T ) − u ~ ∥ U ( Ω r e f ) ∀ v T ∈ U T . (82) \operatorname{vis}_{\mathcal{T}}(f,W^\ell)\le\inf_{\widetilde{u}\in U(\Omega_{\mathrm{ref}};\mathcal{T}_{\mathrm{ref}})}\lVert P_{U(\Omega_{\mathrm{ref}})}(u^*-v_{\mathcal{T}})-\widetilde{u}\rVert_{U(\Omega_{\mathrm{ref}})}\quad\forall\,v_{\mathcal{T}}\in U_{\mathcal{T}}. \tag*{(82)} vis T ( f , W ℓ ) ≤ u ∈ U ( Ω ref ; T ref ) inf ∥ P U ( Ω ref ) ( u ∗ − v T ) − u ∥ U ( Ω ref ) ∀ v T ∈ U T . (82)
Proof. We infer from the definitions of W ∞ W^\infty W ∞ and W ℓ W^\ell W ℓ , (31) , (43) , that
P W ∞ u = ( I − P U T ) P U T ( Ω r e f ) u , P_{W^\infty}u=(I-P_{U_{\mathcal{T}}})P_{U_{\mathcal{T}}(\Omega_{\mathrm{ref}})}u, P W ∞ u = ( I − P U T ) P U T ( Ω ref ) u ,
P W ℓ u = ( I − P U T ) P U T r e f u = ( I − P U T ) P U ( Ω r e f ; T r e f ) u , P_{W^\ell}u=(I-P_{U_{\mathcal{T}}})P_{U_{\mathcal{T}_{\mathrm{ref}}}}u=(I-P_{U_{\mathcal{T}}})P_{U(\Omega_{\mathrm{ref}};\mathcal{T}_{\mathrm{ref}})}u, P W ℓ u = ( I − P U T ) P U T ref u = ( I − P U T ) P U ( Ω ref ; T ref ) u ,
where we have used (41) in the last step. Hence,
( P W ∞ − P W ℓ ) u = ( I − P U T ) ( P U T ( Ω r e f ) − P U ( Ω r e f ; T r e f ) ) u = ( I − P U T ) ( P U ( Ω r e f ) − P U ( Ω r e f ; T r e f ) ) u u ∈ U . (83) \begin{aligned}
(P_{W^\infty}-P_{W^\ell})u
&=(I-P_{U_{\mathcal{T}}})(P_{U_{\mathcal{T}}(\Omega_{\mathrm{ref}})}
-P_{U(\Omega_{\mathrm{ref}};\mathcal{T}_{\mathrm{ref}})})u\\
&=(I-P_{U_{\mathcal{T}}})(P_{U(\Omega_{\mathrm{ref}})}
-P_{U(\Omega_{\mathrm{ref}};\mathcal{T}_{\mathrm{ref}})})u
\qquad u\in\mathbb{U}. \tag*{(83)}
\end{aligned} ( P W ∞ − P W ℓ ) u = ( I − P U T ) ( P U T ( Ω ref ) − P U ( Ω ref ; T ref ) ) u = ( I − P U T ) ( P U ( Ω ref ) − P U ( Ω ref ; T ref ) ) u u ∈ U . (83)
Now, recall from Lemma 3.1 that vis T ( f , W ℓ ) = ∥ ( P W ∞ − P W ℓ ) u ∗ ∥ U \operatorname{vis}_{\mathcal{T}}(f,\mathbb{W}^{\ell})=\lVert(P_{\mathbb{W}^{\infty}}-P_{\mathbb{W}^{\ell}})u^{*}\rVert_{\mathbb{U}} vis T ( f , W ℓ ) = ∥( P W ∞ − P W ℓ ) u ∗ ∥ U . Noticing that ( P W ∞ − P W ℓ ) u ∗ = ( P W ∞ − P W ℓ ) ( u ∗ − v T ) (P_{\mathbb{W}^{\infty}}-P_{\mathbb{W}^{\ell}})u^{*}=(P_{\mathbb{W}^{\infty}}-P_{\mathbb{W}^{\ell}})(u^{*}-v_{\mathcal{T}}) ( P W ∞ − P W ℓ ) u ∗ = ( P W ∞ − P W ℓ ) ( u ∗ − v T ) for any v T ∈ U T v_{\mathcal{T}}\in\mathbb{U}_{\mathcal{T}} v T ∈ U T and invoking (83) , provides
vis T ( f , W ℓ ) 2 = ∥ ( P W ∞ − P W ℓ ) u ∗ ∥ U 2 = ( ( I − P U T ) ( P U ( Ω r e f ) − P U ( Ω r e f ; T r e f ) ) ( u ∗ − v T ) , ( P W ∞ − P W ℓ ) u ∗ ) U ≤ ∥ ( P U ( Ω r e f ) − P U ( Ω r e f ; T r e f ) ) ( u ∗ − v T ) ∥ U ( Ω r e f ) ∥ ( P W ∞ − P W ℓ ) u ∗ ∥ U = inf u ~ ∈ U ( Ω r e f ; T r e f ) ∥ P U ( Ω r e f ) ( u ∗ − v T ) − u ~ ∥ U ( Ω r e f ) ∥ ( P W ∞ − P W ℓ ) u ∗ ∥ U , \begin{aligned}
\operatorname{vis}_{\mathcal{T}}(f,\mathbb{W}^{\ell})^{2}
&=\lVert(P_{\mathbb{W}^{\infty}}-P_{\mathbb{W}^{\ell}})u^{*}\rVert_{\mathbb{U}}^{2}\\
&=\left((I-P_{\mathbb{U}_{\mathcal{T}}})(P_{\mathbb{U}(\Omega_{\mathrm{ref}})}-P_{\mathbb{U}(\Omega_{\mathrm{ref}};\mathcal{T}_{\mathrm{ref}})})(u^{*}-v_{\mathcal{T}}),(P_{\mathbb{W}^{\infty}}-P_{\mathbb{W}^{\ell}})u^{*}\right)_{\mathbb{U}}\\
&\leq\lVert(P_{\mathbb{U}(\Omega_{\mathrm{ref}})}-P_{\mathbb{U}(\Omega_{\mathrm{ref}};\mathcal{T}_{\mathrm{ref}})})(u^{*}-v_{\mathcal{T}})\rVert_{\mathbb{U}(\Omega_{\mathrm{ref}})}\lVert(P_{\mathbb{W}^{\infty}}-P_{\mathbb{W}^{\ell}})u^{*}\rVert_{\mathbb{U}}\\
&=\inf_{\widetilde{u}\in\mathbb{U}(\Omega_{\mathrm{ref}};\mathcal{T}_{\mathrm{ref}})}
\lVert P_{\mathbb{U}(\Omega_{\mathrm{ref}})}(u^{*}-v_{\mathcal{T}})-\widetilde{u}\rVert_{\mathbb{U}(\Omega_{\mathrm{ref}})}
\lVert(P_{\mathbb{W}^{\infty}}-P_{\mathbb{W}^{\ell}})u^{*}\rVert_{\mathbb{U}},
\end{aligned} vis T ( f , W ℓ ) 2 = ∥( P W ∞ − P W ℓ ) u ∗ ∥ U 2 = ( ( I − P U T ) ( P U ( Ω ref ) − P U ( Ω ref ; T ref ) ) ( u ∗ − v T ) , ( P W ∞ − P W ℓ ) u ∗ ) U ≤ ∥( P U ( Ω ref ) − P U ( Ω ref ; T ref ) ) ( u ∗ − v T ) ∥ U ( Ω ref ) ∥( P W ∞ − P W ℓ ) u ∗ ∥ U = u ∈ U ( Ω ref ; T ref ) inf ∥ P U ( Ω ref ) ( u ∗ − v T ) − u ∥ U ( Ω ref ) ∥( P W ∞ − P W ℓ ) u ∗ ∥ U ,
whence the assertion follows. □
We adhere to the previous notation and denote by T = T k \mathcal{T}=\mathcal{T}_{k} T = T k , T k + 1 = T r e f ( K θ , k ) \mathcal{T}_{k+1}=\mathcal{T}_{\mathrm{ref}}(\mathcal{K}_{\theta,k}) T k + 1 = T ref ( K θ , k ) , Ω r e f k \Omega_{\mathrm{ref}}^{k} Ω ref k the refinements and approximate solutions, generated by Reduce (until termination). Accordingly, u k u_{k} u k stands for the solution of (22) in U k = U T k \mathbb{U}_{k}=\mathbb{U}_{\mathcal{T}_{k}} U k = U T k . Moreover, we abbreviate W k + m − j ℓ : = W ℓ ( T k + m − j , T k + m + 1 − j ) \mathbb{W}^{\ell}_{k+m-j}:=\mathbb{W}^{\ell}(\mathcal{T}_{k+m-j},\mathcal{T}_{k+m+1-j}) W k + m − j ℓ := W ℓ ( T k + m − j , T k + m + 1 − j ) , vis k + m − j ( f ) : = vis T m + k − j ( f , T m + k − j ) \operatorname{vis}_{k+m-j}(f):=\operatorname{vis}_{\mathcal{T}_{m+k-j}}(f,\mathcal{T}_{m+k-j}) vis k + m − j ( f ) := vis T m + k − j ( f , T m + k − j ) , j = 1 , … , m j=1,\ldots,m j = 1 , … , m .
Lemma 4.4. If Assumption CAP holds and f f f is a piecewise polynomial on T = T k \mathcal{T}=\mathcal{T}_{k} T = T k . then for any m ∈ N m\in\mathbb{N} m ∈ N
∑ j = 1 m vis m + k − j ( f ) 2 ≤ C 0 ∥ R T k ∥ Ω 2 . (84) \sum_{j=1}^{m}\operatorname{vis}_{m+k-j}(f)^{2}\leq C_{0}\lVert\mathcal{R}_{\mathcal{T}_{k}}\rVert_{\Omega}^{2}. \tag*{(84)} j = 1 ∑ m vis m + k − j ( f ) 2 ≤ C 0 ∥ R T k ∥ Ω 2 . (84) where the constant C 0 C_{0} C 0 depends only on C i n v , C C A P , κ , s , T , Ω C_{\mathrm{inv}},C_{\mathrm{CAP}},\kappa,s,\mathcal{T},\Omega C inv , C CAP , κ , s , T , Ω (see Assumption CAP ). Here C i n v C_{\mathrm{inv}} C inv is the constant appearing in a local inverse estimate for the trial spaces, see [5 ] .
Proof. First fix T \mathcal{T} T and set e T ∗ = u ∗ − u T e_{\mathcal{T}}^{*}=u^{*}-u_{\mathcal{T}} e T ∗ = u ∗ − u T , so that B e T ∗ = R T k Be_{\mathcal{T}}^{*}=\mathcal{R}_{\mathcal{T}_{k}} B e T ∗ = R T k and we can apply (82) to u ∗ − v T = e T ∗ u^{*}-v_{\mathcal{T}}=e_{\mathcal{T}}^{*} u ∗ − v T = e T ∗ . In view of Remark 4.2, this yields
vis T ( f , W ℓ ) ≤ inf u ~ ∈ U ( Ω r e f ; T r e f ) ∥ R T − B u ~ ∥ Ω r e f . (85) \operatorname{vis}_{\mathcal{T}}(f,\mathbb{W}^{\ell})\leq\inf_{\widetilde{u}\in\mathbb{U}(\Omega_{\mathrm{ref}};\mathcal{T}_{\mathrm{ref}})}\lVert\mathcal{R}_{\mathcal{T}}-B\widetilde{u}\rVert_{\Omega_{\mathrm{ref}}}. \tag*{(85)} vis T ( f , W ℓ ) ≤ u ∈ U ( Ω ref ; T ref ) inf ∥ R T − B u ∥ Ω ref . (85)
We will apply this to T = T m + k − j \mathcal{T}=\mathcal{T}_{m+k-j} T = T m + k − j , Ω r e f m + k − j \Omega_{\mathrm{ref}}^{m+k-j} Ω ref m + k − j , j = 1 , … , m j=1,\ldots,m j = 1 , … , m . Now suppose that f f f is a piecewise polynomial subordinate to the partition T k \mathcal{T}_{k} T k . Hence R T k \mathcal{R}_{\mathcal{T}_{k}} R T k is a piecewise polynomial on T k \mathcal{T}_{k} T k as well as on the refinements T k + m − j \mathcal{T}_{k+m-j} T k + m − j , j = 1 , … , m j=1,\ldots,m j = 1 , … , m . Even, when R T k \mathcal{R}_{\mathcal{T}_{k}} R T k is discontinuous there exists a positive s s s so that R T k ∈ H s ( Ω ; R q ) \mathcal{R}_{\mathcal{T}_{k}}\in H^{s}(\Omega;\mathbb{R}^{q}) R T k ∈ H s ( Ω ; R q ) . Note that the cells in Ω r e f k + m − j \Omega_{\mathrm{ref}}^{k+m-j} Ω ref k + m − j arise for j ≤ m j\leq m j ≤ m from at least one subdivision of a cell in T k \mathcal{T}_{k} T k .
To proceed we shall make frequent use of the weak sub-additivity of the Sobolev seminorms in the form
∑ K ∈ K ∣ u ∣ H s ( K ; R q ) 2 ≤ ∣ u ∣ H s ( Ω K ) 2 , (86) \sum_{K\in\mathcal{K}}\lvert u\rvert_{H^{s}(K;\mathbb{R}^{q})}^{2}\leq\lvert u\rvert_{H^{s}(\Omega_{\mathcal{K}})}^{2}, \tag*{(86)} K ∈ K ∑ ∣ u ∣ H s ( K ; R q ) 2 ≤ ∣ u ∣ H s ( Ω K ) 2 , (86)
where K ⊂ T \mathcal{K}\subset\mathcal{T} K ⊂ T and Ω K = ⋃ { K : K ∈ K } \Omega_{\mathcal{K}}=\bigcup\{K:K\in\mathcal{K}\} Ω K = ⋃ { K : K ∈ K } . In view of (86) , we have
∑ K ′ ⊂ K K ′ children of K h K ′ 2 s ∣ R T ∣ H s ( K ′ ) 2 ≤ κ 2 s h K 2 s ∣ R T ∣ H s ( K ) 2 , K ∈ T . (87) \sum_{\substack{K'\subset K\\K'\text{ children of }K}}h_{K'}^{2s}\lvert\mathcal{R}_{\mathcal{T}}\rvert_{H^{s}(K')}^{2}\leq\kappa^{2s}h_{K}^{2s}\lvert\mathcal{R}_{\mathcal{T}}\rvert_{H^{s}(K)}^{2},\qquad K\in\mathcal{T}. \tag*{(87)} K ′ ⊂ K K ′ children of K ∑ h K ′ 2 s ∣ R T ∣ H s ( K ′ ) 2 ≤ κ 2 s h K 2 s ∣ R T ∣ H s ( K ) 2 , K ∈ T . (87)
Consider now the collection of cells K ′ ∈ T m + k + 1 − j K'\in\mathcal{T}_{m+k+1-j} K ′ ∈ T m + k + 1 − j that are contained in Ω r e f m + k − j \Omega_{\mathrm{ref}}^{m+k-j} Ω ref m + k − j . Then, such a K ′ K' K ′ has a unique parent cell K = K ( K ′ ) ∈ T k + m − j K=K(K')\in\mathcal{T}_{k+m-j} K = K ( K ′ ) ∈ T k + m − j . Denoting by h K ′ : = diam K ′ h_{K'}:=\operatorname{diam}K' h K ′ := diam K ′ the local meshsize of K ′ K' K ′ , we have by assumption h K ′ ≤ κ h K h_{K'}\leq\kappa h_{K} h K ′ ≤ κ h K for a fixed κ ∈ ( 0 , 1 ) \kappa\in(0,1) κ ∈ ( 0 , 1 ) , depending only on T \mathcal{T} T .
Now we invoke Assumption CAP to conclude that
vis m + k − j ( f ) 2 ≤ inf u ~ ∈ U ( Ω r e f k + m − j ; T m + k + 1 − j ) ∥ R T k − B u ~ ∥ Ω r e f m + k − j 2 ≤ C C A P ∑ K ′ ∈ T m + k + 1 − j K ′ ⊂ Ω r e f m + k − j h K ′ 2 s ∣ R T ∣ H s ( K ′ ; R q ) 2 . (88) \begin{aligned}
\operatorname{vis}_{m+k-j}(f)^{2}
&\leq\inf_{\widetilde{u}\in\mathbb{U}(\Omega_{\mathrm{ref}}^{k+m-j};\mathcal{T}_{m+k+1-j})}
\lVert\mathcal{R}_{\mathcal{T}_{k}}-B\widetilde{u}\rVert_{\Omega_{\mathrm{ref}}^{m+k-j}}^{2}\\
&\leq C_{\mathrm{CAP}}\sum_{\substack{K'\in\mathcal{T}_{m+k+1-j}\\K'\subset\Omega_{\mathrm{ref}}^{m+k-j}}}h_{K'}^{2s}\lvert\mathcal{R}_{\mathcal{T}}\rvert_{H^{s}(K';\mathbb{R}^{q})}^{2}. \tag*{(88)}
\end{aligned} vis m + k − j ( f ) 2 ≤ u ∈ U ( Ω ref k + m − j ; T m + k + 1 − j ) inf ∥ R T k − B u ∥ Ω ref m + k − j 2 ≤ C CAP K ′ ∈ T m + k + 1 − j K ′ ⊂ Ω ref m + k − j ∑ h K ′ 2 s ∣ R T ∣ H s ( K ′ ; R q ) 2 . (88)
Hence
∑ j = 1 m vis m + k − j ( f ) 2 ≤ C C A P ∑ j = 1 m ∑ K ∈ T k + m + 1 − j K ⊂ Ω r e f k + m − j h K 2 s ∣ R T ∣ H s ( K ; R q ) 2 . (89) \sum_{j=1}^{m} \operatorname{vis}_{m+k-j}(f)^2 \le C_{\mathrm{CAP}} \sum_{j=1}^{m} \sum_{\substack{K\in\mathcal{T}_{k+m+1-j}\\K\subset\Omega_{\mathrm{ref}}^{k+m-j}}} h_K^{2s}\lvert\mathcal{R}_{\mathcal{T}}\rvert_{H^s(K;\mathbb{R}^q)}^2. \tag*{(89)} j = 1 ∑ m vis m + k − j ( f ) 2 ≤ C CAP j = 1 ∑ m K ∈ T k + m + 1 − j K ⊂ Ω ref k + m − j ∑ h K 2 s ∣ R T ∣ H s ( K ; R q ) 2 . (89)
We proceed with partitioning the total refinement region
Ω ^ r e f k : = ⋃ j = 1 m Ω r e f m + k − j , \widehat{\Omega}_{\mathrm{ref}}^k := \bigcup_{j=1}^{m}\Omega_{\mathrm{ref}}^{m+k-j}, Ω ref k := j = 1 ⋃ m Ω ref m + k − j ,
into the collection of cells
K l : = { K ∈ T k + l : K ⊂ Ω r e f k + l , K ∩ Ω r e f k + l ′ = ∅ , l ′ < l } , l = 0 , … , m − 1 , \mathcal{K}_l := \{K\in\mathcal{T}_{k+l}: K\subset\Omega_{\mathrm{ref}}^{k+l},\ K\cap\Omega_{\mathrm{ref}}^{k+l'}=\varnothing,\ l'<l\},\qquad l=0,\ldots,m-1, K l := { K ∈ T k + l : K ⊂ Ω ref k + l , K ∩ Ω ref k + l ′ = ∅ , l ′ < l } , l = 0 , … , m − 1 ,
so that obviously
Ω ^ r e f k = ⋃ l = 0 m − 1 Ω ( K l ) , Ω ( K l ) ∩ Ω ( K q ) = ∅ , q ≠ l , (90) \widehat{\Omega}_{\mathrm{ref}}^k=\bigcup_{l=0}^{m-1}\Omega(\mathcal{K}_l),\qquad\Omega(\mathcal{K}_l)\cap\Omega(\mathcal{K}_q)=\varnothing,\qquad q\ne l, \tag*{(90)} Ω ref k = l = 0 ⋃ m − 1 Ω ( K l ) , Ω ( K l ) ∩ Ω ( K q ) = ∅ , q = l , (90)
where we denote as before for any collection K \mathcal{K} K of cells Ω ( K ) : = ⋃ { K ∈ K } \Omega(\mathcal{K}):=\bigcup\{K\in\mathcal{K}\} Ω ( K ) := ⋃ { K ∈ K } . Note next that when K ∈ K l K\in\mathcal{K}_l K ∈ K l intersects any of the regions Ω r e f k + l ′ \Omega_{\mathrm{ref}}^{k+l'} Ω ref k + l ′ , for some l ′ > l l'>l l ′ > l one must have K ⊂ Ω r e f k + l ′ K\subset\Omega_{\mathrm{ref}}^{k+l'} K ⊂ Ω ref k + l ′ . Define for K ∈ K l K\in\mathcal{K}_l K ∈ K l
d K , l : = # { l ′ > l : K ⊂ Ω r e f k + l ′ } d_{K,l}:=\#\{l'>l:K\subset\Omega_{\mathrm{ref}}^{k+l'}\} d K , l := # { l ′ > l : K ⊂ Ω ref k + l ′ }
the number of times K K K is covered by a higher level refinement region. Hence d K , l d_{K,l} d K , l is for every K ∈ K l K\in\mathcal{K}_l K ∈ K l , l = 0 , … , m − 1 l=0,\ldots,m-1 l = 0 , … , m − 1 , the number of times K K K got subdivided in the process. Therefore, invoking (86) and (87) , we obtain
∑ j = 1 m vis m + k − j ( f ) 2 ≤ C C A P ∑ l = 0 m − 1 ∑ K ∈ K l ( ∑ r = 0 d K , l κ 2 s r ) h K 2 s ∣ R T k ∣ H s ( K ; R q ) 2 . (91) \sum_{j=1}^{m}\operatorname{vis}_{m+k-j}(f)^2\le C_{\mathrm{CAP}}\sum_{l=0}^{m-1}\sum_{K\in\mathcal{K}_l}\left(\sum_{r=0}^{d_{K,l}}\kappa^{2sr}\right)h_K^{2s}\lvert\mathcal{R}_{\mathcal{T}_k}\rvert_{H^s(K;\mathbb{R}^q)}^2. \tag*{(91)} j = 1 ∑ m vis m + k − j ( f ) 2 ≤ C CAP l = 0 ∑ m − 1 K ∈ K l ∑ r = 0 ∑ d K , l κ 2 sr h K 2 s ∣ R T k ∣ H s ( K ; R q ) 2 . (91)
Since κ < 1 \kappa<1 κ < 1 and since, by (90) , the K l \mathcal{K}_l K l mark disjoint regions, we obtain, after using an inverse estimate
∑ j = 1 m vis m + k − j ( f ) 2 ≤ C C A P C κ C i n v ∑ l = 0 m − 1 ∥ R T k ∥ Ω ( K l ) 2 = : C 0 ∥ R T k ∥ Ω ^ r e f k 2 , (92) \sum_{j=1}^{m}\operatorname{vis}_{m+k-j}(f)^2\le C_{\mathrm{CAP}}C_{\kappa}C_{\mathrm{inv}}\sum_{l=0}^{m-1}\lVert\mathcal{R}_{\mathcal{T}_k}\rVert_{\Omega(\mathcal{K}_l)}^2=:C_0\lVert\mathcal{R}_{\mathcal{T}_k}\rVert_{\widehat{\Omega}_{\mathrm{ref}}^k}^2, \tag*{(92)} j = 1 ∑ m vis m + k − j ( f ) 2 ≤ C CAP C κ C inv l = 0 ∑ m − 1 ∥ R T k ∥ Ω ( K l ) 2 =: C 0 ∥ R T k ∥ Ω ref k 2 , (92)
which completes the proof of Lemma 4.4. □
We are now ready to complete the proof of Theorem 4.1.
Ad (a): If in (A1), due to failure of (75) , we have δ k + ∥ f k − B u ˉ δ ∥ Ω ≤ ε \delta_k+\lVert f_k-B\bar{u}_{\delta}\rVert_{\Omega}\le\varepsilon δ k + ∥ f k − B u ˉ δ ∥ Ω ≤ ε we obtain
∥ u ∗ − u ˉ δ ∥ U ≤ ∥ f − f k ∥ Ω + ∥ f k − B u ˉ δ ∥ Ω ≤ δ k + ∥ f k − B u ˉ δ ∥ Ω ≤ ε , \lVert u^*-\bar{u}_{\delta}\rVert_U\le\lVert f-f_k\rVert_{\Omega}+\lVert f_k-B\bar{u}_{\delta}\rVert_{\Omega}\le\delta_k+\lVert f_k-B\bar{u}_{\delta}\rVert_{\Omega}\le\varepsilon, ∥ u ∗ − u ˉ δ ∥ U ≤ ∥ f − f k ∥ Ω + ∥ f k − B u ˉ δ ∥ Ω ≤ δ k + ∥ f k − B u ˉ δ ∥ Ω ≤ ε ,
so that, by definition of u ε u_{\varepsilon} u ε in this case, the scheme meets the target accuracy upon termination.
Ad (b): Since the load in Reduce is a piecewise polynomial on the input partition, Lemma 4.4 says that (47) holds. The claim follows then from Theorem 3.2 with m , ρ m,\rho m , ρ satisfying (65) .
Ad (c): Suppose the scheme terminates in (A2). The input u ˉ k , f k \bar{u}_k,f_k u ˉ k , f k of Reduce in (A2) must have failed (76) , hence satisfies δ k ≤ ω ∥ f k − B u ˉ k ∥ Ω \delta_k\le\omega\lVert f_k-B\bar{u}_k\rVert_{\Omega} δ k ≤ ω ∥ f k − B u ˉ k ∥ Ω . Under Assumption (CAP), if u k + 1 , T k + 1 u_{k+1},\mathcal{T}_{k+1} u k + 1 , T k + 1 are the output of Reduce in step (A2), we know from Theorem 3.2 together with Lemma 4.4 that the exact solution u k ∗ : = B − 1 f k u_k^*:=B^{-1}f_k u k ∗ := B − 1 f k satisfies ∥ u k ∗ − u k + 1 ∥ U ≤ ρ ∥ u k ∗ − u ˉ k ∥ U \lVert u_k^*-u_{k+1}\rVert_U\le\rho\lVert u_k^*-\bar{u}_k\rVert_U ∥ u k ∗ − u k + 1 ∥ U ≤ ρ ∥ u k ∗ − u ˉ k ∥ U , where, as a result of (A1), Solve [ f k , T k ] = u ˉ k \operatorname{Solve}[f_k,\mathcal{T}_k]=\bar{u}_k Solve [ f k , T k ] = u ˉ k . Hence
∥ u ∗ − u k + 1 ∥ U ≤ ∥ u ∗ − u k ∗ ∥ U + ∥ u k ∗ − u k + 1 ∥ U = ∥ f − f k ∥ Ω + ∥ u k ∗ − u k + 1 ∥ U ≤ δ k + ρ ∥ u k ∗ − u ˉ k ∥ U ≤ (4.7) ω ∥ f k − B u ˉ k ∥ Ω + ρ ∥ u k ∗ − u ˉ k ∥ U = ( ρ + ω ) ∥ u k ∗ − u ˉ k ∥ U . \begin{aligned}
\lVert u^*-u_{k+1}\rVert_U &\leq\lVert u^*-u_k^*\rVert_U+\lVert u_k^*-u_{k+1}\rVert_U=\lVert f-f_k\rVert_\Omega+\lVert u_k^*-u_{k+1}\rVert_U\\
&\leq\delta_k+\rho\lVert u_k^*-\bar{u}_k\rVert_U\mathrel{\overset{\text{(4.7)}}{\leq}}\omega\lVert f_k-B\bar{u}_k\rVert_\Omega+\rho\lVert u_k^*-\bar{u}_k\rVert_U\\
&=(\rho+\omega)\lVert u_k^*-\bar{u}_k\rVert_U.
\end{aligned} ∥ u ∗ − u k + 1 ∥ U ≤ ∥ u ∗ − u k ∗ ∥ U + ∥ u k ∗ − u k + 1 ∥ U = ∥ f − f k ∥ Ω + ∥ u k ∗ − u k + 1 ∥ U ≤ δ k + ρ ∥ u k ∗ − u ˉ k ∥ U ≤ (4.7) ω ∥ f k − B u ˉ k ∥ Ω + ρ ∥ u k ∗ − u ˉ k ∥ U = ( ρ + ω ) ∥ u k ∗ − u ˉ k ∥ U .
On the other hand,
∥ u k ∗ − u ˉ k ∥ U ≤ ∥ u k ∗ − u ∗ ∥ U + ∥ u ∗ − u ˉ k ∥ U = ∥ f k − f ∥ Ω + ∥ u ∗ − u ˉ k ∥ U ≤ δ k + ∥ u ∗ − u ˉ k ∥ U ≤ ω ∥ u k ∗ − u ˉ k ∥ U + ∥ u ∗ − u ˉ k ∥ U , \begin{aligned}
\lVert u_k^*-\bar{u}_k\rVert_U\leq\lVert u_k^*-u^*\rVert_U+\lVert u^*-\bar{u}_k\rVert_U=\lVert f_k-f\rVert_\Omega+\lVert u^*-\bar{u}_k\rVert_U \\
&\leq\delta_k+\lVert u^*-\bar{u}_k\rVert_U\leq\omega\lVert u_k^*-\bar{u}_k\rVert_U+\lVert u^*-\bar{u}_k\rVert_U,
\end{aligned} ∥ u k ∗ − u ˉ k ∥ U ≤ ∥ u k ∗ − u ∗ ∥ U + ∥ u ∗ − u ˉ k ∥ U = ∥ f k − f ∥ Ω + ∥ u ∗ − u ˉ k ∥ U ≤ δ k + ∥ u ∗ − u ˉ k ∥ U ≤ ω ∥ u k ∗ − u ˉ k ∥ U + ∥ u ∗ − u ˉ k ∥ U ,
which, upon combining with the preceding bound, yields
∥ u ∗ − u k + 1 ∥ U ≤ ω + ρ 1 − ω ∥ u ∗ − u k ∥ U . (93) \lVert u^*-u_{k+1}\rVert_U\leq\frac{\omega+\rho}{1-\omega}\lVert u^*-u_k\rVert_U. \tag*{(93)} ∥ u ∗ − u k + 1 ∥ U ≤ 1 − ω ω + ρ ∥ u ∗ − u k ∥ U . (93)
In view of (74) , this confirms (78) and finishes the proof of (c). □ \square □
Theorem 4.1 does still not quantify the total work yet, needed to meet the target accuracy. It cannot do so because we do not know when the while-loop (76) terminates, i.e., how fast f δ → f f_\delta\to f f δ → f and how fast ∥ f − B u ~ δ ∥ Ω → 0 \lVert f-B\widetilde{u}_\delta\rVert_\Omega\to0 ∥ f − B u δ ∥ Ω → 0 in step (A1). Such quantifications require additional information about f f f beyond just f ∈ L 2 f\in L_2 f ∈ L 2 , see Remark 3.6. In the next section we discuss exemplary conditions on f f f that lead to complexity bounds.
Complexity - a Light Version
We continue focusing solely on piecewise polynomial perturbations of f f f because this suffices first, to bring out the role of vis T ( f , W ℓ ) \operatorname{vis}_{\mathcal{T}}(f,W^\ell) vis T ( f , W ℓ ) , and second, to highlight those aspects where arguments have to differ from the lines in Afem. In principle, further perturbations, caused e.g. by more general coefficients in B \mathcal{B} B for which B u T B u_{\mathcal{T}} B u T is no longer piecewise polynomial, or inexact solves can be treated in a similar fashion, following essentially the strategy in [22 ] . To account for these further perturbation in complexity estimates would require - on the current level of generality - corresponding assumptions that need to be checked in each concrete case at hand.
Again, since we haven’t specified the structure of T \mathcal{T} T , we work under the following additional requirement which is known to hold in many relevant scenarios and plays the same role in classical Afem scenarios, see e.g. [3 , 23 ] .
RSP: (Refinement Summation Property) One has for K j = K ( T j , θ ) K_j=\mathcal{K}(\mathcal{T}_j,\theta) K j = K ( T j , θ )
# T N − # T 0 ≲ ∑ j = 0 N − 1 # K j , (94) \#\mathcal{T}_N-\#\mathcal{T}_0\lesssim\sum_{j=0}^{N-1}\#\mathcal{K}_j, \tag*{(94)} # T N − # T 0 ≲ j = 0 ∑ N − 1 # K j , (94)
where the proportionality constant is independent of N N N .
Finally, we introduce the approximation classes A r = A L 2 r × A U r \mathcal{A}^r=\mathcal{A}_{L_2}^r\times\mathcal{A}_U^r A r = A L 2 r × A U r , for some r > 0 r>0 r > 0 , comprised of all pairs ( f , B − 1 f ) ∈ L 2 × U (f,\mathcal{B}^{-1}f)\in L_2\times U ( f , B − 1 f ) ∈ L 2 × U with the following property:
(P1): there exists a C f < ∞ C_f<\infty C f < ∞ such that
N r inf T ∈ T ( # T − # T 0 ) ≤ N ∥ f − f T ∥ L 2 ≤ C f , (95) N^r\inf_{\substack{\mathcal{T}\in\mathbb{T}\\(\#\mathcal{T}-\#\mathcal{T}_0)\leq N}}\lVert f-f_{\mathcal{T}}\rVert_{L_2}\leq C_f, \tag*{(95)} N r T ∈ T ( # T − # T 0 ) ≤ N inf ∥ f − f T ∥ L 2 ≤ C f , (95)
where f T f_{\mathcal{T}} f T is the L 2 L_2 L 2 -projection of f f f to the space of all piecewise polynomials P T \mathbb{P}_{\mathcal{T}} P T in H s ( Ω ; R q ) H^s(\Omega;\mathbb{R}^q) H s ( Ω ; R q ) subordinate to T ∈ T \mathcal{T}\in\mathbb{T} T ∈ T .
(P2) For u = B − 1 f u=\mathcal{B}^{-1}f u = B − 1 f , there exits a constant C u < ∞ C_u<\infty C u < ∞ such that
N r inf T ∈ T ( # T − # T 0 ) ≤ N ∥ u − u T ∥ U ≤ C u , (96) N^r\inf_{\substack{\mathcal{T}\in\mathbb{T}\\(\#\mathcal{T}-\#\mathcal{T}_0)\leq N}}\lVert u-u_{\mathcal{T}}\rVert_U\leq C_u, \tag*{(96)} N r T ∈ T ( # T − # T 0 ) ≤ N inf ∥ u − u T ∥ U ≤ C u , (96)
The smallest such constants C f C_f C f , C u C_u C u for which (95) , (96) hold respectively, define semiquasi-norms ∣ f ∣ A r ( L 2 ) |f|_{\mathcal{A}^r(L_2)} ∣ f ∣ A r ( L 2 ) , ∣ u ∣ A r ( U ) |u|_{\mathcal{A}^r(U)} ∣ u ∣ A r ( U ) , so that ∥ f ∥ L 2 + ∣ f ∣ A r ( L 2 ) \|f\|_{L_2}+|f|_{\mathcal{A}^r(L_2)} ∥ f ∥ L 2 + ∣ f ∣ A r ( L 2 ) and ∥ u ∥ U + ∣ u ∣ A r ( U ) \|u\|_U+|u|_{\mathcal{A}^r(U)} ∥ u ∥ U + ∣ u ∣ A r ( U ) are (quasi-)norms on L 2 L_2 L 2 , U U U , respectively.
Hence, given ε > 0 \varepsilon>0 ε > 0 , there exists a T ε ∈ T \mathcal{T}_\varepsilon\in\mathbb{T} T ε ∈ T such that f ∈ A r ( L 2 ) f\in\mathcal{A}^r(L_2) f ∈ A r ( L 2 ) can be approximated in L 2 L_2 L 2 by a piecewise polynomial f T ε f_{\mathcal{T}_\varepsilon} f T ε to accuracy ε \varepsilon ε , i.e., ∥ f − f T ε ∥ L 2 ≤ ε \|f-f_{\mathcal{T}_\varepsilon}\|_{L_2}\leq\varepsilon ∥ f − f T ε ∥ L 2 ≤ ε , where for some multiplicative constant independent of f f f ,
# T ε − # T 0 ≲ ∣ f ∣ A r ( L 2 ) 1 / r ε − 1 / r . (97) \#\mathcal{T}_\varepsilon-\#\mathcal{T}_0\lesssim|f|_{\mathcal{A}^r(L_2)}^{1/r}\varepsilon^{-1/r}. \tag*{(97)} # T ε − # T 0 ≲ ∣ f ∣ A r ( L 2 ) 1/ r ε − 1/ r . (97)
An analogous relation holds for u u u .
We follow [22 ] and assume that the routine APPR \operatorname{APPR} APPR has the following property which can only hold when f ∈ A r f\in\mathcal{A}^r f ∈ A r .
Assumption Af: The pair ( f , APPR ) (f,\operatorname{APPR}) ( f , APPR ) is r r r -optimal, i.e., for a given T \mathcal{T} T , the output ( T ^ , f T ^ ) (\widehat{\mathcal{T}},f_{\widehat{\mathcal{T}}}) ( T , f T ) of APPR [ f , T ; δ ] \operatorname{APPR}[f,\mathcal{T};\delta] APPR [ f , T ; δ ] satisfies for any δ > 0 \delta>0 δ > 0
# T ^ − # T ≤ c ( f ) 1 / r δ − 1 / r , ∥ f − f T ^ ∥ Ω ≤ δ . (98) \#\widehat{\mathcal{T}}-\#\mathcal{T}\leq c(f)^{1/r}\delta^{-1/r},\qquad\|f-f_{\widehat{\mathcal{T}}}\|_{\Omega}\leq\delta. \tag*{(98)} # T − # T ≤ c ( f ) 1/ r δ − 1/ r , ∥ f − f T ∥ Ω ≤ δ . (98)
where c ( f ) c(f) c ( f ) depends only on f f f .
For instance, if suitable sufficiently accurate quadrature methods are available one can employ the Binev-DeVore tree algorithm (in a perturbed form) to generate f δ f_\delta f δ , see e.g. [15 ] .
Theorem 5.1. Adhering to the above notation, the following hold:
(i) Under Assumptions Af , and CAP , Algorithm ALSM [ B , f , θ , ε ] \operatorname{ALSM}[\mathcal{B},f,\theta,\varepsilon] ALSM [ B , f , θ , ε ] terminates after finitely many steps, and outputs a partition T ε ∈ T \mathcal{T}_\varepsilon\in\mathbb{T} T ε ∈ T such that
∥ u ∗ − u T ε ∥ U ≤ ε . (99) \|u^*-u_{\mathcal{T}_\varepsilon}\|_U\leq\varepsilon. \tag*{(99)} ∥ u ∗ − u T ε ∥ U ≤ ε . (99)
(ii) Suppose in addition that Assumption RSP holds and that ( f , u ∗ = B − 1 f ) ∈ A r : = A r ( L 2 ) × A r ( U ) (f,u^*=\mathcal{B}^{-1}f)\in\mathcal{A}^r:=\mathcal{A}^r(L_2)\times\mathcal{A}^r(U) ( f , u ∗ = B − 1 f ) ∈ A r := A r ( L 2 ) × A r ( U ) . Then, for any θ ∈ ( 0 , 1 ) \theta\in(0,1) θ ∈ ( 0 , 1 ) the final partition T ε \mathcal{T}_\varepsilon T ε , produced by ALSM [ B , f , θ , ε ] \operatorname{ALSM}[\mathcal{B},f,\theta,\varepsilon] ALSM [ B , f , θ , ε ] , satisfies
# T ε − # T 0 ≲ ε − 1 / r ∣ ( f , u ∗ ) ∣ A r 1 / r , ε > 0 , (100) \#\mathcal{T}_\varepsilon-\#\mathcal{T}_0\lesssim\varepsilon^{-1/r}|(f,u^*)|_{\mathcal{A}^r}^{1/r},\qquad\varepsilon>0, \tag*{(100)} # T ε − # T 0 ≲ ε − 1/ r ∣ ( f , u ∗ ) ∣ A r 1/ r , ε > 0 , (100)
with a constant depending on θ , T \theta,\mathbb{T} θ , T and on the constants in Assumptions Af, CAP, RSP.
Remark 5.2. There is no constraint on θ \theta θ other than θ ∈ ( 0 , 1 ) \theta\in(0,1) θ ∈ ( 0 , 1 ) .
Proof of Theorem 5.1:
The proof of Theorem 5.1 is based on three Lemmata. The first one concerns the role of Dörfler marking in the present context.
Lemma 5.3. Assume that T ~ ≻ T \widetilde{\mathcal{T}}\succ\mathcal{T} T ≻ T is any refinement with refinement region Ω ~ r e f \widetilde{\Omega}_{\mathrm{ref}} Ω ref such that
∥ u ∗ − u T ~ ∥ U 2 ≤ λ ∥ u ∗ − u T ∥ U 2 (101) \|u^*-u_{\widetilde{\mathcal{T}}}\|_U^2\leq\lambda\|u^*-u_{\mathcal{T}}\|_U^2 \tag*{(101)} ∥ u ∗ − u T ∥ U 2 ≤ λ ∥ u ∗ − u T ∥ U 2 (101)
holds for some λ < 1 \lambda<1 λ < 1 .
Then, one must have
∥ R T ∥ Ω ~ r e f 2 ≥ ( 1 − λ ) ∥ R T ∥ Ω 2 , (102) \|\mathcal{R}_{\mathcal{T}}\|_{\widetilde{\Omega}_{\mathrm{ref}}}^2\geq(1-\lambda)\|\mathcal{R}_{\mathcal{T}}\|_{\Omega}^2, \tag*{(102)} ∥ R T ∥ Ω ref 2 ≥ ( 1 − λ ) ∥ R T ∥ Ω 2 , (102)
in other words the refinement must obey a bulk criterion.
Proof. Let Ω ~ r e f c : = Ω ∖ Ω ~ r e f \widetilde{\Omega}_{\mathrm{ref}}^c:=\Omega\setminus\widetilde{\Omega}_{\mathrm{ref}} Ω ref c := Ω ∖ Ω ref , R ~ T c : = χ Ω ∖ Ω ~ r e f R T \widetilde{\mathcal{R}}_{\mathcal{T}}^c:=\chi_{\Omega\setminus\widetilde{\Omega}_{\mathrm{ref}}}\mathcal{R}_{\mathcal{T}} R T c := χ Ω ∖ Ω ref R T . Consider the variational problem: find z T ∈ U z_{\mathcal{T}}\in U z T ∈ U such that
( B z T , B v ) Ω = ( R ~ T c , B v ) Ω , v ∈ U . (103) (\mathcal{B}z_{\mathcal{T}},\mathcal{B}v)_\Omega=(\widetilde{\mathcal{R}}_{\mathcal{T}}^c,\mathcal{B}v)_\Omega,\qquad v\in U. \tag*{(103)} ( B z T , B v ) Ω = ( R T c , B v ) Ω , v ∈ U . (103)
This is a well posed problem and
∥ z T ∥ U = ∥ B z T ∥ Ω = ∥ R ~ T c ∥ Ω = ∥ R T ∥ Ω ~ r e f c . (104) \|z_{\mathcal{T}}\|_U=\|\mathcal{B}z_{\mathcal{T}}\|_\Omega=\|\widetilde{\mathcal{R}}_{\mathcal{T}}^c\|_\Omega=\|\mathcal{R}_{\mathcal{T}}\|_{\widetilde{\Omega}_{\mathrm{ref}}^c}. \tag*{(104)} ∥ z T ∥ U = ∥ B z T ∥ Ω = ∥ R T c ∥ Ω = ∥ R T ∥ Ω ref c . (104)
By definition,
∥ u ∗ − u T ~ ∥ U = sup v ∈ U ( ( I − P T ~ ) u ∗ , v ) U ∥ v ∥ U = sup v ∈ U ( ( I − P T ~ ) ( u ∗ − u T ) , v ) U ∥ v ∥ U = sup v ∈ U ( R T , B ( I − P T ~ ) v ) Ω ∥ B v ∥ Ω ≥ ( R T , B ( ( I − P T ~ ) z T ) ) Ω ∥ R ~ T c ∥ Ω . \begin{aligned}
\lVert u^* - u_{\widetilde{\mathcal T}}\rVert_U
&= \sup_{v\in U}\frac{((I-P_{\widetilde{\mathcal T}})u^*,v)_U}{\lVert v\rVert_U}
= \sup_{v\in U}\frac{((I-P_{\widetilde{\mathcal T}})(u^*-u_{\mathcal T}),v)_U}{\lVert v\rVert_U}\\
&= \sup_{v\in U}\frac{(\mathcal R_{\mathcal T},B(I-P_{\widetilde{\mathcal T}})v)_\Omega}{\lVert Bv\rVert_\Omega}\\
&\ge\frac{(\mathcal R_{\mathcal T},B((I-P_{\widetilde{\mathcal T}})z_{\mathcal T}))_\Omega}{\lVert\widetilde{\mathcal R}_{\mathcal T}^c\rVert_\Omega}.
\end{aligned} ∥ u ∗ − u T ∥ U = v ∈ U sup ∥ v ∥ U (( I − P T ) u ∗ , v ) U = v ∈ U sup ∥ v ∥ U (( I − P T ) ( u ∗ − u T ) , v ) U = v ∈ U sup ∥ B v ∥ Ω ( R T , B ( I − P T ) v ) Ω ≥ ∥ R T c ∥ Ω ( R T , B (( I − P T ) z T ) ) Ω .
Now, since T ≺ T ~ \mathcal T\prec\widetilde{\mathcal T} T ≺ T , hence U T ⊂ U T ~ U_{\mathcal T}\subset U_{\widetilde{\mathcal T}} U T ⊂ U T
( R T , B ( ( I − P T ~ ) z T ) ) Ω = ( z T , ( I − P U T ~ ) ( u ∗ − u T ) ) U = ( z T , u ∗ − u T ) U = ( B z T , B ( u ∗ − u T ) ) Ω = ( R ~ T c , B ( u ∗ − u T ) ) Ω = ( R ~ T c , R T ) Ω = ∥ R T ∥ Ω ∖ Ω r e f 2 . \begin{aligned}
(\mathcal R_{\mathcal T},B((I-P_{\widetilde{\mathcal T}})z_{\mathcal T}))_\Omega
&=(z_{\mathcal T},(I-P_{U_{\widetilde{\mathcal T}}})(u^*-u_{\mathcal T}))_U
=(z_{\mathcal T},u^*-u_{\mathcal T})_U\\
&=(Bz_{\mathcal T},B(u^*-u_{\mathcal T}))_\Omega
=(\widetilde{\mathcal R}_{\mathcal T}^c,B(u^*-u_{\mathcal T}))_\Omega\\
&=(\widetilde{\mathcal R}_{\mathcal T}^c,\mathcal R_{\mathcal T})_\Omega
=\lVert\mathcal R_{\mathcal T}\rVert_{\Omega\setminus\Omega_{\mathrm{ref}}}^2.
\end{aligned} ( R T , B (( I − P T ) z T ) ) Ω = ( z T , ( I − P U T ) ( u ∗ − u T ) ) U = ( z T , u ∗ − u T ) U = ( B z T , B ( u ∗ − u T ) ) Ω = ( R T c , B ( u ∗ − u T ) ) Ω = ( R T c , R T ) Ω = ∥ R T ∥ Ω ∖ Ω ref 2 .
which gives
∥ u ∗ − u T ~ ∥ U ≥ ∥ R T ∥ Ω ∖ Ω r e f . \lVert u^*-u_{\widetilde{\mathcal T}}\rVert_U\ge\lVert\mathcal R_{\mathcal T}\rVert_{\Omega\setminus\Omega_{\mathrm{ref}}}. ∥ u ∗ − u T ∥ U ≥ ∥ R T ∥ Ω ∖ Ω ref .
Now suppose that ∥ R T ∥ Ω r e f 2 = κ ∥ R T ∥ Ω 2 \lVert\mathcal R_{\mathcal T}\rVert_{\Omega_{\mathrm{ref}}}^2=\kappa\lVert\mathcal R_{\mathcal T}\rVert_\Omega^2 ∥ R T ∥ Ω ref 2 = κ ∥ R T ∥ Ω 2 for some κ < 1 \kappa<1 κ < 1 . Then ( 1 − κ ) ∥ R T ∥ Ω 2 = ∥ R T ∥ Ω ∖ Ω r e f 2 (1-\kappa)\lVert\mathcal R_{\mathcal T}\rVert_\Omega^2=\lVert\mathcal R_{\mathcal T}\rVert_{\Omega\setminus\Omega_{\mathrm{ref}}}^2 ( 1 − κ ) ∥ R T ∥ Ω 2 = ∥ R T ∥ Ω ∖ Ω ref 2 . Thus,
∥ u ∗ − u T ~ ∥ U 2 ≥ ( 1 − κ ) ∥ u ∗ − u T ∥ U 2 , \lVert u^*-u_{\widetilde{\mathcal T}}\rVert_U^2\ge(1-\kappa)\lVert u^*-u_{\mathcal T}\rVert_U^2, ∥ u ∗ − u T ∥ U 2 ≥ ( 1 − κ ) ∥ u ∗ − u T ∥ U 2 ,
and (101) says that λ ≥ ( 1 − κ ) \lambda\ge(1-\kappa) λ ≥ ( 1 − κ ) which gives (102) . □ \square □
The next lemma concerns the complexity of step (A1) in ALSM when f f f satisfies Assumption Af.
Lemma 5.4. If ( f , A p p r ) (f,\mathrm{Appr}) ( f , Appr ) is r r r -optimal the output T k \mathcal T_k T k , f k f_k f k , u ˉ k \bar u_k u ˉ k of step (A1) in ALSM satisfies
# T ~ k − # T k ≤ C c ( f ) 1 / r δ k − 1 / r . (105) \#\widetilde{\mathcal T}_k-\#\mathcal T_k\le Cc(f)^{1/r}\delta_k^{-1/r}. \tag*{(105)} # T k − # T k ≤ C c ( f ) 1/ r δ k − 1/ r . (105) where C C C depends only on r r r and ω \omega ω .
Moreover, if ALSM terminates in (A1), there holds
# T ~ k − # T k ≤ C c ( f ) 1 / r ε − 1 / r , (106) \#\widetilde{\mathcal T}_k-\#\mathcal T_k\le Cc(f)^{1/r}\varepsilon^{-1/r}, \tag*{(106)} # T k − # T k ≤ C c ( f ) 1/ r ε − 1/ r , (106) with the same dependence of C C C as above.
Proof. Suppose that in step (A1) δ ≤ ω ∥ f δ − B u ˉ δ ∥ Ω \delta\le\omega\lVert f_\delta-B\bar u_\delta\rVert_\Omega δ ≤ ω ∥ f δ − B u ˉ δ ∥ Ω , so that (A1) outputs f k f_k f k , T ~ k \widetilde{\mathcal T}_k T k , u ˉ k \bar u_k u ˉ k . If this occurs when having entered (A1) for the first time (i.e. δ 0 = δ = ∥ f ∥ Ω \delta_0=\delta=\lVert f\rVert_\Omega δ 0 = δ = ∥ f ∥ Ω ), we observe that ∥ f − f δ ∥ Ω ≤ δ \lVert f-f_\delta\rVert_\Omega\le\delta ∥ f − f δ ∥ Ω ≤ δ implies ∥ f δ ∥ Ω ≤ 2 δ \lVert f_\delta\rVert_\Omega\le2\delta ∥ f δ ∥ Ω ≤ 2 δ , hence
∥ f δ − B u ˉ δ ∥ Ω ≤ ∥ f δ ∥ Ω + ∥ u ˉ δ ∥ U ≤ 3 δ , \lVert f_\delta-B\bar u_\delta\rVert_\Omega\le\lVert f_\delta\rVert_\Omega+\lVert\bar u_\delta\rVert_U\le3\delta, ∥ f δ − B u ˉ δ ∥ Ω ≤ ∥ f δ ∥ Ω + ∥ u ˉ δ ∥ U ≤ 3 δ ,
by stability. Now r r r -optimality says that
# T ~ 0 − # T 0 ≤ 3 1 / r c ( f ) 1 / r ( 3 δ ) − 1 / r ≤ 3 1 / r c ( f ) 1 / r ∥ f k − B u ˉ k ∥ Ω − 1 / r , \#\widetilde{\mathcal T}_0-\#\mathcal T_0\le3^{1/r}c(f)^{1/r}(3\delta)^{-1/r}\le3^{1/r}c(f)^{1/r}\lVert f_k-B\bar u_k\rVert_\Omega^{-1/r}, # T 0 − # T 0 ≤ 3 1/ r c ( f ) 1/ r ( 3 δ ) − 1/ r ≤ 3 1/ r c ( f ) 1/ r ∥ f k − B u ˉ k ∥ Ω − 1/ r ,
which confirms the assertion in this case. If (A1) terminates at the p p p th step of the loop (76) for some p > 1 p>1 p > 1 and let T ~ k , q \widetilde{\mathcal T}_{k,q} T k , q , f δ , q f_{\delta,q} f δ , q , u ˉ δ , q \bar u_{\delta,q} u ˉ δ , q denote the quantities, generated at the q q q th stage in that loop for some q ≤ p q\le p q ≤ p . Then, for q < p q<p q < p , one has ω ∥ f δ , q − B u ˉ δ , q ∥ Ω < 2 − q δ k \omega\lVert f_{\delta,q}-B\bar u_{\delta,q}\rVert_\Omega<2^{-q}\delta_k ω ∥ f δ , q − B u ˉ δ , q ∥ Ω < 2 − q δ k while ω ∥ f δ , q − B u ˉ δ , q ∥ Ω ≥ 2 − p δ k \omega\lVert f_{\delta,q}-B\bar u_{\delta,q}\rVert_\Omega\ge2^{-p}\delta_k ω ∥ f δ , q − B u ˉ δ , q ∥ Ω ≥ 2 − p δ k . On the other hand, (98) implies that
# T ~ k , p − # T k = # T ~ k , p − # T ~ k , p − 1 + ⋯ + # T ~ k , 1 − # T k ≤ c ( f ) 1 / r ∑ q = 0 p ( 2 − q δ k ) − 1 / r ≤ c ( f ) 1 / r 2 ( p − 1 ) / r δ k − 1 / r , \begin{aligned}
\#\widetilde{\mathcal T}_{k,p}-\#\mathcal T_k=\#\widetilde{\mathcal T}_{k,p}-\#\widetilde{\mathcal T}_{k,p-1}+\cdots+\#\widetilde{\mathcal T}_{k,1}-\#\mathcal T_k \\
&\le c(f)^{1/r}\sum_{q=0}^{p}(2^{-q}\delta_k)^{-1/r}\le c(f)^{1/r}2^{(p-1)/r}\delta_k^{-1/r},
\end{aligned} # T k , p − # T k = # T k , p − # T k , p − 1 + ⋯ + # T k , 1 − # T k ≤ c ( f ) 1/ r q = 0 ∑ p ( 2 − q δ k ) − 1/ r ≤ c ( f ) 1/ r 2 ( p − 1 ) / r δ k − 1/ r ,
as claimed under (105) .
To confirm (106) , observe that
ε < 2 − ( p − 1 ) δ k + ∥ f k , p − 1 − B u ˉ k , p − 1 ∥ Ω , \varepsilon<2^{-(p-1)}\delta_k+\lVert f_{k,p-1}-B\bar u_{k,p-1}\rVert_\Omega, ε < 2 − ( p − 1 ) δ k + ∥ f k , p − 1 − B u ˉ k , p − 1 ∥ Ω ,
while also ω ∥ f k , p − 1 − B u ˉ k , p − 1 ∥ Ω ≤ 2 − ( p − 1 ) δ k \omega\lVert f_{k,p-1}-\mathcal{B}\bar{u}_{k,p-1}\rVert_{\Omega}\le2^{-(p-1)}\delta_k ω ∥ f k , p − 1 − B u ˉ k , p − 1 ∥ Ω ≤ 2 − ( p − 1 ) δ k . Hence ϵ ≤ ( 2 − ( p − 1 ) + ω − 1 ) δ k \epsilon\le(2^{-(p-1)}+\omega^{-1})\delta_k ϵ ≤ ( 2 − ( p − 1 ) + ω − 1 ) δ k whence the assertion follows. □ \square □
The statement of the following lemma is also a standard step in the complexity analysis of Afem. However, the argument needs to be modified because an error reduction can only be asserted after a group of subdivision steps.
Lemma 5.5. Given θ ∈ ( 0 , 1 ) \theta\in(0,1) θ ∈ ( 0 , 1 ) , assume that ( u ∗ , f ) ∈ A r (u^*,f)\in\mathcal{A}^r ( u ∗ , f ) ∈ A r . For ρ < 1 \rho<1 ρ < 1 according to (65) , fixed let ζ , ω > 0 \zeta,\omega>0 ζ , ω > 0 be constants such that (74) holds and
1 − ρ − 2 ( ζ + ( 2 + ζ ) ω ) 2 ≥ θ . (107) 1-\rho^{-2}(\zeta+(2+\zeta)\omega)^2\ge\theta. \tag*{(107)} 1 − ρ − 2 ( ζ + ( 2 + ζ ) ω ) 2 ≥ θ . (107) Given any admissible T = T ~ k \mathcal{T}=\widetilde{\mathcal{T}}_k T = T k , let f T = f k ∈ P T f_{\mathcal{T}}=f_k\in\mathbb{P}_{\mathcal{T}} f T = f k ∈ P T and u ˉ T = Solve [ f T , T ] ∈ U T \bar{u}_{\mathcal{T}}=\operatorname{Solve}[f_{\mathcal{T}},\mathcal{T}]\in\mathbb{U}_{\mathcal{T}} u ˉ T = Solve [ f T , T ] ∈ U T be the (exact) solution of the discrete problem (22) with right hand side f T f_{\mathcal{T}} f T . If
∥ f − f T ∥ Ω ≤ δ k ≤ ω ∥ f T − B u ˉ T ∥ Ω (108) \lVert f-f_{\mathcal{T}}\rVert_{\Omega}\le\delta_k\le\omega\lVert f_{\mathcal{T}}-\mathcal{B}\bar{u}_{\mathcal{T}}\rVert_{\Omega} \tag*{(108)} ∥ f − f T ∥ Ω ≤ δ k ≤ ω ∥ f T − B u ˉ T ∥ Ω (108) then, the output u ˉ T r e f , T r e f \bar{u}_{\mathcal{T}_{\mathrm{ref}}},\mathcal{T}_{\mathrm{ref}} u ˉ T ref , T ref of Reduce [ T , f T , u ˉ T , θ , ρ ] \operatorname{Reduce}[\mathcal{T},f_{\mathcal{T}},\bar{u}_{\mathcal{T}},\theta,\rho] Reduce [ T , f T , u ˉ T , θ , ρ ] satisfies
# T r e f − # T ≤ C ∥ u ∗ − u ˉ T ∥ U − 1 / r ∣ u ∗ ∣ A r 1 / r , (109) \#\mathcal{T}_{\mathrm{ref}}-\#\mathcal{T}\le C\lVert u^*-\bar{u}_{\mathcal{T}}\rVert_{\mathbb{U}}^{-1/r}\lvert u^*\rvert_{\mathcal{A}^r}^{1/r}, \tag*{(109)} # T ref − # T ≤ C ∥ u ∗ − u ˉ T ∥ U − 1/ r ∣ u ∗ ∣ A r 1/ r , (109) with C C C depending only on ζ , ω , T \zeta,\omega,\mathcal{T} ζ , ω , T , and the maximal number m m m of applications of Refine \operatorname{Refine} Refine in step ( A 2 ) (A2) ( A 2 ) of Reduce [ T , f T , u ˉ T , θ , ρ ] \operatorname{Reduce}[\mathcal{T},f_{\mathcal{T}},\bar{u}_{\mathcal{T}},\theta,\rho] Reduce [ T , f T , u ˉ T , θ , ρ ] .
Proof. Given T \mathcal{T} T as in the assertion, let T ˉ \bar{\mathcal{T}} T ˉ be the smallest admissible partition T ˉ ≻ T 0 \bar{\mathcal{T}}\succ\mathcal{T}_0 T ˉ ≻ T 0 such that u ˉ T ˉ = Solve [ f , T ˉ ] \bar{u}_{\bar{\mathcal{T}}}=\operatorname{Solve}[f,\bar{\mathcal{T}}] u ˉ T ˉ = Solve [ f , T ˉ ] satisfies
∥ u ∗ − u ˉ T ˉ ∥ U ≤ ζ ∥ u ∗ − u ˉ T ∥ U , (110) \lVert u^*-\bar{u}_{\bar{\mathcal{T}}}\rVert_{\mathbb{U}}\le\zeta\lVert u^*-\bar{u}_{\mathcal{T}}\rVert_{\mathbb{U}}, \tag*{(110)} ∥ u ∗ − u ˉ T ˉ ∥ U ≤ ζ ∥ u ∗ − u ˉ T ∥ U , (110)
for some ζ ∈ ( 0 , 1 ) \zeta\in(0,1) ζ ∈ ( 0 , 1 ) to be fixed later. Then, by assumption on ( u ∗ , f ) (u^*,f) ( u ∗ , f ) ,
# T ˉ − # T 0 ≤ ζ − 1 / r ∥ u ∗ − u ˉ T ∥ U − 1 / r ∣ u ∗ ∣ A r 1 / r . (111) \#\bar{\mathcal{T}}-\#\mathcal{T}_0\le\zeta^{-1/r}\lVert u^*-\bar{u}_{\mathcal{T}}\rVert_{\mathbb{U}}^{-1/r}\lvert u^*\rvert_{\mathcal{A}^r}^{1/r}. \tag*{(111)} # T ˉ − # T 0 ≤ ζ − 1/ r ∥ u ∗ − u ˉ T ∥ U − 1/ r ∣ u ∗ ∣ A r 1/ r . (111)
Now let T ~ \widetilde{\mathcal{T}} T be the smallest common refinement of T \mathcal{T} T and T ˉ \bar{\mathcal{T}} T ˉ . Denote:
u ˉ T ~ ∈ U T ~ \bar{u}_{\widetilde{\mathcal{T}}}\in\mathbb{U}_{\widetilde{\mathcal{T}}} u ˉ T ∈ U T the (exact) solution of (22) (with right hand side f f f ),
u ˉ T ∈ U T \bar{u}_{\mathcal{T}}\in\mathbb{U}_{\mathcal{T}} u ˉ T ∈ U T is the exact discrete solution in U T \mathbb{U}_{\mathcal{T}} U T with right hand side f T f_{\mathcal{T}} f T ,
u ˉ T ~ ∈ U T ~ \bar{u}_{\widetilde{\mathcal{T}}}\in\mathbb{U}_{\widetilde{\mathcal{T}}} u ˉ T ∈ U T solves (22) in U T ~ \mathbb{U}_{\widetilde{\mathcal{T}}} U T with right hand side f T f_{\mathcal{T}} f T ,
u ˉ ∗ = B − 1 f T ∈ U \bar{u}^*= \mathcal{B}^{-1}f_{\mathcal{T}}\in\mathbb{U} u ˉ ∗ = B − 1 f T ∈ U denote the exact solution of (12) with perturbed right hand side f T f_{\mathcal{T}} f T .
Finally, let Ω ~ r e f \widetilde{\Omega}_{\mathrm{ref}} Ω ref denote the refinement region obtained when passing from T \mathcal{T} T to T ~ \widetilde{\mathcal{T}} T . Recall from Theorem 4.1 , (b), that under the above assumptions on ρ \rho ρ , the number m ′ m' m ′ of refinements needed in Reduce \operatorname{Reduce} Reduce until (72) fails is bounded by m m m . Let us denote the corresponding intermediate discrete solutions with load f T f_{\mathcal{T}} f T by u ˉ j ∈ U T j \bar{u}^j\in\mathbb{U}_{\mathcal{T}^j} u ˉ j ∈ U T j , for some T ≺ T j ⪯ T r e f \mathcal{T}\prec\mathcal{T}^j\preceq\mathcal{T}_{\mathrm{ref}} T ≺ T j ⪯ T ref , j = 0 , … , m ′ j=0,\ldots,m' j = 0 , … , m ′ , u ˉ 0 = u ˉ T \bar{u}^0=\bar{u}_{\mathcal{T}} u ˉ 0 = u ˉ T , u ˉ m ′ = u ˉ T r e f \bar{u}^{m'}=\bar{u}_{\mathcal{T}_{\mathrm{ref}}} u ˉ m ′ = u ˉ T ref . Hence
∥ f T − B u ˉ T j ∥ Ω = ∥ u ˉ ∗ − u ˉ T j ∥ U > ρ ∥ u ˉ ∗ − u ˉ T j − 1 ∥ U , j = 1 , … , m ′ − 1. (112) \lVert f_{\mathcal{T}}-\mathcal{B}\bar{u}^j_{\mathcal{T}}\rVert_{\Omega}=\lVert\bar{u}^*-\bar{u}^j_{\mathcal{T}}\rVert_{\mathbb{U}}>\rho\lVert\bar{u}^*-\bar{u}^{j-1}_{\mathcal{T}}\rVert_{\mathbb{U}},\qquad j=1,\ldots,m'-1. \tag*{(112)} ∥ f T − B u ˉ T j ∥ Ω = ∥ u ˉ ∗ − u ˉ T j ∥ U > ρ ∥ u ˉ ∗ − u ˉ T j − 1 ∥ U , j = 1 , … , m ′ − 1. (112)
We show next that for ζ \zeta ζ sufficiently small ∥ u ˉ ∗ − u ˉ T ~ ∥ U ≤ λ ∥ u ˉ ∗ − u ˉ T ∥ U \lVert\bar{u}^*-\bar{u}_{\widetilde{\mathcal{T}}}\rVert_{\mathbb{U}}\le\lambda\lVert\bar{u}^*-\bar{u}_{\mathcal{T}}\rVert_{\mathbb{U}} ∥ u ˉ ∗ − u ˉ T ∥ U ≤ λ ∥ u ˉ ∗ − u ˉ T ∥ U for some λ < 1 − θ \lambda<1-\theta λ < 1 − θ (see (101) ) in order to apply then Lemma 5.3. To that end, we have, on account of the stability of (22) , (110) , and the fact that T ~ ≺ T ~ \widetilde{\mathcal T} \prec\widetilde{\mathcal T} T ≺ T ,
∥ u ˉ ∗ − u ˉ T ~ ∥ U = ∥ u ∗ − u T ~ + u T ~ − u ˉ T ~ + u ˉ ∗ − u ∗ ∥ U ≤ ∥ u ∗ − u T ~ ∥ U + ∥ B T − 1 ( f − f T ) ∥ U + ∥ f T − f ∥ Ω ≤ 2 ∥ f T − f ∥ Ω + ∥ u ∗ − u T ~ ∥ U ≤ ζ ∥ u ∗ − u ˉ T ∥ U + 2 ∥ f T − f ∥ Ω = ζ ∥ u ˉ ∗ − u ˉ T + u ∗ − u ˉ ∗ ∥ U + 2 ∥ f T − f ∥ Ω ≤ ζ ∥ u ˉ ∗ − u ˉ T ∥ U + ( 2 + ζ ) ∥ f T − f ∥ Ω ≤ ζ ∥ u ˉ ∗ − u ˉ T ∥ U + ( 2 + ζ ) ω ∥ B u ˉ T − f T ∥ Ω = ζ ∥ u ˉ ∗ − u ˉ T ∥ U + ( 2 + ζ ) ω ∥ u ˉ ∗ − u ˉ T ∥ U = ( ζ + ( 2 + ζ ) ω ) ∥ u ˉ ∗ − u ˉ T ∥ U ≤ ρ − 1 ( ζ + ( 2 + ζ ) ω ) ∥ u ˉ ∗ − u ˉ j ∥ U , j < m ′ . (113) \begin{aligned}
\lVert\bar{u}^{*}-\bar{u}_{\widetilde{\mathcal T}}\rVert_{U}
&=\lVert u^{*}-u_{\widetilde{\mathcal T}}+u_{\widetilde{\mathcal T}}-\bar{u}_{\widetilde{\mathcal T}}+\bar{u}^{*}-u^{*}\rVert_{U}\\
&\le\lVert u^{*}-u_{\widetilde{\mathcal T}}\rVert_{U}+\lVert B_{\mathcal T}^{-1}(f-f_{\mathcal T})\rVert_{U}+\lVert f_{\mathcal T}-f\rVert_{\Omega}\\
&\le2\lVert f_{\mathcal T}-f\rVert_{\Omega}+\lVert u^{*}-u_{\widetilde{\mathcal T}}\rVert_{U}\\
&\le\zeta\lVert u^{*}-\bar{u}_{\mathcal T}\rVert_{U}+2\lVert f_{\mathcal T}-f\rVert_{\Omega}\\
&=\zeta\lVert\bar{u}^{*}-\bar{u}_{\mathcal T}+u^{*}-\bar{u}^{*}\rVert_{U}+2\lVert f_{\mathcal T}-f\rVert_{\Omega}\\
&\le\zeta\lVert\bar{u}^{*}-\bar{u}_{\mathcal T}\rVert_{U}+(2+\zeta)\lVert f_{\mathcal T}-f\rVert_{\Omega}\\
&\le\zeta\lVert\bar{u}^{*}-\bar{u}_{\mathcal T}\rVert_{U}+(2+\zeta)\omega\lVert B\bar{u}_{\mathcal T}-f_{\mathcal T}\rVert_{\Omega}\\
&=\zeta\lVert\bar{u}^{*}-\bar{u}_{\mathcal T}\rVert_{U}+(2+\zeta)\omega\lVert\bar{u}^{*}-\bar{u}_{\mathcal T}\rVert_{U}\\
&=\bigl(\zeta+(2+\zeta)\omega\bigr)\lVert\bar{u}^{*}-\bar{u}_{\mathcal T}\rVert_{U}\\
&\le\rho^{-1}\bigl(\zeta+(2+\zeta)\omega\bigr)\lVert\bar{u}^{*}-\bar{u}^{j}\rVert_{U},\qquad j<m'. \tag*{(113)}
\end{aligned} ∥ u ˉ ∗ − u ˉ T ∥ U = ∥ u ∗ − u T + u T − u ˉ T + u ˉ ∗ − u ∗ ∥ U ≤ ∥ u ∗ − u T ∥ U + ∥ B T − 1 ( f − f T ) ∥ U + ∥ f T − f ∥ Ω ≤ 2 ∥ f T − f ∥ Ω + ∥ u ∗ − u T ∥ U ≤ ζ ∥ u ∗ − u ˉ T ∥ U + 2 ∥ f T − f ∥ Ω = ζ ∥ u ˉ ∗ − u ˉ T + u ∗ − u ˉ ∗ ∥ U + 2 ∥ f T − f ∥ Ω ≤ ζ ∥ u ˉ ∗ − u ˉ T ∥ U + ( 2 + ζ ) ∥ f T − f ∥ Ω ≤ ζ ∥ u ˉ ∗ − u ˉ T ∥ U + ( 2 + ζ ) ω ∥ B u ˉ T − f T ∥ Ω = ζ ∥ u ˉ ∗ − u ˉ T ∥ U + ( 2 + ζ ) ω ∥ u ˉ ∗ − u ˉ T ∥ U = ( ζ + ( 2 + ζ ) ω ) ∥ u ˉ ∗ − u ˉ T ∥ U ≤ ρ − 1 ( ζ + ( 2 + ζ ) ω ) ∥ u ˉ ∗ − u ˉ j ∥ U , j < m ′ . (113)
Choosing ω \omega ω , ζ \zeta ζ small enough such that
λ : = ρ − 1 ( ζ + ( 2 + ζ ) ω ) 2 ≤ 1 − θ , (114) \lambda:=\rho^{-1}\bigl(\zeta+(2+\zeta)\omega\bigr)^2\le1-\theta, \tag*{(114)} λ := ρ − 1 ( ζ + ( 2 + ζ ) ω ) 2 ≤ 1 − θ , (114)
we have verified (101) . Denoting by Ω ~ r e f \widetilde{\Omega}_{\mathrm{ref}} Ω ref the refinement region corresponding to T ~ ≺ T \widetilde{\mathcal T}\prec\mathcal T T ≺ T , we apply Lemma 5.3 to f f f replaced by f T f_{\mathcal T} f T to conclude that
∥ B u ˉ j − f T ∥ Ω ~ r e f 2 ≥ θ ∥ B u ˉ T − f T ∥ Ω 2 , j = 0 , … , m ′ − 1. (115) \lVert B\bar{u}^{j}-f_{\mathcal T}\rVert_{\widetilde{\Omega}_{\mathrm{ref}}}^{2}\ge\theta\lVert B\bar{u}_{\mathcal T}-f_{\mathcal T}\rVert_{\Omega}^{2},\qquad j=0,\ldots,m'-1. \tag*{(115)} ∥ B u ˉ j − f T ∥ Ω ref 2 ≥ θ ∥ B u ˉ T − f T ∥ Ω 2 , j = 0 , … , m ′ − 1. (115)
The number of new cells generated when refining T j − 1 \mathcal T^{j-1} T j − 1 to T j \mathcal T^{j} T j , j = 1 , … , m ′ j=1,\ldots,m' j = 1 , … , m ′ is near-minimal. Hence, there exists a constant C C C such that
# T r e f − # T j ≤ C ( # T ~ − # T 0 ) ≤ C ( # T ˉ − # T 0 ) ≤ C ζ − 1 / r ∥ u ∗ − u ˉ T ∥ U − 1 / r ∣ u ∣ A r 1 / r . (116) \begin{aligned}
\#\mathcal T_{\mathrm{ref}}-\#\mathcal T^{j}\le C(\#\widetilde{\mathcal T}-\#\mathcal T_{0})\le C(\#\bar{\mathcal T}-\#\mathcal T_{0}) \\
&\le C\zeta^{-1/r}\lVert u^{*}-\bar{u}_{\mathcal T}\rVert_{U}^{-1/r}|u|_{\mathcal A^{r}}^{1/r}. \tag*{(116)}
\end{aligned} # T ref − # T j ≤ C ( # T − # T 0 ) ≤ C ( # T ˉ − # T 0 ) ≤ C ζ − 1/ r ∥ u ∗ − u ˉ T ∥ U − 1/ r ∣ u ∣ A r 1/ r . (116)
Therefore,
# T r e f − # T ≤ # T r e f − # T m ′ − 1 + ⋯ + # T 1 − # T ≤ ∑ j = 0 m ′ − 1 # T r e f − # T j ≤ m C ζ − 1 / r ∥ u ∗ − u ˉ T ∥ U − 1 / r ∣ u ∣ A r 1 / r , \begin{aligned}
\#\mathcal T_{\mathrm{ref}}-\#\mathcal T\le\#\mathcal T_{\mathrm{ref}}-\#\mathcal T^{m'-1}+\cdots+\#\mathcal T^{1}-\#\mathcal T \\
&\le\sum_{j=0}^{m'-1}\#\mathcal T_{\mathrm{ref}}-\#\mathcal T^{j} \\
&\le mC\zeta^{-1/r}\lVert u^{*}-\bar{u}_{\mathcal T}\rVert_{U}^{-1/r}|u|_{\mathcal A^{r}}^{1/r},
\end{aligned} # T ref − # T ≤ # T ref − # T m ′ − 1 + ⋯ + # T 1 − # T ≤ j = 0 ∑ m ′ − 1 # T ref − # T j ≤ m C ζ − 1/ r ∥ u ∗ − u ˉ T ∥ U − 1/ r ∣ u ∣ A r 1/ r ,
confirming (109) . □
To complete the proof of Theorem 5.1, it remains to bound the partition growth. When f ∈ A r f\in\mathcal A^{r} f ∈ A r and ( f , A p p r ) (f,\mathrm{Appr}) ( f , Appr ) is r r r -optimal (see Assumption Af), Lemma 5.4, (105) , asserts that, at the k k k th stage, the output [ T ~ k , f k , u ˉ k ] [\widetilde{\mathcal T}_{k},f_{k},\bar{u}_{k}] [ T k , f k , u ˉ k ] of step (A1) satisfies
# T ~ k − # T k ≤ C c ( f ) 1 / r δ k − 1 / r (117) \#\widetilde{\mathcal T}_{k}-\#\mathcal T_{k}\le Cc(f)^{1/r}\delta_{k}^{-1/r} \tag*{(117)} # T k − # T k ≤ C c ( f ) 1/ r δ k − 1/ r (117)
prior to termination. The same inequality holds with δ k \delta_{k} δ k replaced by ε \varepsilon ε when the scheme terminates in (A1). The constant C C C depends on T \mathcal T T , ζ \zeta ζ , ω \omega ω , ρ \rho ρ , m m m , satisfying (65) , (74) , and (107) , noting that ζ \zeta ζ and ω \omega ω are chosen in dependence of θ \theta θ which, in turn determines ξ \xi ξ in (56) and thereby ρ \rho ρ and m m m .
We know from the proof of Theorem 4.1 that Reduce[ T k , f k , u ˉ k , θ , ρ ] [\mathcal T_{k},f_{k},\bar{u}_{k},\theta,\rho] [ T k , f k , u ˉ k , θ , ρ ] produces an approximate solution u k + 1 ∈ U T k + 1 u_{k+1}\in U_{\mathcal T_{k+1}} u k + 1 ∈ U T k + 1 such that ∥ f k − B u k + 1 ∥ Ω ≤ ρ ∥ f k − B u ˉ k ∥ Ω \lVert f_{k}-Bu_{k+1}\rVert_{\Omega}\le\rho\lVert f_{k}-B\bar{u}_{k}\rVert_{\Omega} ∥ f k − B u k + 1 ∥ Ω ≤ ρ ∥ f k − B u ˉ k ∥ Ω , and that u ˉ T = u ˉ k \bar{u}_{\mathcal T}=\bar{u}_{k} u ˉ T = u ˉ k , satisfy (108) , as output of step (A1). By Lemma 5.5,
# T k + 1 − # T ~ k ≤ C ∣ u ∗ ∣ A r 1 / r ∥ u ∗ − u ˉ k ∥ U − 1 / r , \#\mathcal T_{k+1}-\#\widetilde{\mathcal T}_{k}\le C|u^{*}|_{\mathcal A^{r}}^{1/r}\lVert u^{*}-\bar{u}_{k}\rVert_{U}^{-1/r}, # T k + 1 − # T k ≤ C ∣ u ∗ ∣ A r 1/ r ∥ u ∗ − u ˉ k ∥ U − 1/ r ,
where C C C depends on ζ , T , ω , m \zeta,\mathcal{T},\omega,m ζ , T , ω , m . Since
∥ u ∗ − u ˉ k ∥ U = ∥ u ∗ − u k ∗ + u k ∗ − u ˉ k ∥ U = ∥ f − f k + f k − B u ˉ k ∥ Ω ≥ ∥ f k − B u ˉ k ∥ Ω − ∥ f − f k ∥ Ω . \begin{aligned}
\|u^*-\bar{u}_k\|_U=\|u^*-u_k^*+u_k^*-\bar{u}_k\|_U=\|f-f_k+f_k-B\bar{u}_k\|_\Omega\\
&\geq\|f_k-B\bar{u}_k\|_\Omega-\|f-f_k\|_\Omega.
\end{aligned} ∥ u ∗ − u ˉ k ∥ U = ∥ u ∗ − u k ∗ + u k ∗ − u ˉ k ∥ U = ∥ f − f k + f k − B u ˉ k ∥ Ω ≥ ∥ f k − B u ˉ k ∥ Ω − ∥ f − f k ∥ Ω .
and recalling that when exiting step (A1), we have ∥ f − f k ∥ Ω ≤ δ k \|f-f_k\|_\Omega\leq\delta_k ∥ f − f k ∥ Ω ≤ δ k and δ k ≤ ω ∥ f k − B u ˉ k ∥ Ω \delta_k\leq\omega\|f_k-B\bar{u}_k\|_\Omega δ k ≤ ω ∥ f k − B u ˉ k ∥ Ω , we conclude that ∥ u ∗ − u ˉ k ∥ U ≥ ( ω − 1 − 1 ) δ k \|u^*-\bar{u}_k\|_U\geq(\omega^{-1}-1)\delta_k ∥ u ∗ − u ˉ k ∥ U ≥ ( ω − 1 − 1 ) δ k and therefore
# T k + 1 − # T ~ k ≤ C ( ω − 1 − 1 ) − 1 / r ∣ u ∗ ∣ A r 1 / r δ k − 1 / r . (118) \#\mathcal{T}_{k+1}-\#\widetilde{\mathcal{T}}_k\leq C(\omega^{-1}-1)^{-1/r}|u^*|_{\mathcal{A}_r}^{1/r}\delta_k^{-1/r}. \tag*{(118)} # T k + 1 − # T k ≤ C ( ω − 1 − 1 ) − 1/ r ∣ u ∗ ∣ A r 1/ r δ k − 1/ r . (118)
Combining this with (117) , yields
# T k + 1 − # T k ≤ C ′ ( c ( f ) 1 / r + ∣ u ∣ A r 1 / r ) δ k − 1 / r . (119) \#\mathcal{T}_{k+1}-\#\mathcal{T}_k\leq C'(c(f)^{1/r}+|u|_{\mathcal{A}_r}^{1/r})\delta_k^{-1/r}. \tag*{(119)} # T k + 1 − # T k ≤ C ′ ( c ( f ) 1/ r + ∣ u ∣ A r 1/ r ) δ k − 1/ r . (119)
where C ′ C' C ′ depends on ζ , ω , T , ρ , θ , m \zeta,\omega,\mathcal{T},\rho,\theta,m ζ , ω , T , ρ , θ , m .
Concluding Remarks
As in the case of classical AFEM, Dörfler marking appears to be the right way to ensure linear convergence and, under natural assumptions, also optimal rates in terms of partition growth. Yet there are a few noteworthy distinctions between the convergence analyses in both scenarios. While the appearance of local meshsizes in the a posteriori error indicators, used in classical AFEM, allows one to establish a fixed error reduction per adaptive cycle (4) , it seems that in ALSM this can only be shown under very stringent assumptions on a certain new variant of data-visibility (see (46) ). The key is therefore to better understand the interrelation between this data-visibility term and the current residual which can be done with the aid of projections to several auxiliary subspaces of U U U , related to the current local refinement. This allows one to establish a fixed error reduction for a finite number of refinement steps - in brief “block reduction”, provided that the load f f f is sufficiently well aligned with the image under B \mathcal{B} B of certain complement spaces, associated with the refinements. Simply assuming this to hold (like assuming that data-oscillation is of higher order) would give a relatively simple error reduction result (see (46) in Theorem 3.2 ). The deeper insight lies therefore in tying “visibility” of f f f to its piecewise polynomial approximability which is a variant of a regularity property. The resulting linear convergence in terms of a “block reduction” remains the key to a complexity analysis, which, however, requires a somewhat amended reasoning concerning complexity. It is perhaps interesting that then there don’t seem to be any constraints on the bulk parameter θ \theta θ other than being less than one.
Natural future goals are to explore to what extend the above concepts carry over to minimum residual methods when the residual is measured in a non-trivial dual space instead of L 2 L_2 L 2 , or in yet a different direction to nonlinear FOSLS formulations.