betaFeedback

WorksMathematics

Convergence of Adaptive Least Squares Finite Element Methods

Abstract

We consider a general class of operator equations Bu=f\mathcal B u=f where B:U→L2\mathcal B:\mathbb U\to \mathbb L_2 is a linear isomorphis from a Hilbert space U\mathbb U onto an ``L2L_2-type'' space L2=L2(Ω;Rq)\mathbb L_2 = L_2(Ω;\mathbb R^q). This covers weak first order formulations of stationary elliptic boundary value problems, the Stokes system or systems for linear elasticity as well as space-time formulations of heat or wave equations. Since an L2L_2-residual is uniformly equivalent to the corresponding error in the trial space norm reliable and efficient computable a posteriori error bounds are for free. In contrast to a matured theory of classical adaptive finite element methods, estblishing linear convergence - and eventually optimal complexity - in a least squares setting seems to have remained open. To a large extent this is due to the fact that least squares error indicators do not exhibit any explicit dependence on local mesh-sizes. In this paper we propose a rather different approach to establish under which circumstances standard Dörfler-marking mesh refinement gives rise to linear convergence and rate optimality of adaptive least squares finite element methods as well. A central role is played by a new notion of data-visibility which is a structural property of the data rather than a smoothness condition.

Introduction

Least Squares Formulations

Well-posedness of a (formal) linear operator equation

Bu=f(1)Bu=f \tag*{(1)}

is inevitably tied to the specification of a (linear) trial space UU - often a Hilbert space - that is supposed to accommodate a unique solution u∗∈Uu^* \in U, and a test space VV, whose dual V′V' then determines the admissible range for the source ff. Existence of a solution for all f∈V′f \in V', its uniqueness and continuous dependence on the data ff then means that B:U→V′B: U \to V' is a norm-isomorphism. This is well known to be equivalent to the fact that the bilinear form b(u,v):=(Bu)(v)b(u,v):=(Bu)(v), that takes U×VU \times V into R\mathbb{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<cb≤Cb<∞0<c_b\le C_b<\infty such that

cb∥u−u∗∥U≤∥f−Bu∥V′≤Cb∥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)}

Thus, on the one hand, the residual in V′V' is a reliable and efficient error estimator, and on the other hand, the exact solution u∗u^* as well as an approximation to u∗u^* from some subspace UnU_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=H01(Ω)=VU=H^1_0(\Omega)=V and V′=(H01(Ω))′=H−1(Ω)V'=(H^1_0(\Omega))'=H^{-1}(\Omega). This has triggered the development of an art to derive computable equivalent expressions for ∥f−Bu∥H−1(Ω)\lVert f-Bu\rVert_{H^{-1}(\Omega)} 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−Bu∥V′\|f-\mathcal{B}u\|_{\mathbb{V}'}. This issue disappears when V=V′\mathbb{V}=\mathbb{V}' happens to be self-dual, hence some kind of an L2L_2-space (e.g. L2(Ω;Rq)L_2(\Omega;\mathbb{R}^q) for some q∈Nq\in\mathbb{N}). In fact, computing a residual in L2L_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} happens to be an isomorphism whose range is some L2L_2-space.

Specializing (2), the solution u∗u^* of (1) is in this case characterized by

u∗=argmin⁡u∈U ∥f−Bu∥L22.(3)u^*=\underset{u\in\mathbb{U}}{\operatorname{argmin}}\ \|f-\mathcal{B}u\|_{L_2}^2. \tag*{(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 L2L_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)−Bu(x)∣2 dx\eta_K(u):=\int_K|f(x)-\mathcal{B}u(x)|^2\,\mathrm{d}x for free, where KK 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)}

the current error is reduced by a fixed factor ρ<1\rho<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}' of L2L_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 L2L_2-type space - convergence performance cannot be quantified. Data-visibility in the present context can be seen as a structural alignment property of ff. 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 ff 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 ff 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) 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} be a real Hilbert space with norm ∥⋅∥\|\cdot\| and B∈L(U,V)\mathcal{B} \in\mathcal{L}(\mathbb{U},\mathbb{V}) where L(U,V)\mathcal{L}(\mathbb{U},\mathbb{V}) is the space of linear operators from U\mathbb{U} to V\mathbb{V}. The Babuška-Nečas Theorem states that B\mathcal{B} is an isomorphism (boundedly invertible) if and only if the bilinear form b(u,v):=(Bu)(v):U×V→Rb(u,v):=(\mathcal{B}u)(v):\mathbb{U}\times\mathbb{V}\to\mathbb{R} is continuous and satisfies (see e.g. [12, 17])

