Vertex-centered finite volume schemes of any order over quadrilateral meshes for elliptic boundary value problems

Abstract

A family of any order finite volume (FV) schemes over quadrilateral meshes is analyzed under the framework of Petrov–Galerkin method. By constructing a special mapping from the trial space to the test space, a unified proof for the inf–sup condition of any order FV schemes is provided under a weak condition that the underlying mesh is an $h^{1+\gamma },\gamma >0$ parallelogram mesh. The optimal convergence rate of FV solutions is then obtained with well-known techniques.

1 Introduction

Due to its local conservation property and other advantages, the finite volume method (FVM) has a wide range of applications in scientific and engineering computations see, e.g., [12, 16, 17, 21–27]. Comparing to its wide applications, the mathematical theory of FVM (cf., [1–7, 9, 11, 13–15, 18, 19]) has not been fully developed, especially for high order schemes.

A main difficulty in the theoretical analysis is the establishment of the stability result (or inf–sup condition in general) for higher order FV schemes. Earlier approaches (see, e.g. [6, 19, 20, 28]) in the literature often adopt the so-called element stiffness matrix analysis by calculating eigenvalues of the stiffness matrix. The stability is established if all eigenvalues of the stiffness matrix are positive. This technique has been successful for linear, quadratic, and cubic elements under different triangular mesh conditions. However, generalization to higher-order elements must be done case-by-case under more and more restrictive mesh conditions. On the other hand, those mesh conditions required for stability are usually sufficient but might not be necessary. Therefore, it is necessary to develop a general framework in analyzing FV schemes of arbitrary order with a common and yet less restrictive mesh condition.

In this paper, we provide a unified analysis for vertex-centered FV schemes of any order over quadrilateral meshes, which is completely different from the classical element stiffness matrix analysis. An essential idea behind our analysis is the following: (1) construct a special mapping from the trial space to the test space. This mapping transfers the bilinear form defined on the trial-test spaces to a bilinear form on the trial space only, and thereby changes the the analysis framework from a Petrov–Galerkin method to a Galerkin finite element method. (2) The transferred bilinear form can be expressed on each element as a summation of function values with weights at those discrete points of the dual partition. With some proper selection of the dual partition points, e.g, the Gauss points, the summation can be viewed as a numerical quadrature (such as the Gauss-quadrature) of a finite element bilinear form. Consequently, coercivity proof of the transferred bilinear form becomes possible.

It is a challenging task to construct the from-trial-to-test-space mapping over an arbitrary unstructured quadrilateral mesh. In this paper, to guarantee the FV bilinear form to be expressed as the summation of function values at Gauss points, we establish our mapping through constraining at all Gauss points. Since the total number of the Gauss points is often greater than the dimension of the test space, it is necessary to justify the existence and uniqueness of our construction. To this end, we first determine those redundant constraints and eliminate them to obtain linearly independent constraints. Then by a discussion of the relation between the number of Gauss points and the dimension of the test space, we prove that the number of linearly independent constraints equals the dimension of the test space. In this way, our operator is uniquely defined.

Another major difficulty in the analysis is: unlike the triangular mesh, the transformation from the reference square to an arbitrary quadrilateral is no longer an affine mapping. As a consequence, the integrand in the transferred bilinear form are not polynomials anymore. We have to take into account of residual of the numerical quadrature. Special care and new design must be taken for the underlying FVM to overcome this difficulty.

Our main result is: Under the shape regular assumption and $h^{1+\gamma }$ distortion (to be specified in Sect. 2) of the mesh, the inf–sup condition is valid for sufficiently small $h$, and hence the error under the $H^1$-norm has the optimal rate of convergence. Different from previous case-by-case works on FVM for linear, quadratic, and cubic quadrilateral elements, our analysis is applicable to any order FVM. Furthermore, our mesh-condition is more relaxed in two aspects: (1) We only require that the minimum interior angle of any quadrilateral is bounded from below; and (2) the mesh distortion parameter $\gamma >0$ can be arbitrarily small. Note that $\gamma = 0$ implies an arbitrary quadrilateral without any structure. Therefore, our mesh condition here is very much similar to the most relaxed mesh condition in finite element methods.

The rest of the paper is organized as follows. In Sect. 2, we present the properties of unstructured quadrilateral meshes. In Sect. 3, we present and analyze a family of FV schemes over quadrilateral meshes under the inf–sup condition. In Sect. 4, we provide a rigorous proof for the inf–sup condition. Several numerical examples illustrating our theory is presented in Sect. 5. A brief conclusion is given in the final and sixth section.

In the rest of this paper, “$A\lesssim B$” means that $A$ can be bounded by $B$ multiplied by a constant which is independent of the parameters which $A$ and $B$ may depend on. “$A\sim B$” means “$A\lesssim B$” and “$B\lesssim A$”.

2 Quadrilateral meshes

Let $\Omega \subset R^2$ be a simply connected polygon. We partition $\Omega$ into the union of a finite number of convex quadrilaterals and denote this quadrilateral mesh by ${\mathcal {T}}_h$, where $h$ is the largest diameter of all quadrilaterals. We denote by ${\mathcal {N}}_h$ and ${\mathcal {E}}_h$ respectively the set of all vertices and all edges of ${\mathcal {T}}_h$. Moreover, let ${\mathcal {N}}_h^\circ ={\mathcal {N}}_h{\setminus }\partial \Omega$, ${\mathcal {E}}_h^\circ ={\mathcal {E}}_h{\setminus }\partial \Omega , {\mathcal {N}}_h^b= {\mathcal {N}}_h\cap \partial \Omega ,{\mathcal {E}}_h^b={\mathcal {E}}_h{\setminus }\partial \Omega$ be the set of interior vertices, internal edges, boundary vertices and boundary edges, respectively.

We call ${\mathcal {T}}_h$ conforming if different quadrilaterals in ${\mathcal {T}}_h$ have no common interior points and a vertex of any quadrilateral does not lie on the interior of a side of any other quadrilateral. We call ${\mathcal {T}}_h$ shape regular if there exist a positive constant $c_1$ and some angle $0<\theta _0<\pi /3$ such that

$$\begin{aligned} \frac{h_\tau }{\rho _\tau } \le c_1,\quad \theta _\tau \ge \theta _0,\quad \forall \tau \in {\mathcal {T}}_h, \end{aligned}$$

where $\rho _\tau ,\theta _\tau$ are the maximum diameter of circles contained in $\tau$ and the minimal interior angle of $\tau$, respectively. For a quadrilateral $\tau \in {\mathcal {T}}_h$, let $d_\tau$ be the distance between midpoints of two diagonals of $\tau$. If $d_\tau ={\mathcal {O}}(h^{1+\gamma }),\gamma \ge 0$, we call $\tau$ an $h^{1+\gamma }$ parallelogram (cf., [8, 26]). If all quadrilaterals in ${\mathcal {T}}_h$ are $h^{1+\gamma }$-parallelograms, we call ${\mathcal {T}}_h$ an $h^{1+\gamma }$ -parallelogram mesh. Note that $\gamma =0$ represents arbitrary quadrilateral meshes, $\gamma =\infty$ represents parallelogram meshes.

For an arbitrary quadrilateral mesh, there exist some relations between the cardinalities of vertices, edges and elements. First, we observe that for a quadrilateral mesh ${\mathcal {T}}_h$,

$$\begin{aligned} \#{\mathcal {N}}^b_h=\#{\mathcal {E}}_h^b \end{aligned}$$

(2.1)

and $\#{\mathcal {E}}_h^b$ must be an even integer, where $\#S$ is the cardinality of some set $S$. Moreover, we have the following relationship

$$\begin{aligned} \#{\mathcal {T}}_h=\frac{1}{2}\#{\mathcal {E}}_h^\circ +\frac{1}{4}\#{\mathcal {E}}_h^b=\#{\mathcal {N}}^\circ _h+\frac{1}{2}\#{\mathcal {N}}_h^b-1. \end{aligned}$$

(2.2)

In fact, since each quadrilateral in ${\mathcal {T}}_h$ has four edges, each interior edge belongs to two quadrilaterals while each boundary edge only belongs to one quadrilateral, we have

$$\begin{aligned} 4\#{\mathcal {T}}_h=2\#{\mathcal {E}}_h^\circ +\#{\mathcal {E}}_h^b. \end{aligned}$$

The first equality in (2.2) is verified. We next show the second equality of (2.2) by induction. When $\#{\mathcal {T}}_h=1$, we have $\#{\mathcal {N}}^\circ _h=0$, $\#{\mathcal {N}}_h^b=4$. Therefore the second equality of (2.2) is valid when $\#{\mathcal {T}}_h=1$. Now we suppose the above equality holds for any mesh ${\mathcal {T}}_h$ with $\#{\mathcal {T}}_h=k$. Let $\tilde{{\mathcal {T}}}_h$ be some quadrilateral mesh with $\#\tilde{{\mathcal {T}}}_h=k+1$. The mesh $\tilde{{\mathcal {T}}}_h$ can be obtained by adding a boundary quadrilateral $\tau$ to a mesh ${\mathcal {T}}_h$ with $\#{\mathcal {T}}_h=k$. Since both the union of the elements in ${\mathcal {T}}_h$ and $\tilde{T}_h$ are simply-connected, there are only three cases: (1) One edge of $\tau$ coincides with a boundary edge of ${\mathcal {T}}_h$, in this case, $\tilde{{\mathcal {N}}}_h^\circ ={\mathcal {N}}^\circ _h, \tilde{{\mathcal {N}}}_h^b={\mathcal {N}}_h^b+2$. (2) Two edges of $\tau$ coincide with two boundary edges of ${\mathcal {T}}_h$, in this case, $\tilde{{\mathcal {N}}}^\circ _h={\mathcal {N}}^\circ _h+1, \tilde{{\mathcal {N}}}_h^b={\mathcal {N}}_h^b$. (3) Three edges of $\tau$ coincide with three boundary edges of ${\mathcal {T}}_h$, in this case, $\tilde{{\mathcal {N}}}^\circ _h={\mathcal {N}}^\circ _h+2, \tilde{{\mathcal {N}}}_h^b={\mathcal {N}}_h^b-2$. We find that in all above 3 cases, we have $\#\tilde{{\mathcal {N}}}^\circ _h+\frac{1}{2}\#\tilde{{\mathcal {N}}}_h^b=k+2$. In other words, we have

$$\begin{aligned} \#\tilde{{\mathcal {T}}}_h=\#\tilde{{\mathcal {N}}}^\circ _h+\frac{1}{2}\#\tilde{{\mathcal {N}}}_h^b-1. \end{aligned}$$

Therefore, the second equality of (2.2) is also valid.

