Citation

## Material Information

Title:
A theoretical foundation for the finite volume element method
Creator:
Cai, Zhiqiang
Publication Date:
Language:
English
Physical Description:
51 leaves : illustrations ; 29 cm

## Subjects

Subjects / Keywords:
Differential equations ( lcsh )
Differential equations ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

## Notes

Bibliography:
Includes bibliographical references.
General Note:
Submitted in partial fulfillment of the requirements for the degree, Doctor of Philosophy, Department of Mathematical and Statistical Sciences.
Statement of Responsibility:
by Zhiqiang Cai.

## Record Information

Source Institution:
Holding Location:
Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
24672955 ( OCLC )
ocm24672955
Classification:
LD1190.L62 1990d .C34 ( lcc )

Full Text
A Theoretical Foundation
for the Finite Volume Element
Method
by
Zhiqiang Cai
Computational Math Group
1200 Larimer St., Campus Box 170
Denver, CO 80204
May 1990

A Theoretical Foundation for
the Finite Volume Element Method
by
Zhiqiang Cai
B. A., Huazhong University of Science and Technology, Wuhan, China, 1982
M. S., Huazhong University of Science and Technology, Wuhan, China, 1985
A thesis submitted to the
Faculty of the Graduate School of the
University of Colorado in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy
Department of Mathematics
May 1990

This thesis for the Doctor of Philosophy degree
by
Zhiqiang Cai
has been approved for the
Department of Mathematics
by
Gita Alaghband
Date 27 August 1990

Zhiqiang Cai (Ph.D., Applied Mathematics)
A Theoretical Foundation for the Finite Volume Element Method
Thesis directed by Professor Stephen McCormick
This thesis is devoted to the development of a theoretical foundation of
the finite volume element method (FVE). FVE is a discretization technique
for partial differential equations, especially those that arise from physical con-
servation laws. FVE uses a volume integral formulation of the problem with
a finite partition set of volumes to discretize the equations, then restricts the
admissible functions to a finite element space to discretize the solution.
Theory for discretization error estimates for general self-adjoint elliptic
boundary value problems with FVE based on triangulations with linear finite
element spaces and a general type of control volume is developed in this thesis.
0(h) estimates of error in a discrete H1 seminorm are established. Under an
additional assumption of local uniformity of the triangulation the estimate is
improved to 0(h2). A basic error estimate of FVE with numerical integration
is also included, and sufficient conditions are given to ensure that the effect
does not decrease the order of convergence.
The form and content of this abstract are approved
publication.
Signed
I recommend its
Stephen McCormick

To My Parents

ACKNOWLEDGMENTS
I would like to express my appreciation to my advisor, Professor Steve
McCormick, for many important corrections, helpful suggestions, and encour-
agement.
I would also like to thank Professors Jan Mandel, Tom Manteuffel, Seymour
Parter, and Tom Russell for many inspiring discussions.
My hearty thanks is also due to the United States Air Force Office of
Scientific Research and the National Science Foundation for their financial
support.

CONTENTS
Chapter 1 Introduction
1.1 Motivation............................................... 1
1.2 Contents of the Thesis................................... 3
Chapter 2 The Primitive Form of Elliptic Boundary Value
Problems
2.1 Sobolev Spaces........................................... 5
2.2 Elliptic Boundary Value Problems in Divergence Form.....10
2.3 The Primitive Form.......................................11
Chapter 3 The Finite Volume Element Method
3.1 Basic Approach..........................................12
3.2 Finite Element Spaces....................................13
3.3 Control Volumes..........................................15
Chapter 4 The Theory of the Finite Volume Element Method
4.1 General Considerations on Convergence....................19
4.2 Error Estimates in the Discrete Hl seminorm..............22
4.3 Sufficient Conditions for Uniform Ellipticity of the FVE
Operator................................................29
Chapter 5 Numerical Integration
5.1 Numerical Integration....................................37
5.2 The Effect of Numerical Integration......................41
References........................................................49

Chapter 1
Introduction
1.1 Motivation.
This thesis is devoted to the development of a theoretical foundation
of the finite volume element method (FVE [14]). FVE is a discretization
technique for partial differential equations, especially those that arise from
physical conservation laws. FVE uses a volume integral formulation of the
problem with a finite partition set of volumes to discretize the equations,
then restricts the admissible functions to a finite element space to discretize
the solution.
The classical finite volume method (FV) is in common use for discretizing
computational fluid dynamics equations. Reasons for its popularity include
its ability to be faithful to physics in general and conservation in particular, to
capture shocks, to produce simple stencils, to apply to a fairly wide range of
fluid flow equations, to effectivelly treat Neumann boundary conditions and
nonuniform grids, and to facilitate multigrid solution. Yet the FV approach
is not fully systematic: use of FV requires a scheme for approximating certain
fluxes, which is often done in an effective but rather ad hoc and restrictive way
that depends upon truncation error analysis. The limitations of truncation
error analysis were treated in depth by Kreiss, Manteuffel, Swartz, Wendroff,
and White (see [13]) and Manteuffel and White (see [15]), who, among other
things, demonstrated that truncation errors can be very large (e.g.,0(l))
even in cases where the actual errors are small (e.g., 0{h) or 0(h2)). Here,
h is the mesh size.
1

FVE was developed as an attempt to use finite element ideas to create
a more systematic FV methodology. The basic idea is to approximate the
discrete fluxes needed in FV by replacing the unknown PDE solution by a
finite element approximation. This means that the discretization design pro-
cess can pay more attention to the local character of the solution (to choose
accurate finite element spaces), and less to the equations. Furthermore, it
provides a very effective discretization process for multilevel adaptive meth-
ods.
FVE is closely related to the control volume finite element method
(CVFE [18]), which was introduced by Baliga and Patanker [2] several years
earlier in the mechanical engineering literature. However, there are impor-
tant differences in how each method treats composite grids, especially in that
FVE allows more general construction of the control volumes. The methods
are same for simple elliptic equations and volumes based on the Voronoi mesh
[23],
A technique with basically the same approach is the generalized box
method, which was analyzed two years ago by Bank and Rose [3]. The main
result of their work is that the solution generated by the box method, ug, is
of comparable accuracy to the solution ui generated by the standard Ritz-
Galerkin procedure using piecewise linear finite elements. In particular, if u
is the true solution and | |i,2,n denotes H1 seminorm, we have for Poissons
equation that
\u UL |l,2,n < \y> Ub\i,2,SI < C\u Ul\i,2,U-
The proof of this result seems to rest heavily on the fact that it is being
applied to Poissons equation, and no superconvergence results are obtained.
2

Cai and McCormick [7] established accuracy estimates for FVE for dif-
fusion equations on simple composite grids; full convergence order 0(h2) is
restored by using higher order elements along grid interfaces; however, the
proofs appeal to the resulting stencil entries and are therefore quite complex.
Ewing, Lazarov, and Vassilevski [9] considered FV on cell-center composite
grids, and they suggested an iterative method for solving nonsymmetric lin-
ear system that arise from FV. In other related work, Nakata, Weiser and
Wheeler [19] have shown that certain block centered finite difference schemes
on rectangular meshes are equivalent to a mixed finite element method.
1.2 Contents of the Thesis.
This thesis consists of preliminary material, a development of the basic
approach of the finite volume element method, and its convergence analysis.
In Chapter 2, we start with basic notations, some results of Sobolev spaces,
and development of a class of elliptic boundary value problems, then derive
the primitive form of elliptic boundary value problems which is employed by
the finite volume element method.
The basic idea of the finite volume element method is to use the primitive
form of the problem with a finite partition set of volumes to discretize the
equations, then restrict the admissible functions to a finite element space to
discretize the solution. Thus, two basic design choices for this method are
the finite element space and the finite set of control volumes. In Chapter 3,
after briefly describing basic approach of the finite volume element method,
we introduce piecewise linear finite element space in a standard way, then
discuss construction of the control volumes. Also, sufficient conditions for
regularity of the control volumes are given.
3

