A Sparse Grid Stochastic Collocation Method for Elliptic Interface Problems with Random Input

Abstract

In this paper, numerical solutions of elliptic partial differential equations with both random input and interfaces are considered. The random coefficients are piecewise smooth in the physical space and moderately depend on a large number of random variables in the probability space. To relieve the curse of dimensionality, a sparse grid collocation algorithm based on the Smolyak construction is used. The numerical method consists of an immersed finite element discretization in the physical space and a Smolyak construction of the extreme of Chebyshev polynomials in the probability space, which leads to the solution of uncoupled deterministic problems as in the Monte Carlo method. Numerical experiments on two-dimensional domains are also presented. Convergence is verified and compared with the Monte Carlo simulations.

1 Introduction

In many applications, a simulation domain is often composed of several materials separated by curves or surfaces from each other, and this often leads to a so-called interface problem consisting of a boundary value problem of a partial differential equation coupled by jump conditions across the material interface required by pertinent physics. Elliptic interface problems have a variety of applications in many scientific and engineering disciplines, including fluid dynamics, materials science, and biological systems. An efficient solver for this type of interface problem is critical for numerical simulations. The immersed finite element method (IFEM) [17–20] has been proposed as a good choice. The IFEM is based on uniform meshes which have many advantages over the usual fitted meshes. The degree of freedom remains the same as the standard linear finite element method. When the discontinuity disappears, the IFEM becomes the standard FEM. The optimal accuracy is obtained by modifying the basis functions on interface elements. Moreover, one does not need to generate a new grid at each time step when a moving interface is involved [14].

On the other hand, in many cases, the information available for a given problem is far from complete and is in general very limited. This leads to the use of stochastic partial differential equations (SPDEs), whose input data, such as model coefficients, forcing terms, boundary conditions, or geometry that are known to some accuracy. There has been growing interest in designing efficient numerical methods for the solution of SPDEs. The methods for solving such problems include Monte Carlo sampling based methods [7, 11, 22, 27], stochastic Galerkin methods [1, 3, 13, 26, 34, 45], and stochastic collocation methods [2, 4, 29, 35, 38].

In real applications, one may encounter both of the two difficulties mentioned above, i.e., an interface problem together with randomness. However, to our knowledge, few papers in the literature deal with interface problems with random input on uniform meshes. In recent years it has become more and more important to model and simulate interface problems with stochastic input parameters. One simple approach to solve interface problems with stochastic input is the Monte Carlo method which has a rate of convergence that may be considered slow. In this paper, we aim at a direct and more effective method. We especially address the situation where the probability space has a moderate dimensionality, which means that the stochastic problem depends on a moderately large number of random variables. One intrusive approach, such as the gPC Galerkin method [37, 39, 40], is usually hard to implement, because it requires the modification of the deterministic code and this may be difficult, expensive, and time consuming for many complex computational problems. The stochastic collocation method as a non-intrusive method seems to be an ideal approach for computing the numerical solutions of the interface problems with random input discussed in this paper. Stochastic collocation method will not be affected by the complexity of the numerical schemes for the governing differential equations and only needs the execution of the deterministic algorithm as in the Monte Carlo method. In addition, the stochastic collocation method essentially preserves the fast convergence of the corresponding Galerkin method. For these reasons, stochastic collocation methods have become popular, and attracted much attention recently [4, 15, 24, 25, 28].

If the number of random variables is moderately large, one should rather consider sparse tensor product spaces as first proposed by Smolyak [33]. We present an isotropic sparse collocation algorithm based on the Smolyak construction for the elliptic interface problem whose discontinuous coefficients depend on a moderate number of random variables. A Galerkin method using bi-orthogonal polynomials is used to solve the stochastic elliptic interface problem in [43]. The proposed method which is equal to the full tensor product method decouples the equation and yields a number of uncoupled systems which motives us to adopt the so-called sparse grid collocation method [6] based on the Smolyak construction. There is a clear advantage of the isotropic Smolyak method with respect to the full tensor, and this justifies our claim that the use of the Smolyak approximation can reduce the curse of dimensionality.

This work claims that the sparse grid methods, which are “non-intrusive”, are efficient for the elliptic interface problems with random input data. Due to the easy implementation, the “non-intrusive” methods have attracted much attention. The developments of them become active and produce many different techniques. There are recently many alternative “non-intrusive” approaches, for example, least-squares projection on polynomial spaces [9, 23, 36, 44], compressed sensing approach [10, 32, 41, 42] and the least interpolation method [25].

The remainder of the paper is organized as follows. In Sect. 2 we formulate the mathematical problem and introduce some definitions and assumptions. We describe our numerical methods and error estimation in Sect. 3. In Sect. 4, we present several numerical examples. We conclude in the last section.

2 The problem description

Let $D\subset \mathbb {R}^2$ be a convex bounded polygonal domain which is separated into two sub-domains $D^+$ and $D^-$ by a smooth interface $\Gamma$, and ($\Omega ,\mathcal {F},P$) be a complete probability space. Here $\Omega$ is the set of outcomes, $\mathcal {F}\in 2^{\Omega }$ is the $\sigma$-algebra of events, and $P: \mathcal {F}\rightarrow [0, 1]$ is a probability measure. Consider the stochastic elliptic interface problem: Find a random function, $u: \Omega \times D\rightarrow \mathbb {R}$, such that P-almost everywhere in $\Omega$, or in other words, almost surely, the following equation holds:

$$\begin{aligned}&-\nabla \cdot \left( \beta (\omega , \cdot )\nabla u(\omega ,\cdot )\right) =f(\omega ,\cdot )&\text{ in }~D^+\cup D^-, \end{aligned}$$

(2.1)

