Overlapping Schwarz and stable subspace decompositions

Write the vertices as $x_0,\dots ,x_d$, their barycentric coordinates as ${\lambda }_0,\dots ,{\lambda }_d$, and set ${\theta }_i=\theta (x_i)$ and $w_i=w(x_i)$. Since ${\sum }_i\mathrm{\nabla }{\lambda }_i=0$, $\mathrm{\nabla }{I}_K(\theta w)={\sum }_{i=1}^d({\theta }_i{w}_i-{\theta }_0{w}_0)\mathrm{\nabla }{\lambda }_i\mathrm{.}$ For each $i\ge 1$, ${\theta }_i{w}_i-{\theta }_0{w}_0={\theta }_i(w_i-w_0)+w_0({\theta }_i-{\theta }_0)$. Affineness gives $\mathrm{\mid }{w}_i-w_0\mathrm{\mid }\le h_K\mathrm{\mid }\mathrm{\nabla }w\mathrm{\mid }$ and $\mathrm{\mid }{\theta }_i-{\theta }_0\mathrm{\mid }\le h_K\mathrm{\mid }\mathrm{\nabla }\theta \mathrm{\mid }$. Applying [F2] to the barycentric gradients therefore gives pointwise $\mathrm{\mid }\mathrm{\nabla }{I}_K(\theta w)\mathrm{\mid }\le C({\max }_i\mathrm{\mid }{\theta }_i\mathrm{\mid }\mathrm{\mid }\mathrm{\nabla }w\mathrm{\mid }+{\max }_i\mathrm{\mid }{w}_i\mathrm{\mid }\mathrm{\mid }\mathrm{\nabla }\theta \mathrm{\mid })\mathrm{.}$

By [F3], the two vertex maxima in step 1.1 are at most $C{h}_K^{-d\mathrm{/}2}\mathrm{\parallel }\theta {\mathrm{\parallel }}_{L^2(K)}$ and $C{h}_K^{-d\mathrm{/}2}\mathrm{\parallel }w{\mathrm{\parallel }}_{L^2(K)}$, respectively. The gradients of affine functions are constant on $K$, so multiplying the pointwise estimate by $\mathrm{\mid }K{\mathrm{\mid }}^{1\mathrm{/}2}\asymp h_K^{d\mathrm{/}2}$ yields $\mathrm{\parallel }\mathrm{\nabla }{I}_K(\theta w){\mathrm{\parallel }}_{L^2(K)}\le C(\mathrm{\mid }\mathrm{\nabla }w\mathrm{\mid }\mathrm{\parallel }\theta {\mathrm{\parallel }}_{L^2(K)}+\mathrm{\mid }\mathrm{\nabla }\theta \mathrm{\mid }\mathrm{\parallel }w{\mathrm{\parallel }}_{L^2(K)}),$ which is the asserted estimate.

Fix any $i\in \mathcal{I}$ with $i\mathrm{\ne }0$ and any nonzero $z\in {\mathbb{R}}^{n_i}$. Full column rank in [F1] gives $R_{i}z\mathrm{\ne }0$, so $z^{\mathsf{T}}{A}_{i}z=(R_{i}z{)}^{\mathsf{T}}A(R_{i}z)>0.$ Also [F4] gives $A_i^{\mathsf{T}}=R_i^{\mathsf{T}}{A}^{\mathsf{T}}{R}_i=A_i$. Thus every such $A_i$ is SPD.

If $0\in \mathcal{I}$, then $R_0=P$ and [F2] gives that $A_0=P^{\mathsf{T}}AP$ is SPD and the exact coarse solve is defined. If $0\mathrm{\notin }\mathcal{I}$, no separate coarse matrix is part of the one-level definition.

By [F3], every SPD $A_i$ in step 1.1 or 1.2 has a unique solution for each local right-hand side. Therefore all exact local solves in Finite-dimensional Schwarz subspace-correction data are well-defined.

