betaFeedback

WorksMathematics

Quasi-orthogonality is a geometric property

Abstract

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 LULU-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 UU and a finite sequence of elements u1,…,un∈Uu_1,\ldots,u_n \in U. For each subset J⊆{1,…,n}J \subseteq\{1,\ldots,n\} and 0≤λj≤10 \leq\lambda_j \leq1 with ∑j∈Jλj=1\sum_{j\in J}\lambda_j=1 we define the weighted mean

μJ,λ:=∑j∈Jλjuj\mu_{J,\lambda}:=\sum_{j\in J}\lambda_j u_j

and the maximal weighted squared distances (variance)

EJ:=max⁡0≤λi≤1∑j∈Jλj=1∑j∈Jλj∥uj−μJ,λ∥U2.E_J:=\max_{\substack{0\leq\lambda_i\leq1\\ \sum_{j\in J}\lambda_j=1}}\sum_{j\in J}\lambda_j\lVert u_j-\mu_{J,\lambda}\rVert_U^2.

We make the following two assumptions:

  • Céa type estimate: There exists CCeˊa>0C_{\mathrm{Céa}}>0 such that for all 1≤i≤j≤k≤ℓ≤n1\leq i\leq j\leq k\leq\ell\leq n, there holds

∥uk−uj∥U≤CCeˊa∥uℓ−ui∥U.(1)\lVert u_k-u_j\rVert_U\leq C_{\mathrm{Céa}}\lVert u_\ell-u_i\rVert_U. \tag*{(1)}
  • Separation: There exists Csep>0C_{\mathrm{sep}}>0 such that for all J⊆{1,…,n}J\subseteq\{1,\ldots,n\}, all v∈conv⁡{ui∣1≤i≤n, i≤J}v\in\operatorname{conv}\{u_i\mid1\leq i\leq n,\ i\leq J\}, there holds

Csep∥μJ,λ−v∥U2≥EJ,(2)C_{\mathrm{sep}}\lVert\mu_{J,\lambda}-v\rVert_U^2\geq E_J, \tag*{(2)}

where (λj)j∈J(\lambda_j)_{j\in J} is the maximizer of EJE_J.

For such sequences, we can prove the following quasi-orthogonality result.

Theorem 1. There exists C>0C>0 that depends only on the constants CCeˊaC_{\mathrm{Céa}}, and CsepC_{\mathrm{sep}} such that

∑i=1n−1∥ui+1−ui∥U2≤Cn1−δ∥un−u1∥U2,\sum_{i=1}^{n-1}\lVert u_{i+1}-u_i\rVert_U^2\leq Cn^{1-\delta}\lVert u_n-u_1\rVert_U^2,