inf⁡u∈Usup⁡v∈Vb(u,v)∥u∥∥v∥V≥cb,sup⁡u∈Usup⁡v∈Vb(u,v)∥u∥∥v∥V≤Cb,(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)}

for v∈Vv\in\mathbb{V} there exists a wv∈Uw_v\in\mathbb{U} such that b(wv,v)≠0b(w_v,v)\ne0.

This means that

∥B∥L(U,V′)≤Cb,∥B−1∥L(V′,U)≤cb−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)}

which in turn says that for any f∈V′f\in\mathbb{V}', Bu=f\mathcal{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)}

has a unique solution u∗u^* which is stable,

Cb−1∥f∥V′≤∥u∗∥≤cb−1∥f∥V′.(8)C_b^{-1}\|f\|_{\mathbb{V}'}\le\|u^*\|\le c_b^{-1}\|f\|_{\mathbb{V}'}. \tag*{(8)}

Unless (7) arises through an energy minimization, where U=V\mathbb{U}=\mathbb{V} is the natural choice and coercivity implies the inf-sup and surjectivity condition, identifying such stable pairs U,V\mathbb{U},\mathbb{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}.

In fact, in what follows, we focus on this latter scenario when V=L2\mathbb{V}=\mathbb{L}_2 is an L2L_2-type space, generally being of the form L2(Ω;Rq)L_2(\Omega;\mathbb{R}^q) for some q∈Nq\in\mathbb{N} (related to the spatial dimension dd of the computational domain Ω⊂Rd\Omega\subset\mathbb{R}^d) hence is self-dual L2=L2′\mathbb{L}_2=\mathbb{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 (⋅,⋅)Ω:L2×L2→R(\cdot,\cdot)_\Omega:\mathbb{L}_2\times\mathbb{L}_2\to\mathbb{R} the canonical inner product on L2\mathbb{L}_2 but prefer to refer to the domain Ω\Omega, as a subscript, as this will change at times. Accordingly, we write

∥g∥L2=∥g∥Ω=(g,g)Ω1/2,\|g\|_{\mathbb{L}_2}=\|g\|_\Omega=(g,g)_\Omega^{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} be a real Hilbert space of functions defined on a computational domain Ω⊂Rd\Omega\subset\mathbb{R}^d. We assume that U⊂L2\mathbb{U}\subset\mathbb{L}_2 is a continuous embedding. If B\mathcal{B} has closed range the following are equivalent:

(i) B:U→L2\mathcal{B}:\mathbb{U}\to\mathbb{L}_2 is an isomorphism, i.e., (5) holds for V=L2=L2′\mathbb{V}=\mathbb{L}_2=\mathbb{L}_2', i.e., there exists a unique solution u∗∈Uu^*\in\mathbb{U}, satisfying

b(u,v)=(Bu)(v)=(f,v)Ω,v∈L2.(9)b(u,v)=(\mathcal{B}u)(v)=(f,v)_\Omega,\qquad v\in\mathbb{L}_2. \tag*{(9)}

(ii) For any f∈L2f\in\mathbb{L}_2 there exists a unique minimizer

u∗=argmin⁡u∈U∥f−Bu∥Ω2,(10)u^*=\underset{u\in\mathbb{U}}{\operatorname{argmin}}\|f-\mathcal{B}u\|_\Omega^2, \tag*{(10)}

that satisfies the following error-residual relation

cb∥u∗−u∥≤∥f−Bu∥Ω≤Cb∥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)}

for some constants 0<cb≤Cb<∞0<c_b\le C_b<\infty.

(iii) The symmetric problem

B(u,v)=(Bu,Bv)Ω=(f,Bv)Ω,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)}

is elliptic over U\mathbb{U} with coercivity and continuity constants cb2,Cb2c_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.