In a coordinate cube, the stated simplices are the regions where the normalized coordinates have one fixed weak ordering. For each coordinate pair, a coarse ordering hyperplane can meet the interior of a fine cube only when the two fine-cell indices agree; there it is the local equality hyperplane used by the fine Freudenthal triangulation. Thus every fine simplex lies in one coarse simplex. The induced order triangulation on a coordinate face is the same from either incident cube, so the meshes match. The reference simplices come from finitely many coordinate permutations, so their shape-regularity constants are bounded by a number depending only on $d$. By [F3], the continuous P1 spaces are nested. Their boundary nodal values vanish; [F4] places both spaces in $H_0^1(\mathrm{\Omega })$.

Let $J_H$ be the face-average Scott–Zhang map of [F1], set $u_0=J_H{u}_h$, and $w=u_h-u_0\in V_h$. Each coarse element patch ${\omega }_K$ meets only coarse cubes whose coordinate indices differ from that of $K$ by at most one. Thus at most $M_d=3^{d}d!$ coarse simplex patches contain a fixed point. Squaring and summing [F1] over the coarse mesh gives $\mathrm{\parallel }w{\mathrm{\parallel }}_{L^2(\mathrm{\Omega })}\le C_{S}H\mathrm{\parallel }\mathrm{\nabla }{u}_h{\mathrm{\parallel }}_{L^2(\mathrm{\Omega })},\mathrm{\parallel }\mathrm{\nabla }{u}_0{\mathrm{\parallel }}_{L^2(\mathrm{\Omega })}\le C_S\mathrm{\parallel }\mathrm{\nabla }{u}_h{\mathrm{\parallel }}_{L^2(\mathrm{\Omega })}$ for a constant $C_S$ depending only on $d$ and shape regularity. The second inequality is the global stability part of [F1]. The stated Countable Choice assumption supplies the choice principle required by the Scott–Zhang and Sobolev-trace suppliers in [F1].

For each coarse cube define ${\psi }_j(x)=\max (0,1-\frac{{\mathrm{dist}}_{\mathrm{\infty }}(x,Q_j)}{\delta }),{\eta }_j(x)=\frac{{\psi }_j(x)}{{\sum }_k{\psi }_k(x)}\mathrm{.}$ At every $x\in \mathrm{\Omega }$, at least one coarse cube contains $x$, so the denominator is at least $1$. Since $\delta \le a$, at most $4^d$ functions ${\psi }_k$ are nonzero at a point; each is $1\mathrm{/}\delta$-Lipschitz. The quotient rule for Lipschitz functions with denominator at least $1$ gives $0\le {\eta }_j\le 1$, ${\sum }_j{\eta }_j=1$, and $\mathrm{\parallel }\mathrm{\nabla }{\eta }_j{\mathrm{\parallel }}_{L^{\mathrm{\infty }}}\le (1+4^d)\mathrm{/}\delta$ almost everywhere. Let ${\theta }_j=I_h{\eta }_j$ be its fine-grid nodal P1 interpolant. The nodal values sum to one, hence ${\sum }_j{\theta }_j=1$ on every fine simplex; barycentric coordinates give $0\le {\theta }_j\le 1$. On a fine simplex with vertices $x_0,\dots ,x_d$ and barycentric coordinates ${\lambda }_i$, $\mathrm{\nabla }{\theta }_j={\sum }_{i=1}^d({\eta }_j(x_i)-{\eta }_j(x_0))\mathrm{\nabla }{\lambda }_i\mathrm{.}$ The Lipschitz bound and [F6] imply $\mathrm{\parallel }\mathrm{\nabla }{\theta }_j{\mathrm{\parallel }}_{L^{\mathrm{\infty }}(K)}\le C_{\theta }\mathrm{/}\delta$ for a constant $C_{\theta }$ depending only on dimension and shape regularity. If ${\theta }_j$ is nonzero on a fine simplex, one of its vertices lies within ${\mathrm{\ell }}^{\mathrm{\infty }}$ distance $\delta$ of $Q_j$, so the whole simplex lies in ${\mathrm{\Omega }}_j$ by the added radius $h$. At most $N=7^d$ expanded coarse cubes contain any point: in each coordinate their side length is at most $a+2(\delta +h)\le 5a$, so at most seven grid intervals can contain that coordinate. Every clipped expanded cube has side lengths between $a$ and $5a$, so its aspect ratio is at most $5$; hence these subdomains are uniformly shape-regular and have diameter at most $5H$.