In Chapter 4, we develop a theory for estimating discretization error of
the finite volume element method. MaiThe m results are that the discretiza-
tion error of the method in the discrete Hl seminorm is 0(h) in general,
0(h%) with essentially symmetric control volumes, and 0(h2) with symmet-
ric control volumes. Proof of these results rests on the assumption that the
FVE operator is uniformly elliptic, for which we give some sufficient condi-
tions.
In practice, integrals appearing in the FVE coefficient matrix are approx-
imated by numerical integration, the effect of which is discussed in Chapter
5. After developing a basic error estimate of FVE with numerical integration,
sufficient conditions are given to ensure that the effect does not decrease the
orders of convergence.
4

Chapter 2
The Primitive Form of Elliptic Boundary Value Problems
Formulation of elliptic boundary value problems employed by the finite
volume element method is of the primitive form, which is derived in this
chapter. After reviewing some basic facts on Sobolev spaces in Section 2.1,
a class of elliptic boundary value problems is described in Section 2.2 and its
primitive form is derived in Section 2.3.
2.1 Sobolev Spaces.
Let fi Â£ Rd be a bounded domain with Lipschitz boundary (see [1]), and
let Lp[tt), for any number p Â£ [l,oo], be the space of measurable functions
with finite norm

(In \v\pdx)*,
ess supj.en|u(a;)|,
1 < p < oo,
p = oo,
where
ess supEGn|u(a;)| = inf{K : |d(s)| < K a.e. on S7}
is the essential supremum of u(). The space Â£p(f2) is a Banach space for
1 < p < oo and a Hilbert space for p = 2.
The Sobolev space TVm,p(J2), for any integer m > 0 and any p E [1, oo], is
defined by the set of all functions v Â£ Lp(fl) for which all partial derivatives
dav (in the distribution sense) with |a| < m belong to the space Lp(fl),
equipped with the norm

(E|a| max|a| 5

where a = (ai,...,ad) is a multi-index with integer on > 0 (i = l,...,d) and
aii
dav =
a = ai + + aa.
daixi daiXd
The space Wm,p(fi) is a Banach space. We also make use of the seminorm
I, J(E||=m/n \dav\pdx)p, p G [1, oo),
{ ma|a|=TIl{ess supx6n]5ax7|}, p = oo.
Also, we let denote the closure of the space which is defined
as the space of all infinitely differentiable functions v : fl R with compact
support (see [1]), in the space For p = 2, by convention, we denote
Wm'2(O) and W^2(0) by Sm(Q) and || ||TOf2|n and | |m>2|fi by
II lh.n and I 12,0) respectively.
In view of future needs, we quote here some basic properties of Sobolev
spaces and interpolation theory in Sobolev spaces (see [1], [4], and [8]).
Sobolev Imbedding Theorem. Let ft 6 Rd be a domain and let tik be
the ^-dimensional domain obtained by intersecting ft with a fc-dimensional
plane in Rd, 1 < k < d. Let j and m be nonnegative integers and let p
satisfy 1 < p < oo. If ft has the cone property, then there exist the following
imbeddings:
(1) For mp > d,
Wm>p(fl) > C(Q).
(2) For mp < d, d mp < k < d, and p < q < d^^np,
Wj+rn'p{fl) Wj'q(flk).
(3) For mp = d and p < q < oo,
Wj+mp(fl) W,-9(ftfc).
6

Let
Pj.(ft) = span{p : p{x) xa, for all |a| < k},
the set of polynomials of degree k on ft.
Bramble-Hilbert Lemma. Let ft be an open subset of Rd with a
Lipschitz continous boundary. For some integer k > 0 and some number
p E [0,oo], let / be a continuous linear form on the space Wfc+1,p(ft) with
the property that
f(p) = 0, for all p E P*(ft).
Then there exists a constant C(ft) such that
l/MI < C(n)||/||;+1JliB, for all vWt+'*(.Sl),
where || ||Â£+1 p n is the norm in the dual space of Wfc+1,p(ft).
This section ends up with an inequality of the imbedding theorem type.
Theorem 2.1.1 (see [21]). Let ft be an open subset of Rd with Lipschitz
continous boundary 5ft; and let ft\$ be a strip of width 6, which is sufficiently
small, adjacent to the boundary 5ft and lying entirely inside the domain ft.
Then we have for any v E IT1 (ft),
IMIo.fi, < cfl^IMkn, (2.1.1)
and for any v E .ffj(ft),
lbllo.fi, < csMi.n, (2.1.2)
where c is a constant independent of v and 6.
The above theorem is a special case of the result in [21] which says that
for any v G Pa(ft), one has
IMkn, < c(tf)|M|ain
(2.1.3)
7

