Quasi-orthogonality is one of the key ingredients for proofs of optimal convergence rates for adaptive mesh refinement methods (Carstensen, Feischl, Page, and Praetorius, arXiv:1312.1171). The work of Feischl (arXiv:2008.12198) proposed a relaxed quasi-orthogonality that follows directly from the inf-sup stability of the underlying problem discretization. The proof uses an intricate connection to the stability of LU-factorization of matrices. Recently, Gantumur (arXiv:2609.16265) presented a vastly simplified argument based solely on Hilbert space arguments. Building on this idea, we show that quasi-orthogonality is a purely geometric property of a set of points. This property is checked for a large class of Petrov-Galerkin methods for monotone, non-linear equations.
Main result
We consider a real Hilbert space U and a finite sequence of elements u1,…,un∈U. For each subset J⊆{1,…,n} and 0≤λj≤1 with ∑j∈Jλj=1 we define the weighted mean
μJ,λ:=j∈J∑λjuj
and the maximal weighted squared distances (variance)
Céa type estimate: There exists CCeˊa>0 such that for all 1≤i≤j≤k≤ℓ≤n, there holds
∥uk−uj∥U≤CCeˊa∥uℓ−ui∥U.(1)
Separation: There exists Csep>0 such that for all J⊆{1,…,n}, all v∈conv{ui∣1≤i≤n,i≤J}, there holds
Csep∥μJ,λ−v∥U2≥EJ,(2)
where (λj)j∈J is the maximizer of EJ.
For such sequences, we can prove the following quasi-orthogonality result.
Theorem 1. There exists C>0 that depends only on the constants CCeˊa, and Csep such that
i=1∑n−1∥ui+1−ui∥U2≤Cn1−δ∥un−u1∥U2,
where δ:=1−log2max{23,(21+16Csep1)−1}>0.
The main idea of the following proof is to look at the variance (mean squared distance from the center) of different subsets of u1,…,un. By using the fact that ui+1,…,un is geometrically separated from u1,…,ui for all 1≤i<n, we will show that combining two disjoint subsets increases the variance by a factor larger than 1/2 over the sum of the individual variances. In Galerkin methods, this separation can often be established by the fact that the residual of the equation w.r.t. uj, j≥i is orthogonal to u1,…,ui (see § 2 for details). Moreover, the variance of subsets of the form {i,i+1} is an upper bound for
The research for this work was heavily AI supported and we provide a LEAN certificate of Theorem 1 under https://github.com/michaelFeischl/quasi-orthogonality-lean. Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – Project-ID 258734477 – SFB 1173, the Austrian Science Fund (FWF) under the special research program Taming complexity in PDE systems (grant SFB F65) as well as projects I6667-N and P36150. This work was also supported by the ERC grant OPTIMAL (grant agreement No. 1011225225). ∥ui+1−ui∥U2. Combining both observations allows us to iteratively combine two disjoint sets into larger ones until we reach the full set. This requires roughly log2(n) iterations. Since the right-hand side bound is the inverse product of the growth factors in each iteration, we obtain the result.
Without loss of generality, we assume that the first sum in the maximum above is the larger one and start with Ij:={2j−1,2j} for all j=1,…,(n−1)/2. Using (6), we may iteratively combine consecutive Ij and Ij+1 to obtain
j=1∑(n−1)/2EIj≤qlog2(n)E{1,…,n}.
Clearly, we have E{1,…,n}≲∥un−u1∥U2 and also EIj≥41∥u2j−u2j−1∥U2. This and qlog2(n)=nlog2(q) conclude the proof. □
Application to non-linear Petrov Galerkin Methods
We show that the assumptions (1) and (2) are relatively straightforward for a large class of nonlinear Petrov-Galerkin methods. Let U,V be real Hilbert spaces. We denote the duality pairing between V⋆ and V by ⟨⋅,⋅⟩, and equip each subspace occurring in the discussion with the norm inherited from its ambient space. Suppose that A:U→V⋆ satisfies
∥Ax−Ay∥V⋆≤L∥x−y∥U,x,y∈U,(7)
for some L>0. Let (Uj)j≥0 and (Vj)j≥0 be nested sequences of finite-dimensional linear subspaces of U and V, respectively. Nestedness means that for all j≥0, we have Uj⊆Uj+1 and Vj⊆Vj+1. Suppose that there is a surjective map T:U→V such that
T∣Uj:Uj→Vj
is surjective for all j≥0 and constants M,α>0, independent of j, such that
∥Tx−Ty∥V≤M∥x−y∥U,(8)
⟨Ax−Ay,Tx−Ty⟩≥α∥x−y∥U2,x,y∈Uj.(9)
We consider the solutions uj∈Uj to
⟨Auj,v⟩=⟨f,v⟩for all v∈Vj.(10)
The well-posedness follows standard arguments and is included for completeness only.
Lemma 2 (Discrete well-posedness). For every f∈V⋆, the equations (10) have a unique solution.
This proves that Tj:=T∣Uj is injective. By its assumed surjectivity it is a bijection, and its inverse is (L/α)-Lipschitz. If Vj={0}, bijectivity implies Uj={0} and the assertion is immediate. Otherwise, define Bj:Vj→Vj⋆ by
⟨Bjz,v⟩:=⟨A(Tj−1z),v⟩,z,v∈Vj.
Writing x=Tj−1z and y=Tj−1ζ, we obtain
∥Bjz−Bjζ∥Vj⋆≤∥Ax−Ay∥V⋆≤αL2∥z−ζ∥V,
⟨Bjz−Bjζ,z−ζ⟩≥α∥x−y∥U2≥M2α∥z−ζ∥V2.
Set Λ=L2/α and β=α/M2. These inequalities imply 0<β≤Λ. Let Rj:Vj→Vj⋆ be the Riesz isometry, and put fj=f∣Vj. The map
The space Vj is complete, so the contraction principle gives a unique fixed point z, equivalently a unique solution of Bjz=fj. Then uj=Tj−1z is the unique solution. □
We show the assumptions (1) and (2) for the sequence {Tu1,…,Tun}⊆V.
Céa type estimate: We obtain for all $0\le i\le j\le k\le\ell\le n
where the second inequality follows by (11) and hence separation (2) with Csep:=4L4M4/α4. Thus Theorem 1 applies to this sequence and by the bi-Lipschitz property of T also yields the result for the sequence {u1,…,un}⊆U.
Application to nonlinear ODEs
In the following we introduce continuous Petrov–Galerkin time stepping for ordinary differential equations. This example showcases, in which applications the abstract Theorem 1 is particularly useful.
For a bounded interval [t0,tend]⊂R, we consider the initial value problem
y′(t)=F(t,y(t))for every t∈[t0,tend],
y(t0)=x0.
The right-hand side F:[t0,tend]×Rd→Rd is supposed to be continuous in its first argument and Lipschitz continuous in its second, i.e. for some LF>0,
Let (Ij)j≥0 be a sequence of partitions of [t0,tend] into finitely many intervals, where each partition Ij+1 is obtained from Ij by subdividing some of its intervals. Such sequences are generated, e.g., by adaptive step-size algorithms. We denote the nodes of the initial partition I0 by t0=t00<t10<⋯<tm0=tend and its maximal step size by
τ0:=1≤n≤mmax(tn0−tn−10).
We require the initial partition to be fine enough in the sense that
whose norms are specified below. For a fixed polynomial degree p∈N, the trial and test spaces are
Uj:={w∈U:w∣I∈Pp(I;Rd) for every I∈Ij},
Vj:={v∈V:v∣I∈Pp−1(I;Rd) for every I∈Ij}.
Hence, the trial functions are continuous piecewise polynomials of degree p, whereas the test functions are piecewise polynomials of degree p−1 which are allowed to jump at the nodes. Both sequences of spaces are nested and finite dimensional. The continuous Petrov–Galerkin method seeks an approximation yj of y such that
yj−x0∈Uj,∫t0tend(yj′(t)−F(t,yj(t)))⋅vj(t)dt=0for every vj∈Vj.(14)
Application of the abstract result
In order to apply Theorem 1, we have to choose the operator A, the norms on U and V, and the map T. We incorporate the initial value in the right-hand side and define A:U→V⋆ by
The assumptions on F imply that t↦F(t,x0+u(t)) is continuous and bounded for every u∈U, so A is well defined. By the Picard–Lindelöf theorem, the initial value problem has a unique solution y∈C1([t0,tend;Rd). Thus, u:=y−x0∈U satisfies Au=0, and uj:=yj−x0∈Uj solves the Petrov–Galerkin equations (10) with f=0 if and only if yj solves (14).
The obvious choice of the remaining ingredients is to equip U with ∥w′∥L2(t0,tend), to equip V with the L2-norm, and to set Tw:=w′. This satisfies T(Uj)=Vj. However, for x,z∈U and w:=x−z, the Lipschitz bound (12) and the Poincaré inequality only show
This yields the strong monotonicity (9) only for short time intervals with LF(tend−t0)<2. To avoid this restriction, we use exponentially decaying weights, first introduced by [1], as is common for Gronwall-type arguments.
Since e−8LF(tend−t0)≤ω≤1, these norms are equivalent to the standard norms and U, V are Hilbert spaces. Moreover, for r∈L2(t0,tend;Rd), the functional v↦∫t0tendr⋅vdt satisfies
∥r∥V⋆2=∫t0tendω(t)∣r(t)∣2dt.(18)
The gain of the weighted norms is a Poincaré inequality whose constant does not depend on the length of the time interval. To see this, let ρ(t):=e−8LF(t−t0). For w∈U, integration by parts and w(t0)=0 give
On every interval of I0, there holds ρ≤ω≤e8LFτ0ρ. Together with e4LFτ0≤2, which is the step-size restriction (13), we obtain
(∫t0tendω∣w∣2dt)1/2≤4LFe4LFτ0(∫t0tendω∣w′∣2dt)1/2≤2LF1∥w∥Ufor every w∈U.(19)
We now verify the operator assumptions of Section 2. Let x,z∈U and w:=x−z. The identity (18), the Lipschitz bound (12), and the weighted Poincaré inequality (19) show
which is the Lipschitz continuity (7) with L=3/2. We choose
T:U→V,Tw:=ωw′.
The definition of the norms (17) immediately gives ∥Tx−Tz∥V=∥x−z∥U, which is (8) with M=1. Furthermore, every partition Ij is a refinement of I0, so ω is constant on each interval of Ij. Therefore, ωw′∈Vj for all w∈Uj, and every v∈Vj is the image of w(t):=∫t0tω−1vds∈Uj. This shows surjectivity
which is the strong monotonicity (9) with α=1/2. Altogether, the assumptions (7)–(9) are satisfied with
L=23,M=1,α=21.
Lemma 2 with f=0 gives a unique solution uj∈Uj of (10) on each level, so yj=x0+uj is the unique solution of (14). Fix ℓ∈N0 and n∈N. By Section 2, the sequence Tuℓ,…,Tuℓ+n satisfies (1) and (2). Since T is an isometry, ∥Tuj−Tuk∥V=∥uj−uk∥U=∥yj−yk∥U for all j,k. Applying Theorem 1 to these n+1 points we obtain
The implied constant and δ as well as the step-size restriction (13) are independent of the polynomial degree p, the dimension d, and the partitions Ij.
Comparison with existing results
A quasi-orthogonality estimate for the method (14) was previously shown in [4]. That work considers an adaptive algorithm which is steered by a residual error estimator ηj and bisects the time steps selected by Dörfler marking. As a key ingredient in their analysis, [4], Lemma 12 proves the following: Suppose that, in addition to (12), the right-hand side F is continuously differentiable with Lipschitz continuous Jacobian, and that the initial partition I0 is sufficiently fine. Then, there exist ε>0, 1>δ>0, and C(n)=O(n1−δ) such that
j=ℓ∑ℓ+n−1(∥yj+1−yj∥H1(t0,tend)2−εηj2)≤C(n)∥y−yℓ∥H1(t0,tend)2for all ℓ,n∈N.
The proof linearizes the initial value problem around the exact solution y and shows that the continuous Petrov–Galerkin discretization of the linearized problem is uniformly inf-sup stable on sufficiently fine partitions. Thus, the linear result of [3] applies to the linearized problem. The difference between the discrete solutions of the nonlinear and the linearized problem is quadratic in the error ∥y−yj∥H1(t0,tend) and is absorbed by the term εηj2.
The estimate (20) differs from this result in the following ways. First, we apply Theorem 1 directly to the nonlinear operator (15). No linearization is necessary, and the Lipschitz continuity (12) is the only assumption on F, whereas the Taylor expansion in [4] requires the differentiability of F. Second, (20) does not contain an error estimator and holds for arbitrary nested refinements of an initial partition satisfying (13). In particular, it implies the estimate of [4 Lemma 12] with ε=0. Third, the step-size restriction (13) is explicit and depends only on the Lipschitz constant LF.
References
References
[1]Adam Bielecki. “Une remarque sur la méthode de Banach-Cacciopoli-Tikhonov dans la théorie des équations différentielles ordinaires”. In: Bull. Acad. Polon. Sci 4.5 (1956), pp. 261–264.
[4]Michael Feischl and David Niederkofler. “Chapter Nine - Optimal adaptive implicit time stepping”. In: Error Control, Adaptive Discretizations, and Applications, Part 4. Ed. by Franz Chouly et al. Vol. 61. Advances in Applied Mechanics. Elsevier, 2025, pp. 407–448. DOI: 10.1016/bs.aams.2025.09.001. URL: https://www.sciencedirect.com/science/article/pii/S0065215625000250.DOI