CBS Constants & Their Role in Error Estimation for Stochastic Galerkin Finite Element Methods

The motivation for this work is the design of efficient a posteriori error estimators for adaptive Galerkin finite element approximation of solutions to partial differential equations (PDEs). In particular, we are interested in PDEs with random inputs and so-called stochastic Galerkin finite element methods (SGFEMs) (see [4, 5, 14, 22, 24, 31]). When the inputs are represented by a finite, or countably infinite number of random variables \(\xi _{m}: \varOmega \rightarrow \mathbb {R}\), \(m=1,2,\ldots ,\) where \(\varOmega \) is a sample space, it is conventional to reformulate the stochastic problem of interest as a high-dimensional deterministic one, whose solution depends on a set of parameters \(y_{m}=\xi _{m}(\omega )\). Unlike sampling methods such as Monte Carlo, in the SGFEM approach, an approximation is sought in a tensor product space of the form \(H_1 \otimes P\) where \(H_1\) is an appropriate finite element space associated with the spatial domain and P is a set of polynomials associated with the parameter domain. When the number of active parameters is high, the dimension of \(H_1 \otimes P\) for standard choices of \(H_1\) and P can become unwieldy. To remedy this, we can either work with standard approximation spaces and deal with the resulting very large discrete systems by using smart linear algebra techniques (see [20, 21, 25, 26, 32, 33]), or we can use an adaptive approach, starting in a low-dimensional space \(H_1^{0} \otimes P^{0}\), and using a posteriori error estimators to decide whether it is necessary to enrich \(H_1^{0}\) or \(P^{0}\), or both. This allows us to build up a tailored sequence of approximation spaces \(H_1^{\ell } \otimes P^{\ell }, \ell =0,1, \ldots \) incrementally, so that the dimension of the final space is balanced against an error tolerance for a quantity of interest.

We consider the steady-state stochastic diffusion problem. Let \(D\subset \mathbb {R}^{2,3}\) be a bounded spatial domain and let \(\mathbf {y}=[y_1,y_2,\dots ]\) be a vector-valued parameter which takes values in \(\varGamma = \prod _{m=1}^{\infty }\varGamma _m\) (the parameter domain). We want to approximate the function \(u:D\times \varGamma \rightarrow \mathbb {R}\) that satisfies For simplicity, we assume that \(f=f(\mathbf {x})\) is independent of \(\mathbf {y}\), but the methodologies discussed herein can be extended to accommodate \(f = f(\mathbf {x},\mathbf {y})\). We also assume that the parameters are bounded, with \(y_{m} \in \varGamma _m = [-1,1]\). We denote by \(\pi (\mathbf {y})\) a product measure on \((\varGamma ,\mathcal {B}(\varGamma ))\), where \(\mathcal {B}(\varGamma )\) is the Borel \(\sigma \)-algebra on \(\varGamma \), so that \(\pi (\mathbf {y})=\prod _{m=1}^{\infty }\pi _m(y_m),\) where \(\pi _m(y_m)\) is a measure on \((\varGamma _m,\mathcal {B}(\varGamma _m))\). In addition,which is true when \(y_m\) is the image of a mean zero random variable and \(\pi _m(y_m)\) is the associated probability measure.

The parameter-free function \(a_0(\mathbf {x})\) typically represents the mean with each term \(a_m(\mathbf {x})y_m\) representing a perturbation away from the mean, while (5) helps ensure the well posedness of the weak formulation of (1a)–(1b).

Next, we recall the classical strengthened Cauchy–Buniakowskii–Schwarz (CBS) inequality (see [1, Theorem 5.4]), a key tool in many areas of numerical analysis.

The smallest constant \(\gamma \in [0,1)\) satisfying (6) isand is known as the CBS constant. In particular, CBS constants appear in the analysis of hierarchical preconditioners (see [2, 3, 30]) and certain types of a posteriori error estimators for Galerkin finite element approximations to PDEs. See, for example, [1, 19, 27, 28].

The design of error estimators for SGFEMs for parameter-dependent PDEs is still under development. However, there have been a few recent works (see [8‐12, 16‐18, 29]) for the model problem (1a)–(1b). In [12] and [11], algorithms constructing so-called sparse SGFEM approximations are driven by a priori error analysis, where the error associated with each discretisation parameter is balanced against the total number of degrees of freedom. In [16] and [17] a general framework for an explicit residual-based error estimation strategy for SGFEMs is proposed, where the selection of hierarchical approximation spaces is driven by a Dörfler marking strategy [15] on both the spatial and parameter domains. In both works, overestimation up to a factor of 10 of the true error is reported. In [18] a similar approach is taken, where residuals are computed using an equilibrated fluxes strategy and overestimation up to a factor of 5 is reported.