The mesh discussed in this paper maybe completely unstructured. We next explain how to label the boundary edges and the four vertices of an element $\tau \in {\mathcal {T}}_h$. If two edges $E_1,E_2\in {\mathcal {E}}_h$ belong to the same quadrilateral $\tau$ and they have no intersections, we call $E_2$ an opposite edge of $E_1$ and denote $E_2=op(E_1,\tau )$. For two edges $E,F\in {\mathcal {E}}_h$, if there exists a finite number of quadrilaterals $\tau _1,\ldots ,\tau _{m-1}$ and associated edges $E_1,\ldots , E_m\in {\mathcal {E}}_h, m\ge 2$ such that $E_1=E, E_m=F, E_{i+1}=op(E_i,\tau _i),i=1,\ldots , m-1$, then we call $F$ as a (far) opposite edge of $E$ and we denote $F=op(E,\tau _1,\ldots ,\tau _{m-1})$ or simply denote $F=op(E)$. If $F_1=op(E),F_2=op(E)$, the number of opposite edges between $E$ and $F_1$ is smaller than that between $E$ and $F_2$, we say that $F_1$ is closer to $E$ than $F_2$. The boundary edge set ${\mathcal {E}}_h^b$ can be split into two subsets ${\mathcal {E}}_h^{b1}$ and ${\mathcal {E}}_h^{b2}$ such that ${\mathcal {E}}_h^{b2}=\{F=op(E)|E\in {\mathcal {E}}_h^{b1}\}$. We list edges in ${\mathcal {E}}_h^{b1}$ by ${\mathcal {E}}_h^{b1}=\{E_i|i=1,\ldots , \frac{\# {\mathcal {E}}_h^b}{2}\}$, then ${\mathcal {E}}_h^{b2}=\{F_i=op(E_i)|i=1,\ldots , \frac{\# {\mathcal {E}}_h^b}{2}\}$, see Fig. 1 for an example in which ${\mathcal {E}}_h^{b1}=\{E_1,\ldots ,E_6\}$ and ${\mathcal {E}}_h^{b2}=\{F_1,\ldots ,F_6\}$ with $F_i=op(E_i), i=1,\ldots ,6$. For a quadrilateral $\tau \in {\mathcal {T}}_h$, its four vertices should be labeled such that: (1) $P_1, P_2,P_3,P_4$ are arranged in counter-clock order. (2) If $E_i, E_j\in {\mathcal {E}}_h^{b1},$ are the boundary edges such that $P_1P_2=E_i\; \text{ or }\; op(E_i), P_3P_4=op(E_i)$ and $P_1P_4=E_j\; \text{ or }\; op(E_j), P_3P_4=op(E_j)$, we require that $P_1P_2$ is closer to $E_i$ than $P_3P_4$, $P_1P_4$ is closer to $E_j\in {\mathcal {E}}_h^{b1}$ than $P_2P_3$. See also Fig. 1 for an example where the four vertices of a $\tau$ are labeled.

Fig. 1

Labeling boundary edges and 4 vertices of a quadrilateral

It is well-known that the geometry of a quadrilateral $\tau =\square P_1P_2P_3P_4\in {\mathcal {T}}_h$ is determined by a transformation from the reference square $\tau _0=[-1,1]^2$ to $\tau$ (cf., e.g. [29, 30]). For all $(\xi ,\eta )\in \tau _0$, let $(x,y)=F_\tau (\xi ,\eta )$ be defined by

$$\begin{aligned} x&= x_1 + \alpha _2^\tau \frac{1+\xi }{2} + \alpha _4^\tau \frac{1+\eta }{2} +\alpha _3^\tau \frac{(1+\xi )(1+\eta )}{4},\\ y&= y_1 + \beta _2^\tau \frac{1+\xi }{2} + \beta _4^\tau \frac{1+\eta }{2} +\beta _3^\tau \frac{(1+\xi )(1+\eta )}{4}, \end{aligned}$$

where $(x_i, y_i)$ is the coordinate of the vertices $P_i,i = 1, 2, 3, 4$ and

$$\begin{aligned} \alpha _2^\tau&= x_2-x_1,\alpha _4^\tau =x_4-x_1,\alpha _3^\tau =x_1-x_2+x_3-x_4,\\ \beta _2^\tau&= y_2-y_1,\ \beta _4^\tau =y_4-y_1,\ \beta _3^\tau =y_1-y_2+y_3-y_4. \end{aligned}$$

Obviously, we have $F_\tau (-1,-1)=P_1, F_\tau (1,-1)\!=\!P_2, F_\tau (1,1)=P_3, F_\tau (-1,1)=P_4$. Moreover, noticing $d_\tau =\frac{1}{2}\sqrt{|\alpha _3^\tau |^2+|\beta _3^\tau |^2}$, we have $\alpha ^\tau _3=\beta ^\tau _3=0$ if $\tau$ is a parallelogram; $\alpha _3^\tau =\beta _3^\tau =\alpha _4^\tau =\beta _2^\tau =0$ if $\tau$ is a rectangle; $\sqrt{|\alpha _3^\tau |^2+|\beta _3^\tau |^2}={\mathcal {O}}(h^{1+\gamma }),$ if $\tau$ is an $h^{1+\gamma }$-parallelogram.

We next introduce Gauss and Lobatto points in ${\mathcal {T}}_h$. For any integer $n\ge 1$, we denote $\mathbb {Z}_n=\{1,\ldots ,n\},\, \mathbb {Z}_n^0=\{0,1,\ldots ,n\}$. Let $\{l_m|m\in \mathbb {Z}^0_r\}$ be $r+1$ Lobatto points of degree $r$ in the interval $[-1,1]$, that is, $l_0=-1, l_r=1$ and $\{l_m|m\in \mathbb {Z}_{r-1}\}$ are the $r-1$ zeros of $L'_{r}$, where $L_r$ is the Legendre polynomial of degree $r$ in $[-1,1]$. We denote the set of Lobatto points in $\tau$ as

$$\begin{aligned} {\mathcal {N}}_\tau =\{L^\tau _{i,j}|i,j\in \mathbb {Z}^0_r\}, \end{aligned}$$

where $L^\tau _{i,j}=F_\tau (l_i,l_j)$. Moreover let ${\mathcal {N}}=\cup _{\tau \in {\mathcal {T}}_h}{\mathcal {N}}_\tau$ be the set of all Lobatto points in ${\mathcal {T}}_h$. Let $\{g_i|i\in \mathbb {Z}_r\}$ be the $r$ Gauss points, i.e., zeros of $L_r$, the Legendre polynomial of degree $r$, on the interval $[-1,1]$. We denote the set of Gauss points in $\tau$ by

$$\begin{aligned} {\mathcal {G}}_\tau =\{G^\tau _{i,j}| i,j\in \mathbb {Z}_r\}, \end{aligned}$$

where $G^\tau _{i,j}=F_\tau (g_i,g_j)$. We denote the set of all Gauss points in ${\mathcal {T}}_h$ by ${\mathcal {G}}=\cup _{\tau \in {\mathcal {T}}_h}{\mathcal {G}}_\tau .$ As an example, the Gauss and Lobatto points of a quadrilateral $\tau$ for $r=2$ are depicted in Fig. 2.

Fig. 2

Gauss and Lobatto points in a quadrilateral ($r = 2$)

We next compare the cardinality of the set of Gauss points ${\mathcal {G}}$ and the cardinality of the set of the interior Lobatto points ${\mathcal {N}}^\circ ={\mathcal {N}}{\setminus } \partial \Omega$. Obviously

$$\begin{aligned} \#{\mathcal {G}}=\#{\mathcal {T}}_h r^2, \end{aligned}$$

where $\#{\mathcal {T}}_h$ is the number of quadrilaterals in ${\mathcal {T}}_h$. We next calculate $\#{\mathcal {N}}^\circ$. Since ${\mathcal {N}}^\circ$ consists of the interior vertices, the Lobatto points in the interior of quadrilaterals and the Lobatto points in the interior of internal edges, we have

$$\begin{aligned} \#{\mathcal {N}}^\circ =\#{\mathcal {N}}^\circ _h+\#({\mathcal {E}}_h^\circ )(r-1)+\#{\mathcal {T}}_h(r-1)^2. \end{aligned}$$

Substituting (2.2) and (2.1) into the above formula, we obtain

$$\begin{aligned} \#{\mathcal {N}}^\circ =(\#{\mathcal {T}}_h)r^2-\frac{1}{2}(\#{\mathcal {E}}_h^b)r+1. \end{aligned}$$

(2.3)

In other words,

$$\begin{aligned} \#{\mathcal {N}}^\circ =\#{\mathcal {G}}-\frac{1}{2}(\#{\mathcal {E}}_h^b)r+1. \end{aligned}$$

(2.4)

We next study further properties of the transformation $F_\tau ,\tau \in {\mathcal {T}}_h$. It is easy to calculate the Jacobi matrix

$$\begin{aligned} DF_\tau (\xi ,\eta )=\left( \begin{array}{ll} \frac{\partial x}{\partial \xi } &{} \frac{\partial y}{\partial \xi }\\ \frac{\partial x}{\partial \eta } &{} \frac{\partial y}{\partial \eta } \end{array}\right) =\left( \begin{array}{ll} \frac{\alpha _2^\tau }{2}+\frac{\alpha _3^\tau (1+\eta )}{4} &{} \frac{\beta _2^\tau }{2}+\frac{\beta _3^\tau (1+\eta )}{4}\\ \frac{\alpha _4^\tau }{2}+\frac{\alpha _3^\tau (1+\xi )}{4} &{} \frac{\beta _4^\tau }{2}+\frac{\beta _3^\tau (1+\xi )}{4} \end{array}\right) , \end{aligned}$$

and its inverse

$$\begin{aligned} DF^{-1}_\tau (\xi ,\eta )=J_\tau ^{-1}\left( \begin{array}{rr} \frac{\partial y}{\partial \eta } &{} -\frac{\partial y}{\partial \xi }\\ -\frac{\partial x}{\partial \eta } &{} \frac{\partial x}{\partial \xi } \end{array}\right) , \end{aligned}$$

where the determinant of the Jacobi matrix $DF_\tau$ is

$$\begin{aligned} J_\tau =J_{\tau ,p}+J_{\tau ,\xi }(1+\xi ) +J_{\tau ,\eta }(1+\eta ), \end{aligned}$$

with

$$\begin{aligned} J_{\tau ,p}=\frac{1}{4}(\alpha _2^\tau \beta _4^\tau -\alpha _4^\tau \beta _2^\tau ), J_{\tau ,\xi }=\frac{1}{8}(\alpha _2^\tau \beta _3^\tau -\alpha _3^\tau \beta _2^\tau ),J_{\tau ,\eta }= \frac{1}{8}(\alpha _3^\tau \beta _4^\tau -\alpha _4^\tau \beta _3^\tau ). \end{aligned}$$

Since $\tau =\square P_1P_2P_3P_4$ is convex and its vertices $P_1,P_2,P_3,P_4$ are labeled counter-clockwisely, we have

$$\begin{aligned} J_{\tau ,p}=\frac{1}{2} S_{\Delta P_1P_2P_4}>0. \end{aligned}$$

Since $\tau$ is a shape regular $h^{1+\gamma }$ parallelogram, we have

$$\begin{aligned} J_{\tau ,p}={\mathcal {O}}(h^2), J_{\tau ,\xi } ,J_{\tau ,\eta }={\mathcal {O}}(h^{2+\gamma }). \end{aligned}$$

(2.5)

We close this section by a study of the relationship of directional derivatives of a function on $\tau$ and that on $\tau _0$. Let $v$ be a differentiable function defined on $\tau$ and $\hat{v}_\tau =v\circ F_\tau$ be a function defined on $\tau _0$. We denote the gradient of $v$ on $\tau$ by $\bigtriangledown v=(\frac{\partial v}{\partial x}, \frac{\partial v}{\partial y})^T$ and the gradient of $\hat{v}_\tau$ on $\tau _0$ by $\hat{\bigtriangledown }{{\hat{v}}_\tau }=(\frac{\partial \hat{v}_\tau }{\partial \xi }, \frac{\partial \hat{v}_\tau }{\partial \eta })^T$. A straightforward calculation yields that

$$\begin{aligned} \hat{\bigtriangledown }^{{\hat{v}}_\tau }=DF_\tau \bigtriangledown v \end{aligned}$$

Let $\mathbf{n}=(n_1,n_2)$ be a unit direction, we have the directional derivative

$$\begin{aligned} \frac{\partial v}{\partial \mathbf{n}}&= \mathbf{n}\cdot \bigtriangledown v=\mathbf{n}\cdot DF_\tau ^{-1}\hat{\bigtriangledown }^{{\hat{v}}_\tau }\nonumber \\&= J_\tau ^{-1}\left( \left( \frac{\partial y}{\partial \eta } n_1 -\frac{\partial x}{\partial \eta } n_2\right) \frac{\partial \hat{v}_\tau }{\partial \xi }+\left( -\frac{\partial y}{\partial \xi }n_1+\frac{\partial x}{\partial \xi }n_2\right) \frac{\partial \hat{v}_\tau }{\partial \eta }\right) . \end{aligned}$$

(2.6)

We next derive the directional derivatives for some specific $\mathbf{n}$.

For all $(\xi ,\eta )\in \tau _0$, $F_\tau ([-1,1]\times \{\eta \})$ and $F_\tau (\{\xi \}\times [-1,1]\})$ are two segments in $\tau$ which passing the point $F_\tau (\xi ,\eta )$. We let

$$\begin{aligned} r^{\tau ,1}_{\xi ,\eta }=|F_\tau ([-1,1]\times \{\eta \})|/2,\quad r^{\tau ,2}_{\xi ,\eta }=|F_\tau (\{\xi \}\times [-1,1]\})|/2 \end{aligned}$$

be the length of two vectors $\frac{1}{2} \overrightarrow{F_{\tau }(-1,\eta )F_\tau (1,\eta )}$ and $\frac{1}{2} \overrightarrow{F_{\tau }(\xi ,-1)F_\tau (\xi ,1)}$, respectively. A straightforward calculation yields

$$\begin{aligned} (r^{\tau ,1}_{\xi ,\eta })^2=\left( \frac{\alpha _2^\tau }{2}+ \frac{\alpha ^\tau _3(1+\eta )}{4}\right) ^2+ \left( \frac{\beta _2^\tau }{2}+\frac{\beta ^\tau _3(1+\eta )}{4}\right) ^2, \end{aligned}$$

and

$$\begin{aligned} (r^{\tau ,2}_{\xi ,\eta })^2=\left( \frac{\alpha _4^\tau }{2} +\frac{\alpha ^\tau _3(1+\xi )}{4}\right) ^2+ \left( \frac{\beta _4^\tau }{2}+\frac{\beta ^\tau _3(1+\xi )}{4}\right) ^2. \end{aligned}$$

We also let