where δ:=1−log⁡2max⁡{32,(12+116Csep)−1}>0\delta:=1-\log_2\max\left\{\frac{3}{2},\left(\frac{1}{2}+\frac{1}{16C_{\mathrm{sep}}}\right)^{-1}\right\}>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,…,unu_1,\ldots,u_n. By using the fact that ui+1,…,unu_{i+1},\ldots,u_n is geometrically separated from u1,…,uiu_1,\ldots,u_i for all 1≤i<n1\leq i<n, we will show that combining two disjoint subsets increases the variance by a factor larger than 1/21/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. uju_j, j≥ij\geq i is orthogonal to u1,…,uiu_1,\ldots,u_i (see § 2 for details). Moreover, the variance of subsets of the form {i,i+1}\{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\lVert u_{i+1}-u_i\rVert_U^2. Combining both observations allows us to iteratively combine two disjoint sets into larger ones until we reach the full set. This requires roughly log⁡2(n)\log_2(n) iterations. Since the right-hand side bound is the inverse product of the growth factors in each iteration, we obtain the result.

Proof of Theorem 1. Step 1: There holds

EI=max⁡0≤λi≤1∑i∈Iλi=1(∑i∈Iλi∥ui∥U2−2∑i∈Iλi⟨ui,μI,λ⟩U+∥μI,λ∥U2)=max⁡0≤λi≤1∑i∈Iλi=1(∑i∈Iλi∥ui∥U2−∥μI,λ∥U2).(3)E_I=\max_{\substack{0\leq\lambda_i\leq1\\ \sum_{i\in I}\lambda_i=1}}\left(\sum_{i\in I}\lambda_i\lVert u_i\rVert_U^2-2\sum_{i\in I}\lambda_i\langle u_i,\mu_{I,\lambda}\rangle_U+\lVert\mu_{I,\lambda}\rVert_U^2\right)=\max_{\substack{0\leq\lambda_i\leq1\\ \sum_{i\in I}\lambda_i=1}}\left(\sum_{i\in I}\lambda_i\lVert u_i\rVert_U^2-\lVert\mu_{I,\lambda}\rVert_U^2\right). \tag*{(3)}

Given I,J⊂{1,…,n}I,J\subset\{1,\ldots,n\} with I∩J=∅I\cap J=\varnothing and i<ji<j for all i∈Ii\in I and j∈Jj\in J, with corresponding maximizers λI\lambda_I and λJ\lambda_J, there holds

EI∪J≥12(∑i∈IλI,i∥ui∥U2+∑i∈JλJ,i∥ui∥U2)−14∥∑i∈IλI,iui+∑i∈JλJ,iui∥U2≥12(EI+EJ)+14∥∑i∈IλI,iui∥U2+14∥∑i∈JλJ,iui∥U2−12⟨∑i∈IλI,iui,∑i∈JλJ,iui⟩U=12(EI+EJ)+14∥μI,λI−μJ,λJ∥U2.(4)\begin{aligned} E_{I\cup J}&\geq\frac{1}{2}\left(\sum_{i\in I}\lambda_{I,i}\lVert u_i\rVert_U^2+\sum_{i\in J}\lambda_{J,i}\lVert u_i\rVert_U^2\right)-\frac{1}{4}\left\lVert\sum_{i\in I}\lambda_{I,i}u_i+\sum_{i\in J}\lambda_{J,i}u_i\right\rVert_U^2\\ &\geq\frac{1}{2}(E_I+E_J)+\frac{1}{4}\left\lVert\sum_{i\in I}\lambda_{I,i}u_i\right\rVert_U^2+\frac{1}{4}\left\lVert\sum_{i\in J}\lambda_{J,i}u_i\right\rVert_U^2-\frac{1}{2}\left\langle\sum_{i\in I}\lambda_{I,i}u_i,\sum_{i\in J}\lambda_{J,i}u_i\right\rangle_U\\ &=\frac{1}{2}(E_I+E_J)+\frac{1}{4}\lVert\mu_{I,\lambda_I}-\mu_{J,\lambda_J}\rVert_U^2. \tag*{(4)} \end{aligned}

Step 2: Separation (2) together with (4) shows for c=1/(4Csep)c=1/(4C_{\mathrm{sep}})

EI∪J≥12(EI+EJ)+cEJ.(5)E_{I\cup J}\geq\frac{1}{2}(E_I+E_J)+cE_J. \tag*{(5)}

If EJ≥12EIE_J\geq\frac{1}{2}E_I, the above inequality (5) shows

EI∪J≥(12+c4)(EI+EJ).E_{I\cup J}\geq\left(\frac{1}{2}+\frac{c}{4}\right)(E_I+E_J).

If EJ<12EIE_J<\frac{1}{2}E_I, we use EI≤EI∪JE_I\leq E_{I\cup J} to also get (EI+EJ)≤32EI≤32EI∪J(E_I+E_J)\leq\frac{3}{2}E_I\leq\frac{3}{2}E_{I\cup J}. Thus, in both cases we have

EI+EJ≤qEI∪J(6)E_I+E_J\leq qE_{I\cup J} \tag*{(6)}

for q:=max⁡{3/2,(1/2+c/4)−1}<2q:=\max\{3/2,(1/2+c/4)^{-1}\}<2.

Step 3: There holds for k=⌊log⁡2(n−1)⌋k=\lfloor\log_2(n-1)\rfloor that

max⁡{∑i=12k∥ui+1−ui∥U2,∑i=n−2kn−1∥ui+1−ui∥U2}≥12∑i=1n−1∥ui+1−ui∥U2.\max\left\{\sum_{i=1}^{2^k}\lVert u_{i+1}-u_i\rVert_U^2,\sum_{i=n-2^k}^{n-1}\lVert u_{i+1}-u_i\rVert_U^2\right\}\geq\frac{1}{2}\sum_{i=1}^{n-1}\lVert u_{i+1}-u_i\rVert_U^2.

Thus, without loss of generality, we may assume n−1=2kn-1=2^k. Moreover, there holds

max⁡{∑j=1(n−1)/2∥u2j−u2j−1∥U2,∑j=1(n−1)/2∥u2j+1−u2j∥U2}≥12∑i=1n−1∥ui+1−ui∥U2.\max\left\{\sum_{j=1}^{(n-1)/2}\lVert u_{2j}-u_{2j-1}\rVert_U^2,\sum_{j=1}^{(n-1)/2}\lVert u_{2j+1}-u_{2j}\rVert_U^2\right\}\geq\frac{1}{2}\sum_{i=1}^{n-1}\lVert u_{i+1}-u_i\rVert_U^2.

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}I_j:=\{2j-1,2j\} for all j=1,…,(n−1)/2j=1,\ldots,(n-1)/2. Using (6), we may iteratively combine consecutive IjI_j and Ij+1I_{j+1} to obtain