At every fine-grid vertex, ${\sum }_j{\theta }_{j}w=w$. The nodal interpolant is linear on each fine simplex, so the local functions $u_j=I_h({\theta }_{j}w)$ satisfy ${\sum }_j{u}_j=w$. Each $u_j$ is supported in ${\mathrm{\Omega }}_j$. At a boundary vertex $w=0$, since $u_h,u_0\in V_h$; hence every $u_j$ has zero boundary nodal values and belongs to $H_0^1(\mathrm{\Omega })$ by [F4]. Thus $u_h=u_0+{\sum }_j{u}_j$ is a decomposition in the stated spaces.

Apply [F2] elementwise and $(s+t{)}^2\le 2s^2+2t^2$: ${\sum }_j\mathrm{\parallel }\mathrm{\nabla }{u}_j{\mathrm{\parallel }}_{L^2(\mathrm{\Omega })}^2\le 2C_P^{2}N(\mathrm{\parallel }\mathrm{\nabla }w{\mathrm{\parallel }}_{L^2(\mathrm{\Omega })}^2+\frac{C_{\theta }^2}{{\delta }^2}\mathrm{\parallel }w{\mathrm{\parallel }}_{L^2(\mathrm{\Omega })}^2)\mathrm{.}$ Indeed, each point belongs to at most $N$ supports, $0\le {\theta }_j\le 1$, and $\mathrm{\mid }\mathrm{\nabla }{\theta }_j\mathrm{\mid }\le C_{\theta }\mathrm{/}\delta$. Also $\mathrm{\parallel }\mathrm{\nabla }w{\mathrm{\parallel }}_2\le (1+C_S)\mathrm{\parallel }\mathrm{\nabla }{u}_h{\mathrm{\parallel }}_2$ by step 1.2.

Substitute the two estimates of step 1.2 into step 2.2 and add $\mathrm{\parallel }\mathrm{\nabla }{u}_0{\mathrm{\parallel }}_2^2\le C_S^2\mathrm{\parallel }\mathrm{\nabla }{u}_h{\mathrm{\parallel }}_2^2$. With $C_{\mathrm{F}\mathrm{E}}=1+C_S^2+2C_P^{2}N((1+C_S{)}^2+C_{\theta }^2{C}_S^2),$ the result is $\mathrm{\parallel }\mathrm{\nabla }{u}_0{\mathrm{\parallel }}_2^2+{\sum }_j\mathrm{\parallel }\mathrm{\nabla }{u}_j{\mathrm{\parallel }}_2^2\le C_{\mathrm{F}\mathrm{E}}(1+(H\mathrm{/}\delta {)}^2)\mathrm{\parallel }\mathrm{\nabla }{u}_h{\mathrm{\parallel }}_2^2\mathrm{.}$ This is the asserted stable-decomposition bound.

Fix $i\in \mathcal{I}$ with $i\mathrm{\ne }0$. Multiplication using [F1] gives ${\mathrm{\Pi }}_i^2=R_i{A}_i^{-1}(R_i^{\mathsf{T}}A{R}_i)A_i^{-1}{R}_i^{\mathsf{T}}A={\mathrm{\Pi }}_i\mathrm{.}$ By [F2], $A_i^{-1}$ is symmetric; [F4] therefore gives ${\mathrm{\Pi }}_i^{\mathsf{T}}A=A{\mathrm{\Pi }}_i$. Its range is contained in $\mathrm{Ran}(R_i)$, and ${\mathrm{\Pi }}_i{R}_i=R_i$, so its range is exactly $V_i$.