$$\begin{aligned} s^\tau _{\xi ,\eta }&= \left( \frac{\alpha _2^\tau }{2}+\frac{\alpha _3^\tau (1+\eta )}{4}\right) \left( \frac{\alpha _4^\tau }{2}+\frac{\alpha _3^\tau (1+\xi )}{4}\right) \\&+ \left( \frac{\beta _2^\tau }{2}+\frac{\beta _3^\tau (1+\eta )}{4}\right) \left( \frac{\beta _4^\tau }{2}+\frac{\beta _3^\tau (1+\xi )}{4}\right) \end{aligned}$$

be the inner product of two vectors $\frac{1}{2} \overrightarrow{F_{\tau }(-1,\eta )F_\tau (1,\eta )}$ and $\frac{1}{2} \overrightarrow{F_{\tau }(\xi ,-1)F_\tau (\xi ,1)}$. Since ${\mathcal {T}}_h$ is shape regular, there exists a minimal angle $\theta _0$ such that each angle of the quadrilateral $\tau$ is larger than $\theta _0$. Thus we have

$$\begin{aligned} |s^\tau _{\xi ,\eta }|\le \cos \theta _0 r^{\tau ,1}_{\xi ,\eta }r^{\tau ,2}_{\xi ,\eta }. \end{aligned}$$

(2.7)

For a fixed $\eta$, the normal direction on the edge $\overrightarrow{F_{\tau }(-1,\eta )F_\tau (1,\eta )}$ is

$$\begin{aligned} \mathbf{n}^1_{\xi ,\eta }=\left( -\frac{\beta _2^\tau }{2}-\frac{\beta ^\tau _3(1+\eta )}{4}, \frac{\alpha _2^\tau }{2}+\frac{\alpha _3^\tau (1+\eta )}{4}\right) \Big /r_{\xi ,\eta }^{\tau ,1}. \end{aligned}$$

Similarly, for a fixed $\xi$, the normal direction on the edge $\overrightarrow{F_{\tau }(\xi ,-1)F_\tau (\xi ,1)}$ is

$$\begin{aligned} \mathbf{n}^2_{\xi ,\eta }=\left( \frac{\beta _4^\tau }{2}+\frac{\beta ^\tau _3(1+\xi )}{4}, -\frac{\alpha _4^\tau }{2}-\frac{\alpha _3^\tau (1+\xi )}{4}\right) \Big /r_{\xi ,\eta }^{\tau ,2}. \end{aligned}$$

Therefore, on the edge $\overrightarrow{F_{\tau }(-1,\eta )F_\tau (1,\eta )}$,

$$\begin{aligned} \frac{\partial v}{\partial \mathbf{n}}=\frac{\partial v}{\partial \mathbf{n}^1_{\xi ,\eta }}=\frac{1}{r_{\xi ,\eta }^{\tau ,1} J_\tau }\left( -s^\tau _{\xi ,\eta }\frac{\partial \hat{v}_\tau }{\partial \xi }+(r_{\xi ,\eta }^{\tau ,1})^2\frac{\partial \hat{v}_\tau }{\partial \eta }\right) . \end{aligned}$$

(2.8)

And on the edge $\overrightarrow{F_{\tau }(\xi ,-1)F_\tau (\xi ,1)}$,

$$\begin{aligned} \frac{\partial v}{\partial \mathbf{n}}=\frac{\partial v}{\partial \mathbf{n}^2_{\xi ,\eta }}=\frac{1}{r_{\xi ,\eta }^{\tau ,2} J_\tau }\left( (r_{\xi ,\eta }^{\tau ,2})^2\frac{\partial \hat{v}_\tau }{\partial \xi }-s^\tau _{\xi ,\eta }\frac{\partial \hat{v}_\tau }{\partial \eta }\right) . \end{aligned}$$

(2.9)

From the above formulae, we find that even $\hat{v}_\tau$ is a polynomial, the directional derivative $\frac{\partial v}{\partial \mathbf{n}}$ may not be a polynomial since $J_\tau$ is not a constant for an arbitrary quadrilateral.

3 Finite volume schemes of any order

We consider finite volume schemes of any order for the elliptic boundary value problem

$$\begin{aligned} -{\bigtriangledown }\cdot (\alpha {\bigtriangledown }u)&= f \ \mathrm{in}\ \Omega ,\end{aligned}$$

(3.1)

$$\begin{aligned} u&= 0 \ \mathrm{on} \ \Gamma , \end{aligned}$$

(3.2)

where $\Omega \subset \mathbb {R}^2$ is a simply connected polygon, $\Gamma =\partial \Omega$, $\alpha \in L^\infty (\Omega )$ and it is bounded from below: There exists a constant $\alpha _0>0$ such that $\alpha (x)\ge \alpha _0$ for almost all $x\in \Omega$, and $f\in L^2(\Omega )$ is a real-valued function defined on $\Omega$.

We will present our finite volume schemes under the framework of Petrov–Galerkin method. We first choose the trial space as the standard FEM space of any degree $r\ge 1$ defined by

$$\begin{aligned} {\mathcal {U}}^r_h=\{v\in C(\Omega )|\hat{v}_\tau =v\circ F_\tau \in {\mathbb Q}_r(\tau _0),\quad \forall \tau \in {\mathcal {T}}_h, \text {and} \ v|_{\partial \Omega }=0\}, \end{aligned}$$

where ${\mathbb {Q}}_r(\tau _0)$ is the set of all bi-polynomials of degree no more than $r$. By the standard approximation theory, we have

$$\begin{aligned} \dim {\mathcal {U}}_h^r=\#{\mathcal {N}}^\circ , \end{aligned}$$

where ${\mathcal {N}}^\circ ={\mathcal {N}}{\setminus } \partial \Omega$ is the set of all internal Lobatto points.

We next present the dual mesh and the corresponding test space. The dual mesh is constructed as follows. For any segment $E$, we denote $G_{E,j}j\in \mathbb {Z}_r$ the Gauss points on $E$. For a quadrilateral $\tau =\square P_1P_2P_3P_4\in {\mathcal {T}}_h$, the dual mesh in $\tau$ is obtained by connecting $G_{\overline{P_1P_2},j}$ and $G_{\overline{P_4P_3},j}, j\in \mathbb {Z}_r$, $G_{\overline{P_1P_4},j}$ and $G_{\overline{P_2P_3},j}, j\in \mathbb {Z}_r$ with lines, see Fig. 2 for an example $r=2$. Since $F_\tau$ is a bilinear transformation, for a fixed $j\in \mathbb {Z}^0_{r+1}$, all Gauss points $G^\tau _{i,j}, i\in \mathbb {Z}^0_{r+1}$ are located on one same line and for a fixed $i\in \mathbb {Z}^0_{r+1}$, all points $G^\tau _{i,j}, j\in \mathbb {Z}^0_{r+1}$ are on another same line. In other words, we construct a control volume $V_p$ for each Lobatto point $p\in {\mathcal {N}}$. The contribution from a quadrilateral $\tau \ni p$ is

$$\begin{aligned} V_{\tau ,p}= \Box G_{ij}^\tau G_{i+1j}^\tau G_{i+1j+1}^\tau G_{ij+1}^\tau \end{aligned}$$

where $i,j$ is chosen such that $p=L^\tau _{ij}$. Here, the notation of Gauss points has been extended to all $i,j\in \mathbb {Z}^0_{r+1}$ by letting $g_0=-1, g_{r+1}=1$, see Fig. 3 for a simple case where $r=2$. Note that in this simple case, the generalized Gauss points $G_{0,0}^\tau =L_{0,0}^\tau , G_{3,0}^\tau =L_{2,0}^\tau , G_{3,3}^\tau =L_{2,2}^\tau , G_{0,2}^\tau =L_{0,2}^\tau .$

Fig. 3

Control volumes associated with a quadrilateral $\tau$ ($r = 2$)

The whole control volume surrounding $P$ is then defined as

$$\begin{aligned} V_P=\bigcup _{\tau \ni P} V_{\tau ,P}. \end{aligned}$$

For the simple case $r=2$, whole control volumes surrounding Lobatto points in a quadrilateral are plotted in Fig. 3. In this figure, each control volume is a polygon surrounded by dash lines. The dual mesh ${\mathcal {T}}'_h$ consists of all control volumes $V_p,p\in {\mathcal {N}}$. That is,

$$\begin{aligned} {\mathcal {T}}'_h=\{V_p|p\in {\mathcal {N}}\}. \end{aligned}$$

The corresponding test space is defined as

$$\begin{aligned} {\mathcal {V}}_h=\text {Span}\{\psi _{V_p}|p\in {\mathcal {N}}^\circ \}, \end{aligned}$$

where $\psi _{A}$ is the characteristic function of some set $A\subset \Omega$. Obviously, we have

$$\begin{aligned} \dim {\mathcal {V}}_h= \#{\mathcal {N}}_0=\dim {\mathcal {U}}_h^r. \end{aligned}$$

We are now ready to present our finite volume schemes. The finite volume solution of (3.1) and (3.2) is a function $u_h\in {\mathcal {U}}^r_h$ which satisfies conservation laws

$$\begin{aligned} -\int _{\partial V_p} \alpha \frac{\partial u_h}{\partial \mathbf{n}}ds =\int _{V_p}fdxdy \end{aligned}$$

(3.3)

on each control volume $V_p, p\in {\mathcal {N}}^\circ$, where $\mathbf{n}$ is the unit outward normal on the boundary curve $\partial V_p$. Let $w_h\in {\mathcal {V}}_h$, $w_h$ can be written as

$$\begin{aligned} w_h=\sum _{p\in {\mathcal {N}}^\circ }w_p\psi _{V_p} \end{aligned}$$

where the coefficients $w_p,p\in {\mathcal {N}}^\circ$ are constants, $\psi _S$ is the characteristic function of the subset $S\subset \Omega$. Multiplying (3.3) with $w_{p}$ and then summing up for all $p\in {\mathcal {N}}^\circ$, we obtain

$$\begin{aligned} -\sum _{p\in {\mathcal {N}}^\circ } w_{p}\int _{\partial V_p}\alpha \frac{\partial u_h}{\partial \mathbf{n}}ds=\int _\Omega f w_hdxdy. \end{aligned}$$

Defining the FVM bilinear form for all $v\in H^1_0(\Omega ), w_h\in {\mathcal {V}}_h$ as

$$\begin{aligned} a_h(v,w_{\mathcal {P}'})= -\sum _{p\in {\mathcal {N}}^\circ } w_p\int _{\partial V_p}\alpha \frac{\partial v}{\partial \mathbf{n}}ds, \end{aligned}$$

(3.4)

the finite volume method for solving Eqs. (3.1) and (3.2) reads as: Find $u_h\in {\mathcal {U}}^r_h$ such that

$$\begin{aligned} a_h(u_h,w_h)=(f,w_h),\quad \forall w_h\in {\mathcal {V}}_h. \end{aligned}$$

(3.5)

We next study of the continuity of the bilinear form $a_h(\cdot ,\cdot )$ defined in (3.4). We denote by ${\mathcal {E}}_h'$ the set of interior edges of the dual partition ${\mathcal {T}}_h'$. Moreover, we define a semi-norm in the test space ${\mathcal {V}}_h$ for all $w_h\in {\mathcal {V}}_h$ by

$$\begin{aligned} |w_h|_h'=\left( \sum _{E\in {\mathcal {E}}_h'} h_E^{-1}\int _E \left[ w_h\right] ^2ds\right) ^{1\over 2}, \end{aligned}$$

where $h_E$ is the diameter of an edge $E$, and a semi-norm in the so-called broken $H^2$ space

$$\begin{aligned} H_h^{2}(\Omega )=\{v\in C(\Omega ): v|_{\tau }\in H^2,\quad \forall \tau \in {\mathcal {T}}_h\} \end{aligned}$$

for all $v\in H^2_h(\Omega )$ by

$$\begin{aligned} |v|_h= \left( \sum _{\tau \in {\mathcal {T}}_h}|v|_{1,\tau }^2+h_\tau ^2|v|_{2,\tau }^2\right) ^{\frac{1}{2}}, \end{aligned}$$

where $h_\tau$ is the diameter of $\tau$. The mesh dependent semi-norm $|\cdot |_{h}$ has also been used in [28].

The bilinear form $a_h(\cdot ,\cdot )$ can be rewritten for all $v\in \ H_0^1(\Omega ),\ w_{h}\in \ {\mathcal {V}}_{h}$ as