References

  1. [1]M. Bachmayr, W. Dahmen, M. Oster, Variationally correct neural residual regression for parametric PDEs: On the viability of controlled accuracy, IMA Journal of Numerical Analysis, (2025), doi10.1093/imanum/draf073arxiv.org/abs/2405.20065
  2. [3]P. Binev, W. Dahmen, R. DeVore, Adaptive Finite Element Methods with Convergence Rates, Numer. Math., 97(2004), 219–268.
  3. [4]Z. Cai, R. Lazarov, T. A. Manteuffel, S. F. McCormick, First-Order System Least Squares for Second-Order Partial Differential Equations: Part I, SIAM Journal on Numerical Analysis, 31 (1994), 1785–1799.DOI
  4. [5]W. Dahmen, I. Graham, B. Fährmann, W. Hackbusch, S. Sauter, Inverse Inequalities on Non-Quasiuniform Meshes and Application to the Mortar Element Method, Math. Comp. 73 (2004), 1107–1138.
  5. [6]T. Führer, M. Karkulik, Space-time least-squares finite elements for parabolic equations, Comput. Math. Appl., 92 (2021), 27–36.arxiv.org/abs/1911.01942
  6. [7]T. Führer,R. Gonzales, M. Karkulik, Well-Posedness of First Order Acoustic Wave Equations and Space-Time Finite Element Approximation, arXiv preprint arXiv:2311.10536, 2023arxiv.org/abs/2311.10536
  7. [8]P. Cortés Castillo,W. Dahmen, J. Gopalakrishnan, DPG loss functions for learning parameter-to-solution maps by neural networks, arXiv preprint: http://arxiv.org/abs/2506.18773, 2025
  8. [9]Pavel Bochev, and Max D. Gunzburger, Least-squares finite element methods, Applied Mathematical Sciences, 166, Springer, New York, 2009, ISBN 978-0-387-30888-3, https://doi.org/10.1007/b13382.
  9. [10]A. Bonito, C. Canuto, R. Nochetto, A Veeser, Acta Numerica (2024), 163–485, doi:10.1017/S0962492924000011DOI
  10. [11]D. Braess, V. Pillwein, J. Schöberl, Equilibrated residual error estimates are p-robust, Comput. Methods Appl. Mech. Engrg 198 (2009), 1189–1197.DOI
  11. [12]D. Braess, Finite Elements: Theory, Fast Solvers, and Applications in Solid Mechanics, Cambridge University Press, 2010, ISBN: 9780511618635, doi.org/10.1017/CBO9780511618635
  12. [13]D. Boffi, F. Brezzi, M. Fortin, Mixed Finite Element Methods and Applications, Springer Series in Computational Mathematics, vol. 44, Springer, 2013.DOI
  13. [14]P. Bingmann, Review and computational comparison of adaptive least-squares finite element schemes, Computers & Mathematics with Applications, 122 (2024), 1–15.
  14. [15]C. Carstensen, E.-J. Park. Convergence and optimality of adaptive least squares finite element methods. SIAM J. Numer. Anal., 53 (2015), 43–62.DOI
  15. [16]C. Carstensen, M. Feischl, M. Page, D. Praetorius, Axioms of adaptivity, Comput. Math. Appl., 67 (2014), 1195–1253.pubmed.ncbi.nlm.nih.gov/25983390
  16. [17]L. Demkowicz, J. Gopalakrishnan, The discontinuous Petrov-Galerkin method, Acta Numerica (2025), pp. 293-384, doi:10.1017/S0962492924000102DOI
  17. [18]M. Feischl, Optimality of a standard adaptive finite element method for the Stokes problem, SIAM J. Numer. Anal., 57 (2019), 1124–1157.DOI
  18. [19]G. Gantner, R. Stevenson, Further results on a space-time FOSLS formulation of parabolic PDEs, ESAIM: Mathematical Modelling and Numerical Analysis, 55 (2021), 283–299.DOI
  19. [20]C. Kreuzer, A. Veeser, Oscillation in a posteriori error estimation, Numer. Math. 148 (2021), 43–78.
  20. [21]Y. Qiu, P. Chen, W. Dahmen, Variationally correct operator learning: Reduced basis neural operator with a posteriori error estimation, Computer Methods in Applied Mechanics and Engineering, 461 (2026), 119228, doi: 10.1016/j.cma.2026.119228, Preprint Dec 2025, arXiv:2512.21319, [math.NA], [cs.LG], [cs.NA]DOI
  21. [22]R. Stevenson, Optimality of a standard adaptive finite element method, Found. Comput. Math., 7 (2007), 245–269.DOI
  22. [23]R. Stevenson, The completion of locally refined simplicial partitions created by bisection, Math. Comp., 77 (2008), 227–241.DOI
  23. [24]P. Morin, R. H. Nochetto, K. G. Siebert, Convergence of adaptive finite element methods, SIAM Rev. 44, (2002) 631–658.
  24. [25]R. H. Nochetto, K. G. Siebert, A. Veeser, Theory of adaptive finite element methods: An introduction, in Multiscale, Nonlinear and Adaptive Approximation (R. DeVore and A. Kunoth, eds), Springer, 2009, pp. 409–542.DOI
  25. [26]R. Verfürth, A Review of A Posteriori Error Estimation and Adaptive Mesh-Refinement Techniques, Wiley-Teubner, Chichester, 1996.

Paper details

vlnc:W_nmvydnn5
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents