ńņš. 36 |

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,

important for adaptive 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.

6.2.1 Admissible Control Volumes

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 |