We focus on the (implicit) approach taken in [8‐10] which is based on solving local subproblems for the error over a ‘detail’ space. The bound for the effectivity index of the resulting error estimators depends on a CBS constant. In [8‐10] no insight into which choices of detail space result in a sharp error bound (effectivity indices close to one) is given. In this paper we provide that analysis. Specifically, we provide detailed information about the CBS constant and derive theoretical bounds for it, for certain choices of SGFEM solution and detail spaces. Due to the way that the spaces associated with the parameter domain are chosen, the CBS constants needed to analyse the estimators in [8‐10] depend only on a pair of finite element spaces on the spatial domain. Hence, our results are also applicable to the design of adaptive finite element schemes for deterministic PDEs. We investigate which choices of detail FEM space result in CBS constants close to zero, to help ensure a sharp error bound. In particular, due to cost restrictions imposed to avoid high-dimensional detail spaces, we investigate non-standard choices that aren’t typically considered in the deterministic setting. The error estimation strategy in [29] also relies on a CBS constant, but in a different setting. Enrichment of the finite element space is not considered.

The following classical results from [1, 6], along with Theorem 1, form the foundations of our main investigation in Sects. 3, 4, 5, 6. Let V be a Hilbert space with norm \(||\cdot ||_V\) and let \(B:V\times V\rightarrow \mathbb {R}\) and \(F:V\rightarrow \mathbb {R}\) denote a bounded and coercive bilinear form and linear functional, respectively. Consider the problem:We assume that \(B(\cdot ,\cdot )\) is an inner product on V with the ‘energy’ normand that (8) is uniquely solvable. We now seek a Galerkin approximation to \(u\in V\). Let X be an \(N_X\)–dimensional subspace of V. We then solve:Computing the error \(e = u-u_X\in V\) is a non-trivial task. Our goal is to estimate the energy error \(||e||_B\). Clearly, e satisfies the problem:where \(u_X\in X\) is the Galerkin approximation satisfying (9).

Now suppose we choose a second subspace \(W\subset V\) of dimension \(N_W\), where \(X \subset W\) (i.e., W is richer than X) and consider the following problem:By letting \(e_W = u_{W} - u_X\) we see thatNote that (12) is simply a restatement of (10) over W. We deduce then that the function \(e_W\in W\) satisfying (12) estimates the true error \(e\in V\) satisfying (10). Whilst we do not compute \(u_W\), it is clear that the quality of that Galerkin approximation (and hence the choice of W) determines the quality of the estimator \(e_W\). To analyse this, we require the following assumption.

In many applications, Assumption 2 is reasonable (see [1, p. 88]). The relationship between \(||e||_B\) and \(||e_W||_B\) is summarised in the next result.

The interpretation of (14) is as follows; \(||e_W||_B\) will never overestimate the true error \(||e||_B\), but could underestimate it by a factor of \((1-\beta ^2)^{-1/2}\).

Problem (12) leads to a linear system of \(N_W\) equations which may be too expensive to solve. This is the case for the problem considered in Sect. 3. Suppose then that \(B_0:V\times V\rightarrow \mathbb {R}\) is an inner product with induced norm \(||\cdot ||_{B_0} = B_0(\cdot ,\cdot )^{1/2}\), whose matrix representation on W is more convenient to work with. We may then consider the alternative problem:The next result summarises the relationship between \(||e_W||_B\) and \(||e_0||_{B_0}\).

Even after replacing \(B(\cdot , \cdot )\) with \(B_{0}(\cdot , \cdot )\), since \(W\supset X\), it may be more expensive to compute \(e_0\in W\) satisfying (15) than \(u_X\in X\) satisfying (9). To reduce the cost further, we insist thatwhere the ‘detail’ space \(Y\subset V\) has dimension \(N_Y\) and consider the lower-dimensional problem:Does \(||e_Y||_{B_0}\) provide a good estimate for \(||e||_{B}\)? To answer this, we require Theorem 1. Since \(X\cap Y = \{0\}\), there exists a constant \(\gamma \in [0,1)\) such thatThe estimates \(||e_Y||_{B_0}\) and \(||e_0||_{B_0}\) are then related by the following theorem.

