<< Ļšåä. ńņš. ńņš. 36(īįłåå źīėč÷åńņāī: 59)ĪĆĖĄĀĖÅĶČÅ Ńėåä. ńņš. >>
C
m CMl .
C ā’1
Here CMk is the number of operations for an iteration with the iteration
method Ī¦k .
In the model problem of the Friedrichsā“Keller triangulation with uniform
reļ¬nement we have C/(C ā’ 1) = 4/3 and C3 = 2. For Ā· = Ā· 0 as basic
norm, Ī± = 2 is a typical case according to Theorem 3.37. The existence of
the constant C2 will hereby ļ¬nally be ensured consistently by the condition
(5.103), observing (5.100). Assuming also that the constants C1 , C2 , Pl
are āsmallā and the iteration method has a āsmallā contraction number ,
only a small number of iterations m is necessary, in the ideal case m = 1.
At least in this situation we can count on only a small increase of the
necessary eļ¬ort through the process of nested iterations, which provides an
Ė
āappropriateā approximation xk on all levels k of discretization.
Finally, it is to be observed that the sequence of the discrete problems
has to be deļ¬ned only during the process of the nested iteration. This oļ¬ers
the possibility to combine it with a posteriori error estimators as discussed
in Section 4.2, in order to develop a grid Tk+1 on which the discrete problem
of level k + 1 is determined, on the basis of xk as a reļ¬nement of Tk .
Ė
6
The Finite Volume Method

Finite volume methods are widely applied when diļ¬erential equations in
divergence form (cf. Section 0.5) or diļ¬erential equations involving such
diļ¬erential expressions (for example, parabolic diļ¬erential equations) are to
be solved numerically. In the class of second-order linear elliptic diļ¬erential
equations, expressions of the form
Lu := ā’ā Ā· (K āu ā’ c u) + r u = f (6.1)
are typical (cf. (0.33)), where
K : ā„¦ ā’ Rd,d , c : ā„¦ ā’ Rd , r, f : ā„¦ ā’ R .
The corresponding āparabolic versionā is
ā‚u
+ Lu = f
ā‚t
and will be treated in Chapter 7.
First-order partial diļ¬erential equations such as the classical conservation
laws
ā Ā· q(u) = 0 ,
where q : R ā’ Rd is a nonlinear vector ļ¬eld depending on u, or higher-order
partial diļ¬erential equations (such as the biharmonic equation (3.36)), or
even systems of partial diļ¬erential equations can be successfully discretized
by the ļ¬nite volume method.
In correspondence to the comparatively large class of problems that can
be treated by the ļ¬nite volume method, there are rather diļ¬erent sources
256 6. Finite Volume Method

1960 Forsythe and Wasow computation of neutron diļ¬usion
1961 MarĖuk
c computation of nuclear reactors
1971 McDonald ļ¬‚uid mechanics
1972 MacCormack and Paullay ļ¬‚uid mechanics
1973 Rizzi and Inouye ļ¬‚uid mechanics in 3D
1977 Samarski integro-interpolation method,
balance method
.
.
.
1979 Jameson ļ¬nite volume method
1984 Heinrich integro-balance method,
generalized ļ¬nite diļ¬erence method
.
.
.
1987 Bank and Rose box method
.
.
.
Table 6.1. Some sources of the ļ¬nite volume method.

originating mainly from practical applications. Some of these sources are
listed in Table 6.1. In contrast to ļ¬nite diļ¬erence or ļ¬nite element methods,
the theoretical understanding of the ļ¬nite volume method remained at an
early stage for a long time; only in recent years has essential progress been
noted.
The ļ¬nite volume method can be viewed as a discretization method of
its own right. It includes ideas from both ļ¬nite diļ¬erence and ļ¬nite element
methods. So in the literature approaches can be found that interpret it as
a āgeneralized ļ¬nite diļ¬erence methodā or rather as a variant of the ļ¬nite
element method. In this chapter, we will consider only equations of the
type (6.1).

