Introduction
We consider Field-Of-Values (FOV) equivalent preconditioners for the time-dependent Stokes equations that have been discretized in time by stage-weighted Radau IIA Runge–Kutta (RK) and weighted discontinuous Galerkin (DG) methods. The time-dependent Stokes problem for velocity u : Ω × I → R d u : \Omega\times I \to\mathbb{R}^{d} u : Ω × I → R d and pressure p : Ω × I → R p : \Omega\times I \to\mathbb{R} p : Ω × I → R , in which Ω ⊂ R d \Omega\subset\mathbb{R}^{d} Ω ⊂ R d , d ∈ { 2 , 3 } d \in\{2, 3\} d ∈ { 2 , 3 } is a bounded polygonal domain and I = [ 0 , T ] I = [0,T] I = [ 0 , T ] the time-interval of interest, is given by
∂ t u − ∇ ⋅ ( ν ∇ u ) + ∇ p = f for ( x , t ) ∈ Ω × I , u = 0 for ( x , t ) ∈ ∂ Ω × I , ∇ ⋅ u = 0 for ( x , t ) ∈ Ω × I , u ( x , 0 ) = u 0 ( 0 ) for x ∈ Ω . (1) \begin{aligned}
\partial_t u - \nabla\cdot(\nu\nabla u) + \nabla p &= f && \text{for } (x,t) \in\Omega\times I,\qquad u = 0 && \text{for } (x,t) \in\partial\Omega\times I,\\
\nabla\cdot u &= 0 && \text{for } (x,t) \in\Omega\times I,\qquad u(x,0) = u_0(0) && \text{for } x \in\Omega. \tag*{(1)}
\end{aligned} ∂ t u − ∇ ⋅ ( ν ∇ u ) + ∇ p ∇ ⋅ u = f = 0 for ( x , t ) ∈ Ω × I , u = 0 for ( x , t ) ∈ Ω × I , u ( x , 0 ) = u 0 ( 0 ) for ( x , t ) ∈ ∂ Ω × I , for x ∈ Ω. (1)
in which ν > 0 \nu> 0 ν > 0 is a given constant (kinematic) viscosity, f : Ω × I → R d f : \Omega\times I \to\mathbb{R}^{d} f : Ω × I → R d a body force, and u 0 : Ω → R d u_0 : \Omega\to\mathbb{R}^{d} u 0 : Ω → R d a given divergence-free initial velocity field.
Preconditioners for the time-dependent Stokes equations discretized by backward Euler have been studied in various works [13, 28, 31, 40]. Of particular interest is the work of Cahouet and Chabard [6] who introduce a simple approximation to the pressure Schur complement of the block system resulting from discretizing eq. (1) . This approximation is a sum of a mass matrix scaled by ν − 1 \nu^{-1} ν − 1 and a Laplacian scaled by the discrete time step. When backward Euler time stepping is used, the discrete form of eq. (1) is symmetric. This symmetry is used, for example, in [26, 27] to prove that the preconditioner of Cahouet and Chabard [6] is parameter-robust, i.e., robust with respect to mesh size, time step, and viscosity. They do this by finding a uniform bound for the condition number of the preconditioned system. See also [5, 29].
When discretizing a time-dependent partial differential equation (PDE) by a higher order time stepping method, the resulting discretization is in general not symmetric. This complicates constructing parameter-robust preconditioners for these methods because a uniform condition number no longer guarantees robust. convergence of Krylov subspace methods. Instead, FOV analysis is often used to describe the asymptotic convergence of GMRES. A functional analytic approach to preconditioning for nonsymmetric problems is briefly discussed in [19]. For nonsymmetric saddle point problems we mention the work of Loghin and Wathen [24] in which they develop robust nonsymmetric FOV equivalent preconditioners. We will use a slight modification of this framework to determine robust FOV equivalent preconditioners for system matrices resulting from Radau IIA RK [10, 14] and higher-order DG [18, 38] time stepping methods applied to eq. (1) . Our preconditioners are higher-order variations of the Cahouet and Chabard [6] preconditioner. Let us also mention [8, 23, 25, 30, 35, 36] for alternative strategies that have been proposed to precondition implicit RK methods applied to time-dependent PDEs.
In this paper we first consider preconditioners for Radau IIA RK time stepping methods. By weighing each stage of the RK scheme by a suitably chosen parameter we are able to show that the discrete weak form of ∂ t u − ∇ ⋅ ( ν ∇ u ) \partial_t u - \nabla\cdot(\nu\nabla u) ∂ t u − ∇ ⋅ ( ν ∇ u ) in eq. (1) when using an s s s -stage Radau IIA RK discretization is coercive. This allows us to design a simple and robust block preconditioner (one block per stage) for the system matrix.
We next consider preconditioners for higher-order weighted DG time stepping methods. The idea of using DG time stepping with weighted inner products in time to discretize time-dependent PDEs has previously been used, for example, in [11, 34]. Weighted inner products in time have also been used to analyze higher-order DG time stepping methods [7, 20, 41]. We use weighted inner products in time to discretize eq. (1) in time and show that the discrete weak form of ∂ t u − ∇ ⋅ ( ν ∇ u ) \partial_t u - \nabla\cdot(\nu\nabla u) ∂ t u − ∇ ⋅ ( ν ∇ u ) in eq. (1) is coercive. This result is in contrast to using traditional DG time-stepping methods in which the discrete weak form of ∂ t u − ∇ ⋅ ( ν ∇ u ) \partial_t u - \nabla\cdot(\nu\nabla u) ∂ t u − ∇ ⋅ ( ν ∇ u ) is inf-sup stable but not necessarily coercive. We will use the coercivity of this weak form to design a robust preconditioner for the weighted DG time stepping method.
Traditional (non-weighted) DG time stepping methods are equivalent to Radau IIA RK time stepping methods [1 , 2 ] . We show that the weighted DG time stepping method results in a new RK method, one in which the RK time-discretization of ∂ t u − ∇ ⋅ ( ν ∇ u ) \partial_t u - \nabla\cdot(\nu\nabla u) ∂ t u − ∇ ⋅ ( ν ∇ u ) in eq. (1) is coercive. This new RK method provides hints as to how to choose the weights in the weighted Radau IIA RK time stepping method.
We organize this paper as follows. In § 2 we summarize, and slightly modify, the framework presented in [24] for FOV-equivalent preconditioners for nonsymmetric saddle-point problems. In § 3 we present and analyze the stage-weighted Radau IIA RK, weighted DG, and new RK time-discretizations of eq. (1) . Parameter-robust FOV equivalent preconditioners are presented in § 4 . Numerical examples in two and three dimensions in § 5 verify the robustness of the proposed preconditioners.
Preconditioning nonsymmetric saddle-point problems
Before determining a preconditioner for discretizations of eq. (1) , we analyze FOV-equivalent preconditioners for a general nonsymmetric saddle-point problem. Let { V h } \{V_h\} { V h } and { Q h } \{Q_h\} { Q h } be families of finite element spaces corresponding to shape regular meshes of size h h h . Let V h V_h V h be endowed with an inner product ( ⋅ , ⋅ ) V h (\cdot,\cdot)_{V_h} ( ⋅ , ⋅ ) V h and denote by ∥ ⋅ ∥ V h \lVert\cdot\rVert_{V_h} ∥ ⋅ ∥ V h the norm induced by this inner product. Similarly, let Q h Q_h Q h be endowed with an inner product ( ⋅ , ⋅ ) Q h (\cdot,\cdot)_{Q_h} ( ⋅ , ⋅ ) Q h and denote its induced norm by ∥ ⋅ ∥ Q h \lVert\cdot\rVert_{Q_h} ∥ ⋅ ∥ Q h . We consider the problem: Find ( u h , p h ) ∈ V h × Q h (u_h,p_h) \in V_h \times Q_h ( u h , p h ) ∈ V h × Q h , such that
a ( u h , v h ) + b ( v h , p h ) = F ( v h ) ∀ v h ∈ V h , − b ( u h , q h ) = G ( q h ) ∀ q h ∈ Q h . (2) \begin{aligned}
a(u_h,v_h) + b(v_h,p_h) &= \mathcal{F}(v_h) && \forall v_h \in V_h,\\
-b(u_h,q_h) &= \mathcal{G}(q_h) && \forall q_h \in Q_h. \tag*{(2)}
\end{aligned} a ( u h , v h ) + b ( v h , p h ) − b ( u h , q h ) = F ( v h ) = G ( q h ) ∀ v h ∈ V h , ∀ q h ∈ Q h . (2)
where F : V h → R \mathcal{F}: V_h \to\mathbb{R} F : V h → R and G : Q h → R \mathcal{G}: Q_h \to\mathbb{R} G : Q h → R are bounded linear functionals. We assume there exist positive constants c a c_a c a and α \alpha α such that the bilinear form a : V h × V h → R a : V_h \times V_h \to\mathbb{R} a : V h × V h → R , which need not be symmetric, satisfies
a ( u h , v h ) ≤ c a ∥ u h ∥ V h ∥ v h ∥ V h ∀ u h , v h ∈ V h , (3) a(u_h,v_h) \le c_a \lVert u_h\rVert_{V_h}\lVert v_h\rVert_{V_h} \qquad\forall u_h,v_h \in V_h, \tag*{(3)} a ( u h , v h ) ≤ c a ∥ u h ∥ V h ∥ v h ∥ V h ∀ u h , v h ∈ V h , (3)
a ( v h , v h ) ≥ α ∥ v h ∥ V h 2 ∀ v h ∈ V h . (4) a(v_h,v_h) \ge\alpha\lVert v_h\rVert_{V_h}^{2} \qquad\forall v_h \in V_h. \tag*{(4)} a ( v h , v h ) ≥ α ∥ v h ∥ V h 2 ∀ v h ∈ V h . (4)
and that there exist positive constants c b c_b c b and β \beta β such that the bilinear form b : V h × Q h → R b : V_h \times Q_h \to\mathbb{R} b : V h × Q h → R satisfies
b ( v h , q h ) ≤ c b ∥ v h ∥ V h ∥ q h ∥ Q h ∀ v h ∈ V h , q h ∈ Q h , (5) b(v_h,q_h) \le c_b \lVert v_h\rVert_{V_h}\lVert q_h\rVert_{Q_h} \qquad\forall v_h \in V_h,\ q_h \in Q_h, \tag*{(5)} b ( v h , q h ) ≤ c b ∥ v h ∥ V h ∥ q h ∥ Q h ∀ v h ∈ V h , q h ∈ Q h , (5)
inf q h ∈ Q h sup v h ∈ V h b ( v h , q h ) ∥ v h ∥ V h ∥ q h ∥ Q h ≥ β . (6) \inf_{q_h\in Q_h}\sup_{v_h\in V_h}\frac{b(v_h,q_h)}{\lVert v_h\rVert_{V_h}\lVert q_h\rVert_{Q_h}} \ge\beta. \tag*{(6)} q h ∈ Q h inf v h ∈ V h sup ∥ v h ∥ V h ∥ q h ∥ Q h b ( v h , q h ) ≥ β . (6)
The assumptions in eqs. (3) and (4) are sufficient for the saddle-point problem eq. (2) to have a unique solution [4, Theorem 4.2.1.
Let ⟨ x , y ⟩ = x T y \langle x,y\rangle= x^{T}y ⟨ x , y ⟩ = x T y ∀ x , y ∈ R n \forall x,y \in\mathbb{R}^{n} ∀ x , y ∈ R n be the Euclidean inner product on R n \mathbb{R}^{n} R n . Let M ∈ R n × n M \in\mathbb{R}^{n\times n} M ∈ R n × n be any symmetric and positive definite matrix. We will write ⟨ x , y ⟩ M : = ⟨ M x , y ⟩ \langle x,y\rangle_M := \langle Mx,y\rangle ⟨ x , y ⟩ M := ⟨ M x , y ⟩ ∀ x , y ∈ R n \forall x,y \in\mathbb{R}^{n} ∀ x , y ∈ R n . This inner product induces the norm ∥ x ∥ M = ⟨ x , x ⟩ M 1 / 2 \lVert x\rVert_M = \langle x,x\rangle_M^{1/2} ∥ x ∥ M = ⟨ x , x ⟩ M 1/2 . Furthermore, we say that the matrices A , B ∈ R n × n A,B \in\mathbb{R}^{n\times n} A , B ∈ R n × n are ( M (M ( M -FOV equivalent if there exist positive constants c ⋆ c_{\star} c ⋆ and c ˉ ⋆ \bar{c}_{\star} c ˉ ⋆ such that
c ⋆ ≤ inf 0 ≠ x ∈ R n ⟨ A B − 1 x , x ⟩ M ⟨ x , x ⟩ M , c ˉ ⋆ ≤ inf 0 ≠ x ∈ R n ⟨ B A − 1 x , x ⟩ M ⟨ x , x ⟩ M . c_{\star} \le\inf_{0\ne x\in\mathbb{R}^{n}}\frac{\langle AB^{-1}x,x\rangle_M}{\langle x,x\rangle_M}, \qquad\bar{c}_{\star} \le\inf_{0\ne x\in\mathbb{R}^{n}}\frac{\langle BA^{-1}x,x\rangle_M}{\langle x,x\rangle_M}. c ⋆ ≤ 0 = x ∈ R n inf ⟨ x , x ⟩ M ⟨ A B − 1 x , x ⟩ M , c ˉ ⋆ ≤ 0 = x ∈ R n inf ⟨ x , x ⟩ M ⟨ B A − 1 x , x ⟩ M .
Let n v = dim V h n_v = \dim V_h n v = dim V h , n q = dim Q h n_q = \dim Q_h n q = dim Q h , n = n v + n q n = n_v+n_q n = n v + n q , { ϕ i } i = 1 n v \{\phi_i\}_{i=1}^{n_v} { ϕ i } i = 1 n v be a basis for V h V_h V h and { ψ i } i = 1 n q \{\psi_i\}_{i=1}^{n_q} { ψ i } i = 1 n q be a basis for Q h Q_h Q h . Let v h ∈ V h v_h \in V_h v h ∈ V h such that v h = ∑ i = 1 n v v i ϕ i v_h = \sum_{i=1}^{n_v}v_i\phi_i v h = ∑ i = 1 n v v i ϕ i and define v ∈ R n v \mathbf{v} \in\mathbb{R}^{n_v} v ∈ R n v to be the resulting vector of expansion coefficients. Likewise, let q h ∈ Q h q_h \in Q_h q h ∈ Q h such that q h = ∑ i = 1 n q q i ψ i q_h = \sum_{i=1}^{n_q}q_i\psi_i q h = ∑ i = 1 n q q i ψ i and define q ∈ R n q \mathbf{q} \in\mathbb{R}^{n_q} q ∈ R n q to be the resulting vector of expansion coefficients. We define the matrices A A A and B B B such that ⟨ A v , v ⟩ = a h ( v h , v h ) \langle A\mathbf{v},\mathbf{v}\rangle= a_h(v_h,v_h) ⟨ A v , v ⟩ = a h ( v h , v h ) and ⟨ B v , q ⟩ = b h ( v h , q h ) \langle B\mathbf{v},\mathbf{q}\rangle= b_h(v_h,q_h) ⟨ B v , q ⟩ = b h ( v h , q h ) , and the vectors f \mathbf{f} f and g \mathbf{g} g such that ⟨ f , v ⟩ = F ( v h ) \langle\mathbf{f},\mathbf{v}\rangle= F(v_h) ⟨ f , v ⟩ = F ( v h ) and ⟨ g , q ⟩ = G ( q h ) \langle\mathbf{g},\mathbf{q}\rangle= G(q_h) ⟨ g , q ⟩ = G ( q h ) . We may then write eq. (2) as finding u ∈ R n v \mathbf{u} \in\mathbb{R}^{n_v} u ∈ R n v and p ∈ R n q \mathbf{p} \in\mathbb{R}^{n_q} p ∈ R n q such that
A [ u p ] = [ A B T − B 0 ] [ u p ] = [ f g ] . (7) \mathcal{A}
\begin{bmatrix}
\mathbf{u}\\
\mathbf{p}
\end{bmatrix}
=
\begin{bmatrix}
A & B^{T}\\
-B & 0
\end{bmatrix}
\begin{bmatrix}
\mathbf{u}\\
\mathbf{p}
\end{bmatrix}
=
\begin{bmatrix}
\mathbf{f}\\
\mathbf{g}
\end{bmatrix}. \tag*{(7)} A [ u p ] = [ A − B B T 0 ] [ u p ] = [ f g ] . (7)
Define the matrices P v P_v P v and P q P_q P q such that
⟨ P v u , v ⟩ = ( u h , v h ) V h ∀ u h , v h ∈ V h , ⟨ P q p , q ⟩ = ( p h , q h ) Q h ∀ p h , q h ∈ Q h , \langle P_v\mathbf{u},\mathbf{v}\rangle= (u_h,v_h)_{V_h}\qquad\forall u_h,v_h \in V_h,\qquad\langle P_q\mathbf{p},\mathbf{q}\rangle= (p_h,q_h)_{Q_h}\qquad\forall p_h,q_h \in Q_h, ⟨ P v u , v ⟩ = ( u h , v h ) V h ∀ u h , v h ∈ V h , ⟨ P q p , q ⟩ = ( p h , q h ) Q h ∀ p h , q h ∈ Q h ,
and
P ~ : = [ P v 0 0 P q ] , P ~ U : = [ P v B T 0 ρ P q ] , (8) \widetilde{P} :=
\begin{bmatrix}
P_v & 0\\
0 & P_q
\end{bmatrix},
\qquad
\widetilde{P}_U :=
\begin{bmatrix}
P_v & B^{T}\\
0 & \rho P_q
\end{bmatrix}, \tag*{(8)} P := [ P v 0 0 P q ] , P U := [ P v 0 B T ρ P q ] , (8)
with ρ \rho ρ a positive parameter. Under the assumptions eqs. (3) and (4), Loghin and Wathen [24] show that P ~ U \widetilde{P}_U P U is ( P ~ − 1 ) (\widetilde{P}^{-1}) ( P − 1 ) -FOV equivalent to A \mathcal{A} A , provided ρ ≤ ρ 0 \rho\le\rho_0 ρ ≤ ρ 0 where ρ 0 \rho_0 ρ 0 is a constant such that ∥ A P v − 1 − I ∥ P v − 1 ≤ ρ 0 \lVert AP_v^{-1}-I\rVert_{P_v^{-1}} \le\rho_0 ∥ A P v − 1 − I ∥ P v − 1 ≤ ρ 0 , see [24, Theorem 3.9, Remark 3.3]. A consequence of this result is that the residuals of the preconditioned system, using preconditioner P ~ U \widetilde{P}_U P U , at the k k k -th GMRES iteration, r k \mathbf{r}^k r k , satisfy [37],
∥ r k ∥ P ~ − 1 ∥ r 0 ∥ P ~ − 1 ≤ ( 1 − c ⋆ c ˉ ⋆ ) k / 2 . (9) \frac{\lVert\mathbf{r}^k\rVert_{\widetilde{P}^{-1}}}{\lVert\mathbf{r}^0\rVert_{\widetilde{P}^{-1}}}
\le\left(1-c_{\star}\bar{c}_{\star}\right)^{k/2}. \tag*{(9)} ∥ r 0 ∥ P − 1 ∥ r k ∥ P − 1 ≤ ( 1 − c ⋆ c ˉ ⋆ ) k /2 . (9)
Remark 1. Loghin and Wathen [24] also prove FOV equivalence for the more general case in which eq. (3b) is replaced by a ( ⋅ , ⋅ ) a(\cdot,\cdot) a ( ⋅ , ⋅ ) being inf-sup stable. In this case, they show that P ~ U \widetilde{P}_U P U , but with P v P_v P v replaced by A A A or a matrix that is ( P v − 1 ) (P_v^{-1}) ( P v − 1 ) -FOV equivalent to A A A , is also ( P ~ − 1 ) (\widetilde{P}^{-1}) ( P − 1 ) -FOV equivalent to A A A , see [24, Theorem 3.7 and 3.9].
In this work we consider a slight modification of eq. (8) . Let
P : = [ ω P v 0 0 ρ P q ] , P U : = [ ω P v B T 0 ρ P q ] . (10) P :=
\begin{bmatrix}
\omega P_v & 0\\
0 & \rho P_q
\end{bmatrix},
\qquad
P_U :=
\begin{bmatrix}
\omega P_v & B^{T}\\
0 & \rho P_q
\end{bmatrix}. \tag*{(10)} P := [ ω P v 0 0 ρ P q ] , P U := [ ω P v 0 B T ρ P q ] . (10)
For completeness, we redo the proofs to show that P U P_U P U is ( P − 1 ) (P^{-1}) ( P − 1 ) -FOV-equivalent to A \mathcal{A} A for ω \omega ω and ρ \rho ρ sufficiently large positive parameters. Our proofs are different from [24]; the assumption that a ( ⋅ , ⋅ ) a(\cdot,\cdot) a ( ⋅ , ⋅ ) is coercive eq. (3b) simplifies the proofs. We have the following result.
Theorem 1. Let c a , c b , α , β c_a,c_b,\alpha,\beta c a , c b , α , β be the constants from eqs. (3) and (4) and let ω \omega ω and ρ \rho ρ be such that ρ ω > 1 4 c a 2 α − 1 \rho\omega> \frac{1}{4}c_a^2\alpha^{-1} ρ ω > 4 1 c a 2 α − 1 and ω > 1 2 c a 2 α − 1 \omega> \frac{1}{2}c_a^2\alpha^{-1} ω > 2 1 c a 2 α − 1 . Then, the matrices A A A and P U P_U P U , as defined in eqs. (7) and (10) are ( P − 1 ) (\mathcal{P}^{-1}) ( P − 1 ) -FOV-equivalent with
c ⋆ = 2 ω α − c a / ρ 2 ω 3 α − 1 max { 1 , α − 2 c a 2 β − 2 } , c ‾ ⋆ = min { 2 α ω − c a 2 , 1 } 2 max { 2 c a 2 + ω ρ − 1 c b 2 , 2 } . c_{\star}=\frac{2\sqrt{\omega}\alpha-c_a/\sqrt{\rho}}{2\sqrt{\omega^3\alpha^{-1}\max\{1,\alpha^{-2}c_a^2\beta^{-2}\}}},\qquad\overline{c}_{\star}=\frac{\min\{2\alpha\omega-c_a^2,1\}}{2\max\{2c_a^2+\omega\rho^{-1}c_b^2,2\}}. c ⋆ = 2 ω 3 α − 1 max { 1 , α − 2 c a 2 β − 2 } 2 ω α − c a / ρ , c ⋆ = 2 max { 2 c a 2 + ω ρ − 1 c b 2 , 2 } min { 2 α ω − c a 2 , 1 } .
Proof. See Appendix A.
Remark 2. Assume that the inner products ( ⋅ , ⋅ ) V h (\cdot,\cdot)_{V_h} ( ⋅ , ⋅ ) V h and ( ⋅ , ⋅ ) Q h (\cdot,\cdot)_{Q_h} ( ⋅ , ⋅ ) Q h are defined such that the constants α , β , c a , c b \alpha,\beta,c_a,c_b α , β , c a , c b in eqs. (3) and (4) are independent of mesh size and other problem parameters, i.e., are uniform constants. Then theorem 1 and eq. (9) imply that asymptotic convergence of GMRES of the preconditioned system is independent of mesh size and other problem parameters.
The fully-discrete time-dependent Stokes problem
To discretize eq. (1) in time we consider both Radau IIA RK time-stepping and DG time-stepping methods. For simplicity, we consider a conforming and inf-sup stable finite element spatial discretization, i.e., V h ⊂ [ H 0 1 ( Ω ) ] d V_h\subset[H_0^1(\Omega)]^d V h ⊂ [ H 0 1 ( Ω ) ] d and Q h ⊂ L 0 2 ( Ω ) Q_h\subset L_0^2(\Omega) Q h ⊂ L 0 2 ( Ω ) . In particular, we will use the Taylor–Hood element. Let ( u , v ) : = ∫ Ω u v d x (u,v):=\int_{\Omega}uv\,\mathrm{d}x ( u , v ) := ∫ Ω uv d x be the L 2 L^2 L 2 -inner product on Ω \Omega Ω , a ( u , v ) : = ν ( ∇ u , ∇ v ) a(u,v):=\nu(\nabla u,\nabla v) a ( u , v ) := ν ( ∇ u , ∇ v ) , and b ( v , q ) : = − ( ∇ ⋅ v , q ) b(v,q):=-(\nabla\cdot v,q) b ( v , q ) := − ( ∇ ⋅ v , q ) . To analyze the discretizations, we consider the following inner products on V h V_h V h and Q h Q_h Q h , respectively:
( u h , v h ) v : = τ ( u h , v h ) + ν ( ∇ u h , ∇ v h ) , (u_h,v_h)_v:=\tau(u_h,v_h)+\nu(\nabla u_h,\nabla v_h), ( u h , v h ) v := τ ( u h , v h ) + ν ( ∇ u h , ∇ v h ) ,
( p h , q h ) q : = inf p h = p h , 1 + p h , 0 q h = q h , 1 + q h , 0 ( τ − 1 ( ∇ p h , 1 , ∇ q h , 1 ) + ν − 1 ( p h , 0 , q h , 0 ) ) . (11) (p_h,q_h)_q:=\inf_{\substack{p_h=p_{h,1}+p_{h,0}\\q_h=q_{h,1}+q_{h,0}}}\left(\tau^{-1}(\nabla p_{h,1},\nabla q_{h,1})+\nu^{-1}(p_{h,0},q_{h,0})\right). \tag*{(11)} ( p h , q h ) q := p h = p h , 1 + p h , 0 q h = q h , 1 + q h , 0 inf ( τ − 1 ( ∇ p h , 1 , ∇ q h , 1 ) + ν − 1 ( p h , 0 , q h , 0 ) ) . (11)
The norms induced by these inner products are denoted by ∥ ⋅ ∥ v \|\cdot\|_v ∥ ⋅ ∥ v and ∥ ⋅ ∥ q \|\cdot\|_q ∥ ⋅ ∥ q . As discussed in [26], ∥ ⋅ ∥ v \|\cdot\|_v ∥ ⋅ ∥ v is a norm on τ [ L 2 ( Ω ) ] d ∩ ν [ H 0 1 ( Ω ) ] d \tau[L^2(\Omega)]^d\cap\nu[H_0^1(\Omega)]^d τ [ L 2 ( Ω ) ] d ∩ ν [ H 0 1 ( Ω ) ] d and ∥ ⋅ ∥ q \|\cdot\|_q ∥ ⋅ ∥ q is a norm on τ − 1 ( H 1 ( Ω ) ∩ L 0 2 ( Ω ) ) + ν − 1 L 0 2 ( Ω ) \tau^{-1}(H^1(\Omega)\cap L_0^2(\Omega))+\nu^{-1}L_0^2(\Omega) τ − 1 ( H 1 ( Ω ) ∩ L 0 2 ( Ω )) + ν − 1 L 0 2 ( Ω ) . It is shown in [26, Section 5.1], that when using the Taylor–Hood element, there exists a uniform constant β > 0 \beta>0 β > 0 such that
sup v h ∈ V h b ( v h , q h ) ∥ v h ∥ v ≥ β ∥ q h ∥ q ∀ q h ∈ Q h . (12) \sup_{v_h\in V_h}\frac{b(v_h,q_h)}{\|v_h\|_v}\geq\beta\|q_h\|_q\qquad\forall q_h\in Q_h. \tag*{(12)} v h ∈ V h sup ∥ v h ∥ v b ( v h , q h ) ≥ β ∥ q h ∥ q ∀ q h ∈ Q h . (12)
The triangulation of the domain Ω \Omega Ω is denoted by T h : = { K } \mathcal{T}_h:=\{K\} T h := { K } , which consists of simplices K K K . We partition the time-interval into N N N subintervals of length Δ t = T / N \Delta t=T/N Δ t = T / N and define t n : = n Δ t t_n:=n\Delta t t n := n Δ t for n = 0 , … , N n=0,\ldots,N n = 0 , … , N , I n = [ t n , t n + 1 ] I_n=[t_n,t_{n+1}] I n = [ t n , t n + 1 ] for n = 0 , … , N − 1 n=0,\ldots,N-1 n = 0 , … , N − 1 , and τ : = 1 / Δ t \tau:=1/\Delta t τ := 1/Δ t .
Radau IIA Runge–Kutta time-stepping
We first discretize eq. (1) in time by a Radau IIA RK time-stepping method [10, 14]. Let A r = [ a i j r ] ∈ R s × s A_r=[a_{ij}^r]\in\mathbb{R}^{s\times s} A r = [ a ij r ] ∈ R s × s be the Radau IIA RK matrix, 0 < c 1 r < … < c s r = 1 0<c_1^r<\ldots<c_s^r=1 0 < c 1 r < … < c s r = 1 the Radau IIA RK nodes, and let t n , i = t n + c i r Δ t t_{n,i}=t_n+c_i^r\Delta t t n , i = t n + c i r Δ t . Define f j ( x ) = f ( x , t n , j ) f_j(x)=f(x,t_{n,j}) f j ( x ) = f ( x , t n , j ) , denote by ( u i , p i ) (u_i,p_i) ( u i , p i ) the approximation to ( u , p ) (u,p) ( u , p ) at t n , i t_{n,i} t n , i , and denote by ( u n , p n ) (u^n,p^n) ( u n , p n ) the approximation to ( u , p ) (u,p) ( u , p ) at t n t_n t n . Discretizing eq. (1) in time we have, given u n u^n u n , that ( u n + 1 , u n + 1 ) (u^{n+1},u^{n+1}) ( u n + 1 , u n + 1 ) is found by solving (see, for example, [15]):
u i = u n + Δ t ∑ j = 1 s a i j r [ f j + ∇ ⋅ ( ν ∇ u j ) − ∇ p j ] , ∇ ⋅ u i = 0 , (13) u_i=u_n+\Delta t\sum_{j=1}^{s}a_{ij}^r\left[f_j+\nabla\cdot(\nu\nabla u_j)-\nabla p_j\right],\qquad\nabla\cdot u_i=0, \tag*{(13)} u i = u n + Δ t j = 1 ∑ s a ij r [ f j + ∇ ⋅ ( ν ∇ u j ) − ∇ p j ] , ∇ ⋅ u i = 0 , (13)
for 1 ≤ i ≤ s 1\leq i\leq s 1 ≤ i ≤ s and setting ( u n + 1 , p n + 1 ) = ( u s , p s ) (u^{n+1},p^{n+1})=(u_s,p_s) ( u n + 1 , p n + 1 ) = ( u s , p s ) . Multiplying eq. (13) by the inverse of the RK matrix and discretizing also in space, we obtain the fully discrete problem: For n = 0 , … , N − 1 n=0,\ldots,N-1 n = 0 , … , N − 1 , find u h n : = ( U 1 , … , U s ) ∈ V h : = [ V h ] s u_h^n:=(U_1,\ldots,U_s)\in V_h:=[V_h]^s u h n := ( U 1 , … , U s ) ∈ V h := [ V h ] s and p h n : = ( P 1 , … , P s ) ∈ Q h : = [ Q h ] s p_h^n:=(P_1,\ldots,P_s)\in Q_h:=[Q_h]^s p h n := ( P 1 , … , P s ) ∈ Q h := [ Q h ] s such that
a ~ r ( u h , v h ) + b ~ r ( v h , p h ) − b ~ r ( u h , q h ) = ∑ i = 1 s [ ( f i , V i ) + τ ∑ j = 1 s ( A r − 1 ) i j ( U n , V i ) ] , (14) \widetilde{a}_r(u_h,v_h)+\widetilde{b}_r(v_h,p_h)-\widetilde{b}_r(u_h,q_h)=\sum_{i=1}^{s}\left[(f_i,V_i)+\tau\sum_{j=1}^{s}(A_r^{-1})_{ij}(U_n,V_i)\right], \tag*{(14)} a r ( u h , v h ) + b r ( v h , p h ) − b r ( u h , q h ) = i = 1 ∑ s [ ( f i , V i ) + τ j = 1 ∑ s ( A r − 1 ) ij ( U n , V i ) ] , (14)
for all v h : = ( V 1 , … , V s ) ∈ V h v_h := (V_1,\ldots,V_s) \in V_h v h := ( V 1 , … , V s ) ∈ V h and q h : = ( Q 1 , … , Q s ) ∈ Q h q_h := (Q_1,\ldots,Q_s) \in Q_h q h := ( Q 1 , … , Q s ) ∈ Q h , in which
a ~ r ( u h , v h ) : = ∑ i = 1 s [ τ ∑ j = 1 s ( A r − 1 ) i j ( U j , V i ) + a ( U i , V i ) ] , b ~ r ( v h , p h ) : = ∑ i = 1 s b ( V i , P i ) . \widetilde{a}_r(u_h,v_h) := \sum_{i=1}^{s}\left[\tau\sum_{j=1}^{s}(\mathsf{A}_r^{-1})_{ij}(U_j,V_i)+a(U_i,V_i)\right], \qquad\widetilde{b}_r(v_h,p_h) := \sum_{i=1}^{s}b(V_i,P_i). a r ( u h , v h ) := i = 1 ∑ s [ τ j = 1 ∑ s ( A r − 1 ) ij ( U j , V i ) + a ( U i , V i ) ] , b r ( v h , p h ) := i = 1 ∑ s b ( V i , P i ) .
We then set ( u h n + 1 , p h n + 1 ) = ( U s , P s ) (u_h^{n+1},p_h^{n+1})=(U_s,P_s) ( u h n + 1 , p h n + 1 ) = ( U s , P s ) . The bilinear form a ~ r ( ⋅ , ⋅ ) \widetilde{a}_r(\cdot,\cdot) a r ( ⋅ , ⋅ ) cannot be shown to satisfy eq. (4) . However, it is known that the RK matrix B \mathsf{B} B of an A-stable irreducible RK method of which B \mathsf{B} B is invertible is weakly positive definite, i.e., that there exists a matrix W ^ ∈ R s × s \widehat{\mathsf{W}}\in\mathbb{R}^{s\times s} W ∈ R s × s such that ⟨ W ^ x , x ⟩ > 0 \langle\widehat{\mathsf{W}}x,x\rangle>0 ⟨ W x , x ⟩ > 0 and ⟨ W ^ B x , x ⟩ > 0 \langle\widehat{\mathsf{W}}\mathsf{B}x,x\rangle>0 ⟨ W B x , x ⟩ > 0 for all x ∈ R s x\in\mathbb{R}^{s} x ∈ R s , see [25, Definition 3.1, Lemma 3.2]. Assuming therefore that there exists a W ^ : = diag ( w ^ 1 , … , w ^ s ) \widehat{\mathsf{W}}:=\operatorname{diag}(\widehat{w}_1,\ldots,\widehat{w}_s) W := diag ( w 1 , … , w s ) with positive w ^ i ∈ R \widehat{w}_i\in\mathbb{R} w i ∈ R such that ⟨ W ^ A r x , x ⟩ > 0 \langle\widehat{\mathsf{W}}\mathsf{A}_r x,x\rangle>0 ⟨ W A r x , x ⟩ > 0 , we multiply each stage in eq. (14) by w ^ i \widehat{w}_i w i and introduce a stage-weighted Radau IIA + Taylor–Hood discretization: For n = 0 , … , N − 1 n=0,\ldots,N-1 n = 0 , … , N − 1 , find u h n : = ( U 1 , … , U s ) ∈ V h : = [ V h ] s u_h^n:=(U_1,\ldots,U_s)\in V_h:=[V_h]^s u h n := ( U 1 , … , U s ) ∈ V h := [ V h ] s and p h n : = ( P 1 , … , P s ) ∈ Q h : = [ Q h ] s p_h^n:=(P_1,\ldots,P_s)\in Q_h:=[Q_h]^s p h n := ( P 1 , … , P s ) ∈ Q h := [ Q h ] s such that
a r ( u h , v h ) + b r ( v h , p h ) − b r ( u h , q h ) = ∑ i = 1 s w ^ i [ ( f i , V i ) + τ ∑ j = 1 s ( A r − 1 ) i j ( U n , V i ) ] , (15) a_r(u_h,v_h)+b_r(v_h,p_h)-b_r(u_h,q_h)=\sum_{i=1}^{s}\widehat{w}_i\left[(f_i,V_i)+\tau\sum_{j=1}^{s}(\mathsf{A}_r^{-1})_{ij}(U_n,V_i)\right], \tag*{(15)} a r ( u h , v h ) + b r ( v h , p h ) − b r ( u h , q h ) = i = 1 ∑ s w i [ ( f i , V i ) + τ j = 1 ∑ s ( A r − 1 ) ij ( U n , V i ) ] , (15)
for all v h : = ( V 1 , … , V s ) ∈ V h v_h:=(V_1,\ldots,V_s)\in V_h v h := ( V 1 , … , V s ) ∈ V h and q h : = ( Q 1 , … , Q s ) ∈ Q h q_h:=(Q_1,\ldots,Q_s)\in Q_h q h := ( Q 1 , … , Q s ) ∈ Q h , in which
a r ( u h , v h ) : = ∑ i = 1 s w ^ i [ τ ∑ j = 1 s ( A r − 1 ) i j ( U j , V i ) + a ( U i , V i ) ] , b r ( v h , p h ) : = ∑ i = 1 s w ^ i b ( V i , P i ) . a_r(u_h,v_h):=\sum_{i=1}^{s}\widehat{w}_i\left[\tau\sum_{j=1}^{s}(\mathsf{A}_r^{-1})_{ij}(U_j,V_i)+a(U_i,V_i)\right],\qquad b_r(v_h,p_h):=\sum_{i=1}^{s}\widehat{w}_i b(V_i,P_i). a r ( u h , v h ) := i = 1 ∑ s w i [ τ j = 1 ∑ s ( A r − 1 ) ij ( U j , V i ) + a ( U i , V i ) ] , b r ( v h , p h ) := i = 1 ∑ s w i b ( V i , P i ) .
In what follows we will prove that a r ( ⋅ , ⋅ ) a_r(\cdot,\cdot) a r ( ⋅ , ⋅ ) and b r ( ⋅ , ⋅ ) b_r(\cdot,\cdot) b r ( ⋅ , ⋅ ) satisfy eqs. (3) and (4) assuming the existence of the aforementioned matrix W ^ \widehat{\mathsf{W}} W . We discuss how to choose W ^ \widehat{\mathsf{W}} W in section 5. We introduce the following inner products associated with V h V_h V h and Q h Q_h Q h :
( u h , v h ) r , v : = ∑ i = 1 s w ^ i ( u i , v i ) v , ( p h , q h ) r , q : = ∑ i = 1 s w ^ i ( p i , q i ) q , (u_h,v_h)_{r,v}:=\sum_{i=1}^{s}\widehat{w}_i(u_i,v_i)_v,\qquad(p_h,q_h)_{r,q}:=\sum_{i=1}^{s}\widehat{w}_i(p_i,q_i)_q, ( u h , v h ) r , v := i = 1 ∑ s w i ( u i , v i ) v , ( p h , q h ) r , q := i = 1 ∑ s w i ( p i , q i ) q ,
respectively, with induced norms denoted by ∥ ⋅ ∥ r , v \|\cdot\|_{r,v} ∥ ⋅ ∥ r , v and ∥ ⋅ ∥ r , q \|\cdot\|_{r,q} ∥ ⋅ ∥ r , q . Here ( ⋅ , ⋅ ) v (\cdot,\cdot)_v ( ⋅ , ⋅ ) v and ( ⋅ , ⋅ ) q (\cdot,\cdot)_q ( ⋅ , ⋅ ) q are defined in eq. (11) .
Lemma 1 (Coercivity). Let W ^ : = diag ( w ^ 1 , … , w ^ s ) ∈ R s × s \widehat{\mathsf{W}}:=\operatorname{diag}(\widehat{w}_1,\ldots,\widehat{w}_s)\in\mathbb{R}^{s\times s} W := diag ( w 1 , … , w s ) ∈ R s × s . If the w ^ i \widehat{w}_i w i are such that C r : = 1 2 ( W ^ A r − 1 + ( W ^ A r − 1 ) T ) C_r:=\frac{1}{2}\left(\widehat{\mathsf{W}}\mathsf{A}_r^{-1}+(\widehat{\mathsf{W}}\mathsf{A}_r^{-1})^{\mathsf{T}}\right) C r := 2 1 ( W A r − 1 + ( W A r − 1 ) T ) is symmetric positive definite, then there exists a uniform constant α > 0 \alpha>0 α > 0 such that
a r ( v h , v h ) ≥ α ∥ v h ∥ r , v 2 ∀ v h ∈ V h . a_r(v_h,v_h)\ge\alpha\|v_h\|_{r,v}^{2}\qquad\forall v_h\in V_h. a r ( v h , v h ) ≥ α ∥ v h ∥ r , v 2 ∀ v h ∈ V h .
Proof. Since C r = 1 2 ( W ^ A r − 1 + ( W ^ A r − 1 ) T ) C_r=\frac{1}{2}\left(\widehat{\mathsf{W}}\mathsf{A}_r^{-1}+(\widehat{\mathsf{W}}\mathsf{A}_r^{-1})^{\mathsf{T}}\right) C r = 2 1 ( W A r − 1 + ( W A r − 1 ) T ) is symmetric positive definite, we have by the spectral theorem that [ C r ] i j = ∑ m = 1 s Z i m λ m Z j m [C_r]_{ij}=\sum_{m=1}^{s}Z_{im}\lambda_m Z_{jm} [ C r ] ij = ∑ m = 1 s Z im λ m Z j m with λ m > 0 \lambda_m>0 λ m > 0 the eigenvalues of C r C_r C r and Z ∈ R s × s Z\in\mathbb{R}^{s\times s} Z ∈ R s × s an orthogonal matrix. Then, since ∑ i = 1 s ∑ j = 1 s τ w ^ i ( A r − 1 ) i j ( V j , V i ) = ∑ i = 1 s ∑ j = 1 s τ [ C r ] i j ( V j , V i ) \sum_{i=1}^{s}\sum_{j=1}^{s}\tau\widehat{w}_i(\mathsf{A}_r^{-1})_{ij}(V_j,V_i)=\sum_{i=1}^{s}\sum_{j=1}^{s}\tau[C_r]_{ij}(V_j,V_i) ∑ i = 1 s ∑ j = 1 s τ w i ( A r − 1 ) ij ( V j , V i ) = ∑ i = 1 s ∑ j = 1 s τ [ C r ] ij ( V j , V i ) ,
a r ( v h , v h ) = τ ∑ m = 1 s λ m ∑ i = 1 s ∑ j = 1 s Z j m Z i m ( V j , V i ) + ν ∑ i = 1 s w ^ i ∥ ∇ V i ∥ L 2 ( Ω ) 2 ≥ λ min τ ∑ i = 1 s ∑ j = 1 s ( ∑ m = 1 s Z m j Z m i ) ( V j , V i ) + ν ∑ i = 1 s w ^ i ∥ ∇ V i ∥ L 2 ( Ω ) 2 = λ min τ ∑ i = 1 s ∑ j = 1 s δ i j ( V j , V i ) + ν ∑ i = 1 s w ^ i ∥ ∇ V i ∥ L 2 ( Ω ) 2 = λ min τ ∑ i = 1 s ∥ V i ∥ L 2 ( Ω ) 2 + ν ∑ i = 1 s w ^ i ∥ ∇ V i ∥ L 2 ( Ω ) 2 ≥ min ( λ min max 1 ≤ k ≤ s w ^ k , 1 ) ∥ v h ∥ r , v 2 , \begin{aligned}
a_r(v_h,v_h)
&=\tau\sum_{m=1}^{s}\lambda_m\sum_{i=1}^{s}\sum_{j=1}^{s}Z_{jm}Z_{im}(V_j,V_i)+\nu\sum_{i=1}^{s}\widehat{w}_i\|\nabla V_i\|_{L^2(\Omega)}^2\\
&\ge\lambda_{\min}\tau\sum_{i=1}^{s}\sum_{j=1}^{s}\left(\sum_{m=1}^{s}Z_{mj}Z_{mi}\right)(V_j,V_i)+\nu\sum_{i=1}^{s}\widehat{w}_i\|\nabla V_i\|_{L^2(\Omega)}^2\\
&=\lambda_{\min}\tau\sum_{i=1}^{s}\sum_{j=1}^{s}\delta_{ij}(V_j,V_i)+\nu\sum_{i=1}^{s}\widehat{w}_i\|\nabla V_i\|_{L^2(\Omega)}^2\\
&=\lambda_{\min}\tau\sum_{i=1}^{s}\|V_i\|_{L^2(\Omega)}^2+\nu\sum_{i=1}^{s}\widehat{w}_i\|\nabla V_i\|_{L^2(\Omega)}^2\\
&\ge\min\left(\frac{\lambda_{\min}}{\max_{1\le k\le s}\widehat{w}_k},1\right)\|v_h\|_{r,v}^{2},
\end{aligned} a r ( v h , v h ) = τ m = 1 ∑ s λ m i = 1 ∑ s j = 1 ∑ s Z j m Z im ( V j , V i ) + ν i = 1 ∑ s w i ∥∇ V i ∥ L 2 ( Ω ) 2 ≥ λ m i n τ i = 1 ∑ s j = 1 ∑ s ( m = 1 ∑ s Z mj Z mi ) ( V j , V i ) + ν i = 1 ∑ s w i ∥∇ V i ∥ L 2 ( Ω ) 2 = λ m i n τ i = 1 ∑ s j = 1 ∑ s δ ij ( V j , V i ) + ν i = 1 ∑ s w i ∥∇ V i ∥ L 2 ( Ω ) 2 = λ m i n τ i = 1 ∑ s ∥ V i ∥ L 2 ( Ω ) 2 + ν i = 1 ∑ s w i ∥∇ V i ∥ L 2 ( Ω ) 2 ≥ min ( max 1 ≤ k ≤ s w k λ m i n , 1 ) ∥ v h ∥ r , v 2 ,
in which λ min \lambda_{\min} λ m i n is the smallest eigenvalue of C r C_r C r .
Lemma 2 (Stability). There exists a uniform constant β > 0 \beta> 0 β > 0 such that
sup v h ∈ V h b r ( v h , q h ) ∥ v h ∥ r , v ≥ β ∥ q h ∥ r , q ∀ q h ∈ Q h . \sup_{v_h\in V_h}\frac{b_r(v_h,q_h)}{\|v_h\|_{r,v}} \ge\beta\|q_h\|_{r,q}\qquad\forall q_h\in Q_h. v h ∈ V h sup ∥ v h ∥ r , v b r ( v h , q h ) ≥ β ∥ q h ∥ r , q ∀ q h ∈ Q h . Proof. By eq. (12) , given Q i ∈ Q h Q_i\in Q_h Q i ∈ Q h , there exists V ~ i ∈ V h \widetilde{V}_i\in V_h V i ∈ V h such that b ( V ~ i , Q i ) = ∥ Q i ∥ q 2 b(\widetilde{V}_i,Q_i)=\|Q_i\|_q^2 b ( V i , Q i ) = ∥ Q i ∥ q 2 and ∥ V ~ i ∥ v ≤ β − 1 ∥ Q i ∥ q \|\widetilde{V}_i\|_v\le\beta^{-1}\|Q_i\|_q ∥ V i ∥ v ≤ β − 1 ∥ Q i ∥ q . Define v ~ h : = ( V ~ 1 , … , V ~ s ) ∈ V h \widetilde{v}_h := (\widetilde{V}_1,\ldots,\widetilde{V}_s)\in V_h v h := ( V 1 , … , V s ) ∈ V h . We find
∥ v ~ h ∥ r , v 2 = ∑ i = 1 s w ^ i ∥ V ~ i ∥ v 2 ≤ ∑ i = 1 s w ^ i β − 2 ∥ Q i ∥ q 2 = β − 2 ∥ q h ∥ r , q 2 , \|\widetilde{v}_h\|_{r,v}^2=\sum_{i=1}^s\widehat{w}_i\|\widetilde{V}_i\|_v^2\le\sum_{i=1}^s\widehat{w}_i\beta^{-2}\|Q_i\|_q^2=\beta^{-2}\|q_h\|_{r,q}^2, ∥ v h ∥ r , v 2 = i = 1 ∑ s w i ∥ V i ∥ v 2 ≤ i = 1 ∑ s w i β − 2 ∥ Q i ∥ q 2 = β − 2 ∥ q h ∥ r , q 2 , b r ( v ~ h , q h ) = ∑ i = 1 s w ^ i b ( V ~ i , q i ) = ∑ i = 1 s w ^ i ∥ Q i ∥ q 2 = ∥ q h ∥ r , q 2 . b_r(\widetilde{v}_h,q_h)=\sum_{i=1}^s\widehat{w}_i b(\widetilde{V}_i,q_i)=\sum_{i=1}^s\widehat{w}_i\|Q_i\|_q^2=\|q_h\|_{r,q}^2. b r ( v h , q h ) = i = 1 ∑ s w i b ( V i , q i ) = i = 1 ∑ s w i ∥ Q i ∥ q 2 = ∥ q h ∥ r , q 2 . The result follows.
Lemma 3 (Continuity). There exist uniform constants c a , c b > 0 c_a,c_b>0 c a , c b > 0 such that
∣ a r ( u h , v h ) ∣ ≤ c a ∥ u h ∥ r , v ∥ v h ∥ r , v ∀ u h , v h ∈ V h , (16) |a_r(u_h,v_h)|\le c_a\|u_h\|_{r,v}\|v_h\|_{r,v}\qquad\forall u_h,v_h\in V_h, \tag*{(16)} ∣ a r ( u h , v h ) ∣ ≤ c a ∥ u h ∥ r , v ∥ v h ∥ r , v ∀ u h , v h ∈ V h , (16) ∣ b r ( v h , q h ) ∣ ≤ c b ∥ v h ∥ r , v ∥ q h ∥ r , q ∀ v h ∈ V h , q h ∈ Q h . (17) |b_r(v_h,q_h)|\le c_b\|v_h\|_{r,v}\|q_h\|_{r,q}\qquad\forall v_h\in V_h,\ q_h\in Q_h. \tag*{(17)} ∣ b r ( v h , q h ) ∣ ≤ c b ∥ v h ∥ r , v ∥ q h ∥ r , q ∀ v h ∈ V h , q h ∈ Q h . (17) Proof. Using a triangle inequality and Cauchy–Schwarz,
∣ a r ( u h , v h ) ∣ ≤ ∣ ∑ i = 1 s ∑ j = 1 s w ^ i ( A ^ r − 1 ) i j ( U j , V i ) ∣ + ∣ ∑ i = 1 s w ^ i ν ( ∇ U i , ∇ V i ) ∣ = : T 1 + T 2 . (18) |a_r(u_h,v_h)|\le\left|\sum_{i=1}^s\sum_{j=1}^s\widehat{w}_i(\widehat{A}_r^{-1})_{ij}(U_j,V_i)\right|+\left|\sum_{i=1}^s\widehat{w}_i\nu(\nabla U_i,\nabla V_i)\right|=:T_1+T_2. \tag*{(18)} ∣ a r ( u h , v h ) ∣ ≤ i = 1 ∑ s j = 1 ∑ s w i ( A r − 1 ) ij ( U j , V i ) + i = 1 ∑ s w i ν ( ∇ U i , ∇ V i ) =: T 1 + T 2 . (18) We bound T 1 T_1 T 1 and T 2 T_2 T 2 separately. First, using Cauchy–Schwarz,
T 1 ≤ max 1 ≤ ℓ , k ≤ s [ ( A ^ r − 1 ) ℓ k ] max 1 ≤ m ≤ s w ^ m 1 / 2 ∑ i = 1 s ∑ j = 1 s τ ∣ ( U j , w ^ i 1 / 2 V i ) ∣ T_1\le\max_{1\le\ell,k\le s}[(\widehat{A}_r^{-1})_{\ell k}]\max_{1\le m\le s}\widehat{w}_m^{1/2}\sum_{i=1}^s\sum_{j=1}^s\tau|(U_j,\widehat{w}_i^{1/2}V_i)| T 1 ≤ 1 ≤ ℓ , k ≤ s max [( A r − 1 ) ℓ k ] 1 ≤ m ≤ s max w m 1/2 i = 1 ∑ s j = 1 ∑ s τ ∣ ( U j , w i 1/2 V i ) ∣ ≤ max 1 ≤ ℓ , k ≤ s [ ( A ^ r − 1 ) ℓ k ] max 1 ≤ m ≤ s w ^ m 1 / 2 min 1 ≤ n ≤ s w ^ n 1 / 2 ∑ i = 1 s ∥ ( τ w ^ i ) 1 / 2 U i ∥ L 2 ( Ω ) ∑ j = 1 s ∥ ( τ w ^ j ) 1 / 2 V j ∥ L 2 ( Ω ) \le\max_{1\le\ell,k\le s}[(\widehat{A}_r^{-1})_{\ell k}]\frac{\max_{1\le m\le s}\widehat{w}_m^{1/2}}{\min_{1\le n\le s}\widehat{w}_n^{1/2}}\sum_{i=1}^s\|(\tau\widehat{w}_i)^{1/2}U_i\|_{L^2(\Omega)}\sum_{j=1}^s\|(\tau\widehat{w}_j)^{1/2}V_j\|_{L^2(\Omega)} ≤ 1 ≤ ℓ , k ≤ s max [( A r − 1 ) ℓ k ] min 1 ≤ n ≤ s w n 1/2 max 1 ≤ m ≤ s w m 1/2 i = 1 ∑ s ∥ ( τ w i ) 1/2 U i ∥ L 2 ( Ω ) j = 1 ∑ s ∥ ( τ w j ) 1/2 V j ∥ L 2 ( Ω ) = max 1 ≤ ℓ , k ≤ s [ ( A ^ r − 1 ) ℓ k ] max 1 ≤ m ≤ s w ^ m 1 / 2 min 1 ≤ n ≤ s w ^ n 1 / 2 ∥ u h ∥ r , v ∥ v h ∥ r , v . =\max_{1\le\ell,k\le s}[(\widehat{A}_r^{-1})_{\ell k}]\frac{\max_{1\le m\le s}\widehat{w}_m^{1/2}}{\min_{1\le n\le s}\widehat{w}_n^{1/2}}\|u_h\|_{r,v}\|v_h\|_{r,v}. = 1 ≤ ℓ , k ≤ s max [( A r − 1 ) ℓ k ] min 1 ≤ n ≤ s w n 1/2 max 1 ≤ m ≤ s w m 1/2 ∥ u h ∥ r , v ∥ v h ∥ r , v . Next, again using Cauchy–Schwarz,
T 2 ≤ ∑ i = 1 s ∥ ( w ^ i ν ) 1 / 2 ∇ U i ∥ L 2 ( Ω ) ∥ ( w ^ i ν ) 1 / 2 ∇ V i ∥ L 2 ( Ω ) = ∥ u h ∥ r , v ∥ v h ∥ r , v . T_2\le\sum_{i=1}^s\|(\widehat{w}_i\nu)^{1/2}\nabla U_i\|_{L^2(\Omega)}\|(\widehat{w}_i\nu)^{1/2}\nabla V_i\|_{L^2(\Omega)}=\|u_h\|_{r,v}\|v_h\|_{r,v}. T 2 ≤ i = 1 ∑ s ∥ ( w i ν ) 1/2 ∇ U i ∥ L 2 ( Ω ) ∥ ( w i ν ) 1/2 ∇ V i ∥ L 2 ( Ω ) = ∥ u h ∥ r , v ∥ v h ∥ r , v . The bounds for T 1 T_1 T 1 and T 2 T_2 T 2 , together with eq. (18) , imply eq. (16) . To prove eq. (17) , note that
∣ b r ( v h , q h ) ∣ = ∣ ∑ i = 1 s w ^ i b ( V i , Q i ) ∣ ≤ ∑ i = 1 s w ^ i 1 / 2 ∥ V i ∥ v w ^ i 1 / 2 ∥ Q i ∥ q |b_r(v_h,q_h)|=\left|\sum_{i=1}^s\widehat{w}_i b(V_i,Q_i)\right|\le\sum_{i=1}^s\widehat{w}_i^{1/2}\|V_i\|_v\,\widehat{w}_i^{1/2}\|Q_i\|_q ∣ b r ( v h , q h ) ∣ = i = 1 ∑ s w i b ( V i , Q i ) ≤ i = 1 ∑ s w i 1/2 ∥ V i ∥ v w i 1/2 ∥ Q i ∥ q ≤ ( ∑ i = 1 s w ^ i ∥ V i ∥ v 2 ) 1 / 2 ( ∑ i = 1 s w ^ i ∥ Q i ∥ q 2 ) 1 / 2 = ∥ v h ∥ r , v ∥ q h ∥ r , q , \le\left(\sum_{i=1}^s\widehat{w}_i\|V_i\|_v^2\right)^{1/2}\left(\sum_{i=1}^s\widehat{w}_i\|Q_i\|_q^2\right)^{1/2}=\|v_h\|_{r,v}\|q_h\|_{r,q}, ≤ ( i = 1 ∑ s w i ∥ V i ∥ v 2 ) 1/2 ( i = 1 ∑ s w i ∥ Q i ∥ q 2 ) 1/2 = ∥ v h ∥ r , v ∥ q h ∥ r , q , where the first inequality was proven in [26, Section 2] and the second by using the discrete Hölder’s inequality.
Discontinuous Galerkin time-stepping
We now consider DG time-stepping to discretize eq. (1) in time. In section 3.2.1 we first analyze this space-time DG+Taylor–Hood discretization. Then, in section 3.2.2, we derive a new RK time-stepping scheme that is algebraically equivalent to the space-time scheme.
Space-time discretization
On each time interval we define the space-time finite element spaces V h n : = P k t ( I n ; V h ) \mathcal{V}_h^n := \mathcal{P}_{k_t}(I_n; V_h) V h n := P k t ( I n ; V h ) and Q h n : = P k t ( I n ; Q h ) \mathcal{Q}_h^n := \mathcal{P}_{k_t}(I_n; Q_h) Q h n := P k t ( I n ; Q h ) , where P k ( I n ; X ) \mathcal{P}_k(I_n; X) P k ( I n ; X ) denotes the set of polynomials of degree k t k_t k t in time with values in X X X (see, for example, [7]). We use weighted inner products in time to define the fully discrete time-dependent Stokes problem. Weighted inner products have previously been used to define space-time discretizations in, for example, [11, 34].
Let κ n ( t ) : = exp ( − τ ( t − t n ) ) \kappa_n(t) := \exp(-\tau(t-t_n)) κ n ( t ) := exp ( − τ ( t − t n )) . The discretization is given by: For n = 0 , … , N − 1 n=0,\ldots,N-1 n = 0 , … , N − 1 , find u h n ∈ V h n u_h^n \in\mathcal{V}_h^n u h n ∈ V h n and p h n ∈ Q h n p_h^n \in\mathcal{Q}_h^n p h n ∈ Q h n such that
a ^ ( u h n , v h ) + b ^ ( v h , p h n ) − b ^ ( u h n , q h ) = ∫ I n ( f , v h ) κ n d t + ( u n − , v n + ) , (19) \widehat{a}(u_h^n,v_h)+\widehat{b}(v_h,p_h^n)-\widehat{b}(u_h^n,q_h)=\int_{I_n}(f,v_h)\kappa_n\,\mathrm{d}t+(u_n^-,v_n^+), \tag*{(19)} a ( u h n , v h ) + b ( v h , p h n ) − b ( u h n , q h ) = ∫ I n ( f , v h ) κ n d t + ( u n − , v n + ) , (19)
for all v h ∈ V h n v_h \in\mathcal{V}_h^n v h ∈ V h n and q h ∈ Q h n q_h \in\mathcal{Q}_h^n q h ∈ Q h n , where
a ^ ( u h n , v h ) : = ∫ I n ( ∂ t u h n , v h ) κ n d t + ( u n + , v n + ) + ∫ I n a ( u h n , v h ) κ n d t , \widehat{a}(u_h^n,v_h):=\int_{I_n}(\partial_tu_h^n,v_h)\kappa_n\,\mathrm{d}t+(u_n^+,v_n^+)+\int_{I_n}a(u_h^n,v_h)\kappa_n\,\mathrm{d}t, a ( u h n , v h ) := ∫ I n ( ∂ t u h n , v h ) κ n d t + ( u n + , v n + ) + ∫ I n a ( u h n , v h ) κ n d t ,
b ^ ( v h , q h ) : = ∫ I n b ( v h , q h ) κ n d t . \widehat{b}(v_h,q_h):=\int_{I_n}b(v_h,q_h)\kappa_n\,\mathrm{d}t. b ( v h , q h ) := ∫ I n b ( v h , q h ) κ n d t .
in which u n − : = u h n − 1 ( t n ) u_n^-:=u_h^{n-1}(t_n) u n − := u h n − 1 ( t n ) and u n + : = u h n ( t n ) u_n^+:=u_h^n(t_n) u n + := u h n ( t n ) . Note that if κ n ( t ) ≡ 1 \kappa_n(t)\equiv1 κ n ( t ) ≡ 1 then we recover the discretization analyzed in [7].
To show that a ^ ( ⋅ , ⋅ ) \widehat{a}(\cdot,\cdot) a ( ⋅ , ⋅ ) and b ^ ( ⋅ , ⋅ ) \widehat{b}(\cdot,\cdot) b ( ⋅ , ⋅ ) satisfy eqs. (3) and (4). We introduce the following inner products on V h n \mathcal{V}_h^n V h n and Q h n \mathcal{Q}_h^n Q h n :
( u h , v h ) v , t : = ∫ I n ( u h , v h ) v κ n d t , ( p h , q h ) q , t : = ∫ I n ( p h , q h ) q κ n d t , (u_h,v_h)_{v,t}:=\int_{I_n}(u_h,v_h)_v\kappa_n\,\mathrm{d}t,\qquad(p_h,q_h)_{q,t}:=\int_{I_n}(p_h,q_h)_q\kappa_n\,\mathrm{d}t, ( u h , v h ) v , t := ∫ I n ( u h , v h ) v κ n d t , ( p h , q h ) q , t := ∫ I n ( p h , q h ) q κ n d t ,
and denote their induced norms by ∥ ⋅ ∥ v , t \|\cdot\|_{v,t} ∥ ⋅ ∥ v , t and ∥ ⋅ ∥ q , t \|\cdot\|_{q,t} ∥ ⋅ ∥ q , t , respectively. Here ( ⋅ , ⋅ ) v (\cdot,\cdot)_v ( ⋅ , ⋅ ) v and ( ⋅ , ⋅ ) q (\cdot,\cdot)_q ( ⋅ , ⋅ ) q are defined in eq. (11) .
Lemma 4 (Coercivity). For all v h ∈ V h n v_h\in\mathcal{V}_h^n v h ∈ V h n ,
a ^ ( v h , v h ) ≥ 1 2 ∥ v h ∥ v , t 2 . \widehat{a}(v_h,v_h)\ge\frac{1}{2}\|v_h\|_{v,t}^2. a ( v h , v h ) ≥ 2 1 ∥ v h ∥ v , t 2 .
Proof. We have, using integration by parts and that κ n ′ = − τ κ n \kappa_n'=-\tau\kappa_n κ n ′ = − τ κ n ,
a ^ ( v h , v h ) = ∫ I n 1 2 d d t ∥ v h ∥ 2 κ n d t + ∥ v n + ∥ 2 + ∫ I n a ( v h , v h ) κ n d t ≥ 1 2 ∫ I n τ ∥ v h ∥ 2 κ n d t + ∫ I n ν ∥ ∇ v h ∥ 2 κ n d t , \begin{aligned}
\widehat{a}(v_h,v_h)=\int_{I_n}\frac{1}{2}\frac{\mathrm{d}}{\mathrm{d}t}\|v_h\|^2\kappa_n\,\mathrm{d}t+\|v_n^+\|^2+\int_{I_n}a(v_h,v_h)\kappa_n\,\mathrm{d}t \\
&\ge\frac{1}{2}\int_{I_n}\tau\|v_h\|^2\kappa_n\,\mathrm{d}t+\int_{I_n}\nu\|\nabla v_h\|^2\kappa_n\,\mathrm{d}t,
\end{aligned} a ( v h , v h ) = ∫ I n 2 1 d t d ∥ v h ∥ 2 κ n d t + ∥ v n + ∥ 2 + ∫ I n a ( v h , v h ) κ n d t ≥ 2 1 ∫ I n τ ∥ v h ∥ 2 κ n d t + ∫ I n ν ∥∇ v h ∥ 2 κ n d t ,
which is the desired result. □ \square □
Lemma 5 (Stability). There exists a uniform constant β > 0 \beta>0 β > 0 such that
sup v h ∈ V h b ^ ( v h , q h ) ∥ v h ∥ v , t ≥ β ∥ q h ∥ q , t ∀ q h ∈ Q h . \sup_{v_h\in V_h}\frac{\widehat{b}(v_h,q_h)}{\|v_h\|_{v,t}}\ge\beta\|q_h\|_{q,t}\qquad\forall q_h\in Q_h. v h ∈ V h sup ∥ v h ∥ v , t b ( v h , q h ) ≥ β ∥ q h ∥ q , t ∀ q h ∈ Q h .
Proof. Following the proof of [20, Theorem 3.2], we use the tensor-product structure of Q h Q_h Q h to write q h ∈ Q h q_h\in Q_h q h ∈ Q h in terms of an orthonormal basis { ϕ i } i = 0 k t \{\phi_i\}_{i=0}^{k_t} { ϕ i } i = 0 k t of P k t ( I n ) P_{k_t}(I_n) P k t ( I n ) with respect to the weighted L 2 ( I n ) L^2(I_n) L 2 ( I n ) inner product,
q h ( x , t ) = ∑ i = 0 k t ϕ i ( t ) q i ( x ) , ϕ i ∈ P k t ( I n ) , q i ∈ Q h . q_h(x,t)=\sum_{i=0}^{k_t}\phi_i(t)q_i(x),\qquad\phi_i\in P_{k_t}(I_n),\ q_i\in Q_h. q h ( x , t ) = i = 0 ∑ k t ϕ i ( t ) q i ( x ) , ϕ i ∈ P k t ( I n ) , q i ∈ Q h .
By eq. (12) , for a given q i ∈ Q h q_i \in Q_h q i ∈ Q h there exists v ~ i ∈ V h \widetilde{v}_i \in V_h v i ∈ V h such that b ( v ~ i , q i ) = ∥ q i ∥ q 2 b(\widetilde{v}_i,q_i)=\|q_i\|_q^2 b ( v i , q i ) = ∥ q i ∥ q 2 and ∥ v ~ i ∥ v ≤ β − 1 ∥ q i ∥ q \|\widetilde{v}_i\|_v \le\beta^{-1}\|q_i\|_q ∥ v i ∥ v ≤ β − 1 ∥ q i ∥ q . We now define v ~ h ( x , t ) = ∑ i = 0 k t ϕ i ( t ) v ~ i ∈ V h \widetilde{v}_h(x,t)=\sum_{i=0}^{k_t}\phi_i(t)\widetilde{v}_i \in V_h v h ( x , t ) = ∑ i = 0 k t ϕ i ( t ) v i ∈ V h . Given q h ∈ Q h q_h \in Q_h q h ∈ Q h , and that { ϕ i } \{\phi_i\} { ϕ i } is an orthonormal basis with respect to the weighted L 2 ( I n ) L^2(I_n) L 2 ( I n ) inner product, we find
∥ q h ∥ q , t 2 = ∑ i = 0 k t ∥ q i ∥ q 2 = ∑ i = 0 k t b ( v ~ i , q i ) = b ^ ( v ~ h , q h ) . (20) \|q_h\|_{q,t}^2=\sum_{i=0}^{k_t}\|q_i\|_q^2=\sum_{i=0}^{k_t}b(\widetilde{v}_i,q_i)=\widehat{b}(\widetilde{v}_h,q_h). \tag*{(20)} ∥ q h ∥ q , t 2 = i = 0 ∑ k t ∥ q i ∥ q 2 = i = 0 ∑ k t b ( v i , q i ) = b ( v h , q h ) . (20)
Likewise, we find that
∥ v ~ h ∥ v , t 2 = ∑ i = 0 k t ∥ v ~ i ∥ v 2 ≤ β − 2 ∑ i = 0 k t ∥ q i ∥ q 2 = β − 2 ∥ q h ∥ q , t 2 . (21) \|\widetilde{v}_h\|_{v,t}^2=\sum_{i=0}^{k_t}\|\widetilde{v}_i\|_v^2\le\beta^{-2}\sum_{i=0}^{k_t}\|q_i\|_q^2=\beta^{-2}\|q_h\|_{q,t}^2. \tag*{(21)} ∥ v h ∥ v , t 2 = i = 0 ∑ k t ∥ v i ∥ v 2 ≤ β − 2 i = 0 ∑ k t ∥ q i ∥ q 2 = β − 2 ∥ q h ∥ q , t 2 . (21)
The result follows from eqs. (20) and (21) .
Lemma 6 (Continuity). There exist uniform constants c a , c b > 0 c_a,c_b>0 c a , c b > 0 such that
∣ a ^ ( u h , v h ) ∣ ≤ c a ∥ u h ∥ v , t ∥ v h ∥ v , t ∀ u h , v h ∈ V h n , (22) |\widehat{a}(u_h,v_h)|\le c_a\|u_h\|_{v,t}\|v_h\|_{v,t}\qquad\forall u_h,v_h\in\mathcal{V}_h^n, \tag*{(22)} ∣ a ( u h , v h ) ∣ ≤ c a ∥ u h ∥ v , t ∥ v h ∥ v , t ∀ u h , v h ∈ V h n , (22) ∣ b ^ ( v h , q h ) ∣ ≤ c b ∥ v h ∥ v , t ∥ q h ∥ v , t ∀ v h ∈ V h n , q h ∈ Q h n . (23) |\widehat{b}(v_h,q_h)|\le c_b\|v_h\|_{v,t}\|q_h\|_{v,t}\qquad\forall v_h\in\mathcal{V}_h^n,\ q_h\in\mathcal{Q}_h^n. \tag*{(23)} ∣ b ( v h , q h ) ∣ ≤ c b ∥ v h ∥ v , t ∥ q h ∥ v , t ∀ v h ∈ V h n , q h ∈ Q h n . (23)
Proof. Using the triangle inequality,
∣ a ^ ( u h , v h ) ∣ ≤ ∣ ∫ I n ( ∂ t u h , κ n v h ) d t ∣ + ∣ ( u n + , v n + ) ∣ + ∣ ∫ I n a ( u h , v h ) κ n d t ∣ = : T 1 + T 2 + T 3 . |\widehat{a}(u_h,v_h)|\le\left|\int_{I_n}(\partial_tu_h,\kappa_nv_h)\,\mathrm{d}t\right|+\left|(u_n^+,v_n^+)\right|+\left|\int_{I_n}a(u_h,v_h)\kappa_n\,\mathrm{d}t\right|=:T_1+T_2+T_3. ∣ a ( u h , v h ) ∣ ≤ ∫ I n ( ∂ t u h , κ n v h ) d t + ( u n + , v n + ) + ∫ I n a ( u h , v h ) κ n d t =: T 1 + T 2 + T 3 .
We bound T 1 T_1 T 1 , T 2 T_2 T 2 , and T 3 T_3 T 3 separately. Note that e − 1 ≤ κ n ( t ) ≤ 1 e^{-1}\le\kappa_n(t)\le1 e − 1 ≤ κ n ( t ) ≤ 1 for t ∈ I n t\in I_n t ∈ I n . Using the Cauchy–Schwarz inequality and that ∫ I n ∥ ∂ t v h ∥ 2 d t ≤ c t τ ∫ I n ∥ v h ∥ 2 d t \int_{I_n}\|\partial_tv_h\|^2\,\mathrm{d}t\le c_t\tau\int_{I_n}\|v_h\|^2\,\mathrm{d}t ∫ I n ∥ ∂ t v h ∥ 2 d t ≤ c t τ ∫ I n ∥ v h ∥ 2 d t for all v h ∈ V h v_h\in\mathcal{V}_h v h ∈ V h , where c t > 0 c_t>0 c t > 0 is a uniform constant (see, e.g., [20, eq. (19b)]), we find
T 1 2 ≤ ∫ I n κ n ∥ ∂ t u h ∥ 2 d t ∫ I n κ n ∥ v h ∥ 2 d t ≤ c t 2 e ∫ I n τ κ n ∥ u h ∥ 2 d t ∫ I n τ κ n ∥ v h ∥ 2 d t ≤ c t 2 e ∥ u h ∥ v , t 2 ∥ v h ∥ v , t 2 . (24) \begin{aligned}
T_1^2&\le\int_{I_n}\kappa_n\|\partial_tu_h\|^2\,\mathrm{d}t\int_{I_n}\kappa_n\|v_h\|^2\,\mathrm{d}t\\
&\le c_t^2e\int_{I_n}\tau\kappa_n\|u_h\|^2\,\mathrm{d}t\int_{I_n}\tau\kappa_n\|v_h\|^2\,\mathrm{d}t\le c_t^2e\|u_h\|_{v,t}^2\|v_h\|_{v,t}^2. \tag*{(24)}
\end{aligned} T 1 2 ≤ ∫ I n κ n ∥ ∂ t u h ∥ 2 d t ∫ I n κ n ∥ v h ∥ 2 d t ≤ c t 2 e ∫ I n τ κ n ∥ u h ∥ 2 d t ∫ I n τ κ n ∥ v h ∥ 2 d t ≤ c t 2 e ∥ u h ∥ v , t 2 ∥ v h ∥ v , t 2 . (24)
Next, again using the Cauchy–Schwarz inequality but now in combination with ∥ u n + ∥ 2 ≤ c τ τ ∫ I n ∥ u h ∥ 2 d t \|u_n^+\|^2\le c_\tau\tau\int_{I_n}\|u_h\|^2\,\mathrm{d}t ∥ u n + ∥ 2 ≤ c τ τ ∫ I n ∥ u h ∥ 2 d t , which holds for all u h ∈ V h u_h\in\mathcal{V}_h u h ∈ V h and where c τ > 0 c_\tau>0 c τ > 0 is a uniform constant (see, e.g., [34, Lemma 4, eq. (17b)]),
T 2 2 ≤ ∥ u h + ∥ 2 ∥ v h + ∥ 2 ≤ c τ 2 e 2 ∫ I n τ κ n ∥ u h ∥ 2 d t ∫ I n τ κ n ∥ v h ∥ 2 d t ≤ c τ 2 e 2 ∥ u h ∥ v , t 2 ∥ v h ∥ v , t 2 . (25) T_2^2\le\|u_h^+\|^2\|v_h^+\|^2\le c_\tau^2e^2\int_{I_n}\tau\kappa_n\|u_h\|^2\,\mathrm{d}t\int_{I_n}\tau\kappa_n\|v_h\|^2\,\mathrm{d}t\le c_\tau^2e^2\|u_h\|_{v,t}^2\|v_h\|_{v,t}^2. \tag*{(25)} T 2 2 ≤ ∥ u h + ∥ 2 ∥ v h + ∥ 2 ≤ c τ 2 e 2 ∫ I n τ κ n ∥ u h ∥ 2 d t ∫ I n τ κ n ∥ v h ∥ 2 d t ≤ c τ 2 e 2 ∥ u h ∥ v , t 2 ∥ v h ∥ v , t 2 . (25)
To bound T 3 T_3 T 3 we use the Cauchy–Schwarz inequality and that ∣ a ( w h , z h ) ∣ ≤ ν ∥ ∇ w h ∥ v ∥ ∇ z h ∥ v |a(w_h,z_h)|\le\nu\|\nabla w_h\|_v\|\nabla z_h\|_v ∣ a ( w h , z h ) ∣ ≤ ν ∥∇ w h ∥ v ∥∇ z h ∥ v for all w h , z h ∈ V h w_h,z_h\in V_h w h , z h ∈ V h to find
T 3 ≤ ∫ I n κ n 1 / 2 ∥ u h ∥ v κ n 1 / 2 ∥ v h ∥ v d t ≤ ∥ u h ∥ v , t ∥ v h ∥ v , t . (26) T_3\le\int_{I_n}\kappa_n^{1/2}\|u_h\|_v\kappa_n^{1/2}\|v_h\|_v\,\mathrm{d}t\le\|u_h\|_{v,t}\|v_h\|_{v,t}. \tag*{(26)} T 3 ≤ ∫ I n κ n 1/2 ∥ u h ∥ v κ n 1/2 ∥ v h ∥ v d t ≤ ∥ u h ∥ v , t ∥ v h ∥ v , t . (26)
Equation (22) follows after combining eqs. (24) to (26) . Next, it is shown in [26, Section 2] that ∣ b ( w h , r h ) ∣ ≤ ∥ w h ∥ v ∥ r h ∥ q |b(w_h,r_h)|\le\|w_h\|_v\|r_h\|_q ∣ b ( w h , r h ) ∣ ≤ ∥ w h ∥ v ∥ r h ∥ q for all w h ∈ V h w_h\in V_h w h ∈ V h and r h ∈ Q h r_h\in Q_h r h ∈ Q h . Using also Cauchy–Schwarz, we find
∣ b ^ ( v h , q h ) ∣ ≤ ∫ I n κ n 1 / 2 ∥ v h ∥ v κ n 1 / 2 ∥ q h ∥ q d t ≤ ∥ v h ∥ v , t ∥ q h ∥ v , t , |\widehat{b}(v_h,q_h)|\le\int_{I_n}\kappa_n^{1/2}\|v_h\|_v\kappa_n^{1/2}\|q_h\|_q\,\mathrm{d}t\le\|v_h\|_{v,t}\|q_h\|_{v,t}, ∣ b ( v h , q h ) ∣ ≤ ∫ I n κ n 1/2 ∥ v h ∥ v κ n 1/2 ∥ q h ∥ q d t ≤ ∥ v h ∥ v , t ∥ q h ∥ v , t ,
proving eq. (19b).
A new RK time-stepping method
Traditional DG time-stepping methods (for which κ n = 1 \kappa_n=1 κ n = 1 ) can be written as a collocation method resulting in a Radau IIA RK method, see for example, [1 , 2 ] . The bilinear form a ~ r \widetilde{a}_r a r of the Radau IIA RK method eq. (14) , however, cannot be shown to satisfy eq. (3b). If there exists a matrix W ^ \widehat{W} W that satisfies the conditions of lemma 1, then the bilinear form a r a_r a r of the stage-weighted Radau IIA RK method eq. (15) is coercive.
An alternative to using a stage-weighted Radau IIA time discretization eq. (15) is to use an RK time discretization such that the resulting discretization is algebraically equivalent to eq. (19) . This because, as shown in § 3.2.1 , the space-time discretization eq. (19) results in bilinear forms that satisfy eqs. (3) and (4). In this section we derive this new RK method.
Let t ^ = τ ( t − t n ) ∈ [ 0 , 1 ] \hat{t}=\tau(t-t_n)\in[0,1] t ^ = τ ( t − t n ) ∈ [ 0 , 1 ] and κ ^ n ( t ^ ) = exp ( − t ^ ) \hat{\kappa}_n(\hat{t})=\exp(-\hat{t}) κ ^ n ( t ^ ) = exp ( − t ^ ) . Since ( 1 − t ^ ) κ ^ n ( t ^ ) (1-\hat{t})\hat{\kappa}_n(\hat{t}) ( 1 − t ^ ) κ ^ n ( t ^ ) is positive on ( 0 , 1 ) (0,1) ( 0 , 1 ) there exists a unique monic polynomial of degree ( s − 1 ) (s-1) ( s − 1 ) , ϕ s − 1 ( t ^ ) \phi_{s-1}(\hat{t}) ϕ s − 1 ( t ^ ) , such that
∫ 0 1 ϕ s − 1 ( t ^ ) q ( t ^ ) ( 1 − t ^ ) κ ^ n ( t ^ ) d t ^ = 0 ∀ q ∈ P s − 2 ( [ 0 , 1 ] ) . (27) \int_0^1 \phi_{s-1}(\hat{t})q(\hat{t})(1-\hat{t})\hat{\kappa}_n(\hat{t})\,\mathrm{d}\hat{t}=0 \qquad\forall q\in P_{s-2}([0,1]). \tag*{(27)} ∫ 0 1 ϕ s − 1 ( t ^ ) q ( t ^ ) ( 1 − t ^ ) κ ^ n ( t ^ ) d t ^ = 0 ∀ q ∈ P s − 2 ([ 0 , 1 ]) . (27)
For the roots of ϕ s − 1 ( t ^ ) \phi_{s-1}(\hat{t}) ϕ s − 1 ( t ^ ) , { c i , τ } i = 1 s − 1 \{c_{i,\tau}\}_{i=1}^{s-1} { c i , τ } i = 1 s − 1 , let
0 < c 1 , τ < ⋯ < c s − 1 , τ < c s , τ = 1. (28) 0<c_{1,\tau}<\cdots<c_{s-1,\tau}<c_{s,\tau}=1. \tag*{(28)} 0 < c 1 , τ < ⋯ < c s − 1 , τ < c s , τ = 1. (28)
For Lagrange basis and weights
ℓ i ( t ^ ) = ∏ j = 1 j ≠ i s t ^ − c j , τ c i , τ − c j , τ , w i = ∫ 0 1 ℓ i ( t ^ ) κ ^ n ( t ^ ) d t ^ , i = 1 , … , s , (29) \ell_i(\hat{t})=\prod_{\substack{j=1\\j\ne i}}^s\frac{\hat{t}-c_{j,\tau}}{c_{i,\tau}-c_{j,\tau}},\qquad w_i=\int_0^1\ell_i(\hat{t})\hat{\kappa}_n(\hat{t})\,\mathrm{d}\hat{t},\qquad i=1,\ldots,s, \tag*{(29)} ℓ i ( t ^ ) = j = 1 j = i ∏ s c i , τ − c j , τ t ^ − c j , τ , w i = ∫ 0 1 ℓ i ( t ^ ) κ ^ n ( t ^ ) d t ^ , i = 1 , … , s , (29)
we define a weighted Radau quadrature rule for q ∈ C ( [ 0 , 1 ] ) q\in C([0,1]) q ∈ C ([ 0 , 1 ]) by
∑ i = 1 s w i q ( c i , τ ) . (30) \sum_{i=1}^s w_iq(c_{i,\tau}). \tag*{(30)} i = 1 ∑ s w i q ( c i , τ ) . (30)
We refer to [39] for the existence of weighted Radau quadrature.
Lemma 7. For any p ∈ P 2 s − 2 ( [ 0 , 1 ] ) p\in P_{2s-2}([0,1]) p ∈ P 2 s − 2 ([ 0 , 1 ]) the quadrature rule eq. (30) satisfies
∫ 0 1 p ( t ^ ) κ ^ n ( t ^ ) d t ^ = ∑ i = 1 s w i p ( c i , τ ) ∀ p ∈ P 2 s − 2 ( [ 0 , 1 ] ) . (31) \int_0^1 p(\hat{t})\hat{\kappa}_n(\hat{t})\,\mathrm{d}\hat{t}=\sum_{i=1}^s w_ip(c_{i,\tau})\qquad\forall p\in P_{2s-2}([0,1]). \tag*{(31)} ∫ 0 1 p ( t ^ ) κ ^ n ( t ^ ) d t ^ = i = 1 ∑ s w i p ( c i , τ ) ∀ p ∈ P 2 s − 2 ([ 0 , 1 ]) . (31) Furthermore, w i > 0 w_i>0 w i > 0 for i = 1 , … , s i=1,\ldots,s i = 1 , … , s .
Proof. Any v ∈ P s − 1 ( [ 0 , 1 ] ) v\in P_{s-1}([0,1]) v ∈ P s − 1 ([ 0 , 1 ]) can be written in terms of the Lagrange basis:
v ( t ^ ) = ∑ i = 1 s v ( c i , τ ) ℓ i ( t ^ ) . (32) v(\hat{t})=\sum_{i=1}^s v(c_{i,\tau})\ell_i(\hat{t}). \tag*{(32)} v ( t ^ ) = i = 1 ∑ s v ( c i , τ ) ℓ i ( t ^ ) . (32)
Multiplying eq. (32) by κ ^ n \hat{\kappa}_n κ ^ n and integrating proves that the quadrature formula and the integral coincide for v v v .
There exist polynomials q ∈ P s − 2 ( [ 0 , 1 ] ) q\in P_{s-2}([0,1]) q ∈ P s − 2 ([ 0 , 1 ]) and v ∈ P s − 1 ( [ 0 , 1 ] ) v\in P_{s-1}([0,1]) v ∈ P s − 1 ([ 0 , 1 ]) such that a given p ∈ P 2 s − 2 ( [ 0 , 1 ] ) p\in P_{2s-2}([0,1]) p ∈ P 2 s − 2 ([ 0 , 1 ]) can be written as
p ( t ^ ) = ( t ^ − 1 ) ϕ s − 1 ( t ^ ) q ( t ^ ) + v ( t ^ ) . (33) p(\hat{t})=(\hat{t}-1)\phi_{s-1}(\hat{t})q(\hat{t})+v(\hat{t}). \tag*{(33)} p ( t ^ ) = ( t ^ − 1 ) ϕ s − 1 ( t ^ ) q ( t ^ ) + v ( t ^ ) . (33)
Using orthogonality of ϕ s − 1 \phi_{s-1} ϕ s − 1 (see eq. (27) ), applying the exact integration of the quadrature formula when applied to v v v , and that the values of v v v and p p p agree at every quadrature node (because the first term of eq. (33) vanishes at the roots of ϕ s − 1 \phi_{s-1} ϕ s − 1 and at 1 1 1 ), gives
∫ 0 1 p ( t ^ ) κ ^ n ( t ^ ) d t ^ = ∫ 0 1 v ( t ^ ) κ ^ n ( t ^ ) d t ^ = ∑ i = 1 s w i v ( c i , τ ) = ∑ i = 1 s w i p ( c i , τ ) , \int_0^1 p(\hat{t})\hat{\kappa}_n(\hat{t})\,\mathrm{d}\hat{t}=\int_0^1 v(\hat{t})\hat{\kappa}_n(\hat{t})\,\mathrm{d}\hat{t}=\sum_{i=1}^s w_iv(c_{i,\tau})=\sum_{i=1}^s w_ip(c_{i,\tau}), ∫ 0 1 p ( t ^ ) κ ^ n ( t ^ ) d t ^ = ∫ 0 1 v ( t ^ ) κ ^ n ( t ^ ) d t ^ = i = 1 ∑ s w i v ( c i , τ ) = i = 1 ∑ s w i p ( c i , τ ) ,
which proves eq. (31) . That w i > 0 w_i > 0 w i > 0 , i = 1 , … , s i = 1, \ldots, s i = 1 , … , s , follows from this exact integration because ∫ 0 1 ℓ i ( t ^ ) 2 κ ^ n ( t ^ ) d t ^ = ∑ j = 1 s w j ℓ i ( c j , τ ) 2 = w i \int_0^1 \ell_i(\hat{t})^2\hat{\kappa}_n(\hat{t})\,\mathrm{d}\hat{t} = \sum_{j=1}^s w_j\ell_i(c_{j,\tau})^2 = w_i ∫ 0 1 ℓ i ( t ^ ) 2 κ ^ n ( t ^ ) d t ^ = ∑ j = 1 s w j ℓ i ( c j , τ ) 2 = w i .
Lemma 8. For 1 ≤ i , j ≤ s 1 \le i,j \le s 1 ≤ i , j ≤ s , s ≥ 2 s \ge2 s ≥ 2 , let
D i j : = ℓ j ′ ( c i , τ ) , d i : = ℓ i ( 0 ) , W : = diag ( w 1 , … , w s ) , H : = W D + d d T (34) D_{ij} := \ell_j'(c_{i,\tau}), \qquad d_i := \ell_i(0), \qquad W := \operatorname{diag}(w_1,\ldots,w_s), \qquad H := WD + dd^T \tag*{(34)} D ij := ℓ j ′ ( c i , τ ) , d i := ℓ i ( 0 ) , W := diag ( w 1 , … , w s ) , H := W D + d d T (34) where the prime in the definition of D i j D_{ij} D ij denotes differentiation with respect to t ^ \hat{t} t ^ . Then, H H H is invertible and the following hold:
H 1 = d , H − 1 W 1 = c τ , e s T H − 1 W 1 = 1 , (35) H\mathbf{1} = d, \qquad H^{-1}W\mathbf{1} = c_\tau, \qquad e_s^T H^{-1}W\mathbf{1} = 1, \tag*{(35)} H 1 = d , H − 1 W 1 = c τ , e s T H − 1 W 1 = 1 , (35) where 1 = ( 1 , … , 1 ) T ∈ R s \mathbf{1} = (1,\ldots,1)^T \in\mathbb{R}^s 1 = ( 1 , … , 1 ) T ∈ R s , e s = ( 0 , … , 0 , 1 ) T e_s = (0,\ldots,0,1)^T e s = ( 0 , … , 0 , 1 ) T , c τ = ( c 1 , τ , … , c s , τ ) T c_\tau= (c_{1,\tau},\ldots,c_{s,\tau})^T c τ = ( c 1 , τ , … , c s , τ ) T .
Proof. We first show that H H H is invertible by showing that if z ∈ R s z \in\mathbb{R}^s z ∈ R s is such that H z = 0 Hz = 0 H z = 0 , then z = 0 z = 0 z = 0 . For z ∈ R s z \in\mathbb{R}^s z ∈ R s set p z ( t ^ ) = ∑ j = 1 s z j ℓ j ( t ^ ) ∈ P s − 1 ( [ 0 , 1 ] ) p_z(\hat{t}) = \sum_{j=1}^s z_j\ell_j(\hat{t}) \in\mathcal{P}_{s-1}([0,1]) p z ( t ^ ) = ∑ j = 1 s z j ℓ j ( t ^ ) ∈ P s − 1 ([ 0 , 1 ]) . Then,
∫ 0 1 κ ^ n p z ′ ( t ^ ) ℓ i ( t ^ ) d t ^ + p z ( 0 ) ℓ i ( 0 ) = ∑ k = 1 s w k [ ∑ j = 1 s z j ℓ j ′ ( c k , τ ) ℓ i ( c k , τ ) ] + ℓ i ( 0 ) ∑ j = 1 s z j ℓ j ( 0 ) (by xref‘eq. (27) ) = ∑ k = 1 s w k [ ℓ i ( c k , τ ) ∑ j = 1 s D k j z j ] + d i d T z (by xref‘eq. (30) ) = w i ( D z ) i + d i d T z (by xref‘eq. (30) and ℓ i ( c k , τ ) = δ i k ) = ( H z ) i . (by xref‘eq. (30) ) \begin{aligned}
\int_0^1 \hat{\kappa}_n p_z'(\hat{t})\ell_i(\hat{t})\,\mathrm{d}\hat{t} + p_z(0)\ell_i(0) \\
&= \sum_{k=1}^s w_k\left[\sum_{j=1}^s z_j\ell_j'(c_{k,\tau})\ell_i(c_{k,\tau})\right] + \ell_i(0)\sum_{j=1}^s z_j\ell_j(0) \qquad\text{(by {xref}`eq. (27)}) \\
&= \sum_{k=1}^s w_k\left[\ell_i(c_{k,\tau})\sum_{j=1}^s D_{kj}z_j\right] + d_i d^Tz \qquad\text{(by {xref}`eq. (30)}) \\
&= w_i(Dz)_i + d_i d^Tz \qquad\text{(by {xref}`eq. (30) and } \ell_i(c_{k,\tau}) = \delta_{ik}\text{)} \\
&= (Hz)_i. \qquad\text{(by {xref}`eq. (30)})
\end{aligned} ∫ 0 1 κ ^ n p z ′ ( t ^ ) ℓ i ( t ^ ) d t ^ + p z ( 0 ) ℓ i ( 0 ) = k = 1 ∑ s w k [ j = 1 ∑ s z j ℓ j ′ ( c k , τ ) ℓ i ( c k , τ ) ] + ℓ i ( 0 ) j = 1 ∑ s z j ℓ j ( 0 ) (by xref ‘eq. (27) ) = k = 1 ∑ s w k [ ℓ i ( c k , τ ) j = 1 ∑ s D k j z j ] + d i d T z (by xref ‘eq. (30) ) = w i ( D z ) i + d i d T z (by xref ‘eq. (30) and ℓ i ( c k , τ ) = δ ik ) = ( H z ) i . (by xref ‘eq. (30) )
Suppose now that H z = 0 Hz = 0 H z = 0 for some z ∈ R s z \in\mathbb{R}^s z ∈ R s . Since any v ∈ P s − 1 ( [ 0 , 1 ] ) v \in\mathcal{P}_{s-1}([0,1]) v ∈ P s − 1 ([ 0 , 1 ]) can be written as a linear combination of ℓ i \ell_i ℓ i 's, the above identity gives
∫ 0 1 κ ^ n ( t ^ ) p z ′ ( t ^ ) v ( t ^ ) d t ^ + p z ( 0 ) v ( 0 ) = 0 ∀ v ∈ P s − 1 ( [ 0 , 1 ] ) . \int_0^1 \hat{\kappa}_n(\hat{t})p_z'(\hat{t})v(\hat{t})\,\mathrm{d}\hat{t} + p_z(0)v(0) = 0 \qquad\forall v \in\mathcal{P}_{s-1}([0,1]). ∫ 0 1 κ ^ n ( t ^ ) p z ′ ( t ^ ) v ( t ^ ) d t ^ + p z ( 0 ) v ( 0 ) = 0 ∀ v ∈ P s − 1 ([ 0 , 1 ]) .
Choosing v ( t ^ ) = t ^ p z ′ ( t ^ ) ∈ P s − 1 ( [ 0 , 1 ] ) v(\hat{t}) = \hat{t}p_z'(\hat{t}) \in\mathcal{P}_{s-1}([0,1]) v ( t ^ ) = t ^ p z ′ ( t ^ ) ∈ P s − 1 ([ 0 , 1 ]) implies ∫ 0 1 t ^ κ ^ n ( t ^ ) ∣ p z ′ ( t ^ ) ∣ 2 d t ^ = 0 \int_0^1 \hat{t}\hat{\kappa}_n(\hat{t})\lvert p_z'(\hat{t})\rvert^2\,\mathrm{d}\hat{t} = 0 ∫ 0 1 t ^ κ ^ n ( t ^ ) ∣ p z ′ ( t ^ ) ∣ 2 d t ^ = 0 , and so p z ′ ≡ 0 p_z' \equiv0 p z ′ ≡ 0 . Moreover, choosing v ( t ^ ) ≡ 1 v(\hat{t}) \equiv1 v ( t ^ ) ≡ 1 implies p z ( 0 ) = 0 p_z(0) = 0 p z ( 0 ) = 0 , and so p z ≡ 0 p_z \equiv0 p z ≡ 0 . Therefore, z = 0 ∈ R s z = 0 \in\mathbb{R}^s z = 0 ∈ R s because z i = p z ( c i , τ ) z_i = p_z(c_{i,\tau}) z i = p z ( c i , τ ) .
We now show the identities in eq. (35) . Note that Lagrange interpolation of the constant function 1 1 1 and t ^ \hat{t} t ^ gives
∑ j = 1 s ℓ j ( t ^ ) = 1 , ∑ j = 1 s c j , τ ℓ j ( t ^ ) = t ^ . \sum_{j=1}^s \ell_j(\hat{t}) = 1, \qquad\sum_{j=1}^s c_{j,\tau}\ell_j(\hat{t}) = \hat{t}. j = 1 ∑ s ℓ j ( t ^ ) = 1 , j = 1 ∑ s c j , τ ℓ j ( t ^ ) = t ^ .
Differentiating these identities and evaluating at the nodes, and also evaluating them at t ^ = 0 \hat{t} = 0 t ^ = 0 , yields
D 1 = 0 , d T 1 = 1 , D c τ = 1 , d T c τ = 0. D\mathbf{1} = 0, \qquad d^T\mathbf{1} = 1, \qquad Dc_\tau= \mathbf{1}, \qquad d^Tc_\tau= 0. D 1 = 0 , d T 1 = 1 , D c τ = 1 , d T c τ = 0.
From these identities and the definition of H H H ,
H 1 = d , H c τ = W 1 , H\mathbf{1} = d, \qquad Hc_\tau= W\mathbf{1}, H 1 = d , H c τ = W 1 ,
from which the first and second identity in eq. (35) follow. The third identity follows from e s T H − 1 W 1 = e s T c τ = 1 e_s^T H^{-1}W\mathbf{1} = e_s^Tc_\tau= 1 e s T H − 1 W 1 = e s T c τ = 1 , since c s , τ = 1 c_{s,\tau} = 1 c s , τ = 1 .
Lemma 9. Let s = k t + 1 ≥ 2 s=k_t+1\ge2 s = k t + 1 ≥ 2 , t n , k = t n + c k , τ Δ t t_{n,k}=t_n+c_{k,\tau}\Delta t t n , k = t n + c k , τ Δ t with quadrature nodes 0 < c 1 , τ < ⋯ < c s − 1 , τ < c s , τ = 1 0<c_{1,\tau}<\cdots<c_{s-1,\tau}<c_{s,\tau}=1 0 < c 1 , τ < ⋯ < c s − 1 , τ < c s , τ = 1 as given by eq. (28) . Let A = [ a i j ] = H − 1 W A=[a_{ij}]=H^{-1}W A = [ a ij ] = H − 1 W . The space-time discretization eq. (19) of the time-dependent Stokes equations is equivalent to using RK time-stepping with Butcher tableau
\begin{array}{c|c}
c_\tau& A\\
\hline
& e_s^T A
\end{array},
\qquad e_s=(0,\ldots,0,1)^T\in\mathbb{R}^s, \tag*{(36)}\end{array}
if
∫ I n κ n ( t ) ( f ( t ) , v h n ( t ) ) d t = Δ t ∑ i = 1 s w i ( f ( t n , i ) , v h n ( t n , i ) ) ∀ v h n ∈ V h n . (37) \int_{I_n}\kappa_n(t)(f(t),v_h^n(t))\,\mathrm{d}t=\Delta t\sum_{i=1}^{s}w_i(f(t_{n,i}),v_h^n(t_{n,i}))\quad\forall v_h^n\in V_h^n. \tag*{(37)} ∫ I n κ n ( t ) ( f ( t ) , v h n ( t )) d t = Δ t i = 1 ∑ s w i ( f ( t n , i ) , v h n ( t n , i )) ∀ v h n ∈ V h n . (37)
Proof of lemma 9. Let t n , i : = t n + c i , τ Δ t t_{n,i}:=t_n+c_{i,\tau}\Delta t t n , i := t n + c i , τ Δ t and write the Lagrange expansion of u h n , p h n u_h^n,p_h^n u h n , p h n on the physical slab as
u h n ( t ) = ∑ j = 1 s U j ℓ j ( t ^ ) , p h n ( t ) = ∑ j = 1 s P j ℓ j ( t ^ ) , t ^ = t − t n Δ t (38) u_h^n(t)=\sum_{j=1}^{s}U_j\ell_j(\hat{t}),\qquad p_h^n(t)=\sum_{j=1}^{s}P_j\ell_j(\hat{t}),\qquad\hat{t}=\frac{t-t_n}{\Delta t} \tag*{(38)} u h n ( t ) = j = 1 ∑ s U j ℓ j ( t ^ ) , p h n ( t ) = j = 1 ∑ s P j ℓ j ( t ^ ) , t ^ = Δ t t − t n (38)
where U j ∈ V h U_j\in V_h U j ∈ V h , P j ∈ Q h P_j\in Q_h P j ∈ Q h . Suppose that ( U j , P j ) j = 1 s (U_j,P_j)_{j=1}^{s} ( U j , P j ) j = 1 s are obtained by the DG method. It follows that
∂ t u h n ( t n , i ) = 1 Δ t ∑ j = 1 s D i j U j , u n + = ∑ j = 1 s d j U j . (39) \partial_tu_h^n(t_{n,i})=\frac{1}{\Delta t}\sum_{j=1}^{s}D_{ij}U_j,\qquad u_n^+=\sum_{j=1}^{s}d_jU_j. \tag*{(39)} ∂ t u h n ( t n , i ) = Δ t 1 j = 1 ∑ s D ij U j , u n + = j = 1 ∑ s d j U j . (39)
In eq. (19) , fix v h ∈ V h v_h\in V_h v h ∈ V h , q h ∈ Q h q_h\in Q_h q h ∈ Q h , and use the time-dependent test function v h ℓ i ( t ^ ) v_h\ell_i(\hat{t}) v h ℓ i ( t ^ ) , q h ℓ i ( t ^ ) q_h\ell_i(\hat{t}) q h ℓ i ( t ^ ) . The time derivative product has temporal degree at most ( s − 2 ) + ( s − 1 ) = 2 s − 3 (s-2)+(s-1)=2s-3 ( s − 2 ) + ( s − 1 ) = 2 s − 3 , and the velocity and pressure products have temporal degree at most 2 s − 2 2s-2 2 s − 2 . Thus all integrals on I n I_n I n are evaluated exactly by the weighted quadrature given in eq. (30) . More specifically, applying the weighted quadrature rule to the derivative term gives
∫ I n κ n ( t ) ( ∂ t u h n ( t ) , v h ) ℓ i ( t ^ ) d t = Δ t ∑ k = 1 s w k ( ∂ t u h n ( t n , k ) , v h ) ℓ i ( c k , τ ) = w i ∑ j = 1 s D i j ( U j , v h ) (by xref‘eq. (35)‘ and ℓ i ( c k , τ ) = δ i k ). \begin{aligned}
\int_{I_n}\kappa_n(t)(\partial_tu_h^n(t),v_h)\ell_i(\hat{t})\,\mathrm{d}t
&=\Delta t\sum_{k=1}^{s}w_k(\partial_tu_h^n(t_{n,k}),v_h)\ell_i(c_{k,\tau})\\
&=w_i\sum_{j=1}^{s}D_{ij}(U_j,v_h)\quad\text{(by {xref}`eq. (35)` and }\ell_i(c_{k,\tau})=\delta_{ik}\text{).}
\end{aligned} ∫ I n κ n ( t ) ( ∂ t u h n ( t ) , v h ) ℓ i ( t ^ ) d t = Δ t k = 1 ∑ s w k ( ∂ t u h n ( t n , k ) , v h ) ℓ i ( c k , τ ) = w i j = 1 ∑ s D ij ( U j , v h ) (by xref ‘eq. (35)‘ and ℓ i ( c k , τ ) = δ ik ).
The term corresponding to ( u n + , v n + ) (u_n^+,v_n^+) ( u n + , v n + ) can be written as d i ∑ j = 1 s d j ( U j , v h ) d_i\sum_{j=1}^{s}d_j(U_j,v_h) d i ∑ j = 1 s d j ( U j , v h ) . Applying the weighted quadrature to eq. (19) therefore results in
∑ j = 1 s H i j ( U j , v h ) + Δ t w i [ a ( U i , v h ) + b ( v h , P i ) + b ( U i , q h ) ] = d i ( u n − , v h ) + Δ t w i ( f ( t n , i ) , v h ) , i = 1 , … , s . (40) \sum_{j=1}^{s}H_{ij}(U_j,v_h)+\Delta tw_i\left[a(U_i,v_h)+b(v_h,P_i)+b(U_i,q_h)\right]
=d_i(u_n^-,v_h)+\Delta tw_i(f(t_{n,i}),v_h),\qquad i=1,\ldots,s. \tag*{(40)} j = 1 ∑ s H ij ( U j , v h ) + Δ t w i [ a ( U i , v h ) + b ( v h , P i ) + b ( U i , q h ) ] = d i ( u n − , v h ) + Δ t w i ( f ( t n , i ) , v h ) , i = 1 , … , s . (40)
If v h = 0 v_h=0 v h = 0 , then b ( U i , q h ) = 0 b(U_i,q_h)=0 b ( U i , q h ) = 0 for all q h ∈ Q h q_h\in Q_h q h ∈ Q h because Δ t w i b ( U i , q h ) = 0 \Delta tw_ib(U_i,q_h)=0 Δ t w i b ( U i , q h ) = 0 and w i > 0 w_i>0 w i > 0 . If we multiply eq. (40) for i = 1 , … , s i=1,\ldots,s i = 1 , … , s by H − 1 H^{-1} H − 1 in the stage index, use that H − 1 d = 1 H^{-1}d=1 H − 1 d = 1 , H − 1 W = A H^{-1}W=A H − 1 W = A , and define K j ∈ V h K_j\in V_h K j ∈ V h by
( K j , v h ) = ( f ( t n , j ) , v h ) − a ( U j , v h ) − b ( v h , P j ) ∀ v h ∈ V h , (K_j,v_h)=(f(t_{n,j}),v_h)-a(U_j,v_h)-b(v_h,P_j)\qquad\forall v_h\in V_h, ( K j , v h ) = ( f ( t n , j ) , v h ) − a ( U j , v h ) − b ( v h , P j ) ∀ v h ∈ V h ,
we find that U i = u n − + Δ t ∑ j = 1 s a i j K j U_i=u_n^-+\Delta t\sum_{j=1}^{s}a_{ij}K_j U i = u n − + Δ t ∑ j = 1 s a ij K j . In particular, U s = u h n ( t n + 1 ) = u n − + Δ t ∑ j = 1 s a s j K j U_s=u_h^n(t_{n+1})=u_n^-+\Delta t\sum_{j=1}^{s}a_{sj}K_j U s = u h n ( t n + 1 ) = u n − + Δ t ∑ j = 1 s a s j K j . By recalling that the last row of the Butcher tableau is e s T A e_s^TA e s T A , u h n ( t n + 1 ) u_h^n(t_{n+1}) u h n ( t n + 1 ) is the solution of the RK method. Conversely, let ( U i , P i ) i = 1 s (U_i,P_i)_{i=1}^{s} ( U i , P i ) i = 1 s satisfy the RK stage equations and reconstruct u h n u_h^n u h n and p h n p_h^n p h n by eq. (38) . Multiplying the stage momentum equations by H H H , and using H 1 = d H1=d H 1 = d and H A = W HA=W H A = W , recovers the momentum part of eq. (40) . The stage constraints give its remaining part. By exactness of the weighted quadrature and the assumption eq. (37) , these are the DG equations tested with v h ℓ i v_h\ell_i v h ℓ i and q h ℓ i q_h\ell_i q h ℓ i . Since these test functions span the DG test spaces, the reconstructed pair solves the DG problem. ◻
As proven in lemma 9 we can write eq. (19) as eq. (40) . Using the notation f i ( x ) = f ( x , t n , i ) f_i(x)=f(x,t_{n,i}) f i ( x ) = f ( x , t n , i ) , that w i − 1 H i j = ( W − 1 H ) i j = ( A − 1 ) i j w_i^{-1}H_{ij}=(W^{-1}H)_{ij}=(A^{-1})_{ij} w i − 1 H ij = ( W − 1 H ) ij = ( A − 1 ) ij and, thanks to eq. (35) , w i − 1 d i = ( W − 1 d ) i = ( W − 1 H 1 ) i = ( A − 1 1 ) i w_i^{-1}d_i=(W^{-1}d)_i=(W^{-1}H\mathbf{1})_i=(A^{-1}\mathbf{1})_i w i − 1 d i = ( W − 1 d ) i = ( W − 1 H 1 ) i = ( A − 1 1 ) i , we can write eq. (40) as:
w i ∑ j = 1 s ( A − 1 ) i j ( U j , v h ) + w i [ a ( U i , v h ) + b ( v h , P i ) + b ( U i , q h ) ] = τ w i ( A − 1 1 ) i ( u n − , v h ) + w i ( f i , v h ) , i = 1 , … , s . w_i\sum_{j=1}^{s}(A^{-1})_{ij}(U_j,v_h)+w_i\left[a(U_i,v_h)+b(v_h,P_i)+b(U_i,q_h)\right]
=\tau w_i(A^{-1}\mathbf{1})_i(u_n^-,v_h)+w_i(f_i,v_h),\qquad i=1,\ldots,s. w i j = 1 ∑ s ( A − 1 ) ij ( U j , v h ) + w i [ a ( U i , v h ) + b ( v h , P i ) + b ( U i , q h ) ] = τ w i ( A − 1 1 ) i ( u n − , v h ) + w i ( f i , v h ) , i = 1 , … , s .
Advancing from t n t_n t n to t n + 1 t_{n+1} t n + 1 we consider the following fully discrete problem: find u h : = ( U 1 , … , U s ) ∈ V h \mathbf{u}_h:=(U_1,\ldots,U_s)\in\mathbf{V}_h u h := ( U 1 , … , U s ) ∈ V h and p h : = ( P 1 , … , P s ) ∈ Q h \mathbf{p}_h:=(P_1,\ldots,P_s)\in\mathbf{Q}_h p h := ( P 1 , … , P s ) ∈ Q h such that
a ( u h , v h ) + b ( v h , p h ) − b ( u h , q h ) = ∑ i = 1 s w i [ ( f i , V i ) + τ ∑ j = 1 s ( A − 1 ) i j ( u n − , V i ) ] , (41) a(\mathbf{u}_h,\mathbf{v}_h)+b(\mathbf{v}_h,\mathbf{p}_h)-b(\mathbf{u}_h,\mathbf{q}_h)=\sum_{i=1}^{s}w_i\left[(f_i,V_i)+\tau\sum_{j=1}^{s}(A^{-1})_{ij}(u_n^-,V_i)\right], \tag*{(41)} a ( u h , v h ) + b ( v h , p h ) − b ( u h , q h ) = i = 1 ∑ s w i [ ( f i , V i ) + τ j = 1 ∑ s ( A − 1 ) ij ( u n − , V i ) ] , (41)
for all v h : = ( V 1 , … , V s ) ∈ V h \mathbf{v}_h:=(V_1,\ldots,V_s)\in\mathbf{V}_h v h := ( V 1 , … , V s ) ∈ V h and q h : = ( Q 1 , … , Q s ) ∈ Q h \mathbf{q}_h:=(Q_1,\ldots,Q_s)\in\mathbf{Q}_h q h := ( Q 1 , … , Q s ) ∈ Q h , in which
a ( u h , v h ) : = ∑ i = 1 s w i [ τ ∑ j = 1 s ( A − 1 ) i j ( U j , V i ) + a ( U i , V i ) ] , b ( v h , p h ) : = ∑ i = 1 s w i b ( V i , P i ) . a(\mathbf{u}_h,\mathbf{v}_h):=\sum_{i=1}^{s}w_i\left[\tau\sum_{j=1}^{s}(A^{-1})_{ij}(U_j,V_i)+a(U_i,V_i)\right],\qquad b(\mathbf{v}_h,\mathbf{p}_h):=\sum_{i=1}^{s}w_i b(V_i,P_i). a ( u h , v h ) := i = 1 ∑ s w i [ τ j = 1 ∑ s ( A − 1 ) ij ( U j , V i ) + a ( U i , V i ) ] , b ( v h , p h ) := i = 1 ∑ s w i b ( V i , P i ) .
We will show that a ( ⋅ , ⋅ ) a(\cdot,\cdot) a ( ⋅ , ⋅ ) and b ( ⋅ , ⋅ ) b(\cdot,\cdot) b ( ⋅ , ⋅ ) satisfy eqs. (3) and (4). We introduce the following inner products associated with V h \mathbf{V}_h V h and Q h \mathbf{Q}_h Q h :
( u h , v h ) v : = ∑ i = 1 s w i ( U i , V i ) v , ( p h , q h ) q : = ∑ i = 1 s w i ( P i , Q i ) q , (\mathbf{u}_h,\mathbf{v}_h)_v:=\sum_{i=1}^{s}w_i(U_i,V_i)_v,\qquad(\mathbf{p}_h,\mathbf{q}_h)_q:=\sum_{i=1}^{s}w_i(P_i,Q_i)_q, ( u h , v h ) v := i = 1 ∑ s w i ( U i , V i ) v , ( p h , q h ) q := i = 1 ∑ s w i ( P i , Q i ) q ,
respectively, with induced norms denoted by ∥ ⋅ ∥ v \|\cdot\|_v ∥ ⋅ ∥ v and ∥ ⋅ ∥ q \|\cdot\|_q ∥ ⋅ ∥ q . Here ( ⋅ , ⋅ ) v (\cdot,\cdot)_v ( ⋅ , ⋅ ) v and ( ⋅ , ⋅ ) q (\cdot,\cdot)_q ( ⋅ , ⋅ ) q are defined in eq. (11) .
Proving stability of b b b and continuity of a a a and b b b follows identical steps as used to prove lemmas 2 and 3. The following lemma will be used to show coercivity of a ( ⋅ , ⋅ ) a(\cdot,\cdot) a ( ⋅ , ⋅ ) .
Lemma 10. Suppose that A A A is the Butcher tableau defined in lemma 9. Let W W W be defined in eq. (34) . Then 1 2 ( W A − 1 + ( W A − 1 ) T ) \frac{1}{2}(WA^{-1}+(WA^{-1})^T) 2 1 ( W A − 1 + ( W A − 1 ) T ) is symmetric positive definite.
Proof. Recall that A = H − 1 W A=H^{-1}W A = H − 1 W , so 1 2 ( W A − 1 + ( W A − 1 ) T ) = 1 2 ( H + H T ) \frac{1}{2}(WA^{-1}+(WA^{-1})^T)=\frac{1}{2}(H+H^T) 2 1 ( W A − 1 + ( W A − 1 ) T ) = 2 1 ( H + H T ) . We show that H + H T H+H^T H + H T is symmetric positive definite. From eq. (34) and the exact integration of the quadrature rule,
( W D ) i j = w i ℓ j ′ ( c i , τ ) = ∑ k = 1 s w k ℓ i ( c k , τ ) ℓ j ′ ( c k , τ ) ( ∵ ℓ i ( c k , τ ) = δ i k ) = ∫ 0 1 κ ^ n ( t ^ ) ℓ i ( t ^ ) ℓ j ′ ( t ^ ) d t ^ . \begin{aligned}
(WD)_{ij}=w_i\ell_j'(c_i,\tau)=\sum_{k=1}^{s}w_k\ell_i(c_k,\tau)\ell_j'(c_k,\tau)\quad(\because\ \ell_i(c_k,\tau)=\delta_{ik}) \\
&=\int_0^1\widehat{\kappa}_n(\widehat{t})\ell_i(\widehat{t})\ell_j'(\widehat{t})\,\mathrm{d}\widehat{t}.
\end{aligned} ( W D ) ij = w i ℓ j ′ ( c i , τ ) = k = 1 ∑ s w k ℓ i ( c k , τ ) ℓ j ′ ( c k , τ ) ( ∵ ℓ i ( c k , τ ) = δ ik ) = ∫ 0 1 κ n ( t ) ℓ i ( t ) ℓ j ′ ( t ) d t .
Then,
( W D + D T W ) i j = ∫ 0 1 κ ^ n ( t ^ ) [ ℓ i ( t ^ ) ℓ j ′ ( t ^ ) + ℓ j ( t ^ ) ℓ i ′ ( t ^ ) ] d t ^ = ∫ 0 1 κ ^ n ( t ^ ) ( ℓ i ( t ^ ) ℓ j ( t ^ ) ) ′ d t ^ . (WD+D^TW)_{ij}=\int_0^1\widehat{\kappa}_n(\widehat{t})\left[\ell_i(\widehat{t})\ell_j'(\widehat{t})+\ell_j(\widehat{t})\ell_i'(\widehat{t})\right]\,\mathrm{d}\widehat{t}
=\int_0^1\widehat{\kappa}_n(\widehat{t})\left(\ell_i(\widehat{t})\ell_j(\widehat{t})\right)'\,\mathrm{d}\widehat{t}. ( W D + D T W ) ij = ∫ 0 1 κ n ( t ) [ ℓ i ( t ) ℓ j ′ ( t ) + ℓ j ( t ) ℓ i ′ ( t ) ] d t = ∫ 0 1 κ n ( t ) ( ℓ i ( t ) ℓ j ( t ) ) ′ d t .
By the integration by parts and κ ^ n ′ ( t ^ ) = − κ ^ n ( t ^ ) \widehat{\kappa}_n'(\widehat{t})=-\widehat{\kappa}_n(\widehat{t}) κ n ′ ( t ) = − κ n ( t ) ,
( W D + D T W ) i j = ( κ ^ n ℓ i ℓ j ) ∣ 0 1 + ∫ 0 1 κ ^ n ( t ^ ) ℓ i ( t ^ ) ℓ j ( t ^ ) d t ^ = e − 1 ℓ i ( 1 ) ℓ j ( 1 ) − ℓ i ( 0 ) ℓ j ( 0 ) + ∫ 0 1 κ ^ n ( t ^ ) ℓ i ( t ^ ) ℓ j ( t ^ ) d t ^ . \begin{aligned}
(WD+D^TW)_{ij}=(\widehat{\kappa}_n\ell_i\ell_j)\big|_0^1+\int_0^1\widehat{\kappa}_n(\widehat{t})\ell_i(\widehat{t})\ell_j(\widehat{t})\,\mathrm{d}\widehat{t} \\
&=e^{-1}\ell_i(1)\ell_j(1)-\ell_i(0)\ell_j(0)+\int_0^1\widehat{\kappa}_n(\widehat{t})\ell_i(\widehat{t})\ell_j(\widehat{t})\,\mathrm{d}\widehat{t}.
\end{aligned} ( W D + D T W ) ij = ( κ n ℓ i ℓ j ) 0 1 + ∫ 0 1 κ n ( t ) ℓ i ( t ) ℓ j ( t ) d t = e − 1 ℓ i ( 1 ) ℓ j ( 1 ) − ℓ i ( 0 ) ℓ j ( 0 ) + ∫ 0 1 κ n ( t ) ℓ i ( t ) ℓ j ( t ) d t .
Applying the quadrature rule to the last integral, a matrix form of this identity is
W D + D T W = e − 1 e s e s T − d d T + W . WD+D^TW=e^{-1}e_se_s^T-dd^T+W. W D + D T W = e − 1 e s e s T − d d T + W .
The result follows by
H + H T = ( W D + d d T ) + ( D T W + d d T ) = d d T + e − 1 e s e s T + W . H + H^{T} = (WD + dd^{T}) + (D^{T}W + dd^{T}) = dd^{T} + e^{-1}e_{s}e_{s}^{T} + W. H + H T = ( W D + d d T ) + ( D T W + d d T ) = d d T + e − 1 e s e s T + W .
Lemma 11 (Coercivity). There exists a uniform constant α > 0 \alpha> 0 α > 0 such that
a ( v h , v h ) ≥ α ∥ v h ∥ v 2 ∀ v h ∈ V h . a(v_h,v_h) \ge\alpha\lVert v_h\rVert_{v}^{2} \qquad\forall v_h \in V_h. a ( v h , v h ) ≥ α ∥ v h ∥ v 2 ∀ v h ∈ V h .
Proof. Since C = 1 2 ( W A − 1 + ( W A − 1 ) T ) C = \frac{1}{2}(WA^{-1} + (WA^{-1})^{T}) C = 2 1 ( W A − 1 + ( W A − 1 ) T ) is symmetric positive definite by lemma 10, the proof follows the same steps as that of lemma 1.
Preconditioning
Let u , v \mathbf{u},\mathbf{v} u , v be the expansion coefficients related to u h , v h ∈ V h u_h,v_h \in V_h u h , v h ∈ V h and let p , q \mathbf{p},\mathbf{q} p , q be the expansion coefficients related to p h , q h ∈ Q h p_h,q_h \in Q_h p h , q h ∈ Q h , respectively. Let P v P_v P v , P q P_q P q , and B B B be the matrices defined by ⟨ P v u , v ⟩ : = ( u h , v h ) v \langle P_v\mathbf{u},\mathbf{v}\rangle:= (u_h,v_h)_v ⟨ P v u , v ⟩ := ( u h , v h ) v for all u h , v h ∈ V h u_h,v_h \in V_h u h , v h ∈ V h , ⟨ P q p , q ⟩ : = ( p h , q h ) q \langle P_q\mathbf{p},\mathbf{q}\rangle:= (p_h,q_h)_q ⟨ P q p , q ⟩ := ( p h , q h ) q for all p h , q h ∈ Q h p_h,q_h \in Q_h p h , q h ∈ Q h , and ⟨ B v , q ⟩ : = b h ( v h , q h ) \langle B\mathbf{v},\mathbf{q}\rangle:= b_h(v_h,q_h) ⟨ B v , q ⟩ := b h ( v h , q h ) for all v h ∈ V h v_h \in V_h v h ∈ V h and q h ∈ Q h q_h \in Q_h q h ∈ Q h . Furthermore, we recall the following result of [3 Corollary 1] . Let P q , 1 P_{q,1} P q , 1 and P q , 0 P_{q,0} P q , 0 be matrices defined for all p h , q h ∈ Q h p_h,q_h \in Q_h p h , q h ∈ Q h by ⟨ P q , 1 p , q ⟩ : = ( ∇ p h , ∇ q h ) \langle P_{q,1}\mathbf{p},\mathbf{q}\rangle:= (\nabla p_h,\nabla q_h) ⟨ P q , 1 p , q ⟩ := ( ∇ p h , ∇ q h ) and ⟨ P q , 0 p , q ⟩ : = ( p h , q h ) \langle P_{q,0}\mathbf{p},\mathbf{q}\rangle:= (p_h,q_h) ⟨ P q , 0 p , q ⟩ := ( p h , q h ) , respectively. Then it can be shown that
P q − 1 = τ P q , 1 − 1 + ν P q , 0 − 1 . P_q^{-1} = \tau P_{q,1}^{-1} + \nu P_{q,0}^{-1}. P q − 1 = τ P q , 1 − 1 + ν P q , 0 − 1 .
Preconditioning for stage-weighted Radau IIA RK time-stepping
Let u , v \mathbf{u},\mathbf{v} u , v be the expansion coefficients related to u h , v h ∈ V h u_h,v_h \in V_h u h , v h ∈ V h and p , q \mathbf{p},\mathbf{q} p , q be the expansion coefficients related to p h , q h ∈ Q h p_h,q_h \in Q_h p h , q h ∈ Q h . Let P v P_v P v and P q P_q P q be matrices defined such that
⟨ P v u , v ⟩ : = ( u h , v h ) r , v ∀ u h , v h ∈ V h , ⟨ P q p , q ⟩ : = ( p h , q h ) r , q ∀ p h , q h ∈ Q h . \langle P_v\mathbf{u},\mathbf{v}\rangle:= (u_h,v_h)_{r,v} \quad\forall u_h,v_h \in V_h,\qquad\langle P_q\mathbf{p},\mathbf{q}\rangle:= (p_h,q_h)_{r,q} \quad\forall p_h,q_h \in Q_h. ⟨ P v u , v ⟩ := ( u h , v h ) r , v ∀ u h , v h ∈ V h , ⟨ P q p , q ⟩ := ( p h , q h ) r , q ∀ p h , q h ∈ Q h .
Furthermore, let B B B be the matrix such that ⟨ B v , q ⟩ : = b r ( v h , q h ) \langle B\mathbf{v},\mathbf{q}\rangle:= b_r(v_h,q_h) ⟨ B v , q ⟩ := b r ( v h , q h ) for all v h ∈ V h v_h \in V_h v h ∈ V h and q ∈ Q h q \in Q_h q ∈ Q h . By theorem 1 and § 3.1 , the preconditioner defined by
P U r k : = [ ω P v B T 0 ρ P q ] (42) \mathcal{P}_{U}^{rk} := \begin{bmatrix} \omega P_v & B^{T} \\ 0 & \rho P_q \end{bmatrix} \tag*{(42)} P U r k := [ ω P v 0 B T ρ P q ] (42)
is FOV-equivalent with the system matrix associated with eq. (15) . We observe that P v P_v P v , P q P_q P q , and B B B are block diagonal matrices with one block per stage. Indeed, the i t h i^{th} i t h block of these matrices is given by w ^ i P v \widehat{w}_iP_v w i P v , w ^ i P q \widehat{w}_iP_q w i P q , and w ^ i B \widehat{w}_iB w i B , respectively, for i = 1 , … , s i = 1,\ldots,s i = 1 , … , s .
The inverse of P U r k \mathcal{P}_{U}^{rk} P U r k is given by
( P U r k ) − 1 = [ ω − 1 P v − 1 − ( ρ ω ) − 1 P v − 1 B T P q − 1 0 ρ − 1 P q − 1 ] . \left(\mathcal{P}_{U}^{rk}\right)^{-1} =
\begin{bmatrix}
\omega^{-1}P_v^{-1} & -(\rho\omega)^{-1}P_v^{-1}B^{T}P_q^{-1} \\
0 & \rho^{-1}P_q^{-1}
\end{bmatrix}. ( P U r k ) − 1 = [ ω − 1 P v − 1 0 − ( ρ ω ) − 1 P v − 1 B T P q − 1 ρ − 1 P q − 1 ] .
For the implementation of this preconditioner we then observe that P q − 1 P_q^{-1} P q − 1 is a block diagonal matrix with one block per stage and the i t h i^{th} i t h block is given by ρ − 1 w ^ i − 1 P q − 1 = ρ − 1 w ^ i − 1 τ P q , 1 − 1 + ρ − 1 w ^ i − 1 ν P q , 0 − 1 \rho^{-1}\widehat{w}_i^{-1}P_q^{-1} = \rho^{-1}\widehat{w}_i^{-1} \tau P_{q,1}^{-1} + \rho^{-1}\widehat{w}_i^{-1}\nu P_{q,0}^{-1} ρ − 1 w i − 1 P q − 1 = ρ − 1 w i − 1 τ P q , 1 − 1 + ρ − 1 w i − 1 ν P q , 0 − 1 .
Remark 3. Setting the weights w ^ i = 1 \widehat{w}_i = 1 w i = 1 in eq. (15) we obtain eq. (14) . It can be shown that a r ( ⋅ , ⋅ ) a_r(\cdot,\cdot) a r ( ⋅ , ⋅ ) is inf-sup stable but not necessarily coercive. In this case, one could replace P v P_v P v in eq. (42) by the matrix associated with a r ( ⋅ , ⋅ ) a_r(\cdot,\cdot) a r ( ⋅ , ⋅ ) and still have an FOV-equivalent preconditioner, see Remark 1. However, the matrix associated with a r ( ⋅ , ⋅ ) a_r(\cdot,\cdot) a r ( ⋅ , ⋅ ) couples the stages. The proposed preconditioner eq. (42) is block diagonal with one block per stage.
Preconditioning for weighted DG time-stepping
Let u , v \mathbf{u},\mathbf{v} u , v be the expansion coefficients related to u h , v h ∈ V h n u_h,v_h \in V_h^n u h , v h ∈ V h n and p , q \mathbf{p},\mathbf{q} p , q be the expansion coefficients related to p h , q h ∈ Q h n p_h,q_h \in Q_h^n p h , q h ∈ Q h n . Let P v , t P_{v,t} P v , t and P q , t P_{q,t} P q , t be matrices defined such that
⟨ P v , t u , v ⟩ : = ( u h , v h ) v , t ∀ u h , v h ∈ V h n , ⟨ P q , t p , q ⟩ : = ( p h , q h ) q , t ∀ p h , q h ∈ Q h n . \langle P_{v,t}\mathbf{u},\mathbf{v}\rangle:= (u_h,v_h)_{v,t}\quad\forall u_h,v_h \in V_h^n,\qquad\langle P_{q,t}\mathbf{p},\mathbf{q}\rangle:= (p_h,q_h)_{q,t}\quad\forall p_h,q_h \in Q_h^n. ⟨ P v , t u , v ⟩ := ( u h , v h ) v , t ∀ u h , v h ∈ V h n , ⟨ P q , t p , q ⟩ := ( p h , q h ) q , t ∀ p h , q h ∈ Q h n .
Furthermore, let B ^ \widehat{B} B be the matrix such that ⟨ B ^ v , q ⟩ : = b ^ ( v h , q h ) \langle\widehat{B}\mathbf{v},\mathbf{q}\rangle:= \widehat{b}(v_h,q_h) ⟨ B v , q ⟩ := b ( v h , q h ) for all v h ∈ V h n v_h \in V_h^n v h ∈ V h n and q h ∈ Q h q_h \in Q_h q h ∈ Q h . By theorem 1 and § 3.2.1 , the preconditioner defined by
P U s t : = [ ω P v , t B ^ T 0 ρ P q , t ] , (43) \mathcal{P}_{U}^{\mathrm{st}} := \begin{bmatrix} \omega P_{v,t} & \widehat{B}^{T} \\ 0 & \rho P_{q,t} \end{bmatrix}, \tag*{(43)} P U st := [ ω P v , t 0 B T ρ P q , t ] , (43)
is FOV-equivalent with the system matrix associated with eq. (19) .
The inverse of P U s t \mathcal{P}_{U}^{\mathrm{st}} P U st is given by
( P U s t ) − 1 = [ ω − 1 P v , t − 1 − ( ρ ω ) − 1 P v , t − 1 B ^ T P q , t − 1 0 ρ − 1 P q , t − 1 ] . \left(\mathcal{P}_{U}^{\mathrm{st}}\right)^{-1} = \begin{bmatrix} \omega^{-1}P_{v,t}^{-1} & -(\rho\omega)^{-1}P_{v,t}^{-1}\widehat{B}^{T}P_{q,t}^{-1} \\ 0 & \rho^{-1}P_{q,t}^{-1} \end{bmatrix}. ( P U st ) − 1 = [ ω − 1 P v , t − 1 0 − ( ρ ω ) − 1 P v , t − 1 B T P q , t − 1 ρ − 1 P q , t − 1 ] .
For the implementation of (the action of) the inverse of P U s t \mathcal{P}_{U}^{\mathrm{st}} P U st we have the following useful characterization of P q , t − 1 P_{q,t}^{-1} P q , t − 1 .
Lemma 12. Let P q t , 1 P_{qt,1} P q t , 1 and P q t , 0 P_{qt,0} P q t , 0 be matrices defined for all p h , q h ∈ Q h p_h,q_h \in Q_h p h , q h ∈ Q h by ⟨ P q t , 1 p , q ⟩ : = ∫ I n ( ∇ p h , ∇ q h ) κ n d t \langle P_{qt,1}\mathbf{p},\mathbf{q}\rangle:= \int_{I_n}(\nabla p_h,\nabla q_h)_{\kappa_n}\,\mathrm{d}t ⟨ P q t , 1 p , q ⟩ := ∫ I n ( ∇ p h , ∇ q h ) κ n d t and ⟨ P q t , 0 p , q ⟩ : = ∫ I n ( p h , q h ) κ n d t \langle P_{qt,0}\mathbf{p},\mathbf{q}\rangle:= \int_{I_n}(p_h,q_h)_{\kappa_n}\,\mathrm{d}t ⟨ P q t , 0 p , q ⟩ := ∫ I n ( p h , q h ) κ n d t . Then
P q , t − 1 = τ P q t , 1 − 1 + ν P q t , 0 − 1 . P_{q,t}^{-1}=\tau P_{qt,1}^{-1}+\nu P_{qt,0}^{-1}. P q , t − 1 = τ P q t , 1 − 1 + ν P q t , 0 − 1 . Proof. We follow [3 Corollary 1] . For any p h ∈ Q h p_h \in Q_h p h ∈ Q h , we have
⟨ p h , p h ⟩ q , t = inf p h = p h , 1 + p h , 0 ∫ I n ( τ − 1 ( ∇ p h , 1 , ∇ p h , 1 ) + ν − 1 ( p h , 0 , q h , 0 ) ) κ n d t . \langle p_h,p_h\rangle_{q,t}=\inf_{p_h=p_{h,1}+p_{h,0}}\int_{I_n}\left(\tau^{-1}(\nabla p_{h,1},\nabla p_{h,1})+\nu^{-1}(p_{h,0},q_{h,0})\right)_{\kappa_n}\,\mathrm{d}t. ⟨ p h , p h ⟩ q , t = p h = p h , 1 + p h , 0 inf ∫ I n ( τ − 1 ( ∇ p h , 1 , ∇ p h , 1 ) + ν − 1 ( p h , 0 , q h , 0 ) ) κ n d t . Applying Lemma 15,
⟨ p h , p h ⟩ q , t = inf p h = p h , 1 + p h , 0 ( τ − 1 ∫ I n ( ∇ p h , 1 , ∇ p h , 1 ) κ n d t + ν − 1 ∫ I n ( p h , 0 , p h , 0 ) κ n d t ) . \langle p_h,p_h\rangle_{q,t}=\inf_{p_h=p_{h,1}+p_{h,0}}\left(\tau^{-1}\int_{I_n}(\nabla p_{h,1},\nabla p_{h,1})_{\kappa_n}\,\mathrm{d}t+\nu^{-1}\int_{I_n}(p_{h,0},p_{h,0})_{\kappa_n}\,\mathrm{d}t\right). ⟨ p h , p h ⟩ q , t = p h = p h , 1 + p h , 0 inf ( τ − 1 ∫ I n ( ∇ p h , 1 , ∇ p h , 1 ) κ n d t + ν − 1 ∫ I n ( p h , 0 , p h , 0 ) κ n d t ) . Denoting the expansion coefficients related to p h , 1 ∈ Q h p_{h,1} \in Q_h p h , 1 ∈ Q h by p 1 \mathbf{p}_1 p 1 and the expansion coefficients related to p h , 0 ∈ Q h p_{h,0} \in Q_h p h , 0 ∈ Q h by p 0 \mathbf{p}_0 p 0 , we write the above as
⟨ P q , t p , p ⟩ = inf p = p 1 + p 0 ( τ − 1 ⟨ P q t , 1 p 1 , p 1 ⟩ + ν − 1 ⟨ P q t , 0 p 0 , p 0 ⟩ ) . \langle P_{q,t}\mathbf{p},\mathbf{p}\rangle=\inf_{\mathbf{p}=\mathbf{p}_1+\mathbf{p}_0}\left(\tau^{-1}\langle P_{qt,1}\mathbf{p}_1,\mathbf{p}_1\rangle+\nu^{-1}\langle P_{qt,0}\mathbf{p}_0,\mathbf{p}_0\rangle\right). ⟨ P q , t p , p ⟩ = p = p 1 + p 0 inf ( τ − 1 ⟨ P q t , 1 p 1 , p 1 ⟩ + ν − 1 ⟨ P q t , 0 p 0 , p 0 ⟩ ) . The rest of the proof is analogous to [3 Corollary 1] .
Numerical examples
For the numerical examples in this section we consider two- and three-stage (stage-weighted) Radau IIA RK + Taylor–Hood eq. (15) and weighted space-time eq. (19) discretizations of the time-dependent Stokes problem. For the spatial discretization we consider P 2 P^2 P 2 –P 1 P^1 P 1 Taylor–Hood element.
For the stage-weighted Radau IIA RK + Taylor–Hood discretization eq. (15) we require C r C_r C r in lemma 1 to be symmetric positive definite. We choose W ^ = W \widehat{W}=W W = W with W W W defined in lemma 8. It is interesting to note that with this choice C r C_r C r is symmetric positive definite for s = 2 , … , 7 s=2,\ldots,7 s = 2 , … , 7 . Indeed, let λ min [ s ] \lambda_{\min}^{[s]} λ m i n [ s ] be the smallest eigenvalue of C r C_r C r of an s s s -stage Radau IIA RK method. Then λ min [ 2 ] = 0.2603 \lambda_{\min}^{[2]}=0.2603 λ m i n [ 2 ] = 0.2603 , λ min [ 3 ] = 0.0842 \lambda_{\min}^{[3]}=0.0842 λ m i n [ 3 ] = 0.0842 , λ min [ 4 ] = 0.0461 \lambda_{\min}^{[4]}=0.0461 λ m i n [ 4 ] = 0.0461 , λ min [ 5 ] = 0.0247 \lambda_{\min}^{[5]}=0.0247 λ m i n [ 5 ] = 0.0247 , λ min [ 6 ] = 0.0121 \lambda_{\min}^{[6]}=0.0121 λ m i n [ 6 ] = 0.0121 , and λ min [ 7 ] = 0.0037 \lambda_{\min}^{[7]}=0.0037 λ m i n [ 7 ] = 0.0037 , which are all positive. For s = 8 , 9 , 10 s=8,9,10 s = 8 , 9 , 10 we find λ min [ 8 ] = − 0.0023 \lambda_{\min}^{[8]}=-0.0023 λ m i n [ 8 ] = − 0.0023 , λ min [ 9 ] = − 0.00768 \lambda_{\min}^{[9]}=-0.00768 λ m i n [ 9 ] = − 0.00768 , and λ min [ 10 ] = − 0.0105 \lambda_{\min}^{[10]}=-0.0105 λ m i n [ 10 ] = − 0.0105 and so for 8 ≤ s ≤ 10 8\leq s\leq10 8 ≤ s ≤ 10 one would need to find a different matrix W ^ \widehat{W} W . (The s s s -stage Radau IIA RK tableaus for s = 2 , … , 10 s=2,\ldots,10 s = 2 , … , 10 were computed using [21].) For the 2-stage Radau IIA RK method we therefore choose W ^ = diag ( w ^ 1 , w ^ 2 ) \widehat{W}=\operatorname{diag}(\widehat{w}_1,\widehat{w}_2) W = diag ( w 1 , w 2 ) with w ^ 1 = ( e − 2 ) − 1 e − 1 ≈ 0.51216588 \widehat{w}_1=(e-2)^{-1}e^{-1}\approx0.51216588 w 1 = ( e − 2 ) − 1 e − 1 ≈ 0.51216588 and w ^ 2 = ( e − 2 ) − 1 ( e + e − 1 − 3 ) ≈ 0.11995468 \widehat{w}_2=(e-2)^{-1}(e+e^{-1}-3)\approx0.11995468 w 2 = ( e − 2 ) − 1 ( e + e − 1 − 3 ) ≈ 0.11995468 , and for a 3-stage Radau IIA RK method we choose W ^ = diag ( w ^ 1 , w ^ 2 , w ^ 3 ) \widehat{W}=\operatorname{diag}(\widehat{w}_1,\widehat{w}_2,\widehat{w}_3) W = diag ( w 1 , w 2 , w 3 ) with w ^ 1 = 0.29272466 \widehat{w}_1=0.29272466 w 1 = 0.29272466 , w ^ 2 = 0.29076228 \widehat{w}_2=0.29076228 w 2 = 0.29076228 , and w ^ 3 = 0.04863362 \widehat{w}_3=0.04863362 w 3 = 0.04863362 .
In what follows we will refer to eq. (15) , in which we use s s s -stages, as rk(s s s ) and we will refer to eq. (19) , in which we use polynomials of degree k t k_t k t in time, as dg(k t k_t k t ).
The simulations were performed using the finite element software package NGSolve [33] together with NETGEN [32] to create the unstructured meshes. For the dg(k t k_t k t ) implementation we use the NGSolve add-on library ngsxfem [22]. We use the GMRES implementation of NGSolve with a relative residual tolerance of 10 − 8 10^{-8} 1 0 − 8 .
We consider two versions of the preconditioners P U r k P_U^{rk} P U r k (defined in eq. (42) ) and P U s t P_U^{st} P U s t (defined in eq. (43) ): (1) an ‘exact’ version in which a sparse direct solver is used to compute the inverses of each block; and (2) an ‘inexact’ version. The inexact version uses the Balancing Domain Decomposition by Constraints (BDDC) method [9] to approximate the action of the inverse of the blocks associated with the ‘velocity’ degrees-of-freedom and to approximate the action of the inverse of the blocks P q t , 1 P_{q_t,1} P q t , 1 (dg(k t k_t k t )) and P q , 1 P_{q,1} P q , 1 (rk(s s s )). A direct solver is used to compute the inverse of the mass matrices P q , 0 P_{q,0} P q , 0 (rk(s s s )) and P q t , 0 P_{q_t,0} P q t , 0 (dg(k t k_t k t )) in two dimensions, while a Jacobi preconditioner is used in three dimensions.
As test case we consider the backward facing step (BFS) problem following the setup in [12]. In two dimensions, we set Ω : = ( [ 0.5 , 4 ] × [ 0 , 0.5 ] ) ∪ ( [ 0 , 4 ] × [ 0.5 , 1 ] ) \Omega:=([0.5,4]\times[0,0.5])\cup([0,4]\times[0.5,1]) Ω := ([ 0.5 , 4 ] × [ 0 , 0.5 ]) ∪ ([ 0 , 4 ] × [ 0.5 , 1 ]) and in three dimensions Ω : = ( ( [ 0.5 , 4 ] × [ 0 , 0.5 ] ) ∪ ( [ 0 , 4 ] × [ 0.5 , 1 ] ) ) × [ 0 , 1 ] \Omega:=(([0.5,4]\times[0,0.5])\cup([0,4]\times[0.5,1]))\times[0,1] Ω := (([ 0.5 , 4 ] × [ 0 , 0.5 ]) ∪ ([ 0 , 4 ] × [ 0.5 , 1 ])) × [ 0 , 1 ] . The boundary of the domains is divided into an inflow boundary Γ i n \Gamma_{in} Γ in (at x = 0 x=0 x = 0 ), an outflow boundary Γ o u t \Gamma_{out} Γ o u t (at x = 4 x=4 x = 4 ), and wall boundaries Γ w a l l = ∂ Ω \ ( Γ i n ∪ Γ o u t ) \Gamma_{wall}=\partial\Omega\backslash(\Gamma_{in}\cup\Gamma_{out}) Γ w a l l = ∂ Ω\ ( Γ in ∪ Γ o u t ) . On the inflow boundary, we impose u = [ 16 ( 1 − x 2 ) ( x 2 − 0.5 ) , 0 ] T \boldsymbol{u}=[16(1-x_2)(x_2-0.5),0]^T u = [ 16 ( 1 − x 2 ) ( x 2 − 0.5 ) , 0 ] T in two dimensions and u = [ 64 ( 1 − x 2 ) ( x 2 − 0.5 ) x 3 ( 1 − x 3 ) , 0 , 0 ] T \boldsymbol{u}=[64(1-x_2)(x_2-0.5)x_3(1-x_3),0,0]^T u = [ 64 ( 1 − x 2 ) ( x 2 − 0.5 ) x 3 ( 1 − x 3 ) , 0 , 0 ] T in three dimensions. On the outflow boundary, we impose the Neumann boundary condition ( − ν ∇ u + p I ) n = 0 (-\nu\nabla\boldsymbol{u}+pI)\boldsymbol{n}=0 ( − ν ∇ u + p I ) n = 0 , in which n \boldsymbol{n} n is the outward pointing normal vector, and on the wall boundaries we impose u = 0 \boldsymbol{u}=0 u = 0 . Per test case we perform only one time step. Since the outflow boundary is a Neumann boundary condition we require to modify ( ⋅ , ⋅ ) q (\cdot,\cdot)_q ( ⋅ , ⋅ ) q in eq. (11) to ( p h , q h ) q : = inf p h = p h , 1 + p h , 2 , q h = q h , 1 + q h , 2 ( τ − 1 ( ∇ p h , 1 , ∇ q h , 1 ) + τ − 1 h − 1 ( p h , 1 , q h , 1 ) L 2 ( Γ o u t ) + ν − 1 ( p h , 2 , q h , 2 ) ) (p_h,q_h)_q:=\inf_{p_h=p_{h,1}+p_{h,2},\,q_h=q_{h,1}+q_{h,2}}\left(\tau^{-1}(\nabla p_{h,1},\nabla q_{h,1})+\tau^{-1}h^{-1}(p_{h,1},q_{h,1})_{L^2(\Gamma_{out})}+\nu^{-1}(p_{h,2},q_{h,2})\right) ( p h , q h ) q := inf p h = p h , 1 + p h , 2 , q h = q h , 1 + q h , 2 ( τ − 1 ( ∇ p h , 1 , ∇ q h , 1 ) + τ − 1 h − 1 ( p h , 1 , q h , 1 ) L 2 ( Γ o u t ) + ν − 1 ( p h , 2 , q h , 2 ) ) .
We first study the performance of the ‘exact’ form of the preconditioners for different scaling parameters ρ \rho ρ and ω \omega ω . In Table 1 we list for the two dimensional problem the number of GMRES iterations to reach the desired tolerance for one time step. We do this for rk(2), rk(3), dg(2), and dg(3). We fix the number of cells in the mesh to 2166 and consider ρ ∈ { 0.01 , 0.05 , 0.1 , 0.5 , 1.0 } \rho\in\{0.01,0.05,0.1,0.5,1.0\} ρ ∈ { 0.01 , 0.05 , 0.1 , 0.5 , 1.0 } , ω ∈ { 1 , 2 , 5 , 10 , 15 } \omega\in\{1,2,5,10,15\} ω ∈ { 1 , 2 , 5 , 10 , 15 } , Δ t ∈ { 10 − 1 , 10 − 2 , 10 − 3 } \Delta t\in\{10^{-1},10^{-2},10^{-3}\} Δ t ∈ { 1 0 − 1 , 1 0 − 2 , 1 0 − 3 } , and ν ∈ { 1 , 10 − 3 } \nu\in\{1,10^{-3}\} ν ∈ { 1 , 1 0 − 3 } . For the majority of cases we observe that the lowest iteration count is obtained with ω ∈ { 2 , 5 } \omega\in\{2,5\} ω ∈ { 2 , 5 } and ρ ∈ { 0.1 , 0.5 } \rho\in\{0.1,0.5\} ρ ∈ { 0.1 , 0.5 } . From theorem theorem 1 we observe that large ω \omega ω has the effect of reducing the difference between c ⋆ c_\star c ⋆ and c ~ ⋆ \widetilde{c}_\star c ⋆ , which implies a better clustering of the eigenvalues of P U − 1 A P_U^{-1}A P U − 1 A . This is also demonstrated for the two dimensional BFS problem in Figure 1 for rk(2) and dg(2). However, increasing ω \omega ω also has the effect of shifting the eigenvalues closer to the y y y -axis. The eigenvalues are shifted away from the y y y -axis by decreasing ρ \rho ρ .
Table 1. Two dimensional BFS problem on a mesh with 2166 cells. Number of GMRES iteration needed to reach the desired tolerance when using the ‘exact’ form of the preconditioner with varying scaling parameters ρ \rho ρ and ω \omega ω .
Figure 1. Two dimensional BFS problem. Distribution of the eigenvalues of P − 1 A \mathcal{P}^{-1}A P − 1 A for different ( ω , ρ ) (\omega,\rho) ( ω , ρ ) -pairs for rk(2) and dg(2). The eigenvalues are computed on a mesh consisting of 408 cells and with ν = 1 \nu= 1 ν = 1 and Δ t = 0.05 \Delta t = 0.05 Δ t = 0.05 .
We now consider h h h -robustness of the preconditioners for rk(2), rk(3), dg(2), and dg(3). We fix ν = 1 \nu=1 ν = 1 and Δ t = 10 − 3 \Delta t=10^{-3} Δ t = 1 0 − 3 . In Table 2 we list for the two and three dimensional BFS problems the number of GMRES iterations needed to reach the desired tolerance. We observe that, when using the exact versions of the preconditioners, the iteration count decreases at the number of mesh cells increases. When using the inexact versions of the preconditioners, the variation in number of iterations is very small as the number of cells in the mesh changes.
Table 2. The two and three dimensional BFS problems. Number of GMRES iterations needed to reach the desired tolerance when using the exact and inexact (in parentheses) versions of the preconditioners. We set Δ t = 10 − 3 \Delta t = 10^{-3} Δ t = 1 0 − 3 , ν = 1 \nu= 1 ν = 1 , and vary the number of cells in the mesh.
Finally, we demonstrate robustness of the preconditioners with respect to the time step Δ t \Delta t Δ t and viscosity ν \nu ν for rk(2), rk(3), dg(2), and dg(3) in Table 3 . In two dimensions we consider a mesh consisting of 8724 cells and in three dimensions a mesh consisting of 4693 cells. We observe some dependence of the solver on Δ t \Delta t Δ t but given the variation in Δ t \Delta t Δ t (from Δ t = 10 − 4 \Delta t=10^{-4} Δ t = 1 0 − 4 to Δ t = 1 \Delta t=1 Δ t = 1 ) this variation is very small. For a given Δ t \Delta t Δ t there is also some variation in iteration count as viscosity decreases from ν = 1 \nu=1 ν = 1 to ν = 10 − 4 \nu=10^{-4} ν = 1 0 − 4 but again, this variation is small given the large variation in ν \nu ν . For viscosities between ν = 10 − 8 \nu=10^{-8} ν = 1 0 − 8 and ν = 10 − 4 \nu=10^{-4} ν = 1 0 − 4 there is no
Table 3. The two and three dimensional BFS problems. Number of GMRES iterations needed to reach the desired tolerance when using the exact and inexact (in parentheses) versions of the preconditioners. This table verifies robustness of the preconditioners with respect to the time step and the viscosity. The spatial mesh is fixed with 8724 cells for the two dimensional runs and 4693 for the three dimensional runs.
change in iteration count.
Acknowledgments
SR acknowledges support from the Natural Sciences and Engineering Research Council of Canada through the Discovery Grant program (RGPIN-2023-03237).
Declarations
ChatGPT 6.1 Sol was used to obtain a first draft of the mathematical results in § 3.2.2 which were then checked and revised by the authors. Microsoft Copilot Chat (Basic) was used in the remainder of the manuscript to confirm and simplify some mathematical results originally derived without AI assistance, and for some mathematical exploration which was further worked out by the authors. Gemini 1.5 Pro was used to improve codes used in this paper. The authors assume responsibility for all content.
References
Proof of thm:fovequiv
Before proving theorem 1 we require the following results.
Lemma 13. The α \alpha α and c a c_a c a be the constants from eq. (3). Then,
α c a − 2 ⟨ P v − 1 u , u ⟩ ≤ ⟨ A − 1 u , u ⟩ ≤ c a α − 2 ⟨ P v − 1 u , u ⟩ ∀ u ∈ R n v . \alpha c_a^{-2}\langle P_v^{-1}\mathbf{u},\mathbf{u}\rangle\le\langle A^{-1}\mathbf{u},\mathbf{u}\rangle\le c_a\alpha^{-2}\langle P_v^{-1}\mathbf{u},\mathbf{u}\rangle\qquad\forall\mathbf{u}\in\mathbb{R}^{n_v}. α c a − 2 ⟨ P v − 1 u , u ⟩ ≤ ⟨ A − 1 u , u ⟩ ≤ c a α − 2 ⟨ P v − 1 u , u ⟩ ∀ u ∈ R n v .
Proof. Let v ∈ R n v \mathbf{v}\in\mathbb{R}^{n_v} v ∈ R n v and u = A v \mathbf{u}=A\mathbf{v} u = A v . By eq. (3b) and Cauchy–Schwarz,
α ⟨ P v v , v ⟩ ≤ ⟨ A v , v ⟩ = ⟨ u , v ⟩ ≤ ⟨ P v − 1 u , u ⟩ 1 / 2 ⟨ P v v , v ⟩ 1 / 2 . (44) \alpha\langle P_v\mathbf{v},\mathbf{v}\rangle\le\langle A\mathbf{v},\mathbf{v}\rangle=\langle\mathbf{u},\mathbf{v}\rangle\le\langle P_v^{-1}\mathbf{u},\mathbf{u}\rangle^{1/2}\langle P_v\mathbf{v},\mathbf{v}\rangle^{1/2}. \tag*{(44)} α ⟨ P v v , v ⟩ ≤ ⟨ A v , v ⟩ = ⟨ u , v ⟩ ≤ ⟨ P v − 1 u , u ⟩ 1/2 ⟨ P v v , v ⟩ 1/2 . (44)
Combining eq. (3a) with eq. (40),
⟨ A − 1 u , u ⟩ = ⟨ A v , v ⟩ ≤ c a ⟨ P v v , v ⟩ ≤ c a α − 2 ⟨ P v − 1 u , u ⟩ , \langle A^{-1}\mathbf{u},\mathbf{u}\rangle=\langle A\mathbf{v},\mathbf{v}\rangle\le c_a\langle P_v\mathbf{v},\mathbf{v}\rangle\le c_a\alpha^{-2}\langle P_v^{-1}\mathbf{u},\mathbf{u}\rangle, ⟨ A − 1 u , u ⟩ = ⟨ A v , v ⟩ ≤ c a ⟨ P v v , v ⟩ ≤ c a α − 2 ⟨ P v − 1 u , u ⟩ ,
proving the upper bound. For the lower bound, using the definition of the dual norm and eq. (3a),
∥ u ∥ P v − 1 = sup w ∈ R n v w ≠ 0 ⟨ u , w ⟩ ∥ w ∥ P v = sup w ∈ R n v w ≠ 0 ⟨ A v , w ⟩ ∥ w ∥ P v ≤ sup w ∈ R n v w ≠ 0 c a ∥ v ∥ P v ∥ w ∥ P v ∥ w ∥ P v , \|\mathbf{u}\|_{P_v^{-1}}=\sup_{\substack{\mathbf{w}\in\mathbb{R}^{n_v}\\\mathbf{w}\ne0}}\frac{\langle\mathbf{u},\mathbf{w}\rangle}{\|\mathbf{w}\|_{P_v}}=\sup_{\substack{\mathbf{w}\in\mathbb{R}^{n_v}\\\mathbf{w}\ne0}}\frac{\langle A\mathbf{v},\mathbf{w}\rangle}{\|\mathbf{w}\|_{P_v}}\le\sup_{\substack{\mathbf{w}\in\mathbb{R}^{n_v}\\\mathbf{w}\ne0}}\frac{c_a\|\mathbf{v}\|_{P_v}\|\mathbf{w}\|_{P_v}}{\|\mathbf{w}\|_{P_v}}, ∥ u ∥ P v − 1 = w ∈ R n v w = 0 sup ∥ w ∥ P v ⟨ u , w ⟩ = w ∈ R n v w = 0 sup ∥ w ∥ P v ⟨ A v , w ⟩ ≤ w ∈ R n v w = 0 sup ∥ w ∥ P v c a ∥ v ∥ P v ∥ w ∥ P v ,
so that ⟨ P v − 1 u , u ⟩ ≤ c a 2 ⟨ P v v , v ⟩ \langle P_v^{-1}\mathbf{u},\mathbf{u}\rangle\le c_a^2\langle P_v\mathbf{v},\mathbf{v}\rangle ⟨ P v − 1 u , u ⟩ ≤ c a 2 ⟨ P v v , v ⟩ . Then, again using eq. (3b),
α c a − 2 ⟨ P v − 1 u , u ⟩ ≤ α ⟨ P v v , v ⟩ ≤ ⟨ A v , v ⟩ = ⟨ A − 1 w , w ⟩ , \alpha c_a^{-2}\langle P_v^{-1}\mathbf{u},\mathbf{u}\rangle\le\alpha\langle P_v\mathbf{v},\mathbf{v}\rangle\le\langle A\mathbf{v},\mathbf{v}\rangle=\langle A^{-1}\mathbf{w},\mathbf{w}\rangle, α c a − 2 ⟨ P v − 1 u , u ⟩ ≤ α ⟨ P v v , v ⟩ ≤ ⟨ A v , v ⟩ = ⟨ A − 1 w , w ⟩ ,
proving the lower bound.
Lemma 14. Let S = B A − 1 B T S=BA^{-1}B^T S = B A − 1 B T and let c a , c b , α , β c_a,c_b,\alpha,\beta c a , c b , α , β be the constants from eqs. (3) and (4). Then,
α c a − 2 β 2 ⟨ P q q , q ⟩ ≤ ⟨ S q , q ⟩ ≤ c a α − 2 c b 2 ⟨ P q q , q ⟩ ∀ q ∈ R n q . \alpha c_a^{-2}\beta^2\langle P_q\mathbf{q},\mathbf{q}\rangle\le\langle S\mathbf{q},\mathbf{q}\rangle\le c_a\alpha^{-2}c_b^2\langle P_q\mathbf{q},\mathbf{q}\rangle\qquad\forall\mathbf{q}\in\mathbb{R}^{n_q}. α c a − 2 β 2 ⟨ P q q , q ⟩ ≤ ⟨ S q , q ⟩ ≤ c a α − 2 c b 2 ⟨ P q q , q ⟩ ∀ q ∈ R n q .
Proof. Using lemma 13,
⟨ S q , q ⟩ = ⟨ B A − 1 B T q , q ⟩ = ⟨ A − 1 B T q , B T q ⟩ ≥ α c a − 2 ⟨ P v − 1 B T q , B T q ⟩ . (45) \langle S\mathbf{q},\mathbf{q}\rangle=\langle BA^{-1}B^T\mathbf{q},\mathbf{q}\rangle=\langle A^{-1}B^T\mathbf{q},B^T\mathbf{q}\rangle\ge\alpha c_a^{-2}\langle P_v^{-1}B^T\mathbf{q},B^T\mathbf{q}\rangle. \tag*{(45)} ⟨ S q , q ⟩ = ⟨ B A − 1 B T q , q ⟩ = ⟨ A − 1 B T q , B T q ⟩ ≥ α c a − 2 ⟨ P v − 1 B T q , B T q ⟩ . (45)
Using eq. (4b) and the definition of the dual norm, we note that ∥ B T q ∥ P v − 1 ≥ β ∥ q ∥ P q \|B^T\mathbf{q}\|_{P_v^{-1}}\ge\beta\|\mathbf{q}\|_{P_q} ∥ B T q ∥ P v − 1 ≥ β ∥ q ∥ P q . Combining with eq. (41),
⟨ S q , q ⟩ ≥ α c a − 2 β 2 ⟨ P q q , q ⟩ , \langle S\mathbf{q},\mathbf{q}\rangle\ge\alpha c_a^{-2}\beta^2\langle P_q\mathbf{q},\mathbf{q}\rangle, ⟨ S q , q ⟩ ≥ α c a − 2 β 2 ⟨ P q q , q ⟩ ,
proving the lower bound. For the upper bound, using again lemma 13,
⟨ S q , q ⟩ = ⟨ B A − 1 B T q , q ⟩ = ⟨ A − 1 B T q , B T q ⟩ ≤ c a α − 2 ⟨ P v − 1 B T q , B T q ⟩ . (46) \langle S\mathbf{q},\mathbf{q}\rangle=\langle BA^{-1}B^T\mathbf{q},\mathbf{q}\rangle=\langle A^{-1}B^T\mathbf{q},B^T\mathbf{q}\rangle\le c_a\alpha^{-2}\langle P_v^{-1}B^T\mathbf{q},B^T\mathbf{q}\rangle. \tag*{(46)} ⟨ S q , q ⟩ = ⟨ B A − 1 B T q , q ⟩ = ⟨ A − 1 B T q , B T q ⟩ ≤ c a α − 2 ⟨ P v − 1 B T q , B T q ⟩ . (46)
Using eq. (4a) and the definition of the dual norm, ∥ B T q ∥ P v − 1 ≤ c b ∥ q ∥ P q \|B^T\mathbf{q}\|_{P_v^{-1}}\le c_b\|\mathbf{q}\|_{P_q} ∥ B T q ∥ P v − 1 ≤ c b ∥ q ∥ P q . Combining with eq. (42),
⟨ S q , q ⟩ ≤ c a α − 2 c b 2 ⟨ P q q , q ⟩ , \langle S\mathbf{q},\mathbf{q}\rangle\le c_a\alpha^{-2}c_b^2\langle P_q\mathbf{q},\mathbf{q}\rangle, ⟨ S q , q ⟩ ≤ c a α − 2 c b 2 ⟨ P q q , q ⟩ ,
proving the upper bound.
We now prove the ( P − 1 ) (\mathcal{P}^{-1}) ( P − 1 ) -FOV-equivalence of A \mathcal{A} A and P U \mathcal{P}_U P U .
Proof of theorem 1. Step 1. We start with some useful inequalities. Let A s = 1 2 ( A + A T ) A_s=\frac{1}{2}(A+A^T) A s = 2 1 ( A + A T ) be the symmetric part of A A A and note that ⟨ A v , v ⟩ = ⟨ A s v , v ⟩ \langle Av,v\rangle=\langle A_sv,v\rangle ⟨ A v , v ⟩ = ⟨ A s v , v ⟩ . Let v = A s − 1 w v=A_s^{-1}w v = A s − 1 w for any v ∈ R n v v\in\mathbb{R}^{n_v} v ∈ R n v and note that ⟨ A v , v ⟩ = ⟨ A s v , v ⟩ = ⟨ A s − 1 w , w ⟩ \langle Av,v\rangle=\langle A_sv,v\rangle=\langle A_s^{-1}w,w\rangle ⟨ A v , v ⟩ = ⟨ A s v , v ⟩ = ⟨ A s − 1 w , w ⟩ . Then, using Cauchy–Schwarz and eq. (3b), ⟨ A s − 1 w , w ⟩ = ⟨ w , v ⟩ ≤ ∥ w ∥ P v − 1 ∥ v ∥ P v ≤ ∥ w ∥ P v − 1 α − 1 / 2 ⟨ A s v , v ⟩ 1 / 2 \langle A_s^{-1}w,w\rangle=\langle w,v\rangle\leq\lVert w\rVert_{P_v^{-1}}\lVert v\rVert_{P_v}\leq\lVert w\rVert_{P_v^{-1}}\alpha^{-1/2}\langle A_sv,v\rangle^{1/2} ⟨ A s − 1 w , w ⟩ = ⟨ w , v ⟩ ≤ ∥ w ∥ P v − 1 ∥ v ∥ P v ≤ ∥ w ∥ P v − 1 α − 1/2 ⟨ A s v , v ⟩ 1/2 , so that
⟨ A s − 1 w , w ⟩ ≤ α − 1 ⟨ P v − 1 w , w ⟩ . (47) \langle A_s^{-1}w,w\rangle\leq\alpha^{-1}\langle P_v^{-1}w,w\rangle. \tag*{(47)} ⟨ A s − 1 w , w ⟩ ≤ α − 1 ⟨ P v − 1 w , w ⟩ . (47)
By definition of the dual norm and eq. (3a),
∥ A w ∥ P v − 1 = sup v ∈ R n v v ≠ 0 ⟨ A w , v ⟩ ∥ v ∥ P v ≤ sup v ∈ R n v v ≠ 0 c a ∥ w ∥ P v ∥ v ∥ P v ∥ v ∥ P v = c a ∥ w ∥ P v . (48) \lVert Aw\rVert_{P_v^{-1}}=\sup_{\substack{v\in\mathbb{R}^{n_v}\\v\ne0}}\frac{\langle Aw,v\rangle}{\lVert v\rVert_{P_v}}\leq\sup_{\substack{v\in\mathbb{R}^{n_v}\\v\ne0}}\frac{c_a\lVert w\rVert_{P_v}\lVert v\rVert_{P_v}}{\lVert v\rVert_{P_v}}=c_a\lVert w\rVert_{P_v}. \tag*{(48)} ∥ A w ∥ P v − 1 = v ∈ R n v v = 0 sup ∥ v ∥ P v ⟨ A w , v ⟩ ≤ v ∈ R n v v = 0 sup ∥ v ∥ P v c a ∥ w ∥ P v ∥ v ∥ P v = c a ∥ w ∥ P v . (48)
Likewise, by definition of the dual norm and eq. (4a),
∥ B v ∥ P q − 1 = sup q ∈ R n q q ≠ 0 ⟨ B v , q ⟩ ∥ q ∥ P q ≤ sup q ∈ R n q q ≠ 0 c b ∥ v ∥ P v ∥ q ∥ P q ∥ q ∥ P q = c b ∥ v ∥ P v . (49) \lVert Bv\rVert_{P_q^{-1}}=\sup_{\substack{q\in\mathbb{R}^{n_q}\\q\ne0}}\frac{\langle Bv,q\rangle}{\lVert q\rVert_{P_q}}\leq\sup_{\substack{q\in\mathbb{R}^{n_q}\\q\ne0}}\frac{c_b\lVert v\rVert_{P_v}\lVert q\rVert_{P_q}}{\lVert q\rVert_{P_q}}=c_b\lVert v\rVert_{P_v}. \tag*{(49)} ∥ B v ∥ P q − 1 = q ∈ R n q q = 0 sup ∥ q ∥ P q ⟨ B v , q ⟩ ≤ q ∈ R n q q = 0 sup ∥ q ∥ P q c b ∥ v ∥ P v ∥ q ∥ P q = c b ∥ v ∥ P v . (49)
Step 2. We determine c ⋆ c_\star c ⋆ . Using eq. (3b) and lemmas 13 and 14, and taking the infimum over non-zero vectors,
inf 0 ≠ x ∈ R n ⟨ A P − 1 x , x ⟩ P − 1 ⟨ x , x ⟩ P − 1 = inf ( v , q ) ∈ R n v × R n q ω − 2 ⟨ P v − 1 A P v − 1 v , v ⟩ − ρ − 1 ω − 2 ⟨ P v − 1 A P v − 1 B T P q − 1 q , v ⟩ + ρ − 2 ω − 1 ⟨ P q − 1 B P v − 1 B T P q − 1 q , q ⟩ ω − 1 ⟨ P v − 1 v , v ⟩ + ρ − 1 ⟨ P q − 1 q , q ⟩ ≥ inf ( v , q ) ∈ R n v × R n q ω − 2 ⟨ P v − 1 A s P v − 1 v , v ⟩ − ρ − 1 ω − 2 ⟨ P v − 1 A P v − 1 B T P q − 1 q , v ⟩ + ρ − 2 ω − 1 ⟨ P q − 1 B P v − 1 B T P q − 1 q , q ⟩ α − 1 ω − 1 ⟨ P v − 1 A s P v − 1 v , v ⟩ + ρ − 1 α − 3 c a 2 β − 2 ⟨ P q − 1 B P v − 1 B T P q − 1 q , q ⟩ ≥ 1 c ~ inf ( v , q ) ∈ R n v × R n q ρ 2 ⟨ P v − 1 A s P v − 1 v , v ⟩ − ρ ⟨ P v − 1 A P v − 1 B T P q − 1 q , v ⟩ + ρ ω ⟨ P q − 1 B P v − 1 B T P q − 1 q , q ⟩ ρ 2 ⟨ P v − 1 A s P v − 1 v , v ⟩ + ρ ω ⟨ P q − 1 B P v − 1 B T P q − 1 q , q ⟩ . (50) \begin{aligned}
\inf_{0\ne x\in\mathbb{R}^n}\frac{\langle\mathcal{A}\mathcal{P}^{-1}x,x\rangle_{\mathcal{P}^{-1}}}{\langle x,x\rangle_{\mathcal{P}^{-1}}}
&=\inf_{(v,q)\in\mathbb{R}^{n_v}\times\mathbb{R}^{n_q}}
\frac{\omega^{-2}\langle P_v^{-1}AP_v^{-1}v,v\rangle-\rho^{-1}\omega^{-2}\langle P_v^{-1}AP_v^{-1}B^TP_q^{-1}q,v\rangle+\rho^{-2}\omega^{-1}\langle P_q^{-1}BP_v^{-1}B^TP_q^{-1}q,q\rangle}{\omega^{-1}\langle P_v^{-1}v,v\rangle+\rho^{-1}\langle P_q^{-1}q,q\rangle}\\
&\geq\inf_{(v,q)\in\mathbb{R}^{n_v}\times\mathbb{R}^{n_q}}
\frac{\omega^{-2}\langle P_v^{-1}A_sP_v^{-1}v,v\rangle-\rho^{-1}\omega^{-2}\langle P_v^{-1}AP_v^{-1}B^TP_q^{-1}q,v\rangle+\rho^{-2}\omega^{-1}\langle P_q^{-1}BP_v^{-1}B^TP_q^{-1}q,q\rangle}{\alpha^{-1}\omega^{-1}\langle P_v^{-1}A_sP_v^{-1}v,v\rangle+\rho^{-1}\alpha^{-3}c_a^2\beta^{-2}\langle P_q^{-1}BP_v^{-1}B^TP_q^{-1}q,q\rangle}\\
&\geq\frac{1}{\widetilde c}\inf_{(v,q)\in\mathbb{R}^{n_v}\times\mathbb{R}^{n_q}}
\frac{\rho^2\langle P_v^{-1}A_sP_v^{-1}v,v\rangle-\rho\langle P_v^{-1}AP_v^{-1}B^TP_q^{-1}q,v\rangle+\rho\omega\langle P_q^{-1}BP_v^{-1}B^TP_q^{-1}q,q\rangle}{\rho^2\langle P_v^{-1}A_sP_v^{-1}v,v\rangle+\rho\omega\langle P_q^{-1}BP_v^{-1}B^TP_q^{-1}q,q\rangle}. \tag*{(50)}
\end{aligned} 0 = x ∈ R n inf ⟨ x , x ⟩ P − 1 ⟨ A P − 1 x , x ⟩ P − 1 = ( v , q ) ∈ R n v × R n q inf ω − 1 ⟨ P v − 1 v , v ⟩ + ρ − 1 ⟨ P q − 1 q , q ⟩ ω − 2 ⟨ P v − 1 A P v − 1 v , v ⟩ − ρ − 1 ω − 2 ⟨ P v − 1 A P v − 1 B T P q − 1 q , v ⟩ + ρ − 2 ω − 1 ⟨ P q − 1 B P v − 1 B T P q − 1 q , q ⟩ ≥ ( v , q ) ∈ R n v × R n q inf α − 1 ω − 1 ⟨ P v − 1 A s P v − 1 v , v ⟩ + ρ − 1 α − 3 c a 2 β − 2 ⟨ P q − 1 B P v − 1 B T P q − 1 q , q ⟩ ω − 2 ⟨ P v − 1 A s P v − 1 v , v ⟩ − ρ − 1 ω − 2 ⟨ P v − 1 A P v − 1 B T P q − 1 q , v ⟩ + ρ − 2 ω − 1 ⟨ P q − 1 B P v − 1 B T P q − 1 q , q ⟩ ≥ c 1 ( v , q ) ∈ R n v × R n q inf ρ 2 ⟨ P v − 1 A s P v − 1 v , v ⟩ + ρ ω ⟨ P q − 1 B P v − 1 B T P q − 1 q , q ⟩ ρ 2 ⟨ P v − 1 A s P v − 1 v , v ⟩ − ρ ⟨ P v − 1 A P v − 1 B T P q − 1 q , v ⟩ + ρ ω ⟨ P q − 1 B P v − 1 B T P q − 1 q , q ⟩ . (50)
where c ~ = ω α − 1 max { 1 , α − 2 c a 2 β − 2 } \widetilde c=\omega\alpha^{-1}\max\{1,\alpha^{-2}c_a^2\beta^{-2}\} c = ω α − 1 max { 1 , α − 2 c a 2 β − 2 } . To find a lower bound for the right hand side of eq. (50) , we follow the proof of Theorem 4.3 of [16], i.e., we find lower bounds for the generalized eigenvalues of
[ ρ 2 P v − 1 A s P v − 1 − 1 2 ρ P v − 1 A P v − 1 B T P q − 1 − 1 2 ρ P q − 1 B P v − 1 A T P v − 1 ρ ω P q − 1 B P v − 1 B T P q − 1 ] [ v q ] = λ [ ρ 2 P v − 1 A s P v − 1 0 0 ρ ω P q − 1 B P v − 1 B T P q − 1 ] [ v q ] . \begin{bmatrix}
\rho^2P_v^{-1}A_sP_v^{-1} & -\frac{1}{2}\rho P_v^{-1}AP_v^{-1}B^TP_q^{-1}\\
-\frac{1}{2}\rho P_q^{-1}BP_v^{-1}A^TP_v^{-1} & \rho\omega P_q^{-1}BP_v^{-1}B^TP_q^{-1}
\end{bmatrix}
\begin{bmatrix}v\\q\end{bmatrix}
=
\lambda
\begin{bmatrix}
\rho^2P_v^{-1}A_sP_v^{-1} & 0\\
0 & \rho\omega P_q^{-1}BP_v^{-1}B^TP_q^{-1}
\end{bmatrix}
\begin{bmatrix}v\\q\end{bmatrix}. [ ρ 2 P v − 1 A s P v − 1 − 2 1 ρ P q − 1 B P v − 1 A T P v − 1 − 2 1 ρ P v − 1 A P v − 1 B T P q − 1 ρ ω P q − 1 B P v − 1 B T P q − 1 ] [ v q ] = λ [ ρ 2 P v − 1 A s P v − 1 0 0 ρ ω P q − 1 B P v − 1 B T P q − 1 ] [ v q ] .
After algebraic manipulation, we find that λ \lambda λ satisfies
( λ − 1 ) 2 = ⟨ P q − 1 B P v − 1 A T A s − 1 A P v − 1 B T P q − 1 q , q ⟩ 4 ρ ω ⟨ P q − 1 B P v − 1 B T P q − 1 q , q ⟩ = ⟨ A s − 1 A w , A w ⟩ 4 ρ ω ⟨ P v w , w ⟩ , (51) (\lambda-1)^2=\frac{\langle P_q^{-1}BP_v^{-1}A^TA_s^{-1}AP_v^{-1}B^TP_q^{-1}q,q\rangle}{4\rho\omega\langle P_q^{-1}BP_v^{-1}B^TP_q^{-1}q,q\rangle}=\frac{\langle A_s^{-1}Aw,Aw\rangle}{4\rho\omega\langle P_vw,w\rangle}, \tag*{(51)} ( λ − 1 ) 2 = 4 ρ ω ⟨ P q − 1 B P v − 1 B T P q − 1 q , q ⟩ ⟨ P q − 1 B P v − 1 A T A s − 1 A P v − 1 B T P q − 1 q , q ⟩ = 4 ρ ω ⟨ P v w , w ⟩ ⟨ A s − 1 A w , A w ⟩ , (51)
where we defined w = P v − 1 B T P q − 1 q w=P_v^{-1}B^TP_q^{-1}q w = P v − 1 B T P q − 1 q . Combining eqs. (47) and (48) ,
⟨ A s − 1 A w , A w ⟩ ≤ α − 1 ⟨ P v − 1 A w , A w ⟩ = α − 1 ∥ A w ∥ P v − 1 2 ≤ α − 1 c a 2 ∥ w ∥ P v 2 = α − 1 c a 2 ⟨ P v w , w ⟩ . (52) \langle A_s^{-1}Aw,Aw\rangle\leq\alpha^{-1}\langle P_v^{-1}Aw,Aw\rangle=\alpha^{-1}\lVert Aw\rVert_{P_v^{-1}}^2\leq\alpha^{-1}c_a^2\lVert w\rVert_{P_v}^2=\alpha^{-1}c_a^2\langle P_vw,w\rangle. \tag*{(52)} ⟨ A s − 1 A w , A w ⟩ ≤ α − 1 ⟨ P v − 1 A w , A w ⟩ = α − 1 ∥ A w ∥ P v − 1 2 ≤ α − 1 c a 2 ∥ w ∥ P v 2 = α − 1 c a 2 ⟨ P v w , w ⟩ . (52)
Using eq. (52) in eq. (51) , we find that ∣ λ − 1 ∣ ≤ c a 2 ρ α ω \lvert\lambda-1\rvert\leq\frac{c_a}{2\sqrt{\rho\alpha\omega}} ∣ λ − 1 ∣ ≤ 2 ρ α ω c a . Combined with eq. (50) , the expression from c ⋆ c_\star c ⋆ follows. Positivity of c ⋆ c_\star c ⋆ is a consequence of ρ ω > 1 4 c a 2 α − 1 \rho\omega>\frac{1}{4}c_a^2\alpha^{-1} ρ ω > 4 1 c a 2 α − 1 .
Step 3. We determine c ˉ ⋆ \bar c_\star c ˉ ⋆ . By definition and the substitution x = A y x=Ay x = A y
c ˉ ⋆ ≤ inf 0 ≠ x ∈ R n ⟨ P − 1 P U A − 1 x , x ⟩ ⟨ P − 1 x , x ⟩ = inf 0 ≠ y ∈ R n ⟨ P − 1 P U y , A y ⟩ ⟨ P − 1 A y , A y ⟩ . (53) \bar c_\star\leq\inf_{0\ne x\in\mathbb{R}^n}\frac{\langle P^{-1}P_UA^{-1}x,x\rangle}{\langle P^{-1}x,x\rangle}=\inf_{0\ne y\in\mathbb{R}^n}\frac{\langle P^{-1}P_Uy,Ay\rangle}{\langle P^{-1}Ay,Ay\rangle}. \tag*{(53)} c ˉ ⋆ ≤ 0 = x ∈ R n inf ⟨ P − 1 x , x ⟩ ⟨ P − 1 P U A − 1 x , x ⟩ = 0 = y ∈ R n inf ⟨ P − 1 A y , A y ⟩ ⟨ P − 1 P U y , A y ⟩ . (53)
We consider separately the numerator and denominator. For y = [ v T q T ] T \mathbf{y}=[\mathbf{v}^{T}\ \mathbf{q}^{T}]^{T} y = [ v T q T ] T and defining w = P v − 1 B T q \mathbf{w}=P_{v}^{-1}B^{T}\mathbf{q} w = P v − 1 B T q , we find for the numerator
⟨ P U − 1 P U y , A y ⟩ = ⟨ v + ω − 1 P v − 1 B T q , A v + B T q ⟩ − ⟨ q , B v ⟩ = ⟨ A s v , v ⟩ + ω − 1 ⟨ A v , w ⟩ + ω − 1 ⟨ w , P v w ⟩ . (54) \left\langle P_{U}^{-1}P_{U}\mathbf{y},A\mathbf{y}\right\rangle=\left\langle\mathbf{v}+\omega^{-1}P_{v}^{-1}B^{T}\mathbf{q},A\mathbf{v}+B^{T}\mathbf{q}\right\rangle-\langle\mathbf{q},B\mathbf{v}\rangle
=\langle A_{s}\mathbf{v},\mathbf{v}\rangle+\omega^{-1}\langle A\mathbf{v},\mathbf{w}\rangle+\omega^{-1}\langle\mathbf{w},P_{v}\mathbf{w}\rangle. \tag*{(54)} ⟨ P U − 1 P U y , A y ⟩ = ⟨ v + ω − 1 P v − 1 B T q , A v + B T q ⟩ − ⟨ q , B v ⟩ = ⟨ A s v , v ⟩ + ω − 1 ⟨ A v , w ⟩ + ω − 1 ⟨ w , P v w ⟩ . (54)
By Cauchy–Schwarz, Young’s inequality, and eq. (48) ,
⟨ A v , w ⟩ ≥ − 1 2 c a 2 ∥ v ∥ P v 2 − 1 2 ∥ w ∥ P v 2 . (55) \langle A\mathbf{v},\mathbf{w}\rangle\geq-\frac{1}{2}c_{a}^{2}\|\mathbf{v}\|_{P_{v}}^{2}-\frac{1}{2}\|\mathbf{w}\|_{P_{v}}^{2}. \tag*{(55)} ⟨ A v , w ⟩ ≥ − 2 1 c a 2 ∥ v ∥ P v 2 − 2 1 ∥ w ∥ P v 2 . (55)
Using eq. (4) and eq. (51) to bound the right hand side of eq. (50) from below,
⟨ P U − 1 P U y , A y ⟩ ≥ α ∥ v ∥ P v 2 − 1 2 c a 2 ω − 1 ∥ v ∥ P v 2 − 1 2 ω − 1 ∥ w ∥ P v 2 + ω − 1 ∥ w ∥ P v 2 = ( α − 1 2 c a 2 ω − 1 ) ∥ v ∥ P v 2 + 1 2 ω − 1 ∥ w ∥ P v 2 . (56) \begin{aligned}
\left\langle P_{U}^{-1}P_{U}\mathbf{y},A\mathbf{y}\right\rangle\geq\alpha\|\mathbf{v}\|_{P_{v}}^{2}-\frac{1}{2}c_{a}^{2}\omega^{-1}\|\mathbf{v}\|_{P_{v}}^{2}-\frac{1}{2}\omega^{-1}\|\mathbf{w}\|_{P_{v}}^{2}+\omega^{-1}\|\mathbf{w}\|_{P_{v}}^{2} \\
&=\left(\alpha-\frac{1}{2}c_{a}^{2}\omega^{-1}\right)\|\mathbf{v}\|_{P_{v}}^{2}+\frac{1}{2}\omega^{-1}\|\mathbf{w}\|_{P_{v}}^{2}. \tag*{(56)}
\end{aligned} ⟨ P U − 1 P U y , A y ⟩ ≥ α ∥ v ∥ P v 2 − 2 1 c a 2 ω − 1 ∥ v ∥ P v 2 − 2 1 ω − 1 ∥ w ∥ P v 2 + ω − 1 ∥ w ∥ P v 2 = ( α − 2 1 c a 2 ω − 1 ) ∥ v ∥ P v 2 + 2 1 ω − 1 ∥ w ∥ P v 2 . (56)
Expanding now the denominator of eq. (53) ,
⟨ P − 1 A y , A y ⟩ = ω − 1 ∥ A v + B T q ∥ P v − 1 2 + ρ − 1 ∥ B v ∥ P q − 1 2 . (57) \left\langle P^{-1}A\mathbf{y},A\mathbf{y}\right\rangle=\omega^{-1}\|A\mathbf{v}+B^{T}\mathbf{q}\|_{P_{v}^{-1}}^{2}+\rho^{-1}\|B\mathbf{v}\|_{P_{q}^{-1}}^{2}. \tag*{(57)} ⟨ P − 1 A y , A y ⟩ = ω − 1 ∥ A v + B T q ∥ P v − 1 2 + ρ − 1 ∥ B v ∥ P q − 1 2 . (57)
Define w \mathbf{w} w such that B T q = P v w B^{T}\mathbf{q}=P_{v}\mathbf{w} B T q = P v w . Using the triangle inequality, eqs. (48) and (49) , we bound the right hand side of eq. (53),
⟨ P − 1 A y , A y ⟩ = ω − 1 ∥ A v + P v w ∥ P v − 1 2 + ρ − 1 ∥ B v ∥ P q − 1 2 \left\langle P^{-1}A\mathbf{y},A\mathbf{y}\right\rangle=\omega^{-1}\|A\mathbf{v}+P_{v}\mathbf{w}\|_{P_{v}^{-1}}^{2}+\rho^{-1}\|B\mathbf{v}\|_{P_{q}^{-1}}^{2} ⟨ P − 1 A y , A y ⟩ = ω − 1 ∥ A v + P v w ∥ P v − 1 2 + ρ − 1 ∥ B v ∥ P q − 1 2
≤ 2 ω − 1 c a 2 ∥ v ∥ P v 2 + 2 ω − 1 ∥ w ∥ P v 2 + ρ − 1 c b 2 ∥ v ∥ P v 2 . (58) \leq2\omega^{-1}c_{a}^{2}\|\mathbf{v}\|_{P_{v}}^{2}+2\omega^{-1}\|\mathbf{w}\|_{P_{v}}^{2}+\rho^{-1}c_{b}^{2}\|\mathbf{v}\|_{P_{v}}^{2}. \tag*{(58)} ≤ 2 ω − 1 c a 2 ∥ v ∥ P v 2 + 2 ω − 1 ∥ w ∥ P v 2 + ρ − 1 c b 2 ∥ v ∥ P v 2 . (58)
Combining eqs. (52) and (54) with eq. (53) ,
inf 0 ≠ y ∈ R n ⟨ P − 1 P U y , A y ⟩ ⟨ P − 1 A y , A y ⟩ ≥ inf 0 ≠ y ∈ R n ( 2 α ω − c a 2 ) ∥ v ∥ P v 2 + ∥ w ∥ P v 2 ( 4 c a 2 + 2 ω ρ − 1 c b 2 ) ∥ v ∥ P v 2 + 4 ∥ w ∥ P v 2 ≥ c ˉ ⋆ . \inf_{0\ne\mathbf{y}\in\mathbb{R}^{n}}\frac{\left\langle P^{-1}P_{U}\mathbf{y},A\mathbf{y}\right\rangle}{\left\langle P^{-1}A\mathbf{y},A\mathbf{y}\right\rangle}\geq\inf_{0\ne\mathbf{y}\in\mathbb{R}^{n}}\frac{(2\alpha\omega-c_{a}^{2})\|\mathbf{v}\|_{P_{v}}^{2}+\|\mathbf{w}\|_{P_{v}}^{2}}{(4c_{a}^{2}+2\omega\rho^{-1}c_{b}^{2})\|\mathbf{v}\|_{P_{v}}^{2}+4\|\mathbf{w}\|_{P_{v}}^{2}}\geq\bar{c}_{\star}. 0 = y ∈ R n inf ⟨ P − 1 A y , A y ⟩ ⟨ P − 1 P U y , A y ⟩ ≥ 0 = y ∈ R n inf ( 4 c a 2 + 2 ω ρ − 1 c b 2 ) ∥ v ∥ P v 2 + 4∥ w ∥ P v 2 ( 2 α ω − c a 2 ) ∥ v ∥ P v 2 + ∥ w ∥ P v 2 ≥ c ˉ ⋆ .
Positivity of c ˉ ⋆ \bar{c}_{\star} c ˉ ⋆ is a consequence of ω > 1 2 c a 2 α − 1 \omega>\frac{1}{2}c_{a}^{2}\alpha^{-1} ω > 2 1 c a 2 α − 1 .
An equality used in the proof of lemma 12
Lemma 15. The following equality holds:
∫ I n inf p h = p h , 1 + p h , 0 ( τ − 1 ( ∇ p h , 1 , ∇ p h , 1 ) + ν − 1 ( p h , 0 , p h , 0 ) ) κ n d t = inf p h = p h , 1 + p h , 0 ( τ − 1 ∫ I n ( ∇ p h , 1 , ∇ p h , 1 ) κ n d t + ν − 1 ∫ I n ( p h , 0 , p h , 0 ) κ n d t ) . (59) \int_{I_{n}}\inf_{p_{h}=p_{h,1}+p_{h,0}}\left(\tau^{-1}(\nabla p_{h,1},\nabla p_{h,1})+\nu^{-1}(p_{h,0},p_{h,0})\right)\kappa_{n}\,\mathrm{d}t
=\inf_{p_{h}=p_{h,1}+p_{h,0}}\left(\tau^{-1}\int_{I_{n}}(\nabla p_{h,1},\nabla p_{h,1})\kappa_{n}\,\mathrm{d}t+\nu^{-1}\int_{I_{n}}(p_{h,0},p_{h,0})\kappa_{n}\,\mathrm{d}t\right). \tag*{(59)} ∫ I n p h = p h , 1 + p h , 0 inf ( τ − 1 ( ∇ p h , 1 , ∇ p h , 1 ) + ν − 1 ( p h , 0 , p h , 0 ) ) κ n d t = p h = p h , 1 + p h , 0 inf ( τ − 1 ∫ I n ( ∇ p h , 1 , ∇ p h , 1 ) κ n d t + ν − 1 ∫ I n ( p h , 0 , p h , 0 ) κ n d t ) . (59)
Proof. Step 1. Consider the left hand side of eq. (55). Let { ϕ i } i = 0 k t \{\phi_{i}\}_{i=0}^{k_{t}} { ϕ i } i = 0 k t be an orthonormal basis of P k ( I n ) P_{k}(I_{n}) P k ( I n ) with respect to the weighted L 2 ( I n ) L^{2}(I_{n}) L 2 ( I n ) inner product. Then p h ( x , t ) = ∑ i = 0 k t ϕ i ( t ) p i ( x ) p_{h}(x,t)=\sum_{i=0}^{k_{t}}\phi_{i}(t)p_{i}(x) p h ( x , t ) = ∑ i = 0 k t ϕ i ( t ) p i ( x ) and we write
∫ I n inf p h = p h , 1 + p h , 0 ( τ − 1 ( ∇ p h , 1 , ∇ p h , 1 ) + ν − 1 ( p h , 0 , p h , 0 ) ) κ n d t = ∑ i = 0 k t inf p i = p i , 1 + p i , 0 ( τ − 1 ( ∇ p i , 1 , ∇ p i , 1 ) + ν − 1 ( p i , 0 , p i , 0 ) ) . \int_{I_{n}}\inf_{p_{h}=p_{h,1}+p_{h,0}}\left(\tau^{-1}(\nabla p_{h,1},\nabla p_{h,1})+\nu^{-1}(p_{h,0},p_{h,0})\right)\kappa_{n}\,\mathrm{d}t
=\sum_{i=0}^{k_{t}}\inf_{p_{i}=p_{i,1}+p_{i,0}}\left(\tau^{-1}(\nabla p_{i,1},\nabla p_{i,1})+\nu^{-1}(p_{i,0},p_{i,0})\right). ∫ I n p h = p h , 1 + p h , 0 inf ( τ − 1 ( ∇ p h , 1 , ∇ p h , 1 ) + ν − 1 ( p h , 0 , p h , 0 ) ) κ n d t = i = 0 ∑ k t p i = p i , 1 + p i , 0 inf ( τ − 1 ( ∇ p i , 1 , ∇ p i , 1 ) + ν − 1 ( p i , 0 , p i , 0 ) ) .
The infimum for each i i i is attained by the unique p i , 1 ⋆ ∈ Q h p_{i,1}^{\star}\in Q_{h} p i , 1 ⋆ ∈ Q h that satisfies [17, Section 5.4]
τ − 1 ( ∇ p i , 1 ⋆ , ∇ r i ) + ν − 1 ( p i , 1 ⋆ , r i ) = ν − 1 ( p i , r i ) , \tau^{-1}(\nabla p_{i,1}^{\star},\nabla r_{i})+\nu^{-1}(p_{i,1}^{\star},r_{i})=\nu^{-1}(p_{i},r_{i}), τ − 1 ( ∇ p i , 1 ⋆ , ∇ r i ) + ν − 1 ( p i , 1 ⋆ , r i ) = ν − 1 ( p i , r i ) ,
@page 23/24 starts_mid=1 ends_mid=1 We consider separately the numerator and denominator. For y = [ v T q T ] T \mathbf{y}=[\mathbf{v}^{T}\ \mathbf{q}^{T}]^{T} y = [ v T q T ] T and defining w = P v − 1 B T q \mathbf{w}=P_{v}^{-1}B^{T}\mathbf{q} w = P v − 1 B T q , we find for the numerator
⟨ P U − 1 P U y , A y ⟩ = ⟨ v + ω − 1 P v − 1 B T q , A v + B T q ⟩ − ⟨ q , B v ⟩ = ⟨ A s v , v ⟩ + ω − 1 ⟨ A v , w ⟩ + ω − 1 ⟨ w , P v w ⟩ . (60) \left\langle P_{U}^{-1}P_{U}\mathbf{y},A\mathbf{y}\right\rangle=\left\langle\mathbf{v}+\omega^{-1}P_{v}^{-1}B^{T}\mathbf{q},A\mathbf{v}+B^{T}\mathbf{q}\right\rangle-\langle\mathbf{q},B\mathbf{v}\rangle
=\langle A_{s}\mathbf{v},\mathbf{v}\rangle+\omega^{-1}\langle A\mathbf{v},\mathbf{w}\rangle+\omega^{-1}\langle\mathbf{w},P_{v}\mathbf{w}\rangle. \tag*{(60)} ⟨ P U − 1 P U y , A y ⟩ = ⟨ v + ω − 1 P v − 1 B T q , A v + B T q ⟩ − ⟨ q , B v ⟩ = ⟨ A s v , v ⟩ + ω − 1 ⟨ A v , w ⟩ + ω − 1 ⟨ w , P v w ⟩ . (60)
By Cauchy–Schwarz, Young’s inequality, and eq. (48) ,
⟨ A v , w ⟩ ≥ − 1 2 c a 2 ∥ v ∥ P v 2 − 1 2 ∥ w ∥ P v 2 . (61) \langle A\mathbf{v},\mathbf{w}\rangle\geq-\frac{1}{2}c_{a}^{2}\|\mathbf{v}\|_{P_{v}}^{2}-\frac{1}{2}\|\mathbf{w}\|_{P_{v}}^{2}. \tag*{(61)} ⟨ A v , w ⟩ ≥ − 2 1 c a 2 ∥ v ∥ P v 2 − 2 1 ∥ w ∥ P v 2 . (61)
Using eq. (4) and eq. (51) to bound the right hand side of eq. (50) from below,
⟨ P U − 1 P U y , A y ⟩ ≥ α ∥ v ∥ P v 2 − 1 2 c a 2 ω − 1 ∥ v ∥ P v 2 − 1 2 ω − 1 ∥ w ∥ P v 2 + ω − 1 ∥ w ∥ P v 2 = ( α − 1 2 c a 2 ω − 1 ) ∥ v ∥ P v 2 + 1 2 ω − 1 ∥ w ∥ P v 2 . (62) \begin{aligned}
\left\langle P_{U}^{-1}P_{U}\mathbf{y},A\mathbf{y}\right\rangle\geq\alpha\|\mathbf{v}\|_{P_{v}}^{2}-\frac{1}{2}c_{a}^{2}\omega^{-1}\|\mathbf{v}\|_{P_{v}}^{2}-\frac{1}{2}\omega^{-1}\|\mathbf{w}\|_{P_{v}}^{2}+\omega^{-1}\|\mathbf{w}\|_{P_{v}}^{2} \\
&=\left(\alpha-\frac{1}{2}c_{a}^{2}\omega^{-1}\right)\|\mathbf{v}\|_{P_{v}}^{2}+\frac{1}{2}\omega^{-1}\|\mathbf{w}\|_{P_{v}}^{2}. \tag*{(62)}
\end{aligned} ⟨ P U − 1 P U y , A y ⟩ ≥ α ∥ v ∥ P v 2 − 2 1 c a 2 ω − 1 ∥ v ∥ P v 2 − 2 1 ω − 1 ∥ w ∥ P v 2 + ω − 1 ∥ w ∥ P v 2 = ( α − 2 1 c a 2 ω − 1 ) ∥ v ∥ P v 2 + 2 1 ω − 1 ∥ w ∥ P v 2 . (62)
Expanding now the denominator of eq. (53) ,
⟨ P − 1 A y , A y ⟩ = ω − 1 ∥ A v + B T q ∥ P v − 1 2 + ρ − 1 ∥ B v ∥ P q − 1 2 . (63) \left\langle P^{-1}A\mathbf{y},A\mathbf{y}\right\rangle=\omega^{-1}\|A\mathbf{v}+B^{T}\mathbf{q}\|_{P_{v}^{-1}}^{2}+\rho^{-1}\|B\mathbf{v}\|_{P_{q}^{-1}}^{2}. \tag*{(63)} ⟨ P − 1 A y , A y ⟩ = ω − 1 ∥ A v + B T q ∥ P v − 1 2 + ρ − 1 ∥ B v ∥ P q − 1 2 . (63)
Define w \mathbf{w} w such that B T q = P v w B^{T}\mathbf{q}=P_{v}\mathbf{w} B T q = P v w . Using the triangle inequality, eqs. (48) and (49) , we bound the right hand side of eq. (53),
⟨ P − 1 A y , A y ⟩ = ω − 1 ∥ A v + P v w ∥ P v − 1 2 + ρ − 1 ∥ B v ∥ P q − 1 2 \left\langle P^{-1}A\mathbf{y},A\mathbf{y}\right\rangle=\omega^{-1}\|A\mathbf{v}+P_{v}\mathbf{w}\|_{P_{v}^{-1}}^{2}+\rho^{-1}\|B\mathbf{v}\|_{P_{q}^{-1}}^{2} ⟨ P − 1 A y , A y ⟩ = ω − 1 ∥ A v + P v w ∥ P v − 1 2 + ρ − 1 ∥ B v ∥ P q − 1 2
≤ 2 ω − 1 c a 2 ∥ v ∥ P v 2 + 2 ω − 1 ∥ w ∥ P v 2 + ρ − 1 c b 2 ∥ v ∥ P v 2 . (64) \leq2\omega^{-1}c_{a}^{2}\|\mathbf{v}\|_{P_{v}}^{2}+2\omega^{-1}\|\mathbf{w}\|_{P_{v}}^{2}+\rho^{-1}c_{b}^{2}\|\mathbf{v}\|_{P_{v}}^{2}. \tag*{(64)} ≤ 2 ω − 1 c a 2 ∥ v ∥ P v 2 + 2 ω − 1 ∥ w ∥ P v 2 + ρ − 1 c b 2 ∥ v ∥ P v 2 . (64)
Combining eqs. (52) and (54) with eq. (53) ,
inf 0 ≠ y ∈ R n ⟨ P − 1 P U y , A y ⟩ ⟨ P − 1 A y , A y ⟩ ≥ inf 0 ≠ y ∈ R n ( 2 α ω − c a 2 ) ∥ v ∥ P v 2 + ∥ w ∥ P v 2 ( 4 c a 2 + 2 ω ρ − 1 c b 2 ) ∥ v ∥ P v 2 + 4 ∥ w ∥ P v 2 ≥ c ˉ ⋆ . \inf_{0\ne\mathbf{y}\in\mathbb{R}^{n}}\frac{\left\langle P^{-1}P_{U}\mathbf{y},A\mathbf{y}\right\rangle}{\left\langle P^{-1}A\mathbf{y},A\mathbf{y}\right\rangle}\geq\inf_{0\ne\mathbf{y}\in\mathbb{R}^{n}}\frac{(2\alpha\omega-c_{a}^{2})\|\mathbf{v}\|_{P_{v}}^{2}+\|\mathbf{w}\|_{P_{v}}^{2}}{(4c_{a}^{2}+2\omega\rho^{-1}c_{b}^{2})\|\mathbf{v}\|_{P_{v}}^{2}+4\|\mathbf{w}\|_{P_{v}}^{2}}\geq\bar{c}_{\star}. 0 = y ∈ R n inf ⟨ P − 1 A y , A y ⟩ ⟨ P − 1 P U y , A y ⟩ ≥ 0 = y ∈ R n inf ( 4 c a 2 + 2 ω ρ − 1 c b 2 ) ∥ v ∥ P v 2 + 4∥ w ∥ P v 2 ( 2 α ω − c a 2 ) ∥ v ∥ P v 2 + ∥ w ∥ P v 2 ≥ c ˉ ⋆ .
Positivity of c ˉ ⋆ \bar{c}_{\star} c ˉ ⋆ is a consequence of ω > 1 2 c a 2 α − 1 \omega>\frac{1}{2}c_{a}^{2}\alpha^{-1} ω > 2 1 c a 2 α − 1 .
An equality used in the proof of lemma 12
Lemma 15. The following equality holds:
∫ I n inf p h = p h , 1 + p h , 0 ( τ − 1 ( ∇ p h , 1 , ∇ p h , 1 ) + ν − 1 ( p h , 0 , p h , 0 ) ) κ n d t = inf p h = p h , 1 + p h , 0 ( τ − 1 ∫ I n ( ∇ p h , 1 , ∇ p h , 1 ) κ n d t + ν − 1 ∫ I n ( p h , 0 , p h , 0 ) κ n d t ) . (65) \int_{I_{n}}\inf_{p_{h}=p_{h,1}+p_{h,0}}\left(\tau^{-1}(\nabla p_{h,1},\nabla p_{h,1})+\nu^{-1}(p_{h,0},p_{h,0})\right)\kappa_{n}\,\mathrm{d}t
=\inf_{p_{h}=p_{h,1}+p_{h,0}}\left(\tau^{-1}\int_{I_{n}}(\nabla p_{h,1},\nabla p_{h,1})\kappa_{n}\,\mathrm{d}t+\nu^{-1}\int_{I_{n}}(p_{h,0},p_{h,0})\kappa_{n}\,\mathrm{d}t\right). \tag*{(65)} ∫ I n p h = p h , 1 + p h , 0 inf ( τ − 1 ( ∇ p h , 1 , ∇ p h , 1 ) + ν − 1 ( p h , 0 , p h , 0 ) ) κ n d t = p h = p h , 1 + p h , 0 inf ( τ − 1 ∫ I n ( ∇ p h , 1 , ∇ p h , 1 ) κ n d t + ν − 1 ∫ I n ( p h , 0 , p h , 0 ) κ n d t ) . (65)
Proof. Step 1. Consider the left hand side of eq. (55). Let { ϕ i } i = 0 k t \{\phi_{i}\}_{i=0}^{k_{t}} { ϕ i } i = 0 k t be an orthonormal basis of P k ( I n ) P_{k}(I_{n}) P k ( I n ) with respect to the weighted L 2 ( I n ) L^{2}(I_{n}) L 2 ( I n ) inner product. Then p h ( x , t ) = ∑ i = 0 k t ϕ i ( t ) p i ( x ) p_{h}(x,t)=\sum_{i=0}^{k_{t}}\phi_{i}(t)p_{i}(x) p h ( x , t ) = ∑ i = 0 k t ϕ i ( t ) p i ( x ) and we write
∫ I n inf p h = p h , 1 + p h , 0 ( τ − 1 ( ∇ p h , 1 , ∇ p h , 1 ) + ν − 1 ( p h , 0 , p h , 0 ) ) κ n d t = ∑ i = 0 k t inf p i = p i , 1 + p i , 0 ( τ − 1 ( ∇ p i , 1 , ∇ p i , 1 ) + ν − 1 ( p i , 0 , p i , 0 ) ) . \int_{I_{n}}\inf_{p_{h}=p_{h,1}+p_{h,0}}\left(\tau^{-1}(\nabla p_{h,1},\nabla p_{h,1})+\nu^{-1}(p_{h,0},p_{h,0})\right)\kappa_{n}\,\mathrm{d}t
=\sum_{i=0}^{k_{t}}\inf_{p_{i}=p_{i,1}+p_{i,0}}\left(\tau^{-1}(\nabla p_{i,1},\nabla p_{i,1})+\nu^{-1}(p_{i,0},p_{i,0})\right). ∫ I n p h = p h , 1 + p h , 0 inf ( τ − 1 ( ∇ p h , 1 , ∇ p h , 1 ) + ν − 1 ( p h , 0 , p h , 0 ) ) κ n d t = i = 0 ∑ k t p i = p i , 1 + p i , 0 inf ( τ − 1 ( ∇ p i , 1 , ∇ p i , 1 ) + ν − 1 ( p i , 0 , p i , 0 ) ) .
The infimum for each i i i is attained by the unique p i , 1 ⋆ ∈ Q h p_{i,1}^{\star}\in Q_{h} p i , 1 ⋆ ∈ Q h that satisfies [17, Section 5.4]
τ − 1 ( ∇ p i , 1 ⋆ , ∇ r i ) + ν − 1 ( p i , 1 ⋆ , r i ) = ν − 1 ( p i , r i ) , \tau^{-1}(\nabla p_{i,1}^{\star},\nabla r_{i})+\nu^{-1}(p_{i,1}^{\star},r_{i})=\nu^{-1}(p_{i},r_{i}), τ − 1 ( ∇ p i , 1 ⋆ , ∇ r i ) + ν − 1 ( p i , 1 ⋆ , r i ) = ν − 1 ( p i , r i ) ,
for all r i ∈ Q h r_i \in Q_h r i ∈ Q h . Summing over i i i , and using that p h , 1 ∗ ( x , t ) = ∑ i = 0 k t ϕ i ( t ) p i , 1 ∗ ( x ) ∈ Q h p_{h,1}^{*}(x,t) = \sum_{i=0}^{k_t} \phi_i(t)p_{i,1}^{*}(x) \in Q_h p h , 1 ∗ ( x , t ) = ∑ i = 0 k t ϕ i ( t ) p i , 1 ∗ ( x ) ∈ Q h and r h ( x , t ) = ∑ i = 0 k t ϕ i ( t ) r i ( x ) ∈ Q h r_h(x,t) = \sum_{i=0}^{k_t} \phi_i(t)r_i(x) \in Q_h r h ( x , t ) = ∑ i = 0 k t ϕ i ( t ) r i ( x ) ∈ Q h ,
∫ I n ( τ − 1 ( ∇ p h , 1 ∗ , ∇ r h ) + ν − 1 ( p h , 1 ∗ , r h ) ) κ n d t = ∫ I n ν − 1 ( p h , r h ) κ n d t . (66) \int_{I_n} \left(\tau^{-1}(\nabla p_{h,1}^{*},\nabla r_h)+\nu^{-1}(p_{h,1}^{*},r_h)\right)\kappa_n\,\mathrm{d}t = \int_{I_n}\nu^{-1}(p_h,r_h)\kappa_n\,\mathrm{d}t. \tag*{(66)} ∫ I n ( τ − 1 ( ∇ p h , 1 ∗ , ∇ r h ) + ν − 1 ( p h , 1 ∗ , r h ) ) κ n d t = ∫ I n ν − 1 ( p h , r h ) κ n d t . (66)
Step 2. The infimum of the right hand side of eq. (55) is attained by the unique p h , 1 † ∈ Q h p_{h,1}^{\dagger} \in Q_h p h , 1 † ∈ Q h that satisfies
τ − 1 ∫ I n ( ∇ p h , 1 † , ∇ s h ) κ n d t + ν − 1 ∫ I n ( p h , 1 † , s h ) κ n d t = ν − 1 ∫ I n ( p h , s h ) κ n d t , (67) \tau^{-1}\int_{I_n}(\nabla p_{h,1}^{\dagger},\nabla s_h)\kappa_n\,\mathrm{d}t+\nu^{-1}\int_{I_n}(p_{h,1}^{\dagger},s_h)\kappa_n\,\mathrm{d}t=\nu^{-1}\int_{I_n}(p_h,s_h)\kappa_n\,\mathrm{d}t, \tag*{(67)} τ − 1 ∫ I n ( ∇ p h , 1 † , ∇ s h ) κ n d t + ν − 1 ∫ I n ( p h , 1 † , s h ) κ n d t = ν − 1 ∫ I n ( p h , s h ) κ n d t , (67)
for all s h ∈ Q h s_h \in Q_h s h ∈ Q h . Since eqs. (66) and (67) are the same equation, we conclude that p h , 1 ∗ = p h , 1 † p_{h,1}^{*}=p_{h,1}^{\dagger} p h , 1 ∗ = p h , 1 † and so eq. (55) holds.