If X and Y are orthogonal with respect to the inner product \(B_0(\cdot ,\cdot )\) then \(\gamma = 0\) and \(||e_Y||_{B_0} = ||e_0||_{B_0}\). Consolidating Theorems 2–4 yields the final result.

In summary, the quality of the energy error estimate \(||e_Y||_{B_0}\) is determined by two constants \(\beta \) and \(\gamma \), which both depend on X and Y. Ideally, we want \(\sqrt{1-\beta ^2}\sqrt{1-\gamma ^2} \approx 1\). Given a fixed initial approximation space X, what is the best choice of detail space Y, from the point of view of obtaining the best possible error estimate? This is the essence of our investigation.

The variational formulation of (1a)–(1b) is:where \(H_{0}^{1}(D)\) is the usual Hilbert space and \(L_{\pi }^2(\varGamma )\) is given byV is equipped with the norm \(|| \cdot ||_V\), where \(||v||_V^2 = \int _{\varGamma }||v(\cdot ,\mathbf {y})||_{H_0^1(D)}^2\ d\pi (\mathbf {y})\) and the bilinear form \(B:V\times V\rightarrow \mathbb {R}\) and the linear functional \(F:V\rightarrow \mathbb {R}\) are given by To ensure that (23) is well-posed, we make the following assumption.

If Assumption 3 holds, the bilinear form \(B(\cdot ,\cdot )\) defined in (24) induces a norm \({||\cdot ||_B = B(\cdot ,\cdot )^{1/2}}\) (the energy norm). Note that due to (3), we have the decompositionfor all \(u,v\in V\), where the component bilinear forms are defined by If (4) in Assumption 1 holds, then \(B_0(\cdot ,\cdot )\) in (27a) also induces a norm \(||\cdot ||_{B_0} = B_0(\cdot ,\cdot )^{1/2}\). Moreover, the following norm equivalence holds:where \(0< \lambda< 1< \varLambda < \infty \) and

The constant \(\gamma \in [0, 1)\) in (34) and (44), which is equivalent to the constant \(\gamma \in [0, 1)\) satisfying (39), is not unique. Given \(H_1\) and \(H_2\), we want to find the smallest such constant, the CBS constant. We now recall a standard result from [19] which leads to a numerical method for computing the CBS constant associated with (39).

Suppose first that \(M\in \mathbb {R}^{N\times N}\) is symmetric and positive definite with \(N:=m+n\) for \(m,n\in \mathbb {N}\). Then \((\mathbb {R}^N,(\cdot ,\cdot )_{M})\) is a Hilbert space with respect to the inner product \((\mathbf {u},\mathbf {v})_{M}:=\mathbf {u}^\top M\mathbf {v}\). Now consider \(U,V\subset \mathbb {R}^N\) given bywhich satisfies \(U\cap V = \{\mathbf{0}\}\). When M has a particular block structure, Theorem 1 along with U and V in (46), leads to the following result (see [19] for a proof).

We now demonstrate that the CBS constant associated with (39) for various choices of \(H_1\) and \(H_2\) can be computed by solving an eigenvalue problem of the form (49). Recall that \(H_1, H_2\subset H_{0}^{1}(D)\) with \(H_1\cap H_2 = \{0\}\). For now, we assume \(a_0(\mathbf {x}) = 1\). Note that due to the symmetry of (38) we may compute the CBS constant associated with the equivalent result; there exists a \(\gamma \in [0,1)\) such thatGiven \(H_1 := \text {span}\{\phi _i(\mathbf {x})\}_{i=1}^n\) and \(H_2 := \text {span}\{\psi _i(\mathbf {x})\}_{i=1}^m\), we can define the augmented subspaceof dimension \(N=m+n\). We have \(H = \text {span}\{\varPhi _i(\mathbf {x})\}_{i=1}^N\), where \(\varPhi _i = \psi _i,\) for \(i=1,2,\dots ,m\), and \(\varPhi _{m+i} = \phi _i\), for \(i=1,2,\dots ,n.\) Then, for all \(u\in H_2\) and \(v\in H_1\), \(\langle u,v\rangle = \mathbf {u}^{\top }M\mathbf {v}\) for some \(\mathbf {u}\in U\) and \(\mathbf {v}\in V\) in (46).