If $0\in \mathcal{I}$, write ${\mathrm{\Pi }}_0=I-C$ with $C$ from [F3]. Since $C^2=C$ and $C$ is $A$-self-adjoint, $I-C$ is also idempotent and $A$-self-adjoint. Moreover, $\mathrm{Ran}(I-C)=\ker C=\mathrm{Ran}(P)$ because $C$ projects onto $\mathrm{Ran}(P{)}^{{\perp }_A}$. Thus ${\mathrm{\Pi }}_0$ is the $A$-orthogonal projection onto $V_0$. If $0\mathrm{\notin }\mathcal{I}$, there is no coarse projection to check.

For every present index $i$, idempotence and $A$-self-adjointness give $a({\mathrm{\Pi }}_{i}x,(I-{\mathrm{\Pi }}_i)x)=a(x,{\mathrm{\Pi }}_i(I-{\mathrm{\Pi }}_i)x)=0$. Expanding the squared norm of $x={\mathrm{\Pi }}_{i}x+(I-{\mathrm{\Pi }}_i)x$ proves the Pythagorean identity. Also $a({\mathrm{\Pi }}_{i}x,x)=a({\mathrm{\Pi }}_{i}x,{\mathrm{\Pi }}_{i}x)$ by the same orthogonality.

The block matrix $\mathcal{D}$ is SPD by [F2]. The spanning assumption makes the concatenated map $R$ surjective. If $x^{\mathsf{T}}Bx=0$, then $0=(R^{\mathsf{T}}x{)}^{\mathsf{T}}{\mathcal{D}}^{-1}(R^{\mathsf{T}}x),$ so $R^{\mathsf{T}}x=0$ because ${\mathcal{D}}^{-1}$ is SPD. Surjectivity of $R$ then gives $x=0$. Thus $B$ is SPD and has an inverse.

For fixed $x$, define $z_{\ast }={\mathcal{D}}^{-1}{R}^{\mathsf{T}}{B}^{-1}x$. Then $R{z}_{\ast }=B{B}^{-1}x=x$, so it is feasible. For any other feasible $z$, write $w=z-z_{\ast }$. Then $Rw=0$ and $z_{\ast }^{\mathsf{T}}\mathcal{D}w=x^{\mathsf{T}}{B}^{-1}Rw=0$. Therefore $z^{\mathsf{T}}\mathcal{D}z=z_{\ast }^{\mathsf{T}}\mathcal{D}{z}_{\ast }+w^{\mathsf{T}}\mathcal{D}w\ge z_{\ast }^{\mathsf{T}}\mathcal{D}{z}_{\ast }$. Direct multiplication gives $z_{\ast }^{\mathsf{T}}\mathcal{D}{z}_{\ast }=x^{\mathsf{T}}{B}^{-1}x$. This proves the minimum identity.

The stable-decomposition hypothesis implies that the local spaces span $V$, so [F3] makes $B$ SPD. Each ${\mathrm{\Pi }}_i$ is $A$-self-adjoint by [F2], hence $T=BA={\sum }_i{\mathrm{\Pi }}_i$ is $A$-self-adjoint. Moreover $a(Tx,x)={\sum }_i\mathrm{\parallel }{\mathrm{\Pi }}_{i}x{\mathrm{\parallel }}_A^2\ge 0$; if this is zero, then every ${\mathrm{\Pi }}_{i}x=0$. For any $v_i\in V_i$, [F2] gives ${\mathrm{\Pi }}_i{v}_i=v_i$, so $a(x,v_i)=a({\mathrm{\Pi }}_{i}x,v_i)=0$. The spaces span $V$, hence $x=0$ and $T$ is positive.

Fix $x\mathrm{\ne }0$ and choose the decomposition $x={\sum }_i{R}_i{z}_i$ from the stable-decomposition hypothesis. Orthogonal projection gives $\mathrm{\parallel }x{\mathrm{\parallel }}_A^2={\sum }_{i}a(x,R_i{z}_i)={\sum }_{i}a({\mathrm{\Pi }}_{i}x,R_i{z}_i)\le {\left({\sum }_i\mathrm{\parallel }{\mathrm{\Pi }}_{i}x{\mathrm{\parallel }}_A^2\right)}^{1\mathrm{/}2}{\left({\sum }_i{z}_i^{\mathsf{T}}{A}_i{z}_i\right)}^{1\mathrm{/}2}\mathrm{.}$ The last inequality is [F5] in the product inner product on the finite tuple space. The assumed bound on the second factor yields $a(Tx,x)={\sum }_i\mathrm{\parallel }{\mathrm{\Pi }}_{i}x{\mathrm{\parallel }}_A^2\ge C_0^{-1}\mathrm{\parallel }x{\mathrm{\parallel }}_A^2$, proving the lower Rayleigh bound.

