Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
SIAM J. NUMER. ANAL.c
2012 Society for Industrial and Applied Mathematics
Vol. 50, No. 2, pp. 418–438
P1-NONCONFORMING FINITE ELEMENTS ON
TRIANGULATIONS INTO TRIANGLES AND QUADRILATERALS∗
R. ALTMANN†AND C. CARSTENSEN‡
Abstract. The P1-nonconforming finite element is introduced for arbitrary triangulations into
quadrilaterals and triangles of multiple connected Lipschitz domains. An explicit a priori analysis for
the combination of the Park–Sheen and the Crouzeix–Raviart nonconforming finite element methods
is given for second-order elliptic PDEs with inhomogeneous Dirichlet boundary conditions.
Key words. nonconforming finite elements, elliptic problems, a priori estimates
AMS subject classifications. 65N30, 65N12, 65N15
DOI. 10.1137/110823675
1. Introduction. Park and Sheen [PS03, Par03] introduced a basis for noncon-
forming P1finite elements on triangulations into quadrilaterals of simply connected
domains. Adaptive mesh-refinement has recently been proved to be optimal for the re-
lated Crouzeix–Raviart nonconforming FEM on triangles [BM08, Rab10]. In order to
use adaptive mesh-refinements with the Park–Sheen nonconforming FEM on quadri-
laterals, this paper introduces the combination of Park–Sheen with Crouzeix–Raviart
nonconforming finite elements. This requires understanding the Park–Sheen FEM
on multiple connected domains which consist of the domain Ω without all triangles.
The first main result of this paper characterizes a basis of this nonconforming finite
element space with global edge-connected exceptional basis functions of Definition 2.5,
below. The second main result is a complete a priori error analysis with explicit
constants for smooth solutions of second-order elliptic boundary value problems with
inhomogeneous Dirichlet conditions. For the Poisson model problem
(1.1) −Δu=fin Ω := (0,1)2and u=0on∂Ω
and a uniform triangulation of Ω into squares and right isosceles triangles of size h,
the a priori estimate of this paper implies for the energy norm (cf. Remark 5.2 below
for a proof)
|||u−uPS|||NC ≤1.75hfL2(Ω).
The proposed combination of the Park–Sheen and the Crouzeix–Raviart nonconform-
ing elements combines the minimal degrees of freedom per element domain with the
flexibility of adaptive mesh-refinements. The rest of the paper is organized as fol-
lows. Section 2 introduces a basis of the nonconforming and piecewise linear finite
∗Received by the editors February 7, 2011; accepted for publication (in revised form) November
13, 2011; published electronically March 13, 2012. This work was partly supported by the WCU
program through KOSEF (R31-2008-000-10049-0).
http://www.siam.org/journals/sinum/50-2/82367.html
†Institut f¨ur Mathematik, Technische Universit¨at Berlin, Straße des 17. Juni 136, D-10623 Berlin
Charlottenburg, Germany (raltmann@math.tu-berlin.de). This author’s work was supported by the
Berlin Mathematical School, the KKGS Stiftung, the Humboldt-Universit¨at zu Berlin, and the ERC
grant “Modeling, Simulation and Control of Multi-Physics Systems.”
‡Institut f¨ur Mathematik, Humboldt–Universit¨at zu Berlin, Unter den Linden 6, D-10099 Berlin,
Germany, and Department of Computational Science and Engineering, Yonsei University, 120-749
Seoul, Korea (cc@math.hu-berlin.de).
418
Downloaded 11/08/17 to 130.149.177.68. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
P1-NONCONFORMING FINITE ELEMENTS 419
element space on triangulations into triangles and quadrilaterals. Section 3 discusses
inhomogeneous Dirichlet boundary data and the possibility of inconsistent boundary
conditions. Section 4 analyzes a nonconforming interpolation operator, which en-
sures consistent boundary data. Section 5 presents explicit constants for an a priori
estimate for second-order elliptic PDEs. The numerical experiment of the Poisson
problem on a Z-shape with graded meshes and combined triangles and quadrilaterals
concludes the paper and underlines the necessity of the flexible mixture of triangles
and quadrilaterals.
We employ standard notation on Lebesgue and Sobolev spaces and write ab
to abbreviate a≤cb with some constant c, independent of the mesh-size.
2. The P1-nonconforming finite element. This section introduces a basis for
nonconforming P1finite elements on triangulations into triangles and convex quadri-
laterals. Let Tbe a regular triangulation (see [Cia78]) of the two-dimensional bounded
and connected Lipschitz domain Ω ⊂R2with polygonal boundary ∂Ω into closed tri-
angles (namely, T3) and closed, convex quadrilaterals (namely, T4) with the set of
edges Eand the set of nodes N. Here, regular means that hanging nodes are excluded
in the sense that two distinct nondisjoint element domains share either a common
edge or a common vertex. The first goal of this paper is a characterization of a basis
of the nonconforming finite element space
PS(T):=P1(T)∩C({mid(E)|E∈E})
of piecewise affine functions which are continuous at the midpoints of all interior edges.
This generalizes the Crouzeix–Raviart finite elements CR(T3)[CR73]aswellasthe
nonconforming P1 finite elements on quadrilaterals after Park and Sheen [PS03] in
the sense that they may be mixed arbitrarily.
Here and throughout this paper, Pk(T) denotes the set of piecewise polynomials
of degree ≤kwith respect to T. Furthermore, mid(E) stands for the midpoint of the
edge E,N:= |N| denotes the number of nodes, and N(E) denotes the two endpoints
of an edge E. All quadrilaterals in this paper are closed and convex with inner angles
strictly smaller than π. All domains have polygonal boundary.
Definition 2.1 (edge-neighbors, Rk-related, edge-connected). Two distinct ele-
ment domains A, B ∈T are edge-neighbors or R-related if they share a common edge,
written ARB. Two element domains A, B ∈T are Rk-related, k≥2,ifARBor
there exist C1,...,C
m∈T with ARC1,C
1RC2,...,C
mRBand m≤k−1∈N∪{∞}.
Two element domains Aand Bin Tare called edge-connected if AR∞B.
Remark 2.1. The relation R∞is an equivalence relation and defines equivalence
classes called edge-connectivity components.
Definition 2.2 (nodal basis function I). Given an edge-connected triangulation
T4of a Lipschitz domain into quadrilaterals with set of edges E(z):={E∈E|z∈
N(E)}and the respective set of midpoints mid(E(z)), a nodal basis function ϕj∈
PS(T4)is uniquely defined for every vertex zjby
ϕj(m)=1if m∈mid(E(zj)),
0if m∈mid(E)\mid(E(zj)).
(2.1)
Remark 2.2. (a) Any function u∈P1(Q) is characterized by the quadrilateral
condition (diagonal rule) m1+m3=m2+m4for its values m1=u(mid(E1)),...,
m4=u(mid(E4)) at the consecutive midpoints mid(E1),...,mid(E4); see Figure 2.1.
In particular, (2.1) is well defined in PS(T4).
Downloaded 11/08/17 to 130.149.177.68. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
420 R. ALTMANN AND C. CARSTENSEN
z1z2
z3
z4
m2
m3
m4
m1
Fig. 2.1.Diagonal rule m1+m3=m2+m4illustrates that the midpoints of a convex quadri-
lateral Qform a parallelogram.
(b) For an enumeration E={E1,...,E
|E|},anyu∈PS(T4) is represented by
the vector xu∈R|E| defined by
xu(j):=u(mid(Ej)),j=1,...,|E|.
This stores the function values at the |E| midpoints of edges where uis continuous.
Let Ej1,E
j2,E
j3,E
j4denote the consequent edges of the quadrilateral Qjand let the
matrix M∈ {−1,0,1}|T 4|×|E| equal
Mjk =⎧
⎪
⎨
⎪
⎩
1ifk=j1or k=j3,
−1ifk=j2or k=j4,
0otherwise
for j=1,...,|T 4|,k=1,...,|E|, which represents all |T4|diagonal rules. Then,
u∈PS(T4) implies Mxu= 0. In addition, for a continuous function vwith coefficient
vector xvdefined as above, Mxv= 0 implies the unique existence of a function
vPS ∈PS(T4) with v(mid(Ej)) = vPS(mid(Ej)) for j=1,...,|E|.
Theorem 2.1 (see [PS03]). Let T4be an edge-connected regular triangulation of
the simply connected Lipschitz domain Ω⊂R2into quadrilaterals with edges Eand
nodes N.ThenPS(T4)has the dimension |E| − |T4|=N−1with the counting
measure |·|such that |E|,N:= |N|,|T 4|denote the number of edges, nodes, and
quadrilaterals. For any j0∈{1,...,N}, with the omission operator ∨
·,
(ϕ1,...,∨
ϕj0,...,ϕ
N):=(ϕ1,...,ϕ
j0−1,ϕ
j0+1,...,ϕ
N)
is a basis of PS(T4).
Definition 2.3 (multiple connected). A bounded, connected, and open set Ω⊂
R2is called k-times connected if there exist exactly kconnectivity components of
∂Ω=Γ
0∪Γ1∪···∪Γk−1,whereΓ0,...,Γk−1are pairwise disjoint connected compact
sets in R2such that Γ0is the boundary of the unbounded connectivity component of
R2\Ω.
Although we are interested in Lipschitz domains we have to consider non-Lipschitz
domains for quadrilaterals. The reason is that in the combination of triangles and
quadrilaterals every edge-connectivity component of quadrilaterals will be discussed
separately, which could be possibly non-Lipschitz. An example is the triangulation
Downloaded 11/08/17 to 130.149.177.68. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
P1-NONCONFORMING FINITE ELEMENTS 421
Γ0
Γ0
Γ0Γ1
Γ1
Γ0
Fig. 2.2.Example of (left) a simply and (right) a twice connected non-Lipschitz domain.
z1z2
Q1
Q2
Q3
Q4
Q5
Fig. 2.3.Examples of Mnedge-connectivity components of T4(zn):(left)T4(z1)=C1,1=
{Q1,Q
2,Q
3}for M1=1and (right) T4(z2)=C2,1˙
∪C
2,2with C2,1={Q4},C2,2={Q5}for
M2=2.
from Figure 2.2, where the holes are filled with two triangles, respectively. For arbi-
trary connected polygonal domains we have to allow, in contrast to Lipschitz domains,
multiple nodal basis functions per node. For any node zn∈Nthe neighboring quadri-
laterals
T4(zn):={Q∈T4|zn∈N(Q)}
are partitioned into Mnpairwise disjoint edge-connectivity components Cn,1,...,Cn,Mn,
T4(zn)=Cn,1˙
∪C
n,2˙
∪... ˙
∪C
n,Mn.
For an example see Figure 2.3. Notice that for Lipschitz domains M1=M2=···=
MN=1holds.
Definition 2.4 (nodal basis function II). For any node znwith neighbor-
ing quadrilaterals T4(zn)=Cn,1˙
∪... ˙
∪C
n,Mnwe define Mnnodal basis functions
ϕn,1,...,ϕ
n,Mn∈PS(T4)in the following way. Given a triangulation Cn,m,de-
fine ϕ∈PS(Cn,m)as in Definition 2.2 and extend ϕby zero to a function ϕn,m in
PS(T4).
The rest of this section is devoted to multiple connected domains. Figure 2.4
illustrates that the nodal basis functions from Definition 2.4 do not suffice.
Example 2.1 (necessity of new basis functions). The triangulation T4of the
domain Ω = (−1,2)2\[0,1]2into eight squares of size 1 as in Figure 2.4 displays (left)
nodal basis functions −ϕ1,+ϕ2,...,+ϕ16 of the type defined in Definition 2.2. In fact,
one can prove that ϕ1,...,ϕ
15 are linearly independent, whence dim PS(T4)≥15.
Downloaded 11/08/17 to 130.149.177.68. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
422 R. ALTMANN AND C. CARSTENSEN
−ϕ1+ϕ2−ϕ3+ϕ4
+ϕ5−ϕ6+ϕ7−ϕ8
−ϕ9+ϕ10 −ϕ11 +ϕ12
+ϕ13 −ϕ14 +ϕ15 ϕ16
1
1
1-1
0
0
ψ
Fig. 2.4.Nodal basis functions ϕ1,...,ϕ
16 from Definition 2.2 (left) are linearly dependent
and (right) exclude ψ∈PS(T4)as discussed in Example 2.1.
Since ϕ16 =−ϕ1+ϕ2−···−ϕ14 +ϕ15,ϕ16 lies in span{ϕ1,...,ϕ
15}. The right side
of Figure 2.4 displays
ψ∈PS(T4)\span{ϕ1,...,ϕ
15}
and hence dim PS(T4)≥16. An immediate proof of ψ/∈span{ϕ1,...,ϕ
15}employs
the linear functional
:PS(T4)→R,v→ v(1/2,0) + v(1/2,1) −v(0,1/2) −v(1,1/2)
and the fact (ϕ1)=···=(ϕ15)=0=1=(ψ).
Example 2.1 suggests enlarging the set of nodal basis functions by some other
functions in PS(T4) which somehow link connectivity components of R2\Ω. In what
follows E(D) denotes the set of edges in the subset D⊆Ω.
Definition 2.5 (edge-path). Let T4be an edge-connected triangulation into
quadrilaterals of some k-times connected domain Ω⊂R2with k≥2.Further
let Γaand Γbdenote two different components of ∂Ω. Choose a subtriangulation
{Q1,...,Q
J}⊂T4which is (in itself) edge-connected and satisfies
E(Q1)∩E(Γa)=∅and E(QJ)∩E(Γb)=∅
as well as
Ej+1 := E(Qj)∩E(Qj+1)∈Efor j=1,...,J −1.
Then, for any choice
E1∈E(Q1)∩E(Γa)and EJ+1 ∈E(QJ)∩E(Γb),
an edge-path ψ∈PS(T4)is defined by
ψ(m):=⎧
⎪
⎨
⎪
⎩
1if m= mid(E1),
±1if m= mid(Ej)for j=2,...,J,
0for any other midpoint.
(2.2)
Downloaded 11/08/17 to 130.149.177.68. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
P1-NONCONFORMING FINITE ELEMENTS 423
1−11−1
−1
1
Γa
Q1
0 0 0 0
0
00
000
Γb
Fig. 2.5.Illustration of ψfrom Definition 2.5. Since E(Q1)∩E(Γa)allows two choices of E1,
there exists a second choice of ψ.
For j=1,...,J−1the signs are uniquely defined by ψ(mid(Ej+1)) = ψ(mid(Ej)) if
Ej∩Ej+1 =∅and ψ(mid(Ej+1)) = −ψ(mid(Ej)) if Ej∩Ej+1 =∅.
Remark 2.3. (a) It holds that supp ψ=Q1∪···∪QJ.
(b) The choice of E1and EJis not unique; cf. Figure 2.5. Also, the subtriangu-
lation {Q1,...,Q
J}and therefore supp ψis not unique; cf. Figure 2.4. Thus, there
exist several possibilities for ψ.
The following theorem introduces a basis of PS(T4) for general multiple con-
nected domains with polygonal boundary.
Theorem 2.2 (basis for multiple connected domains). For the regular triangula-
tion T4of the k-times connected domain Ω⊂R2into edge-connected quadrilaterals,
PS(T4)has the k-independent dimension
dim(PS(T4)) = |E|−|T 4|.
Let ϕn,m denote the nodal basis functions for n=1,...,N,m=1,...,M
nfrom
Definition 2.4. Further, let ψ1,...,ψ
k−1denote edge-paths from Definition 2.5, each
connecting two pairwise disjoint connectivity components of ∂Ωsuch that each connec-
tivity component of ∂Ωappears at least once. Then, for any (n0,m
0),n0∈{1,...,N},
m0∈{1,...,M
n0},
(ψ1,...,ψ
k−1,ϕ
1,1,...,ϕ
1,M1,ϕ
2,1,...,∨
ϕn0,m0,...,ϕ
N,MN)(2.3)
(with the omission operator ∨
·)isabasisofPS(T4).
Proof. The arguments in the proof of dim(PS(T4)) ≤|E|−|T4|in [PS03, p. 632]
work identically for multiple connected domains. It remains to show that (2.3) are
|E|−|T4|linearly independent functions in order to prove that this defines a basis.
The proof uses mathematical induction over the number of quadrilaterals in T4.
The initial step |T 4|= 1, i.e., a triangulation of only one quadrilateral which is simply
connected and Lipschitz, is already shown by Theorem 2.1. Assume that the claim is
true for triangulations into nquadrilaterals and let T4be an arbitrary triangulation
into n+1≥2 edge-connected quadrilaterals. Choose a quadrilateral Q∈T4which
contains a boundary edge such that S4:= T4\{Q}still is edge-connected. The
induction hypothesis gives a basis for PS(S4). We distinguish four cases.
Case 1. |E(Q)∩E(S4)|= 1 (cf. Figure 2.6). First, we consider all basis functions of
PS(S4) which vanish in M1. Those functions can be extended by zero to functions in
PS(T4). Second, basis functions with nonzero values in M1are extended by the same
Downloaded 11/08/17 to 130.149.177.68. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
424 R. ALTMANN AND C. CARSTENSEN
A B
Q
M1
M3
M4
S4
A
Q
M1
M2
M3
M4
S4
Fig. 2.6.Situation of (left) Case 1and (right) Case 2in the proof of Theorem 2.2.
Q
M1
M2
M3
M4
S4S4
Q
M3
S4
Fig. 2.7.Situation of (left) Case 3and (right) Case 4in the proof of Theorem 2.2.
value in M4and zero elsewhere such that the quadrilateral condition of Qis fulfilled.
All these functions are still linearly independent in PS(T4). Together with the nodal
basis functions from Definition 2.4 at Aand B, which are obviously independent
because of their value in M3, we constructed
(|E|−3) −|S4|+2=(|E|−3) −(|T 4|−1) + 2 = |E|−|T4|
independent functions.
Case 2. E(Q)∩E(S4) are exactly two neighboring edges (cf. Figure 2.6). Again
we extend all basis functions of PS(S4)toPS(T4) by zero if they vanish in M1and
M2. Otherwise we extend with zero in M3and the appropriate value in M4such that
the diagonal rule in Qis fulfilled. With the same argumentation as above, these are
together with the nodal basis function from Definition 2.4 at A
(|E|−2) −(|T 4|−1) + 1 = |E|−|T 4|
linearly independent functions.
Case 3. E(Q)∩E(S4) are exactly two opposed edges (cf. Figure 2.7). In this
case we extend all basis functions of PS(S4) with zero in M1and with some value
in M3such that the quadrilateral condition of Qis fulfilled. Here, we have to add
an edge-path from Definition 2.5, i.e., the function which has the values 1 in M1,−1
in M3, and zero in all other midpoints. This ensures with the induction hypothesis
that all connectivity components of ∂Ω are linked by edge-paths. Obviously, these
are |E|−|T 4|linearly independent functions.
Case 4. |E(Q)∩E(S4)|= 3 (cf. Figure 2.7). Since (|E|−1) −|S4|=|E| −|T 4|,
we just have to extend all basis functions of PS(S4) by the appropriate value in M3
(quadrilateral condition).
At this state, we have found a basis of PS(T4) which does not totally coincide with
(2.3). However, the choice of the basis of PS(S4) and some easy linear combinations
(especially with the new added functions) yield the claim.
Downloaded 11/08/17 to 130.149.177.68. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
P1-NONCONFORMING FINITE ELEMENTS 425
Remark 2.4. Let Bbe the (|E|−|T 4|)×|E|matrix, where B(f,e)givesthevalue
of the fth function in (2.3) at the midpoint of the eth edge and Mthe matrix from
Remark 2.2(b) which stores all quadrilateral conditions. Then the theorem says that
a vector xsatisfies Mx = 0 if and only if xis a linear combination of the rows of B.
Therein the vector xcontains the function values of a function in PS(T4)atthe|E|
midpoints of edges.
Theorem 2.3 (basis of PS(T)). Let T=T3∪T4be a regular triangulation of
the bounded Lipschitz domain Ωinto triangles and quadrilaterals.
Furthermore, T4=C1˙
∪C2˙
∪... ˙
∪CK,whereeachCkdenotes one edge-connectivity
component of T4.LetBk=(fk,1,...,f
k,|Bk|)denote a basis of PS(Ck)for each
k=1,...,K, according to Theorem 2.2. By Fk,j ∈PS(T)we denote the extension
of fk,j by zero at all midpoints of E\E(Ck),k=1,...,K,j=1,...,|Bk|.Furtherlet
φEdenote the Crouzeix–Raviart basis function for any edge Ewhich is not part of a
quadrilateral. The function φEhas the value 1at the midpoint of Eand is zero at all
midpoints of E\{E}. Then, with the enumeration E(T3)\E(T4)={E1,...,E
L},
(F1,1,...,F
1,|B1|,F
2,1,...,F
K,|BK|,φ
E1,...,φ
EL)(2.4)
is a basis of PS(T)and dim(PS(T)) = |E|−|T 4|.
Proof. Consider a linear combination of functions in (2.4) which gives zero and
therefore vanishes at all midpoints of E.Forj=1,...,L, the Crouzeix–Raviart basis
function φEjis the only function in (2.4) with φEj(mid(Ej)) = 0. Thus the coefficients
of φE1,...,φ
ELhave to vanish. Since the components {Ck}cannot be edge-connected,
we can consider each edge-connectivity component separately. The fact that Bkis a
basis of PS(Ck) shows the linear independence of (2.4).
Given an arbitrary uPS ∈PS(T), again we use the fact that Bkis a basis of
PS(Ck). Consequently, the values of uPS at the midpoints of E(T4) can be designed.
For any remaining edge, i.e., E(T3)\E(T4), there exists a Crouzeix–Raviart basis
function.
3. Consistent boundary conditions. This section is devoted to Dirichlet
boundary conditions and the concept of consistent Dirichlet data. In fact, the di-
agonal rule of PS(Q) for a quadrilateral Qstates a necessary condition for the values
at the midpoints of E(Q).
Definition 3.1 (consistent Dirichlet data). Consider Dirichlet data given by
the values at the midpoints of E(ΓD). Such data are called consistent if there exists
a linear combination of functions in PS(T)which have the given boundary values at
the midpoints of E(ΓD).
The following theorem shows how to recognize triangulations where inconsistent
boundary data can appear.
Theorem 3.1. Let Γ0,...,Γk−1denote the connectivity components of ∂Ω=Γ
D
and Ta triangulation into quadrilaterals and triangles. Then, every Dirichlet data
is consistent if and only if there exists a component Γj0which contains an edge of a
triangle or consists of an odd quantity of edges.
Proof. Consider that each boundary component consists only of quadrilateral
edges and all quantities of edges are even. With E(∂Ω) = {E1,...,E
2k}we show
that the data with 1 at the midpoint of E1=conv{A, B}and zero at midpoints of
E(∂Ω)\{E}are not consistent. Since edge-paths just shift boundary data to different
boundary components, we can assume that Ω is simply connected. Thus, only ϕA
and ϕBare nonzero at mid(E1). To generate the value 1 we use xtimes ϕA.To
reach all the zeros at the boundary one gets alternately minus and plus xtimes the
Downloaded 11/08/17 to 130.149.177.68. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
426 R. ALTMANN AND C. CARSTENSEN
corresponding nodal basis function. Because of the even quantity of boundary edges,
we obtain −xtimes ϕB. Thus, the value on the midpoint of E1is x−x=0,which
is a contradiction.
For the other direction we construct the boundary data with the value 1 on an
arbitrary boundary edge E=conv{A, B}and zero anywhere else. Because of the
edge-paths, it suffices to consider edges of Γj0. On edges of triangles there is nothing
to show, hence we consider an edge of a quadrilateral. To construct the required
boundary data, we set 1/2timesϕAand 1/2timesϕB. To obtain all the zero values,
we set alternately minus and plus 1/2 times the corresponding nodal basis function.
This algorithm works because of the odd quantity of edges or stops if an edge of a
triangle appears.
Remark 3.1. Consistent boundary conditions are necessary for the existence of
discrete solutions in section 5.1. Theorem 5.2 presents sufficient conditions as well.
Remark 3.2. In the case of inconsistent data one may change the triangulation,
i.e., split one quadrilateral at the boundary into two triangles; see Theorem 3.1. One
may also change the data and consider the projection bcon
Dof the boundary data bD
into the space of consistent boundary.
The approximation operator of the next section will lead to consistent boundary
data.
4. Approximation operator J.This section analyzes the nonconforming in-
terpolation operator for triangulations into triangles and quadrilaterals and serves as
preparation for the calculation of explicit a priori constants in section 5.
Definition 4.1 (approximation operator J[PS03]). We define the approxima-
tion operator J:C(Ω) →PS(T)by
(Jϕ)(m):=1
2(ϕ(P1)+ϕ(P2)) for m=(P1+P2)/2∈mid(E)
for all midpoints m∈mid(E),P1,P
2∈Nwith conv{P1,P
2}∈Eand ϕ∈C(Ω).
Remark 4.1. Since Jmaps into PS(T), the operator designs consistent boundary
data for given Dirichlet data uD∈C(Ω).
Proposition 4.1. Let T=conv{P1,P
2,P
3}be a triangle with greatest interior
angle α,diameterhT,and
C(α):=1/4+2/π2
1−|cos α|1/2
.
Then, for w∈H2(T)and the nodal interpolation operator IC, it holds that
∇(w−ICw)L2(T)≤C(α)hTD2wL2(T),(4.1)
w−ICwL2(T)≤5/3C(α)h2
TD2wL2(T).(4.2)
Proof. The proof of (4.1) can be found in [CGR11]. With mean integral
·dx,
one notices the trace identity
E
fds=
T
fdx+1
2
T
(x−P)·∇f(x)dx(4.3)
follows if T=conv{E,P},E∈E(T), P∈N(T) with integration by parts and
Downloaded 11/08/17 to 130.149.177.68. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
P1-NONCONFORMING FINITE ELEMENTS 427
elementary geometry. Set e:= w−ICwand obtain by the trace identity (f=e2)
e2
L2(T)≤|T|
|E|e2
L2(E)+hTeL2(T)∇eL2(T)
≤|T|
|E|e2
L2(E)+1
2e2
L2(T)+h2
T
2∇e2
L2(T).
Since evanishes at the endpoints of E, we use the Friedrichs inequality. In addition,
we again use the trace identity with f=|∂e/∂s|2,whichgives
|T|
|E|e2
L2(E)≤|T||E|
π2∂e/∂s2
L2(E)≤h2
T
π2∇e2
L2(T)+h3
T
π2∇eL2(T)D2eL2(T).
The aforementioned estimates and the first claim (4.1) lead with 2/π ≤C(α)eventu-
ally to
1
2e2
L2(T)≤h2
T
π2∇e2
L2(T)+h3
T
π2∇eL2(T)D2wL2(T)+h2
T
2∇e2
L2(T)
≤5C2(α)
6h4
TD2w2
L2(T).
The a priori estimate requires an estimate for w−Jw2
H1(Q)and some shape
regularity conditions on the triangulation T. Suppose that interior angles ωin Tare
uniformly bounded from below and bounded away from πin the sense of
0<ω
0≤ω≤π−ω0<π
with some universal constant ω0>0. Let θ0>0 be the smallest angle of diagonals
in all quadrilaterals in T.
Remark 4.2. For a quadrilateral Qdivided by a diagonal into two triangles, the
largest interior angles of the triangles belong to the interval [ω0,π−ω0]. Hence,
∇(w−ICw)L2(Q)≤C(ω0)hQD2wL2(Q).(4.4)
The rest of this section proves the following theorem.
Theorem 4.2. Let Qbe a convex quadrilateral with constants C(θ0)and C(ω0)
as defined in Proposition 4.1. Then, for any w∈H2(Q), it holds that
∇(w−Jw)L2(Q)≤C(θ0)hQD2wL2(Q),(4.5)
w−JwL2(Q)≤(2C(ω0)+C(θ0)/2)h2
QD2wL2(Q).(4.6)
Proof. Let E=conv{P1,P
3}be one diagonal of Q=conv{P1,...,P
4}with unit
tangent vector τ:= (P3−P1)/|P3−P1|.Letm1and m2be the edge midpoints of
conv{P1,P
2}and conv{P2,P
3}; see Figure 4.1. Then,
Jw(P3)−Jw(P1)=2Jw(m2)−2Jw(m1)=w(P3)−w(P1).
Hence f:= ∇(w−Jw)·τsatisfies
Efds = 0. The trace identity (4.3) on T1=
conv{P2,E}leads for ¯
f:=
T1fdxto
|¯
f|≤ 1
2|T1|x−P2L2(T1)∇fL2(T1)≤hT
8|T1|∇fL2(T1).
Downloaded 11/08/17 to 130.149.177.68. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
428 R. ALTMANN AND C. CARSTENSEN
T2
T1
m1
m2
E
P1
P2
P3
P4
Fig. 4.1.Quadrilateral Qdivided by diagonal Einto triangles T1and T2in the proof of
Theorem 4.2.
The Pythagoras theorem and the Poincar´e inequality with the Payne–Weinberger
constant [PW60] imply
f2
L2(T1)=f−¯
f2
L2(T1)+¯
f2
L2(T1)≤h2
T1
π2+1
8∇f2
L2(T1).(4.7)
The same calculation for T2as well as on the triangles which occur by the division of
Qby the other diagonal with tangent vector μ:= (P4−P2)/|P4−P2|.|τ·μ|=|cos θ0|
equals the angle of the diagonals and [CGR11] shows
|a|2≤(a·τ)2+(a·μ)2
1−|τ·μ|for all a∈R2.
This is evaluated for a:= ∇(w−Jw)(x) and thereafter integrated over x∈Q.The
estimate (4.7) for all the triangles then proves (4.5).
The proof of the second claim employs the nodal interpolation operator ICfrom
Proposition 4.1 on the triangles T1and T2of Figure 4.1. Since e:= ICw−Jw ∈P1(T1)
vanishes along m1m2,
e(y)=e(x)+∇e|T1·(y−x)=∇e|T1·(y−x)
for all y∈T1and x∈m1m2. Therefore,
e2
L2(T1)≤h2
T1/4∇e2
L2(T1).
This and an analogue on T2lead to
e2
L2(Q)≤h2
Q/4∇e2
L2(Q).
The triangle inequality and (4.5)–(4.4) imply
∇eL2(Q)≤∇(w−ICw)L2(Q)+∇(w−Jw)L2(Q)
≤(C(ω0)+C(θ0))hQD2wL2(Q).
This and (4.2) result in
w−JwL2(Q)≤w−ICwL2(Q)+eL2(Q)
≤5/3C(ω0)h2
QD2wL2(Q)+1/2(C(ω0)+C(θ0))h2
QD2wL2(Q)
≤(2C(ω0)+C(θ0)/2)h2
QD2wL2(Q).
Downloaded 11/08/17 to 130.149.177.68. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
P1-NONCONFORMING FINITE ELEMENTS 429
5. A priori error estimate for elliptic PDEs. This section analyzes explic-
itly the involved constant in the a priori error estimate using Park–Sheen elements.
Therefore, the existence of a unique solution of the discrete Dirichlet problem is shown
first.
5.1. Model problem and its discretization. For the bounded Lipschitz do-
main Ω, the right-hand side f∈L2(Ω), and uD∈H2(Ω), the elliptic boundary value
problem reads
−div(A∇u)+b·∇u+γu =fin Ω,
u=uDon ∂Ω.
(5.1)
Here and throughout this paper, the matrix A∈L∞(Ω; R2×2) is bounded, symmetric,
and uniformly positive definite in the sense that there exist positive αmin,α
max with
0<α
min|ξ|2≤ξtA(x)ξ≤αmax|ξ|2<∞for all ξ∈R2and a.e. x∈Ω.
Furthermore, let b∈H(div,Ω) ∩L∞(Ω; R2)andγ∈L∞(Ω) be bounded almost
everywhere by positive βmax := bL∞(Ω) and γmax := γL∞(Ω) and assume
div b≤2γa.e. in Ω.(5.2)
The nonsymmetric bilinear form awith
a(u, v):=(A∇u, ∇v)L2(Ω) +(b·∇u+γu,v)L2(Ω) for all u, v ∈H1(Ω)
is bounded and H1
0(Ω)-elliptic. With the linear functional F:= f−a(uD,·), the weak
formulation reads as follows: seek u0∈H1
0(Ω) such that
a(u0,v)=F(v) for any v∈H1
0(Ω).(5.3)
The Lax–Milgram lemma [BS08, p. 62] guarantees the unique existence of the weak
solution u:= u0+uD. The regularity of uis a subtle issue and we refer to [Gri85] for
sufficient conditions for u∈H2(Ω).
Given a regular triangulation Tof Ω into triangles and quadrilaterals, the finite
element space with boundary conditions reads
PS0(T)={vPS ∈PS(T)|for all E∈E(∂Ω),v
PS(mid(E)) = 0}.
The discrete problem involves the restriction of ato an element Q∈T,namely,
aQ(u, v):=(A∇u, ∇v)L2(Q)+(b·∇u+γu,v)L2(Q),
and the discrete bilinear form
aNC(u, v):=
Q∈T
aQ(u, v)foru, v ∈PS(T)+H1(Ω).
The discrete bilinear form corresponds to
|||v|||NC := aNC(v,v)1/2for u, v ∈PS(T)+H1(Ω).
With FNC := f−aNC(uD,·), the weak formulation for the discrete problem reads as
follows: seek u0
PS ∈PS0(T) such that
aNC(u0
PS,v
PS)=FNC(vPS) for all vPS ∈PS0(T).(5.4)
Given any solution u0
PS, the Park–Sheen approximation to the exact solution ureads
uPS := u0
PS +JuD∈PS(T). The existence of the discrete solution is the subject of
the next subsection.
Downloaded 11/08/17 to 130.149.177.68. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
430 R. ALTMANN AND C. CARSTENSEN
5.2. Discrete ellipticity. The existence of a unique discrete solution is based on
a discrete Friedrichs inequality for a partition Tof Ω into triangles and quadrilaterals.
Theorem 5.1 (discrete Friedrichs inequality). There exists a constant CdF,in-
dependent of the mesh-size of T, such that any v∈H1
0(Ω) + PS0(T)satisfies
vL2(Ω) ≤CdF∇NCvL2(Ω) := CdF
T∈T ∇v2
L2(T)1/2
.(5.5)
Proof.LetT∗be some refined triangulation into triangles where each quadrilat-
eral in Tis divided into two triangles. Then v∈H1
0(Ω) + CR0(T∗) and (5.5) follows
from [BS08, Theorem 10.6.12].
Let κdenote the ratio of the largest and smallest edge in any quadrilateral, i.e.,
max
Q∈T 4
largest edge of Q
smallest edge of Q=: κ.
If Tconsists only of triangles, set κ=1.
Theorem 5.2 (existence of a unique discrete solution). Let b∈H(div,Ω) be
piecewise constant. For sufficient small mesh-size in the sense that
hmax := max{hT|T∈T}≤αmin sin ω0
2κβmax
,(5.6)
there exists a unique solution u0
PS ∈PS0(T)of (5.4).
Proof. The boundedness of aNC is obvious, so the focus is on the ellipticity with
respect to the broken H1-norm
·H1(T):= (·2
L2(Ω) +|·|2
NC)1/2with |·|2
NC =
Q∈T ∇·2
L2(Q).
Notice that b∈H(div,Ω) ∩P0(T;R2) means that the jumps [b·νE]Evanish across
all interior edges. An elementwise integration by parts plus (5.2) lead to
αmin|u0
PS|2
NC +1
2
Q∈T
∂Q
(b·ν)(u0
PS)2ds ≤aNC(u0
PS,u
0
PS).
Let Ebe an edge of some quadrilateral Q.IfEis an edge on the boundary ∂Ω, u0
PS
is affine and vanishes in mid(E). It follows with h2
E/|Q|≤κ/ sin ω0that
E
(u0
PS)2ds =h3
E
12
∂u0
PS
∂s E
2
≤h3
E
12|Q|∇u0
PS2
L2(Q)≤hEκ
12 sinω0∇u0
PS2
L2(Q).
ForaninterioredgeE=E(Q1)∩E(Q2) with midpoint mE:= mid(E), the product
rule for jumps [·]Eand averages ·Eleads to
E
[(u0
PS)2]Eds =2
E
[u0
PS]Eu0
PSEds =2
E
[u0
PS]E(u0
PSE−u0
PS(mE))ds.
Since [u0
PS]Eand u0
PSE−u0
PS(mE) are affine along Eand vanish in mE,
2
E
[u0
PS]E(u0
PSE−u0
PS(mE))ds ≤h3
E
6|∇u0
PS|Q1|2+|∇u0
PS|Q2|2
≤hEκ
6sinω0∇NCu0
PS2
L2(Q1∪Q2).
Downloaded 11/08/17 to 130.149.177.68. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
P1-NONCONFORMING FINITE ELEMENTS 431
In the case that Qis a triangle, the aforementioned arguments remain valid with
the substitution of κby 4. The discrete Friedrichs inequality (5.5) as well as the
combination of the preceding estimates and the summation over all quadrilaterals
and triangles lead to
1
1+C2
dF αmin −hmaxβmaxκ
sin ω0u0
PS2
H1(T)≤aNC(u0
PS,u
0
PS).
Provided hmax is sufficiently small as in (5.6), this implies ellipticity in the sense of
αmin
2+2C2
dF u0
PS2
H1(T)≤aNC(u0
PS,u
0
PS).
Remark 5.1. With an analogous calculation, the ellipticity of ||| · |||NC can be
shown for functions in H1
0(Ω) + PS0(T). For sufficient small hmax and v∈H1
0(Ω) +
PS0(T), it holds that
αmin
2∇NCv2
L2(Ω) =αmin
2|v|2
NC ≤ |||v|||2
NC.(5.7)
5.3. Strang lemma. In the case b=0,|||·|||NC is a norm for the space H1
0(Ω)+
PS0(T). Otherwise, |||·|||NC is only positive definite for sufficient fine meshes and the
triangle inequality involves a constant, as shown in the following lemma.
Lemma 5.3 (generalized triangle inequality). Let u, v ∈H1
0(Ω) + PS0(T)and
the mesh-size sufficiently small such that (5.7) holds. Then the constants
Cmax := (αmax +βmaxCdF +γmaxC2
dF)/αmin and C:= Cmax +1/2
satisfy
|||u+v|||NC ≤C(|||u|||NC +|||v|||NC).(5.8)
Proof. The bounds of A,b,andγ, (5.7), (5.5), and the Young inequality yield
|||u+v|||2
NC ≤ |||u|||2
NC +|||v|||2
NC +2αmax|u|NC|v|NC
+βmax(|u|NCvL2(Ω) +|v|NCuL2(Ω))+2γmaxuL2(Ω)vL2(Ω)
≤ |||u|||2
NC +|||v|||2
NC +4Cmax|||u|||NC|||v|||NC
≤(Cmax +1/2)(|||u|||NC +|||v|||NC)2.
Theorem 5.4 (Strang lemma). The Strang lemma for the present situation reads
|||u0−u0
PS|||NC ≤Cinf
vPS∈PS0(T)|||u0−vPS|||NC
+2
αmin
sup
wPS∈PS0(T)
|aNC(u0,w
PS)−FNC(wPS)|
|wPS|NC .
(5.9)
Proof. The proof of the Strang lemma in a standard formulation (see, e.g., [BS08,
Lemma 10.1.9]) uses the triangle inequality of the energy norm aNC(·,·). Instead
we use the generalized triangle inequality (5.8). Furthermore, Theorem 5.2 implies
for bpiecewise constant and small hmax as in (5.6) that
αmin/2|wPS|2
NC ≤ |||wPS|||2
NC.
Downloaded 11/08/17 to 130.149.177.68. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
432 R. ALTMANN AND C. CARSTENSEN
5.4. Approximation error. This subsection is devoted to the analysis of the
approximation error
inf
vPS∈PS0(T)|||u0−vPS|||NC ≤ |||u0−Ju0|||NC
with the interpolation operator Jfrom section 4 and Ju0∈PS0(T). The estimates
(4.5)–(4.6) from Theorem 4.2 on quadrilaterals and (4.1)–(4.2) from Proposition 4.1
on triangles apply to e:= w−Jw with the assumptions on A,b,γand lead to
|||e|||2
Q:=
Q
A∇e·∇edx+
Q
(b·∇e+γe)edx
≤αmax∇e2
L2(Q)+βmax∇eL2(Q)eL2(Q)+γmaxe2
L2(Q)
≤αmax max{C2(θ0),C2(ω0)}h2
Q+βmax(5/3C(ω0)+C(θ0))2h3
Q
+γmax(2C(ω0)+C(θ0)/2)2h4
QD2u02
L2(Q)
=: (C2
app +C2
1hQ+C2
2h2
Q)hQD2u02
L2(Q).
The constants C(θ0)andC(ω0) are as in Theorem 4.2. Hence,
|||u0−Ju0|||NC ≤(Capp +C1h1/2+C2h)hD2u0L2(Ω).(5.10)
5.5. Consistency error. This subsection is devoted to the analysis of the con-
sistency error and is based on the calculations in [PS03] to prove
sup
wPS∈PS0(T)
|aNC(u0,w
PS)−FNC(wPS)|
|wPS|NC ≤√8καmax
√3sinω01+π
π21/2
hD2uL2(Ω).
(5.11)
Throughout this subsection, vjdenotes the restriction of vto a quadrilateral Qj.
5.5.1. Projection R0.Let γj,k denote some interior edge common to Qj,Q
k∈
T. Further, let ·,·γdenote the L2-scalar product on γ.SetP0(E)thespaceof
edgewise constant functions and define the projection
R0:H2(Ω) →P0(E)
by
νj·A∇vj−R0vj,zγ=0
for all z∈P0(γ), where γequals either an interior edge γj,k or an boundary edge.
This requires A∇v∈H(div,Ω) ∩L2+(Ω) for some >0, which is the case for the
exact solution u. The paper [PS03] shows for adjacent quadrilaterals or triangles
Qj,Q
k∈T and wPS ∈PS(T) the orthogonality
R0vj,w
PS|Qjγj,k +R0vk,w
PS|Qkγj,k =0.(5.12)
Downloaded 11/08/17 to 130.149.177.68. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
P1-NONCONFORMING FINITE ELEMENTS 433
α
A
B
P
TEE
Fig. 5.1.Quadrilateral Qdivided into four subtriangles. TEdenotes the triangle with edge E.
5.5.2. Estimate of ν|Q·A∇u|Q−R0u|QL2(∂Q).To shorten the notation,
set
gQ:= ν|Q·A∇u|Q∈L2(∂Q)and gQ,E := ν|E·A∇u|Q∈L2(E).
Then R0u|Qis the edgewise integral mean of gQalong the boundary of Q.Consider
the decomposition of Qinto four triangles as in Figure 5.1 and let gQ,E denote the
integral mean of gQ,E on TE.
Lemma 5.5 (trace inequality I). Let Qbe a quadrilateral with diameter hQand
shape regularity constants ω0and κ, which is divided into four triangles as in Fig-
ure 5.1. Let Edenote some edge of Qwith neighboring triangle TE.Letf∈H1(TE)
satisfy
TEf(x)dx =0.Then,
f2
L2(E)≤8κ
sin ω01
π2+1
πhQ∇f2
L2(TE).(5.13)
Proof. The trace identity (4.3) leads directly to a trace inequality on TE. Together
with the Poincar´e inequality, this implies
f2
L2(E)≤|E|
|TE|fL2(TE)(fL2(TE)+hTE∇fL2(TE))
≤|E|
|TE|h2
TE1
π2+1
π∇f2
L2(TE).
Shape regularity shows for α:= ∠BAP from Figure 5.1 the estimate sinω0/(2κ)≤
sin α.Then|TE|=(|E||AP |sin α)/2 concludes the proof.
This subsubsection concludes with an application of Lemma 5.5 to control ν|Q·
A∇u|Q−R0u|QL2(∂Q). The Pythagoras theorem implies gQ−R0u|QL2(E)≤gQ−
gQ,EL2(E). Therefore,
gQ−R0u|Q2
L2(∂Q)≤
E∈∂Q gQ,E −gQ,E2
L2(E)
(5.13)
≤Ctr hQ
E∈∂Q ∇gQ,E2
L2(TE)
≤Ctr α2
maxhQD2u2
L2(Q).(5.14)
For a quadrilateral Q,Ctr := 8κ/ sin ω0(1/π2+1/π) from Lemma 5.5. For a triangle
set TE:= Qand substitute κby 1.
Downloaded 11/08/17 to 130.149.177.68. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
434 R. ALTMANN AND C. CARSTENSEN
5.5.3. Estimate of |aNC(u0,w
PS)−FNC(wPS)|.Let wPS ∈PS0(T)be
arbitrary. An integration by parts leads with (5.1) to
aNC(u0,w
PS)−FNC(wPS)
=
|T |
j=1
Qj
(A∇u)·∇wPS dx +
Qj
(b·∇u+γu)wPS dx−
Ω
fwPS dx
(5.1)
=
|T |
j=1
∂Qj
wPS (νj·A∇u)ds
(5.12)
=
|T |
j=1νj·A∇uj−R0uj,w
PS|Qj∂Qj
=
|T |
j=1νj·A∇uj−R0uj,w
PS|Qj−mj∂Qj.
This holds for any edgewise constant mj, which is set as the integral mean
mj|E:=
E
wPS|Qjds.
The Cauchy–Schwarz inequality leads to
|aNC(u0,w
PS)−FNC(wPS)|
≤
|T |
j=1
h1/2
Qjνj·A∇uj−R0ujL2(∂Qj)h−1/2
QjwPS|Qj−mjL2(∂Qj)
≤⎛
⎝
|T |
j=1
hQjνj·A∇uj−R0uj2
L2(∂Qj)⎞
⎠
(∗)
1/2⎛
⎝
|T |
j=1
h−1
QjwPS −mj2
L2(∂Qj)⎞
⎠
(∗∗)
1/2
.
Estimate (5.14) allows for
(∗)≤8κα
2
max
sin ω01
π2+1
πhD2u2
L2(Ω).
The subsequent lemma allows for the control of (∗∗).
Lemma 5.6 (trace inequality II). Let Qbe a quadrilateral or triangle with diame-
ter hQand shape regularity constants ω0and κ.Letw∈P1(Q)be affine with integral
mean m|E:=
Ewdsalong any edge E∈E(Q). Then it holds that
w−m2
L2(∂Q)≤κ
3sinω0
hQ∇w2
L2(Q).
Downloaded 11/08/17 to 130.149.177.68. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
P1-NONCONFORMING FINITE ELEMENTS 435
Proof. Since ∇wis constant on Q, it holds that
w−m2
L2(∂Q)=
E∈E(Q)
E|x−mid(E)|2∂w
∂s 2
ds
≤1
12 max
E∈E(Q)h2
E∇w2
L2(∂Q)
=1
12 max
E∈E(Q)h2
E|∂Q|
|Q|∇w2
L2(Q).
Shape regularity results in
max
E∈E(Q)hE|∂Q|≤4κ|Q|
sin ω0
.
Lemma 5.6 implies
(∗∗)≤
j
κ
3sinω0∇wPS2
L2(Qj)=κ
3sinω0|wPS|2
NC.
The combination of the aforementioned estimates of (∗)–(∗∗) verifies
|aNC(u0,w
PS)−FNC(wPS)|≤√8καmax
√3sinω01+π
π21/2
hD2uL2(Ω) |wPS|NC.
Since wPS ∈PS0(T) is arbitrary, this proves (5.11).
5.6. Result. In the case b=0andbpiecewise constant, we consider hmax to
be as small as in (5.6). Then, the Strang lemma (5.9), the approximation error (5.10),
and the consistency error (5.11) lead to the a priori estimate
|||u0−u0
PS|||NC ≤C(CapphD2u0L2(Ω) +CconhD2uL2(Ω)
+(C1h1/2+C2h)hD2u0L2(Ω)).
The constant Cis from Lemma 5.3, while Capp,C
1,C
2are from section 5.4 and
Ccon := 4κα
max
√3αmin sin ω01+π
π21/2
.
The rest of this section is devoted to the discussion of |||u−uPS|||NC.
Approximation of Dirichlet boundary conditions. From section 5.4 we obtain the
constants for estimates of the form uD−JuDL2(Ω) h2D2uDL2(Ω),∇NC(uD−
JuD)L2(Ω) hD2uDL2(Ω) as well as
|||uD−JuD|||NC ≤(Capp +C1h1/2+C2h)hD2uDL2(Ω).
Approximation of lower-order terms. The discrete Friedrichs inequality (5.5) yields a
bound of u0−u0
PS in the L2-norm,
u0−u0
PSL2(Ω) ≤CdF∇NC(u0−u0
PS)L2(Ω) =: CdF|u0−u0
PS|NC.
Downloaded 11/08/17 to 130.149.177.68. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
436 R. ALTMANN AND C. CARSTENSEN
To bound the error in the H1-seminorm, let ˜u0∈PS0(T) denote the best approxima-
tion of u0in PS0(T). Then, (5.7) implies
∇NC(u0−u0
PS)L2(Ω) ≤∇
NC(u0−˜u0)L2(Ω) +∇NC(u0
PS −˜u0)L2(Ω)
≤∇
NC(u0−Ju0)L2(Ω) +2
αmin |||u0
PS −˜u0|||NC.
The best-approximation property of ˜u0leads to
|||u0
PS −˜u0|||2
NC =aNC(u0
PS −u0,u
0
PS −˜u0)=FNC(u0
PS −˜u0)−aNC(u0,u
0
PS −˜u0),
i.e., the consistency error from section 5.5. This results in
∇NC(u0−u0
PS)L2(Ω) ≤Capp
√αmax hD2u0L2(Ω) +CconhD2uL2(Ω).
Estimation of complete error. Recall that the triangle inequality is not valid for
||| · |||NC. Also, the generalized triangle inequality from Lemma 5.3 cannot be used to
combine the two estimates since uD/∈H1
0(Ω) + PS0(T). Nevertheless,
|||u−uPS|||2
NC =|||uD−JuD|||2
NC +|||u0−u0
PS|||2
NC
+aNC(uD−JuD,u
0−u0
PS)+aNC(u0−u0
PS,u
D−JuD)
≤ |||uD−JuD|||2
NC +|||u0−u0
PS|||2
NC
+2αmax|uD−JuD|NC|u0−u0
PS|NC
+βmax(|uD−JuD|NCu0−u0
PSL2(Ω)
+|u0−u0
PS|NCuD−JuDL2(Ω))
+2γmaxuD−JuDL2(Ω)u0−u0
PSL2(Ω).
The combined calculations from above result in an a priori estimate with explicit
constants of the form
|||u−uPS|||NC hD2uL2(Ω) +hD2uDL2(Ω) +hD2u0L2(Ω).
Remark 5.2 (example from the introduction). Consider the homogeneous Poisson
model problem (1.1) from the introduction with a uniform triangulation of Ω = (0,1)2
into squares and right isosceles triangles of size h. This gives in particular αmin =
αmax =1,β
max =0,γ
max =0,κ =1,ω
0=θ0=π/2. Thus, the approximation error
and the consistency error involve the constants
Capp =C(π/2) ≤0.68,C
con =4/π (1 + π)/3≤1.5.
Because of b=0, we can use the Strang lemma in its standard formulation and
obtain together with the convexity of Ω,
|||u−uPS|||NC ≤(Capp +Ccon/√2)hD2uL2(Ω) ≤1.75hfL2(Ω).
6. Numerical experiment. The computer experiment of this section is beyond
the analysis of this paper in that the exact solution does not belong to H2(Ω) and
the anisotropic mesh-refinement leads to degenerate constants as κ→∞. Neverthe-
less, numerical evidence underlines that adaptivity and even anisotropy improve the
convergence rate significantly. Consider the Dirichlet problem
−Δu=0inΩ and u=uDon ∂Ω
Downloaded 11/08/17 to 130.149.177.68. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
P1-NONCONFORMING FINITE ELEMENTS 437
Fig. 6.1.Triangulations of a Z-shape domain: (left) T0, (middle) uniform refined mesh, and
(right) graded mesh.
101102103104
10−2
10−1
Number De
g
rees of Freedom
Energyerror
uniform
graded β= 1.7
adaptive
graded β=2.75
Fig. 6.2.Plot of the energy error for uniform, graded, and adaptive refinement strategies.
on the Z-shape Ω := {x∈(−1,1)2|0<arg x<7π/4}from Figure 6.1. In polar
coordinates the exact solution and its trace uD=u|∂Ωread
u(r, ϕ)=r4/7sin(4ϕ/7)
with a typical corner singularity at the origin. The interpolation error estimate of
Theorem 4.2 leads to linear convergence for all element domains with positive distance
to the reentering corner at the origin. A standard argument for the singular part of
the solution leads to the interpolation estimate
u−JuL2(Q)h4/7
Q.
It is expected that the overall final error estimate for this singular solution leads to
|||u−uPS|||NC h4/7
max.
This is in fact observed in the numerical experiment for uniform mesh-refinement
which results in an empirical convergence rate 0.28 ≈1
24/7 (two space dimensions);
see Figure 6.2. Graded meshes generate anisotropic elements and refine the mesh
near the origin; see the right side of Figure 6.1. A graded mesh of a unit square
into (N−1)2rectangles is characterized by the sequence 0,(1
N)β,(2
N)β,...,1 with
parameter β≥1.
The error in the energy norm of the discrete solution using Park–Sheen elements
with graded meshes results in the empirical convergence rate 0.44 for β=1.7and
Downloaded 11/08/17 to 130.149.177.68. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.
438 R. ALTMANN AND C. CARSTENSEN
0.49 for β=2.75; cf. Figure 6.2. Also, the adaptive algorithm gains the convergence
rate 0.49, which is near the optimal convergence rate of 0.5 for first-order methods.
The marking strategy involves the purely heuristic (but optimal for Crouzeix–Raviart
elements [Rab10]) estimator
η2(Q):=
E∈E(Q)
hE[∂uPS/∂s]E2
L2(E)
with jump [·]E. The marking process uses the D¨orfler criterion [D¨or96] and marks a
minimal number of elements M⊂T such that
η(M):=⎛
⎝
Q∈M
η2(Q)⎞
⎠
1/2
≥1
4η(T).
The adaptive finite element cycle then reads SOLVE →ESTIMATE →MARK →
REFINE.
Remark 6.1 (smooth solutions). Unreported numerical examples for smooth
solutions show the optimal convergence rates with (almost) quasi-uniform meshes in
agreement with the theoretical results of this paper.
REFERENCES
[BM08] R. Becker and S. Mao,An optimally convergent adaptive mixed finite element method,
Numer. Math., 111 (2008), pp. 35–54.
[BS08] S. C. Brenner and L. R. Scott,The Mathematical Theory of Finite Element Methods,
Texts in Appl. Math. 15, 3rd ed., Springer, New York, 2008.
[CGR11] C. Carstensen, J. Gedicke, and D. Rim,Explicit error estimates for Courant,
Crouzeix-Raviart and Raviart-Thomas finite element methods, J. Comput. Math.,
submitted, 2011.
[Cia78] P. G. Ciarlet,The Finite Element Method for Elliptic Problems, North-Holland, Am-
sterdam, 1978.
[CR73] M. Crouzeix and P.-A. Raviart,Conforming and nonconforming finite element meth-
ods for solving the stationary Stokes equations, Math. Anal. Numer., 7 (1973),
pp. 33–76.
[D¨or96] W. D¨
orfler,A convergent adaptive algorithm for Poisson’s equation,SIAMJ.Numer.
Anal., 33 (1996), pp. 1106–1124.
[Gri85] P. Grisvard,Elliptic Problems in Nonsmooth Domains, Monogr. Stud. Math. 24, Pit-
man, Boston, MA, 1985.
[Par03] C. Park,A Study on Locking Phenomena in Finite Element Computations,Ph.D.thesis,
Seoul National University, 2003.
[PS03] C. Park and D. Sheen,P1-nonconforming quadrilateral finite element methods for
second-order elliptic problems, SIAM J. Numer. Anal., 41 (2003), pp. 624–640.
[PW60] L. E. Payne and H. F. Weinberger,An optimal Poincar´e inequality for convex do-
mains, Arch. Ration. Mech. Anal., 5 (1960), pp. 286–292.
[Rab10] H. Rabus,A natural adaptive nonconforming FEM of quasi-optimal complexity, Comput.
Methods Appl. Math., 10 (2010), pp. 315–325.
Downloaded 11/08/17 to 130.149.177.68. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php