with.
{c8a, 0 < a < Â§,
c8^\ln8\, a = |,
c8%, \ < a < 1,
where c is a constant independent of v and 8, and JT(f2) is fractional order
Sobolev spaces (see [1]). Since reference [21] is written in Russian and we have
not seen it, we give a proof of Theorem 2.1.1 for the sake of completeness.
Proof of Theorem 2.1.1. Let us first consider any v Â£ Since
the boundary dfl is Lipschitz-continuous and 8 is sufficiently small, then there
exist constants a > 0 and f3 > 0, and a finite number of local coordinate
systems and local Lipschitz-continuous maps ar, 1 < r < R, which are
definded on
{xr Â£ Rd~l : |r| respectively, such that
dÂ£l = U^=1{(*i,*r) : x\ = ar{xr), \xr\ < a},
and
c uf=1nr,
where = (zj,..., |r| < a stands for |Â£| < a, 2 < i < d, and
= {(xi,xr) : ar(p) < p < ar(xr) + 8, |r| < a}.
It is easy to see that for any point (p,r) Â£
Cl dv(x\,xr)
piC
v(x^,xr) = v(ar(xr),xr) + I
J ar
(Jr) dx\
dx\.
8

By Cauchy-Schwartz inequality, we have
^(*1 j*r)|2 < 2|u(ar(r),r)|2
+ 2(a:j ar(xr)) f
J a
a^+s dv{x^,xr)
2dx j.
p(xr) xl
Integrating the above inequality over interval [ar(r), ar(r) + 5] with respect
to ajj and over region \xr\ < a with respect to xr, we have
/ v2dx <2sf v2ds + 82 f \dv{XJfr)\2dx
JnT JdnT JnT xi
<26 I v2ds + 62 vu Vvdx-
J J flp
Hence, we have
j v2dx < 28[ I v2ds + 6 I s/v \/vdx\. (2.1.4)
vÂ£l(j v dÂ£l vflg
Now (2.1.1) follows from the facts that
/ ^2ds < cIMIi,n
Jen
and
Mi,ft. < Mi,n-
(2.1.5)
For any v G .D(fl), (2.1.2) is a consequence of (2.1.4) and (2.1.5).
To complete the proof, it remains to use the denseness of the spaces
C(n) and D(SI) in the spaces H1(fi) and .ffj(fi), respectively.
9

2.2 Elliptic Boundary Value Problems in Divergence Form.
We shall consider the following self-adjoint elliptic boundary value prob-
lems in divergence form
-V(^V'U) = / in
u 0 on To,
(A S7 v,) ~n = g on Tj,
(2.2.1)
where the domain 12 is an open subset in Rd with Lipschitz boundary T = 312
which is partitioned by To and Fi; V is the divergence operator defined by
V =
/ \
dxi
Veil/
/ E ir2(12) and g E L2(Ti) are given real-valued functions; the real-valued
function matrix
/ 11 12 lci ^
21 22 . d2d
\ 0>d 1 a-d! ddd /
is given, and aij E 2/(12) for 1 < i,j < d. Assume henceforth that the
following uniform ellipticity condition holds: there exists a constant ai > 0
such that
> aitTt (2.2.2)
for all Â£ E Rd and E 12.
10

2.3 The Primitive Form.
[20])
Given functions w,V{ Â£ J1(fZ), i = 1 ...,d, the Greens formula (cf.
I wdiVidx = I Vidiwdx + / wviUids (2.3.1)
v S7 / o /r
holds for any integer i Â£ [l,d], where ~n = (ni, ...,rid)T is the unit outward
normal vector defined on the boundary T of J7. By letting w = 1 and taking
the sum over i, we get the Gauss divergence formula
I \?-vdx= I v-~rids,
Jn Jt
(2.3.2)
where v = (ui, ...,Vd)T is a vector function. Replacing v by A V v in (2.3.2),
we obtain
(2.3.3)
I V (^4 V v)dx = J (Asj v)-~n ds,
J n Jr
for all yu Â£ (JT1(fi))d. That is, (2.3.3) is true for all v Â£ H2(Â£l).
By taking the integral of (2.2.1) over any volume Veil with a Lipschitz
boundary and using formula (2.3.3) on the left-hand side, (2.2.1) may be
transformed to the following Primitive Form (or Surface Integral Form ):
Find u Â£ ff(02)(n;r0) = {u Â£ H\n) : v = 0 on r0} D H2(Q)
such that, for any volume Vc ft with Lipschitz boundary
/ {A y u) lids I fdz,
Jav Jv
(2.3.4)
where n is the unit outward normal vector on the boundary of V,
dV.
11

Chapter 3
The Finite Volume Element Method
Discretizations based on the primitive form (2.3.4) can preserve a sense
of conservation, which is quite important in computational fluid dynamics.
The basic idea of the finite volume element method is to use a finite set of
control volumes to discretize the equations and restrict the unknowns to be
in a finite-dimensional space. The basic approach of FVE is suggested in
Section 3.1. Two basic choices of FVE are finite element spaces and control
volumes, which are described in Section 3.2 and Section 3.3, respectively.
3.1 Basic Approach.
There are two basic ways to discretize problem (2.3.4) by finite volumes,
both of which use a finite set of control volume to discretize the equation. The
conventional finite volume approach uses finite differences of u at neighboring
points in order to replace the continuous fluxes {A \/u) ~n (see [9] and [11]).
Instead, the finite volume element method evaluates the continuous fluxes
by restricting the unknowns to lie in a finite-dimensional space. In particu-
lar, let Vh be a finite set of control volumes and Sq be a finite-dimensional
space. Assume that the dimension of equals the cardinality of Vh\ the
dimension of Sq dictates the number of unknowns in the discretization and
the cardinality of Vh dictates the number of its equations. The discrete FVE
problem is then written as follows:
Find uh (E Sq such that, for all Vh Â£ Vh,
I (A V uh) lids J fdz. (3.1.1)
JdVh Jvh
12

For the FVE method, treatment of the Neumann boundary condition is
straightforward: we do not need to impose the Neumann boundary condition
directly on the finite element space Sq ; instead, we incorporate it in (3.1.1)
by specifying A V uh whenever dVh coincides with a Neumann boundary.
However, the Dirichlet condition is imposed directly on Sq Therefore, we
may say that the Neumann boundary condition and the Dirichlet boundary
condition are natural and essential respectively, as in the finite element
method case. In the next two sections, we will discuss two basic FVE design
choices, the finite element space Sq and the finite set of control volumes Vh
3.2 Finite Element Spaces.
In this section, we introduce a piecewise linear finite element space in a
standard way (see [8]). For simplicity, we assume that fl C R2 is a polygonal
domain and restrict ourselves to piecewise linear finite element spaces defined
on triangulations. By a triangulation, Th, of the domain fi, we mean a set
of triangular elements such that the intersection of any two distinct elements
in Th either consists of a common side or common vertex, or is empty, and
= Uj-hK (see Figure 3.2.1).
For any K Â£ let
h,K = diam(if), h = majcKe7-hhK,
and
Pk = sup{diam(C) : C is a disk contained in K}.
13

Figure 3.2.1. Triangulation.
Assume that Th is regular (see [8]): there exists a constant <7 such that, for
all K UhTh,
hK < o-pK- (3.2.1)
It is known that (3.2.1) is equivalent to Zlamals condition (see [24]): there
exists a constant 0q > 0 such that, for all K Â£ Ll/l7'h,
0K >6o, (3.2.2)
where 0k denotes the smallest interior angle of K.
Now supposing that a family of triangulations, Th, is given on fi, we
first consider a family of piecewise linear finite element spaces
Sh {v Â£ C,0(17) : v\k is linear for all K 6 Th}
where v\k is the restriction of v to K. Then the finite element space Sq is
chosen by imposing the Dirichlet condition on Sh, i.e.,
Si = {> 6 Sk : v|r0 = o}.
14

3.3 Control Volumes.
In general, we may construct the control volumes as follows: choose any
interior point or median of K Â£ UhTh and connect it with the medians of K
(see Figure 3.3.1). In this dissertation, we are particularly interested in the
case that is the circumcenter, orthocenter, incenter, or centroid (i.e., center
of gravity) of the triangle K, which are the respective midpoint of the cir-
cumscribed circle of K, intersection of its altitudes, midpoint of its inscribed
circle, and intersection of its medians. The control volume associated with
the circumcenter of the triangle was considered in [3], [6], and [11]; that
related to the centroid is in common use in CFD and forms the -so-called
Voronoi mesh (see [23]). In order to keep the circumcenter and orthocenter
from lying outside of the triangle, we assume throughout this paper that no
interior angle of any triangle in Th is larger than 90.
Figure 3.3.1. Sample control volume Vh (dotted lines).
15

Suppose that the m > n grid points (i.e., vertices of Th) are singly
subscripted so that
nh = {z* : 1 < i < m}
denotes the set of nodes of 'Th and
nh = {4 : i < i < n} = nh n (n u i^)
denotes nodes of both its interior and Neumann boundary
rf = nh n ri.
Let
rÂ£ = nh \ nh.
Here and henceforth, we drop the superscript h when there is no danger of
ambiguity. For each i=l,...,m, let N(i) denote the set of neighbors of Z{ in flh
(i.e., points zj such that Z{ and Zj are distinct vertices of a common element
K 6 Th). Let
Vi = {j : Zj 6 N(i), 1 < j < m}
denote the subscript set for neighbors of Zi in Qh and let
v = {{i,j} 1 < i,j Note that the unordered pairs {i,j} = in oj are in one-to-one corre-
spondence to the edges in Th. Now given 1 let
lij = Vi n Vj
where V{ and Vj are the control volumes associated with points Z{ and Zj,
respectively. Let ~n ij to be the unit outward normal vector on 7ij (outward
16

with respect to V/1). Let Zij denote the line segment connecting Zi and zj.
For each {i,j} G let \jij | and |Zij | denote the Euclidean lengths of 7^ and
Zij, respectively.
Now each {i,j} G u; corresponds to two triangles, with a common
face Zij, which we denote by if' and if". We say that the control vol-
umes are symmetric if 7ij fl if' and 7ij fl if" are perpendicular to Zij and
Itij n if | = Yiij fl if"| for all {i,j} G u;; they are essentially symmetric if
they are symmetric except for some volumes lying in a subregion, f1, that
consists of a fixed number of strips in fi with width O(h); otherwise, they
are nonsymmetric Note that the control volumes associated with either
the orthocenter, the incenter, or the centroid are symmetric if each trian-
gle if G Th is equilateral; the control volumes related to the circumcenter
are symmetric if Th consists of equilateral triangles or triangles which are
obtained by bisecting rectangles of the same shape.
By connecting the point zjc with the vertices of if G Th, we obtain a
new triangulation Th. We say that the control volumes are regular if the
new triangulation Th is regular. For this, we have the following simple facts
from plane geometry.
Proposition 3.3.1. If Th is regular, then the control volumes associ-
ated with the incenter and centroid are regular.
Denote the angles of if' and if" opposite the common face Zij by the
respective Ok' and 6j(" (see Figure 3.3.2).
Proposition 3.3.2. Assume that Th is regular.
(1) If there exists a constant 0 > 0 such that, for all if', if" G Th,
@K' ^ @ and @Kn ^ (3.3.1)
17

Figure 3.3.2. Opposing angles 9k> and 9k" of the respective triangles
K' and K" with respect to the common face.
then the control volumes related to the orthocenter are regular.
(2) If there exists a constant 0 > 0 such that, for all K', K" 6
- 7T 7T
either 9k> or 9k< <----------------9
2 2
(3.3.2)
and
- 7T _ 7r -
either Ok" or 9k" <
(3.3.3)
then the control volumes related to the circumcenter are regu-
lar.
18

Chapter 4
The Theory of the Finite Volume Element Method
In this chapter, we consider the problem of determining estimates in the
discrete H seminorm of the difference u Uh, where u (E Uq '(12; To) is the
solution of a second-order boundary value problem (2.3.4) and Uh G Sg is the
FVE solution of (3.1.1). In Section 4.1, a basic error estimate, which implies
convergence of the FVE discretization, is established. Convergence order is
obtained in Section 4.2 by bounding the right-hand side of the inequality
(4.1.6) in Theorem 4.1.1. Sufficient conditions for uniform ellipticity of the
FVE operator B are given in Section 4.3.
4.1 General Considerations on Convergence.
Define the discrete H1 seminorm by
Mi.n* = | X -(*i))2 J
For each {i,j} G oj, define the linear functional bij by
bij(v) = (Ay v) liijds (4-1-1)
J m
and the linear operator B by
n
(4.1.2)
1=1
We call B uniformly elliptic on iSq if there exists a constant 0:2 > 0 indepen-
dent of the space Sq such that, for all v in Sg,
n
^2v(zi)(Bv)i > (4.1.3)
i=l
19

Conditions which guarantee uniform ellipticity of B will be given in the Sec-
tion 4.3 of this chapter.
Let ~n i be the unit outward normal vector on dV{ (i = 1, ...,ra). Since
(Bv)i = V' bij(v) = / (As/v)-"uids, (4.1.4)
;e* JeVi
then we can rewrite (3.1.1) as follows:
Find uh Â£ Â£q such that
Buh = fh, (4.1.5)
where fh is the n-dimensional vector with components f-1 = fv fdz.
Let u Â£ fi"Q2^(fl;ro) and uh Â£ Sq denote the solutions of (2.3.4) and
(3.1.1), respectively. Since 2To2^(fi;I?o) C C (fl), we may define the linear
interpolant uj of u in Sq as follows: ttj Â£ 5q such that uj(zi) = u(zi), 1 <
i < m. Our central aim is to estimate the discrete H1 seminorm of the
discretization error
e = u uh.
To do this, we will make use of its discrete counterpart
e
h
Uj uh
and the interpolation error
ej = u uj[.
Denote
= {{*,j} G u : I'Tijl Â£ 0}.
Our first lemma develops a basic error estimate which establishes convergence
of the FVE discretization.
20

Theorem 4.1.1. Assume that B satisfies (4.1.3). Then
4 h (Me/))2
a2 .
Proof. From (2.3.4) and (3.1.1) we have
Bu = Buh.
Hence, from the linearity of B, we have
Be*1 Bej.
(4.1.6)
Note that e(zj) = eft(zj), 1 < i < m, and that b{j(ej) = 6ji(ej) for all
{i,j} 6 u;. Thus, by (4.1.3), it follows that
I |2 | h|2
0=21e!i,nk ~ a2\e li,nfc
1=1
= X eh(Zi) X Me/)
i=l
= X ehizi))bn(ei)
{i,i}Â£u o
< left|i,n* ( X
\{i,j}Gui0
This proves (4.1.6) and, hence, the lemma. |
By the Schwarz inequality and Sobolev trace imbedding theorem, it is
easy to see that each 6jj(-), {i, j} G is a bounded linear functional defined
on IT1 (FT' U K"), where K' and K" have a common face Zij. Therefore,
21

Theorem 4.1.1 and the interpolation theory in the Sobolev space imply con-
vergence of the FVE discretization. Furthermore, the simple, yet crucial,
inequality (4.1.6) shows that the problem of estimating the discretization er-
ror u Uh in the discrete H1 seminorm is reduced to a problem of bounding
interpolation error, which is acted on by bounded linear functionals. This we
treat in the next section.
4.2 Error Estimates in the Discrete H1 Seminorm.
Let E{j C R2 denote the closed convex hull ofjijUZij (see Figure 4.2.1).
For each {i,j} E a; and K E Th such that Eij fl K ^ 0, assume that E{j fl K
is affine-equivalent to a reference triangle E C R2 as follows: there exists an
invertible mapping Fijtx : R2 R2 of the affine form
Fij,K{z) F>ij,Kz + dijtK
such that Eij fl K = Fij,K{E). Let
7 = Fij^inj ^ K)
and define the linear functional fij,K by
fij,K(v) = - (v vj)) liijds, (4.2.1)
J -a; n K
where vj is the linear interpolant of v in Sq. Let
Pk = span{p : p(x,y) = xqyr, q,r > 0, 0 < q + r < k},
the set of polynomial of degree k. Then it is obvious that the linear functional
fij,K vanishes on Pi:
fij,K(v) = 0, Vu E Pi
(4.2.2)
22

For the symmetric control volume case, Eij is a rhombus (as in Figure 4.2.1).
Assume that each Eij is affine-equivalent to a reference rhombus E C R2 as
follows: there is an invertible mapping Fij : R2 R2 of the affine form
F DijZ "b dij
such that Eij Fij(E). Let
i = and z = Kri1(Zij)-
Without loss of generality, suppose 7 and Z lie on the x and y axes, respec-
tively. Define the linear functional fij by
fij(v) = bij(v -/) = -/ (4v( vi)) Hds
J-fij
where uj is the linear interpolant of v in Sq. We then have the following
stronger result.
Zj
Figure 4.2.1. Sample rhombus Eij (dotted lines).
23

Lemma 4.2.1. Assume that the matrix A is constant on 7ij and that
Eij is affine-quivalent to the reference rhombus E. Then for the case of sym-
metric volumes, the linear functional fij defined by fij(v) = fij(v) vanishes
on P 2.
Proof. Let v(z) = v(z) and vi(z) = vj(z). Then
/(*) = / Ii"ii2(^r/v( */)) (
where hij = Dfj1 if ij and nij = Apparently, fij(v) vanishes on P\.
For any v E P2 > v may be represented by
v'= v + (Atz,z),
where A\ is a 2 x 2 symmetric constant matrix and v G Pi- By the linearity
of fij, yu = 2Aiz and J. sjvids = 0 for v = (A\z,z). We thus have, for any
v G P21 that
= 0.
Hence, the lemma is proved. |
Let E be any triangle (or rhombus), the respective 7 and Z be any one
side and its median (or diagonal) of E, and ~n be the unit vector which is
orthogonal to 7. Let
h,E = diam(F?)
and
pE = sup{diam(C) : C is a circle contained in E}.
24

Assume there exists a constant cte such that
h,E < cte\Z\ and h,E < ctePe
(4.2.3)
Define the linear functional / by
f{v) = f{A V (u vj)) lids,
J 7
where uj is interpolant of u in Sg. We then have the following estimate of
\f(v)\-
Lemma 4.2.2. Assume that ||.<4||2 is bounded on E, E satisfies (4.2.3),
and E is affine-equivalent to a reference element E C R2. Suppose that the
linear functional / defined by f(v) f(v) vanishes on Pv~i for some v > 2.
Then, for all v Â£ To), we have
\f(v)\ < c'maxze7||A||2h^ 1\v\VjE, (4.2.4)
where c' is a constant independent of h.E-
Proof. Let v{z) = v(z), vj(z) = uj(z), and A(z) = A(z). Then
f(v) = f(v) = ~ j IHh(AD~t\/(v uj)) (L>n)|^Jds,
where n = D;?~n and n is the unit normal vector with the same direction as
13
h. Since ||n||2 = 1, by using the Cauchy-Schwartz inequality and the Sobolev
trace imbedding theorem, we have
< c1|7|-^maxzeT||A(z)||2||L>-1||2||Â£>||2|7| ||v u/H^,
25

where c\ is a constant independent of v. Prom the Bramble-Hilbert lemma,
we have
|/(v)| < cica|7| 2 maxzÂ£l\\A(z)\\2\\D Il^ll^lhItI | i|fÂ£
< c1C2C3\'y\~*maxzey\\A(z)\\2\\D-1\\l\\D\\2+1\'Y\\det(D)\~3\v\u,E.
Let
p sup{diam(C) : C is a circle contained in E},
h = diam(.E), and |2j?| and \E\ be the areas of E and E, respectively. Then
(see [8])
l-Dlla <
h,E
a J
P
|E|
ID~
h
2 <
|det(D)| = and |E| = cA\Z\\i\,
where C4 = |sin0o or and 6q is the interior angle of E between the line
segments Z and 7. These facts and (4.2.3) imply that
l/WI = l/()l
h
>p) mU|Z|l7l
\V\u,E
< c'max,e7||.A(z)||2fcÂ£ 1\v\VjE
where
c' = cic2c3c~ = o-(2+y)|7|H2|E|^/5_(l/+1).
This proves the lemma. |
Theorem 4.2.1. Assume that a{j(z) E W100(ft), 1 < i,j <2, and
u G H{u)(n), v = 2 or 3. Suppose that FVE operator B is uniformly elliptic
on 5* and that the triangulation Th and the control volumes Vh are regular.
Then we have:
26

(1) for the general case,
leli,nfc ^ c/i|u|2)n;
(2) for the case of essentially symmetric control volumes,
leli,nfc < chf |M|3,n;
(3) for the case of symmetric control volumes,
leli,n* < c/i2||u||3,n-
(4.2.5)
(4.2.6)
(4.2.7)
Here, c is a constant independent of the mesh size h = max^gj-i hx
Proof. (1) By Theorem 4.1.1 and Lemma 4.2.2, we have

1
a2
E bU*t)
(t,i}eu>0
1
2
<
V2
2
S ( / (A V ei) ~rtijds)2
{i,j}Eu0 RET* JfHnK
<
V2
2
[ Yj (c'max2g7/.
+ (c'max2e7 \\A\\2hEn \u\2jEn)2}2.
{i,j} Eu>0
1
2
(4.2.5) is thus proved with c = ^-maxz
(3) For convenience, we drop the subscripts ij. Let A = A(z) where z is
the midpoint of Z. Then
f(u) =h+I2,
where
h = f {{A- A)\7 {u- UI))
J y
n
ds
27

and
I2 = I {A V (u uj)) ~n ds.
J -y
Since aij(z) Â£ W1,00(f2), 1 < i,j < 2, then
max,e7||A A\\2 < c"hE,
where c" is a constant independent of hE. It follows from Lemma 4.2 that
|Ji| < c'ch2E\u\2,E
and
l^l < c,||-^[||2^bI'u|3iB-
(4.2.7) is now proved with c = ^-max{c", maxjen||.<4||2}.
(2) Let w : Eij fl K C fi for some K Â£ Th}. By
(1) and (3) we know that
li,nfc
< -
a2
E + E (M<=/))2
{i.ijew! {i,j}Gui\ui
1
2
(4.2.6) thus follows from the observation that
IMl3,n\n IMI3>n
and that
Ma.fi ^ cfci||u||3,n,
where c is a constant independent of the mesh size h. |
28

4.3 Sufficient Conditions for Uniform Ellipticity of the FVE Oper-
ator B.
In the previous section, we established error estimates for FVE under
the assumption that the FVE operator B is uniformly elliptic, conditions
for which we discuss in this section. For the case that A is a multiple of
the identity, Proposition 4.3.1 gives a sufficient condition which holds for the
control volumes defined in Section 3.3, but which rests on the mesh size.
For diagonal A, a sufficient condition which does not depend on the mesh
size is given in Lemma 4.3.1 which holds for the control volumes related to
circumcenters. This section finishes with a sufficient condition which holds
for the control volumes associated with circumcenters and the case that A is
not diagonal.
Proposition 4.3.1. Assume that A a(z)I and that it satisfies con-
dition (2.2.2). Then there exist an ho > 0 and a constant a > 0, dependent
only on ho and aj, such that, for all h < ho, (4.1.3) holds with constant
2 = ol. Furthermore, if a(z) = 1, then (4.1.3) holds with 0-2 = 1 for any
mesh size h > 0.
The proof of this proposition is just a straightforward consequence of
the Lemma 3 in [3] and its analogue. For the sake of the completeness, we
include a proof here.
Proof of Proposition 4.3.1. For any v E 5q let denote the
usual nodal basis for satisfying
i(zj) = 6ij, Vzj 6 tth.
By direct calculation, it is easy to show that (see [3])

By multiplying v(zj) on both side of the above equality and taking the sum
from 1 to n, we have
71 p
y~](Bv)iv(zi) = / yu \jvdx.
i= i Ja
The proof for the case that a(z) = 1 is complete by noting that
Mi fifc = / Vuds, Vu G 5}.
./n
The rest of the proof follows by the same argument and the following equality
(see [3])
I a y v ~n ids = (1 + O(h)) I a y v yud, Vu G ,i = 1,
Jn
I
Lemma 4.3.1. Let the condition (2.2.2) hold and assume one of the
following conditions:
(i) ai = 2 = a in ft.
(ii) Each ~n ij, {i,j} G wo, is parallel to one of the coordinate axes.
Then (4.1.3) holds with 2 = ati-
Proof. For any v G we have
n n
^2v(zi){Bv)i = J2v(Zi) ^2 MM
i=l i=l
= Kz0 v(zj))1>ij(v).
{i,j}Gv
Suppose (i) holds. Then
MM = (v{Zi) v{zj))j^ I ai(z)ds,
I Vij
30

where ai(z)ds > aids = 'a:i|7ij|, so (4.1.3) follows with <22 = i.
Suppose (ii) holds. Without loss of generality we assume li ij is parallel
to the y axis: ~nij ^
Then
bij(v) = / a2(z)^-ds = V^Zl\7 f a2{z)ds,
Jjii dV \Zij\ J7ij
where a2(z) > ck 11O'j[. (4.1.3) again follows with a2 = aj. |
Condition (ii) in Lemma 4.3.2 will be satisfied, for example, by a cross-
product mesh where the triangles are obtained by dividing each rectangular
mesh cell in two triangles, as in Figure 4.3.1. Note then that iv0 7^ lo.
Figure 4.3.1. Sample cross-product grid
and its triangulation.
We now give a sufficient condition for the case that A is not diagonal.
However, for this theory we restrict our attention to the case that the control
volume is associated with circumcenters.
For each element K E denote the vertices, side segments, and
control volume segments of K by i, Zi and 7j, respectively, and let ~n i be
31

2
Figure 4.3.2. Vertices a{, side segments Z{, control volume segments
7i (dotted lines), and unit normal vectors ~n j.
the unit normal vector on 7i, i = 1,2,3 (see Figure 4.3.2). We first establish
(4.1.3) for the case that A is constant.
Lemma 4.3.2. Suppose that the matrix A is constant on each K Â£
UhTh and that it satisfies the uniformly ellipticity condition (2.2.2). If each
element is either a right or an isosceles triangle, then B is uniformly elliptic
with constant 0:2 = a\cr~l.
Proof. Note that
n
J2v{zi)(Bv)i = Y ~ vizi))bij(v)
= Y l^jl(Vt>,"rWj) Y / (A \/v, li^ds
0 KeuhTh'''ri>nK
= Y WK>
KeuhT*
where
3
wk = Y l^*llT*l(Vu>"rci)Ci4- V
32

Suppose that the element K is isosceles. Without loss of generality, assume
that the vertex angle, which is the angle formed by two equal sides, is 6.
Since

n 3
n i + n 2

then
3
wk = {A yi;,y^lZf-H7tl(VT?,~ra j)~n j)
i=l
= (A Vo.KIZjIIt,! + V2)K,
a
a
+ [
|23ll7>l(V,'H,i) + (|Z2||7!|+^l!i)(V. ^2)1^2),
a
a
where a = ||Wi + 1^21|2 = 2(1 + cos(Wi,W2)) 2(1 cosO). We now
proceed to obtain a lower bound on wk- First note that, since ~n 1 and ~n 2
are linearly independent in R2, we may let
S?v = Vi n 1 + U2 n 2-
But then
[s/v,~n \) = v\ v-zcosO and (S7v,~n 2) = vicosO + v2.
Solving these two equations for v\ and i>2 yields
1
and
*>i = -t-5t[(V n 1) + (V^, n 2)cos0]
sm*v
V2 = y7[(Vu>^i )c<>s0 + (V^, rai-
sin'4#
33

Note that IZ3H73I = 2cos6\Z\ H711 = 2cos0\Z2 | (721 Then wk {A S7 v,q)
where

a
+ + (|23||T2| +
a
. .. I c r / 2 COS0 . , v . 2iCOS0 . - y n y
I^iIItiKK1 + =7;-------m)(V'wJ w 1) + ^n 2)] n 1
2(1 cosO)
2(1 cos#)
r 2cos0 . 2cos0
+ ------o\ (V^j n 1) + (1 + ^------^r)(V*b n 2)\ n 2}
"2(1 COS0)
IZjIItiI
2(1 cosO)
{[(V'Uj'rai) + coa^vv,^)]^!
1 COS0
+ [cos8(s/vi~n 1) + (yy, "^2)] ^2}
. , sin20
|Zl|WT^?v'-
Hence,
wk {A\7 v,q)
. .. . am20 , .
= 1-^iliTil! _C0^(-A VPVP)
q777^fl
-ai|Zlll7llr^?(v1,,v,)-
In other words, we can bound wk from below by replacing A by a*. Return-
ing to the definition of wk, this means that
wk > y](Vtt,'nN)(yu,n>j)|^l|7i|
1=1
= oli[{v{z2) v(z1))2j^\ + {v(z3) v{z2))2 -7^
\Zi\
+ (v(Zl) v(z3))2 j^y]
l^|
> aio- 1[(v(2) -t>(*i))2 + (v(z3) ~v{z2)f + (w(zi) v(z2))2],
34

where cr is from (3.2.1). For the case of that the element if is a right triangle,
the above inequality for wk follows from observations that
|T3| = 0, |Zi||7i| = |^21 |T21, and q = \Z2 ]|ti I V
These prove the lemma. |
Theorem 4.3.1. Consider the case that the control volumes are formed
from element circumcenters. Assume that aij(z) Â£ W1,00(fi), 1 < i,j < 2,
and that each triangle K Â£ Th is either right or isosceles. Then there exist
an ho > 0 and a constant a > 0, dependent only on ho and cti, such that,
for all h < ho, B is uniformly elliptic, i.e., B satisfies (4.1.3) with constant
a2 ~ a.
Proof. Let A(z) = A(zjc) for all z Â£ K C Th, where zk is the circum-
center of triangle K. Since a{j Â£ W1,oo(0), 1 < i,j < 2, then there exists a
constant c\ such that, for all if Â£ Th,
max || A(z) A(,z)|| < c\h.
zÂ£K
Letting
then
wk
X)lZi$$vv,lii) / ((A A) V v,~ni)ds, i= 1 \wk\ <^2\Zi\\ji\\\ V v\\2 m&x\\A A\\ ' zÂ£K 3 < |Zi||7*||| Vw||2 1=1 3 < c1c2h^2\Zi\\'>fi\(s7v,'n i)2. ii 35 The last inequality follows from the fact that there exists a constant C2 > 0 such that, for any K Â£ Tfe, 3 3 ^\Zi\\li\ < C2^\Zi\yfi\coa2{^v^lti). i=l i=l We then have ^v(zi){Bv)i i= 1 ^ ] l^iiKV^i n ij) ^ ] / (A V n ij)ds {i,j}two KÂ£Th J~fi* + ^ l^ijKvv, ij) I ((-A '4-) V n ij)ds {ij}So 7*' = + wk) KeTk > aio--1 -c^hM^. Hence, the theorem follows from chosing ho such that, for all h < ho, a = ai 0. I 36 Chapter 5 Numerical Integration In practice, even if the functions aij and / have simple analytical expres- sions, integrals of aij and / which appear in the FVE coefficient matrix are seldom computed exactly. It is typical that they are approximated through the process of numerical quadrature, the effect of which we discuss in this chapter. In Section 5.1, we describe finite volume element method with nu- merical integration. After establishing a basic error estimate, which is an extension of Theorem 4.1.1, we find sufficient conditions which ensure that the order of convergence in the absence of numerical integration is unaltered by the effect of numerical integration. 5.1 FVE with Numerical Integration. Denote the basis of the space S% by {(^(z)}[L-[, where is the hat function associated with zi, that is, (/>i(z) is linear on each triangle element K E Th and i(zi) Su for all 1 < l,i < n. Then solving the corresponding discrete problem amounts to finding the coefficients ui, 1 < l < n, of the expansion n uh = y^uifa. i=i These coefficients form a solution of the linear system n J= fi, 1 < i < n, (5.1.1) l=i where Let n ij be the unit outward normal vector on 7ij, which is associated with V{. Then, for any v Â£ , we have / (A v v) ~nijds jEwi "W = XXX) / (AS7 v)-liijds jcerfc Jyi> nir = X) XI (/ Ads)s/v-liij. jEui KÂ£Th nK The last equality follows from the fact that and n ij are constant on 7ij n K. Therefore, (4.1.4) can be rewritten as (Bv)i = X] Â£ (/ Ads) V v (5.1.3) jÂ£ui KeT*- Jy^K Note that the integral of a matrix M = (mij)nXn is defined componentwise by j Min = (j m 13 dfj,)r In practice, even if the functions dij and f have simple analytical expres- sions, the integrals J7..nK A(z)ds and JvnK f[z)dz which appear in (5.1.3) and (5.1.2), respectively, are seldom computed exactly. To study the effects of numerical integration, we will assume that dij(z) and f(z) are defined everywhere on the respective {dVi : i 1, ...,m} and Cl. For each 1 < i < n, j Â£ u)i, and K Â£ Th, let Fij,K z Â£ K > Fij,K(z) = DijlKz + dij^K (5.1.4) be the invertible affine mapping from K onto K. Assume without loss of generality that the Jacobian of the mapping Fijis positive definite. Let 38 7 be such that Fij^ifl) 7ij D K and V be such that Fij^iV) ViP\ K. Then Yfij n K\ SyZ )WB iji^nK and (5.1.6) f A(z)ds = ^ f A(z)ds J-yiinK 171 Jit (5.1.5) / f(z)dz =det(DijjK) l f(z)dz JVinK Jv where the hat quantities are defined by the usual correspondence, i.e., A(z) = A(z) and f(z) = f(z) for all z = Fijtjc(z), z G K. In other words, computing the integrals /7..nKAds and Jv.nK fdz amounts to computing the respective integrals f. A(z)ds and J^.f(z)dz. Let (Z = l,...,Xi) and j3t ^ (Z = 1,...,X2) be the quadrature coefficients, and rji^ (Z = l,...,Lj) and rj^y (Z = 1,...,L2) be the quadrature points. Assume that /3zi7 and p- are strictly positive, and rji^ G 7, rji y G V. Then the integrals J\ A(z)ds and fv f(z)dz are approximated by quadratures as follows: f Li / A{z)ds ~ Jtr 1=1 and / f(z)dz ~ v V 1_i For 1 < Z < Li, define Itij n K | (5.1.7) (5.1.8) =i ItI and VimnK = FijlK{viA) (5.1.9) and, for 1 < Z < L2, define PiMnK = det[DijtK )/3ly and T]i,VinK = FijtK(Vitv)- (5.1.10) 39 Then the quadrature approximations over element K are given by . L i. I A(z)ds PlntjnKA{riinijnK) (5.1.11) J~i uC\K l=1 and / f{z)dz ~ V pi,Vi mcfiviMMc)- JVinK j_j (5.1.12) Accordingly, we introduce the following quadrature error functionals: for any 1 < i < n, j E Wi and each K Â£ Th, define f Ll RyiinK(A) = / A(z)ds ,~tij ni J-yijnK l=1 r Ll Rj(A) = I A(z)ds (5.1.13) (5.1.14) and f Lj Rvinicif) = / f(z)dz '^2,Pi,vir\Kf{rii,Vir\K), JViCK l=1 %(/) = / -J2Pi,vf(\v)- Jv ,=1 These are related by R^nK{A) I'yij n K ItI and Rvinicif) = det{DijiK)Rv(f). Let L 2 fi = 5^ fi,K = 'YjPl,vinKf{'rn,viC\K) Kerh Kerh 1=1 (5.1.15) (5.1.16) (5.1.17) (5.1.18) (5.1.19) 40 and define the linear operator B : Sq * -R by its elements: Li (Bv)i = X X 1 jew KÂ£Th 1=1 As in Section 3, we say B uniformly elliptic on if there exists a constant h h a > 0 independent of the space S0 such that, for all v E S0, n ^2v(zi){Bv)i > a||;iflk. (5.1.21) i1 Now, instead of solving the linear system (5.1.1) with the coefficients (5.1.3) and right-hand sides (5.1.2), we solve the modified linear system n = l<* 1=1 with B and / defined in the respective (5.1.20) and (5.1.19). 5.2. The Effect of Numerical Integration. For our subsequent analysis, rather than working with the matrix sys- tem (5.1.22), it will be more convenient to consider the following equivalent formulation of the discrete problem: Find uh E Sq such that Buh = fh (5.2.1) where fh is the vector in Rn with components //*, 1 < i < n. For any v E Sq, define the discrete L2 norm by Mo,ft*=( X y2(Zi))^ (5-2-2) {i,j} 41 For any vector w Â£ Rn, define the l2 norm by n = QCwi)*- (5-2-3) i1 We now have the following basic error estimate. Theorem 5.2.1. Assume that B satisfies (5.1.21). Then W,,#* < i{c'|/* /*!,+ ( E + [ E ( E (fimnirWV/) ->?)]*}. (5.2.4) {i,j}Gu)0 KÂ£Th where c' is a constant dependent only on the domain 12. Proof. By the linearity of B and B, (4.1.5), and (5.2.1), we have {Beh)i = (Buj)i (Buf)i + (Bujji (Bu)i + (Bu)i (Buk)i = ((B BM (Be,)i + (fi //*). From this, (5.1.21), and the fact that e(zj) = eh(zi), 1 < i < m, it follows that d|e 2 _ i,nfe - ale h\2 _ li,nk i=l < IE - B)u,)iI + IE e^ZiXBesU 1=1 *=1 + iEe',(2i)(/f-/f)i. i1 (5.2.5) 42 According to (5.1.20) and (5.1.3) and since ~n ij = ~n ji, we then have | Â£ --BWM i1 iteh(zi)E E(/ Ada~ i= 1 jÂ£wi KÂ£Th JHiriK Li -'YlPlnijnKA(T)in.jnK)) Vuj'ii I l=i | (e (zt) e (zj)) E-/ nir(-d-) V ul' 71 I {*ii}e<"o KÂ£Th <|efe|i,^[ EE { ^2 RliinK{A)s7uI-ltij)2]^. {i,j}eu0 Ker^ (5.2.6) The last inequality follows from the Cauchy-Schwarz inequality. ^From the proof of Theorem 4.1.1, we know that Â£e(*i)(BeJ)i|<|e\jl.( Â£ ^(ej))i. (5.2.7) *=1 {*ij}6o By the Cauchy-Schwarz inequality and the Poincare-Friedrichs inequality (see [8]), we have i Â£>*(*)(/?-/f)i Z=1 ^ leftlo,n^l/A fhfo.n'1 (5.2.8) where c' is a constant dependent only on the domain fi. (5.1.17) now follows from inequalities (5.2.5), (5.2.6), (5.2.7), and (5.2.8). Hence, the theorem is proved. | 43 Estimating the discretization error now amounts to bounding the three terms on the right-hand side of inequality (5.2.4). We can use the assump- tions and proof of Theorem 4.2.1 to show that the second term, Â£ bUei) {i,j}Gv o is 0{h?), where v 1 in general, v = | for essentially symmetric control volumes, and v = 2 for symmetric control volumes. The other two terms are due to numerical quadrature. Thus, our present objective is to give suffi- cient conditions on the quadratures which ensure that the effect of numerical integration does not decrease these orders of convergence. Lemma 5.2.1. Assume that, for some integer v > 1, the quadrature error functional Ry(v) vanishes on Pu-i(V). Then, for any q > ^ and any / e wv{Vi n K), |-Rvinif(/)I < chvK\Vi n K\1~?\f\ViqivinKi (5.2.9) where jD K\ is the measure of V{ (~1 K and c is a constant independent of K E Th and hj(. Proof. / Â£ WI/9(Vj fl K) implies that / Â£ Wv'q(V) and q > ^ implies that Wv'q{y) is imbedded into C(V). It follows from the Sobolev imbedding theorem that l-^V(/)l Cll/lo,oo,t>' C2ll/lli/, By the Bramble-Hilbert lemma, we have \Ry(f)\ 3\f\v,q,V 44 Now (5.2.9) follows from the facts that \f\v,q,v ^ c4Dij,K\\I'\det(DijjK)\ \f\u,q,v{nK, and \D. ij,K | \det{DijiK)\ = \Vi n K \v\ RviMcif) = det(Dij,K)Rv(f), where |V"| is the measure of V. Hence, the lemma is proved. | Without loss of generality, assume that the line segment 7 lies on the * axis. We omit the proof of the next lemma since it is virtually the same as that for Lemma 5.2.1. Lemma 5.2.2. Assume that, for some integer u > 1, the quadrature error functional Ry(v) vanishes on P_ 1(7). Then, for any v 6 Wv,00(yijnK) (1 < i < n, j Â£ u>j), we have liJ-mnifMI < chp-'lvl^nK, (5.2.10) where c is a constant independent of K Â£ Th and Hr. Note that \^-\ and |^-| are both bounded by chK2 ||u||2,^njr for all z G K. According to Lemma 5.2.2, we then have that \RyijnK(A) V ui < 5^(l-R7n*(ii)l|-^-| + \R-/ijnK(a2i)\\j-$$
l-1 V
2
< < E | |i/,oo,7jj nK 11 "a 112,E{j n K1
l,k=l
45

where c absorbs various constants. Therefore, application of the Cauchy-
Schwarz inequality implies that
X (RiunK{A) V uT) ~nij
KKÂ£Th
< c X ((-^nif^) V /) ^ij)2
KÂ£Th
RET* l,k=1
2
< ch2,/+1 X X lajfc^,oo,7iinldl'lill2,Â£;iJ-niC
l,kl
Hence, the third term on the right-hand side of inequality (5.2.4) is bounded
according to
XI ( (^7 u< irerfe
2
< chl,+ IMh.n E |ifc |i/,oo,n
l,k=l
(5.2.11)
To estimate the first term on the right-hand side of (5.2.5), note from the
definitions of fj*, //*, and Rv{nK{f) that
ft ft = Â£ Rnmrtf).
Kerh
46

Since \Vi fl K\ < h2, then by Lemma 5.2.1 and the Cauchy- Schwarz inequa-
lity, we have
E lflWnK(/)l
KeTh
< chV+2^~^ \f\v,q,V[nK
KeTh
Kerh
= cfc-'+20-i>|/|,v,.
Thus, since n < ch 2, we have
(E\f> ~ ft I2)1 S E l/lv,g,V( ) 2
2=1
< chI'+2(1~?)|/|I,)g)nn35r
2=1
< cfe-+1|/U,,,n.
Hence, the first term on the right-hand side of (5.2.4) is bounded according
to
Ifh ~ fh\ofn* < chv+1\f\v,q,n- (5.2.12)
Combining inequalities (5.2.4), (5.2.11), and (5.2.12), we have our final
result.
Theorem 5.2.2. Assume that aij(z) Â£ WI/,00(n), 1 < i,j < 2, u > 1;
f(z) Â£ W1,5(fi) with q > 2; and u Â£ IT^(fi), v = 2 or 3. Suppose that B is
uniformly elliptic on Sg and that Th and Vh are regular. Suppose also that
the quadrature error functionals Rj(v) and R-^(v) vanish on the respective
Po(7) and Po(V). Then we have:
47

(1) for the general case,
2
|e|i,ftk i,fc=l
(2) for the case of essentially symmetric control volumes,
2
leli,ft* < ch*{h*\f\i,q,n + IM|3,n + ||tt||a,n Mi.oo.n);
l,kl
(3) for the case of symmetric control volumes,
2
leli,nft < ch2(\f\i,q,n + IMkn + fc*IM|2)n lt*lalooIn)-
l,kl
Here, c is a constant independent of h.
(5.2.13)
(5.2.14)
(5.2.15)
48

References
[2] B. R. Baliga and S. V. Patankar, A new finite-element formulation for
convection-diffusion problems, Num. Heat Transfer 3(1980), 393-409.
[3] R. E. Bank and D. J. Rose, Some error estimates for the box method,
SIAM J. Numer. Anal. 24(1987), 777-787.
[4] J. H. Bramble and S. R. Hilbert, Estimation of linear functionals on
Sobolev spaces with application to Fourier transforms and spline inter-
polation, SIAM J. Numer. Anal. 7 (1970), 112-124.
[5] Z. Cai, On the finite volume element method, submitted to Numer.
Math.
[6] Z. Cai, J. Mandel and S. McCormick, The finite volume element method
for diffusion equations on general triangulations, SIAM J. Numer. Anal.,
to appear.
[7] Z. Cai and S. McCormick, On the accuracy of the finite volume element
method for diffusion equations on composite grids, SIAM J. Numer.
Anal. 27:3(1990).
[8] P. G. Ciarlet, The Finite Element Method for Elliptic Problems, North-
Holland, Amsterdam, 1978.
[9] R. E. Ewing, R. D. Lazarov, and P. S. Vassilevski, Local refinement
techniques for elliptic problems on cell-centered grids, Univ. Wyoming
E.O.R.I. rep. no. 1888-16.
[10] W. Hackbusch, On first and second order box schemes, Computing
41(1989), 277-296.
[11] B. Heinrich, Finite Difference Methods on Irregular Networks, Birkhau-
ser Verlag, 1987.
49

[12] J. Kadlec, On the regularity of the solution of the Poisson equation on
a domain with boundary locally similar to the boundary of a convex
domain, Czechoslovak Math. J. 14(1964), 386-393.
[13] H. O. Kreiss, T. A. Manteuffel, B. Swartz, B. Wendroff and A. B. White,
Supraconvergent schemes on irregular grids, Math. Comp. 47(1986),
537-554.
[14] C. Liu and S. McCormick, The finite volume element method (FVE) for
planar cavity flow, Proc. 11th Internat. Conf. on CFD, Williamsburg,
VA, June 28 July 2, 1988.
[15] T. A. Manteuffel and A. B. White, The numerical solution of second-
order boundary value problems on nonuniform meshes, Math. Comp.
47(1986), 511-535.
[16] S. McCormick, Multilevel Adaptive Methods for Partial Differential E-
[17] S. McCormick and J. Thomas, The fast adaptive composite grid method
(FAC) for elliptic boundary value problems, Math. Comp. 46(1986),
439-456.
[18] W. J. Minkowycz, E. M. Sparrow, and J. E. Schneider, eds, Handbook
of Numerical Heat Transfer, John Wiley, New York, 1988.
[19] M. Nakata, A. Weiser, and M. F. Wheeler, Some super convergence re-
sults for mixed finite element methods for elliptic problems on rectangu-
lar domains, in The Mathematics of Finite Elements and Applications
V-MAFFLAP 1984, J. R. Whiteman, ed., 1985, 367-389.
[20] J. Necas, Les methodes Directes en Theorie des Equations Elliptiques,
Masson, Paris, 1967.
50

[21] A. Oganesjan and L. A. Ruchovec, Variational Difference Methods of
Solving Elliptic Equations (in Russian), Erevan, Izd. AN Arm. SSR,
1979.
[22] A. A. Samarskii, R. D. Lazarov, and L. Makarov, Finite Difference
Schemes for Differential Equations with Weak Solutions (in Russian),
Moscow Vissaya Skola, Moscow, 1987.
[23] G. Voronoi, Nouvelles applications des parameters continus a la theorie
des forms quadratures, J. Reine angew Math. 134(1908), 198-287.
[24] M. Zlamal, On the finite element method, Numer. Math. 12(1968),
394-409.
51