Abstract
The classical continuous finite element method with Lagrangian \(Q^k\) basis reduces to a finite difference scheme when all the integrals are replaced by the \((k+1)\times (k+1)\) Gauss–Lobatto quadrature. We prove that this finite difference scheme is \((k+2)\)th order accurate in the discrete 2-norm for an elliptic equation with Dirichlet boundary conditions, which is a superconvergence result of function values. We also give a convenient implementation for the case \(k=2\), which is a simple fourth order accurate elliptic solver on a rectangular domain.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
1.1 Motivation
In this paper we consider solving a two-dimensional elliptic equation with smooth coefficients on a rectangular domain by high order finite difference schemes, which are constructed via using suitable quadrature in the classical continuous finite element method on a rectangular mesh. Consider the following model problem as an example: a variable coefficient Poisson equation \(-\nabla \cdot (a({\mathbf {x}})\nabla u)=f, a({\mathbf {x}})>0\) on a square domain \(\Omega =(0,1)\times (0,1)\) with homogeneous Dirichlet boundary conditions. The variational form is to find \(u\in H_0^1(\Omega )=\{v\in H^1(\Omega ): v|_{\partial \Omega }=0\}\) satisfying
where \(A(u,v)=\iint _{\Omega } a\nabla u \cdot \nabla v dx dy\), \( (f,v)=\iint _{\Omega }fv dxdy.\) Let h be the mesh size of an uniform rectangular mesh and \(V_0^h\subseteq H^1_0(\Omega )\) be the continuous finite element space consisting of piecewise \(Q^k\) polynomials (i.e., tensor product of piecewise polynomials of degree k), then the \(C^0\)-\(Q^k\) finite element solution is defined as \(u_h\in V_0^h\) satisfying
Standard error estimates of (1.1) are \(\Vert u-u_h\Vert _{1}\le C h^{k}\Vert u\Vert _{k+1}\) and \(\Vert u-u_h\Vert _{0}\le C h^{k+1}\Vert u\Vert _{k+1}\) where \(\Vert \cdot \Vert _k\) denotes \(H^k(\Omega )\)-norm, see [5]. For \(k\ge 2\), \({\mathcal {O}} (h^{k+1})\) superconvergence for the gradient at Gauss quadrature points and \({\mathcal {O}} (h^{k+2})\) superconvergence for functions values at Gauss–Lobatto quadrature points were proven for one-dimensional case in [1, 2, 11] and for two-dimensional case in [4, 8, 14, 17].
When implementing the scheme (1.1), integrals are usually approximated by quadrature. The most convenient implementation is to use \((k+1)\times (k+1)\) Gauss–Lobatto quadrature because they not only are superconvergence points but also can define all the degree of freedoms of Lagrangian \(Q^k\) basis. See Fig. 1 for the case \(k=2\). Such a quadrature scheme can be denoted as finding \(u_h\in V_0^h\) satisfying
where \(A_h(u_h,v_h)\) and \(\langle f,v_h\rangle _h\) denote using tensor product of \((k+1)\)-point Gauss–Lobatto quadrature for integrals \(A(u_h,v_h)\) and \((f,v_h)\) respectively.
An illustration of Lagrangian \(Q^2\) element and the \(3\times 3\) Gauss–Lobatto quadrature
It is well known that many classical finite difference schemes are exactly finite element methods with specific quadrature scheme, see [5]. We will write scheme (1.2) as an exact finite difference type scheme in Sect. 7 for \(k=2\). Such a finite difference scheme not only provides an efficient and also convenient way for assembling the stiffness matrix especially for a variable coefficient problem, but also with has advantages inherited from the variational formulation, such as symmetry of stiffness matrix and easiness of handling boundary conditions in high order schemes. This is the variational approach to construct a high order accurate finite difference scheme.
Classical quadrature error estimates imply that standard finite element error estimates still hold for (1.2), see [5, 7]. The focus of this paper is to prove that the superconvergence of function values at Gauss–Lobatto points still holds. To be more specific, for Dirichlet type boundary conditions, we will show that (1.2) with \(k\ge 2\) is a \((k+2)\)th order accurate finite difference scheme in the discrete 2-norm under suitable smoothness assumptions on the exact solution and the coefficients.
In this paper, the main motivation to study superconvergence is to use it for constructing \((k+2)\)th order accurate finite difference schemes. For such a task, superconvergence points should define all degree of freedoms over the whole computational domain including boundary points. For high order finite element methods, this seems possible only on quite structured meshes such as rectangular meshes for a rectangular domain and equilateral triangles for a hexagonal domain, even though there are numerous superconvergence results for interior cells in unstructured meshes.
1.2 Related Work and Difficulty in Using Standard Tools
To illustrate our perspectives and difficulties, we focus on the case \(k=2\) in the following. For computing the bilinear form in the scheme (1.1), another convenient implementation is to replace the smooth coefficient a(x, y) by a piecewise \(Q^2\) polynomial \(a_I(x,y)\) obtained by interpolating a(x, y) at the quadrature points in each cell shown in Fig. 1. Then one can compute the integrals in the bilinear form exactly since the integrand is a polynomial. Superconvergence of function values for such an approximated coefficient scheme was proven in [13] and the proof can be easily extended to higher order polynomials and three-dimensional cases. This result might seem surprising since interpolation error \(a(x,y)-a_I(x,y)\) is of third order. On the other hand, all the tools used in [13] are standard in the literature.
From a practical point of view, (1.2) is more interesting since it gives a genuine finite difference scheme. It is straightforward to use standard tools in the literature for showing superconvergence still holds for accurate enough quadrature. Even though the \(3\times 3\) Gauss–Lobatto quadrature is fourth order accurate, the standard quadrature error estimates cannot be used directly to establish the fourth order accuracy of (1.2), as will be explained in detail in Remark 3.8 in Sect. 3.2.
We can also rewrite (1.2) for \(k=2\) as a finite difference scheme but its local truncation error is only second order as will be shown in Sect. 7.4. The phenomenon that truncation errors have lower orders was named supraconvergence in the literature. The second order truncation error makes it difficult to establish the fourth order accuracy following any traditional finite difference analysis approaches.
To construct high order finite difference schemes from variational formulation, we can also consider finite element method with \(P^2\) basis on a regular triangular mesh in which two adjacent triangles form a rectangle [18]. Superconvergence of function values in \(C^0\)-\(P^2\) finite element method at the three vertices and three edge centers can be proven [4, 17]. See also [10]. Even though the quadrature using only three edge centers is third order accurate, error cancellations happen on two adjacent triangles forming a rectangle, thus fourth order accuracy of the corresponding finite difference scheme is still possible. However, extensions to construct higher order finite difference schemes are much more difficult.
1.3 Contributions and Organization of the Paper
The main contribution is to give the proof of the \((k+2)\)th order accuracy of (1.2) with \(k\ge 2\), which is an easy construction of high order finite difference schemes for variable coefficient problems. An important step is to obtain desired sharp quadrature estimate for the bilinear form, for which it is necessary to count in quadrature error cancellations between neighboring cells. Conventional quadrature estimating tools such as the Bramble–Hilbert Lemma only give the sharp estimate on each cell thus cannot be used directly. A key technique in this paper is to apply the Bramble–Hilbert Lemma after integration by parts on proper interpolation polynomials to allow error cancellations.
The paper is organized as follows. In Sect. 2, we introduce our notations and assumptions. In Sect. 3, standard quadrature estimates are reviewed. Superconvergence of bilinear forms with quadrature is shown in Sect. 4. Then we prove the main result for homogeneous Dirichlet boundary conditions in Sect. 5 and for nonhomogeneous Dirichlet boundary conditions in Sect. 6. Section 7 provides a simple finite difference implementation of (1.2). Section 8 contains numerical tests. Concluding remarks are given in Sect. 9.
2 Notations and Assumptions
2.1 Notations and Basic Tools
We will use the same notations as in [13]:
We only consider a rectangular domain \(\Omega =(0,1)\times (0,1)\) with its boundary denoted as \(\partial \Omega \).
Only for convenience, we assume \(\Omega _h\) is an uniform rectangular mesh for \({{\bar{\Omega }}}\) and \(e=[x_e-h,x_e+h]\times [y_e-h,y_e+h]\) denotes any cell in \(\Omega _h\) with cell center \((x_e,y_e)\). The assumption of an uniform mesh is not essential to the discussion of superconvergence. All superconvergence results in this paper can be easily extended to continuous finite element method with \(Q^k\) element on a quasi-uniform rectangular mesh, but not on a generic quadrilateral mesh or any curved mesh.
\(Q^k(e)=\left\{ p(x,y)=\sum \limits _{i=0}^k\sum \limits _{j=0}^k p_{ij} x^iy^j, (x,y)\in e\right\} \) is the set of tensor product of polynomials of degree k on a cell e.
\(V^h=\{p(x,y)\in C^0(\Omega _h): p|_e \in Q^{k}(e),\quad \forall e\in \Omega _h\}\) denotes the continuous piecewise \(Q^{k}\) finite element space on \(\Omega _h\).
\(V^h_0=\{v_h\in V^h: v_h=0 \quad \text{ on }\quad \partial \Omega \}.\)
The norm and seminorms for \(W^{k,p}(\Omega )\) and \(1\le p<+\infty \), with standard modification for \(p=+\infty \):
$$\begin{aligned}&\Vert u\Vert _{k,p,\Omega }=\left( \sum \limits _{i+j\le k}\iint _{\Omega }|\partial _x^i\partial _y^ju(x,y)|^pdxdy\right) ^{1/p},\\&|u|_{k,p,\Omega }=\left( \sum \limits _{i+j= k}\iint _{\Omega }|\partial _x^i\partial _y^ju(x,y)|^pdxdy\right) ^{1/p},\\&[u]_{k,p,\Omega }=\left( \iint _{\Omega }|\partial _x^k u(x,y)|^pdxdy+\iint _{\Omega }|\partial _y^k u(x,y)|^p dxdy\right) ^{1/p}. \end{aligned}$$Notice that \([u]_{k+1,p,\Omega }=0\) if u is a \(Q^k\) polynomial.
For simplicity, sometimes we may use \(\Vert u\Vert _{k,\Omega }\), \(|u|_{k,\Omega }\) and \([u]_{k,\Omega }\) denote norm and seminorms for \(H^k(\Omega )=W^{k,2}(\Omega )\).
When there is no confusion, \(\Omega \) may be dropped in the norm and seminorms, e.g., \(\Vert u\Vert _k=\Vert u\Vert _{k,2,\Omega }\).
For any \(v_h\in V^h\), \(1\le p<+\infty \)and \(k\ge 1\), we will abuse the notation to denote the broken Sobolev norm and seminorms by the following symbols
$$\begin{aligned} \Vert v_h\Vert _{k,p,\Omega }:= & {} \left( \sum _e\Vert v_h\Vert _{k,p,e}^p\right) ^{\frac{1}{p}}, \quad |v_h|_{k,p,\Omega }:= \left( \sum _e|v_h|_{k,p,e}^p\right) ^{\frac{1}{p}},\\ {[}v_h]_{k,p,\Omega }:= & {} \left( \sum _e[v_h]_{k,p,e}^p\right) ^{\frac{1}{p}}. \end{aligned}$$Let \(Z_{0,e}\) denote the set of \((k+1)\times (k+1)\) Gauss–Lobatto points on a cell e.
\(Z_0=\bigcup _e Z_{0,e}\) denotes all Gauss–Lobatto points in the mesh \(\Omega _h\).
Let \(\Vert u\Vert _{2,Z_0}\) and \(\Vert u\Vert _{\infty ,Z_0}\) denote the discrete 2-norm and the maximum norm over \(Z_0\) respectively:
$$\begin{aligned} \Vert u\Vert _{2,Z_0}=\left[ h^2\sum _{(x,y)\in Z_0} |u(x,y)|^2\right] ^{\frac{1}{2}},\quad \Vert u\Vert _{\infty ,Z_0}=\max _{(x,y)\in Z_0} |u(x,y)|. \end{aligned}$$For a continuous function f(x, y), let \(f_I(x,y)\) denote its piecewise \(Q^k\) Lagrange interpolant at \(Z_{0,e}\) on each cell e, i.e., \(f_I\in V^h\) satisfies:
$$\begin{aligned} f(x,y)=f_I(x,y), \quad \forall (x,y)\in Z_0. \end{aligned}$$\(P^k(t)\) denotes the set of polynomial of degree k of variable t.
\((f,v)_e\) denotes the inner product in \(L^2(e)\) and (f, v) denotes the inner product in \(L^2(\Omega )\):
$$\begin{aligned} (f,v)_e=\iint _{e} fv\, dxdy,\quad (f,v)=\iint _{\Omega } fv\, dxdy=\sum _e (f,v)_e. \end{aligned}$$\(\langle f,v\rangle _{e,h}\) denotes the approximation to \((f,v)_e\) by using \((k+1)\times (k+1)\)-point Gauss Lobatto quadrature with \(k \ge 2\) for integration over cell e.
\(\langle f,v\rangle _h\) denotes the approximation to (f, v) by using \((k+1)\times (k+1)\)-point Gauss Lobatto quadrature with \(k \ge 2\) for integration over each cell e.
\({\hat{K}}=[-1,1]\times [-1,1]\) denotes a reference cell.
For f(x, y) defined on e, consider \({\hat{f}}(s, t)=f(sh+ x_e,t h+ y_e)\) defined on \({\hat{K}}\). Let \({\hat{f}}_I\) denote the \(Q^k\) Lagrange interpolation of \({\hat{f}}\) at the \((k+1) \times (k+1)\) Gauss Lobatto quadrature points on \({\hat{K}}\).
\(({\hat{f}},{\hat{v}})_{{\hat{K}}}=\iint _{{\hat{K}}} {\hat{f}}{\hat{v}}\, dsdt.\)
\(\langle {\hat{f}},{\hat{v}}\rangle _{{\hat{K}}}\) denotes the approximation to \(({\hat{f}},{\hat{v}})_{{\hat{K}}}\) by using \((k+1) \times (k+1)\)-point Gauss–Lobatto quadrature.
On the reference cell \({\hat{K}}\), for convenience we use the superscript h over the ds or dt to denote we use \((k+1)\)-point Gauss–Lobatto quadrature on the corresponding variable. For example,
$$\begin{aligned} \iint _{{\hat{K}}} {\hat{f}} d^hsdt=\int _{-1}^{1}\left[ w_1{\hat{f}}(-1,t)+w_{k+1}{\hat{f}}(1,t)+ \sum _{i=2}^k w_i{\hat{f}}(x_i,t)\right] dt. \end{aligned}$$Since \(({\hat{f}}{\hat{v}})_I\) coincides with \({\hat{f}}{\hat{v}}\) at the quadrature points, we have
$$\begin{aligned} \iint _{{\hat{K}}} ({\hat{f}}{\hat{v}})_I dxdy=\iint _{{\hat{K}}} ({\hat{f}}{\hat{v}})_I d^hxd^hy=\iint _{{\hat{K}}} {\hat{f}}{\hat{v}} d^hxd^hy=\langle {\hat{f}},{\hat{v}}\rangle _{{\hat{K}}}. \end{aligned}$$
The following are commonly used tools and facts:
For two-dimensional problems,
$$\begin{aligned} h^{k-2/p}|v|_{k,p,e}=|{\hat{v}}|_{k,p,{\hat{K}}},\quad h^{k-2/p}[v]_{k,p,e}=[{\hat{v}}]_{k,p,{\hat{K}}}, \quad 1\le p\le \infty . \end{aligned}$$Inverse estimates for polynomials:
$$\begin{aligned} \Vert v_h\Vert _{k+1, e}\le C h^{-1} \Vert v_h\Vert _{k, e},\quad \forall v_h \in V^h, k\ge 0. \end{aligned}$$(2.1)Sobolev’s embedding in two and three dimensions: \(H^{2}({\hat{K}})\hookrightarrow C^0({\hat{K}})\).
The embedding implies
$$\begin{aligned}&\Vert {\hat{f}}\Vert _{0,\infty ,{\hat{K}}}\le C \Vert {\hat{f}}\Vert _{k,2, {\hat{K}}},\quad \forall {\hat{f}}\in H^{k}({\hat{K}}), k\ge 2,\\&\Vert {\hat{f}}\Vert _{1,\infty ,{\hat{K}}}\le C \Vert {\hat{f}}\Vert _{k+1,2, {\hat{K}}}, \quad \forall {\hat{f}}\in H^{k+1}({\hat{K}}), k\ge 2. \end{aligned}$$Cauchy–Schwarz inequalities in two dimensions:
$$\begin{aligned} \sum _e \Vert u\Vert _{k,e}\Vert v\Vert _{k,e}\le \left( \sum _e \Vert u\Vert ^2_{k,e}\right) ^{\frac{1}{2}}\left( \sum _e \Vert v\Vert ^2_{k,e}\right) ^{\frac{1}{2}}, \quad \Vert u\Vert _{k,1,e}={\mathcal {O}}(h) \Vert u\Vert _{k,2,e}. \end{aligned}$$Poincaré inequality: let \({\bar{u}}\) be the average of \(u\in H^1(\Omega )\) on \(\Omega \), then
$$\begin{aligned} |u-{\bar{u}}|_{0,p,\Omega }\le C |\nabla u|_{0,p,\Omega }, \quad p\ge 1. \end{aligned}$$If \({\bar{u}}\) is the average of \(u\in H^1(e)\) on a cell e, we have
$$\begin{aligned} |u-{\bar{u}}|_{0,p,e}\le C h |\nabla u|_{0,p,e}, \quad p\ge 1. \end{aligned}$$For \(k\ge 2\), the \((k+1)\times (k+1)\) Gauss–Lobatto quadrature is exact for integration of polynomials of degree \(2k-1\ge k+1\) on \({\hat{K}}\).
Define the projection operator \({\hat{\Pi }}_1: {\hat{u}} \in L^1({\hat{K}})\rightarrow {{\hat{\Pi }}}_1{\hat{u}}\in Q^1({\hat{K}})\) by
$$\begin{aligned} \iint _{{\hat{K}}} ({\hat{\Pi }}_1 \hat{u} ) w dsdt= \iint _{{\hat{K}}} \hat{u} w dsdt,\forall w\in Q^1({\hat{K}}). \end{aligned}$$(2.2)Notice that all degree of freedoms of \({\hat{\Pi }}_1 \hat{u}\) can be represented as a linear combination of \(\iint _{{\hat{K}}} {\hat{u}}(s,t) p(s,t)dsdt\) for \(p(s,t)=1,s,t,st\), thus the \(H^1({\hat{K}})\) (or \(H^2({\hat{K}})\)) norm of \({\hat{\Pi }}_1 \hat{u}\) are determined by \(\iint _{{\hat{K}}} {\hat{u}}(s,t) p(s,t)dsdt\). By Cauchy–Schwarz inequality \(|\iint _{{\hat{K}}} {\hat{u}}(s,t) {\hat{p}}(s,t)dsdt|\le \Vert {\hat{u}}\Vert _{0,2,{\hat{K}}}\Vert {\hat{p}}\Vert _{0,2,{\hat{K}}}\le C \Vert {\hat{u}}\Vert _{0,2,{\hat{K}}}\), we have \(\Vert \Pi _1 \hat{u}\Vert _{1,2,{\hat{K}}} \le C \Vert {\hat{u}}\Vert _{0,2,{\hat{K}}}\), which means \({\hat{\Pi }}_1\) is a continuous linear mapping from \(L^2({\hat{K}})\) to \(H^1({\hat{K}})\). By a similar argument, one can show \({\hat{\Pi }}_1\) is a continuous linear mapping from \(L^2({\hat{K}})\) to \(H^2({\hat{K}})\).
2.2 Coercivity and Elliptic Regularity
We consider the elliptic variational problem of finding \(u\in H_0^1(\Omega )\) to satisfy
where \({\mathbf {a}}=\begin{pmatrix} a^{11} &{}\quad a^{12}\\ a^{21} &{}\quad a^{22} \end{pmatrix}\) is real symmetric positive definite and \(\mathbf{b}=[b^1 \quad b^2]\). Assume the coefficients \({\mathbf {a}}\), \({\mathbf {b}}\) and c are smooth with uniform upper bounds, thus \(A(u,v)\le C\Vert u\Vert _1\Vert v\Vert _1\) for any \(u, v\in H^1_0(\Omega )\). We denote \(\lambda _{{\mathbf {a}}}\) as the smallest eigenvalues of \({\mathbf {a}}\). Assume \(\lambda _{{\mathbf {a}}}\) has a positive lower bound and \( \nabla \cdot {\mathbf {b}}\le 2c \), so that coercivity of the bilinear form can be easily achieved. Since
we have
By the equivalence of two norms \(|\cdot |_{1}\) and \(\Vert \cdot \Vert _{1}\) for the space \(H^1_0(\Omega )\) (see [5]), we conclude that the bilinear form \(A(u,v)=({\mathbf {a}} \nabla u, \nabla v)+({\mathbf {b}}\cdot \nabla u,v)+(c u, v)\) satisfies coercivity \(A(v,v)\ge C \Vert v\Vert _1\) for any \(v\in H^1_0(\Omega )\).
The coercivity can also be achieved if we assume \(| {\mathbf {b}}|< 4\lambda _{{\mathbf {a}}}c \). By Young’s inequality
we have
Let \(A^*\) be the dual operator of A, i.e., \(A^*(u,v)=A(v,u)\). We need to assume the elliptic regularity holds for the dual problem of (2.3) :
where C is independent of w and f. See [9, 16] for the elliptic regularity with Lipschitz continuous coefficients on a Lipschitz domain.
3 Quadrature Error Estimates
In the following, we will use \({\hat{\quad }}\) for a function to emphasize the function is defined on or transformed to the reference cell \({\hat{K}} =[-1,1]\times [-1,1]\) from a mesh cell.
3.1 Standard Estimates
The Bramble–Hilbert Lemma for \(Q^k\) polynomials can be stated as follows, see Exercise 3.1.1 and Theorem 4.1.3 in [6]:
Theorem 3.1
If a continuous linear mapping \({{\hat{\Pi }}}: H^{k+1}({\hat{K}})\rightarrow H^{k+1}({\hat{K}})\) satisfies \({{\hat{\Pi }}} {\hat{v}}={\hat{v}}\) for any \({\hat{v}}\in Q^k({\hat{K}})\), then
Thus if \(l(\cdot )\) is a continuous linear form on the space \(H^{k+1}({\hat{K}})\) satisfying \(l({\hat{v}})=0,\forall {\hat{v}}\in Q^k({\hat{K}}),\) then
where \( \Vert l\Vert '_{k+1, {\hat{K}}}\) is the norm in the dual space of \(H^{k+1}({\hat{K}})\).
By applying Bramble–Hilbert Lemma, we have the following standard quadrature estimates. See Theorems 2.3 and 2.4 in [13] for the detailed proof.
Theorem 3.2
For a sufficiently smooth function \(a(x,y) \in H^{2k}(e)\) and \(k \ge 2\), let m is an integer satisfying \(k\le m\le 2k\), we have
Theorem 3.3
If \(f\in H^{k+2}(\Omega )\) with \(k \ge 2\), then
Remark 3.4
By the Theorem 3.1, on the reference cell \({\hat{K}}\), for \(a(x,y) \in H^{k+2}(e)\) and \(k \ge 2\), we have
and
The following two results are also standard estimates obtained by applying the Bramble–Hilbert Lemma.
Lemma 3.5
If \(f\in H^{2}(\Omega )\) or \(f\in V^h\), we have \((f,v_h)-\langle f,v_h\rangle _h ={\mathcal {O}}(h^2) |f|_{2} \Vert v_h\Vert _0,\quad \forall v_h\in V^h.\)
Proof
For simplicity, we ignore the subscript in \(v_h\). Let E(f) denote the quadrature error for integrating f(x, y) on e. Let \({\hat{E}}({\hat{f}})\) denote the quadrature error for integrating \({\hat{f}}(s,t)=f(x_e+sh,y_e+th)\) on the reference cell \({\hat{K}}\). Due to the embedding \(H^{2}({\hat{K}})\hookrightarrow C^0({\hat{K}})\), we have
Thus the mapping \({\hat{f}}\rightarrow E({\hat{f}} {\hat{v}})\) is a continuous linear form on \(H^2({\hat{K}})\) and its norm is bounded by \(C\Vert {\hat{v}}\Vert _{0,{\hat{K}}}\). If \({\hat{f}} \in Q^1({\hat{K}})\), then we have \({\hat{E}}({\hat{f}} {\hat{v}})=0\). By the Bramble–Hilbert Lemma Theorem 3.1 on this continuous linear form, we get
So on a cell e, we get
Summing over all elements and use Cauchy–Schwarz inequality, we get the desired result. \(\square \)
Theorem 3.6
Assume all coefficients of (2.3) are in \(W^{2,\infty }(\Omega )\). We have
Proof
Following the same arguments as in the proof of Lemma 3.4, we have
Let \(f=a^{11} (v_h)_x\) and \(v = (z_h)_x \) in the estimate above, we get
where the inverse estimate (2.1) is used in the last inequality. Similarly, we have
which implies
\(\square \)
3.2 A Refined Consistency Error
In this subsection, we will show how to establish the desired consistency error estimate for smooth enough coefficients:
Theorem 3.7
Assume \(a(x,y)\in W^{k+2,\infty }(\Omega )\), \(u\in H^{k+3}(\Omega )\), \(k \ge 2\), then
Remark 3.8
We emphasize that Theorem 3.7 cannot be proven by applying the Bramble–Hilbert Lemma directly. Consider the constant coefficient case \(a(x,y)\equiv 1\) and \(k=2\) as an example,
Since the \(3 \times 3\) Gauss–Lobatto quadrature is exact for integrating \(Q^3\) polynomials, by Theorem 3.1 we have
Notice that \({\hat{v}}_h\) is \(Q^2\) thus \(({\hat{v}}_h)_{stt}\) does not vanish and \([({\hat{v}}_h)_s]_{4,{\hat{K}}}\le C |{\hat{v}}_h|_{3,{\hat{K}}}\). So by Bramble–Hilbert Lemma for \(Q^k\) polynomials, we can only get
Thus by Cauchy–Schwarz inequality after summing over e, we only have
In order to get the desired estimate involving only the broken \(H^2\)-norm of \(v_h\), we will take advantage of error cancellations between neighboring cells through integration by parts.
Proof
For simplicity, we ignore the subscript \(_h\) of \(v_h\) in this proof and all the following v are in \(V^h\) which are \(Q^k\) polynomials in each cell. First, by Theorem 3.3, we easily obtain (3.7) and (3.8):
We will only discuss \((au_x, v_x)-\langle au_x, v_x\rangle _h\) and the same discussion also applies to derive (3.6a) and (3.6b).
Since we have
where we use the fact \({\hat{a}}{\hat{u}}_s {\hat{v}}_s = ({\hat{a}}{\hat{u}}_s)_I{\hat{v}}_s\) on the Gauss–Lobatto quadrature points. For fixed t, \(({\hat{a}}{\hat{u}}_s)_I{\hat{v}}_s\) is a polynomial of degree \(2k-1\) w.r.t. variable s, thus the \((k+1)\)-point Gauss–Lobatto quadrature is exact for its s-integration, i.e.,
To estimate the quadrature error we introduce some intermediate values then do interpretation by parts,
For the first term in (3.12), let \(\overline{{\hat{v}}_s}\) be the cell average of \({\hat{v}}_s\) on \({\hat{K}}\), then
By (3.2) we have
By Cauchy–Schwarz inequality, the Bramble–Hilbert Lemma on interpolation error and Poincaré inequality, we have
Thus we have
For the second term in (3.12), we can estimate it the same way as in the proof of Theorem 2.4. in [13]. For each \({\hat{v}} \in Q^k({\hat{K}})\) we can define a linear form on \(H^k({\hat{K}})\) as
where \({\hat{F}}\) is an antiderivative of \({\hat{f}}\) w.r.t. variable s. Due to the linearity of interpolation operator and differentiating operation, \({\hat{E}}_{{\hat{v}}}\) is well defined. By the embedding \(H^{2}({\hat{K}})\hookrightarrow C^0({\hat{K}})\), we have
where we use the fact that all the norms on \(Q^k({\hat{K}})\) are equivalent to derive the first inequality. The above inequalities imply that the mapping \({\hat{E}}_{{\hat{v}}}\) is a continuous linear form on \(H^k({\hat{K}})\). With projection \(\Pi _1\) defined in (2.2), we have
Notice that \({\hat{F}}\) by definition is an antiderivative of \({\hat{f}}\) w.r.t. only variable s. If \({\hat{f}} \in Q^{k-1}({\hat{K}})\), then \({\hat{F}}_I\) is a polynomial of degree only \(k-1\) w.r.t. to variable t thus \(({\hat{F}}_I)_s\in Q^{k-1}({\hat{K}})\). The quadrature is exact for polynomials of degree \(2k-1\), thus \( Q^{k-1}({\hat{K}}) \subset \ker {\hat{E}}_{{\hat{v}} - \Pi _1{\hat{v}}}\). So by the Bramble–Hilbert Lemma, we get
and we also have
Thus we have
Now we only need to discuss the line integral term. Let \(L_2\) and \(L_4\) denote the left and right boundary of \(\Omega \) and let \(l^e_2\) and \(l^e_4\) denote the left and right edge of element e or \(l^{{\hat{K}}}_2\) and \(l^{{\hat{K}}}_4\) for \({\hat{K}}\). Since \(({\hat{a}}{\hat{u}}_s)_I{\hat{v}}\) mapped back to e will be \(\frac{1}{h}(au_x)_Iv\) which is continuous across \(l^e_2\) and \(l^e_4\), after summing over all elements e, the line integrals along the inner edges are canceled out and only the line integrals on \(L_2\) and \(L_4\) remain.
For a cell e adjacent to \(L_2\), consider its reference cell \({\hat{K}}\), and define a linear form \({\hat{E}}({\hat{f}} ) = \int _{-1}^1 {\hat{f}}(-1,t) dt - \int _{-1}^1 {\hat{f}}(-1,t)d^ht\), then we have
which means that the mapping \({\hat{f}} \rightarrow {\hat{E}}({\hat{f}} {\hat{v}})\) is continuous with operator norm less than \(C\Vert {\hat{v}}\Vert _{0,l^{{\hat{K}}}_2}\) for some C. Clearly we have
By the Theorem 3.1 we get
where the first inequality comes from the accuracy of the \((k+1)\)-point Gauss–Lobatto quadrature rule, i.e. \(\hat{E}({\hat{f}})=0,\, \forall {\hat{f}} \in Q^{2k-1}({\hat{K}})\). The \((k+1)\)-point Gauss–Lobatto quadrature rule also gives
For the third term in (3.12), we sum them up over all the elements. Then for the line integral along \(L_2\)
Let \(s_\alpha \) and \(\omega _\alpha \) (\(\alpha =1,2,\cdots , k+2\)) denote the quadrature points and weights in \((k+2)\)-point Gauss–Lobatto quadrature rule for \(s\in [-1,1]\). Since \({\hat{v}}^2_{tt}(s, t)\in Q^{2k}({\hat{K}})\), \((k+2)\)-point Gauss–Lobatto quadrature is exact for s-integration thus
which implies
thus
By Cauchy–Schwarz inequality and trace inequality, we have
Combine all the estimates above, we get (3.5b). Since the \(\frac{1}{2}\) order loss is only due to the line integral along the boundary \(\partial \Omega \). If \(v\in V_0^h\), \(v_{yy}=0\) on \(L_2\) and \(L_4\) so we have (3.5a). \(\square \)
4 Superconvergence of Bilinear Forms
The M-type projection in [3, 4] is a very convenient tool for discussing the superconvergence of function values. Let \(u_p\) be the M-type \(Q^k\) projection of the smooth exact solution u and its definition will be given in the following subsection. To establish the superconvergence of the original finite element method (1.1) for a generic elliptic problem (2.3) with smooth coefficients, one can show the following superconvergence of bilinear forms, see [4, 14] (see also [13] for a detailed proof):
In this section we will show the superconvergence of the bilinear form \(A_h\):
4.1 Definition of M-Type Projection
We first recall the definition of M-type projection. More detailed definition can also be found in [13]. Legendre polynomials on the reference interval \([-1,1]\) are given as
which are \(L^2\)-orthogonal to one another. Define their antiderivatives as M-type polynomials:
which satisfy the following properties:
If \(j-i\ne 0, \pm 2\), then \(M_i(t)\perp M_j(t)\), i.e., \(\int _{-1}^1 M_i(t)M_j(t) dt=0.\)
Roots of \(M_k(t)\) are the k-point Gauss–Lobatto quadrature points for \([-1,1]\).
Since Legendre polynomials form a complete orthogonal basis for \(L^{2}([-1,1])\), for any \({\hat{f}}(t)\in H^1([-1,1])\), its derivative \({\hat{f}}'(t)\) can be expressed as Fourier–Legendre series
The one-dimensional M-type projection is defined as \( {\hat{f}}_k(t)=\sum _{j=0}^{k}{\hat{b}}_{j}M_j(t), \) where \({\hat{b}}_0=\frac{{\hat{f}}(1)+{\hat{f}}(-1)}{2}\) is determined by \({\hat{b}}_1=\frac{{\hat{f}}(1)-{\hat{f}}(-1)}{2}\) so that \({\hat{f}}_k(\pm 1)={\hat{f}}(\pm 1)\). We have \( {\hat{f}}(t)=\lim \limits _{k\rightarrow \infty }{\hat{f}}_k(t)=\sum \limits _{j=0}^{\infty }{\hat{b}}_{j}M_j(t). \) The remainder \({\hat{R}}[{\hat{f}}]_k(t)\) of one-dimensional M-type projection is
For a function \({\hat{f}}(s,t)\in H^2({\hat{K}})\) on the reference cell \({\hat{K}}=[-1,1]\times [-1,1]\), its two-dimensional M-type expansion is given as
where
The M-type \(Q^k\) projection of \({\hat{f}}\) on \({\hat{K}}\) and its remainder are defined as
The M-type \(Q^k\) projection is equivalent to the point-line-plane interpolation used in [14, 15]. See Theorem 3.1 in [13] for the proof of the following fact:
Theorem 4.1
For \(k\ge 2\), the M-type \(Q^k\) projection is equivalent to the \(Q^k\) point-line-plane projection \(\Pi \) defined as follows:
- 1.
\(\Pi {\hat{u}}={\hat{u}}\) at four corners of \({\hat{K}}=[-1,1]\times [-1,1]\).
- 2.
\(\Pi {\hat{u}}-{\hat{u}}\) is orthogonal to polynomials of degree \(k-2\) on each edge of \({\hat{K}}\).
- 3.
\(\Pi {\hat{u}}-{\hat{u}}\) is orthogonal to any \({\hat{v}}\in Q^{k-2}({\hat{K}})\) on \({\hat{K}}\).
For f(x, y) on \(e=[x_e-h, x_e+h]\times [y_e-h, y_e+h]\), let \({\hat{f}}(s,t)= f( sh+x_e, t h+y_e)\) then the M-type \(Q^k\) projection of f on e and its remainder are defined as
Now consider a function \(u(x, y)\in H^{k+2} (\Omega )\), let \(u_p (x, y)\) denote its piecewise M-type \(Q^k\) projection on each element e in the mesh \(\Omega _h\). The first two properties in Theorem 4.1 imply that \(u_p (x, y)\) on each edge of e is uniquely determined by u(x, y) along that edge. So \(u_p (x, y)\) is a piecewise continuous \(Q^k\) polynomial on \(\Omega _h\).
M-type projection has the following properties. See Theorem 3.2, Lemmas 3.1 and 3.2 in [13] for the proof.
Theorem 4.2
For \(k \ge 2\),
Lemma 4.3
For \({\hat{f}} \in H^{k+1}({\hat{K}})\), \(k \ge 2\),
- 1.
\(|{\hat{R}}[{\hat{f}}]_{k,k}|_{0,\infty ,{\hat{K}}}\le C [{\hat{f}}]_{k+1,{\hat{K}}},\quad |\partial _s {\hat{R}}[{\hat{f}}]_{k,k}|_{0,\infty , {\hat{K}}}\le C[{\hat{f}}]_{k+1,{\hat{K}}}.\)
- 2.
\({\hat{R}}[{\hat{f}}]_{k+1,k+1}-{\hat{R}}[{\hat{f}}]_{k,k}=M_{k+1}(t)\sum _{i=0}^k {\hat{b}}_{i,k+1}M_{i}(s)+M_{k+1}(s)\sum _{j=0}^{k+1}{\hat{b}}_{k+1,j}M_j(t).\)
- 3.
\(|{\hat{b}}_{i,k+1}|\le C_k |{\hat{f}}|_{k+1,2,{\hat{K}}},|{\hat{b}}_{k+1,i}|\le C_k |{\hat{f}}|_{k+1,2,{\hat{K}}},\quad 0\le i\le k+1.\)
- 4.
If \({\hat{f}}\in H^{k+2}({\hat{K}})\), then \(|{\hat{b}}_{i,k+1}|\le C_k |{\hat{f}}|_{k+2,2,{\hat{K}}},\quad 1\le i\le k+1.\)
4.2 Estimates of M-Type Projection with Quadrature
Lemma 4.4
Assume \({\hat{f}}(s,t) \in H^{k+3}({\hat{K}})\), \(k \ge 2\),
Proof
First, we have
due to the fact that roots of \(M_{k+1}(t)\) are the \((k+1)\)-point Gauss–Lobatto quadrature points for \([-1,1]\).
We have
Then by Lemma 4.3,
Notice that we have \(\langle l_{k+1}(s)\sum _{j=0}^{k+2}{\hat{b}}_{k+2,j}M_j(t),1 \rangle _{{\hat{K}}}=0\) since the \((k+1)\)-point Gauss–Lobatto quadrature for s-integration is exact and \(l_{k+1}(s)\) is orthogonal to 1. Lemma 4.3 implies \(|{\hat{b}}_{i+1,k+2}|\le C[{\hat{f}}]_{k+3,{\hat{K}}}\) for \(i\ge 0\), thus we have
\(\square \)
Lemma 4.5
Assume \(a(x,y)\in W^{k,\infty }(\Omega )\), \(u(x,y)\in H^{k+3}(\Omega )\) and \(k \ge 2\). Then
Proof
As before, we ignore the subscript of \(v_h\) for simplicity. We have
and on each cell e,
For the first term in (4.2), we have
By Lemma 4.4,
By Lemma 4.3,
By Bramble–Hilbert Lemma Theorem 3.1 we have
and
Thus,
For the second term in (4.2), we have
Since \(M_{k+1}(t)\) vanishes at \((k+1)\) Gauss–Lobatto points, we have
For the second term in (4.4),
where the last step is due to the facts that \(({\hat{\Pi }}_1 {\hat{a}}) \overline{{\hat{v}}_s}\) and \(\overline{{\hat{a}}}({\hat{v}}_s- \overline{{\hat{v}}}_s)\) are polynomials of degree at most \(k-1\) with respect to variable s, the \((k+1)\)-point Gauss–Lobatto quadrature on s-integration is exact for polynomial of degree \(2k-1\), and \(l_k(s)\) is orthogonal to polynomials of lower degree. With Lemma 4.3, we have
Combined with (4.3), we have proved the estimate. \(\square \)
Lemma 4.6
Assume \(a(x,y)\in W^{2,\infty }(\Omega )\), \(u(x,y)\in H^{k+2}(\Omega )\) and \(k \ge 2\). Then
Proof
As before, we ignore the subscript of \(v_h\) for simplicity and
On each cell e we have
For the first term in (4.6), due to the embedding \(H^{2}({\hat{K}})\hookrightarrow C^0({\hat{K}})\), Bramble–Hilbert Lemma Theorem 3.1 and Lemma 4.3, we have
For the second term in (4.6), we have
and
Thus, we have \(\langle a (u-u_p), v_h\rangle _h=\mathcal O(h^{k+2})\Vert a\Vert _{2,\infty }\Vert u\Vert _{k+2}\Vert v_h\Vert _2\). \(\square \)
Lemma 4.7
Assume \(a\in W^{2,\infty }(\Omega )\), \(u\in H^{k+3}(\Omega )\) and \(k\ge 2\). Then
Proof
As before, we ignore the subscript in \(v_h\) and we have
On each cell e, we have
For the first term in (4.7), we have
Due to Lemma 4.4,
and by the same arguments as in the proof of Lemma 4.6 we have
Thus
For the second term in (4.7), we have
where the last step is due to that \(M_{k+1}(t)\) vanishes at \((k+1)\) Gauss–Lobatto points. Then
where the last step is due to the facts that \({\hat{\Pi }}_1( {\hat{a}}{\hat{v}})\) is a linear function in s thus the \((k+1)\)-point Gauss–Lobatto quadrature on s-variable is exact, and \(l_k(s)\) is orthogonal to linear functions.
By Lemma 4.3 and Theorem 3.1, we have
Thus
By (4.8) and (4.9) and sum up over all the cells, we get the desired estimate. \(\square \)
Lemma 4.8
Assume \(a(x,y)\in W^{4,\infty }(\Omega )\), \(u(x,y)\in H^{k+3}(\Omega )\) and \(k \ge 2\). Then
Proof
We ignore the subscript in \(v_h\) and we have
and on each cell e
By the same arguments as in the proof of Lemma 4.5, we have
and
For simplicity, we define
then by the third and fourth estimates in Lemma 4.3, we have
where \({\hat{b}}_{k+1}^{(m)}(t)\) is the mth derivative of \({\hat{b}}_{k+1}(t)\). We use the same technique in the proof of Theorem 3.7 and we let \(l_k = l_k(s)\), \(b_{k+1} = b_{k+1}(t)\) in the following,
and
After integration by parts with respect to the variable s, we have
which is exactly the same integral estimated in the proof of Lemma 3.7 in [13]. By the same proof of Lemma 3.7 in [13], after summing over all elements, we have the estimate for the term \(\iint _{{\hat{K}}}l_{k}(s){\hat{b}}_{k+1}(t){\hat{a}}{\hat{v}}_t dsdt\):
Then we can do similar estimation as in Theorem 3.7 for I, II, III separately.
For term I, by Theorem 3.1 and the estimate (3.2), we have
For term II, as in the proof of Theorem 3.7, we define the linear form as
for each \({\hat{v}} \in Q^k({\hat{K}})\) and \({\hat{F}}\) is an antiderivative of \({\hat{f}}\) w.r.t. variable t. We can easily see that \({\hat{E}}_{{\hat{v}}}\) is well defined and \({\hat{E}}_{{\hat{v}}}\) is a continuous linear form on \(H^k({\hat{K}})\). With projection \({\hat{\Pi }}_1\) defined in (2.2), we have
Since \( Q^{k-1}({\hat{K}}) \subset \ker {\hat{E}}_{{\hat{v}} - {\hat{\Pi }}_1{\hat{v}}}\) thus
and
Thus we have
Now we only need to discuss term III. Let \(L_1\) and \(L_3\) denote the top and bottom boundaries of \(\Omega \) and let \(l^e_1\), \(l^e_3\) denote the top and bottom edges of element e (and \(l^{{\hat{K}}}_1\) and \(l^{{\hat{K}}}_3\) for \({\hat{K}}\)). Notice that after mapping back to the cell e we have
and similarly we get \(b_{k+1}(y_e-h)={\hat{b}}_{k+1}(-1)=(k+\frac{1}{2})\int _{x_e-h}^{x_e+h} \partial _x u(x,y_e-h) l_k(\frac{x-x_e}{h})dx\). Thus the term \(l(\frac{x-x_e}{h})b_{k+1}(y)av\) is continuous across the top and bottom edges of cells. Therefore, if summing over all elements e, the line integral on the inner edges are cancelled out. So after summing over all elements, the line integral reduces to two line integrals along \(L_1\) and \(L_3\). We only need to discuss one of them. For a cell e adjacent to \(L_1\), consider its reference cell \({\hat{K}}\) and define linear form \({\hat{E}}({\hat{f}} ) = \int _{-1}^1 {\hat{f}}(s,1) ds - \int _{-1}^1 {\hat{f}}(s,1)d^hs\), then we have
thus the mapping \({\hat{f}} \rightarrow {\hat{E}}({\hat{f}} {\hat{v}})\) is continuous with operator norm less than \(C\Vert {\hat{v}}\Vert _{0,l^{{\hat{K}}}_1}\) for some C. Since \({\hat{E}}(({\hat{a}}{\hat{u}}_s)_I{{\hat{\Pi }}}_1 {\hat{v}})=0\) we have
where the first inequality is derived from \({\hat{E}}({\hat{f}}({\hat{v}}-{{\hat{\Pi }}}_1{\hat{v}}))=0, \forall {\hat{f}} \in Q^{k-1}({\hat{K}})\) and Theorem 3.1.
Since \(l_k(t)=\frac{1}{2^k k!}\frac{d^k}{dt^k} (t^2-1)^k\), after integration by parts k times,
where L(s) is a polynomial of degree 2k by taking antiderivatives of \(l_k(s)\)k times. Then by Cauchy–Schwarz inequality we have
By (3.13), we get \(|{\hat{v}}|_{2,l^{{\hat{K}}}_1} =h^{\frac{3}{2}}|{\hat{v}}|_{2,l^{e}_1} \le C h |v|_{2,e}. \) Thus we have
where the trace inequality \( \Vert u\Vert _{k+1,\partial \Omega } \le C \Vert u\Vert _{k+2, \Omega }\) is used.
Combine all the estimates above, we get (4.10a). Since the \(\frac{1}{2}\) order loss is only due to the line integral along \(L_1\) and \(L_3\), on which \(v_{xx}=0\) if \(v\in V^h_0\), we get 4.10b). \(\square \)
By all the discussions in this subsection, we have proven (4.1a) and (4.1b).
5 Homogeneous Dirichlet Boundary Conditions
5.1 \(V^h\)-Ellipticity
In order to discuss the scheme (1.2), we need to show \(A_h\) satisfies \(V^h\)-ellipticity
We first consider the \(V_h\)-ellipticity for the case \(\mathbf{b}\equiv 0\).
Lemma 5.1
Assume the coefficients in (2.3) satisfy that \({\mathbf {b}}\equiv 0\), both c(x, y) and the eigenvalues of \(\mathbf{a}(x,y)\) have a uniform upper bound and a uniform positive lower bound, then there exist two constants \(C_1, C_2>0\) independent of mesh size h such that
Proof
Let \(Z_{0,{\hat{K}}}\) denote the set of \((k+1)\times (k+1)\) Gauss–Lobatto points on the reference cell \({\hat{K}}\). First we notice that the set \(Z_{0,{\hat{K}}}\) is a \(Q^k({\hat{K}})\)-unisolvent subset. Since the Gauss–Lobatto quadrature weights are strictly positive, we have
where \(i=1,2\) represents the spatial derivative on variable \(x_i\) respectively. Since \(\partial _i {\hat{p}}\in Q^k({\hat{K}})\) and it vanishes on a \(Q^k({\hat{K}})\)-unisolvent subset, we have \(\partial _i {\hat{p}}\equiv 0\). As a consequence, \(\sqrt{\sum _{i=1}^{n}\langle \partial _i {\hat{p}},\partial _i {\hat{p}}\rangle _h}\) defines a norm over the quotient space \(Q^k({\hat{K}})/Q^0({\hat{K}})\). Since that \(|\cdot |_{1,{\hat{K}}}\) is also a norm over the same quotient space, by the equivalence of norms over a finite dimensional space, we have
On the reference cell \({\hat{K}}\), by the assumption on the coefficients, we have
Mapping these back to the original cell e and summing over all elements, by the equivalence of two norms \(|\cdot |_{1}\) and \(\Vert \cdot \Vert _{1}\) for the space \(H^1_0(\Omega )\supset V^h_0\) [5], we get \(C_1\Vert v_h\Vert ^2_1 \le A_h(v_h,v_h)\le C_2\Vert v_h\Vert ^2_1\). \(\square \)
For discussing \(V_h\)-ellipticity when \({\mathbf {b}}\) is nonzero, by Young’s inequality we have
Thus we have
where \(\lambda _{{\mathbf {a}}}\) is smallest eigenvalue of \({\mathbf {a}}\). Then we have the following Lemma
Lemma 5.2
Assume \(4\lambda _{{\mathbf {a}}}c > |{\mathbf {b}}|^2\), then there exists a constant \(C>0\) independent of mesh size h such that
5.2 Standard Estimates for the Dual Problem
In order to apply the Aubin–Nitsche duality argument for establishing superconvergence of function values, we need certain estimates on a proper dual problem. Define \(\theta _h:=u_h-u_p\). Then we consider the dual problem: find \(w\in H_0^1(\Omega )\) satisfying
where \(A^*(\cdot ,\cdot )\) is the adjoint bilinear form of \(A(\cdot ,\cdot )\) such that
Let \(w_h\in V_0^h\) be the solution to
Notice that the right hand side of (5.3) is different from the right hand side of the scheme (1.2).
We need the following standard estimates on \(w_h\) for the dual problem.
Theorem 5.3
Assume all coefficients in (2.3) are in \(W^{2,\infty }(\Omega )\). Let w be defined in (5.2), \(w_h\) be defined in (5.3), and \(\theta _h = u_h-u_p\). Assume elliptic regularity (2.6) and \(V^h\) ellipticity holds, we have
Proof
By \(V^h\) ellipticity, we have \(C_1\Vert w_h-v_h\Vert _1^2\le A^*_h(w_h-v_h, w_h-v_h)\). By the definition of the dual problem, we have
Thus for any \(v_h\in V_0^h\), by Theorem 3.6, we have
Thus
Now consider \(\Pi _1 w \in V^h_0\) where \(\Pi _1\) is the piecewise \(Q^1\) projection and its definition on each cell is defined through (2.2) on the reference cell. By the Bramble Hilbert Lemma Theorem 3.1 on the projection error, we have
thus \(\Vert \Pi _1 w\Vert _2\le \Vert w\Vert _2+\Vert w-\Pi _1 w\Vert _2\le C \Vert w\Vert _2\). By setting \(v_h=\Pi _1 w\), from (5.4) we have
By the inverse estimate on the piecewise polynomial \(w_h-\Pi _1 w\), we get
By (5.5) and (5.6), we also have
With (5.7), (5.8) and the elliptic regularity \(\Vert w\Vert _2\le C \Vert \theta _h\Vert _0\), we get
\(\square \)
5.3 Superconvergence of Function Values
Theorem 5.4
Assume \(a_{ij}, b_i, c \in W^{k+2,\infty }(\Omega )\) and \(u(x,y)\in H^{k+3}(\Omega )\), \(f(x,y)\in H^{k+2}(\Omega )\) with \(k \ge 2\). Assume elliptic regularity (2.6) and \(V^h\) ellipticity holds. Then \(u_h\), the numerical solution from scheme (1.2), is a \((k+2)\)th order accurate approximation to the exact solution u in the discrete 2-norm over all the \((k+1)\times (k+1)\) Gauss–Lobatto points:
Proof
By Theorems 3.7 and 3.3, for any \(v_h \in V^h_0\),
Let \(\theta _h=u_h-u_p\), then \(\theta _h\in V_0^h\) due to the properties of the M-type projection. So by (4.1a) and Theorem 5.3, we get
thus
Finally, by the equivalence of the discrete 2-norm on \(Z_0\) and the \(L^2(\Omega )\) norm in finite-dimensional space \(V^h\) and Theorem 4.2, we obtain
\(\square \)
Remark 5.5
To extend the discussions to Neumann type boundary conditions, due to (4.1b) and Theorem 3.7, one can only prove \((k+\frac{3}{2})\)th order accuracy:
On the other hand, for solving a general elliptic equation, only \({\mathcal {O}}(h^{k+\frac{3}{2}})\) superconvergence at all Lobatto point can be proven for Neumann boundary conditions even for the full finite element scheme (1.1), see [4].
Remark 5.6
All key discussions can be extended to three-dimensional cases. For instance, M-type expansion has been used for discussing superconvergence for the three-dimensional case [4]. The most useful technique in Sect. 3.2 to obtain desired consistency error estimate is to derive error cancellations between neighboring cells through integration by parts on suitable interpolation polynomials, which still seems possible on rectangular meshes in three dimensions.
6 Nonhomogeneous Dirichlet Boundary Conditions
We consider a two-dimensional elliptic problem on \(\Omega =(0,1)^2\) with nonhomogeneous Dirichlet boundary condition,
Assume there is a function \({\bar{g}} \in H^1(\Omega )\) as a smooth extension of g so that \({\bar{g}}|_{\partial \Omega } = g\). The variational form is to find \({{\tilde{u}}} = u - {\bar{g}} \in H_0^1(\Omega )\) satisfying
In practice, \({\bar{g}}\) is not used explicitly. By abusing notations, the most convenient implementation is to consider
and \(g_I\in V^h\) which is defined as the \(Q^k\) Lagrange interpolation at \((k+1)\times (k+1)\) Gauss–Lobatto points for each cell on \( \Omega \) of g(x, y). Namely, \(g_I\in V^h\) is the piecewise \(P^k\) interpolation of g along the boundary grid points and \(g_I=0\) at the interior grid points. The numerical scheme is to find \({{\tilde{u}}}_h \in V_0^h\), s.t.
Then \(u_h = {{\tilde{u}}}_h + g_I\) will be our numerical solution for (6.1). Notice that (6.3) is not a straightforward approximation to (6.2) since \({\bar{g}}\) is never used. Assuming elliptic regularity and \(V^h\) ellipticity hold, we will show that \(u_h-u\) is of \((k+2)\)th order in the discrete 2-norm over all \((k+1)\times (k+1)\) Gauss–Lobatto points.
6.1 An Auxiliary Scheme
In order to discuss the superconvergence of (6.3), we need to prove the superconvergence of an auxiliary scheme. Notice that we discuss the auxiliary scheme only for proving the accuracy of (6.3). In practice one should not implement the auxiliary scheme since (6.3) is a much more convenient implementation with the same accuracy.
Let \({\bar{g}}_p\in V^h\) be the piecewise M-type \(Q^k\) projection of the smooth extension function \({\bar{g}}\), and define \(g_p\in V^h\) as \(g_p={\bar{g}}_p\) on \(\partial \Omega \) and \(g_p = 0\) at all the inner grids. The auxiliary scheme is to find \({{\tilde{u}}}^{*}_h \in V_0^h\) satisfying
Then \(u^{*}_h = {{\tilde{u}}}^{*}_h + g_p\) is the numerical solution for problem (6.2). Define \(\theta _h=u^{*}_h-u_p\), then by Theorem 4.1 we have \(\theta _h \in V_0^h\). Following Sect. 5.2, define the following dual problem: find \(w\in H_0^1(\Omega )\) satisfying
Let \(w_h\in V_0^h\) be the solution to
Notice that the dual problem has homogeneous Dirichlet boundary conditions. By Theorems 3.3, 3.7, for any \(v_h \in V^h_0\),
By (4.1a) and Theorem 5.3, we get
thus \( \Vert u_h^{*}-u_p\Vert _0=\Vert \theta _h\Vert _0={\mathcal {O}}(h^{k+2})( \Vert u\Vert _{k+3} +\Vert f\Vert _{k+2}).\) So Theorem 5.4 still holds for the auxiliary scheme (6.4):
6.2 The Main Result
In order to extend Theorem 5.4 to (6.3), we only need to prove
The difference between (6.4) and (6.3) is
We need the following Lemma.
Lemma 6.1
Assuming \(u\in H^{k+4}(\Omega )\) for \(k \ge 2\), with \(g_I\) and \(g_p\) being defined as in this Section, then we have
Proof
For simplicity, we ignore the subscript \(_h\) of \(v_h\) in this proof and all the following v are in \(V^h\).
Notice that \(g_I-g_p\equiv 0\) in interior cells. Thus we only consider cells adjacent to \(\partial \Omega \). Let \(L_1, L_2, L_3\) and \(L_4\) denote the top, left, bottom and right boundary edges of \({{\bar{\Omega }}}=[0,1]\times [0,1]\) respectively. Without loss of generality, we consider cell \(e=[x_e-h,x_e+h]\times [y_e-h,y_e+h]\) adjacent to the left boundary \(L_2\), i.e., \(x_e-h=0\). Let \(l^e_1, l^e_2, l^e_3\) and \(l^e_4\) denote the top, left, bottom and right boundary edges of e respectively.
On \(l_2\subset L_2\), Let \(\phi _{ij}(x,y),i,j=0,1,\ldots ,k,\) be Lagrange basis functions on edge \(l_2^e\) for the \((k+1)\times (k+1)\) Gauss–Lobatto points in cell e. Then \(g_I-g_p = \sum _{i,j=0}^{k}\lambda _{ij} \phi _{ij}(x,y)\) and \(|\lambda _{ij}|\le \Vert g_I-g_p\Vert _{\infty ,Z_0}\). Due to Sobolev’s embedding, we have \(u\in W^{k+2,\infty }(\Omega )\). By Theorem 4.2, we have
Thus we get \(\forall v \in V^h_0\),
Since for polynomials on \({\hat{K}}\) all the norm are equivalent, we have
which implies
Similarly, for any \(v \in V^h_0\), we have
Thus we conclude that
\(\square \)
By (6.8) and Lemma 6.1, we have
Let \(\theta _h={{\tilde{u}}}^{*}_h- {{\tilde{u}}}_h \in V_0^h\). Following Sect. 5.2, define the following dual problem: find \(w\in H_0^1(\Omega )\) satisfying
Let \(w_h\in V_0^h\) be the solution to
By (6.10) and Theorem 5.3, we get
thus \( \Vert {{\tilde{u}}}^{*}_h- {{\tilde{u}}}_h\Vert _0=\Vert \theta _h\Vert _0=\mathcal O(h^{k+2}) \Vert u\Vert _{k+4}.\) By equivalence of norms for polynomials, we have
Notice that both \({{\tilde{u}}}_h\) and \({{\tilde{u}}}^*_h\) are constant zero along \(\partial \Omega \), and \(u_h|_{\partial \Omega }=g_I\) is the Lagrangian interpolation of g along \(\partial \Omega \). With (6.7), we have proven the following main result.
Theorem 6.2
Assume elliptic regularity (2.6) and \(V^h\) ellipticity holds. For a nonhomogeneous Dirichlet boundary problem (6.1), with suitable smoothness assumptions for \(k \ge 2\), \(a_{ij}, b_i, c \in W^{k+2,\infty }(\Omega )\), the exact solution of (6.2) \(u(x,y) = {{\tilde{u}}} + {\bar{g}} \in H^{k+4}(\Omega )\) and \(f(x,y)\in H^{k+2}(\Omega )\), the numerical solution \(u_h\) by scheme (6.3) is a \((k+2)\)th order accurate approximation to u in the discrete 2-norm over all the \((k+1)\times (k+1)\) Gauss–Lobatto points:
7 Finite Difference Implementation
In this section we present the finite difference implementation of the scheme (6.3) for the case \(k=2\) on a uniform mesh. The finite difference implementation of the nonhomogeneous Dirichlet boundary value problem is based on a homogeneous Neumann boundary value problem, which will be discussed first. We demonstrate how it is derived for the one-dimensional case then give the two-dimensional implementation. It provides efficient assembling of the stiffness matrix and one can easily implement it in MATLAB. Implementations for higher order elements or quasi-uniform meshes can be similarly derived, even though it will no longer be a conventional finite difference scheme on a uniform grid.
7.1 One-Dimensional Case
Consider a homogeneous Neumann boundary value problem \( -(au')' = f \text { on } [0,1], u'(0) = 0, u'(1) = 0, \) and its variational form is to seek \(u\in H^1([0,1])\) satisfying
Consider a uniform mesh \(x_i = ih\), \(i = 0,1,\ldots , n+1 \), \(h=\frac{1}{n+1}\). Assume n is odd and let \(N=\frac{n+1}{2}\). Define intervals \(I_k =[x_{2k},x_{2k+2}]\) for \(k=0,\ldots ,N-1\) as a finite element mesh for \(P^2\) basis. Define
Let \(\{v_i\}_{i=0}^{n+1} \subset V^h \) be a basis of \(V^h\) such that \(v_i(x_j)= \delta _{ij}, \,i,j=0,1,\ldots ,n+1\). With 3-point Gauss–Lobatto quadrature, the \(C^0\)-\(P^2\) finite element method for (7.1) is to seek \(u_h\in V^h\) satisfying
Let \(u_j=u_h(x_j)\), \(a_j=a(x_j)\) and \(f_j=f(x_j)\) then \(u_h(x)=\sum \limits _{j=0}^{n+1} u_jv_j(x)\). We have
The matrix form of this scheme is \({\bar{S}}\bar{ {\mathbf {u}}}={\bar{M}} \bar{{\mathbf {f}}}\), where
the stiffness matrix \({\bar{S}}\) is has size \((n+2)\times (n+2)\) with (i, j)th entry as \(\langle a v_i',v_j'\rangle _h\), and the lumped mass matrix M is a \((n+2)\times (n+2)\) diagonal matrix with diagonal entries \(h \begin{pmatrix} \frac{1}{3},\frac{4}{3},\frac{2}{3},\frac{4}{3},\frac{2}{3},\ldots ,\frac{2}{3},\frac{4}{3},\frac{1}{3} \end{pmatrix}\).
Next we derive an explicit representation of the matrix \({\bar{S}}\). Since basis functions \(v_i\in V^h\) and \(u_h(x)\) are not \(C^1\) at the knots \(x_{2k}\) (\(k=1,2,\ldots ,N-1\)), their derivatives at the knots are double valued. We will use superscripts \(+\) and − to denote derivatives obtained from the right and from the left respectively, e.g., \(v'^+_{2k}\) and \(v'^-_{2k+2}\) denote the derivatives of \(v_{2k}\) and \(v_{2k+2}\) respectively in the interval \(I_{k}=[x_{2k}, x_{2k+2}]\). Then in the interval \(I_{k}=[x_{2k}, x_{2k+2}]\) we have the following representation of derivatives
By abusing notations, we use \((v_i)'_{2k}\) to denote the average of two derivatives of \(v_i\) at the knots \(x_{2k}\):
Let \([v_i]\) denote the difference between the right derivative and left derivative:
Then at the knots, we have
We also have
Let \({\mathbf {v}}_i\) denote a column vector of size \(n+2\) consisting of grid point values of \(v_i(x)\). Plugging (7.4) into (7.5), with (7.3), we get
where A is a diagonal matrix with diagonal entries \(a_0,a_1,\ldots ,a_{n},a_{n+1}\), and
Since \(\{v_i\}_{i=0}^{n}\) are the Lagrangian basis for \(V^h\), we have
Now consider the one-dimensional Dirichlet boundary value problem:
Consider the same mesh as above and define
Then \(\{v_i\}_{i=1}^{n} \subset V^h \) is a basis of \(V^h_0\) for \(\{v_i\}_{i=0}^{n+1}\) defined above. The one-dimensional version of (6.3) is to seek \(u_h\in V^h_0\) satisfying
Notice that we can obtain (7.7) by simply setting \(u_h(0)=\sigma _0\) and \(u_h(1)=\sigma _1\) in (7.2). So the finite difference implementation of (7.7) is given as follows:
- 1.
Assemble the \((n+2)\times (n+2)\) stiffness matrix \({\bar{S}}\) for homogeneous Neumann problem as in (7.6).
- 2.
Let S denote the \(n\times n\) submatrix \({\bar{S}}(2:n+1, 2:n+1)\), i.e., \([{\bar{S}}_{ij}]\) for \(i,j=2,\cdots , n+1\).
- 3.
Let \({\mathbf {l}}\) denote the \(n\times 1\) submatrix \(\bar{S}(2:n+1, 1)\) and \({\mathbf {r}}\) denote the \(n\times 1\) submatrix \(\bar{S}(2:n+1, n+2)\), which correspond to \(v_0(x)\) and \(v_{n+1}(x)\).
- 4.
Let \({\mathbf {u}}=\begin{bmatrix} u_1&u_2&\cdots&u_n \end{bmatrix}^T\) and \({\mathbf {f}}=\begin{bmatrix} f_1&f_2&\cdots&f_n \end{bmatrix}^T\). Define \({\mathbf {w}}=\begin{bmatrix} \frac{4}{3},\frac{2}{3},\frac{4}{3},\frac{2}{3},\ldots ,\frac{2}{3},\frac{4}{3} \end{bmatrix} \) as a column vector of size n. The scheme (7.7) can be implemented as
$$\begin{aligned} S {\mathbf {u}}= h {\mathbf {w}}^T{\mathbf {f}} -\sigma _0\mathbf{l}-\sigma _1{\mathbf {r}}. \end{aligned}$$
7.2 Notations and Tools for the Two-Dimensional Case
We will need two operators:
Kronecker product of two matrices: if A is \(m \times n\) and B is \(p\times q\), then \(A\otimes B\) is \(mp\times nq\) give by
$$\begin{aligned} A\otimes B=\begin{pmatrix} a_{11}B &{}\quad \cdots &{}\quad a_{1n} B\\ \vdots &{}\quad \vdots &{}\quad \vdots \\ a_{m1}B &{}\quad \cdots &{}\quad a_{mn} B \end{pmatrix}. \end{aligned}$$For a \(m\times n\) matrix X, vec(X) denotes the vectorization of the matrix X by rearranging X into a vector column by column.
The following properties will be used:
- 1.
\((A \otimes B)(C \otimes D)=AC \otimes BD\).
- 2.
\((A \otimes B)^{-1}=A^{-1}\otimes B^{-1}\).
- 3.
\((B^T\otimes A)vec(X)=vec(AXB)\).
- 4.
\((A \otimes B)^T=A^T \otimes B^T.\)
Consider a uniform grid \((x_i,y_j)\) for a rectangular domain \(\bar{\Omega }=[0,1]\times [0,1]\) where \(x_i = ih_x\), \(i = 0,1,\ldots , n_x+1\), \(h_x=\frac{1}{n_x+1}\) and \(y_j = jh_y\), \(j = 0,1,\ldots , n_y+1\), \(h_y=\frac{1}{n_y+1}\).
Assume \(n_x\) and \(n_y\) are odd and let \(N_x=\frac{n_x+1}{2}\) and \(N_y=\frac{n_y+1}{2}\). We consider rectangular cells \(e_{kl} =[x_{2k},x_{2k+2}]\times [y_{2l},y_{2l+2}]\) for \(k=0,\ldots ,N_x-1\) and \(l=0,\ldots ,N_y-1\) as a finite element mesh for \(Q^2\) basis. Define
For the coefficients \({\mathbf {a}}(x,y)=\begin{pmatrix} a^{11} &{}\quad a^{12}\\ a^{21} &{}\quad a^{22} \end{pmatrix} \), \({\mathbf {b}}=[b^1 \quad b^2]\) and c in the elliptic operator (2.3), consider their grid point values in the following form:
Let \(diag({\mathbf {x}})\) denote a diagonal matrix with the vector \({\mathbf {x}}\) as diagonal entries and define
Let \(s=x\) or y, we define the D and E matrices with dimension \({(n_s+2)\times (n_s+2)}\) for each variable:
Define an inflation operator \(Infl: \mathbb {R}^{n_y\times n_x}\longrightarrow \mathbb {R}^{(n_y+2)\times (n_x+2)}\) by adding zeros:
and its matrix representation is given as \({{\tilde{I}}}_x \otimes \tilde{I}_y\) where
Its adjoint is a restriction operator \(Res: \mathbb {R}^{(n_y+2)\times (n_x+2)} \longrightarrow \mathbb {R}^{n_y\times n_x} \) as
and its matrix representation is \({{\tilde{I}}}_x^T \otimes \tilde{I}_y^T.\)
7.3 Two-Dimensional Case
For \({{\bar{\Omega }}}=[0,1]^2\) we first consider an elliptic equation with homogeneous Neumann boundary condition:
The variational form is to find \(u\in H^1(\Omega )\) satisfying
The \(C^0\)-\(Q^2\) finite element method with \(3\times 3\) Gauss–Lobatto quadrature is to find \(u_h\in V^h\) satisfying
Let \({\bar{U}}\) be a \((n_y+2)\times (n_x+2)\) matrix such that its (j, i)th entry is \({\bar{U}}(j,i)=u_h(x_{i-1},y_{j-1})\), \(i=1,\ldots ,n_x+2\), \(j=1,\ldots ,n_y+2\). Let \({\bar{F}}\) be a \((n_y+2)\times (n_x+2)\) matrix such that its (j, i)th entry is \({\bar{F}}(j,i)=f(x_{i-1},y_{j-1})\). Then the matrix form of (7.11) is
where
Now consider the scheme (6.3) for nonhomogeneous Dirichlet boundary conditions. Its numerical solution can be represented as a matrix U of size \(ny\times nx\) with (j, i)-entry \(U(j,i)=u_h(x_i, y_j)\) for \(i=1,\cdots , nx; j=1,\cdots , ny\). Similar to the one-dimensional case, its stiffness matrix can be obtained as the submatrix of \({\bar{S}}\) in (7.12). Let \({\bar{G}}\) be a \((n_y+2)\) by \((n_x+2)\) matrix with (j, i)th entry as \(\bar{G}(j,i)=g(x_{i-1},y_{j-1})\), where
In particular, \({\bar{G}}(j+1,i+1) = 0\) for \(j=1,\ldots ,n_y\), \(i=1,\ldots ,n_x\). Let F be a matrix of size \(ny\times nx\) with (j, i)-entry as \(F(j,i)=f(x_i, y_j)\) for \(i=1,\cdots , nx; j=1,\cdots , ny\). Then the scheme (6.3) becomes
Even though the stiffness matrix is given as \(S=({{\tilde{I}}}_x^T\otimes {{\tilde{I}}}_y^T){\bar{S}}({{\tilde{I}}}_x\otimes {{\tilde{I}}}_y)\), S should be implemented as a linear operator in iterative linear system solvers. For example, the matrix vector multiplication \((\tilde{I}_x^T\otimes {{\tilde{I}}}_y^T)S^{11}_a({{\tilde{I}}}_x\otimes \tilde{I}_y)vec(U)\) is equivalent to the following linear operator from \(\mathbb {R}^{ny\times nx}\) to \(\mathbb {R}^{ny\times nx}\):
where \(\circ \) is the Hadamard product (i.e., entrywise multiplication).
7.4 The Laplacian Case
For one-dimensional constant coefficient case with homogeneous Dirichlet boundary condition, the scheme can be written as a classical finite difference scheme \(H {\mathbf {u}}={\mathbf {f}}\) with
In other words, if \(x_i\) is a cell center, the scheme is
and if \(x_i\) is a knot away from the boundary, the scheme is
It is straightforward to verify that the local truncation error is only second order.
For the two-dimensional Laplacian case homogeneous Dirichlet boundary condition, the scheme can be rewritten as
where \(H_x\) and \(H_y\) are the same H matrix above with size \(n_x\times n_x\) and \(n_y\times n_y\) respectively. The inverse of \((H_x\otimes I_y)+(I_x\otimes H_y)\) can be efficiently constructed via the eigen-decomposition of small matrices \(H_x\) and \(H_y\):
- 1.
Compute eigen-decomposition of \(H_x=T_x \Lambda _x T_x^{-1}\) and \(H_y=T_y \Lambda _y T_y^{-1}\).
- 2.
The properties of Kronecker product imply that
$$\begin{aligned} (H_x\otimes I_y)+(I_x\otimes H_y)=(T_x\otimes T_y)(\Lambda _x\otimes I_y+I_x\otimes \Lambda _y)(T_x^{-1}\otimes T_y^{-1}), \end{aligned}$$thus
$$\begin{aligned} {[}(H_x\otimes I_y)+(I_x\otimes H_y)]^{-1}=(T_x\otimes T_y)(\Lambda _x\otimes I_y+I_x\otimes \Lambda _y)^{-1}(T_x^{-1}\otimes T_y^{-1}). \end{aligned}$$ - 3.
It is nontrivial to determine whether H is diagonalizable. In all our numerical tests, H has no repeated eigenvalues. So if assuming \(\Lambda _x\) and \(\Lambda _y\) are diagonal matrices, the matrix vector multiplication \([(H_x\otimes I_y)+(I_x\otimes H_y)]^{-1}vec(F)\) can be implemented as a linear operator on F:
$$\begin{aligned} T_y([T_y^{-1} F(T_x^{-1})^T]./\Lambda )T_x^T, \end{aligned}$$(7.14)where \(\Lambda \) is a \(n_y\times n_x\) matrix with (i, j)th entry as \(\Lambda (i,j)=\Lambda _y(i,i)+\Lambda _x(j,j)\) and ./ denotes entry-wise division for two matrices of the same size.
For the 3D Laplacian, the matrix can be represented as \(H_x\otimes I_y\otimes I_z+I_x\otimes H_y\otimes I_z+I_x\otimes I_y\otimes H_z\) thus can be efficiently inverted through eigen-decomposition of small matrices \(H_x, H_y\) and \(H_z\) as well.
Since the eigen-decomposition of small matrices \(H_x\) and \(H_y\) can be precomputed, and (7.14) costs only \(\mathcal O(n^3)\) for a 2D problem on a mesh size \(n\times n\), in practice (7.14) can be used as a simple preconditioner in conjugate gradient solvers for the following linear system equivalent to (7.13):
even though the multigrid method as reviewed in [19] is the optimal solver in terms of computational complexity.
8 Numerical Results
In this section we show a few numerical tests verifying the accuracy of the scheme (6.3) for \(k=2\) implemented as a finite difference scheme on a uniform grid. We first consider the following two dimensional elliptic equation:
where \({\mathbf {a}}=\left( {\begin{array}{cc} a_{11} &{} a_{12} \\ a_{21} &{} a_{22} \\ \end{array} } \right) \), \(a_{11}=10+30y^5+x\cos {y}+y\), \(a_{12}=a_{21}=2+0.5(\sin (\pi x)+x^3)(\sin (\pi y)+y^3)+\cos (x^4+y^3)\), \(a_{22}=10+x^5\), \({\mathbf {b}}={\mathbf {0}}\), \(c=1+x^4y^3\), with an exact solution
The errors at grid points are listed in Table 1 for purely Dirichlet boundary condition and Table 2 for purely Neumann boundary condition. We observe fourth order accuracy in the discrete 2-norm for both tests, even though only \({\mathcal {O}}(h^{3.5})\) can be proven for Neumann boundary condition as discussed in Remark 5.5. Regarding the maximum norm of the superconvergence of the function values at Gauss–Lobatto points, one can only prove \({\mathcal {O}}(h^3\log h)\) even for the full finite element scheme (1.1) since discrete Green’s function is used, see [4].
Next we consider a three-dimensional problem \(-\Delta u=f\) with homogeneous Dirichlet boundary conditions on a cube \([0,1]^3\) with the following exact solution
See Table 3 for the performance of the finite difference scheme. There is no essential difficulty to extend the proof to three dimensions, even though it is not very straightforward. Nonetheless we observe that the scheme is indeed fourth order accurate. The linear system is solved by the eigenvector method shown in Sect. 7.4. The discrete 2-norm over the set of all grid points \(Z_0\) is defined as \(\Vert u\Vert _{2,Z_0}=\left[ h^3\sum _{(x,y,z)\in Z_0} |u(x,y,z)|^2\right] ^{\frac{1}{2}}\).
Last we consider (8.1) with convection term and the coefficients \({\mathbf {b}}\) is incompressible \(\nabla \cdot \mathbf{b}=0\): \({\mathbf {a}}=\left( {\begin{array}{cc} a_{11} &{} a_{12} \\ a_{21} &{} a_{22} \\ \end{array} } \right) \), \(a_{11}=100+30y^5+x\cos {y}+y\), \(a_{12}=a_{21}=2+0.5(\sin (\pi x)+x^3)(\sin (\pi y)+y^3)+\cos (x^4+y^3)\), \(a_{22}=100+x^5\), \({\mathbf {b}}=\left( {\begin{array}{c} b_{1} \\ b_{2} \\ \end{array} } \right) \), \(b_1=\psi _y\), \(b_2=-\psi _x\), \(\psi = x\exp (x^2+y)\), \(c=1+x^4y^3\), with an exact solution
The errors at grid points are listed in Table 4 for Dirichlet boundary conditions.
9 Concluding Remarks
In this paper we have proven the superconvergence of function values in the simplest finite difference implementation of \(C^0\)-\(Q^k\) finite element method for elliptic equations. In particular, for the case \(k=2\) the scheme (6.3) can be easily implemented as a fourth order accurate finite difference scheme as shown in Sect. 7. It provides only only an convenient approach for constructing fourth order accurate finite difference schemes but also the most efficient implementation of \(C^0\)-\(Q^k\) finite element method without losing superconvergence of function values. In a follow up paper [12], we will show that discrete maximum principle can be proven for the scheme (6.3) in the case \(k=2\) when solving a variable coefficient Poisson equation.
References
Bakker, M.: A note on \(C^0\) Galerkin methods for two-point boundary problems. Numer. Math. 38, 447–453 (1982)
Chen, C.: Superconvergent points of Galerkin’s method for two point boundary value problems. Numer. Math. A J. Chin. Univ. 1, 73–79 (1979)
Chen, C.: Superconvergence of finite element solutions and their derivatives. Numer. Math. A J. Chin. Univ. 3, 118–125 (1981)
Chen, C.: Structure Theory of Superconvergence of Finite Elements (In Chinese). Hunan Science and Technology Press, Changsha (2001)
Ciarlet, P.G.: Basic error estimates for elliptic problems. Handb. Numer. Anal. 2, 17–351 (1991)
Ciarlet, P.G.: The Finite Element Method for Elliptic Problems. Society for Industrial and Applied Mathematics, Philadelphia (2002)
Ciarlet, P.G., Raviart, P.-A.: The combined effect of curved boundaries and numerical integration in isoparametric finite element methods. In: The Mathematical Foundations of the Finite Element Method with Applications to Partial Differential Equations, pp. 409–474. Elsevier (1972)
Douglas, J., Dupont, T., Wheeler, M.F.: An \(L^{\infty }\) estimate and a superconvergence result for a Galerkin method for elliptic equations based on tensor products of piecewise polynomials. ESAIM Math. Model. Numer. Anal. 8, 61–66 (1974)
Grisvard, P.: Elliptic Problems in Nonsmooth Domains, vol. 69. SIAM, Philadelphia (2011)
Huang, Y., Xu, J.: Superconvergence of quadratic finite elements on mildly structured grids. Math. Comput. 77, 1253–1268 (2008)
Lesaint, P., Zlamal, M.: Superconvergence of the gradient of finite element solutions. RAIRO Anal. Numér. 13, 139–166 (1979)
Li, H., Zhang, X.: On the monotonicity and discrete maximum principle of the finite difference implementation of \(C^0\)-\(Q^2\) finite element method. arXiv preprint arXiv:1905.06422 (2019)
Li, H., Zhang, X.: Superconvergence of \(C^0\)-\( Q^k \) finite element method for elliptic equations with approximated coefficients. arXiv preprint arXiv:1902.00945 (2019)
Lin, Q., Yan, N.: Construction and Analysis for Efficient Finite Element Method (In Chinese). Hebei University Press, Baoding (1996)
Lin, Q., Yan, N., Zhou, A.: A rectangle test for interpolated finite elements. In: Proceedings of Systems Science and Systems Engineering, pp. 217–229. Great Wall Culture Publ. Co, Hong Kong (1991)
Savaré, G.: Regularity results for elliptic equations in Lipschitz domains. J. Funct. Anal. 152, 176–201 (1998)
Wahlbin, L.: Superconvergence in Galerkin Finite Element Methods. Springer, Berlin (2006)
Whiteman, J.: Lagrangian finite element and finite difference methods for Poisson problems. In: Collatz, L. (ed.) Numerische Behandlung von Differentialgleichungen, pp. 331–355. Springer, Berlin (1975)
Xu, J., Zikatanov, L.: Algebraic multigrid methods. Acta Numer. 26, 591–721 (2017)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Research is supported by the NSF Grants DMS-1522593 and DMS-1913120.
Rights and permissions
About this article
Cite this article
Li, H., Zhang, X. Superconvergence of High Order Finite Difference Schemes Based on Variational Formulation for Elliptic Equations. J Sci Comput 82, 36 (2020). https://doi.org/10.1007/s10915-020-01144-w
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10915-020-01144-w
Keywords
- Superconvergence
- High order accurate discrete Laplacian
- Elliptic equations
- Finite difference scheme based on variational formulation
- Gauss–Lobatto quadrature