$$\begin{aligned} a_h(v,w_h)= \sum _{E\in {\mathcal {E}}_h'}[w_h]_E\int _E \alpha \frac{\partial v}{\partial \mathbf{n}}ds, \end{aligned}$$

(3.6)

where $[w_h]_E=w_h|_{V_2}-w_h|_{V_1}$ denotes the jump of the $w_h$ across the common edge $E=V_1\cap V_2$ of two volumes $V_1, V_2 \in {\mathcal {T}}'_h$ and $\mathbf{n}$ denotes the normal vector on $E$ pointing from $V_1$ to $V_2$.

Theorem 3.1

The finite volume bilinear form $a_h(\cdot ,\cdot )$ is variationally exact:

$$\begin{aligned} a_h(u,w_h)=(f,w_h)\quad \forall \ w_h\in \ {\mathcal {V}}_h \end{aligned}$$

(3.7)

and continuous: for all $v\in \ H_0^1(\Omega )\cap H_h^{2}(\Omega ),\ w_h\in \ {\mathcal {V}}_h$,

$$\begin{aligned} |a_h(v,w_h)|\lesssim |v|_h |w_h|'_h, \end{aligned}$$

(3.8)

where the hidden constant is independent of $h$.

Furthermore, let $u$ be the solution of (3.1) and (3.2), $u_h$ the solution of (3.5). If there holds the following inf–sup condition

$$\begin{aligned} \inf _{v_h\in {\mathcal {U}}_{h}^r}\sup _{w_h \in {\mathcal {V}}_h' } \frac{a_h (v_h ,w_h)}{|v_h |_{h} |w_{h}|'_{h}}\gtrsim 1, \end{aligned}$$

(3.9)

then

$$\begin{aligned} |u-u_h|_{h}\lesssim \inf _{v_h\in {\mathcal {U}}^r_{h}}|u-v_h|_{h}. \end{aligned}$$

(3.10)

Consequently, if $u\in H^{r+1}(\Omega )$,

$$\begin{aligned} |u-u_h|_{1}\lesssim h^r|u|_{r+1}. \end{aligned}$$

(3.11)

Proof

First, (3.7) follows by multiplying (3.1) with an arbitrary function $w_h\in {\mathcal {V}}_h$ and then using Green’s formula in each control volume $\tau \in {\mathcal {T}}_h'$.

Secondly we prove (3.8). By the Cauchy–Schwartz inequality, for all $v\in \ H_0^1(\Omega )$ and all $w_h\in {\mathcal {V}}_h$, there holds

$$\begin{aligned} a_h(v,w_h) \le \Vert \alpha \Vert _\infty |w_h|'_h \left( \sum _{E\in {\mathcal {E}}_h'} h_E\int _E \left( \frac{\partial v}{\partial \mathbf{n}}\right) ^2ds\right) ^{\frac{1}{2}}. \end{aligned}$$

By the trace inequality and the shape regularity of ${\mathcal {T}}_h,$

$$\begin{aligned} \left( h_E\int _{E\cap \tau } \left( \frac{\partial v}{\partial \mathbf{n}}\right) ^2ds\right) ^{\frac{1}{2}}\lesssim |v|_{1,\tau }+ h_\tau |v|_{2,\tau } \end{aligned}$$

where $\tau \in {\mathcal {T}}_h$ and $\tau \cap E\not =\emptyset$. Since for any given $E\in {\mathcal {E}}_h'$, there are at most two elements $\tau \in {\mathcal {T}}_h$ such that $\tau \cap E\not =\emptyset$, we have

$$\begin{aligned} a_{\mathcal {P}}(v,w_h)&\lesssim |w_h|'_h \left( \sum _{E\in {\mathcal {E}}_h}\sum _{\tau \in {\mathcal {T}}_h,\tau \cap E\not =\emptyset } |v|^2_{1,\tau }+ h_\tau ^2|v|^2_{2,\tau }\right) ^{\frac{1}{2}}\\&\lesssim |w_h|'_h \left( \sum _{\tau \in {\mathcal {T}}_h} |v|^2_{1,\tau }+ h_\tau ^2|v|^2_{2,\tau }\right) ^{\frac{1}{2}}. \end{aligned}$$

Then there exists a positive $M$ which depends only on $\alpha$ and $r$ such that (3.8) holds.

We next show (3.10). By (3.7) and the inf–sup condition (3.9), for all $v_h\in {\mathcal {U}}^r_h$, there holds

$$\begin{aligned} |u_h-v_h|_h\lesssim \sup _{w_h\in {\mathcal {V}}_h'}\frac{a_h(u_h-v_h,w_h)}{|w_h|'_h} = \sup _{w_h\in {\mathcal {V}}_h'}\frac{a_h(u-v_h,w_h)}{|w_h|'_h}. \end{aligned}$$

Then by the triangle inequality and the continuity (3.8), we have

$$\begin{aligned} |u-u_h|_{h}\le |u-v_h|_h+|v_h-u_h|_h \lesssim |u-v_h|_h. \end{aligned}$$

That is, (3.10) holds.

We conclude from the definition of $|\cdot |_h$ and (3.10) that

$$\begin{aligned} |u-u_h|_1\le |u-u_h|_h\lesssim \inf \limits _{v_h\in {\mathcal {U}}^r_h}|u-v_h|_{h}. \end{aligned}$$

Note that

$$\begin{aligned} \inf \limits _{v_h\in {\mathcal {U}}^r_h}|u-v_h|_h\le |u-u_I|_{1}+h|u-u_I|_{2}, \end{aligned}$$

where $u_I\in {\mathcal {U}}^r_h$ is the interpolation of $u$ which will be introduced precisely in next subsection. By the standard approximation theory, we obtain the estimate (3.11). $\square$

Remark 3.2

We observe from the above theorem that the inf–sup condition (3.9) plays a critical role in the proof of the optimal convergence rates of the FV solutions. The proof of (3.9) is the task of next section.

4 Inf–sup property

This section is devoted to a rigorous proof for (3.9) which is the core of the paper. Since by the inverse inequality, we have the norm equivalence

$$\begin{aligned} |v_h|_h\sim |v_h|_1, \quad \forall v_h\in {\mathcal {U}}_h^r, \end{aligned}$$

the inf–sup property (3.9) is equivalent to

$$\begin{aligned} \inf _{v_h\in {\mathcal {U}}_{h}^r}\sup _{w_h \in {\mathcal {V}}_h' } \frac{a_h (v_h ,w_h)}{|v_h |_1 |w_{h}|'_{h}}\gtrsim 1. \end{aligned}$$

(4.1)

We begin with a simple observation that we only need to prove (4.1) for the case that $\alpha$ is piecewise constant with respect to the partition ${\mathcal {T}}_h$. In fact, for a piecewise continuous coefficient $\alpha$, let

$$\begin{aligned} \bar{\alpha }(x,y)=\frac{1}{|\tau |}\int _\tau \alpha (x,y)dxdy, \quad \forall (x,y)\in \tau \in {\mathcal {T}}_h \end{aligned}$$

and denote its piecewise modulus of continuity by

$$\begin{aligned} m_{\mathcal {T}_h}(\alpha ,h)=\sup \{|\alpha (\mathbf{x}_1)-\alpha (\mathbf{x}_2)|:|\mathbf{x}_1-\mathbf{x}_2|\le h,\quad \forall \ \mathbf{x}_1, \mathbf{x}_2\in \tau , \forall \ \tau \in {\mathcal {T}}_h\}. \end{aligned}$$

The fact that $\alpha$ is piecewise continuous implies that $m_{\mathcal {T}_h}(\alpha ,h)$ converges to 0 when $h$ goes to 0. We define a new bilinear form $\bar{a}_h(\cdot ,\cdot )$ for all $v_h\in {\mathcal {U}}_h^r, w_h\in {\mathcal {V}}_h$ by