6.1 The Basic Idea of the Finite Volume Method
Now we will describe the fundamental steps in the derivation of the ļ¬nite
volume method. For simplicity, we restrict ourselves to the case d = 2 and
r = 0. Furthermore, we set q(u) := ā’K āu + c u. Then equation (6.1)
becomes
ā Ā· q(u) = f . (6.2)
In order to obtain a ļ¬nite volume discretization, the domain ā„¦ will be
subdivided into M subdomains ā„¦i such that the collection of all those
subdomains forms a partition of ā„¦, that is:
(1) each ā„¦i is an open, simply connected, and polygonally bounded set
without slits,
6.1. Basics 257

(2) ā„¦i ā© ā„¦j = ā… (i = j),
(3) āŖM ā„¦i = ā„¦ .
i=1

These subdomains ā„¦i are called control volumes or control domains.
Without going into more detail we mention that there also exist ļ¬nite
volume methods with a well-deļ¬ned overlapping of the control volumes
(that is, condition 2 is violated).
The next step, which is in common with all ļ¬nite volume methods, con-
sists in integrating equation (6.2) over each control volume ā„¦i . After that,
Gaussā™s divergence theorem is applied:

Ī½ Ā· q(u) dĻ = i ā {1, . . . , M } ,
f dx ,
ā‚ā„¦i ā„¦i

where Ī½ denotes the outer unit normal to ā‚ā„¦i . By the ļ¬rst condition of the
partition, the boundary ā‚ā„¦i is formed by straight-line segments Ī“ij (j =
1, . . . , ni ), along which the normal Ī½|Ī“ij =: Ī½ij is constant (see Figure 6.1).
So the line integral can be decomposed into a sum of line integrals from
which the following equation results:
ni
Ī½ij Ā· q(u) dĻ = f dx . (6.3)
Ī“ij ā„¦i
j=1

Ī½i 2 Ī½i 1

ā„¦i
Ī½i 3
Ī½i 5

Ī½i 4

Figure 6.1. A control volume.

Now the integrals occurring in (6.3) have to be approximated. This can
be done in very diļ¬erent ways, and so diļ¬erent ļ¬nal discretizations are
obtained.
In general, ļ¬nite volume methods can be distinguished by the following
criteria:
(1) the geometric shape of the control volumes ā„¦i ,
(2) the position of the unknowns (āproblem variablesā) with respect to
the control volumes,
258 6. Finite Volume Method

(3) the approximation of the boundary (line (d = 2) or surface (d = 3))
integrals.
Especially the second criterion divides the ļ¬nite volume methods into two
large classes: the cell-centred and the cell-vertex ļ¬nite volume methods. In
the cell-centred methods, the unknowns are associated with the control
volumes (for example, any control volume corresponds to a function value
at some interior point (e.g., at the barycentre)). In the cell-vertex methods,
the unknowns are located at the vertices of the control volumes. Sometimes,
instead of the ļ¬rst-mentioned class a subdivision into two classes, the so-
called cell-centred and node-centred methods, is considered. The diļ¬erence
is whether the problem variables are assigned to the control volumes or,
given the problem variables, associated control volumes are deļ¬ned.
Example 6.1 Consider the homogeneous Dirichlet problem for the Pois-
son equation on the unit square:
ā’āu = in ā„¦ = (0, 1)2 ,
f
u= 0 on ā‚ā„¦ .

Problem variables:
aj2
Function values at the nodes ai
of a square grid with mesh width
aj3 ai aj1
h>0
aj4 Control volumes:
ā„¦i := {x ā ā„¦ : |x ā’ ai |ā < h }
2

Figure 6.2. Problem variables and control volumes in a cell-centred ļ¬nite volume
method.

For an inner control volume ā„¦i (i.e., ai ā ā„¦), equation (6.3) takes the
form
4
ā’ Ī½ijk Ā· āu dĻ = f dx ,
Ī“ijk ā„¦i
k=1

