COMPUTATIONAL METHODS IN APPLIED MATHEMATICS, Vol.6(2006), No.2, pp.154–177
c
2006 Institute of Mathematics of the National Academy of Sciences of Belarus
SUPRACONVERGENCE OF A FINITE DIFFERENCE
SCHEME FOR ELLIPTIC BOUNDARY VALUE PROBLEMS
OF THE THIRD KIND IN FRACTIONAL ORDER SOBOLEV
SPACES
E. EMMRICH1and R.D.GRIGORIEFF
1
Abstract — In this paper, we study the convergence of the finite difference discretiza-
tion of a second order elliptic equation with variable coefficients subject to general
boundary conditions. We prove that the scheme exhibits the phenomenon of supra-
convergence on nonuniform grids, i.e., although the truncation error is in general of
the first order alone, one has second order convergence. More precisely, for s∈(1/2,2]
the optimal order O(hs)-convergence of the finite difference solution and its gradient
appears if the exact solution is in the Sobolev — Slobodetskij space H1+s(Ω). All error
estimates are strictly local.
Another result of the paper is a close relationship between finite difference scheme
and linear finite element methods combined with a special kind of quadrature. As
a consequence, the results of the paper can be viewed as the introduction of a fully
discrete finite element method for which the gradient is superclose, i.e., the error of
the approximate gradient with respect to the linear interpolation of the solution uis
of the second order if u∈H3(Ω). A numerical example is given.
2000 Mathematics Subject Classification: 65N06, 65N12, 65N15, 65N30.
Keywords: nonuniform grid, elliptic finite difference scheme, stability, supraconver-
gence, supercloseness of gradient, fully discrete linear FEM.
1. Introduction
We consider the discretization of the differential equation
Au := −(aux)x−(buy)y+cu =fin Ω ⊂R2(1.1)
subject to the boundary conditions of the third kind
Bu := auxηx+buyηy+αu =ψon Γ := ∂Ω (1.2)
by finite differences defined on agenerally nonuniform rectangular grid ΩHon the domain
Ω, which is assumed to be a union of rectangles. Here ηxand ηydenote the components of
the outer normal on Γ.
The main aim of the paper is to study the behaviour of the finite difference solution for
a sequence of variable grids ΩH,H∈Λ,with the maximal mesh size Hmax converging to
1Technische Universit¨at Berlin, Institut f¨ur Mathematik, Straße des 17. Juni 135, 10623 Berlin, Germany.
Bereitgestellt von | Technische Universität Berlin
Angemeldet
Heruntergeladen am | 15.10.18 15:35
Supraconvergence of a finite difference scheme 155
zero. The grids are assumed to be quasi-uniform except for the cases of s=1ands=2,
where no restriction is placed on the nonuniformity. Under these circumstances the scheme
is, in general, only first order consistent. Our aim is to show that nevertheless the finite
difference solution and its gradient are one order more accurate. This property of the FDM
is usually called supraconvergence (see [24]). More precisely, we prove optimal convergence
rates O(hs),s∈(1/2,2],of the scheme for weak solutions ubelonging to the fractional order
Sobolev — Slobodetskij space H1+s(Ω). It is shown that the gradient is also approximated
with the same order. The error estimates are strictly local as is desirable when working with
nonuniform grids.
Supraconvergence results for two-dimensional elliptic problems were obtained by several
authors. Some basic studies can be found in [29]. In [33] the Laplacian in a square domain
subject to Neumann boundary conditions and in [5] a general second order elliptic equation
in a polygonal domain subject to Dirichlet boundary conditions were considered. In both
papers the solution was assumed to be smooth, i.e., that ubelongs to C4(Ω).
It is known from the finite elements that the second order convergence in the L2-norm has
already been obtained for solutions u∈H3(Ω), which is optimal with respect to the smooth-
ness assumed. The aim of many papers was to establish also for finite difference schemes
the convergence rates that are optimal with respect to the smoothness of the solution, even
in the case of a less smooth solution u∈Ht(Ω) with t<3. Major steps in this direction
can be found in [20], [23] and [38], where finite difference schemes on uniform meshes for
different types of (positive definite) elliptic equations in a rectangular domain subject to
Dirichlet boundary conditions are considered. Third kind boundary conditions are analyzed
in [21], where apart from the logarithmic factor the second order convergence was proved for
u∈H3(Ω). A weaker typical smoothness assumption is u∈H1+s(Ω) with s>0 ensuring
that the pointwise restriction of uon the mesh makes sense, but even s>−1/2wascon-
sidered in [28]. The convergence is usually studied in discrete analogues of Sobolev spaces.
Relying on another method of analysis, domains with a curved boundary are admitted in
[11]. Other authors, see [16] and [22], concentrate on handling equations with nonsmooth co-
efficients or on obtaining convergence in discrete Lp-norms (see [38]). An excellent overview
has recently been given in [16] and also in [17], where the analysis can be found in detail. In
[7] the supraconvergence was analyzed based on the maximum principle.
Finite differences on nonuniform meshes for the Laplacian in a square with solutions
u∈H1+s(Ω) are considered in [40] for s= 2 and in [3] and [19] for s∈[1,2]. The idea in
these papers is to add a correction to the standard finite difference scheme on uniform grids
that makes the scheme second order accurate also on nonuniform meshes. This disagrees with
the result of the present paper that no correction is needed to prove the same convergence
order as on uniform meshes, i.e., supraconvergence takes place. Our kind of analysis works
fine in the case of Dirichlet boundary conditions (see the forthcoming paper [6]). We consider
here the more complicated boundary conditions of the third kind, which were studied in [3]
for s= 2 on nonuniform meshes in rectangular domains. Also mixed derivative terms could
be included in the differential operator A. For ease of presentation we restrict ourselves to
the present simpler case. Problems with mixed derivatives were studied with the aid of the
maximum principle for smooth solutions uin [34].
A one-dimensional version of the results obtained in this paper was published in [1]. In
the one-dimensional case, several authors studied the supraconvergence (see [8–10,15,24,32,
37]). Also for hyperbolic and parabolic equations the supraconvergence was considered (see
[2,18,29,39,42]).
Bereitgestellt von | Technische Universität Berlin
Angemeldet
Heruntergeladen am | 15.10.18 15:35
156 E. Emmrich and R. D. Grigorieff
In the proofs we prefer to work with the usual norms in the Sobolev — Slobodetskij
spaces thus avoiding the uncomfortable discrete versions of these norms. Also, we find it
helpful in the analysis to establish equivalence with the linear finite element method on the
standard triangulation THassociated with the rectangular grid ΩHcombined with a special
kind of quadrature. In fact, this relation opens up the possibility of expressing the discretized
boundary conditions, always a problem for finite difference methods if conditions of the third
kind are involved, in a reasonable form. As a consequence, the second order convergence of
the gradient in the finite difference scheme is nothing but the supercloseness ([36], [41, p. 80])
of the gradient of the fully discrete FEM approximation, i.e., it is second order accurate to
the linear interpolation QHuon THof the exact solution u. Several recovery techniques for
the gradient are based on the supercloseness property (see [12–14,25,26, 30,43,44] and the
references in [27]). In the supercloseness results involved in these papers the meshes are
either completely uniform or a smooth transformation of a uniform mesh when working on
nonuniform meshes. We want to point out the significant difference in the behaviour of the
scheme on uniform and nonuniforms grids, which can be well seen from the finite difference
presentation: while on the former grids the truncation error is of the second order and
smoothly varying from grid point to grid point, it is of the first order and strongly oscillating
on the latter. In most cases the Dirichlet conditions were considered, but in [13] and [36] also
boundary conditions of the third kind are admitted. The order of the supercloseness in the
latter case is then reduced to O(h3/2). In [30], the finite element scheme is fully discrete. It is
obtained with the aid of a second order accurate quadrature formula, while our quadrature
formulas are only of the first order. Recently, the supercloseness has been studied in [31] for
nonconforming finite elements.
The paper is organized as follows. In Section 2 we describe the finite difference method for
problem (1.1), (1.2). In the next section an equivalent linear FEM with quadrature for which
stability is easy to obtain is introduced. In Section 4 the crucial estimate for the truncation
error is proved for the low regularity case s∈(1/2,1],from which, together with the stability,
the first convergence result in Theorem 4.1 follows: the H1-norm of the discretization error
QH(u−uH)isoforderO(Hs
max)provideduis in the Sobolev — Slobodetskij space H1+s(Ω).
Our supraconvergence result, i.e., that the same convergence result holds also for s∈(1,2],
is stated in Theorem 5.1 and proved in Section 5. In this section it is also shown that in
general supraconvergence does not take place in the case of the right-hand side f∈H1(Ω)
in (1.1) if pointwise restriction on the grid ΩHis used in place of the integral average (2.3)
below. But the pointwise restriction can be taken if f∈Hs(Ω),s>1(seeRemark5.4).In
Section 6 we give some numerical results. Some notations are given in an appendix.
2. The finite difference scheme
In this section, we set up the discretization of (1.1) and (1.2). We first introduce a generally
nonequidistant rectangular grid ΩH.Leth={hj}j∈Zand k={k}∈Zbe two sequences of
mesh sizes, i.e., of positive numbers. We define the grid
Rx
h={xj∈R:xj+1 =xj+hj,j∈Z}
with x0∈Rgiven and the corresponding grid Ry
kwith the mesh size vector kin place of h
and y0in place of x0. Points in the middle between two adjacent grid points are denoted
by xj+1/2:= xj+hj/2andxj−1/2:= xj−hj−1/2(= x(j−1)+1/2) and, respectively, in the
Bereitgestellt von | Technische Universität Berlin
Angemeldet
Heruntergeladen am | 15.10.18 15:35
Supraconvergence of a finite difference scheme 157
y-direction. Let RHbe the two-dimensional rectangular grid
RH=Rx
h×Ry
k⊂R2
and define ΩH:= Ω ∩RH,ΓH:= Γ ∩RH,ΩH:= Ω∩RH(= ΩH∪ΓH).The grid ΩHis
assumed to satisfy the condition that the vertices of Ω are in ΓH.
For the formulation of the finite difference approximation we use the centered finite
difference quotients
(δ(1/2)
xv)j, := vj+1/2, −vj−1/2,
xj+1/2−xj−1/2
and (δ(1/2)
xv)j+1/2, := vj+1, −vj,
xj+1 −xj
.
Here vj, := v(xj,y
)andvj+1/2, := v(xj+1/2,y
) for the functions vdefined on Ω. The
operators also apply for the grid functions vH∈WH, the space of functions defined on ΩH,
if the final result makes sense. The definition of δ(1/2)
yetc. is analogous. If it is convenient
we also use the notation vP:= vH(P)forP∈ΩH. Then we approximate the differential
operator (1.1) by
AHuH:= −δ(1/2)
x(aδ(1/2)
xuH)−δ(1/2)
y(bδ(1/2)
yuH)+cuH=fHin ΩH.(2.1)
We assume that the coefficients of Abelong at least to C(Ω) to ensure that AHuHis well-
defined. We also assume that at least α, ψ ∈C(Γ) and f∈L2(Ω). Further assumptions will
be imposed later. The right-hand side fHin (2.1) is obtained by averaging fin the following
way: for a point P=(xj,y
)∈ΩHlet xP:= xj,y
P:= yand
P:= (xj−1/2,x
j+1/2)×(y−1/2,y
+1/2)∩Ω,ω
P:= |P|,(2.2)
where |P|denotes the measure of P.Then
fP:= 1
ωP
P
f(x, y)dV. (2.3)
In Section 5 we will also consider the possibility of taking fHto be the pointwise restriction
of fon the grid ΩH. The pointwise restriction of the function von the grid ΩHwill be
denoted by RHv. If it is clear from the context, we often write only vin place of RHv.
The right-hand side ψof the boundary condition is simply approximated by its restriction
to the points in ΓH.Inthecases∈(1/2,1],we can also take (see Remark 4.2)
ψP:= 1
σP
ΓP
ψ(x, y)dσ, P ∈ΓH,(2.4)
where
σP:= |ΓP|with ΓP:= (xj−1/2,x
j+1/2)×(y−1/2,y
+1/2)∩∂ΩforP=(xj,y
)∈ΓH.(2.5)
We come to the discretization of the boundary conditions, where we distinguish three
different types of boundary points: inner points on straight segments, convex and re-entrant
corners of ΓH. The following discretizations can be systematically derived from the varia-
tional formulation (3.6) in Section 3.
Bereitgestellt von | Technische Universität Berlin
Angemeldet
Heruntergeladen am | 15.10.18 15:35
158 E. Emmrich and R. D. Grigorieff
We start with the point (xj,y
)∈ΓHon the interior of the vertical segment with Ω lying
locally to the right. The discretization is then
−(aδ(1/2)
xuH)j+1/2, −hj
2δ(1/2)
y(bδ(1/2)
yuH)j, +hj
2(cuH)j, +(αuH)j, =ψj, +hj
2fj,.(2.6)
Next we consider the convex corner (xj,y
) with Ω lying locally to the right and above.
The discretization is in this case given by
−k
hj+k
(aδ(1/2)
xuH)j+1/2, −hj
hj+k
(bδ(1/2)
yuH)j,+1/2+hjk
2(hj+k)(cuH)j, +(αuH)j, =
ψj, +hjk
2(hj+k)fj,.(2.7)
Finally, let (xj,y
) be a re-entrant corner with Ω lying locally to the left and below, which
leads to
k
hj+k
(aδ(1/2)
xuH)j−1/2, −k−1(hj+hj−1)
2(hj+k)δ(1/2)
x(aδ(1/2)
xuH)j, +hj
hj+k
(bδ(1/2)
yuH)j,−1/2−
hj−1(k+k−1)
2(hj+k)δ(1/2)
y(bδ(1/2)
yuH)j, +hj−1k−1+hjk−1+hj−1k
2(hj+k)(cuH)j, +(αuH)j, =
ψj, +hj−1k−1+hjk−1+hj−1k
2(hj+k)fj,.(2.8)
The discretization in the remaining points has a corresponding form, we refrain from writing
them down for all possible geometric situations. We refer to them altogether as “discrete
boundary conditions”. These discretizations can be rewritten in a more familiar form by
introducing auxiliary gridpoints. For example, in the case of (2.6) let uj−1, be an auxiliary
variable in an auxiliary gridpoint (xj−hj,y
). If a=1,then (2.6) is equivalent to the
equations
(AHuH)j, =fj, and (uH)j+1, −(uH)j−1,
2hj
+(αuH)j, =ψj,.
Here, according to the introduction of the auxiliary gridpoint, the coordinate xj−1/2has to
be replaced by xj−hj/2inAH.
3. Equivalent fully discrete Galerkin method
Our analysis of the finite difference method is based on the observation that equations (2.1)
and together with the discrete boundary conditions (see (2.6) – (2.8)) can be equivalently
written as a linear finite element method with quadrature which is also of interest in its own.
We start with the common variational formulation of (1.1), (1.2). By (·,·)0and ·,·0we
denote the standard inner product on L2(Ω) and L2(Γ), respectively. We also use ·sand
|·|s, or more explicitly ·s,Ωand |·|s,Ω, for the usual norm and seminorm, respectively, in
the Sobolev — Slobodetskij space Hs(Ω) for s⩾0. Let us recall that for σ∈(0,1)
|v|σ,Ω:=
Ω×Ω
|v(x, y)−v(ξ,η)|2
|(x, y)−(ξ,η)|2+2σdV dV 1/2
(3.1)
Bereitgestellt von | Technische Universität Berlin
Angemeldet
Heruntergeladen am | 15.10.18 15:35
Supraconvergence of a finite difference scheme 159
and for positive s=[s]+σwith σ∈(0,1)
|v|s,Ω:=
|α|=[s]|Dαv|2
σ,Ω1/2
,vs,Ω:= (v2
[s],Ω+|v|2
s,Ω)1/2.(3.2)
We will need the Sobolev — Slobodetskij spaces Hs(Γ), too. In this case, some care has to
be taken if s>1 since Γ is only Lipschitz. In our situation we circumvent this difficulty by
defining the norm simply as the (Euclidean) sum of its well-defined Hs-norms extended over
the (disjoint) straight sections of Γ. By Wt
q(Ω) with t∈N0and q⩾1 we denote the usual
LqSobolev space with the seminorm and norm
|v|t,q :=
|α|=t
Ω
|Dαv(x, y)|qdV 1/q
,vt,q := t
k=0 |v|q
k,q1/q
,
respectively, understanding the case q=∞in the usual way.
The variational formulation of our problem is:
find u∈H1(Ω) such that A(u, v)=(f,v)0+ψ,v0for v∈H1(Ω),(3.3)
where A(·,·) is the sesquilinear form defined by
A(v,w)=(avx,w
x)0+(bvy,w
y)0+(cv, w)0+αv, w0for v,w ∈H1(Ω).(3.4)
We make the general assumption that the operator Ain (1.1) is uniformly elliptic in Ω and,
for simplicity, that c⩾0inΩ,α⩾0 on Γ and, additionally, that not both cand αvanish
identically. Recall that the coefficients a, b, c and αare assumed to be at least continuous.
Then the homogeneous problem (3.3), i.e., with f=0andψ= 0, has only the solution
u=0.
Next we introduce discrete analogues of the inner products (·,·)0and ·,·0by
(vH,w
H)H:=
P∈ΩH
ωP(vH)P(wH)Pfor vH,w
H∈WH(3.5)
and
ϕH,χ
HH:=
P∈ΓH
σP(ϕH)P(χH)P
for the grid functions ϕH,χ
Hon ΓHwith ωPfrom (2.2) and σPfrom (2.5). The fully discrete
variational problem has the form
find uH∈WHsuch that AH(uH,v
H)=(fH,v
H)H+ψH,v
HH,v
H∈WH.(3.6)
Here AH(·,·) is a sesquilinear form which we are now going to define. Let THbe a triangu-
lation of Ω using the set ΩHas vertices. The specific choice of THdoes not matter for the
subsequent results to hold. By QHvHwe denote the continuous piecewise linear interpolation
of vHwith respect to TH.ThenAH(·,·)isgivenasthesum
AH=aH+bH+cH+γH(3.7)
of sesquilinear forms corresponding to the different terms in the continuous variational prob-
lem (3.4). They are all constructed in a similar way on the basis of linear triangular finite
elements combined with an individual quadrature for each term.
Bereitgestellt von | Technische Universität Berlin
Angemeldet
Heruntergeladen am | 15.10.18 15:35
160 E. Emmrich and R. D. Grigorieff
Let ∆ ∈TH. We define a∆,x to be the value of the coefficient aat the midpoint of the
edge of ∆ parallel to the x-axis. Then let
aH(vH,w
H):=
∆∈TH
a∆,x
∆
(QHvH)x(QHwH)xdV for vH,w
H∈WH.(3.8)
Similarly, let b∆,y denote the value of the coefficient bat the midpoint of the side of ∆ parallel
to the y-axis and
bH(vH,w
H):=
∆∈TH
b∆,y
∆
(QHvH)y(QHwH)ydV for vH,w
H∈WH.(3.9)
Finally,
cH(vH,w
H):=(cvH,w
H)Hfor vH,w
H∈WH.(3.10)
The boundary term in (3.4) is simply discretized by
γH(vH,w
H):=αvH,w
HHfor vH,w
H∈WH.(3.11)
The finite difference equations belonging to (3.6) are obtained by choosing grid functions
vHthat vanish at all but one grid point in ΩH. In this way the following proposition is seen
to hold.
Proposition 3.1. Let the sesquilinear form AH(·,·)and the operator AHbe defined by
(3.7) and (2.1), respectively. Then
AH(vH,w
H)=(AHvH,w
H)
for all vH,wH∈WHwith wH=0on ΓH. Moreover, the finite difference equations (2.1)
together with the discrete boundary conditions (see (2.6) –(2.8)) are equivalent to the discrete
variational problem (3.6).
We now turn to the stability of (3.6) and consider an infinite sequence of grids RHsuch
that the maximal mesh size Hmax := max{hj,k
:j, ∈Z}tends to zero. By Λ we denote
the sequence of mesh size vectors. The sequence of grids ΩH,H ∈Λ, is called quasi-uniform
if all possible quotients of mesh sizes in ΩHare bounded uniformly for H∈Λ.
From the ellipticity of the variational problem (3.3), also taking into account the conti-
nuity and the sign assumptions of the coefficients, the following proposition is easily seen to
hold.
Proposition 3.2. The following inequality holds for all vH∈WHand Hmax small
enough:
QHvH1⩽Csup
0=wH∈WH
|AH(vH,w
H)|
QHwH1
.(3.12)
HereandinthefollowingCdenotes a generic constant independent of significant quan-
tities.
Bereitgestellt von | Technische Universität Berlin
Angemeldet
Heruntergeladen am | 15.10.18 15:35
Supraconvergence of a finite difference scheme 161
4. Convergence: case s∈(1/2,1]
Our error estimates are based on the inverse stability inequality (3.12) in Proposition 3.2
applied to the global discretization error RHu−uHin place of vH,whereRHu∈WHdenotes
the pointwise restriction of uto the grid ΩH.Hence, since uHsolves (3.6), we have to estimate
the truncation error
τH:= AH(RHu, vH)−(fH,v
H)H−ψH,v
HH(4.1)
in terms of QHvH1. This will be done in this section for the case of a solution uof low
regularity.
To simplify the presentation, we introduce for P∈Ωx
1/2:= {(xj+1/2,y
)∈Ω}the coordi-
nates xP:= xj+1/2,yP:= y, the step size hP:= hj,and the line segments, rectangles and
differences
SP:= {xj+1/2}×(y−1/2,y
+1/2)∩Ω,P:= (xj,x
j+1)×(y−1/2,y
+1/2)∩Ω,
(∆xvH)P:= vj+1, −vj,.(4.2)
For the point set Ωy
1/2:= {(xj,y
+1/2)∈Ω}the corresponding quantities are defined. Note
that the above symbols will be differently defined in the sequel depending on where the point
Pis situated.
Our starting point is the quantity (fH,v
H)Hin (4.1). According to the definition of fH
in (2.3), we have
(fH,v
H)H=
P∈ΩH
P
(Au)(x, y)dV (vH)P.(4.3)
We transform the quantities in (4.3) containing derivatives.
Lemma 4.1. The following identity holds:
P∈ΩH
P
(aux)xdV (vH)P=−
P∈Ωx
1/2
SP
auxdy(∆xvH)P+
P∈ΓH
ΓP
auxηxdσ(vH)P.(4.4)
Proof. Integrating by parts, we obtain
P∈ΩH
P
(aux)xdV (vH)P=
P∈ΩH
∂P
auxηxdσ (vH)P.
Note that ηxtakes the values 1, −1,and 0 on ∂P. Separating the integrals extended over
sections of Γ from the sum and then summing by parts leads to (4.4).
Lemma 4.2. Let s∈(1/2,1),u∈H1+s(Ω),a∈W1
2/(1−s)(Ω) and assume that {ΩH}H∈Λ
is quasi-uniform. Then the following estimate holds for all P∈Ωx
1/2:
SP
auxdy−|SP|(aδ(1/2)
xu)P
⩽C|SP|suxs, P+uys, P⩽C(diam P)su1+s, P(4.5)
Proof. Denoting the left-hand side of (4.5) by |FP|,we obtain
|FP|⩽aP
SP(δ(1/2)
xu)P−uxdy+
SP
(aPux−auxdy.(4.6)
Bereitgestellt von | Technische Universität Berlin
Angemeldet
Heruntergeladen am | 15.10.18 15:35
162 E. Emmrich and R. D. Grigorieff
For the given range of sthe imbeddings Hs(Ω) →L2(SP), H1+s(Ω) →C(Ω) and W1
2/(1−s)(Ω)
→C(Ω) are continuous (see [35, Th. 3.37 with Th. 3.30 and Th. 3.26 with Th. 3.16 and
Th. A.4]). Hence
F1(u):=aP
SP(δ(1/2)
xu)P−uxdy (4.7)
is a bounded linear functional on H1+s(Ω). It vanishes for the functions 1,x,y. We transform
Pto the unit square, apply the generalized Bramble — Hilbert Lemma for the fractional
order spaces (see [4, Th. 6.1]), and obtain after transforming back
|F1(u)|⩽Csup
Ω|a(x, y)||SP|
hP
max{|SP|,h
P}1
hP|SP|max{|SP|1+s,h
1+s
P}|u|1+s, P.
Since the grids are quasi-uniform, F1(u) can be estimated by the right-hand side of (4.5).
We will now estimate the second member of the right-hand side of (4.6). Fix ux∈Hs(Ω)
and let
F2(a):=
SP
(aPux−aux)dy =
SPaP−a(xP,y)ux(xP,y)dy.
For brevity we set r:= 2/(1 −s). The linear form F2(a) is bounded for a∈W1
r(Ω) and
vanishes for a= 1. With the aid of the Bramble — Hilbert Lemma we can derive in a similar
way as before the bound
|F2(a)|⩽C|SP|(hr
P+|SP|r)1
hP|SP|1/r
|a|W1
r(P)×
1
hP|SP|+1
(hP|SP|)2max{h2+2s
P,|SP|2+2s}1/2
uxs, P.
Thus also F2can be estimated as desired and the proof is complete.
Remark 4.1. The assertion of Lemma 4.2 holds true if the norm of uxover the rectangle
Pis replaced by the norm over the part of Plying to the left or the right of the segment
SP, respectively. This is immediate from the proof. In the proof of Theorem 4.1 we will
make use of this observation. A corresponding remark applies to the following Lemmas 4.3
and 4.4.
Lemma 4.3. Let u∈H2(Ω) and a∈W1
∞(Ω). Then the following estimate holds for
P∈Ωx
1/2:
SP
auxdy −|SP|(aδ(1/2)
xu)P⩽Cdiam P|SP|
hP1/2
ux1,P.(4.8)
Proof. Our starting point is again (4.6) and we use F1and F2as defined in the proof of
Lemma 4.2. For almost all y∈SP,P =(xj+1/2,y
), we obtain by virtue of the Bramble —
Hilbert Lemma
aP(δ(1/2)
xu)P−ux⩽Csup
Ω|a(x, y)|
xj+1
xj
|uxx(x, y)|dx
Bereitgestellt von | Technische Universität Berlin
Angemeldet
Heruntergeladen am | 15.10.18 15:35
Supraconvergence of a finite difference scheme 163
and integration with respect to ytogether with the Schwarz inequality leads to the bound
in (4.8) for |F1|. Similarly, since for each fixed ux∈H1(Ω) the linear form F2is bounded for
a∈W1
∞(Ω),the Bramble — Hilbert Lemma furnishes
|F2|⩽C|SP|(|SP|+hP)max{axL∞(P),ayL∞(P)}(|SP|hP)−1/2ux1,P,
which can be estimated as desired.
Lemma 4.4. Let s∈(1/2,1],u∈H1+s(Ω) and a∈W1
2/(1−s)(Ω).Fors∈(1/2,1)
assume additionally that the sequence of grids {ΩH}H∈Λis quasi-uniform. Then for all
vH∈WH
P∈Ωx
1/2
SP
auxdy (∆xvH)P−aH(RHu, vH)
⩽C
P∈Ωx
1/2
(diam P)2su2
1+s, P1/2
QHvH1⩽
CH
s
maxu1+sQHvH1.(4.9)
Proof. A short calculation shows that the sesquilinear form aHfrom (3.8) permits the
representation
aH(RHu, vH)=
P∈Ωx
1/2
|SP|(aδ(1/2)
xu)P(∆xvH)P.(4.10)
Since, with FPfrom the proof of Lemma 4.2,
P∈Ωx
1/2
FP(∆xvH)P
2
⩽
P∈Ωx
1/2
hP
|SP||FP|2
P∈Ωx
1/2
hP|SP||(δ(1/2)
xvH)P|2
the first inequality follows from Lemma 4.2 if s∈(1/2,1) and from Lemma 4.3 if s=1.The
second one is a consequence of diam P⩽√2Hmax and P∈Ωx
1/2u2
1+s, P⩽u2
1+s.
Lemma 4.5. Let s∈(1/2,1],u∈H1+s(Ω) and c∈W1
2/(1−s)(Ω).Fors∈(1/2,1)
assume additionally that the sequence of grids {ΩH}H∈Λis quasi-uniform. Then for all
vH∈WH
P∈ΩH
P
(cu)(x, y)dV (vH)P−(cu, vH)H
⩽C
P∈ΩH
(diam P)2su2
1+s, P1/2
QHvH0⩽
CH
s
maxu1+sQHvH0.(4.11)
Proof. The main ingredient of the proof is the estimate
|F|:=
P
(cu)(x, y)dV −ωP(cu)P
⩽C(diam P)sω1/2
Pu1+s, P(4.12)
for P∈ΩHfrom which the assertion follows using the Schwarz inequality and the relation
P∈ΩH
ωP|(vH)P|2⩽C
Ω
|(QHvH)(x, y)|2dV.
We consider only the case s∈(1/2,1),the case s= 1 being similar. Let
F1:=
Pc(x, y)−cPu(x, y)dV, F2:= cP
Pu(x, y)−uPdV,
Bereitgestellt von | Technische Universität Berlin
Angemeldet
Heruntergeladen am | 15.10.18 15:35
164 E. Emmrich and R. D. Grigorieff
such that |F|⩽|F1|+|F2|. For brevity let r:= 2/(1−s). The imbeddings H1+s(Ω) →C(Ω)
and W1
r(Ω) →C(Ω) are continuous. Fix u∈H1+s(Ω). Then F1is a linear form that is
bounded for c∈W1
r(P) and vanishes for c= 1. Hence, the Bramble — Hilbert Lemma
furnishes after a suitable scaling
|F1|⩽CωPω−1
P(diam P)r1/r|c|W1
r(P)ω−1
P1+(diam P)2+ω−1
P(diam P)4+2s1/2u1+s, P
leading to the desired bound. Next we are going to estimate the linear functional F2,whichis
for each fixed c∈W1
r(P) bounded for u∈H1+s(Ω) and vanishes for u= 1. The generalized
Bramble — Hilbert Lemma shows in this situation that F2is already bounded with respect
to the semi-norm |u|2
1+|u|2
1+s1/2. With the usual scaling procedure it follows that
|F2|⩽Csup
P|c(x, y)|ωPω−1
P(diam P)2|u|2
1,P+ω−2
P(diam P)4+2s|u|2
1+s, P1/2.
With the same type of arguments one can prove the following lemma.
Lemma 4.6. Let s∈(1/2,1],ψ∈Hs(Γ) and α∈W1
1/(1−s)(Γ). Then the following
estimate holds for P∈ΓH:
ΓP
αψ dσ −σP(αψ)P⩽Cσs+1/2
Pψs,ΓP.(4.13)
Lemma 4.7. Let s∈(1/2,1] and ψ∈Hs(Γ). Then for all vH∈WH
P∈ΓH
ΓP
ψdσ(vH)P−ψ,vHH
⩽C
P∈ΓH
σ2s
Pψ2
s,ΓP1/2
QHvH1⩽CHs
maxψs,ΓQHvH1.
Proof. With the aid of Lemma 4.6, choosing α= 1, and the Schwarz inequality we can
estimate the square of the left-hand side of the asserted inequality by CP∈ΓHσ2s
Pψ2
s,ΓP×
P∈ΓHσP|(vH)P|2.Since
P∈ΓH
σP|(vH)P|2⩽CQHvH,Q
HvH0⩽CQHvH2
1,Ω
the first inequality in the assertion is proved. The second one follows from the same argument
as in the proof of Lemma 4.5.
Remark 4.2. Inthecasethatψis discretized by (2.4), the corresponding left-hand side
of the estimate in Lemma 4.7 vanishes identically.
With the aid of Lemma 4.6 we also obtain the next estimate.
Lemma 4.8. Let s∈(1/2,1],u∈H1+s(Ω) and α∈W1
1/(1−s)(Γ). Then for all vH∈WH
P∈ΓH
ΓP
αu dσ(vH)P−αu, vHH
⩽C
P∈ΓH
σ2s
Pu2
s,ΓP1/2
QHvH1⩽CHs
maxus,ΓQHvH1.
We are now in the position to prove the low regularity error estimate.
Bereitgestellt von | Technische Universität Berlin
Angemeldet
Heruntergeladen am | 15.10.18 15:35
Supraconvergence of a finite difference scheme 165
Theorem 4.1. Let s∈(1/2,1]. Assume u∈H1+s(Ω),a, b, c ∈W1
2/(1−s)(Ω),α∈
W1
1/(1−s)(Γ) and ψ∈Hs(Γ).Fors∈(1/2,1) assume additionally that the sequence of
grids {ΩH}H∈Λis quasi-uniform. Then for Hmax small enough there exists a unique solution
uHof the finite difference equations satisfying
QH(RHu−uH)1⩽C
P∈ΩH
(diam P)2su2
1+s, P+
P∈ΓH
σ2s
Pu2
s,ΓP+|ψ|2
s,ΓP1/2
⩽
CH
s
maxu1+s+ψs,Γ.
Proof. From Proposition 3.2 follows, for Hmax small enough, the uniqueness of problem
(3.6) and hence the unique existence of uH. The asserted bound will be obtained from the
same proposition by estimating τHfrom (4.1). Note that τHcan be written in the form
τH=aH(u, vH)+bH(u, vH)+(cu, vH)H+αu, vHH−(fH,v
H)H−ψ,vHH.
Substitute (fH,v
H)Hfrom (4.3). Use now (4.4) and the corresponding relation for the y-
derivative term (buy)y(let us remark that relation (4.4) can be used although umay not have
second order derivatives because it is only an intermediate step in transforming the integral
of finto well-defined quantities). Since (1.2) holds in Hs−1/2(Γ),we have the relation
ΓPauxηx+buyηydσ =
ΓPψ−αudσ. (4.14)
The asserted bound is then obtained by collecting the estimates from Lemmas 4.4, 4.5, 4.7,
and 4.8.
5. Convergence: case s∈(1,2]
We are now going to prove the supraconvergence. We begin with estimating the error in
replacing (aδ(1/2)
xu)Pin (4.10) by (aux)P.
Lemma 5.1. Let s∈(1,2],u∈H1+s(Ω) and a∈C(Ω).Fors∈(1,2) assume addi-
tionally that the sequence of grids {ΩH}H∈Λis quasi-uniform. Then for all vH∈WH
P∈Ωx
1/2
|SP||(aδ(1/2)
xu)P−(aux)P(∆xvH)P|⩽C
P∈Ωx
1/2
(diam P)2s|ux|2
s, P1/2
|QHvH|1⩽
CHs
max|ux|s|QHvH|1.
Proof. The proof follows similar lines as in the proofs before. We consider only the
case s∈(1,2), the case s= 2 is similar albeit somewhat easier. Note that the imbedding
Hs(Ω) →C(Ω) is continuous. Let P=(xj+1/2,y
)∈Ωx
1/2.Weconsider
(aδ(1/2)
xu)P−(aux)P=aP1
hj
xj+1
xj
ux(x, y)dx −(ux)P
Bereitgestellt von | Technische Universität Berlin
Angemeldet
Heruntergeladen am | 15.10.18 15:35
166 E. Emmrich and R. D. Grigorieff
as a linear functional in ux∈Hs(Ω). It vanishes for polynomials of degree 1. By virtue of
the generalized Bramble — Hilbert Lemma we obtain
(aδ(1/2)
xu)P−(aux)P⩽Csup
Ω|a(x, y)|1
hP|SP|(hP+|SP|)max{hs
P,|SP|s}|ux|s, P,
from which the result is easily derived as before.
Remark 5.1. The claim of Lemma 5.1 holds also true if the rectangle Pis replaced
by the upper or lower half of P. This is immediate from the proof. We have avoided to
state this fact in the wording of the lemma to keep the presentation easier. But in the proof
of Theorem 5.1 we will make use of this observation. A corresponding remark applies to
Lemmas 5.3 and 5.4.
The next lemma provides an essential step in obtaining supraconvergence. We need for
points P∈Ωxy
1/2:= {(xj+1/2,y
+1/2)∈Ω}the line segments, points and rectangles
SP:= {xj+1/2}×(y,y
+1),S
P−:= {xj+1/2}×(y,y
+1/2),S
P+:= {xj+1/2}×(y+1/2,y
+1),
P−:= (xj+1/2,y
),P
+:= (xj+1/2,y
+1),P:= (xj,x
j+1)×(y,y
+1).(5.1)
For points P=(xj,y
+1/2)∈Ωy
1/2we define the following vertices and half vertical line
segments of the rectangle P(= (xj−1/2,x
j+1/2)×(y,y
+1)): If P∈Ωy
1/2\Γthen
S(1)
P:= {xj+1/2}×(y+1/2,y
+1),S
(2)
P:= {xj−1/2}×(y+1/2,y
+1),
S(3)
P:= {xj−1/2}×(y,y
+1/2),S
(4)
P:= {xj+1/2}×(y,y
+1/2),
P(1) := (xj+1/2,y
+1),P
(2) := (xj−1/2,y
+1),P
(3) := (xj−1/2,y
),P
(4) := (xj+1/2,y
),
hP:= xj+1/2−xj−1/2,k
P:= y+1 −y.
For P∈Γy
1/2:= Ωy
1/2∩Γ, the set of midpoints of the vertical boundary sections, the
definitions are corresponding, only with xj+1/2or xj−1/2, respectively, replaced adequately
by xj.ForΓ
y
1/2we need also the half sections Γ−
P,Γ+
Pof the boundary sections below and
above Pand
ΓP:= Γ−
P∪Γ+
P,σ
P:= y+1 −y.(5.2)
Fig. 1 may help to identify the sets introduced here.
j−1jj+1
l−1
l
l+1
P
S(3)
P
S(2)
P
S(4)
P
S(1)
P
F i g. 1. Notation in the proof of Lemma 5.2 for P∈Ωy
1/2
Bereitgestellt von | Technische Universität Berlin
Angemeldet
Heruntergeladen am | 15.10.18 15:35
Supraconvergence of a finite difference scheme 167
Lemma 5.2. The following identity
P∈Ωx
1/2
SP
auxdy −|SP|(aux)P(∆xvH)P=F1+F2+F3(5.3)
holds, where
F1=
P∈Ωxy
1/2
SP
auxdy −kP
2(aux)P++(aux)P−(∆xvH)P++(∆
xvH)P−
2,
F2=
P∈Ωy
1/2
4
i=1
(−1)i
S(i)
P
auxdy −kP
2(aux)P(i)(∆yvH)P
2,
F3=
P∈Γy
1/2
(ηx)P
Γ+
P
auxdσ −σP
2(aux)P+−
Γ−
P
auxdσ +σP
2(aux)P−(∆yvH)P
2.
Proof. We divide the integral extended over SPinto two integrals over the halfsections
below and above Pand note that |SP|is equal to the sum of the lengths of these halfsections.
A straightforward calculation yields that the left-hand side of (5.3) can be written as F1plus
the quantity
P∈Ωxy
1/2
SP+
auxdy −kP
2(aux)P+−
SP−
auxdy +kP
2(aux)P−(∆xvH)P+−(∆xvH)P−
2.
Noting that (∆xvH)P+−(∆xvH)P−=(∆
x∆yvH)P,we perform another summation by parts,
this time with respect to the x-variable, which yields the assertion.
Lemma 5.3. Let s∈(1,2],u∈H1+s(Ω) and a∈W2
2/(2−s)(Ω).Fors∈(1,2) assume
additionally that the sequence of grids {ΩH}H∈Λis quasi-uniform. For all vH∈WHthe
quantity F1in Lemma 5.2 can be estimated by
|F1|⩽C
P∈Ωxy
1/2
(diam P)2sux2
s, P1/2|QHvH|1⩽CHs
maxuxs|QHvH|1.
Proof. Webeginwiththecases∈(1,2).As a preparation, we introduce for P∈Ωxy
1/2
the quantities
F11 :=
SPa−aP−(ay)P(y−yP)uxdy,
F12 := kP
2aP−(ay)P
kP
2−aP−(ux)P−+aP+(ay)P
kP
2−aP+(ux)P+,
F13 := aP
SP
uxdy −kP
2(ux)P++(ux)P−,
F14 := (ay)P
SP
(y−yP)uxdy −k2
P
4(ux)P+−(ux)P−,(5.4)
Bereitgestellt von | Technische Universität Berlin
Angemeldet
Heruntergeladen am | 15.10.18 15:35
168 E. Emmrich and R. D. Grigorieff
which we are going to estimate. We use in the following that the imbeddings W2
r(Ω) →C1(Ω)
and Hs(Ω) →C(Ω) are continuous, where r:= 2/(2 −s).
Starting with (5.4) we note that F11 is a bounded bilinear form for (a, ux)∈W2
r(Ω) ×
Hs(Ω) that vanishes for a=1,x,y. With a scaling as in the proofs before, recalling also that
the grids are quasi-uniform, we derive with the aid of the generalized Bramble — Hilbert
Lemma the estimate
|F11|⩽C(diam P)s|a|W2
r(P)uxs, P⩽C(diam P)suxs, P.
A similar argument yields the same bound for F12.InF13 we deal with the second order
accurate trapezoidal rule applied to ux(xP,·) and obtain again with the aid of the generalized
Bramble — Hilbert Lemma the bound
|F13|⩽Csup
Ω|a(x, y)|(diam P)suxs, P⩽C(diam P)suxs, P.
Finally, F14 is a linear bounded functional with respect to ux∈Hs(Ω) vanishing for ux=1.
Reasoning as before, it is seen that the same bound as for F13 applies to F14.SinceF1can
be written as
F1=
P∈Ωxy
1/2F11 +F12 +F13 +F14hP
2(QHvH)xP−+(QHvH)xP+
the assertion is obtained after an application of the Schwarz inequality.
We now turn to the proof in the case s= 2 and start with the observation that we have
the trapezoidal rule applied to auxunder the sum defining F1which is exact for the functions
1,x and y. The Bramble — Hilbert Lemma furnishes the bound
SP
auxdy −kP
2(aux)P++(aux)P−
⩽CkP
hP1/2
(diam P)2|aux|2,P.
Note that a∈W2
∞(Ω) and so aux∈H2(Ω). The proof can be completed as before.
Lemma 5.4. Let s∈(1,2],u∈H1+s(Ω) and a∈W2
2/(2−s)(Ω).Fors∈(1,2) as-
sume additionally that the sequence of grids {ΩH}H∈Λis quasi-uniform. The quantity F2in
Lemma 5.2satisfies the same estimate as F1in Lemma 5.3.
Proof. We begin with the case s∈(1,2).Let P∈Ωxy
1/2. Wedenoteby ¯
Pthe center of
the rectangle Pand introduce the quantities
F21 :=
4
i=1
(−1)i
S(i)
P
a−a¯
P−(ax)¯
P
h(i)
P
2−(ay)¯
P(y−y¯
P)uxdy,
F22 :=
4
i=1
(−1)ikP
2a¯
P+(ax)¯
P
h(i)
P
2+(ay)¯
P
k(i)
P
2−aP(i)(ux)P(i),
F23 :=a¯
P
4
i=1
(−1)i
S(i)
P
uxdy−kP
2(ux)P(i)
,F
24 :=
4
i=1
(−1)i(ax)¯
P
h(i)
P
2
S(i)
P
uxdy−kP
2(ux)P(i)
,
Bereitgestellt von | Technische Universität Berlin
Angemeldet
Heruntergeladen am | 15.10.18 15:35
Supraconvergence of a finite difference scheme 169
F25 :=
4
i=1
(−1)i(ay)¯
P
S(i)
P
(y−y¯
P)uxdy −kP
2
k(i)
P
2(ux)P(i),
where h(i)
P:= hPfor i=1,4, h(i)
P:= −hPfor i=2,3, and k(i)
P:= kPfor i=1,2, k(i)
P:= −kP
for i=3,4. The quantities F21 and F22 can be estimated in the same way as F11 and
F12, respectively, in the proof of Lemma 5.3. Note that F23 vanishes for ux=1,x,y, and,
consequently, can be estimated as F13 before. Finally, F24 and F25, considered as functionals
in ux, vanish for ux= 1 and hence can be estimated as F13 and F14 before. Upon noting that
F2=P∈Ωy
1/25
j=1 F2jkP(QHvH)yP/2 the proof is completed in the same way as that of
Lemma 5.3.
Consider now the case s=2.LetP=(xj,y
+1/2)∈Ωy
1/2. We start with the identity
F:=
4
i=1
(−1)i
S(i)
P
auxdy −kP
2(aux)P(i)=
xj+1/2
xj−1/2
y+1/2
y
(aux)xdy −
y+1
y+1/2
(aux)xdy −kP
2(aux)x(x, y)+kP
2(aux)x(x, y+1)dx.
The integrand of the outer integral exists for almost all x∈(xj−1/2,x
j+1/2) and is the sum
of errors of one-dimensional rectangle rules applied to (aux)xthat can be estimated with the
aid of the Bramble — Hilbert Lemma. We obtain
|F|⩽C
xj+1/2
xj−1/2
k3/2
P
y+1
ya(x, y)ux(x, y)xy
2dy1/2
⩽Ch1/2
Pk3/2
Pux2,P⩽C(h2
P+k2
P)ux2,P,
wherewemadeuseofa∈W2
∞(Ω) and invoked the Schwarz and Young inequalities in the
second and third step, respectively. The proof can now be completed as before.
Remark 5.2. The proofs of Lemmas 5.3 and 5.4 simplify considerably if the coefficient
ais constant.
To estimate the error related to the approximation of cu, we need two auxiliary lemmas.
The proof of the first one is straightforward.
Lemma 5.5. The following identity holds for ej,w
j∈C,j=1,...,4:
4
4
i=1
eiwi=
4
i=1
ei
4
i=1
wi+(e1−e2+e3−e4)(w1−w2+w3−w4)+
(e1+e2−e3−e4)(w1+w2−w3−w4)+(e1−e2−e3+e4)(w1−w2−w3+w4).
Lemma 5.6. Let s∈(1,2] and g∈Hs(Ω). Then for all vH∈WH
P∈ΩH
P
gdV(vH)P−(RHg,vH)H
⩽C
P∈Ωxy
1/2
(diam P)2sg2
s, P1/2QHvH1.
Bereitgestellt von | Technische Universität Berlin
Angemeldet
Heruntergeladen am | 15.10.18 15:35
170 E. Emmrich and R. D. Grigorieff
Proof. Let P∈Ωxy
1/2. Analogously to the case P∈Ωy
1/2considered in Lemma 5.2 we in-
troduce the vertices P(i),i=1,2,3,4,of Pand divide Pinto four congruent subrectangles
(i)
P(with vertices Pand P(i)). It is then seen that
P∈ΩH
P
gdV(vH)P−(RHg,vH)H=
P∈ΩH
P
gdV −| P|gP(vH)P=
P∈Ωxy
1/2
4
i=1
(i)
P
gdV −| (i)
P|gP(i)(vH)P(i).
For P∈Ωxy
1/2we apply Lemma 5.5 with ei:= (i)
PgdV −| (i)
P|gP(i),w
i:= (vH)P(i)and
estimate the resulting quantities. Firstly, discarding a factor 4, there appears the quantity
4
i=1
(i)
P
gdV −| (i)
P|gP(i)4
i=1
(vH)P(i)=
P
gdV −|P|
4
4
i=1
gP(i)4
i=1
(vH)P(i),(5.5)
containing a two-dimensional analogue of the trapezoidal rule which can be estimated with
the aid of the generalized Bramble — Hilbert Lemma by
C(diam P)s|g|s, P4
i=1 |P||(vH)P(i)|21/2
⩽C(diam P)s|g|s, PQHvH0,P.
Thus for this part the desired bound is obtained. The next quantity resulting from the
application of Lemma 5.5 is
4
i=1
(−1)i
(i)
P
gdV −| (i)
P|gP(i)4
i=1
(−1)i(vH)P(i).(5.6)
In this situation we have quadrature rules that are exact for constant functions only, but we
can exploit the alternating structure in the last sum. We obtain this time the bound
C(diam P)s|g|s−1,P+gxs−1,P+gys−1,P×
|P|
(vH)P(1) −(vH)P(2)
hP
2
+
(vH)P(3) −(vH)P(4)
hP
21/2
⩽C(diam P)sgs, P|QHvH|1,P
furnishing the bound we need. The remaining quantities can be estimated similarly and the
proof is complete.
Lemma 5.7. Let s∈(1,2],u∈Hs(Ω) and c∈W2
2/(2−s)(Ω). Then for all vH∈WH
P∈ΩH
P
cu dV (vH)P−(RH(cu),v
H)H
⩽C
P∈Ωxy
1/2
(diam P)2su2
s, P1/2
QHvH1.
Proof. The first part of the proof is the same as that of Lemma 5.6 until formula (5.5)
with g=cu. We continue the present proof by estimating (5.5). First the coefficient cis
approximated by its first order Taylor polynomial with the midpoint ¯
Pof Pas a center. In
the step corresponding to (5.6), the factor cof uis approximated by c¯
P. The course of the
proof is now similar to that of Lemma 5.4. We do not give the details.
Bereitgestellt von | Technische Universität Berlin
Angemeldet
Heruntergeladen am | 15.10.18 15:35
Supraconvergence of a finite difference scheme 171
Lemma 5.8. Let s∈(1,2],φ∈Hs(Γ) and α∈W2
1/(2−s)(Γ). Then the following estimate
holds for all vH∈WH:
P∈Γy
1/2
ΓP
αφ dσ −kP
2((αφ)P++(αφ)P−)((vH)P++(vH)P−)
⩽
C
P∈Γy
1/2
k2s
Pφ2
s,ΓP1/2
QHvH1⩽CHs
max φs,ΓQHvH1.
Proof. The main step in the proof is to show the estimate
|G|:=
ΓP
αφ dσ −kP
2(αφ)P++(αφ)P−
⩽Ck1/2+s
Pφs,ΓP.(5.7)
To this end we introduce the quantities
G1:=
ΓPα−αP−(ασ)P(σ−yP)φdσ,
G2:= kP
2αP+(ασ)P
kP
2−αP+φP++αP−(ασ)P
kP
2−αP−φP−,
G3:= αP
ΓP
φdσ−kP
2(φP++φP−),G
4:= (ασ)P
ΓP
(σ−yP)φdσ−k2
P
4(φP+−φP−)
that sum up to G. Here, ασdenotes the derivative of αalong the boundary. With the same
arguments as already used before the estimate (5.7) is obtained.
We are now in the position to prove the supraconvergence. We denote by the rectangles
belonging to Ωxy
1/2(see (5.1)) and by Sthe sections belonging to Γx
1/2and Γy
1/2(see (5.2)).
Theorem 5.1. Let s∈(1,2],u ∈H1+s(Ω),a,b,c ∈W2
2/(2−s)(Ω),ψ ∈Hs(Γ) and α∈
W2
1/(2−s)(Γ).Fors∈(1,2) assume additionally that the sequence of grids {ΩH}H∈Λis quasi-
uniform. Then for Hmax small enough there exists a unique solution uHof the finite difference
equations (2.1) together with the discrete boundary conditions (see (2.6) –(2.8)) satisfying
QH(RHu−uH)1⩽C
⊂Ω
(diam )2su2
1+s, +
S⊂Γ|S|2su2
s,S +|ψ|2
s,S1/2
⩽
CH
s
maxu1+s,Ω+|ψ|s,Γ.
Proof. The proof follows the same lines as that of Theorem 4.1. We only have to estimate
the truncation error
τH=aH(u, vH)+bH(u, vH)+(cu, vH)H+αu, vHH−(fH,v
H)H−ψ,vHH
in terms of the claimed bound. We begin with the part containing (aux)xin (fH,v
H)H,which
is transformed according to Lemma 4.1. For the moment we consider only the quantities
related to subdomains of Ω and leave those related to boundary sections to the second part
of the proof. So we form the difference of aH(u, vH) with the first quantity on the right-hand
side of (4.4). Recall the representation (4.10) in which we can replace aδ(1/2)
xuby auxat the
Bereitgestellt von | Technische Universität Berlin
Angemeldet
Heruntergeladen am | 15.10.18 15:35
172 E. Emmrich and R. D. Grigorieff
expense of an error that is estimated in Lemma 5.1. We then apply Lemma 5.2 and estimate
the quantities F1and F2with the aid of Lemmas 5.3 and 5.4. In these calculations only the
boundary quantity F3in Lemma 5.2 is left over and needs further consideration (later in this
proof). The error coming from the second order y-derivatives part (buy)yin the differential
operator Ais estimated similarly. The last error left over comes along with (cu, vH)H.It
can be estimated with the aid of Lemma 5.7 in the form needed.
We come now to the boundary-related parts of τHwhich we collect next. In the proof
given so far we left aside the second member of the right-hand side of (4.4) and F3from
Lemma 5.2. In both of them we replace auxηxwith the aid of (1.2) by ψ−αu =: φ. Together
with the corresponding boundary contributions in τHfrom vertical boundary sections we end
up with
P∈Γy
H
ΓP
φdσ(vH)P−
P∈Γy
1/2
Γ+
P
φdσ−kP
2φP+−
Γ−
P
φdσ+kP
2φP−(∆yvH)P
2−φ, vH(y)
H,(5.8)
where Γy
Hand ·,·(y)
Hdenote the part of ΓHand ·,·H, respectively, extended over the
vertical sections of Γ. The identity
P∈Γy
H
ΓP
φdσ(vH)P−φ, vH(y)
H=
P∈Γy
1/2
ΓP
φdσ−kP
2φP++φP−(vH)P++(vH)P−
2+
P∈Γy
1/2
Γ+
P
φdσ−kP
2φP+−
Γ−
P
φdσ+kP
2φP−(vH)P+−(vH)P−
2
shows that only the composite trapezoidal rule is left over in (5.8) which can be estimated
according to Lemma 5.8 by
C
P∈Γy
1/2
k2s
Pφ2
s,ΓP1/2
QHvH1⩽C
P∈Γy
1/2
k2s
Pu2
s,ΓP+ψ2
s,ΓP1/2
QHvH1.
The horizontal boundary sections give rise to corresponding estimates. Altogether the proof
is complete.
By interpolating the result of Theorem 4.1 for s= 1 and of Theorem 5.1 for s=2we
obtain the following corollary which holds without the assumption of quasi-uniformity of the
grid. Note that the local error estimates in Theorem 5.1 are not obtained using interpolation.
Also the nonclosed range of exponents s∈(1/2,2] is not accessible by interpolation.
Corollary 5.1. Let s∈[1,2],u∈H1+s(Ω), a,b,c ∈W2
∞(Ω),ψ∈Hs(Γ) and α∈
W2
∞(Γ). Then for Hmax small enough there exists a unique solution uHof the finite difference
equations (2.1) with discrete boundary conditions (2.6) –(2.8) satisfying
QH(RHu−uH)1⩽CH
s
maxu1+s,Ω+|ψ|s,Γ.
Remark 5.3. If the right-hand side fof (1.1) is in Hs(Ω),s ∈(1,2], then its approxi-
mation (2.3) can be replaced by the pointwise restriction to the grid ΩHwithout changing
the convergence rate. This follows from the observation that according to Lemma 5.6 the
corresponding perturbation of the right-hand side of (3.6) can be estimated by
|(fH−RHf,vH)H|=
P∈ΩH
P
f(x, y)dV −ωPf(xP,y
P)(vH)P
⩽
Bereitgestellt von | Technische Universität Berlin
Angemeldet
Heruntergeladen am | 15.10.18 15:35
Supraconvergence of a finite difference scheme 173
C
P∈Ωxy
1/2
(diam P)2sf2
s, P1/2
QHvH1.
Remark 5.4. If fis not smooth enough, then the use of the pointwise restriction in the
approximation of fin (1.1) may spoil the supraconvergence. We give an example. Consider
the Neumann boundary value problem
−∆u+u=fin Ω,∂u
∂n =0 on Γ,(5.9)
where Ω := (0,1)2. We discretize (5.9) on a sequence of uniform grids ΩH,H∈Λ, where
Λ, indexed by m, is here the sequence of uniform mesh size vectors Hwith step sizes
hm=km:= 1/m, m ∈N. We will show that the convergence cannot be quadratic for
all f∈H1(Ω). To this end a sequence {f(m)∈H1(Ω)}m∈Nof the right-hand sides in
(5.9) is constructed such that the corresponding exact and discrete solutions u(m)and u(m)
H,
respectively, satisfy
lim
m→∞ h−2
mu(m)−QHu(m)
H0=∞while {f(m)1}m∈Nis bounded.(5.10)
Then, as a consequence of the uniform boundedness principle, the maps
H1(Ω) f→ h−2
mu−QHuH∈L2(Ω),H∈Λ,
cannot be pointwise bounded. Since u∈H3(Ω) then h−2
m{QH(u−uH)}H∈Λis not pointwise
bounded either. To verify (5.10), take
f(m)(x, y)= 1
m(1 −cos(2πmx)),u
(m)(x, y)= 1
m1−cos(2πmx)
1+(2πm)2.
From RHf(m)= 0 it follows that u(m)
H= 0 and a direct calculation shows (5.10) to hold true.
(Note that {f(m)2}m∈Nis not bounded.)
6. Numerical experiment
In the following we give the result of some numerical calculations. We consider the problem
Au := −uxx −uyy +u=fin (0,π)2(6.1)
subject to Neumann boundary conditions. The right-hand side fis taken to be the Fourier
series
f(x, y):=
j,k∈Z
fj,kei(jx+ky),f
j,k := (1 + j2+k2)−s/2log(2 + j2+k2)r,(6.2)
where r=−0.6ands∈Rwill be chosen from some range of exponents. The solution
of (6.1) is u(x, y):=j,k∈Zuj,kei(jx+ky),u
j,k := (1 + j2+k2)−(2+s)/2log(2 + j2+k2)r.We
determined numerically u0=5.0. It can be seen that for r<−0.5 the norm
j,k∈Z
(1 + j2+k2)1+t|uj,k|21/2
(6.3)
Bereitgestellt von | Technische Universität Berlin
Angemeldet
Heruntergeladen am | 15.10.18 15:35
174 E. Emmrich and R. D. Grigorieff
(which is equivalent to u1+t) is finite for t=s, such that u∈H1+s((0,π)2). But the series
in (6.3) is divergent for t>sand hence u∈ H1+t((0,π)2)fort>s.
We discretize the problem with the finite difference scheme in Section 2 on an equidistant
grid with mesh size htaking as the discrete right-hand side fHboth the averaged restriction
(2.3) and the pointwise restriction of f. The grid function fHcan be written as a finite
Fourier series fH(x, y):=N
j,k=−N+1 Fj,kei(jx+ky)for (x, y)∈(0,π)2
H,N=π/h, where the
coefficients Fj,k are obtained numerically from the given fj,k in (6.2) by summing up the
aliasing terms. The finite difference solution is then
uH(x, y):=
N
j,k=−N+1
Fj,k
1+sinc
2(jh/2) + sinc2(kh/2)ei(jx+ky)for (x, y)∈(0,π)2
H,
where sinc(x):=sin(x)/x. The error norm |QH(u−uH)|1is then easily obtained with the aid
of the Fourier coefficients of the finite Fourier series. Instead of |QH(u−uH)|0we calculate
the equivalent norm |u−uH|Hbelonging to the discrete inner product (3.5), which is also eas-
ily obtained from the Fourier coefficients. In fact, if (u−uH)(x, y)=N
j,k=−N+1 Ej,kei(jx+ky)
for (x, y)∈(0,π)2
Hthen we work with the equivalent norm N
j,k=0 |Ej,k|21/2.Ascanbe
seen from Figs 2 and 3, in using the averaged restriction (2.3) of fthe convergence order in the
F i g. 2. Order of convergence of L2-errors (tri-
angles) and H1-errors (circles) for the averaged
restriction of fas a function of N
F i g. 3. Order of convergence for the pointwise (left) and averaged restrictions of fas a function of s
Bereitgestellt von | Technische Universität Berlin
Angemeldet
Heruntergeladen am | 15.10.18 15:35
Supraconvergence of a finite difference scheme 175
L2-norm exceeds the estimated one in Theorems 4.1 and 5.1 for s<2, for s⩽1evenby
one order, while the order for the pointwise restriction of fbehaves in accordance with the
bounds. We think that the higher convergence order observed numerically is due to the
symmetries in the solution u. As can also be seen, the pointwise restriction of fshows a
higher order of convergence than the worst case expectation according to Remark 5.4.
Appendix
This appendix provides a collection of some notations invoked in this paper.
•Meshes:
ΩH:= Ω ∩RH,ΓH:= Γ ∩RH,ΩH:= Ω∩RH.
•Basic rectangles and boundary sections in the partition:
For P=(xj,y
)∈ΩH:P:= (xj−1/2,x
j+1/2)×(y−1/2,y
+1/2)∩Ω,ω
P:= |P|,
ΓP:= (xj−1/2,x
j+1/2)×(y−1/2,y
+1/2)∩∂Ω,σ
P:= |ΓP|.
•Midpoints of horizontal gridline sections:
For P∈Ωx
1/2:= {(xj+1/2,y
)∈Ω}:SP:= {xj+1/2}×(y−1/2,y
+1/2)∩Ω,
P:= (xj,x
j+1)×(y−1/2,y
+1/2)∩Ω,(∆xvH)P:= vj+1, −vj,.
Analogous definitions hold in the vertical direction.
•Centers of subdivision rectangles:
For P∈Ωxy
1/2:= {(xj+1/2,y
+1/2)∈Ω}:SP:= {xj+1/2}×(y,y
+1),
P:= (xj,x
j+1)×(y,y
+1),P−:= (xj+1/2,y
),P
+:= (xj+1/2,y
+1),
SP−:= {xj+1/2}×(y,y
+1/2),S
P+:= {xj+1/2}×(y+1/2,y
+1).
•For P=(xj,y
+1/2)∈Ωy
1/2\Γ:
S(1)
P:= {xj+1/2}×(y+1/2,y
+1),S(2)
P:= {xj−1/2}×(y+1/2,y
+1),
S(3)
P:= {xj−1/2}×(y,y
+1/2),S(4)
P:= {xj+1/2}×(y,y
+1/2)(seeFig.1),
P(1) := (xj+1/2,y
+1),P(2) := (xj−1/2,y
+1),P(3) := (xj−1/2,y
),P(4) := (xj+1/2,y
),
hP:= xj+1/2−xj−1/2,k
P:= y+1 −y.
For P=(xj,y
+1/2)∈Γy
1/2:= Ωy
1/2∩Γ with the interior of Ω lying to the right of P:
replace xj−1/2by xjin the definitions before.
Γ−
P:= {xj}×(y,y
+1/2),Γ+
P:= {xj}×(y+1/2,y
+1),ΓP:= Γ−
P∪Γ+
P,σ
P:= y+1 −y.
References
1. S. Barbeiro, J. A. Ferreira, and R. D. Grigorieff, Supraconvergence of a finite difference scheme for
solutions in Hs(0,L), IMA J. Numer. Anal., 25 (2005), pp. 797–811.
2. D. Bojovi´c, Convergence in W1,1/2
2norm of finite difference method for parabolic problem, CMAM,
3(2003), pp. 45–58.
3. D. Bojovi´c and B. S. Jovanovi´c, Fractional order convergence rate estimates of finite difference method
on nonuniform meshes, CMAM, 1(2001), pp. 213–221.
4. T. Dupont and R. Scott, Polynomial approximation of functions in Sobolev spaces,Math. Comp.,
34 (1980), pp. 441–463.
5. J. A. Ferreira and R. D. Grigorieff, On the supraconvergence of elliptic finite difference schemes, Appl.
Numer. Math., 28 (1998), pp. 275–292.
Bereitgestellt von | Technische Universität Berlin
Angemeldet
Heruntergeladen am | 15.10.18 15:35
176 E. Emmrich and R. D. Grigorieff
6. J. A. Ferreira and R. D. Grigorieff, Supraconvergence and supercloseness of a scheme for elliptic equa-
tions on nonuniform grids, to appear in Numer. Funct. Anal. Optimiz.
7. P.A. Forsyth and P. H. Sammon, Quadratic convergence for cell-centered grids, Appl. Numer. Math.,
4(1988), pp. 377–394.
8. B. Garc´ıa-Archila, A supraconvergent scheme for the Korteweg-de Vries equation, Numer. Math.,
61 (1992), pp. 292–310.
9. B. Garc´ıa-Archila and J. M. Sanz-Serna, A finite difference formula for the discretization of d3/dx3
on nonuniform grids,Math.Comp.,57 (1991), pp. 239–257.
10. R. D. Grigorieff, Some stability inequalities for compact finite difference operators,Math. Nachr.,
135 (1988), pp. 93–101.
11. W. Hackbusch, Elliptic differential equations: theory and numerical treatment, Springer, Berlin,
1992.
12. I.Hlav´aˆcek and M. Kˆr´ıˆcek, On a superconvergent finite element scheme for elliptic systems, I. Dirich-
let boundary condition,Apl.Mat.,32 (1987), pp. 131–154.
13. I.Hlav´aˆcek and M. Kˆr´ıˆcek, On a superconvergent finite element scheme for elliptic systems, II.
Boundary conditions of Newton and Neumann type,Apl.Mat.,32 (1987), pp. 200–213.
14. I.Hlav´aˆcek, M. Kˆr´ıˆcek and V. Piˆstora, How to recover the gradient of linear elements on nonuniform
triangulations,Apl.Mat.,41 (1996), pp. 241–267.
15. F. de Hoog and D. Jackett, On the rate of convergence of finite difference schemes on nonuniform
grids, J. Austral. Math. Soc., Sr. B, 26 (1985), pp. 247–256.
16. B. S. Jovanovi´c, Finite difference schemes for partial differential equations with weak solutions and
irregular coefficients, CMAM, 4(2004), pp. 48–65.
17. B. S. Jovanovi´c, The finite difference method for boundary-value problems with weak solutions,Po-
sebna Izdanja, 16. Matematiˇcki Institut u Beogradu, Belgrade, 1993.
18. B. S. Jovanovi´c, L. D. Ivanovi´c and E. E. S¨uli, Convergence of a finite-difference scheme for second-
order hyperbolic equations with variable coefficients, IMA J. Numer. Anal., 7(1987), pp. 39–45.
19. B. S. Jovanovi´c and P. P. Matus, Estimation of the convergence rate of difference schemes for elliptic
problems, Comput. Math. Math. Phys., 39 (1999), pp. 56–64.
20. B. S. Jovanovi´c, L. D. Ivanovi´c and E. E. S¨uli, Convergence of finite-difference schemes for elliptic
equations with variable coefficients, IMA J. Numer. Anal., 7(1987), pp. 301–305.
21. B. S. Jovanovi´candB.Z.Popovi´c, Convergence of a finite difference scheme for the third boundary-
value problem for an elliptic equation with variable coefficients, CMAM, 1(2001), pp. 356–366.
22. B. S. Jovanovi´candB.Z.Popovi´c, Some convergence rate estimates for finite difference schemes,
Mat. Vesnik, 49 (1997), pp. 249–256.
23. B. S. Jovanovi´c, E. E. S¨uli and L. D. Ivanovi´c, On finite difference schemes of high order accuracy for
elliptic equations with mixed derivatives,Mat.Vesnik,38 (1986), pp. 131–136.
24. H. O.Kreiss, T. A. Manteuffel, B. Swartz, B. Wendroff and A. B. White Jr., Supra-convergent schemes
on irregular grids,Math.Comp.,47 (1986), pp. 537–554.
25. M. Kˆr´ıˆcek and P. Neittaanm¨aki, Superconvergence phenomenon in the finite element method arising
from averaging gradients, Numer. Math., 45 (1987), pp. 105–116.
26. M. Kˆr´ıˆcek and P. Neittaanm¨aki, On a global superconvergence of the gradient of linear triangular
elements, J. Comput. Appl. Math., 18 (1987), pp. 221–233.
27. M. Kˆr´ıˆcek and P. Neittaanm¨aki, Bibliography on superconvergence, in: Finite element methods (M.
Kˆr´ıˆcek, P. Neittaanm¨aki and R. Stenberg eds.), Marcel Dekker, New York, 1998, pp. 315–348.
28. R. D. Lazarov, V. L. Makarov and W. Weinelt, On the convergence of difference schemes for the
approximation of solutions u∈Wm
2(m>0.5) of elliptic equations with mixed derivatives, Numer. Math.,
44 (1984), pp. 223–232.
29. C.D. Levermore, T. A. Manteuffel and A. B. White Jr., 1988, Numerical solutions of partial differ-
ential equations on irregular grids, in: Computational techniques and applications, CTAC-87, Sydney 1987
(J. Noye and C. Fletcher eds.), North-Holland, Amsterdam — New York, 1988, pp. 417–426.
30. N. Levine, Superconvergent recovery of the gradient from piecewise linear finite-element approxima-
tions, IMA J. Numer. Anal., 5(1985), pp. 407–427.
31. Q. Lin, L. Tobiska and A. Zhou, Superconvergence and extrapolation of non-conforming finite ele-
ments applied to the Poisson equation, IMA J. Numer. Anal., 25 (2005), pp. 160–181.
32. T. A. Manteuffel and A. B. White Jr., The numerical solution of second order boundary value prob-
lems on nonuniform meshes,Math.Comp.,47 (1986), pp. 511–535.
Bereitgestellt von | Technische Universität Berlin
Angemeldet
Heruntergeladen am | 15.10.18 15:35
Supraconvergence of a finite difference scheme 177
33. M. A. Marletta, Supraconvergence of discretization methods on nonuniform meshes, M. Sc. Thesis,
Oxford University, 1988.
34. P. Matus and I. Rybak, Difference schemes for elliptic equations with mixed derivatives, CMAM, 4
(2004), pp. 494–505.
35. W. McLean, Strongly elliptic systems and boundary integral equations, University Press, Cambridge,
2000.
36. L. A. Oganesyan and L. A. Rukhovets, Study of the rate of convergence of variational difference
schemes for second-order elliptic equations in a two-dimensional field with a smooth boundary, USSR Com-
put. Math. Math. Phys., 9(1972), pp. 153–183.
37. A. A. Samarskij, Theorie der Differenzenverfahren, Geest & Portig, Leipzig, 1984.
38. E. S¨uli, B. Jovanovi´c, L. Ivanovi´c, Finite difference approximations of generalized solutions,Math.
Comp., 45 (1985), pp. 319–327.
39. V. Thom´ee, J.-C. Xui and N.-Y. Zhang, Superconvergence of the gradient in piecewise linear finite
element approximation to a parabolic problem, SIAM J. Numer. Anal., 26 (1989), pp. 553–573.
40. P. N. Vabishchevich, A. A. Samarskii and P. P. Matus, Second-order accurate finite-difference sche-
mes on nonuniform grids, Comput. Math. Math. Phys., 38 (1998), pp. 399–410.
41. L. B. Wahlbin, Superconvergence in Galerkin finite element methods, Lect. Notes in Math. 1605,
Springer, Berlin, 1995.
42. B. Wendroff and A. B. White Jr., Some supraconvergent schemes for hyperbolic equations on irregular
grids, in: Nonlinear hyperbolic equations — theory, computation methods, and applications, Aachen 1988
(J. Ballmann and R. Jeltsch eds.), Notes Numer. Fluid Mech. 24, Vieweg, Braunschweig, 1989, pp. 671–677.
43. J. R. Whiteman and G. Goodsell, Some gradient superconvergence results in the finite element
method, in: Numerical analysis and parallel processing (P. R. Turner ed.), Lect. Notes in Math. 1397, Springer,
Berlin, 1987, pp. 182–260.
44. A. Zlotnik, On superonvergence of a gradient for finite element methods for an elliptic equation with
nonsmooth right-hand side, CMAM, 2(2002), pp. 295–321.
Bereitgestellt von | Technische Universität Berlin
Angemeldet
Heruntergeladen am | 15.10.18 15:35