$$\begin{aligned} \bar{a}_{h}(v_h,w_h)&:= \sum _{E\in {\mathcal {E}}'_{h}}[w_h]\int _E \bar{\alpha }\frac{\partial v_h}{\partial \mathbf{n}}ds. \end{aligned}$$

If (4.1) is valid for a piecewise constant coefficient, then for all $v_h\in {\mathcal {U}}_h^r$,

$$\begin{aligned} \sup _{w_h\in {\mathcal {V}}_h} \frac{\bar{a}_{h}(v_h,w_h)}{|w_h|_h'} \gtrsim |v_h|_1 . \end{aligned}$$

On the other hand, by the same arguments in Theorem 3.1, we have

$$\begin{aligned} |a_{h}(v_h, w_h)-\bar{a}_{h}(v_h,w_h)|\lesssim m_{\mathcal {T}_h}(\alpha ,h)|v_h|_1|w_h|_h', \end{aligned}$$

Then when $h$ is sufficiently small,

$$\begin{aligned} \sup _{w_h\in {\mathcal {V}}_h} \frac{a_{h}(v_h,w_h)}{|w_h|_h'}\gtrsim (1-m_{\mathcal {T}_h}(\alpha ,h))|v_h|_{1}\ge \frac{1}{2}|v_h|_{1} \end{aligned}$$

which implies the inf–sup condition (4.1) for arbitrary piecewise continuous $\alpha$.

In the rest analysis of this section, unless specifically mentioned, we always suppose that $\alpha$ is piecewise constant respect to ${\mathcal {T}}_h$.

4.1 An equivalent discrete form

In this subsection, we transfer the FV bilinear form (3.6) to a summation of function values at Gauss points.

To this end, we first describe the dual edges in a quadrilateral $\tau \in {\mathcal {T}}_h$. Let

$$\begin{aligned} E^\xi _{ij}=\overline{G^\tau _{i,j}G^\tau _{i+1,j}}, \quad \forall (i,j)\in \mathbb {Z}^0_r\times \mathbb {Z}_r, \end{aligned}$$

be the edges along $\xi -$direction and

$$\begin{aligned} E_{ij}^\eta =\overline{G^\tau _{i,j}G^\tau _{i, j+1}}, \quad \forall (i,j)\in \mathbb {Z}_r\times \mathbb {Z}^0_r, \end{aligned}$$

the edges along $\eta$-direction in $\tau$. The set of dual edges in $\tau$ is the union of edges along two directions, that is:

$$\begin{aligned} {\mathcal {E}}_h'\cap \tau = \{E^\eta _{ij}: i\in \mathbb {Z}_r, j\in \mathbb {Z}_r^0\}\cup \{E_{ij}^\xi , i\in \mathbb {Z}^0_{r}, j\in \mathbb {Z}_r\}. \end{aligned}$$

Secondly, we define the jumps of a test function $w_h\in {\mathcal {V}}_h$. Note that a function $w_h\in {\mathcal {V}}_h$ can be represented as $w_h=\sum _{p\in {\mathcal {N}}^\circ } (w_h)_p\psi _{V_p}$, where $(w_h)_p\in \mathbb {R}$ is a constant. Letting $(w_h)_p=0$ for all $p\in {\mathcal {N}}\cap \partial \Omega$, we write $w_h=\sum _{p\in {\mathcal {N}}} (w_h)_p\psi _{V_p}$. For all $\tau \in {\mathcal {T}}_h$ and all $i,j\in \mathbb {Z}^0_r$, the contribution from $\tau$ to the control volume $V_{L_{i,j}^\tau }$ is $F_\tau ([g_i, g_{i+1}]\times [g_j,g_{j+1})]$. Therefore in the quadrilateral $\tau$,

$$\begin{aligned} w_h=\sum _{(i,j)\in \mathbb {Z}_r^0\times \mathbb {Z}_r^0}w^\tau _{ij}\psi _{F_\tau ([g_i, g_{i+1}]\times [g_j,g_{j+1})]}, \end{aligned}$$

where $w^\tau _{i,j}=(w_h)_{L^\tau _{i,j}}.$ For all $(i,j)\in \mathbb {Z}^0_r\times \mathbb {Z}_r$, we denote the jump of $w_h$ on the edge $E_{ij}^\xi$ by

$$\begin{aligned}{}[w_h]^\tau _{\xi ,ij}=w_{ij}^\tau -w_{ij-1}^\tau , \end{aligned}$$

and for all $(i,j)\in \mathbb {Z}_r\times \mathbb {Z}_r^0$, we denote the jump on the edge $E_{ij}^\eta$ by

$$\begin{aligned}{}[w_h]^\tau _{\eta ,ij}=w_{ij}^\tau -w_{i-1j}^\tau . \end{aligned}$$

For all $(i,j)\in \mathbb {Z}_r\times \mathbb {Z}_r$, we define the (double) jump of $w_h$ at Gauss point $G^\tau _{i,j}$ as

$$\begin{aligned} \lfloor w_h \rfloor ^\tau _{i,j}=w^\tau _{i,j}+w^\tau _{i-1,j-1}-w^\tau _{i-1,j}-w^\tau _{i,j-1}. \end{aligned}$$

Obviously, we have

$$\begin{aligned} \lfloor w_h \rfloor ^{\tau }_{i,j}=[w_h]^\tau _{\xi ,ij}-[w_h]^\tau _{\xi ,i-1j}=[w_h]^\tau _{\eta ,ij}-[w_h]^\tau _{\eta ,ij-1}. \end{aligned}$$

With these notations, for all $v\in \ H_0^1(\Omega ),\ w_{h}\in \ {\mathcal {V}}_{h}'$, we have

$$\begin{aligned} a_h(v,w_h)= \sum _{\tau \in {\mathcal {T}}_h} a_{h,\tau }(v,w_h) \end{aligned}$$

where the element-wise bilinear form

$$\begin{aligned} a_{h,\tau }(v, w_h)&= \sum _{E\in \tau \cap {\mathcal {E}}_h'}[w_h]\int _E \alpha \frac{\partial v}{\partial \mathbf{n}}ds, \quad \\&= \sum _{(i,j)\in \mathbb {Z}_r^0\times \mathbb {Z}_r} [w_h]^\tau _{\xi ,ij}\int _{E^\xi _{ij}} \alpha \frac{\partial v}{\partial \mathbf{n}}ds +\sum _{(i,j)\in \mathbb {Z}_r\times \mathbb {Z}_r^0} [w_h]^\tau _{\eta ,ij}\int _{E^\eta _{ij}} \alpha \frac{\partial v}{\partial \mathbf{n}}ds. \end{aligned}$$

To transform the above formulae to a summation of function values at Gauss points, we next introduce a primal function of the function $\alpha \frac{\partial v}{\partial \mathbf{n}}$ along a path which is defined as below. For a boundary edge $E\in {\mathcal {E}}_h^{b1}$, let $E_i, i=1,\ldots , m, m\ge 2$ be the sequence of edges in ${\mathcal {E}}_h$ satisfying: (1) $E_1=E\in {\mathcal {E}}_h^{b1}, E_m=F\in {\mathcal {E}}_h^{b2}$, (2) The edges $E_i, E_{i+1}$ belong to the same quadrilateral $\tau _i$ and $E_{i+1}=op(E_i),i=1,\ldots , m-1$. Given some point $P\in E$, let $Q_i\in E_i, i=1,\ldots ,m$ be a sequence of points such that: (1) $Q_1=P\in E=E_1$, (2) Let the four vertices of $\tau _i$ be labeled as $P^i_j, j=1,\ldots ,4$. If $E_i=P^i_1P^i_2$, then $Q_i=F_{\tau _i}(\xi ,-1)$ and $P_{i+1}=F_{\tau _i}(\xi ,1)$ for some $-1<\xi <1$; If $E_i=P^i_1P^i_4$, then $Q_i=F_{\tau _i}(-1,\eta )$ and $Q_{i+1}=F_{\tau _i}(1,\eta )$ for some $-1<\eta <1$,. We connect $Q_iQ_{i+1}, i=1,\ldots m-1$ with segments, then we obtain the pass starting from the point $P\in E=E_1$ and ending at the point $Q=Q_m\in E_m=F\in {\mathcal {E}}_h^{b2}$. We denote this pass by $S_{E,P}$, see Fig. 4 for a path (depicted by dash line) which starts from $P\in E_4$ and ends at a point $Q$ in the opposite boundary edge $F_4$.

Fig. 4

A path starts from $P\in E_4$ and ends at $Q\in F_4$. The segment $\overline{Q_iQ_{i+1}}$ is the portion of this pass in the element $\tau _i=\square P_1^iP_2^iP_3^iP_4^i$. The two points can be expressed as $Q_{i}=F_{\tau _i}(\xi ,-1), Q_{i+1}=F_{\tau _i}(\xi ,1)$

For all $E\in {\mathcal {E}}_h^{b1}, P\in E$ and for any point $Q\in S_{E,P}$, we define

$$\begin{aligned} V_{E,P}(Q)= \int _{~\widehat{PQ}} \alpha \frac{\partial v}{\partial \mathbf{n}} ds, \end{aligned}$$

(4.2)

where the curve $\widehat{PQ}\subset S_{E,P}$ is a portion of the path $S_{E,P}$ which starts from $P$ and ends at the point $\tilde{P}$ which belongs to the opposite boundary edge $F\in {\mathcal {E}}_h^{b2}$.

For $\tau =\square P_1P_2P_3P_4\in \in {\mathcal {T}}_h$, let $E^\tau _1,E^\tau _2\in {\mathcal {E}}_h^{b1}$ be two boundary edges such that $P_1P_2=op(E^\tau _1),P_1P_4=op(E^\tau _2)$. We notice that for a fixed $j\in \mathbb {Z}_r$, all the Gauss points $G^\tau _{i,j}, i\in \mathbb {Z}^0_{r+1}$ are situated on the same pass derived from some point $Q^1_j\in E^\tau _1$. Similarly, for a fixed $i\in \mathbb {Z}_r$, all the Gauss points $G^\tau _{i,j}, j\in \mathbb {Z}^0_{r+1}$ are situated on the same pass derived from some point $Q^2_i\in E^\tau _2$. Therefore, for all $j\in \mathbb {Z}_r, i\in \mathbb {Z}_r^0$,

$$\begin{aligned} \int _{E^\xi _{ij}} \alpha \frac{\partial v}{\partial \mathbf{n}}=V_{E_1^\tau , Q^1_j}(G^\tau _{i+1,j})-V_{E_1^\tau , Q^1_j}(G^\tau _{i,j}); \end{aligned}$$

and for all $i\in \mathbb {Z}_r, j\in \mathbb {Z}_r^0$,

$$\begin{aligned} \int _{E^\eta _{ij}} \alpha \frac{\partial v}{\partial \mathbf{n}}=V_{E_2^\tau , Q^2_i}(G^\tau _{i,j+1})-V_{E_2^\tau , Q^2_i}(G^\tau _{i,j}). \end{aligned}$$

Then, for all $v\in \ H_0^1(\Omega ),\ w_{h}\in \ {\mathcal {V}}_{h}'$,

$$\begin{aligned} a_{h,\tau }(v,w_h)&= \sum _{(i,j)\in \mathbb {Z}_r^0\times \mathbb {Z}_r} [w_h]^\tau _{\xi ,ij}(V_{E_1^\tau , Q^1_j}(G^\tau _{i+1,j})-V_{E_1^\tau , Q^1_j}(G^\tau _{i,j}))\\&+\sum _{(i,j)\in \mathbb {Z}_r\times \mathbb {Z}_r^0} [w_h]^\tau _{\eta ,ij}(V_{E_2^\tau , Q^2_i}(G^\tau _{i,j+1})-V_{E_2^\tau , Q^2_i}(G^\tau _{i,j}))\\&= a_\tau (v,w_h)+b_\tau (v,w_h), \end{aligned}$$

where the element-wise bilinear form

$$\begin{aligned} a_\tau (v,w_h)=-\sum _{(i,j)\in \mathbb {Z}_r\times \mathbb {Z}_r}\lfloor w_h\rfloor ^\tau _{i,j}(V_{E^\tau _1,Q^1_j}(G^\tau _{i,j})+V_{E_2^\tau ,Q^2_i}(G^\tau _{i,j})), \end{aligned}$$

(4.3)

and the boundary term

$$\begin{aligned} b_\tau (v,w_h)&= \sum _{j\in \mathbb {Z}_r}([w_h]^\tau _{\xi ,rj}V_{E_1^\tau , Q^1_j}(G^\tau _{r+1,j})-[w_h]^\tau _{\xi ,0j}V_{E_1^\tau , Q^1_j}(G^\tau _{0,j}))\\&+\sum _{i\in \mathbb {Z}_r} ([w_h]^\tau _{\eta ,ir}V_{E_2^\tau , Q^2_i}(G^\tau _{i,r+1})-[w_h]^\tau _{\eta ,i0}V_{E_2^\tau , Q^2_i}(G^\tau _{i,0})). \end{aligned}$$

Since the function $V_{E,P}$ is continuous across each internal edge in ${\mathcal {T}}_h$, we have

$$\begin{aligned} \sum _{\tau \in {\mathcal {T}}_h} b_\tau (v,w_h)=0. \end{aligned}$$

Finally, we obtain

$$\begin{aligned} a_h(v,w_h)=\sum _{\tau \in {\mathcal {T}}_h} a_\tau (v,w_h) \end{aligned}$$

with $a_\tau (\cdot ,\cdot )$ defined by (4.3).

4.2 A novel mapping from the trial space to test space

A key step to establish (4.1) is the construction of a novel mapping from the trial space to the test space.

Let $\Pi$ be a mapping which maps $v_h\in {\mathcal {U}}_h^r$ to $w_h\in {\mathcal {V}}_h$ such that the coefficients of $w_h$ satisfy

$$\begin{aligned} \lfloor w_h \rfloor ^\tau _{i,j}=A_i A_j \frac{\partial ^2 \hat{v}_\tau }{\partial \xi \partial \eta }(g_i, g_j), \quad \forall \tau \in {\mathcal {T}}_h, (i,j)\in \mathbb {Z}_r\times \mathbb {Z}_r, \end{aligned}$$

(4.4)

where $\hat{v}_\tau =v_h\circ F_\tau \in {\mathbb {Q}}_r$ for all $\tau \in {\mathcal {T}}_h$, and $A_j, j\in \mathbb {Z}_r$ are the weights of the Gauss quadrature $\sum _{j=1}^r A_j v(g_j)$ for computing the integral $\int _{-1}^1 v(x) dx.$

We next explain that for a given $v_h\in {\mathcal {U}}_h^r$, (4.4) determine a unique $w_h\in {\mathcal {V}}_h$. First if $v_h=0$, then $\forall \tau \in {\mathcal {T}}_h, (i,j)\in \mathbb {Z}_r\times \mathbb {Z}_r$,

$$\begin{aligned} \lfloor w_h \rfloor ^\tau _{i,j}=w^\tau _{i,j}+w^\tau _{i-1,j-1}-w^\tau _{i-1,j}-w^\tau _{i,j-1}=0. \end{aligned}$$

Noticing the fact that $w_h=0$ on $\partial \Omega$, we obtain that $w_h=0$ on the whole domain $\Omega$. The uniqueness of $\Pi$ is proved.

We next explain that there exists a $w_h$ which satisfies all constraints (4.4). Since (4.4) is a linear system with $\#{\mathcal {G}}=\#{\mathcal {T}}_h r^2$ equations, while the degree of freedom of a $w_h$ is $\dim {\mathcal {V}}_h=\#{\mathcal {N}}^\circ =\#{\mathcal {G}}-\frac{1}{2}\#{\mathcal {G}}^b_{h}+1$, one may doubt if the linear system is over-determined. The following lemma explains there exists a lot of redundant equations in (4.4).

Lemma 4.1

Let $v_h\in {\mathcal {U}}_h^r$, then for any $E_i\in {\mathcal {E}}_h^{b1}$ and any $j\in \mathbb {Z}^r$, we have

$$\begin{aligned} \sum _{l=1}^m\sum _{k\in \mathbb {Z}_r} A_k\frac{\partial ^2 \hat{v}_{\tau _l}}{\partial \xi \partial \eta }(g_k, g_j)=0, \end{aligned}$$

(4.5)

where $\tau _l,l=1,\ldots m$ are quadrilaterals which begin at $E_i\in {\mathcal {E}}_h^{b1}$ and end at $F_i=op(E_i)\in {\mathcal {E}}_h^{b2}$. Consequently, for all $E_i\in {\mathcal {E}}_h^{b1}$ and all $j\in \mathbb {Z}^r$ and all $w_h\in {\mathcal {V}}_h$,

$$\begin{aligned} \sum _{l=1}^m\sum _{k\in \mathbb {Z}_r} \lfloor w_h\rfloor ^{\tau _l}_{k,j}= \sum _{l=1}^m\sum _{k\in \mathbb {Z}_r} A_kA_j\frac{\partial ^2 \hat{v}_{\tau _l}}{\partial \xi \partial \eta }(g_k, g_j). \end{aligned}$$

(4.6)

Proof

For fixed $l\in \mathbb {Z}_m, j\in \mathbb {Z}_r$, the function $\frac{\partial ^2 \hat{v}_{\tau _l}}{\partial \xi \partial \eta }(\cdot , g_j)\in {\mathbb {P}}_{r-1}(-1,1)$. Therefore, by the property of a Gauss quadrature

$$\begin{aligned} \sum _{k\in \mathbb {Z}_r} A_k\frac{\partial ^2 \hat{v}_{\tau _l}}{\partial \xi \partial \eta }(g_k, g_j)&= \int _{-1}^1\frac{\partial ^2 \hat{v}_{\tau _l}}{\partial \xi \partial \eta }(\xi , g_j)d\xi =\frac{\partial \hat{v}_{\tau _l}}{\partial \eta }(1, g_j)-\frac{\partial \hat{v}_{\tau _l}}{\partial \eta }(-1, g_j). \end{aligned}$$

Now since $v_h\in C(\Omega )$, we have for all $l=1,\ldots , m-1$,

$$\begin{aligned} \frac{\partial \hat{v}_{\tau _l}}{\partial \eta }(1, g_j)=\frac{\partial \hat{v}_{\tau _{l+1}}}{\partial \eta }(-1, g_j). \end{aligned}$$

Therefore,

$$\begin{aligned} \sum _{l=1}^m\sum _{k\in \mathbb {Z}_r} A_k\frac{\partial ^2 \hat{v}_{\tau _l}}{\partial \xi \partial \eta }(g_k, g_j)=\frac{\partial \hat{v}_{\tau _m}}{\partial \eta }(1, g_j)-\frac{\partial \hat{v}_{\tau _1}}{\partial \eta }(-1, g_j). \end{aligned}$$

Note that $E_i,F_i\subset \partial \Omega$, then $v_h=0$ on $E_i$ and $F_i$. That is $\hat{v}_{\tau _1}(-1,\eta )=0=\hat{v}_{\tau _m}(1,\eta ),\forall \eta \in (-1,1)$. Consequently, (4.5) hold for all $E_i\in {\mathcal {E}}_h^{b1}$ and all $j\in \mathbb {Z}_r$.

We next show (4.6). Since $(w_h)_p=0$ for all $p\in {\mathcal {N}}{\setminus }{\mathcal {N}}^\circ$, we have

$$\begin{aligned} \sum _{l=1}^m\sum _{k\in \mathbb {Z}_r} \lfloor w_h\rfloor ^{\tau _l}_{k,j}=[w_h]^{\tau _m}_{\xi , r,j}-[w_h]^{\tau _1}_{\xi , 0,j}=0, \end{aligned}$$

from which and (4.5), the Eq. (4.6) follows. $\square$

This lemma indicates that equations in (4.4) are linear dependent. Obviously we have $\#{\mathcal {E}}_h^{b1}r=\frac{1}{2}\#{\mathcal {E}}_h^{b}r$ equations in (4.6). Moreover, if we choose $\frac{1}{2}\#{\mathcal {E}}_h^{b}r-1$ equations of (4.6) hold, the rest 1 equation will hold automatically. In other words, we have $\frac{1}{2}\#{\mathcal {E}}_h^{b}r-1$ linear independent equations in (4.6). Now we remove $\frac{1}{2}\#{\mathcal {E}}_h^{b}r-1$ constraints from (4.4), we get a linear system with $\#{\mathcal {N}}^\circ$ unknowns and $\#{\mathcal {N}}^\circ$ equations. Using the fact $v_h=0$ implies $w_h=0$, this linear system has a unique solution. The existence of $w_h=\Pi v_h$ is also proved.

We next show that $\Pi$ is bounded from the trial space to the test space.

Lemma 4.2

If ${\mathcal {T}}_h$ is shape regular, then for any $v_h\in {\mathcal {U}}_h^r$,

$$\begin{aligned} |\Pi v_h|'_h\lesssim |v_h|_1, \end{aligned}$$

(4.7)

where the hidden constant depends only on $r$.

Proof

First, the fact that ${\mathcal {T}}_h$ is a shape regular mesh yields that

$$\begin{aligned} |v_h|_{1,\tau }\sim |\hat{v}_\tau |_{1,\tau _0},\quad \forall \tau \in {\mathcal {T}}_h. \end{aligned}$$

Consequently,

$$\begin{aligned} |v_h|_1^2=\sum _{\tau \in {\mathcal {T}}_h}|v_h|_{1,\tau }^2\sim \sum _{\tau \in {\mathcal {T}}_h}|\hat{v}_\tau |_{1,\tau _0}^2. \end{aligned}$$

On the other hand, by the definition of the semi-norm $|\cdot |'_{h}$,

$$\begin{aligned} (|\Pi v_h|'_h)^2=\sum _{E\in {\mathcal {E}}_h'} ([\Pi v_h]_E)^2=\sum _{\tau \in {\mathcal {T}}_h}\sum _{E\in {\mathcal {E}}_h'\cap \tau } ([\Pi v_h]_E)^2. \end{aligned}$$

Therefore, to show (4.7), we only need to show that for all $\tau \in {\mathcal {T}}_h$,

$$\begin{aligned} \sum _{E\in {\mathcal {E}}_h'\cap \tau } ([\Pi v_h]_E)^2\lesssim |\hat{v}_\tau |_{1,\tau _0}^2. \end{aligned}$$

(4.8)

Noticing $\frac{\partial ^2\hat{v}_\tau }{\partial \xi \partial \eta }\in Q_{r-1}(\tau _0)$, we have

$$\begin{aligned} \sum _{i\in \mathbb {Z}_r} \lfloor \Pi v_h\rfloor ^{\tau }_{ij}&= A_j\sum _{i\in \mathbb {Z}_r} A_i \frac{\partial ^2 \hat{v}_{\tau }}{\partial \xi \partial \eta }(g_i, g_j)=A_j\int _{-1}^1\frac{\partial ^2 \hat{v}_{\tau }}{\partial \xi \partial \eta }(\xi , g_j)d\xi \\&= A_j\frac{\partial \hat{v}_{\tau }}{\partial \eta }(1, g_j)-A_j\frac{\partial \hat{v}_{\tau }}{\partial \eta }(-1, g_j). \end{aligned}$$

Then, by the fact that $\lfloor \Pi v_h \rfloor ^{\tau }_{i,j}=[\Pi v_h]^\tau _{\xi ,i,j}-[\Pi v_h]^\tau _{\xi ,i-1,j}$, we have

$$\begin{aligned}{}[\Pi v_h]^{\tau }_{\xi ,r,j}-[\Pi v_h]^{\tau }_{\xi ,0,j}=A_j\frac{\partial \hat{v}_{\tau }}{\partial \eta }(1, g_j)-A_j\frac{\partial \hat{v}_{\tau }}{\partial \eta }(-1, g_j). \end{aligned}$$

Since $v_h=0$ and $w_h=0$ on $\partial \Omega$, for all $\tau \in {\mathcal {T}}_h, j\in \mathbb {Z}_r$, we have

$$\begin{aligned}{}[\Pi v_h]^{\tau }_{\xi ,0,j}=A_j\frac{\partial \hat{v}_{\tau }}{\partial \eta }(-1, g_j). \end{aligned}$$

Therefore, by the inverse inequality,

$$\begin{aligned} |[\Pi v_h]^{\tau }_{\xi ,0,j}|\le A_j\left\| \frac{\partial \hat{v}_{\tau }}{\partial \eta }(\cdot , g_j)\right\| _{L^\infty (-1,1)}\lesssim A_j\left\| \frac{\partial \hat{v}_{\tau }}{\partial \eta }(\cdot , g_j)\right\| _{L^2(-1,1)}. \end{aligned}$$

Since for $i\in \mathbb {Z}_r$,

$$\begin{aligned}{}[\Pi v_h]^{\tau }_{\xi ,i,j}&= [\Pi v_h]^{\tau }_{\xi ,0,j}+\sum _{i'=1}^i\lfloor \Pi v_h\rfloor ^{\tau }_{i',j}\\&= [\Pi v_h]^{\tau }_{\xi ,0,j}+A_j\sum _{i'=1}^{i} A_{i'} \frac{\partial ^2 \hat{v}_{\tau }}{\partial \xi \partial \eta }(g_i, g_j), \end{aligned}$$

and by the inverse inequality,

$$\begin{aligned} \left| \sum _{i'=1}^{i} A_{i'} \frac{\partial ^2 \hat{v}_{\tau }}{\partial \xi \partial \eta }(g_{i'}, g_j)\right|&\lesssim \left\| \frac{\partial ^2 \hat{v}_{\tau }}{\partial \xi \partial \eta }(\cdot , g_j)\right\| _{L^\infty (-1,1)}\\&\lesssim \left\| \frac{\partial ^2 \hat{v}_{\tau }}{\partial \xi \partial \eta }(\cdot , g_j)\right\| _{L^2(-1,1)}\\&\lesssim \left\| \frac{\partial \hat{v}_{\tau }}{\partial \eta }(\cdot , g_j)\right\| _{L^2(-1,1)}, \end{aligned}$$

for all $i\in \mathbb {Z}^0_r$, there holds

$$\begin{aligned} |[\Pi v_h]^{\tau }_{\xi ,i,j}|\lesssim A_j \left\| \frac{\partial \hat{v}_{\tau }}{\partial \eta }(\cdot , g_j)\right\| _{L^2(-1,1)}. \end{aligned}$$

(4.9)

Since $\int _{-1}^1(\frac{\partial \hat{v}_{\tau }}{\partial \eta }(\xi , \cdot ))^2d\xi$ is a polynomial (w.r.t $\eta$) of degree less than $2r-1$, we have

$$\begin{aligned} \sum _{j\in \mathbb {Z}_r}A_j \int _{-1}^1 \left( \frac{\partial \hat{v}_{\tau }}{\partial \eta }(\xi , g_j)\right) ^2d\xi = \int _{-1}^1\int _{-1}^1 \left( \frac{\partial \hat{v}_{\tau }}{\partial \eta }(\xi , \eta )\right) ^2d\xi d\eta =\left\| \frac{\partial \hat{v}_{\tau }}{\partial \eta }\right\| _{L^2(\tau _0)}^2. \end{aligned}$$

Noticing (4.9), we obtain

$$\begin{aligned} \sum _{i\in \mathbb {Z}_r^0, j\in \mathbb {Z}_r}([\Pi v_h]^{\tau }_{\xi ,i,j})^2\lesssim \left\| \frac{\partial \hat{v}_{\tau }}{\partial \eta }\right\| _{L^2(\tau _0)}^2. \end{aligned}$$

Similarly,

$$\begin{aligned} \sum _{i\in \mathbb {Z}_r, j\in \mathbb {Z}^0_r}([\Pi v_h]^{\tau }_{\eta ,i,j})^2\lesssim \left\| \frac{\partial \hat{v}_{\tau }}{\partial \xi }\right\| _{L^2(\tau _0)}^2. \end{aligned}$$

Consequently,

$$\begin{aligned} \sum _{E\in {\mathcal {E}}_h'\cap \tau } ([\Pi v_h]_E)^2 =\sum _{i\in \mathbb {Z}_r^0, j\in \mathbb {Z}_r}([\Pi v_h]^{\tau }_{\xi ,i,j})^2+\sum _{i\in \mathbb {Z}_r, j\in \mathbb {Z}^0_r}([\Pi v_h]^{\tau }_{\eta ,i,j})^2\lesssim |\hat{v}_{\tau }|^2_{1,\tau _0}. \end{aligned}$$

That is, (4.8) is verified. The inequality (4.7) then follows. $\square$

4.3 Coercivity of bilinear form $a_h(\cdot ,\Pi \cdot )$

With the help of $\Pi$, we obtain a bilinear form $a_h(\cdot ,\Pi \cdot )$ which is defined only on the trial space ${\mathcal {U}}_h^r$. In this subsection, we show the coercivity of $a_h(\cdot ,\Pi \cdot )$.

By (4.3), for all $v\in {\mathcal {U}}_h^r$,

$$\begin{aligned} a_{\tau }(v,\Pi v) =I_1+I_2. \end{aligned}$$

where

$$\begin{aligned} I_1=-\sum _{(i,j)\in \mathbb {Z}_r\times \mathbb {Z}_r} A_i A_j \frac{\partial ^2 \hat{v}_\tau }{\partial \xi \partial \eta }(g_i, g_j)V_{E^\tau _1,Q^1_j}(G^\tau _{i,j}), \end{aligned}$$

and

$$\begin{aligned} I_2=-\sum _{(i,j)\in \mathbb {Z}_r\times \mathbb {Z}_r} A_i A_j \frac{\partial ^2 \hat{v}_\tau }{\partial \xi \partial \eta }(g_i, g_j)V_{E_2^\tau ,Q^2_i}(G^\tau _{i,j}). \end{aligned}$$

We will only estimate the lower bound of $I_1$ since the lower bound of $I_2$ can be obtained by dual reasoning.

For all $j\in \mathbb {Z}^r$, we denote

$$\begin{aligned} \Theta _j(\xi )=\frac{\partial ^2 \hat{v}_\tau }{\partial \xi \partial \eta }(\cdot , g_j)V_{E^\tau _1,Q^1_j}(F_\tau (\cdot ,g_j)), \xi \in [-1,1], \end{aligned}$$

and let

$$\begin{aligned} Err^\tau _{\xi ,j}=\int _{-1}^{1}\Theta _j(\xi )d\xi -\sum _{i\in \mathbb {Z}_r} A_i \Theta _j(g_i) \end{aligned}$$

be the error of the Gauss quadrature.

Lemma 4.3

If $\tau \in {\mathcal {T}}_h$ is an $h^{1+\gamma }$-parallelogram, then for sufficiently small $h$,

$$\begin{aligned} Err^\tau _{\xi ,j}\gtrsim -h_\tau ^{\gamma }|\hat{v}_\tau |^2_{1,\tau _0},\quad \forall j\in \mathbb {Z}_r, \end{aligned}$$

(4.10)

where the hidden constant is independent of $h$.

Proof

By [10, p98, (2.7.12)], for all $i\in \mathbb {Z}_N$

$$\begin{aligned} Err^\tau _{\xi ,j}=\frac{2^{2r+1}(r!)^4}{(2r+1)[(2r)!]^3}(\Theta _j)^{(2r)}(\xi '), \end{aligned}$$

where $\xi '\in (-1,1)$.

We next calculate and estimate $(\Theta _j)^{(2r)}$. By the Definition (4.2) and the formula (2.8), we have that for all $\xi _0\in (-1,1)$ and all $j\in \mathbb {Z}_r$,

$$\begin{aligned} V_{E^\tau _1,Q^1_j}(F_\tau (\xi _0,g_j))\!=\!V_{E^\tau _1,Q^1_j}(F_\tau (-1,g_j))\!+\!\int _{-1}^{\xi _0} \frac{\alpha }{J_\tau }\left( \!-\!s^\tau _{\xi ,g_j}\frac{\partial \hat{v}_\tau }{\partial \xi }+(r_{\xi ,g_j}^{\tau ,1})^2\frac{\partial \hat{v}_\tau }{\partial \eta }\right) d\xi , \end{aligned}$$

and consequently,

$$\begin{aligned} \frac{d}{d\xi }V_{E^\tau _1,Q^1_j}(F_\tau (\xi ,g_j))=\frac{\alpha }{J_\tau }\left( -s^\tau _{\xi ,g_j}\frac{\partial \hat{v}_\tau }{\partial \xi }+(r_{\xi ,g_j}^{\tau ,1})^2\frac{\partial \hat{v}_\tau }{\partial \eta }\right) . \end{aligned}$$

Then by the Leibnitz formula and noticing that the function $\frac{\partial ^2 \hat{v}_\tau }{\partial \xi \partial \eta }(\cdot , g_j)$ is a polynomial of degree $r-1$, we have

$$\begin{aligned} \Theta _j^{(2r)}(\xi ') ={\mathcal {J}}_1+{\mathcal {J}}_2+{\mathcal {J}}_3. \end{aligned}$$

where

$$\begin{aligned} {\mathcal {J}}_1&= \alpha \left( {\begin{array}{c}2r\\ r-1\end{array}}\right) \frac{(r^{\tau ,1}_{\xi ,j})^2}{J_\tau }\left( \frac{\partial ^{r+1}\hat{v}_\tau }{\partial \xi ^r\partial \eta }(\xi ',g_j)\right) ^2,\\ {\mathcal {J}}_2&= -\alpha \left( {\begin{array}{c}2r\\ r-1\end{array}}\right) \frac{(s_{\xi ,j}^\tau )'}{J_\tau }\frac{\partial ^r \hat{v}_\tau }{\partial \xi ^r}(\xi ',g_j)\frac{\partial ^{r+1}\hat{v}_\tau }{\partial \xi ^r\partial \eta }(\xi ',g_j),\\ {\mathcal {J}}_3&= \alpha \left( {\begin{array}{c}2r\\ r-1\end{array}}\right) \frac{\partial ^{r+1}\hat{v}_\tau }{\partial \xi ^r\partial \eta }(\xi ',g_j)\sum _{l=1}^{r}\left( \frac{1}{J_\tau }\right) ^{(l)}\left( -s^\tau _{\xi ,g_j}\frac{\partial \hat{v}_\tau }{\partial \xi }+(r_{\xi ,g_j}^{\tau ,1})^2\frac{\partial \hat{v}_\tau }{\partial \eta }\right) ^{(r-l)}(\xi ')\\&+\sum _{k=0}^{r-2} \left( {\begin{array}{c}2r\\ k\end{array}}\right) \frac{\partial ^{k+2}\hat{v}_\tau }{\partial \xi ^{k+1}\partial \eta }(\xi ') \left( \frac{\alpha }{J_\tau }\left( -s^\tau _{\xi ,j}\frac{\partial \hat{v}_\tau }{\partial \xi }+(r_{\xi ,j}^{\tau ,1})^2\frac{\partial \hat{v}_\tau }{\partial \eta }\right) \right) ^{(2r-k-1)}(\xi '). \end{aligned}$$

The fact that $J_{\tau ,p}>0$ and (2.5) yield that $J_\tau >0$ for sufficiently small $h$. Consequently, when $h$ is sufficiently small,

$$\begin{aligned} {\mathcal {J}}_1\ge 0. \end{aligned}$$

On the other hand, since $s_{\xi ,j}^\tau$ is linear with respect to $\xi$, $(s_{\xi ,j}^\tau )'=(\frac{\beta _2^\tau }{2}+\frac{\beta _3^\tau (1+g_j)}{4}) (\frac{\beta _3^\tau }{4})={\mathcal {O}}(h_\tau ^{2+\gamma })$, by the inverse inequality

$$\begin{aligned} |{\mathcal {J}}_2|\lesssim h^\gamma |\hat{v}_{\tau }|^2_{1,\tau _0}. \end{aligned}$$

Next we estimate ${\mathcal {J}}_3$. We observe that ${\mathcal {J}}_3$ is a summation of a finite number of terms which can be represented as

$$\begin{aligned} \alpha \frac{\partial ^{k_1+1}\hat{v}_\tau }{\partial \xi ^{k_1}\partial \eta } \left( \left( \frac{s^\tau _{\xi ,j}}{J_\tau }\right) ^{(l)}\frac{\partial ^{k_2+1}\hat{v}_\tau }{\partial \xi ^{k_2+1}} +\left( \frac{(r_{\xi ,j}^{\tau ,1})^2}{J_\tau }\right) ^{(l)}\frac{\partial ^{k_2+1} \hat{v}_\tau }{\partial \xi ^{k_2}\partial \eta }\right) \end{aligned}$$

for some $1\le l\le 2r, 0\le k_i, \le 2r, i=1,2$. Recall that $J_\tau$ is linear with respect to $\xi$, $J'_\tau =J_{\tau ,\xi }={\mathcal {O}}(h_\tau ^{2+\gamma })$. For all $l\ge 1$,

$$\begin{aligned} ( J_\tau ^{-1})^{(l)}=(-1)^l l!(J_\tau )^{-l-1}(J'_\tau )^l={\mathcal {O}}(h_\tau ^{l\gamma -2}). \end{aligned}$$

On the other hand, $(r_{\xi ,j}^{\tau ,1})^2$ is a constant with respect to $\xi$, $(r_{\xi ,j}^{\tau ,1})^2={\mathcal {O}}(h_\tau ^2)$. $s_{\xi ,j}^\tau$ is linear with respect to $\xi$, $s_{\xi ,j}^\tau ={\mathcal {O}}(h^{2}), (s_{\xi ,j}^\tau )'={\mathcal {O}}(h_\tau ^{2+\gamma })$. Therefore for all $l\ge 1$, we always have

$$\begin{aligned} \left( \frac{s^\tau _{\xi ,j}}{J_\tau }\right) ^{(l)}\lesssim h_\tau ^{\gamma },\left( \frac{(r_{\xi ,j}^{\tau ,1})^2}{J_\tau }\right) ^{(l)}\lesssim h_\tau ^\gamma . \end{aligned}$$

Again by the inverse inequality, we have

$$\begin{aligned} |{\mathcal {J}}_3|\lesssim h_\tau ^\gamma |\hat{v}_{\tau }|^2_{1,\tau _0}. \end{aligned}$$

Consequently,

$$\begin{aligned} \Theta _j^{(2r)}(\xi ')\gtrsim -h_\tau ^\gamma |\hat{v}_{\tau }|^2_{1,\tau _0}. \end{aligned}$$

The proof of (4.10) is completed. $\square$

We are now ready to bound $a_\tau (\cdot ,\cdot )$ from below.

Lemma 4.4

If $\tau \in {\mathcal {T}}_h$ is a shape regular $h^{1+\gamma }$-parallelogram, then when $h$ is sufficiently small,

$$\begin{aligned} a_\tau (v_h,\Pi v_h)\gtrsim C|v_h|^2_{1,\tau }+\mathrm{bdy}_\tau , \end{aligned}$$

(4.11)

where $C>0$ depends only on the minimal angle $\theta _0$, the parameters $\gamma$ and $r$, and

$$\begin{aligned} \mathrm{bdy}_\tau&= \sum _{j\in \mathbb {Z}_r} A_j \mathrm{bdy}_{\tau ,1,j}+\sum _{i\in \mathbb {Z}_r} A_i \mathrm{bdy}_{\tau ,2,i}. \end{aligned}$$

with

$$\begin{aligned} \mathrm{bdy}_{\tau ,1,j}=\frac{\partial \hat{v}_\tau }{\partial \eta }(-1, g_j)V_{E^\tau _1,g_j}(F_\tau (-1,g_j))-\frac{\partial \hat{v}_\tau }{\partial \eta }(1, g_j)V_{E^\tau _1,g_j}(F_\tau (1,g_j)), \end{aligned}$$

and

$$\begin{aligned} \mathrm{bdy}_{\tau ,2,i}=\frac{\partial \hat{v}_\tau }{\partial \eta }(g_i, -1)V_{E^\tau _2,g_i}(F_\tau (g_i,-1))-\frac{\partial \hat{v}_\tau }{\partial \eta }(g_i,1)V_{E^\tau _2,g_i}(F_\tau (g_i,1)). \end{aligned}$$

Proof

By (4.10), there exists a positive constant $C_1$ such that

$$\begin{aligned} I_1\ge -\sum _{j\in \mathbb {Z}_r} A_j\int _{-1}^1\Theta _j(\xi )d\xi -C_1h^{\gamma }|v|^2_{1,\tau }. \end{aligned}$$

Using the integration by parts, we have

$$\begin{aligned} -\int _{-1}^1\Theta _j(\xi )d\xi =\int _{-1}^1 \Phi _1(\xi ,g_j)d\xi +\mathrm{bdy}_{\tau ,1,j}, \end{aligned}$$

where

$$\begin{aligned} \Phi _1(\xi ,\eta )=\frac{\partial \hat{v}_\tau }{\partial \eta }\left( \frac{\alpha }{J_\tau }\left( -s^\tau _{\xi ,\eta }\frac{\partial \hat{v}_\tau }{\partial \xi }+(r_{\xi ,\eta }^{\tau ,1})^2\frac{\partial \hat{v}_\tau }{\partial \eta }\right) \right) . \end{aligned}$$

Then

$$\begin{aligned} I_1\ge \int _{-1}^1 \sum _{j\in \mathbb {Z}_r}A_j\Phi _1(\xi ,g_j)d\xi +\sum _{j\in \mathbb {Z}_r}A_j \mathrm{bdy}_{\tau ,1,j}-Ch^{\gamma }|v_h|^2_{1,\tau }. \end{aligned}$$

By the same arguments in Lemma 4.3, we obtain that for any fixed $\xi \in [-1,1]$,

$$\begin{aligned} \left| \int _{-1}^1\Phi _1(\xi ,\eta )d\eta -\sum _{j\in \mathbb {Z}_r}A_j\Phi _1(\xi ,g_j)\right| \lesssim h^\gamma |v_h|^2_{1,\tau }. \end{aligned}$$

Consequently,

$$\begin{aligned} I_1\ge \int _{\tau _0}\Phi _1(\xi ,\eta )d\xi d\eta +\sum _{j\in \mathbb {Z}_r}A_j \mathrm{bdy}_{\tau ,1,j}-Ch^{\gamma }|v_h|^2_{1,\tau }. \end{aligned}$$

By dual reasoning, we have

$$\begin{aligned} I_2\ge \int _{\tau _0}\Phi _2(\xi ,\eta )d\xi d\eta +\sum _{i\in \mathbb {Z}_r}A_i \mathrm{bdy}_{\tau ,2,i}-C_1h^{\gamma }|v_h|^2_{1,\tau }, \end{aligned}$$

where

$$\begin{aligned} \Phi _2(\xi ,\eta )=\frac{\partial \hat{v}_\tau }{\partial \xi }\left( \frac{\alpha }{J_\tau }\left( -s^\tau _{\xi ,\eta }\frac{\partial \hat{v}_\tau }{\partial \eta }+(r_{\xi ,\eta }^{\tau ,2})^2\frac{\partial \hat{v}_\tau }{\partial \xi }\right) \right) . \end{aligned}$$

Therefore, we have

$$\begin{aligned} a_\tau (v_h,\Pi v_h)&\ge \int _{\tau _0} (\Phi _1(\xi ,\eta )+\Phi _2(\xi ,\eta )) d\xi d\eta +\mathrm{bdy}_{\tau }-Ch^{\gamma }|v_h|^2_{1,\tau }. \end{aligned}$$

Note that

$$\begin{aligned} \Phi _1(\xi ,\eta )+\Phi _2(\xi ,\eta )=\frac{\alpha }{J_\tau }\left( (r_{\xi ,\eta }^{\tau ,1})^2\left( \frac{\partial \hat{v}_\tau }{\partial \eta }\right) ^2+(r_{\xi ,\eta }^{\tau ,2})^2\left( \frac{\partial \hat{v}_\tau }{\partial \xi }\right) ^2-2s^\tau _{\xi ,\eta }\frac{\partial \hat{v}_\tau }{\partial \xi }\frac{\partial \hat{v}_\tau }{\partial \eta }\right) . \end{aligned}$$

By (2.7) and Cauchy–Schwartz inequality, we have

$$\begin{aligned} \int _{\tau _0} \left| 2s^\tau _{\xi ,\eta }\frac{\partial \hat{v}_\tau }{\partial \xi } \frac{\partial \hat{v}_\tau }{\partial \eta }\right| d\xi d\eta \le \cos \theta _0 \int _{\tau _0} \left( (r^{\tau ,1}_{\xi ,\eta })^2 \left( \frac{\partial \hat{v}_\tau }{\partial \eta }\right) ^2+(r^{\tau ,2}_{\xi ,\eta })^2 \left( \frac{\partial \hat{v}_\tau }{\partial \xi }\right) ^2\right) d\xi d\eta . \end{aligned}$$

Therefore,

$$\begin{aligned} \Phi _1(\xi ,\eta )+\Phi _2(\xi ,\eta )\ge (1-\cos \theta _0)\frac{\alpha }{J_\tau }\left( (r_{\xi ,\eta }^{\tau ,1})^2\left( \frac{\partial \hat{v}_\tau }{\partial \eta }\right) ^2+(r_{\xi ,\eta }^{\tau ,2})^2\left( \frac{\partial \hat{v}_\tau }{\partial \xi }\right) ^2\right) . \end{aligned}$$

Note that $r_{\xi ,\eta }^{\tau ,1},r_{\xi ,\eta }^{\tau ,2}={\mathcal {O}}(h_\tau ), J_\tau ={\mathcal {O}}(h_\tau ^2)$, and $\alpha \ge \alpha _0$. Moreover, we have the equivalence $|\hat{v}_\tau |_{1,\tau _0}\sim |v_h|_{1,\tau }$. Therefore there exists a constant $C_2>0$ such that

$$\begin{aligned} a_\tau (v_h,\Pi v_h)\ge C_2|v_h|^2_{1,\tau } +\mathrm{bdy}_{\tau }-2C_1h^{\gamma }|v_h|^2_{1,\tau }. \end{aligned}$$

When $h$ is sufficiently small, the estimate (4.11) is valid. $\square$

Finally, we are ready to state and show the coercivity of $a_h(\cdot ,\Pi \cdot )$.

Theorem 4.5

Let ${\mathcal {T}}_h$ be a shape regular $h^{1+\gamma }$ parallelogram, then

$$\begin{aligned} a_h(v_h,\Pi v_h)\gtrsim |v_h|^2_{1}, \quad \forall v_h\in {\mathcal {U}}_h^r. \end{aligned}$$

(4.12)

Proof

The facts that $v_h$ and $V_{E,P},\forall E\in {\mathcal {E}}_h^{b,1},P\in E$ are continuous across each internal edge $E\in {\mathcal {E}}_h$ and that $v_h=0$ on the boundary $\partial \Omega$ implies that

$$\begin{aligned} \sum _{\tau \in {\mathcal {T}}_h} \mathrm{bdy_\tau }=0. \end{aligned}$$

Then (4.12) is a direct consequence of local estimates (4.11). $\square$

4.4 Inf–sup property

Summarizing the above two lemmas, we obtain the following inf–sup property.

Theorem 4.6

Let ${\mathcal {T}}_h$ be a shape regular $h^{1+\gamma },\gamma >0$ quadrilateral mesh and suppose the coefficient $\alpha$ is piecewise continuous with respect to ${\mathcal {T}}_h$. Then (4.1) holds when the meshsize $h$ is sufficiently small.

Proof

When $\alpha$ is piecewise constant, by (4.12) and (4.7), for any $v_h\in {\mathcal {U}}^r_h$,

$$\begin{aligned} \sup _{w_h\in {\mathcal {V}}_{h}} \frac{a_{h}(v_h,w_{h})}{|w_{h}|'_h} \ge \frac{a_h(v_h,\Pi v_h)}{|\Pi v_h|'_h}\gtrsim \frac{|v_h|_1^2}{|\Pi v_h|_h'}\gtrsim |v_h|_{1}. \end{aligned}$$

The inf–sup condition (4.1) is proved. Furthermore, an argument in the beginning of this section guarantee that (4.1) holds also for general piecewise continuous coefficient $\alpha$ with respect to the underlying mesh. $\square$

Remark 4.7

Let us reiterate the essential idea in establishing the inf–sup condition, the construction of the special mapping from the trail space to the test space is the key. Recall that the trial space is the same as the standard finite element method, which contains globally continuous piecewise polynomials. On the other hand, the test space contains globally discontinuous piecewise constants with much more “pieces” on the dual mesh. The feasibility of the mapping between the two spaces can be seen from the counting of total degrees of freedom. We examine the simplest case, the Poisson equation ($\alpha =0$) with zero Dirichlet boundary condition and ${\mathcal {T}}_h$ is the $n\times n$ square partition of the unit square $[0,1]^2$. For bilinear element, the dimension of the trial space is $(n-1)^2$, while the piecewise constants in the test space has exactly $(n-1)^2$ non-zero pieces on the dual mesh. For biquadratic element, the dimension of the trial space is $(2n-1)^2$. By our construction, non-zero constant pieces are those between four adjacent Gaussian points that form a square. In each of the horizontal and vertical directions, there are $2n$ Gaussian points and $2n-1$ intervals between them, and hence there are $(2n-1)^2$ squares between Gaussian points so that the test space has exactly $(2n-1)^2$ non-zero pieces on the dual mesh. The counting can be easily extended to $r$-degree tensor product space with both trial and test space have the same dimension $(rn-1)^2$. As for a general domain which can be partitioned by general quadrilaterals, a careful examination of the topological structure is needed. Nevertheless, the degrees of freedom for trial and test spaces are still the same, which guarantees the the existence of the aforementioned mapping even though the construction of such a mapping requires more delicate analysis as we have done in this work.

5 Numerical results

In this section, we present two numerical examples to validate our theoretical findings.

Example 1

We consider the problem (3.1), (3.2) with $\alpha =1$ and $\Omega =[0,1]^2$. We choose the right-hand-side function

$$\begin{aligned} f(x,y)&= [(5\pi ^2-4x^2-3)\sin (2\pi x) \sin (\pi y)-8\pi x\sin (\pi y)\cos (2 \pi x)\\&-2\pi \cos (\pi y)\sin (2\pi x)]e^{x^2+y}, (x,y)\in [0,1]^2 \end{aligned}$$

which allows the exact solution

$$\begin{aligned} u(x,y)=\sin (2\pi x) \sin (\pi y) e^{x^2+y}, (x,y)\in [0,1]^2. \end{aligned}$$

We use FV schemes (3.5) with $r=1,2,3,4$ to compute FVM approximate solutions of $u$. The partition ${\mathcal {T}}_k={\mathcal {T}}_{h_k}$, $k=1,\dots ,6$, are obtained by first uniformly refining the unite square $[0,1]^2$ and then adding some lines to obtain associated trapezoidal meshes, see Fig. 5 for an example of trapezoidal mesh.

Fig. 5

A trapezoidal mesh

We present our numerical results in Table 1. In this table, $r$ indicates the polynomial order, $N=h_k^{-1}=2^k, k=1,\ldots , 6$ indicates the number of partition along the $x-$ and $y-$ directions. The “Error” indicates the computed $H^1$ semi-norm error $|u-u_{h_k}|_{H^1}$ where $u_{h_j}$ is the finite volume solution in the space $U^r_{{h_k}}$ and “C.O.” indicates the computed convergence order of the $H^1$ semi-norm error. We observe that $|u-u_{h_k}|_{H^1}$ decays with the optimal convergence order $h_k^{r}$ which supports our theory (3.11).

Example 2

We consider the problem (3.1), (3.2) with $\Omega =[0,1]^2$ which admits a unique solution

$$\begin{aligned} u(x,y)&= \frac{x(1-x)+y(1-y)}{4}-\frac{2}{\pi ^3}\sum _{i=0}^{\infty }\frac{1}{(2i+1)^3(1+e^{-(2i+1)\pi })} \\&\cdot [(e^{-(2i+1)\pi y}+e^{-(2i+1)\pi (1-y)})\sin (2i+1)\pi x\\&+(e^{-(2i+1)\pi x}+e^{-(2i+1)\pi (1-x)})\sin (2i+1)\pi y ]. \end{aligned}$$

One can verify that $-\Delta u=1$ in $\Omega$. However, in this numerical experiment, we choose the non-constant coefficient as

$$\begin{aligned} \alpha (x,y)=\left\{ \begin{array}{ll} 1 &{}\quad x\le y\\ 1+x-y &{}\quad x>y \end{array} \right. \end{aligned}$$

which is continuous but not globally smooth in $\Omega$. Correspondingly, the right-hand-side function is given by

$$\begin{aligned} f(x,y)=\left\{ \begin{array}{ll} 1, &{}\quad x\le y\\ 1+x-y+\frac{\partial u}{\partial y}-\frac{\partial u}{\partial x}, &{}\quad x>y. \end{array} \right. \end{aligned}$$

Table 1 Error and convergence order for the problem with a sufficiently smooth function

We use FV schemes (3.5) with $r=1,2,3,4$ to compute FVM approximate solutions of $u$. The partition ${\mathcal {T}}_k={\mathcal {T}}_{h_k}$, $k=1,\dots ,7$, are quadrilateral meshes which are obtained by giving the corresponding rectangular meshes a small random perturbation. Specifically, the node coordinates of a point $(x_{ij},y_{ij})$ of the quadrilateral mesh ${\mathcal {T}}_k$ are given by

$$\begin{aligned} \begin{array}{l} x_{ij} = \frac{i}{N} + 0.1 \frac{1}{N} \sin \left( \frac{i\pi }{N}\right) \sin \left( \frac{j\pi }{N}\right) \text{ randn() }, \\ y_{ij} = \frac{j}{M} + 0.1 \frac{1}{M} \sin \left( \frac{i\pi }{N}\right) \sin \left( \frac{j\pi }{N}\right) \text{ randn() }, \\ 0 \le i,j \le N, \end{array} \end{aligned}$$

where $N=2^k,k=1,\ldots ,7$ and randn() is a built-in random number generator that usually produces a uniformly distributed random number in $(0,1)$. Notice that the random quadrilateral meshes used in ${\mathcal {T}}_k$ are not nested as $k$ increases from 1 to 8 since for each run, the random numbers are different. What we know is that the maximal distortion in the meshes is about 20 % of the uniform mesh size $h=1/M$. Depicted in Fig. 6 is the grid ${\mathcal {T}}_4$.

Fig. 6

A rectangular mesh with small random perturbation

The numerical results are demonstrated in Table 2. We observe that when $r=1$, the error $|u-u_{h_k}|_{H^1}$ decays with the optimal convergence order $r$, even here the coefficient $\alpha$ is nonsmooth and the underlying mesh has been randomly perturbed. However, when $r=2,3,4$, the error decay order is of about 2. Note that this does Not violate (3.11), since here the exact solution $u$ has singularities in the four corners of $\Omega$ and thus it only belongs to $H^{3-\epsilon }$ with an arbitrary small $\epsilon$. Moreover, we find that similar phenomena happen when we use corresponding FEM methods to compute the same problem. How to construct optimal order FV schemes based on adaptive (non-uniform) mesh for singular problems is our next on-going project.

Table 2 Error and convergence for the problem with a singular solution

6 Conclusions and future works

The design and analysis of high-order FV schemes are challenging tasks. In this paper, we constructed a family of any order FV schemes based on the Gauss points. Using a novel mapping from the trial to test space, we provide a unified proof for the optimal-convergence-order property of our FV schemes. Moreover, to prove this optimal-convergence-order property, we only require a very relaxed mesh condition which is similar to that in finite element methods.

It is obvious that we can use the same idea to construct FV schemes for 3D elliptic problems, and some other problems such as nonlinear problems. In fact, we have constructed and tested numerically some 3D FV schemes for some simple examples. From our numerical experiments, the 3D FV schemes also have optimal convergence order. However, since the traditional tensor-product argument is difficult to be applied to the arguments in the analysis of the current paper, the analysis of corresponding 3D FV schemes will be a challenging task and it is one of our on-going project.