The matrix \(M\in \mathbb {R}^{N\times N}\) is symmetric and positive definite and has the structure (47) with \([A]_{ij} = \langle \phi _{i}, \phi _{j}\rangle \), for \(i,j=1,\ldots ,n\), \([B]_{ij} = \langle \psi _{i}, \psi _{j}\rangle \) for \(i,j=1,\ldots , m\) and \([C]_{ij} = \langle \phi _{i}, \psi _{j}\rangle \) for \(i=1,\ldots , n\) and \(j=1,\ldots , m\). By Corollary 1, there exists a constant \(\gamma \in [0,1)\) such that (48) holds, which is equivalent to (50). Therefore, the CBS constant \(\gamma _{\min }\) satisfying (50) can be computed numerically by solving the eigenvalue problem (49).

Given a fixed space \(H_1\) associated with a uniform mesh \(\mathcal {T}_h\) on the spatial domain D, we construct \(H_2\) element-wise. That is, we insist that \(H_2\) admits the decompositionwhere \(\Box _k\) denotes an element in \(\mathcal {T}_h\). We choose the functions \(\psi _{i}^{k}\) to be bubble functions so that \(H_{k,2}\) contains functions which only have non-zero support on \(\square _{k}\). The linear system associated with the estimator \(e_{Y_{1}}\) satisfying (35) then decouples. Since \(e_{Y_{1}} \in Y_{1}:=H_2\otimes P\), on each \(\Box _{k}\), we have to solve a problem of size \(m_{k} \times \text {dim}(P)\). Since \(\text {dim}(P)\) may be large, to keep costs reasonable, we must restrict the dimension of \(H_{k,2}\). Note that the necessity to restrict the dimension of \(H_2\) is not as prevalent in the deterministic PDE setting, where each local problem for the analogous error estimate is of dimension \(m_k\), not \(m_{k} \times \text {dim}(P)\). The goal is to find the best space (the one leading to the tightest error bound), of a fixed small dimension. Below, we fix \(H_{1}\) and consider various choices of \(H_{2}\) of the same dimension. We vary the mesh size h, and estimate the CBS constant by solving the eigenvalue problem (49).

In this section we fix \(H_{k,1}\) to be the local \(\mathbb {Q}_{1}\) finite element space so that \(A_k\) is given by (58) and assume that the degrees of freedom are numbered as shown in Fig. 3. We also assume that \(H_{k,2}\) is chosen so that dim\((H_{k,2})=5\) and the resulting matrices \(B_k\) and \(C_k\) have a particular structure. Exploiting this structure, and using only linear algebra arguments, we show that the local CBS constant \(\gamma _{k,\min }\) can be calculated analytically without assembling and solving (57). To simplify notation, we drop the subscript k.

The next results show that if the matrices B and C have certain structures, then \(CB^{-1}C^{\top }\) always has the structure (60) and an explicit expression is available for the constant \(\beta \) in (65), and hence the CBS constant.

Combining the last two results, we see that to compute the CBS constant, we only need to know \(\alpha \) (one entry of C) and \(\alpha _{1}\) and \(\alpha _{3}\) (two entries of the first column of \(B^{-1}\)). We can determine the latter analytically by exploiting the spectral decomposition for circulant matrices. Lemma 2 is standard (for example, see [13]) and we apply it to \(\bar{B}\) in (69) in Lemma 3.

Combining the above results, gives the following final result.

The matrices B and C associated with the examples in Sect. 4.1 (corresponding to the four choices of \(H_{k,2}\) from Example 1) all have the desired structure. The associated values of \(\alpha , b_{1}\) and \(b_{3},\) and the squares of the CBS constants are recorded in Table 3 (to stress that these are local quantities we reintroduce the subscript k). The results match the numerical estimates obtained in Sect. 4.1. With the new approach, the matrices A, B and C do not need to be assembled, and no eigenvalue problem needs to be solved.