For each $x$, write ${\mathrm{\Pi }}_{i}x=R_i{y}_i$ with $y_i=A_i^{-1}{R}_i^{\mathsf{T}}Ax$. The synthesis hypothesis and [F2] give $\mathrm{\parallel }Tx{\mathrm{\parallel }}_A^2={\parallel {\sum }_i{R}_i{y}_i\parallel }_A^2\le C_1{\sum }_i\mathrm{\parallel }{\mathrm{\Pi }}_{i}x{\mathrm{\parallel }}_A^2=C_{1}a(Tx,x)\mathrm{.}$ Set $q=a(Tx,x)\mathrm{/}\mathrm{\parallel }x{\mathrm{\parallel }}_A^2$. [F5] gives $q\mathrm{\parallel }x{\mathrm{\parallel }}_A\le \mathrm{\parallel }Tx{\mathrm{\parallel }}_A$, while the displayed inequality gives $\mathrm{\parallel }Tx{\mathrm{\parallel }}_A^2\le C_{1}q\mathrm{\parallel }x{\mathrm{\parallel }}_A^2$. If $q>0$, these imply $q\le C_1$; if $q=0$, the same upper bound is immediate.

By [F4] and the assumed lower order bound, every ${\tilde{A}}_i$ is SPD. For every SPD matrix $M$ and vector $y$, $y^{\mathsf{T}}{M}^{-1}y={\max }_z(2y^{\mathsf{T}}z-z^{\mathsf{T}}Mz),$ because completing the square subtracts $(z-M^{-1}y{)}^{\mathsf{T}}M(z-M^{-1}y)$. Since ${\tilde{A}}_i⪯\beta A_i$, this maximum for ${\tilde{A}}_i$ is at least the maximum for $\beta A_i$, namely ${\beta }^{-1}{y}^{\mathsf{T}}{A}_i^{-1}y$; since $\alpha A_i⪯{\tilde{A}}_i$, it is at most the maximum for $\alpha A_i$, namely ${\alpha }^{-1}{y}^{\mathsf{T}}{A}_i^{-1}y$. Thus ${\beta }^{-1}{A}_i^{-1}⪯{\tilde{A}}_i^{-1}⪯{\alpha }^{-1}{A}_i^{-1}$. Summing after congruence by $R_i$ yields ${\beta }^{-1}B⪯\tilde{B}⪯{\alpha }^{-1}B$.

Step 1.4 establishes that each inverse in $\tilde{B}$ is SPD. By the stable-decomposition hypothesis, the local spaces span $V$; hence if $x\mathrm{\ne }0$ then $R_i^{\mathsf{T}}x\mathrm{\ne }0$ for some $i$, since otherwise $x$ would be Euclidean-orthogonal to their span $V$. Therefore $x^{\mathsf{T}}\tilde{B}x={\sum }_i(R_i^{\mathsf{T}}x{)}^{\mathsf{T}}{\tilde{A}}_i^{-1}(R_i^{\mathsf{T}}x)>0$, so $\tilde{B}$ is symmetric positive definite. It follows that $\tilde{B}A$ is $A$-self-adjoint and positive, because $A\tilde{B}A$ is symmetric positive definite; the inexact Rayleigh quotient and condition number are therefore defined. The matrix comparison in step 1.4 bounds $a(\tilde{B}Ax,x)=x^{\mathsf{T}}A\tilde{B}Ax$ below by ${\beta }^{-1}{x}^{\mathsf{T}}ABAx$ and above by ${\alpha }^{-1}{x}^{\mathsf{T}}ABAx$. The exact bounds in steps 1.2 and 1.3 therefore give the stated inexact minimum, maximum, and condition-ratio bounds.