∑j=1(n−1)/2EIj≤qlog⁡2(n)E{1,…,n}.\sum_{j=1}^{(n-1)/2}E_{I_j}\leq q^{\log_2(n)}E_{\{1,\ldots,n\}}.

Clearly, we have E{1,…,n}≲∥un−u1∥U2E_{\{1,\ldots,n\}}\lesssim\lVert u_n-u_1\rVert_U^2 and also EIj≥14∥u2j−u2j−1∥U2E_{I_j}\geq\frac{1}{4}\lVert u_{2j}-u_{2j-1}\rVert_U^2. This and qlog⁡2(n)=nlog⁡2(q)q^{\log_2(n)}=n^{\log_2(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,VU,V be real Hilbert spaces. We denote the duality pairing between V⋆V^\star and VV by ⟨⋅,⋅⟩\langle\cdot,\cdot\rangle, and equip each subspace occurring in the discussion with the norm inherited from its ambient space. Suppose that A:U→V⋆A:U\to V^\star satisfies

∥Ax−Ay∥V⋆≤L∥x−y∥U,x,y∈U,(7)\|Ax-Ay\|_{V^\star}\le L\|x-y\|_U,\qquad x,y\in U, \tag*{(7)}

for some L>0L>0. Let (Uj)j≥0(U_j)_{j\geq0} and (Vj)j≥0(V_j)_{j\geq0} be nested sequences of finite-dimensional linear subspaces of UU and VV, respectively. Nestedness means that for all j≥0j\geq0, we have Uj⊆Uj+1U_j\subseteq U_{j+1} and Vj⊆Vj+1V_j\subseteq V_{j+1}. Suppose that there is a surjective map T:U→VT:U\to V such that

T∣Uj:Uj→VjT|_{U_j}:U_j\to V_j

is surjective for all j≥0j\geq0 and constants M,α>0M,\alpha>0, independent of jj, such that

∥Tx−Ty∥V≤M∥x−y∥U,(8)\|Tx-Ty\|_V\le M\|x-y\|_U, \tag*{(8)}
⟨Ax−Ay,Tx−Ty⟩≥α∥x−y∥U2,x,y∈Uj.(9)\langle Ax-Ay,Tx-Ty\rangle\ge\alpha\|x-y\|_U^2,\qquad x,y\in U_j. \tag*{(9)}

We consider the solutions uj∈Uju_j\in U_j to

⟨Auj,v⟩=⟨f,v⟩for all v∈Vj.(10)\langle Au_j,v\rangle=\langle f,v\rangle\qquad\text{for all }v\in V_j. \tag*{(10)}

The well-posedness follows standard arguments and is included for completeness only.

Lemma 2 (Discrete well-posedness). For every f∈V⋆f\in V^\star, the equations (10) have a unique solution.

Proof. For x,y∈Ujx,y\in U_j, the assumptions give

α∥x−y∥U2≤∥Ax−Ay∥V⋆∥Tx−Ty∥V≤L∥x−y∥U∥Tx−Ty∥V.(11)\alpha\|x-y\|_U^2\le\|Ax-Ay\|_{V^\star}\|Tx-Ty\|_V\le L\|x-y\|_U\|Tx-Ty\|_V. \tag*{(11)}

This proves that Tj:=T∣UjT_j:=T|_{U_j} is injective. By its assumed surjectivity it is a bijection, and its inverse is (L/α)(L/\alpha)-Lipschitz. If Vj={0}V_j=\{0\}, bijectivity implies Uj={0}U_j=\{0\} and the assertion is immediate. Otherwise, define Bj:Vj→Vj⋆B_j:V_j\to V_j^\star by

⟨Bjz,v⟩:=⟨A(Tj−1z),v⟩,z,v∈Vj.\langle B_jz,v\rangle:=\langle A(T_j^{-1}z),v\rangle,\qquad z,v\in V_j.

Writing x=Tj−1zx=T_j^{-1}z and y=Tj−1ζy=T_j^{-1}\zeta, we obtain

∥Bjz−Bjζ∥Vj⋆≤∥Ax−Ay∥V⋆≤L2α∥z−ζ∥V,\|B_jz-B_j\zeta\|_{V_j^\star}\le\|Ax-Ay\|_{V^\star}\le\frac{L^2}{\alpha}\|z-\zeta\|_V,
⟨Bjz−Bjζ,z−ζ⟩≥α∥x−y∥U2≥αM2∥z−ζ∥V2.\langle B_jz-B_j\zeta,z-\zeta\rangle\ge\alpha\|x-y\|_U^2\ge\frac{\alpha}{M^2}\|z-\zeta\|_V^2.

Set Λ=L2/α\Lambda=L^2/\alpha and β=α/M2\beta=\alpha/M^2. These inequalities imply 0<β≤Λ0<\beta\le\Lambda. Let Rj:Vj→Vj⋆R_j:V_j\to V_j^\star be the Riesz isometry, and put fj=f∣Vjf_j=f|_{V_j}. The map

Fj(z):=z−βΛ2Rj−1(Bjz−fj),z∈VjF_j(z):=z-\frac{\beta}{\Lambda^2}R_j^{-1}(B_jz-f_j),\qquad z\in V_j

satisfies

∥Fj(z)−Fj(ζ)∥V2=∥z−ζ∥V2−2βΛ2⟨Bjz−Bjζ,z−ζ⟩+β2Λ4∥Bjz−Bjζ∥Vj⋆2\|F_j(z)-F_j(\zeta)\|_V^2=\|z-\zeta\|_V^2-\frac{2\beta}{\Lambda^2}\langle B_jz-B_j\zeta,z-\zeta\rangle+\frac{\beta^2}{\Lambda^4}\|B_jz-B_j\zeta\|_{V_j^\star}^2
≤(1−β2Λ2)∥z−ζ∥V2.\le\left(1-\frac{\beta^2}{\Lambda^2}\right)\|z-\zeta\|_V^2.

The space VjV_j is complete, so the contraction principle gives a unique fixed point zz, equivalently a unique solution of Bjz=fjB_jz=f_j. Then uj=Tj−1zu_j=T_j^{-1}z is the unique solution. □

We show the assumptions (1) and (2) for the sequence {Tu1,…,Tun}⊆V\{Tu_1,\ldots,Tu_n\}\subseteq V.

Céa type estimate: We obtain for all $0\le i\le j\le k\le\ell\le n

α∥uk−uj∥U2≤⟨Auk−Auj,Tuk−Tuj⟩=⟨Auk−Auj,Tuk−Tui⟩≤LM∥uk−uj∥U∥uk−ui∥U\alpha\|u_k-u_j\|_U^2\le\langle Au_k-Au_j,Tu_k-Tu_j\rangle=\langle Au_k-Au_j,Tu_k-Tu_i\rangle\le LM\|u_k-u_j\|_U\|u_k-u_i\|_U

and

α∥uk−ui∥U2≤⟨Auk−Aui,Tuk−Tui⟩=⟨Auℓ−Aui,Tuk−Tui⟩≤LM∥uℓ−ui∥U∥uk−ui∥U.\alpha\|u_k-u_i\|_U^2\le\langle Au_k-Au_i,Tu_k-Tu_i\rangle=\langle Au_\ell-Au_i,Tu_k-Tu_i\rangle\le LM\|u_\ell-u_i\|_U\|u_k-u_i\|_U.

Both estimates can be combined with the bi-Lipschitz property of TT to show (1) with CCeˊa=(LM/α)3C_{\mathrm{Céa}}=(LM/\alpha)^3.

Separation: To see (2), consider v∈conv⁡{Tui∣1≤i≤n, i≤J}v \in\operatorname{conv}\{Tu_i \mid1 \le i \le n,\, i \le J\} and

⟨Aumax⁡J−Aumin⁡J,μJ,λ−v⟩=⟨Aumax⁡J−Aumin⁡J,μJ,λ−Tumin⁡J⟩=∑j∈Jλj⟨Auj−Aumin⁡J,Tuj−Tumin⁡J⟩≥αM2∑j∈Jλj∥Tuj−Tumin⁡J∥V2≥αM2EJ,\begin{aligned} \langle Au_{\max J} - Au_{\min J},\mu_{J,\lambda}-v\rangle= \langle Au_{\max J} - Au_{\min J},\mu_{J,\lambda}-Tu_{\min J}\rangle\\ &= \sum_{j\in J}\lambda_j\langle Au_j-Au_{\min J},Tu_j-Tu_{\min J}\rangle\\ &\ge\frac{\alpha}{M^2}\sum_{j\in J}\lambda_j\lVert Tu_j-Tu_{\min J}\rVert_V^2 \ge\frac{\alpha}{M^2}E_J, \end{aligned}

where the last inequality follows since the mean minimizes the squared distances. Cauchy–Schwarz yields

L∥umax⁡J−umin⁡J∥U∥μJ,λ−v∥V≥∥Aumax⁡J−Aumin⁡J∥V⋆∥μJ,λ−v∥V≥αM2EJ.L\lVert u_{\max J}-u_{\min J}\rVert_U\lVert\mu_{J,\lambda}-v\rVert_V \ge\lVert Au_{\max J}-Au_{\min J}\rVert_{V^\star}\lVert\mu_{J,\lambda}-v\rVert_V \ge\frac{\alpha}{M^2}E_J.

Moreover, we have for i=min⁡Ji=\min J and j=max⁡Jj=\max J that

EJ≥12(∥Tui−(Tui+Tuj)/2∥V2+∥Tuj−(Tui+Tuj)/2∥V2)≥α24L2∥umax⁡J−umin⁡J∥U2,E_J\ge\frac{1}{2}\left(\lVert Tu_i-(Tu_i+Tu_j)/2\rVert_V^2+\lVert Tu_j-(Tu_i+Tu_j)/2\rVert_V^2\right)\ge\frac{\alpha^2}{4L^2}\lVert u_{\max J}-u_{\min J}\rVert_U^2,

where the second inequality follows by (11) and hence separation (2) with Csep:=4L4M4/α4C_{\mathrm{sep}}:=4L^4M^4/\alpha^4. Thus Theorem 1 applies to this sequence and by the bi-Lipschitz property of TT also yields the result for the sequence {u1,…,un}⊆U\{u_1,\ldots,u_n\}\subseteq 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[t_0,t_{\mathrm{end}}]\subset\mathbb{R}, we consider the initial value problem

y′(t)=F(t,y(t))for every t∈[t0,tend],y'(t)=F(t,y(t))\quad\text{for every }t\in[t_0,t_{\mathrm{end}}],
y(t0)=x0.y(t_0)=x_0.

The right-hand side F:[t0,tend]×Rd→RdF:[t_0,t_{\mathrm{end}}]\times\mathbb{R}^d\to\mathbb{R}^d is supposed to be continuous in its first argument and Lipschitz continuous in its second, i.e. for some LF>0L_F>0,

∣F(t,a)−F(t,b)∣≤LF∣a−b∣,a,b∈Rd,t∈[t0,tend].(12)\lvert F(t,a)-F(t,b)\rvert\le L_F\lvert a-b\rvert,\qquad a,b\in\mathbb{R}^d,\quad t\in[t_0,t_{\mathrm{end}}]. \tag*{(12)}

Continuous Petrov–Galerkin time stepping

Let (Ij)j≥0(\mathcal{I}_j)_{j\ge0} be a sequence of partitions of [t0,tend][t_0,t_{\mathrm{end}}] into finitely many intervals, where each partition Ij+1\mathcal{I}_{j+1} is obtained from Ij\mathcal{I}_j 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\mathcal{I}_0 by t0=t00<t10<⋯<tm0=tendt_0=t_0^0<t_1^0<\cdots<t_m^0=t_{\mathrm{end}} and its maximal step size by

τ0:=max⁡1≤n≤m(tn0−tn−10).\tau_0:=\max_{1\le n\le m}(t_n^0-t_{n-1}^0).

We require the initial partition to be fine enough in the sense that

LFτ0≤log⁡24.(13)L_F\tau_0\le\frac{\log2}{4}. \tag*{(13)}

We work with the spaces

U:={w∈H1(t0,tend;Rd):w(t0)=0},V:=L2(t0,tend;Rd),U:=\{w\in H^1(t_0,t_{\mathrm{end}};\mathbb{R}^d):w(t_0)=0\},\qquad V:=L^2(t_0,t_{\mathrm{end}};\mathbb{R}^d),

whose norms are specified below. For a fixed polynomial degree p∈Np\in\mathbb{N}, the trial and test spaces are

Uj:={w∈U:w∣I∈Pp(I;Rd) for every I∈Ij},U_j:=\{w\in U:w|_I\in\mathcal{P}^p(I;\mathbb{R}^d)\text{ for every }I\in\mathcal{I}_j\},
Vj:={v∈V:v∣I∈Pp−1(I;Rd) for every I∈Ij}.V_j:=\{v\in V:v|_I\in\mathcal{P}^{p-1}(I;\mathbb{R}^d)\text{ for every }I\in\mathcal{I}_j\}.

Hence, the trial functions are continuous piecewise polynomials of degree pp, whereas the test functions are piecewise polynomials of degree p−1p-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 yjy_j of yy such that

yj−x0∈Uj,∫t0tend(yj′(t)−F(t,yj(t)))⋅vj(t) dt=0for every vj∈Vj.(14)y_j-x_0\in U_j,\qquad\int_{t_0}^{t_{\mathrm{end}}}(y_j'(t)-F(t,y_j(t)))\cdot v_j(t)\,\mathrm{d}t=0\quad\text{for every }v_j\in V_j. \tag*{(14)}

Application of the abstract result

In order to apply Theorem 1, we have to choose the operator AA, the norms on UU and VV, and the map TT. We incorporate the initial value in the right-hand side and define A:U→V⋆A: U \to V^\star by

⟨Au,v⟩:=∫t0tend(u′(t)−F(t,x0+u(t)))⋅v(t) dt.(15)\langle Au,v\rangle:= \int_{t_0}^{t_{\mathrm{end}}} \left(u'(t)-F(t,x_0+u(t))\right)\cdot v(t)\,\mathrm{d}t. \tag*{(15)}

The assumptions on FF imply that t↦F(t,x0+u(t))t\mapsto F(t,x_0+u(t)) is continuous and bounded for every u∈Uu\in U, so AA is well defined. By the Picard–Lindelöf theorem, the initial value problem has a unique solution y∈C1([t0,tend;Rd)y\in C^1([t_0,t_{\mathrm{end}};\mathbb{R}^d). Thus, u:=y−x0∈Uu:=y-x_0\in U satisfies Au=0Au=0, and uj:=yj−x0∈Uju_j:=y_j-x_0\in U_j solves the Petrov–Galerkin equations (10) with f=0f=0 if and only if yjy_j solves (14).

The obvious choice of the remaining ingredients is to equip UU with ∥w′∥L2(t0,tend)\lVert w'\rVert_{L^2(t_0,t_{\mathrm{end}})}, to equip VV with the L2L^2-norm, and to set Tw:=w′Tw:=w'. This satisfies T(Uj)=VjT(U_j)=V_j. However, for x,z∈Ux,z\in U and w:=x−zw:=x-z, the Lipschitz bound (12) and the Poincaré inequality only show

⟨Ax−Az,w′⟩≥∥w′∥L2(t0,tend)2−LF∥w∥L2(t0,tend)∥w′∥L2(t0,tend)≥(1−LF(tend−t0)2)∥w′∥L2(t0,tend)2.\langle Ax-Az,w'\rangle\geq\lVert w'\rVert_{L^2(t_0,t_{\mathrm{end}})}^2-L_F\lVert w\rVert_{L^2(t_0,t_{\mathrm{end}})}\lVert w'\rVert_{L^2(t_0,t_{\mathrm{end}})}\geq\left(1-\frac{L_F(t_{\mathrm{end}}-t_0)}{\sqrt{2}}\right)\lVert w'\rVert_{L^2(t_0,t_{\mathrm{end}})}^2.

This yields the strong monotonicity (9) only for short time intervals with LF(tend−t0)<2L_F(t_{\mathrm{end}}-t_0)<\sqrt{2}. To avoid this restriction, we use exponentially decaying weights, first introduced by [1], as is common for Gronwall-type arguments.

We define the piecewise constant weight

ω(t):=e−8LF(tn−10−t0)for tn−10<t<tn0,n=1,…,m.(16)\omega(t):=e^{-8L_F(t_{n-1}^0-t_0)}\qquad\text{for }t_{n-1}^0<t<t_n^0,\quad n=1,\ldots,m. \tag*{(16)}

The weight is fixed on the initial partition I0\mathcal{I}_0 and does not depend on the level jj. We equip UU and VV with the norms

∥w∥U2:=∫t0tendω(t)∣w′(t)∣2 dt,∥v∥V2:=∫t0tendω(t)−1∣v(t)∣2 dt.(17)\lVert w\rVert_U^2:=\int_{t_0}^{t_{\mathrm{end}}}\omega(t)|w'(t)|^2\,\mathrm{d}t,\qquad\lVert v\rVert_V^2:=\int_{t_0}^{t_{\mathrm{end}}}\omega(t)^{-1}|v(t)|^2\,\mathrm{d}t. \tag*{(17)}

Since e−8LF(tend−t0)≤ω≤1e^{-8L_F(t_{\mathrm{end}}-t_0)}\leq\omega\leq1, these norms are equivalent to the standard norms and UU, VV are Hilbert spaces. Moreover, for r∈L2(t0,tend;Rd)r\in L^2(t_0,t_{\mathrm{end}};\mathbb{R}^d), the functional v↦∫t0tendr⋅v dtv\mapsto\int_{t_0}^{t_{\mathrm{end}}}r\cdot v\,\mathrm{d}t satisfies

∥r∥V⋆2=∫t0tendω(t)∣r(t)∣2 dt.(18)\lVert r\rVert_{V^\star}^2=\int_{t_0}^{t_{\mathrm{end}}}\omega(t)|r(t)|^2\,\mathrm{d}t. \tag*{(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)\rho(t):=e^{-8L_F(t-t_0)}. For w∈Uw\in U, integration by parts and w(t0)=0w(t_0)=0 give

∫t0tendρ w⋅w′ dt=12ρ(tend)∣w(tend)∣2+4LF∫t0tendρ∣w∣2 dt≥4LF∫t0tendρ∣w∣2 dt.\int_{t_0}^{t_{\mathrm{end}}}\rho\,w\cdot w'\,\mathrm{d}t=\frac{1}{2}\rho(t_{\mathrm{end}})|w(t_{\mathrm{end}})|^2+4L_F\int_{t_0}^{t_{\mathrm{end}}}\rho|w|^2\,\mathrm{d}t\geq4L_F\int_{t_0}^{t_{\mathrm{end}}}\rho|w|^2\,\mathrm{d}t.

The Cauchy–Schwarz inequality therefore implies

(∫t0tendρ∣w∣2 dt)1/2≤14LF(∫t0tendρ∣w′∣2 dt)1/2.\left(\int_{t_0}^{t_{\mathrm{end}}}\rho|w|^2\,\mathrm{d}t\right)^{1/2}\leq\frac{1}{4L_F}\left(\int_{t_0}^{t_{\mathrm{end}}}\rho|w'|^2\,\mathrm{d}t\right)^{1/2}.

On every interval of I0\mathcal{I}_0, there holds ρ≤ω≤e8LFτ0ρ\rho\leq\omega\leq e^{8L_F\tau_0}\rho. Together with e4LFτ0≤2e^{4L_F\tau_0}\leq2, which is the step-size restriction (13), we obtain

(∫t0tendω∣w∣2 dt)1/2≤e4LFτ04LF(∫t0tendω∣w′∣2 dt)1/2≤12LF∥w∥Ufor every w∈U.(19)\left(\int_{t_0}^{t_{\mathrm{end}}}\omega|w|^2\,\mathrm{d}t\right)^{1/2}\leq\frac{e^{4L_F\tau_0}}{4L_F}\left(\int_{t_0}^{t_{\mathrm{end}}}\omega|w'|^2\,\mathrm{d}t\right)^{1/2}\leq\frac{1}{2L_F}\lVert w\rVert_U\qquad\text{for every }w\in U. \tag*{(19)}

We now verify the operator assumptions of Section 2. Let x,z∈Ux,z\in U and w:=x−zw:=x-z. The identity (18), the Lipschitz bound (12), and the weighted Poincaré inequality (19) show

∥Ax−Az∥V⋆≤∥w∥U+LF(∫t0tendω∣w∣2 dt)1/2≤32∥x−z∥U,\lVert Ax-Az\rVert_{V^\star}\leq\lVert w\rVert_U+L_F\left(\int_{t_0}^{t_{\mathrm{end}}}\omega|w|^2\,\mathrm{d}t\right)^{1/2}\leq\frac{3}{2}\lVert x-z\rVert_U,

which is the Lipschitz continuity (7) with L=3/2L=3/2. We choose

T:U→V,Tw:=ωw′.T:U\to V,\qquad Tw:=\omega w'.

The definition of the norms (17) immediately gives ∥Tx−Tz∥V=∥x−z∥U\lVert Tx-Tz\rVert_V=\lVert x-z\rVert_U, which is (8) with M=1M=1. Furthermore, every partition Ij\mathcal{I}_j is a refinement of I0\mathcal{I}_0, so ω\omega is constant on each interval of Ij\mathcal{I}_j. Therefore, ωw′∈Vj\omega w' \in V_j for all w∈Ujw \in U_j, and every v∈Vjv \in V_j is the image of w(t):=∫t0tω−1v ds∈Ujw(t):=\int_{t_0}^{t}\omega^{-1}v\,\mathrm{d}s \in U_j. This shows surjectivity

T(Uj)=Vjfor every j≥0.T(U_j)=V_j \qquad\text{for every }j\ge0.

Finally, (12) and (19) show

⟨Ax−Az,Tx−Tz⟩=∫t0tendω(w′−F(t,x0+x)+F(t,x0+z))⋅w′ dt≥∥w∥U2−LF(∫t0tendω∣w∣2 dt)1/2∥w∥U≥12∥x−z∥U2.\begin{aligned} \langle Ax-Az,Tx-Tz\rangle &=\int_{t_0}^{t_{\mathrm{end}}}\omega\bigl(w'-F(t,x_0+x)+F(t,x_0+z)\bigr)\cdot w'\,\mathrm{d}t\\ &\ge\lVert w\rVert_U^2-L_F\left(\int_{t_0}^{t_{\mathrm{end}}}\omega\lvert w\rvert^2\,\mathrm{d}t\right)^{1/2}\lVert w\rVert_U\\ &\ge\frac{1}{2}\lVert x-z\rVert_U^2. \end{aligned}

which is the strong monotonicity (9) with α=1/2\alpha=1/2. Altogether, the assumptions (7)–(9) are satisfied with

L=32,M=1,α=12.L=\frac{3}{2},\qquad M=1,\qquad\alpha=\frac{1}{2}.

Lemma 2 with f=0f=0 gives a unique solution uj∈Uju_j\in U_j of (10) on each level, so yj=x0+ujy_j=x_0+u_j is the unique solution of (14). Fix ℓ∈N0\ell\in\mathbb{N}_0 and n∈Nn\in\mathbb{N}. By Section 2, the sequence Tuℓ,…,Tuℓ+nTu_\ell,\ldots,Tu_{\ell+n} satisfies (1) and (2). Since TT is an isometry, ∥Tuj−Tuk∥V=∥uj−uk∥U=∥yj−yk∥U\lVert Tu_j-Tu_k\rVert_V=\lVert u_j-u_k\rVert_U=\lVert y_j-y_k\rVert_U for all j,kj,k. Applying Theorem 1 to these n+1n+1 points we obtain

∑j=ℓℓ+n−1∥yj+1−yj∥U2≲n1−δ∥yℓ+n−yℓ∥U2with δ∈(0,1).\sum_{j=\ell}^{\ell+n-1}\lVert y_{j+1}-y_j\rVert_U^2\lesssim n^{1-\delta}\lVert y_{\ell+n}-y_\ell\rVert_U^2 \qquad\text{with }\delta\in(0,1).

It remains to return to the standard norm. Since w(t0)=0w(t_0)=0 implies ∥w∥L2(t0,tend)≤12(tend−t0)2∥w′∥L2(t0,tend)\lVert w\rVert_{L^2(t_0,t_{\mathrm{end}})}\le\frac{1}{2}(t_{\mathrm{end}}-t_0)^2\lVert w'\rVert_{L^2(t_0,t_{\mathrm{end}})}, the bounds on the weight show

∥w∥U2≤∥w∥H1(t0,tend)2≤(1+(tend−t0)22)e8LF(tend−t0)∥w∥U2for every w∈U.\lVert w\rVert_U^2\le\lVert w\rVert_{H^1(t_0,t_{\mathrm{end}})}^2\le\left(1+\frac{(t_{\mathrm{end}}-t_0)^2}{2}\right)e^{8L_F(t_{\mathrm{end}}-t_0)}\lVert w\rVert_U^2 \qquad\text{for every }w\in U.

We conclude that, for every ℓ∈N0\ell\in\mathbb{N}_0 and n∈Nn\in\mathbb{N},

∑j=ℓℓ+n−1∥yj+1−yj∥H1(t0,tend)2≲n1−δ∥yℓ+n−yℓ∥H1(t0,tend)2.(20)\sum_{j=\ell}^{\ell+n-1}\lVert y_{j+1}-y_j\rVert_{H^1(t_0,t_{\mathrm{end}})}^2\lesssim n^{1-\delta}\lVert y_{\ell+n}-y_\ell\rVert_{H^1(t_0,t_{\mathrm{end}})}^2. \tag*{(20)}

The implied constant and δ\delta as well as the step-size restriction (13) are independent of the polynomial degree pp, the dimension dd, and the partitions Ij\mathcal{I}_j.

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\eta_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 FF is continuously differentiable with Lipschitz continuous Jacobian, and that the initial partition I0\mathcal{I}_0 is sufficiently fine. Then, there exist ε>0\varepsilon>0, 1>δ>01>\delta>0, and C(n)=O(n1−δ)C(n)=O(n^{1-\delta}) such that

∑j=ℓℓ+n−1(∥yj+1−yj∥H1(t0,tend)2−εηj2)≤C(n)∥y−yℓ∥H1(t0,tend)2for all ℓ,n∈N.\sum_{j=\ell}^{\ell+n-1}\left(\lVert y_{j+1}-y_j\rVert_{H^1(t_0,t_{\mathrm{end}})}^2-\varepsilon\eta_j^2\right)\le C(n)\lVert y-y_\ell\rVert_{H^1(t_0,t_{\mathrm{end}})}^2 \qquad\text{for all }\ell,n\in\mathbb{N}.

The proof linearizes the initial value problem around the exact solution yy 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)\lVert y-y_j\rVert_{H^1(t_0,t_{\mathrm{end}})} and is absorbed by the term εηj2\varepsilon\eta_j^2.

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 FF, whereas the Taylor expansion in [4] requires the differentiability of FF. 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\varepsilon= 0. Third, the step-size restriction (13) is explicit and depends only on the Lipschitz constant LFL_F.

References

References

  1. [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.
  2. [3]Michael Feischl. “Inf-sup stability implies quasi-orthogonality”. In: Math. Comp. 91.337 (Sept. 2022), pp. 2059–2094. ISSN: 0025-5718. DOI: 10.1090/mcom/3748. URL: https://doi.org/10.1090/mcom/3748.
  3. [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

Paper details

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

views · 7

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