We now return to (1a)–(1b) and assess the quality of the energy error estimator \(\eta \) in (37), extending the discussion in [8] and [10]. First, we select \(X= H_1\otimes P\) and compute \(u_X\in X\) by solving (9). We choose either \(H_1=\mathbb {Q}_1(h)\) or \(H_1=\mathbb {Q}_2(h)\) on a uniform square partition of D and fix P to be the space of global polynomials with total degree less than or equal to p in \(y_1,y_2,\dots , y_M\). Each parameter \(y_{m}\) is assumed to be the image of a mean zero uniform random variable. Hence, for a given multi-index \(\mu \in J_P\) we construct the basis functions in (30) by tensorizing univariate Legendre polynomials. Next, we compute \(\eta = \eta (u_X)\) in (37) by solving (35) and (36), choosing \(H_2\) and Q so that the conditions in (31) are satisfied. For \(H_{2}\), we consider the spaces from Examples 1 and 2. We choose Q to be the space of polynomials associated with \(J_Q:= \hat{J}_{Q}\backslash J_P\) where \(\hat{J}_Q\) is the set of multi-indices associated with the space of polynomials with total degree less than or equal to \(p+1\) in \(y_1,y_2,\dots , y_M, y_{M+1}\).

By Theorem 6, the effectivity index \(\theta _{\text {eff}}:= \eta (u_X)/||u-u_X||_B\) satisfies

Since \(||u-u_X||_B\) cannot be computed, we examine \({\hat{\theta }_{\text {eff}} := \eta (u_X)/||u_{\text {ref}}-u_X||_B}\), where \(u_{\text {ref}}\in X_{\text {ref}}\) is a surrogate solution obtained by solving (9) over a sufficiently rich subspace \(X_{\text {ref}}\subset V\) where \(X_{\text {ref}}\supset X\). We define \(X_\text {ref}\) in the same way as X, with \(M_{\text {ref}}=10\), \(h_{\text {ref}} = 2^{-7}\) and \(p_{\text {ref}}= 8\). Fixing \(H_1\), P and Q, we investigate which choice of \(H_2\) consistently leads to \(\hat{\theta }_{\text {eff}}\approx 1\).

Using classical theory from [1, 6] for Galerkin approximation, we provided an alternative derivation of an error estimator from [10] and the associated bound. Our approach highlights the straightforward extension of an error estimation strategy for standard Galerkin FEMs for deterministic PDEs to SGFEMs for parameter-dependent PDEs. The quality of the estimator depends on a CBS constant associated with two finite element spaces \(H_1\) and \(H_2\). For \(H_1 = \mathbb {Q}_1(h)\) and \(H_{1}=\mathbb {Q}_2(h)\) we investigated non-standard choices of \(H_2\) which lead to small CBS constants. When \(H_1 = \mathbb {Q}_1(h)\) and \(H_2\) satisfies certain conditions, we derived new theoretical estimates for the CBS constant. In Sect. 6 we demonstrated that the best choice of \(H_2\) for constructing an effective error estimator is not necessarily the space that leads to the smallest CBS constant. Through numerical experiments, we demonstrated that Q must also be carefully selected and tailored to properties of the diffusion coefficient. When both \(H_2\) and Q are chosen appropriately, the estimator exhibits effectivity indices close to one.

Choosing \(H_{2}\) and Q so that the effectivity index is close to one is not the end of the story. If the estimated error associated with \(u_{X} \in X=H_{1} \otimes P\) is too high, we need to decide how to enrich X and compute a new approximation. The error estimate needs to be accurate, but to derive adaptive algorithms using (44)–(45), we should only work with spaces \(H_2\) and Q such that it is straight-forward to compute new SGFEM approximations in \((H_{1}\oplus H_{2}) \otimes P\) and/or \(H_{1} \otimes (P \oplus Q)\). For example, when \(H_1 = \mathbb {Q}_1(h)\), choosing \(H_2=\mathbb {Q}_2(h)\) yields an accurate error estimate for the current approximation, but does not give a feasible spatial adaptive enrichment strategy. Choosing \(H_{2}=\mathbb {Q}_1(h/2)\) is more natural. Fortunately, this space also yields a good error estimator. When \(H_1 = \mathbb {Q}_2(h)\), \(H_{2}=\mathbb {Q}_2^r(h/2)\) yields an excellent estimator. Although using \(H_{2}=\mathbb {Q}_2(h/2)\) is more natural for adaptivity, we recommend using \(H_{2} =\mathbb {Q}_2^r(h/2)\) to estimate the error. Not only is this cheapest option of all those considered, since \(\mathbb {Q}_2(h/2)\) is richer, the estimated spatial error reduction \(||e_{Y_1}||_{B_0}\) obtained using \(H_{2}=\mathbb {Q}_2^r(h/2)\) is still informative, if we wish to assess the benefit of computing a new approximation in \(\left( \mathbb {Q}_2(h)\oplus \mathbb {Q}_2(h/2)\right) \otimes P\).