$$\begin{aligned}&\left[ u(\omega ,\cdot )\right] _{\Gamma }=0~~\left[ \beta (\omega ,\cdot )\frac{\partial u(\omega ,\cdot )}{\partial \mathbf n }\right] _{\Gamma }=0&\text{ on } \Gamma ,\end{aligned}$$

(2.2)

$$\begin{aligned}&u=0&\text{ on }~\partial D. \end{aligned}$$

(2.3)

Here $\mathbf n$ is the unit outward normal direction pointing to the domain $D^+$. The symbol $[\cdot ]_\Gamma$ means the jump across the interface $\Gamma$, i.e., the value on $D^+$ minus the value on $D^-$. The coefficient $\beta (\omega ,\mathbf {x}): \Omega \times D\rightarrow \mathbb {R}$ is a piecewise random function, that is,

$$\begin{aligned} \beta (\omega ,\mathbf {x})=\left\{ \begin{aligned} \beta ^-(\omega ,\mathbf {x})~~~\mathbf {x}\in D^-,\\ \beta ^+(\omega ,\mathbf {x})~~~\mathbf {x}\in D^+. \end{aligned} \right. \end{aligned}$$

(2.4)

We assume that $\beta ^-(\omega ,\cdot )$ and $\beta ^+(\omega ,\cdot )$ are smooth enough in each sub-domain for any realization $\omega \in \Omega$. In addition, we shall make the following assumptions of the data:

• 1. The coefficient $\beta (\omega ,\cdot )$ is uniformly bounded and coercive, i.e., there exist $\beta _{min},~\beta _{max}\in (0,~\infty )$ such that $P\left\{ \omega \in \Omega :~\beta (\omega ,\mathbf {x})\in [\beta _{min},~\beta _{max}],~\forall \mathbf {x}\in D \right\} =1$;

• 2. For any $\omega \in \Omega$, the function $f(\omega ,~\cdot )$ belongs to the space $L^2(D)$ and is square integrable with respect to P in the sense of

  $$\begin{aligned} \int _\Omega \Vert f(\omega ,\cdot )\Vert ^2_{L^2(D)}dP(\omega )<\infty . \end{aligned}$$

Next, we introduce some Hilbert spaces:

• $L^2_P(\Omega )\otimes H^1_{0}(D)$, equipped with the norm $\Vert v\Vert ^2_{L^2_P(\Omega )\otimes H^1_{0}(D)}=\int _{D}\mathbb {E}[|\nabla v|^2]d\mathbf {x},$ where $\mathbb {E}[ \cdot ]$ stands for the expectation.

• $\widetilde{H}^2(D)=\{v\in H^1_0(D): v\in H^2(D^s), s=+,-\}$, equipped with the norm

  $$\begin{aligned} \Vert v\Vert ^2_{\widetilde{H}^2(D)}=\Vert v\Vert ^2_{H^2(D^+)}+\Vert v\Vert ^2_{H^2(D^-)}. \end{aligned}$$

Multiplying the Eq. (2.1) by a function $v \in L^2_P(\Omega )\otimes H^1_{0}(D)$, integrating by parts and using the interface conditions (2.2), we obtain the weak form of the problem (2.1)–(2.3): Find $u\in L^2_P(\Omega )\otimes H^1_{0}(D)$ such that

$$\begin{aligned} \int _{D}\mathbb {E}[\beta \nabla u\cdot \nabla v]d\mathbf {x}=\int _D\mathbb {E}[fv]d\mathbf {x} ~~ \text{ for } \text{ all } v\in L^2_P(\Omega )\otimes H^1_{0}(D). \end{aligned}$$

(2.5)

A straightforward application of the Lax–Milgram theorem together with the assumptions made above allows one to state the well-posedness of the problem (2.5).

Moreover, we have the following regularity result for the problem with respect to $\mathbf {x}$ (see [5]). The solution to (2.5) has realizations in the space $\widetilde{H}^2(D)$, i.e., for any $\omega \in \Omega$, $u(\omega ,\cdot )\in \widetilde{H}^2(D)$ and $\Vert u(\omega ,\cdot )\Vert _{\widetilde{H}^2(D)}\le C\Vert f(\omega ,\cdot )\Vert _{L^2(D)}$.

2.1 Finite-dimensional noise assumption

In some problems the source of randomness can be characterized exactly by a finite number of independent random variables. However, in many applications, the random inputs are stochastic processes which are infinite-dimensional objects. For example, the coefficient $\beta ^\pm (\omega ,\mathbf {x})$ often represents an uncertain material property, e.g., conductivity, that is a stochastic process in space. So, to solve the problem (2.5) numerically, the first step is to reduce the infinite-dimensional probability space to a finite-dimensional space. The Karhunen–Loève expansion [12, 13, 31] is one of the most widely used techniques for dimension reduction.

Let the mean and the covariance of $\beta ^\pm (\omega ,\mathbf {x})$ be defined as

$$\begin{aligned} \beta ^\pm _0(\mathbf {x})=\int _{\Omega }\beta ^\pm (\omega ,\mathbf {\mathbf {x}})dP,\quad \forall \mathbf {x}\in D^\pm \end{aligned}$$

and

$$\begin{aligned} Cov_{\beta ^\pm }(\mathbf {x},\mathbf {x}_1)=\int _{\Omega }\left( \beta ^\pm (\omega ,\mathbf {x})-\beta ^\pm _0(\mathbf {x})\right) \left( \beta ^\pm (\omega ,\mathbf {x}_1)-\beta ^\pm _0(\mathbf {x}_1)\right) dP, \end{aligned}$$

respectively. Then the Karhunen–Loève (KL) expansion of $\beta ^\pm (\omega ,\mathbf {x})$ is

$$\begin{aligned} \beta ^\pm (\omega ,\mathbf {x})=\beta ^\pm _0(\mathbf {x})+\sum _{n=1}^{\infty }\sqrt{\lambda ^\pm _n}\beta ^\pm _n(\mathbf {x})y^\pm _n(\omega ), \end{aligned}$$

where $\beta _n^\pm$ are the orthogonal and normalized eigenfunctions and $\lambda _n^\pm$ are the corresponding eigenvalues of the following eigenvalue problem

$$\begin{aligned} \int _{D^\pm }Cov_{\beta ^\pm }(\mathbf {x},\mathbf {x}_1)\beta ^\pm _n(\mathbf {x}_1)d\mathbf {x}_1=\lambda ^\pm _n\beta ^\pm _n(\mathbf {x}). \end{aligned}$$

The random variables $y^\pm _n(\omega )$ are mutually uncorrelated with zero mean value and unit variance and are defined by

$$\begin{aligned} y^\pm _n(\omega )=\frac{1}{\sqrt{\lambda ^\pm _n}}\int _{D^\pm }\beta ^\pm (\omega ,\mathbf {x}-\beta _0^\pm (\mathbf {x})\beta ^\pm _n(\mathbf {x}))d\mathbf {x},\quad n=1,2,\cdots . \end{aligned}$$

It is shown in [13] that the Karhunen–Loève expansion is optimal among all possible representations of random processes in the sense of the mean-square error. The truncated Karhunen–Loève expansion reads

$$\begin{aligned} \beta ^\pm _{N^\pm }(\omega ,\mathbf {x})=\beta ^\pm _0(\mathbf {x})+\sum _{n=1}^{N^\pm }\sqrt{\lambda ^\pm _n}\beta ^\pm _n(\mathbf {x})y^\pm _n(\omega ). \end{aligned}$$

(2.6)

In practice, one has to choose the number of the truncated terms $N^\pm$ properly so that the influence of truncation error is relatively small and can be omitted.

In summary, the above descriptions motivate us to make the following assumption.

Assumption 2.1

(Finite-dimensional noise) The coefficients in the original equation have the form

$$\begin{aligned} \beta ^{\pm }(\omega ,\mathbf {x})= & {} \beta ^{\pm }\left( y^\pm _1(\omega ),y^\pm _2(\omega ),\ldots ,y^\pm _{N^\pm }(\omega ),\mathbf {x}\right) \\= & {} \beta ^\pm _0(\mathbf {x})+\sum _{n=1}^{N^\pm }\sqrt{\lambda ^\pm _n}\beta ^\pm _n(\mathbf {x})y^\pm _n(\omega )~~\text{ in } ~ \Omega \times D^\pm , \end{aligned}$$

where $N^\pm$ are positive integers, $\{y^\pm _n\}_{n=1}^{N^\pm }$ are real-valued and independent random variables with mean value zero and unit variance. The function f has a similar form $f(\omega ,\mathbf {x})=f(y_1^f(\omega ),\ldots ,y^f_{N^f}(\omega ),\mathbf {x})$. Define $\mathbf {y}=(y_1,\ldots ,y_N)=(y^+_1,\ldots ,y^+_{N^+},y^-_1,\ldots ,y^-_{N^-},y^f_1,\ldots ,y^f_{N^f})$ with $N=N^++N^-+N^f$, we can rewrite $\beta ^\pm (\omega ,\mathbf {x})=\beta ^\pm (\mathbf {y},\mathbf {x})$ and $f(\omega ,\mathbf {x})=f(\mathbf {y},\mathbf {x})$.

For $n=1,\ldots ,N$, we assume that the image of $y_n$, i.e., the set $\Theta _n\equiv y_n(\Omega )$, is a bounded interval in $\mathbb {R}$, and the random variable $y_n$ has a known density function $\rho _n:~\Theta _n\rightarrow \mathbb {R}^+$. Since the random variables $y_n$ are independent, the joint probability density of $\mathbf {y}=(y_1,\ldots ,y_N)$ is $\rho (\mathbf {y})=\prod _{n=1}^N\rho _n(y_n):~\Theta \rightarrow \mathbb {R}^+$, where $\Theta \equiv \prod _{n=1}^N\Theta _n\subset \mathbb {R}^N$.

Under the finite-dimensional assumption, the stochastic problem (2.1)–(2.3) now becomes a deterministic elliptic interface problem with N-dimensional parameter, i.e., find $u(\mathbf {y},\mathbf {x}):\Theta \times D\rightarrow \mathbb {R}$, for all $\mathbf {y}\in \Theta$, the following holds

$$\begin{aligned} \left\{ \begin{aligned}&-\nabla \cdot (\beta (\mathbf {y},\mathbf {x})\nabla u(\mathbf {y},\mathbf {x}))=f(\mathbf {y},\mathbf {x})~~&\mathbf {x}\in D^+\cup D^-,\\&[u(\mathbf {y},\mathbf {x})]_{\Gamma }=0~~\left[ \beta \frac{\partial u(\mathbf {y},\mathbf {x})}{\partial \mathbf n }\right] _{\Gamma }=0&\mathbf {x}\in \Gamma ,\\&u(\mathbf {y},\mathbf {x})=0~~&\mathbf {x}\in \partial D.\\ \end{aligned} \right. \end{aligned}$$

(2.7)

Note that here and later in this paper the gradient notation, $\nabla$, means differentiation with respect to $\mathbf {x}\in D$. The stochastic variational formulation (2.5) has a deterministic equivalent: Find $u(\mathbf {y},\mathbf {x})\in L^2_{\rho }(\Theta )\otimes H^1_{0}(D)$ such that

$$\begin{aligned}&\int _{\Theta \times D} \rho (\mathbf {y})\beta (\mathbf {y},\mathbf {x})\nabla u(\mathbf {y},\mathbf {x})\cdot \nabla v(\mathbf {y},\mathbf {x})d\mathbf {y}d\mathbf {x}\nonumber \\&\quad =\int _{\Theta \times D} \rho (\mathbf {y}) f(\mathbf {y},\mathbf {x})v(\mathbf {y},\mathbf {x})d\mathbf {y}d\mathbf {x},~~\forall v\in L^2_{\rho }(\Theta )\otimes H^1_{0}(D). \end{aligned}$$

(2.8)

3 Stochastic collocation methods

In this section, we introduce the stochastic collocation method for computing the statistical moments of the solution u to the problem (2.7). In the stochastic collocation method, the numerical solution is sought in a finite-dimensional space $\mathcal {P}_{\mathbf {p}}(\Theta )\otimes W_h(D)$ which can be regarded as an approximation of $L^2_{\rho }(\Theta )\otimes H^1_{0}(D)$.

Here $W_h(D)$ is a finite element space, which contains piecewise polynomials defined on the triangulation $\mathcal {T}_h$ that has a maximum mesh-spacing parameter $h>0$. For elliptic problems with smooth coefficients, the common choice is the standard linear finite element space. While for the interface problems the standard linear finite element can not achieve optimal accuracy, unless the triangulation is aligned with the interface. So we choose the immersed finite element space $S_h(D)$ which is discussed in Sect. 3.2 together with the immersed finite element method. The semidiscrete approximation $u_h(\mathbf {y},\cdot ):\Theta \rightarrow S_h(D)$ is obtained by the immersed finite element method.

In random spaces, $\mathcal {P}_{\mathbf {p}}(\Theta )\subset L_\rho ^2(\Theta )$ is the span of tensor product polynomials with degree at most $\mathbf {p}=(p_1,\ldots ,p_N)$, i.e., $\mathcal {P}_{\mathbf {p}}(\Theta )=\otimes _{n=1}^N\mathcal {P}_{p_n}(\Theta _n)$, with $\mathcal {P}_{p_n}(\Theta _n)$=span$\left\{ y_n^k,k\right. \left. =0,\ldots ,p_n\right\} ,~n=1,\ldots ,N.$ Hence the dimension of $\mathcal {P}_{\mathbf {p}}(\Theta )$ is $N_p=\prod _{n=1}^N(p_n+1)$.

In the stochastic collocation method, we first evaluate approximation functions $u_h(\mathbf {y}_k,\cdot )\in S_h(D)$ to the solution of (2.7) on a suitable set of points $\mathbf {y}_k\in \Theta$ using the immersed finite element method (see Sect. 3.2). Then the fully discrete solution $u_{h,\mathbf {p}}\in C^0(\Theta ;S_h(D))$ is a polynomial interpolation in the random space, i.e.,

$$\begin{aligned} u_{h,\mathbf {p}}(\mathbf {y},\mathbf {x} )=\sum _ku_h(\mathbf {y}_k,\mathbf {x})l_k^{\mathbf {p}}(\mathbf {y}), \end{aligned}$$

(3.1)

where, for instance, the functions $l_k^{\mathbf {p}}$ can be taken as the Lagrange polynomials. Then the approximation of the expected value of u to the stochastic equation (2.1)–(2.3) can be evaluated as

$$\begin{aligned} \mathbf {E}[u]\approx \mathbf {E}[u_{h,\mathbf {p}}]=\sum _ku_h(\mathbf {y}_k,\mathbf {x})\int _\Theta \rho (\mathbf {y})l_k^{\mathbf {p}}(\mathbf {y})d\mathbf {y}. \end{aligned}$$

3.1 Smolyak approximation

First we assume $N=1$, and let $\{y_1^i,\ldots ,y_{m_i}^i\}\subset \Theta$ be a sequence of abscissas for Lagrange interpolation. Here the integer i means the level of approximation and $m_i$ is the number of interpolation points used at level i. Then, the one-dimensional Lagrange interpolation is

$$\begin{aligned} \mathcal {U}^{i}(u)=\sum _{k=1}^{m_i}u(y_k^i)l_k^i, \end{aligned}$$

where $l_k^i\in \mathcal {P}_{m_i-1}(\Theta )$ are the Lagrange polynomials of degree $m_i-1$, i.e., $l_k^i(y)=\prod ^{m_i}_{k=1,k\ne j}\frac{(y-y_k^i)}{(y_j^i-y_k^i)}$. In the multi-dimensional case, i.e., $N>1$, the Lagrange interpolation based on the full tensor product is defined by

$$\begin{aligned} \mathcal {I}_{\mathbf {i}}^N(u)(\mathbf {y})=(\mathcal {U}^{i_1}\otimes \cdots \otimes \mathcal {U}^{i_N})(u)(\mathbf {y})=\sum _{j_1=1}^{m_{i_1}}\cdots \sum _{j_N=1}^{m_{i_N}} u(y_{j_1}^{i_1},\ldots ,y_{j_N}^{i_N})(l_{j_1}^{i_1}\otimes \cdots \otimes l_{j_N}^{i_N}).\nonumber \\ \end{aligned}$$

(3.2)

Obviously, the number of the total interpolation points needed in the full tensor interpolation is $\eta =\Pi _{n=1} ^N m_{i_n}$. If we use the same points in each direction, i.e., $m_i=m$, $i=1,\ldots ,N$, then $\eta =m^N$. The exponential growth of interpolation nodes with respect to the dimension of random space is a drawback which is often called the curse of dimensionality. The sparse grid method proposed in [2, 38], which greatly reduces the curse of dimensionality, is a good choice for solving the stochastic problem.

Now we briefly describe the isotropic Smolyak formulation which is a linear combination of low order tensor product formula (3.2). The Smolyak formula is then given by (see [29])

$$\begin{aligned} \mathcal {A}(w,N)=\sum _{w+1\le |\mathbf {i}|\le w+N}(-1)^{w+N-|\mathbf {i}|}\left( \begin{array}{c} N-1 \\ w+N-|\mathbf {i}| \\ \end{array} \right) (\mathcal {U}^{i_1}\otimes \cdots \otimes \mathcal {U}^{i_N}), \end{aligned}$$

(3.3)

where $\mathbf {i}\in \mathbb {N}_+^N$ and $|\mathbf {i}|=i_1+\cdots +i_N$. The set of the sparse grids needed to compute $\mathcal {A}(w,N)(u)$ is

$$\begin{aligned} \mathcal {H}(w,N)=\sum _{w+1\le |\mathbf {i}|\le w+N}(\vartheta ^{i_1}\times \cdots \times \vartheta ^{i_N}), \end{aligned}$$

where $\vartheta ^i=\{y_1^i,\ldots ,y_{m_i}^i\}$ is the set of abscissas used by $\mathcal {U}^i$. In this paper we choose to use Clenshaw–Curtis abscissas which are the extreme of Chebyshev polynomials, that is, for any choice of $m_i>1$,

$$\begin{aligned} y_j^i=-\text{ cos }\frac{\pi (j-1)}{m_i-1},\quad j=1,\ldots ,m_i. \end{aligned}$$

(3.4)

In addition, we define $y_1^i=0$ if $m_i=1$, and choose $m_1=1$ and $m_i=2^{i-1}+1$ for $i>1$.

Note that Clenshaw–Curtis abscissas are nested, so that the Smolyak approximation requires fewer interpolation points than the corresponding formula with non-nested points, for example, Gaussian abscissas. In Fig. 1, we show the sparse grids in $\mathcal {H}(w,N)$ with $w=5$ and $N=2$. For comparison, the full tensor product grids based on the same one-dimensional nodes are shown on the right of Fig. 1, and we observe that the sparse grid has significantly fewer nodes.

Fig. 1

Two-dimensional (N=2) interpolation nodes based on the extreme of Chebyshev polynomials (3.4). Left sparse grids $\mathcal {H}(w,N)$ with $w=5$. Total number of points is 145. Right the tensor product grids based on the same one-dimensional nodes. Total number of nodes is 1089

3.2 Immersed finite element methods

In this section we give a brief review of the immersed finite element space introduced in [20]. Since the triangulation $\mathcal {T}_h$ is independent of the interface $\Gamma$, there exist some elements that the interface passes through. We call these elements interface elements and the rest non-interface elements. The set of interface elements and non-interface elements are denoted by $\mathcal {T}_h^{int}$ and $\mathcal {T}_h^{non}$, respectively. For complicated interfaces, it may be necessary to refine the mesh to resolve the interface.

On non-interface elements, we use the standard linear basis functions. On interface elements, the linear functions are broken along the interface to satisfy the jump conditions across the interface in some sense. We take a typical interface element $\triangle ABC$ whose geometric configuration is given in Fig. 2 as a demonstration. The line segment $\overline{SE}$ divides T into two parts $T^+$ and $T^-$. Let $\mathbf n$ and $\mathbf t$ be the unit normal and tangential directions of the line segment $\overline{SE}$, respectively. We construct the following piecewise linear function on this element,

$$\begin{aligned} \phi (\mathbf {x})=\left\{ \begin{array}{ll} \phi ^+=a^++b^+x_1+c^+x_2,\quad \quad &{}\mathbf {x}=(x_1,x_2)\in T^+,\\ {}\phi ^-=a^-+b^-x_1+c^-x_2,\quad \quad &{}\mathbf {x}=(x_1,x_2)\in T^-.\\ \end{array} \right. \end{aligned}$$

(3.5)

The coefficients are chosen such that

$$\begin{aligned}&\phi (A)=V_1,~\phi (B)=V_2,~\phi (C)=V_3, \end{aligned}$$

(3.6)

$$\begin{aligned}&\phi ^+(S)=\phi ^-(S),~\phi ^+(E)=\phi ^-(E),~\beta ^+\frac{\partial \phi ^+}{\partial \mathbf n }=\beta ^-\frac{\partial \phi ^-}{\partial \mathbf n }, \end{aligned}$$

(3.7)

where $V_i$, $i=1,2,3$ are the nodal variables. Intuitively, there are six unknowns in (3.5) and six restrictions in (3.6)–(3.7). The piecewise linear function is uniquely determined by $V_i$, $i=1,2,3$ (see [20]). Now we define the immersed finite element space $S_h(D)$ as the set of all piecewise linear functions that satisfy

$$\begin{aligned} \left\{ \begin{aligned}&\phi |_{T} \text{ is } \text{ the } \text{ linear } \text{ function } \text{ if } T\in \mathcal {T}_h^{non},\\&\phi |_{T} \text{ is } \text{ the } \text{ piecewise } \text{ linear } \text{ function } \text{ defined } \text{ in } \text{(3.5)--(3.7) } \text{ if } T\in \mathcal {T}_h^{int},\\&\phi \text{ is } \text{ continuous } \text{ at } \text{ all } \text{ nodal } \text{ points },\\&\phi (\mathbf {x}_b)=0 \text{ if } \mathbf {x}_b \text{ is } \text{ a } \text{ nodal } \text{ point } \text{ on } \partial D. \end{aligned} \right. \end{aligned}$$

The immersed finite element space $S_h$ is a modification to the standard piecewise linear conforming finite element space when the coefficient $\beta$ is discontinuous. The two spaces are the same when $\beta ^+=\beta ^-$. For any $\mathbf {y}\in \Theta$, the immersed finite element approximation of (2.7) reads: Find $u_h(\mathbf {y},\cdot )\in S_h(D)$ such that

$$\begin{aligned} a_h(u_h(\mathbf {y},\mathbf {x}),v(\mathbf {x}))=\int _D f(\mathbf {y},\mathbf {x})v(\mathbf {x})d\mathbf {x},\quad \forall v(\mathbf {x})\in S_h(D), \end{aligned}$$

(3.8)

where the bilinear form $a_h(\cdot ,\cdot )$ is defined by

$$\begin{aligned} a_h(w,v)=\sum _{T\in \mathcal {T}_h}\int _T\beta \nabla w\cdot \nabla vd\mathbf {x},\quad \forall w,v\in S_h(D). \end{aligned}$$

(3.9)

It has been proven in [8, Theorem 5.1] that the immersed finite element method has the optimal convergence order in $L^2$-norm, that is,

$$\begin{aligned} \Vert u(\mathbf {y},\cdot )-u_h(\mathbf {y},\cdot )\Vert _{L^2(D)}\le Ch^2\Vert u(\mathbf {y},\cdot )\Vert _{\widetilde{H}^2(D)},\quad \forall \mathbf {y}\in \Theta . \end{aligned}$$

(3.10)

We note that $v_h(x)$ in $S_h$ is likely discontinuous across the adjacent edges of two interface elements. That is why $S_h$ is called a non-conforming finite element space in [20]. We can see this from the diagram in Fig. 2. If $\phi (A)$, $\phi (B)$, $\phi (C)$ and $\phi (G)$ are given, we can obtain $\phi |_{\triangle ABC}$ and $\phi |_{\triangle ACG}$ independently so that $\phi |_{\triangle ACG}(E)\not =\phi _{\triangle ACG}(E)$. The set of these edges where the function of $S_h(D)$ is discontinuous is denoted by $\mathcal {E}_h^{int}$. To cancel the non-conforming error caused by the discontinuity on $\mathcal {E}^{int}_h$, two correction terms are added to the bilinear form and the resulting method is outperform than original immersed finite element method (see [16, 21]).

Fig. 2

A typical interface element and a neighboring element

3.3 Error analysis

We recall that u is the solution of the original stochastic problem (2.1)–(2.3), $u_h$ is the semidiscrete approximation obtained by the IFEM and $\mathcal {A}(w,N)u_h$ is the fully discrete numerical solution. The error to be considered can be split as

$$\begin{aligned}&\Vert u-\mathcal {A}(w,N)u_h\Vert _{L^2_\rho (\Theta )\otimes L^2(D)}\le \Vert u-u_h\Vert _{L^2_\rho (\Theta )\otimes L^2(D)}\nonumber \\&\quad +\Vert u_h-\mathcal {A}(w,N)u_h\Vert _{L^2_\rho (\Theta )\otimes L^2(D)}. \end{aligned}$$

(3.11)

The first term is nothing but the approximation error in physical spaces, i.e., the error of the IFEM. By (3.10), we have

$$\begin{aligned} \begin{aligned} \Vert u-u_h\Vert _{L^2_\rho (\Theta )\otimes L^2(D)}&=\left( \int _\Theta \int _D\rho |u(\mathbf {y},\mathbf {x})-u_h(\mathbf {y},\mathbf {x})|^2d\mathbf {x}d\mathbf {y}\right) ^{1/2}\\&\le Ch^2\Vert u\Vert _{L^2_\rho (\Theta )\otimes \widetilde{H}^2(D)}. \end{aligned} \end{aligned}$$

(3.12)

The second term is the Smolyak approximation error. To estimate the approximation error, we first give the following lemma [29, Theorem 3.10].

Lemma 3.1

Let $\Theta ^*=\prod _{j=1,j\not =n}^N\Theta _j$ and $y_n^*$ be an arbitrary element of $\Theta ^*$. For each $y_n\in \Theta _n$, assume that there exists $\tau _n$ such that $u(y_n,y_n^*,\mathbf {x})$ as a function of $y_n$ admits an analytic extension $u(z,y_n^*,\mathbf {x})$, $z\in \mathbb {C}$, in the region of the complex plane

$$\begin{aligned} \sigma (\Theta _n;\tau _n)=\{z\in \mathbb {C},\text{ dis } t(z,\Theta _n)\le \tau _n\}. \end{aligned}$$

(3.13)

Also define the parameter

$$\begin{aligned} \sigma =\frac{1}{2}\min _{n=1,\ldots ,N}\log \left( \frac{2\tau _n}{|\Theta _n|}+\sqrt{1+\frac{4\tau _n^2}{|\Theta _n|^2}}\right) . \end{aligned}$$

(3.14)

Then the isotropic Smolyak formula (3.3) based on Clenshaw–Curtis abscissas satisfies

$$\begin{aligned} \Vert u-\mathcal {A}(w,N)(u)\Vert _{L^\infty (\Theta ^N;W_h(D))}\le C(\sigma ,N)\eta ^{-\mu _1} \text{ with } \mu _1=\frac{\sigma }{1+\log (2N)}, \end{aligned}$$

(3.15)

where $\eta =|\mathcal {H}(w,N)|$ is the number of collocation points, and the constant $C(\sigma ,N)$ only depends on $\sigma$ and N.

This lemma indicates that under some regularity assumptions the Smolyak formula based on Clenshaw–Curtis abscissas has at least algebraic convergence with respect to the number of collocation points.

However $u_h$ is required to satisfy the regularity assumption made in the above lemma. It has been proved in [2, Lemma 3.2] that the problem satisfies the regularity assumption with $0<\tau _n<1/(2/\gamma _n)$ if the following holds:

$$\begin{aligned} \left\| \frac{\partial ^k_{y_n}\beta (\mathbf {y},\cdot )}{\beta (\mathbf {y},\cdot )}\right\| _{L^\infty (D)}\le \gamma _n^kk!~~~\frac{\Vert \partial ^k_{y_n}f(\mathbf {y},\cdot )\Vert _{L^2(D)}}{1+\Vert f(\mathbf {y},\cdot )\Vert _{L^2(D)}}\le \gamma _n^kk!. \end{aligned}$$

(3.16)

Under the assumption 2.1, we have

$$\begin{aligned} \frac{\partial ^k_{y_n}\beta ^+(\mathbf {y},\mathbf {x})}{\beta (\mathbf {y},\mathbf {x})}\le \left\{ \begin{aligned}&\sqrt{\lambda _n}\beta ^+_n(\mathbf {x})/\beta _{min} ~~&\text{ if } k=1\\&0&\text{ if } k>1 \text{ or } n>N^+ \end{aligned} \right. \end{aligned}$$

(3.17)

and similar results for $\beta ^-$ and f. Thus (3.16) is satisfied if we take $\gamma _n=\sqrt{\lambda _n}\Vert \beta ^+_n\Vert _{L^\infty (D^+)}/\beta _{min}$ for $n=1,\ldots , N^+$. For the case of $n>N^+$, the constant $\gamma _n$ can be chosen similarly. Note that the regularity results are valid also for the semidiscrete solution $u_h$.

Using Lemma 3.1, the second term now can be estimated as

$$\begin{aligned} \Vert u_h-\mathcal {A}(w,N)u_h\Vert _{L^2_\rho (\Theta )\otimes L^2(D)}\le C \Vert u_h-\mathcal {A}(w,N)u_h\Vert _{L^\infty _\rho (\Theta )\otimes L^2(D)}\le C(\sigma ,N)\eta ^{-\mu _1}.\nonumber \\ \end{aligned}$$

(3.18)

Substituting (3.12) and (3.18) into (3.11), we therefore get the following convergence result.

Theorem 3.2

Under the assumption 2.1, it holds that

$$\begin{aligned} \Vert u-\mathcal {A}(w,N)u_h\Vert _{L^2_\rho (\Theta )\otimes L^2(D)}\le Ch^2\Vert u\Vert _{L^2_\rho (\Theta )\otimes \widetilde{H}^2(D)}+C(\sigma ,N)\eta ^{-\sigma /(1+\log (N))},\qquad \quad \end{aligned}$$

(3.19)

where $\sigma$ is defined in (3.14) and the constants C and $C(\sigma ,N)$ are independent of h and $\eta$.

Using the theorem, the error in the expected value of u is easily estimated, i.e.,

$$\begin{aligned} \begin{aligned} \Vert \mathbb {E}[u]-\mathbb {E}[\mathcal {A}(w,N)u_h]\Vert _{L^2(D)}&\le \Vert u-\mathcal {A}(w,N)u_h\Vert _{L^2_\rho (\Theta )\otimes L^2(D)}\\&\le Ch^2\Vert u\Vert _{L^2_\rho (\Theta )\otimes \widetilde{H}^2(D)}+C(\sigma ,N)\eta ^{-\sigma /(1+\log (N))}.\qquad \end{aligned} \end{aligned}$$

(3.20)

4 Numerical examples

In this section, we present some numerical examples to show the performance of the sparse grid stochastic collocation method. A comparison of the efficiency of the proposed sparse grid stochastic collocation method with both the Monte Carlo method and the sparse grid stochastic collocation method based on standard linear finite element methods will be given. For simplicity, the problems are defined in the rectangular domain $D=[-1,1]\times [-1,1]$ which is partitioned into $2N_h^2$ right triangles with mesh size h. We consider a deterministic right-hand function f and construct the random coefficient as

(4.1)

with $N=2M$ the dimension of random space, and $y_n\in [-1,1]$, $n=1,\ldots ,N$, are independent uniformly distributed random variables.

In all examples, we compute the $L^2(D)$ error to the expected value, i.e.,

$$\begin{aligned} \text{ Error }=\Vert \mathbb {E}[u]-\mathbb {E}[\mathcal {A}(w,N)u_h]\Vert _{L^2(D)}, \end{aligned}$$

(4.2)

where the expected value of exact solution is approximated as $\mathbb {E}[u]\approx \mathbb {E}[\mathcal {A}(\widetilde{w},N)u_h]$ with a larger $\widetilde{w}$.

Example 1

The interface $\Gamma$ is a circle centered at the origin with radius $r_0=0.5$, as shown in Fig. 3. The true solution is

$$\begin{aligned} u=\left\{ \begin{aligned}&\frac{r^3}{\beta ^-}~~~~~~~~~~~~~~~~~~~~~~~~~&\text{ in }~D^-,\\&\frac{r^3}{\beta ^+}+(\frac{1}{\beta ^-}-\frac{1}{\beta ^+})r_0^3~~~~&\text{ in }~D^+. \end{aligned} \right. \end{aligned}$$

(4.3)

where $r=\sqrt{x_1^2+x_2^2}$. In this example, we choose $\beta _0^+=100$ and $\beta _0^-=1$ in (4.1).

Fig. 3

The domain and the interface of Example 1

First a low-dimensional random inputs with $N=6$ is tested. We use the proposed sparse grid stochastic collocation method based on immersed finite element method (SGSC-IFEM) and linear finite element method (SGSC-Linear FEM) respectively. Figure 4 shows the $L^2$ error in expected value of the solution versus the number of collocation points $\eta$ and the mesh size h for different numerical methods. We plot the errors at different resolutions, such as $N_h=128$, $N_h=256$ and $N_h=512$. From Fig. 4a we can see that when we select a fixed value of $N_h$, the error decays fast first and then stagnates as the number of collocation points increases. The error stagnates because the approximation error in the physical spaces becomes predominant. If we wish the error is reduced further, then we need to increase $N_h$. From Fig. 4b we can see that when we fix the “level” $w=4$, the order of errors in $L^2$ norm is $O(h^2)$ for the IFEM, but only O(h) for the standard linear FEM.

Fig. 4

A comparison between the sparse grid stochastic collocation (SGSC) method based on the IFEM and the standard linear FEM for solving Example 1 with N=6. a $L^2$ error versus the number of collocation points $\eta$. b $L^2$ error versus the mesh-spacing parameter h with $w=4$

In practical stochastic collocation computing, the PDE solver is usually a “black-box” to provide the function evaluations at the sample points. In the following experiments, we use IFEM for both sparse grid stochastic collocation method and Monte Carlo method with $N_h=512$, assuming that the approximation error in the “black-box” is small enough to investigate the convergence properties of the isotropic Smolyak method.

Now we choose a moderately high-dimensional random space with $N=10$. Figure 5 shows the error convergence with respect to the number of grids for the sparse grid stochastic collocation method and Monte Carlo method. We can see that the sparse grid stochastic collocation method converges quickly, and it converges faster than the Monte Carlo finite element method. In Fig. 7, we plot the error distribution of the expected value of numerical solution with different “level”. From these figures we can see that the numerical error is small although very low “level” is used. In addition, we observe that the shape of the error distribution for $w=1$ and 2 is almost the same as that of exact expectation (see Fig. 6), but changes completely when $w=3$ and 4. The reason is that when w is small, such as $w=1$ and 2, the error of the isotropic Smolyak approximation in the random space is larger than the approximation error in the physical space. As we increase w, the approximation error in the physical space becomes larger than that from the Smolyak approximation.

Fig. 5

A comparison between the sparse grid stochastic collocation method and the Monte Carlo approach for solving Example 1 with N=10 and $N_h=512$

Fig. 6

The exact expectation of Example 1 with N=10

Fig. 7

The error distribution of the expected value of Example 1 with N=10 and w=1, 2, 3, 4

Example 2

The interface is the zero level set of the function is $\varphi (x_1,x_2)=-x_2^2+((x_1-1)\text{ tan }\theta )^2x_1$, where $\theta$ is a parameter. The interface has a corner of angle $2\theta$ at (1, 0) as shown in Fig. 8. The exact solution is chosen as $u=\varphi (x_1,x_2)/\beta$. It is easy to verify that the solution indeed satisfies the PDE and the jump conditions using the fact of $\mathbf n =\nabla \varphi /|\nabla \varphi |$. In this case, we choose $\beta _0^-=1$ and $\beta _0^+=10$ in (4.1). The dimension of random space is set to be $N=10$.

Fig. 8

The domain and the interface of Example 2. The interface has a corner of angle 2$\theta$ at (1, 0)

A comparison between the sparse gird collocation method and the Monte Carlo method is given in Fig. 9. It can be concluded again that the sparse grid collocation method is accurate and performs better than the Monte Carlo method. We plot the expected value of the exact solution in Fig. 10. The corresponding error distributions of expected value from “level” 1 to “level” 4 are displayed in Fig. 11. From these figures we observe the similar phenomena as Example 1. The shape of the error distribution for $w=1$ and 2 is almost the same as that of exact expectation (see Fig. 10), but changes completely when $w=3$ and 4.

Fig. 9

A comparison between the SGSC-IFEM and the MC-IFEM for solving Example 2 with N=10

Fig. 10

The expected value of Example 2 with N=10

Fig. 11

The error distribution of the expected value of Example 2 with N=10 and w=1, 2, 3, 4

Example 3

We consider the case where $\beta _0^+$ and $\beta _0^-$ in (4.1) is not a piecewise constant,

$$\begin{aligned} \left\{ \begin{aligned}&\beta _0^+=1~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~&\text{ in }~D^+,\\&\beta _0^-=10+5(x_1^2-x_1x_2+x_2^2)~~~&\text{ in }~D^-. \end{aligned} \right. \end{aligned}$$

(4.4)

The interface is the zero level set of $\varphi (x_1,x_2)=x_1^2/(0.5^2)+x_2^2/(0.25)^2-1$. The exact solution is chosen as $u=\varphi (x_1,x_2)/\beta$. And we set $N=8$.

A comparison between the sparse gird collocation method and the Monte Carlo method is given in Fig. 12. It can be concluded again that the sparse grid collocation method is accurate and performs better than the Monte Carlo method.

Fig. 12

A comparison between the SGSC-IFEM and the MC-IFEM for solving Example 3 with N=8

The expected value of the exact solution is presented in Fig. 13. The corresponding error distributions of expected value from “level” 1 to “level” 4 are displayed in Fig. 14. We can see that the shape of the error distribution is almost the same as that of exact expectation (see Fig. 13) when $w=1$ and 2, changes a little when $w=3$, and changes completely when $w=4$. We can conclude that when w is small, such as $w=1$ and 2, the error of the isotropic Smolyak method is dominant. As we increase w, the approximation error in the physical space becomes larger than that from the Smolyak approximation.

Fig. 13

The expected value of Example 3 with N=8

Fig. 14

The error distribution of the expected value of Example 3 with N=8 and w=1, 2, 3, 4

5 Conclusion and future work

We have presented a stochastic collocation method for the numerical solution of elliptic partial differential equations with both random inputs and interfaces. To relieve the curse of dimensionality, we use the sparse grid collocation method based on the isotropic Smolyak construction instead of using the full tensor product construction. In the error analysis, we divide the error into two parts and provide the error estimates respectively. Numerical examples have shown that the sparse grid collocation method preserves a high level of accuracy and it is a valid alternative to the more traditional Monte Carlo method. For the sparse grid stochastic collocation method, the deterministic PDE solver is usually considered as a “black-box” solver which is the case for interface problems. In order to apply the sparse isotropic Smolyak approximation, we must guarantee the error in the “black-box” small enough. The IFEM is a good choice as verified by our numerical experiments. The accuracy of the IFEM, in fact, reduces the total computational cost.

In this paper, we only considered the case that the coefficient of the PDE has random input. In real applications, it is also important to consider the interface itself as a random curve owing to the lack of information for the media (see [30]). Whether our current work can be extended to the random interfaces is under investigation.