where Ī“ijk := ā‚ā„¦i ā© ā‚ā„¦jk . A closer look at the directional derivatives shows
that
Ī½ij1 Ā· āu = ā‚1 u , Ī½ij2 Ā· āu = ā‚2 u ,
Ī½ij3 Ā· āu = ā’ā‚1 u , Ī½ij4 Ā· āu = ā’ā‚2 u .
i.e. they are just partial derivatives with respect to the ļ¬rst or the second
variable on the corresponding parts of the boundary.
6.1. Basics 259

Approximating the integrals on Ī“ijk by means of the midpoint rule and
replacing the derivatives by diļ¬erence quotients, we have

4 4
ai + ajk
ā’ Ī½ijk Ā· āu dĻ ā ā’ Ī½ijk Ā· āu h
2
Ī“ijk
k=1 k=1
u(aj1 )ā’u(ai ) u(aj2 )ā’u(ai ) u(ai )ā’u(aj3 ) u(ai )ā’u(aj4 )
āā’ ā’ ā’
+ h
h h h h
4
= 4 u(ai ) ā’ u(ajk ) .
k=1

Thus, we obtain exactly the expression that results from the application of
a ļ¬nite element method with continuous, piecewise linear ansatz and test
functions on a Friedrichsā“Keller triangulation (cf. Figure 2.9).
Furthermore, if we approximate the integral ā„¦i f dx by f (ai )h2 , we see
that this term coincides with the trapeziodal rule applied to the right-hand
side of the mentioned ļ¬nite element formulation (cf. Lemma 2.13).
Actually, it is no accident that both discretization methods lead to the
same algebraic system. Later on we will prove a more general result to
conļ¬rm the above observation.
The boundary control volumes are treated as follows:
If ai ā ā‚ā„¦, then parts of the boundary ā‚ā„¦i lie on ā‚ā„¦. At these nodes,
the Dirichlet boundary conditions already prescribe values of the unknown
function, and so there is no need to include the boundary control volumes
into the balance equations (6.3).
A detailed description for the case of ļ¬‚ux boundary conditions will be
given later, in Section 6.2.4; see (6.23).

Example 6.2 We consider the same boundary value problem as in
Example 6.1.

Problem variables:
Function values at the nodes ai
of a square grid with mesh width
h>0
ā„¦i
Control volumes:
Subsquares of the grid

Figure 6.3. Problem variables and control volumes in a cell-vertex ļ¬nite volume
method.
260 6. Finite Volume Method

In the interior of ā„¦, the resulting discretization yields a 12-point stencil
(in the terminology of ļ¬nite diļ¬erence methods).
Remark 6.3 In the ļ¬nite volume discretization of systems of partial dif-
ferential equations (resulting from ļ¬‚uid mechanics, for example), both
methods are used simultaneously for diļ¬erent variables; see Figure 6.4.

. . . ..
O O O O O

. . . . : problem variable of type 1
O O O O O

. . . . : problem variable of type 2
O
O O O O O

. . . .
O O O O O

O O O O O

Figure 6.4. Finite volume discretization of systems of partial diļ¬erential
equations.