For an arbitrary initial error $x$, set $e_{-1}=x$, $d_0={\mathrm{\Pi }}_{0}x$, and $e_0=x-d_0$. For $i=1,\dots ,m$, set $d_i={\mathrm{\Pi }}_i{e}_{i-1}$ and $e_i=e_{i-1}-d_i$. By [F2], each correction is orthogonal to its updated error, so telescoping gives $D:={\sum }_{i=0}^m\mathrm{\parallel }{d}_i{\mathrm{\parallel }}_A^2=\mathrm{\parallel }x{\mathrm{\parallel }}_A^2-\mathrm{\parallel }{e}_m{\mathrm{\parallel }}_A^2\mathrm{.}$ Also $e_{i-1}=x-d_0-{\sum }_{j=1}^{i-1}{d}_j$.

Fix a local index $i\ge 1$ and set $b_i=\mathrm{\parallel }{\mathrm{\Pi }}_{i}x{\mathrm{\parallel }}_A$, $c_i=\mathrm{\parallel }{d}_i{\mathrm{\parallel }}_A$, and $q_i=\mathrm{\parallel }{\mathrm{\Pi }}_i{d}_0{\mathrm{\parallel }}_A$. Since $x=e_{i-1}+d_0+{\sum }_{j<i}{d}_j$ and ${\mathrm{\Pi }}_i$ is an orthogonal projection, $a({\mathrm{\Pi }}_{i}x,e_{i-1})=a({\mathrm{\Pi }}_{i}x,{\mathrm{\Pi }}_i{e}_{i-1})=a({\mathrm{\Pi }}_{i}x,d_i)$ and $a({\mathrm{\Pi }}_{i}x,d_0)=a({\mathrm{\Pi }}_{i}x,{\mathrm{\Pi }}_i{d}_0)$. Thus $b_i^2=a({\mathrm{\Pi }}_{i}x,d_i)+a({\mathrm{\Pi }}_{i}x,{\mathrm{\Pi }}_i{d}_0)+{\sum }_{j<i}a({\mathrm{\Pi }}_{i}x,d_j)$. The first term has absolute value at most $b_i{c}_i$ and the second at most $b_i{q}_i$ by [F4]; the remaining terms are at most $b_i{\sum }_{j<i}{ϵ}_{ij}{c}_j$ by [A2]. If $b_i=0$ the resulting bound is immediate; otherwise divide by $b_i$ to obtain $b_i\le c_i+q_i+{\sum }_{j<i}{ϵ}_{ij}{c}_j\mathrm{.}$

Let $L$ be the strict lower-triangular part of $G$, and let $b,c,q\in {\mathbb{R}}^m$ have entries $b_i,c_i,q_i$. They are nonnegative and $0\le Lc\le Gc$ entrywise. Hence $\mathrm{\parallel }Lc{\mathrm{\parallel }}_2\le \mathrm{\parallel }Gc{\mathrm{\parallel }}_2\le \rho \mathrm{\parallel }c{\mathrm{\parallel }}_2$, and step 2.1 yields $\mathrm{\parallel }b{\mathrm{\parallel }}_2\le (1+\rho )\mathrm{\parallel }c{\mathrm{\parallel }}_2+\mathrm{\parallel }q{\mathrm{\parallel }}_2\mathrm{.}$ Furthermore, by [F2], $\mathrm{\parallel }q{\mathrm{\parallel }}_2^2={\sum }_{i=1}^{m}a({\mathrm{\Pi }}_i{d}_0,d_0)=a({\sum }_{i=1}^m{\mathrm{\Pi }}_i{d}_0,d_0)\le a(T{d}_0,d_0)\le C_1\mathrm{\parallel }{d}_0{\mathrm{\parallel }}_A^2\mathrm{.}$ The first inequality uses that ${\mathrm{\Pi }}_0$ is positive semidefinite; the last is [F3].