Assets and Drawbacks of the Finite Volume Method
Assets:
ā¢ Flexibility with respect to the geometry of the domain ā„¦ (as in ļ¬nite
element methods).
ā¢ Admissibility of unstructured grids (as in ļ¬nite element methods,
ā¢ Simple assembling.
ā¢ Conservation of certain laws valid for the continuous problem
(for example, conservation laws or maximum principles). This
property is important in the numerical solution of diļ¬erential equa-
tions with discontinuous coeļ¬cients or of convection-dominated
diļ¬usion-convection equations (see Section 6.2.4).
ā¢ Easy linearization of nonlinear problems (simpler than in ļ¬nite
element methods (Newtonā™s method)).
ā¢ Simple discretization of boundary conditions (as in ļ¬nite element
methods, especially a ānaturalā treatment of Neumann or mixed
boundary conditions).
ā¢ In principle, no restriction of the spatial dimension d of the domain
ā„¦.
6.1. Basics 261

Drawbacks:

ā¢ Smaller ļ¬eld of applications in comparison with ļ¬nite element or ļ¬nite
diļ¬erence methods.

ā¢ Diļ¬culties in the design of higher order methods (no so-called p-
version available as in the ļ¬nite element method).

ā¢ In higher spatial dimensions (d ā„ 3), the construction of some classes
or types of control volumes may be a complex task and thus may lead
to a time-consuming assembling.

ā¢ Diļ¬cult mathematical analysis (stability, convergence, . . . ).

Exercises
6.1 Given the boundary value problem

ā’(au ) = 0 in (0, 1) , u(0) = 1 , u(1) = 0 ,

with piecewise constant coeļ¬cients

ĪŗĪ± , x ā (0, Ī¾) ,
a(x) :=
x ā (Ī¾, 1) ,
Ī±,

where Ī±, Īŗ are positive constants and Ī¾ ā (0, 1) \ Q :

(a) What is the weak solution u ā H 1 (0, 1) of this problem?
(b) For general āsmoothā coeļ¬cients a, the diļ¬erential equation is
obviously equivalent to

ā’au ā’ a u = 0 .

Therefore, the following discretization is suggested:
uiā’1 ā’ 2ui + ui+1 ai+1 ā’ aiā’1 ui+1 ā’ uiā’1
ā’ai ā’ = 0,
2
h 2h 2h
where an equidistant grid with the nodes xi = ih (i = 0, . . . , N + 1)
and ai := a(xi ), ui :ā u(xi ) is used.
This discretization is also formally correct in the given situation of
discontinuous coeļ¬cients. Find the discrete solution (ui )N in this
i=1
case.
(c) Under what conditions do the values ui converge to u(xi ) for h ā’ 0?
262 6. Finite Volume Method

6.2 The Finite Volume Method for Linear Elliptic
Diļ¬erential Equations of Second Order on
Triangular Grids
In this section we will explain the development and the analysis of a ļ¬nite
volume method of ācell-centredā type for a model problem. Here, ā„¦ ā‚ R2
is a bounded, simply connected domain with a polygonal boundary, but
without slits.

The Voronoi Diagram
By {ai }iāĪ ā‚ ā„¦ we denote a consecutively numbered point set that includes
all vertices of ā„¦, where Ī is the corresponding set of indices. Typically, the
points ai are placed at those positions where the values u(ai ) of the exact
solution u are to be approximated. The convex set
ā„¦i := x ā R2 |x ā’ ai | < |x ā’ aj |
Ė for all j = i
is called the Voronoi polygon (or Dirichlet domain, Wignerā“Seitz cell,
Ė
Thiessen polygon, . . . ). The family ā„¦i iāĪ is called the Voronoi diagram
of the point set {ai }iāĪ .

. . .
.. boundary of ā„¦

. ā¼
.. boundary of ā„¦i

Figure 6.5. Voronoi diagram.

The Voronoi polygons are convex, but not necessarily bounded, sets (con-
sider the situation near the boundary in Figure 6.5). Their boundaries are
polygons. The vertices of these polygons are called Voronoi vertices.
It can be shown that at any Voronoi vertex at least three Voronoi poly-
gons meet. According to this property, Voronoi vertices are classiļ¬ed into
regular and degenerate Voronoi vertices: In a regular Voronoi vertex, the
boundaries of exactly three Voronoi polygons meet, whereas a degenerate
Voronoi vertex is shared by at least four Voronoi polygons. In the latter
case, all the corresponding nodes ai are located at some circle (they are
 << Ļšåä. ńņš. ńņš. 36(īįłåå źīėč÷åńņāī: 59)ĪĆĖĄĀĖÅĶČÅ Ńėåä. ńņš. >>