a(u, u) ≥ k0 |u|2 + ±0 u2 dσ ≥ min{k0 , ±0 } |u|2 + ≥ C5 u

u2 dσ 2

1 1 1

˜ ˜

“ “

’2

with C5 := CF min{k0 , ±0 }. Therefore, we obtain the existence and

uniqueness of a solution analogously to Theorem 3.12.

(III) General Case

First, we consider the case of a homogeneous Dirichlet boundary

condition on “3 with |“3 |d’1 > 0. For this, we de¬ne

V := v ∈ H 1 („¦) : γ0 (v) = 0 on “3 . (3.30)

Here V is a closed subspace of H 1 („¦), since the trace mapping γ0 :

H 1 („¦) ’ L2 (‚„¦) and the restriction of a function from L2 (‚„¦) to L2 (“3 )

are continuous.

Suppose u is a solution of (3.12), (3.18)“(3.20); that is, in the sense

of classical solutions let u ∈ C 2 („¦) © C 1 („¦) and the di¬erential equation

¯

(3.12) be satis¬ed pointwise in „¦ and the boundary conditions (3.18)“

(3.20) pointwise on their respective parts of ‚„¦ under the assumptions

(3.13), (3.21). However, the weaker case that u ∈ H 2 („¦) and the di¬erential

equation is satis¬ed in the sense of L2 („¦) and the boundary conditions

(3.18)“(3.20) are satis¬ed in the sense of L2 (“j ), j = 1, 2, 3, under the

assumptions (3.14), (3.22) can also be considered here.

As in (I), according to (3.11),

{K∇u · ∇v + c · ∇u v + r uv} dx +

a(u, v) := ± uv dσ (3.31)

„¦ “2

for all v ∈ V .

= b(v) := f v dx + g1 v dσ + g2 v dσ

„¦ “1 “2

Under the assumptions (3.15), (3.22) the continuity of a and b, (3.25)) and

((3.24) can be proven analogously to (II).

Conditions for V -Ellipticity of a

For the veri¬cation of the V -ellipticity we again proceed similarly to (II),

but now the boundary conditions are more complicated. Here we have for

the convective term

1 1

c · ∇u u dx = ’ ∇ · c u2 dx + ν · cu2 dσ ,

2 2 “1 ∪“2

„¦ „¦

and therefore

1

K∇u · ∇u + r ’ ∇ · c u2 dx

a(u, u) =

2

„¦

1 1

ν · c u2 dσ + ± + ν · c u2 dσ .

+

2 “1 2

“2

3.2. Elliptic Boundary Value Problems 107

In order to ensure the V -ellipticity of a we need, besides the obvious

conditions

1

ν · c ≥ 0 on “1 and ± + ν · c ≥ 0 on “2 , (3.32)

2

the following corollary from Theorem 3.13.

Corollary 3.14 Suppose „¦ ‚ Rd is a bounded Lipschitz domain and “ ‚

˜

‚„¦ has a positive (d ’ 1)-dimensional measure. Then there exists some

constant CF > 0 such that for all v ∈ H 1 („¦) with v|“ = 0,

˜

1/2

¤ CF |∇v| dx = CF |v|1 .

2

v 0

„¦

This corollary yields the same results as in the case of homogeneous

Dirichlet boundary conditions on the whole of ‚„¦.

If |“3 |d’1 = 0, then by tightening conditions (3.32) for c and ±, the

application of Theorem 3.13 as done in (II) may be successful.

Summary

We will now present a summary of our considerations for the case of

homogeneous Dirichlet boundary conditions.

Theorem 3.15 Suppose „¦ ‚ Rd is a bounded Lipschitz domain. Under the

assumptions (3.15), (3.16), (3.22) with g3 = 0, the boundary value problem

(3.12), (3.18)“(3.20) has one and only one weak solution u ∈ V , if

(1) r ’ 1 ∇ · c ≥ 0 in „¦ .

2

(2) ν · c ≥ 0 on “1 .

(3) ± + 1 ν · c ≥ 0 on “2 .

2

(4) Additionally, one of the following conditions is satis¬ed:

(a) |“3 |d’1 > 0 .

(b) There exists some „¦ ‚ „¦ with |„¦|d > 0 and r0 > 0 such that

˜ ˜

r ’ 1 ∇ · c ≥ r0 on „¦.

˜

2

(c) There exists some “1 ‚ “1 with |“1 |d’1 > 0 and c0 > 0 such

˜ ˜

that ν · c ≥ c0 on “1 .

˜

(d) There exists some “2 ‚ “2 with |“2 |d’1 > 0 and ±0 > 0 such

˜ ˜

that ± + 1 ν · c ≥ ±0 on “2 .

˜

2

Remark 3.16 We point out that by using di¬erent techniques in the proof,

it is possible to weaken conditions (4)(b)“(d) in such a way that only the

following has to be assumed:

x ∈ „¦ : r ’ 1∇ · c > 0

(b) > 0,

2 d

{x ∈ “1 : ν · c > 0}

(c) > 0,

d’1

x ∈ “2 : ± + 1 ν · c > 0

(d ) > 0.

2 d’1

108 3. Finite Element Methods for Linear Elliptic Problems

However, we stress that the conditions of Theorem 3.15 are only su¬-

cient, since concerning the V -ellipticity, it might also be possible to balance

an inde¬nite addend by some “particular de¬nite” addend. But this would

require conditions in which the constants CP and CF are involved.

Note that the pure Neumann problem for the Poisson equation

’∆u =f in „¦ ,

(3.33)

‚ν u =g on ‚„¦

is excluded by the conditions of Theorem 3.15. This is consistent with the

fact that not always a solution of (3.33) exists, and if a solution exists, it

obviously is not unique (see Exercise 3.8).

Before we investigate inhomogeneous Dirichlet boundary conditions, the

application of the theorem will be illustrated by an example of a natural

situation described in Chapter 0.

For the linear stationary case of the di¬erential equation (0.33) in the

form

∇ · (c u ’ K∇u) + r u = f

˜

we obtain, by di¬erentiating and rearranging the convective term,

’∇ · (K∇u) + c · ∇u + (∇ · c + r ) u = f ,

˜

which gives the form (3.12) with r := ∇ · c + r . The boundary ‚„¦ consists

˜

only of two parts “1 and “2 . Therein, “1 an out¬‚ow boundary and “2 an

in¬‚ow boundary; that is, the conditions

c · ν ≥ 0 on “1 and c · ν ¤ 0 on “2

hold. Frequently prescribed boundary conditions are

’(c u ’ K∇u) · ν = ’ν · c u on “1 ,

’(c u ’ K∇u) · ν = g2 on “2 .

They are based on the following assumptions: On the in¬‚ow boundary “2

the normal component of the total (mass) ¬‚ux is prescribed but on the

out¬‚ow boundary “1 , on which in the extreme case K = 0 the boundary

conditions would drop out, only the following is required:

• the normal component of the total (mass) ¬‚ux is continuous over “1 ,

• the ambient mass ¬‚ux that is outside „¦ consists only of a convective

part,

• the extensive variable (for example, the concentration) is continuous

over “1 , that is, the ambient concentration in x is also equal to u(x).

Therefore, after an obvious reformulation we get, in accordance with the

de¬nitions of “1 and “2 due to (3.18), (3.19), the Neumann boundary

3.2. Elliptic Boundary Value Problems 109

condition (3.18), and the mixed boundary condition (3.19),

K∇u · ν =0 on “1 ,

K∇u · ν + ± u = g2 on “2 ,

where ± := ’ν · c.

Now the conditions of Theorem 3.15 can be checked:

We have r’ 1 ∇·c = r + 1 ∇·c; therefore, for the latter term the inequality

˜2

2

in (1) and (4)(b) must be satis¬ed. Further, the condition ν · c ≥ 0 on

“1 holds due to the characterization of the out¬‚ow boundary. Because of

± + 1 ν · c = ’ 2 ν · c, the condition (3) is satis¬ed due to the de¬nition of

1

2

the in¬‚ow boundary.

Now we address the case of inhomogeneous Dirichlet boundary

conditions (|“3 |d’1 > 0).

This situation can be reduced to the case of homogeneous Dirich-

let boundary conditions, if we are able to choose some (¬xed) element

w ∈ H 1 („¦) in such a way that (in the sense of trace) we have

γ0 (w) = g3 on “3 . (3.34)

The existence of such an element w is a necessary assumption for the exis-

tence of a solution u ∈ H 1 („¦). On the other hand, such an element w can

˜

exist only if g3 belongs to the range of the mapping

v ’ γ0 (v)|“3 ∈ L2 (“3 ).

H 1 („¦)

However, this is not valid for all g3 ∈ L2 (“3 ), since the range of the trace

operator of H 1 („¦) is a proper subset of L2 (‚„¦).

Therefore, we assume the existence of such an element w. Since only

the homogeneity of the Dirichlet boundary conditions of the test functions

plays a role in derivation (3.31) of the bilinear form a and the linear form

b, we ¬rst obtain with the space V , de¬ned in (3.30), and

V := v ∈ H 1 („¦) : γ0 (v) = g3 on “3 = v ∈ H 1 („¦) : v ’ w ∈ V

˜

the following variational formulation:

Find u ∈ V such that

˜˜

for all v ∈ V .

a(˜, v) = b(v)

u

However, this formulation does not ¬t into the theoretical concept of

˜

Section 3.1 since the space V is not a linear one.

If we put u := u + w, then this is equivalent to the following:

˜

Find u ∈ V such that

a(u, v) = b(v) ’ a(w, v) =: ˜

b(v) for all v ∈ V . (3.35)

Now we have a variational formulation for the case of inhomogeneous

Dirichlet boundary conditions that has the form required in the theory.

110 3. Finite Element Methods for Linear Elliptic Problems

Remark 3.17 In the existence result of Theorem 3.1, the only assumption

is that b has to be a continuous linear form in V .

For d = 1 and „¦ = (a, b) this is also satis¬ed, for instance, for the special

linear form

δγ (v) := v(γ) for v ∈ H 1 (a, b),

where γ ∈ (a, b) is arbitrary but ¬xed, since by Lemma 3.4 the space

H 1 (a, b) is continuously embedded in the space C[a, b]. Thus, for d = 1

point sources (b = δγ ) are also allowed. However, for d ≥ 2 this does not

hold since H 1 („¦) ‚ C(„¦).

¯

Finally, we will once again state the general assumptions under which the

variational formulation of the boundary value problem (3.12), (3.18)“(3.20)

in the space (3.30),

V = v ∈ H 1 („¦) : γ0 (v) = 0 on “3 ,

has properties that satisfy the conditions of the Lax“Milgram Theorem

(Theorem 3.1):

• „¦ ‚ Rd is a bounded Lipschitz domain.

• kij , ci , ∇ · c, r ∈ L∞ („¦) , f ∈ L2 („¦) , i, j ∈ {1, . . . , d}, and, if

|“1 ∪ “2 |d’1 > 0, ν · c ∈ L∞ (“1 ∪ “2 ) (i.e., (3.15)).

• There exists some constant k0 > 0 such that in „¦, we have ξ ·K(x)ξ ≥

k0 |ξ|2 for all ξ ∈ Rd (i.e., (3.16)),

• gj ∈ L2 (“j ) , j = 1, 2, 3, ± ∈ L∞ (“2 ) (i.e., (3.22)).

• The following hold:

r ’ 1 ∇ · c ≥ 0 in „¦ .

(1) 2

ν · c ≥ 0 on “1 .

(2)

± + 1 ν · c ≥ 0 on “2 .

(3) 2

(4) Additionally, one of the following conditions is satis¬ed:

(a) |“3 |d’1 > 0 .

(b) There exists some „¦ ‚ „¦ with |„¦|d > 0 and r0 > 0 such

˜ ˜

that r ’ 1 ∇ · c ≥ r0 on „¦.

˜

2

(c) There exists some “1 ‚ “1 with |“1 |d’1 > 0 and c0 > 0

˜ ˜

such that ν · c ≥ c0 on “1 .

˜

(d) There exists some “2 ‚ “2 with |“2 |d’1 > 0 and ±0 > 0

˜ ˜

such that ± + 1 ν · c ≥ ±0 on “2 .

˜

2

• If |“3 |d’1 > 0 , then there exists some w ∈ H 1 („¦) with γ0 (w) = g3

on “3 (i.e., (3.34)).

3.2. Elliptic Boundary Value Problems 111

3.2.2 An Example of a Boundary Value Problem of Fourth

Order

The Dirichlet problem for the biharmonic equation reads as follows:

Find u ∈ C 4 („¦) © C 1 („¦) such that

¯

∆2 u = f in „¦ ,

(3.36)

‚ν u = u = 0 on ‚„¦ ,

where

d

2 2 2

∆ u := ∆ (∆u) = ‚i ‚j u .

i,j=1

In the case d = 1 this collapses to ∆2 u = u(4) .

For u, v ∈ H 2 („¦) it follows from Corollary 3.9 that

(u ∆v ’ ∆u v) dx = {u ‚ν v ’ ‚ν u v}dσ

„¦ ‚„¦

and hence for u ∈ H 4 („¦), v ∈ H 2 („¦) (by replacing u with ∆u in the above

equation),

∆2 u v dx ’

∆u ∆v dx = ‚ν ∆u v dσ + ∆u ‚ν v dσ .

„¦ „¦ ‚„¦ ‚„¦

For a Lipschitz domain „¦ we de¬ne

H0 („¦) := v ∈ H 2 („¦) v = ‚ν v = 0 on ‚„¦

2

2

and obtain the variational formulation of (3.36) in the space V := H0 („¦):

Find u ∈ V , such that

for all v ∈ V .

a(u, v) := ∆u ∆v dx = b(v) := f v dx

„¦ „¦

More general, for a boundary value problem of order 2m in conservative

form, we obtain a variational formulation in H m („¦) or H0 („¦).

m

3.2.3 Regularity of Boundary Value Problems

In Section 3.2.1 we stated conditions under which the linear elliptic bound-

ary value problem admits a unique solution u (˜, respectively) in some

u

1

subspace V of H („¦). In many cases, for instance for the interpolation of

the solution or in the context of error estimates (also in norms other than

the · V norm) it is not su¬cient that u (˜, respectively) have only ¬rst

u

2

weak derivatives in L („¦).

Therefore, within the framework of the so-called regularity theory, the

question of the assumptions under which the weak solution belongs to

H 2 („¦), for instance, has to be answered. These additional conditions

contain conditions about

112 3. Finite Element Methods for Linear Elliptic Problems

• the smoothness of the boundary of the domain,

• the shape of the domain,

• the smoothness of the coe¬cients and the right-hand side of the

di¬erential equation and the boundary conditions,

• the kind of the transition of boundary conditions in those points,

where the type is changing,

which can be quite restrictive as a whole. Therefore, in what follows we

often assume only the required smoothness. Here we cite as an example

one regularity result ([13, Theorem 8.12]).

Theorem 3.18 Suppose „¦ is a bounded C 2 -domain and “3 = ‚„¦. Further,

assume that kij ∈ C 1 („¦), ci , r ∈ L∞ („¦) , f ∈ L2 („¦) , i, j ∈ {1, . . . , d},

¯

as well as (3.16). Suppose there exists some function w ∈ H 2 („¦) with

γ0 (w) = g3 on “3 . Let u = u + w and let u be a solution of (3.35). Then

˜

u ∈ H („¦) and

2

˜

¤ C{ u + w 2}

u

˜ +f

2 0 0

with a constant C > 0 independent of u, f , and w.

One drawback of the above result is that it excludes polyhedral domains.

If the convexity of „¦ is additionally assumed, then it can be transferred

to this case. Simple examples of boundary value problems in domains with

reentrant corners show that one cannot avoid such additional assumptions

(see Exercise 3.5).

Exercises

3.5 Consider the boundary value problem (1.1), (1.2) for f = 0 in the

sector „¦ := (x, y) ∈ R2 x = r cos •, y = r sin • with 0 < r < 1, 0 < • <

± for some 0 < ± < 2π, thus with the interior angle ±. Derive as in (1.23),

by using the ansatz w(z) := z 1/± , a solution u(x, y) = w(x + iy) for an

appropriate boundary function g. Then check the regularity of u, that is,

u ∈ H k („¦), in dependence of ±.

3.6 Consider the problem (1.29) with the transmission condition (1.30)

and, for example, Dirichlet boundary conditions and derive a variational

formulation for this.

3.7 Consider the variational formulation:

Find u ∈ H 1 („¦) such that

∇u · ∇v dx = for all v ∈ H 1 („¦) ,

f v dx + gv dσ (3.37)

„¦ „¦ ‚„¦

Exercises 113

where „¦ is a bounded Lipschitz domain, f ∈ L2 („¦) and g ∈ L2 (‚„¦).

(a) Let u ∈ H 1 („¦) be a solution of this problem. Show that ’∆u exists

in the weak sense in L2 („¦) and

’∆u = f .

(b) If additionally u ∈ H 2 („¦), then ‚ν u|‚„¦ exists in the sense of trace in

L2 (‚„¦) and

‚ν u = g

where this equality is to be understood as

(‚ν u ’ g)v dσ = 0 for all v ∈ H 1 („¦) .

‚„¦

3.8 Consider the variational equation (3.37) for the Neumann problem

for the Poisson equation as in Exercise 3.7.

(a) If a solution u ∈ H 1 („¦) exists, then the compatibility condition

f dx + g dσ = 0 (3.38)

„¦ ‚„¦

has to be ful¬lled.

(b) Consider the following bilinear form on H 1 („¦) :

∇u · ∇v dx +

a(u, v) :=

˜ u dx v dx .

„¦ „¦ „¦

1

Show that a is V -elliptic on H („¦).

˜

Hint: Do it by contradiction using the fact that a bounded sequence in

H 1 („¦) possesses a subsequence converging in L2 („¦) (see, e.g., [37]).

(c) Consider the unique solution u ∈ H 1 („¦) of

˜

for all v ∈ H 1 („¦) .

a(u, v) =

˜ f v dx + gv dσ

„¦ ‚„¦

Then:

|„¦| u dx =

˜ f dx + g dσ .

„¦ „¦ ‚„¦

Furthermore, if (3.38) is valid, then u is a solution of (3.37) (with

˜

„¦ u dx = 0).

˜

3.9 Show analogously to Exercise 3.7: A weak solution u ∈ V ‚ H 1 („¦)

of (3.31), where V is de¬ned in (3.30), with data satisfying (3.14) and

(3.22), ful¬lls a di¬erential equation in L2 („¦). The boundary conditions

are ful¬lled in the following sense:

g2 v dσ for all v ∈ V .

‚νK u v dσ+ (‚νK u+± u)v dσ = g1 v dσ+

“1 “2 “1 “2

114 3. Finite Element Methods for Linear Elliptic Problems

3.3 Element Types and A¬ne Equivalent

Triangulations

In order to be able to exploit the theory developed in Sections 3.1 and 3.2

we make the assumption that „¦ is a Lipschitz domain.

The ¬nite element discretization of the boundary value problem (3.12)

with the boundary conditions (3.18)“(3.20) corresponds to performing a

Galerkin approximation (cf. (2.23)) of the variational equation (3.35) with

the bilinear form a and the linear form b, supposed to be de¬ned as in

(3.31), and some w ∈ H 1 („¦) with the property w = g3 on “3 . The solution

of the weak formulation of the boundary value problem is then given by

u := u + w, if u denotes the solution of the variational equation (3.35).

˜

Since the bilinear form a is in general not symmetric, (2.21) and (2.23),

respectively (the variational equation), are no longer equivalent to (2.22)

and (2.24), respectively (the minimization problem), so that in the following

we pursue only the ¬rst, more general, ansatz.

The Galerkin approximation of the variational equation (3.35) reads as

follows: Find some u ∈ Vh such that

a(uh , v) = b(v) ’ a(w, v) = ˜ for all v ∈ Vh .

b(v) (3.39)

The space Vh that is to be de¬ned has to satisfy Vh ‚ V . Therefore, we

speak of a conforming ¬nite element discretization, whereas for a non-

conforming discretization this property, for instance, can be violated. The

ansatz space is de¬ned piecewise with respect to a triangulation Th of „¦

with the goal of getting small supports for the basis functions. A trian-

gulation in two space dimensions consisting of triangles has already been

de¬ned in de¬nition (2.25). The generalization in d space dimensions reads

as follows:

De¬nition 3.19 A triangulation Th of a set „¦ ‚ Rd consists of a ¬nite

number of subsets K of „¦ with the following properties:

Every K ∈ Th is closed.

(T1)

For every K ∈ Th its nonempty interior int (K) is a Lipschitz domain.

(T2)

„¦ = ∪K∈Th K.

(T3)

For di¬erent K1 and K2 of Th the intersection of int (K1 ) and int (K2 )

(T4)

is empty.

The sets K ∈ Th , which are called somewhat inaccurately elements in the

following, form a nonoverlapping decomposition of „¦. Here the formulation

is chosen in such a general way, since in Section 3.8 elements with curved

boundaries will also be considered. In De¬nition 3.19 some condition, which

corresponds to the property (3) of de¬nition (2.25), is still missing. In the

following this will be formulated speci¬cally for each element type. The

3.3. Element Types and A¬ne Equivalent Triangulations 115

parameter h is a measure for the size of all elements and mostly chosen as

h = max diam (K) K ∈ Th ;

that is, for instance, for triangles h is the length of the triangle™s largest

edge.

For a given vector space Vh let

PK := {v|K | v ∈ Vh } for K ∈ Th , (3.40)

that is,

Vh ‚ v : „¦ ’ R v|K ∈ PK for all K ∈ Th .

In the example of “linear triangles” in (2.27) we have PK = P1 , the poly-

nomials of ¬rst order. In the following de¬nitions the space PK will always

consist of polynomials or of smooth “polynomial-like” functions, such that

we can assume PK ‚ H 1 (K) © C(K). Here, H 1 (K) is an abbreviation for

H 1 (int (K)). The same holds for similar notation.

As the following theorem shows, elements v ∈ Vh of a conforming ansatz

space Vh ‚ V have therefore to be continuous :

Theorem 3.20 Suppose PK ‚ H 1 (K) © C(K) for all K ∈ Th . Then

Vh ‚ C(„¦) ⇐’ Vh ‚ H 1 („¦)

¯

and, respectively, for V0h := v ∈ Vh v = 0 on ‚„¦ ,

V0h ‚ C(„¦) ⇐’ V0h ‚ H0 („¦) .

¯ 1

Proof: See, for example, [9, Theorem 5.1 (p. 62)] or also Exercise 3.10. 2

If Vh ‚ C(„¦), then we also speak of C 0 -elements. Hence with this notion

¯

we do not mean only the K ∈ Th , but these provided with the local ansatz

space PK (and the degrees of freedom still to be introduced). For a bound-

ary value problem of fourth order, Vh ‚ H 2 („¦) and hence the requirement

Vh ‚ C 1 („¦) are necessary for a conforming ¬nite element ansatz. There-

¯

fore, this requires, analogously to Theorem 3.20, so-called C 1 -elements. By

degrees of freedom we denote a ¬nite number of values that are obtained

for some v ∈ PK from evaluating linear functionals on PK . The set of

these functionals is denoted by ΣK . In the following, these will basically

be the function values in ¬xed points of the element K, as in the example

of (2.27). We refer to these points as nodes. (Sometimes, this term is used

only for the vertices of the elements, which at least in our examples are

always nodes.) If the degrees of freedom are only function values, then we

speak of Lagrange elements and specify Σ by the corresponding nodes of

the element. Other possible degrees of freedom are values of derivatives in

¬xed nodes or also integrals. Values of derivatives are necessary if we want

to obtain C 1 -elements.

116 3. Finite Element Methods for Linear Elliptic Problems

As in the example of (2.27) (cf. Lemma 2.10), Vh is de¬ned by specifying

PK and the degrees of freedom on K for K ∈ Th . These have to be chosen

such that, on the one hand, they enforce the continuity of v ∈ Vh and,

on the other hand, the satisfaction of the homogeneous Dirichlet bound-

ary conditions at the nodes. For this purpose, compatibility between the

Dirichlet boundary condition and the triangulation is necessary, since it

will be required in (T6).

As can be seen from the proof of Lemma 2.10, it is essential

that the interpolation problem, locally de¬ned on K ∈

(F1) (3.41)

Th by the degrees of freedom, is uniquely solvable in PK ,

that this also holds on the (d ’ 1)-dimensional boundary

surfaces F of K ∈ Th for the degrees of freedom from F

and the functions v|F where v ∈ PK ; this then ensures

(F2) (3.42)

the continuity of v ∈ Vh , if PK and PK match in the

sense of PK |F = PK |F for K, K ∈ Th intersecting in F

(see Figure 3.2).

. .

PK = P1 PK = P1

F

.

. .

Figure 3.2. Compatibility of the ansatz space on the boundary surface and the

degrees of freedom there.

The following ¬nite elements de¬ned by their basic domain K(∈ Th ),

the local ansatz space PK , and the degrees of freedom ΣK satisfy these

properties.

For this, let Pk (K) be the set of mappings p : K ’ R of the following

form:

γ±1 ...±d x±1 · · · x±d = γ± x± ,

p(x) = p(x1 , . . . , xd ) = (3.43)

1 d

|±|¤k |±|¤k

hence the polynomials of order k in d variables. The set Pk (K) forms

a vector space, and since p ∈ Pk (K) is di¬erentiable arbitrarily often,

Pk (K) is a subset of all function spaces introduced so far (provided that

the boundary conditions do not belong to their de¬nition).

For both, K ∈ Th and K = Rd we have

d+k

dim Pk (K) = dim Pk (Rd ) = , (3.44)

k

as even Pk (Rd )|K = Pk (K) (see Exercise 3.12). Therefore, for short we will

use the notation P1 = P1 (K) if the dimension of the basic space is ¬xed.

3.3. Element Types and A¬ne Equivalent Triangulations 117

We start with simplicial ¬nite elements, that is, elements whose basic

domain is a regular d-simplex of Rd . By this we mean the following:

De¬nition 3.21 A set K ‚ Rd is called a regular d-simplex if there exist

d + 1 distinct points a1 , . . . , ad+1 ∈ Rd , the vertices of K, such that

a2 ’ a1 , . . . , ad+1 ’ a1 are linearly independent (3.45)

(that is, a1 , . . . , ad+1 do not lie in a hyperplane) and

conv {a1 , . . . , ad+1 }

K =

d+1 d+1

»i ai 0 ¤ »i (¤ 1) ,

:= x= »i = 1 (3.46)

i=1 i=1

d+1 d+1

»i (ai ’ a1 ) »i ≥ 0 , »i ¤ 1 .

= x = a1 +

i=2 i=2

A face of K is a (d ’ 1)-simplex de¬ned by d points of {a1 , . . . , ad+1 }.

The particular d-simplex

K := conv {ˆ1 , . . . , ad+1 } with a1 = 0 , ai+1 = ei , i = 1, . . . , d ,

ˆ a ˆ ˆ ˆ (3.47)

is called the standard simplicial reference element.

In the case d = 2 we get a triangle with dim P1 = 3 (cf. Lemma 2.10). The

faces are the 3 edges of the triangle. In the case d = 3 we get a tetrahedron

with dim P1 = 4, the faces are the 4 triangle surfaces, and ¬nally, in the

case d = 1 it is a line segment with dim P1 = 2 and the two boundary

points as faces.

More precisely, a face is not interpreted as a subset of Rd , but of a

(d ’ 1)-dimensional space that, for instance, is spanned by the vectors

a2 ’ a1 , . . . , ad ’ a1 in the case of the de¬ning points a1 , . . . , ad .

Sometimes, we also consider degenerate d-simplices, where the assump-

tion (3.45) of linear independence is dropped. We consider, for instance,

a line segment in the two-dimensional space as it arises as an edge of a

triangular element. In the one-dimensional parametrisation it is a regular

1-simplex, but in R2 a degenerate 2-simplex.

The unique coe¬cients »i = »i (x), i = 1, . . . , d + 1, in (3.46), are called

barycentric coordinates of x. This de¬nes mappings »i : K ’ R, i =

1, . . . , d + 1.

We consider aj as a column of a matrix; that is, for j = 1, . . . , d, aj =

(aij )i=1,...,d . The de¬ning conditions for »i = »i (x) can be written as a

(d + 1) — (d + 1) system of equations:

d+1

aij »j = xi

x

j=1

” B» = (3.48)

1

d+1

»j = 1

j=1

118 3. Finite Element Methods for Linear Elliptic Problems

«

for

· · · a1,d+1

a11

¬. ·

.

..

¬. ·

.

.

B=¬ . . ·. (3.49)

ad1

· · · ad,d+1

···

1 1

The matrix B is nonsingular due to assumption (3.45); that is, »(x) =

B ’1 x , and hence

1

d

»i (x) = cij xj + ci,d+1 for all i = 1, . . . , d + 1 ,

j=1

where C = (cij )ij := B ’1 .

Consequently, the »i are a¬ne-linear, and hence »i ∈ P1 . The level

surfaces x ∈ K »i (x) = µ correspond to intersections of hyperplanes

with the simplex K (see Figure 3.3). The level surfaces for distinct µ1 and

µ2 are parallel to each other, that is, in particlular, to the level surface for

µ = 0, which corresponds to the triangle face spanned by all the vertices

apart of ai .

»1 = »1 = µ

1

2

.a 3

.

a31

.a 23

.

a1

.

a12

.a 2

Figure 3.3. Barycentric coordinates and hyperplanes.

By (3.48), the barycentric coordinates can be de¬ned for arbitrary x ∈ Rd

(with respect to some ¬xed d-simplex K). Then

x ∈ K ⇐’ 0 ¤ »i (x) ¤ 1 for all i = 1, . . . , d + 1 .

Applying Cramer™s rule to the system B» = x , we get for the ith

1

barycentric coordinate

«

a11 · · · x1 · · · a1,d+1

¬. ·

. .

¬. ·

1 . .

det ¬ . . . ·.

»i (x) =

ad1 · · · xd · · · ad,d+1

det(B)

1 ··· 1 ··· 1

3.3. Element Types and A¬ne Equivalent Triangulations 119

Here, in the ith column ai has been replaced with x. Since in general,

vol (K) = vol (K) | det(B)|

ˆ (3.50)

ˆ

for the reference simplex K de¬ned by (3.47) (cf. (2.50)), we have for the

volume of the d-simplex K = conv {a1 , . . . , ad+1 },

«

a11 · · · a1,d+1

¬. ·

.

..

¬. ·

1 .

.

. .

det ¬ ·,

vol (K) =

ad1 · · · ad,d+1

d!

1 ··· 1

and from this,

vol (conv {a1 , . . . , x, . . . , ad+1 })

»i (x) = ± . (3.51)

vol (conv {a1 , . . . , ai , . . . , ad+1 })

The sign is determined by the arrangement of the coordinates.

In the case d = 2 for example, we have

vol (K) = det(B)/2

⇐’ a1 , a2 , a3 are ordered positively (that is, counterclockwise).

Here, conv {a1 , . . . , x, . . . , ad+1 } is the d-simplex that is generated by re-

placing ai with x and is possibly degenerate if x lies on a face of K (then

»i (x) = 0). Hence, in the case d = 2 we have for x ∈ K that the barycentric

coordinates »i (x) are the relative areas of the triangles that are spanned by

x and the vertices other than ai . Therefore, we also speak of surface coordi-

nates (see Figure 3.4). Analogous interpretations hold for d = 3. Using the

barycentric coordinates, we can now easily specify points that admit a ge-

ometric characterization. The midpoint aij := 1 (ai + aj ) of a line segment

2

that is given by ai and aj satis¬es, for instance,

1

»i (x) = »j (x) = .

2

By the barycentre of a d-simplex we mean

d+1

1 1

aS := ai ; thus »i (aS ) = for all i = 1, . . . , d + 1 . (3.52)

d+1 d+1

i=1

A geometric interpretation follows directly from the above considerations.

In the following suppose conv {a1 , . . . , ad+1 } to be a regular d-simplex.

We make the following de¬nition:

Finite Element: Linear Ansatz on the Simplex

= conv {a1 , . . . , ad+1 } ,

K

= P1 (K) ,

P (3.53)

= {p (ai ) , i = 1, . . . , d + 1} .

Σ

120 3. Finite Element Methods for Linear Elliptic Problems

conv{x ,a2 ,a 3}

. .

a3 a2

. x

conv{a1 ,x,a 3} conv{a1 ,a 2 ,x}

.a1

Figure 3.4. Barycentric coordinates as surface coordinates.

The local interpolation problem in P , given by the degrees of freedom Σ,

namely,

¬nd some p ∈ P for u1 , . . . , ud+1 ∈ R such that

p(ai ) = ui for all i = 1, . . . , d + 1 ,

can be interpreted as the question of ¬nding the inverse image of a linear

mapping from P to R|Σ| . By virtue of (3.44),

|Σ| = d + 1 = dim P .

Since both vector spaces have the same dimension, the solvability of the

interpolation problem is equivalent to the uniqueness of the solution. This

consideration holds independently of the type of the degrees of freedom (as

far as they are linear functionals on P ). Therefore, we need only to ensure

the solvability of the interpolation problem. This is obtained by specifying

N1 , . . . , Nd+1 ∈ P with Ni (aj ) = δij for all i, j = 1, . . . , d + 1 ,

the so-called shape functions (see (2.29) for d = 2). Then the solution of

the interpolation problem is given by

d+1

p(x) = ui Ni (x) (3.54)

i=1

and analogously in the following; that is, the shape functions form a basis

of P and the coe¬cients in the representation of the interpolating function

are exactly the degrees of freedom u1 , . . . , ud+1 .

Due to the above considerations, the speci¬cation of the shape functions

can easily be done by choosing

Ni = »i .

Finite Element: Quadratic Ansatz on the Simplex

Here, we have

= conv {a1 , . . . , ad+1 } ,

K

3.3. Element Types and A¬ne Equivalent Triangulations 121

= P2 (K) ,

P (3.55)

= {p (ai ) , p (aij ) , i = 1, . . . , d + 1, i < j ¤ d + 1} ,

Σ

where the aij denote the midpoints of the edges (see Figure 3.5).

Since here we have

(d + 1)(d + 2)

|Σ| = = dim P ,

2

it also su¬ces to specify the shape functions. They are given by

»i (2»i ’ 1) , i = 1, . . . , d + 1 ,

4»i »j , i, j = 1, . . . , d + 1 , i < j .

. .

d=2 d=3

. .

. .

. .. dim = 10

. ..

dim = 6

. ..

.

Figure 3.5. Quadratic simplicial elements.

If we want to have polynomials of higher degree as local ansatz functions,

but still Lagrange elements, then degrees of freedom also arise in the interior

of K:

Finite Element: Cubic Ansatz on the Simplex

conv {a1 , . . . , ad+1 } ,

K =

P3 (K) ,

P = (3.56)

{p(ai ), p(ai,i,j ), p(ai,j,k )} ,

Σ =

where

2 1

ai,i,j := ai + aj for i, j = 1, . . . , d + 1 , i = j ,

3 3

1

ai,j,k :=

(ai + aj + ak ) for i, j, k = 1, . . . , d + 1 , i < j < k .

3

Since here |Σ| = dim P also holds, it is su¬cient to specify the shape

functions, which is possible by

1

»i (3»i ’ 1)(3»i ’ 2), i = 1, . . . , d + 1 ,

2

9

»i »j (3»i ’ 1), i, j = 1, . . . , d + 1 , i = j ,

2

122 3. Finite Element Methods for Linear Elliptic Problems

27»i »j »k , i, j, k = 1, . . . , d + 1 , i < j < k .

Thus for d = 2 the value at the barycentre arises as a degree of freedom.

This, and in general the ai,j,k , i < j < k, can be dropped if the ansatz

space P is reduced (see [9, p. 70]).

All ¬nite elements discussed so far have degrees of freedom that are

de¬ned in convex combinations of the vertices. On the other hand, two

regular d-simplices can be mapped bijectively onto each other by a unique

a¬ne-linear F , that is, F ∈ P1 such that as de¬ning condition, the vertices

of the simplices should be mapped onto each other. If we choose, besides

ˆ

the general simplex K, the standard reference element K de¬ned by (3.47),

then F = FK : K ’ K is de¬ned by

ˆ

F (ˆ) = B x + a1 ,

x ˆ (3.57)

where B = (a2 ’ a1 , . . . , ad+1 ’ a1 ).

Since for F we have

d+1 d+1 d+1

»i F (ˆi ) for »i ≥ 0 ,

F »i ai

ˆ = a »i = 1 ,

i=1 i=1 i=1

F is indeed a bijection that maps the degrees of freedom onto each other as

ˆ

well as the faces of the simplices. Since the ansatz spaces P and P remain

invariant under the transformation FK , the ¬nite elements introduced so

far are (in their respective classes) a¬ne equivalent to each other and to

the reference element.

ˆ ˆˆ

De¬nition 3.22 Two Lagrange elements (K, P, Σ), (K, P , Σ) are called

equivalent if there exists a bijective F : K ’ K such that

ˆ

F (ˆ) a ∈ K generates a degree of freedom on K

ˆ ˆ

aˆ

a a ∈ K generates a degree of freedom on K

=

(3.58)

and

p:K ’R p—¦F ∈P

ˆ

P = .

They are called a¬ne equivalent if F is a¬ne-linear.

Here we have formulated the de¬nition in a more general way, since in

Section 3.8 elements with more general F will be introduced: For isopara-

metric elements the same functions F as in the ansatz space are admissible

for the transformation. From the elements discussed so far only the simplex

with linear ansatz is thus isoparametric. Hence, in the (a¬ne) equivalent

case a transformation not only of the points is de¬ned by

x = F ’1 (x) ,

ˆ

ˆ ˆ

but also of the mappings, de¬ned on K and K, (not only of P and P ) is

given by

v : K ’ R,

ˆˆ v (ˆ) := v(F (ˆ))

ˆx x

3.3. Element Types and A¬ne Equivalent Triangulations 123

for v : K ’ R and vice versa.

We can also use the techniques developed so far in such a way that only

the reference element is de¬ned, and then a general element is obtained

from this by an a¬ne-linear transformation. As an example of this, we

consider elements on a cube.

Suppose K := [0, 1]d = x ∈ Rd 0 ¤ xi ¤ 1, i = 1, . . . , d is the unit

ˆ

ˆ

cube. The faces of K are de¬ned by setting a coordinate to 0 or 1; thus for

instance,

j’1 d

[0, 1] — {0} — [0, 1] .

i=1 j+1

Let Qk (K) denote the set of polynomials on K that are of the form

γ±1 ,...,±d x±1 · · · x±d .

p(x) = 1 d

0¤±i ¤k

i=1,...,d

Hence, we have Pk ‚ Qk ‚ Pdk .

Therefore, we de¬ne a reference element generally for k ∈ N as follows:

Finite Element: d-polynomial Ansatz on the Cuboid

ˆ [0, 1]d ,

K =

ˆ ˆ

P = Qk (K) , (3.59)

i1 id

, ij ∈ {0, . . . , k}, j = 1, . . . , d

ˆ

Σ = p(ˆ) x =

xˆ ,..., ,

k k

which is depicted in Figure 3.6. Again, we have |Σ| = dim P , such that

ˆ ˆ

for the unique solvability of the local interpolation problem we have only

ˆ

to specify the shape functions. They are obtained on K as the product of

the corresponding shape functions for the case d = 1, thus of the Lagrange

basis polynomials

kˆj ’ ij

d k

x

pi1 ,...,id (ˆ) :=

x .

ij ’ ij

i =0

j=1 j

i =ij

j

Interior degrees of freedom arise from k = 2 onward. Hence the ansatz

space on the general element K is, according to the de¬nition above,

’1

P = p —¦ FK p ∈ Qk (K) .

ˆ

ˆ ˆ

In the case of a general rectangular cuboid, that is, if B in (3.57) is a

diagonal matrix, then P = Qk (K) holds, analogously to the simplices.

However, for a general B additional polynomial terms arise that do not

belong to Qk (see Exercise 3.14).

124 3. Finite Element Methods for Linear Elliptic Problems

. .

d = 2 , dim = 4

. . . .

d=3

dim = 8

. .

. . . .

bilinear ansatz trilinear ansatz

.. ... ...

d = 2 , dim = 9

. . . .

d=3

. . . . . . . . dim = 27

. . . .

.. ... ...

. . . .

biquadratic ansatz triquadratic ansatz

Figure 3.6. Quadratic and cubic elements on the cube.

An a¬ne-linear transformation does not generate general cuboids but

only d-epipeds, thus for d = 3 parallelepipeds and for d = 2 only parallelo-

grams. To map the unit square to an arbitrary general convex quadrilateral,

we need some transformation of Q1 , that is, isoparametric elements (see

(3.142)).

Let Th be a triangulation of d-simplices or of a¬nely transformed d-

unit cubes. In particular, „¦ = int(∪K∈Th K) is polygonally bounded. The

condition (F1) in (3.41) is always satis¬ed. In order to be able to satisfy

the condition (F2) in (3.42) as well, a further assumption in addition to

(T1)“(T4) has to be made about the triangulation:

(T5) Every face of some K ∈ Th is either a subset of the boundary “ of „¦

or identical to a face of another K ∈ Th .

˜

In order to ensure the validity of the homogeneous Dirichlet boundary

condition on “3 for the vh ∈ Vh that have to be de¬ned, we additionally

assume the following:

(T6) The boundary sets “1 , “2 , “3 decompose into faces of elements K ∈

Th .

A face F of K ∈ Th that is lying on ‚„¦ is therefore only allowed to contain

a point from the intersection “i © “j for i = j, if and only if the point is a

3.3. Element Types and A¬ne Equivalent Triangulations 125

boundary point of F . We recall that the set “3 has been de¬ned as being

closed in ‚„¦.

In the following, we suppose that these conditions are always satis¬ed.

A triangulation that also satis¬es (T5) and (T6) is called conforming.

Then, for all of the above ¬nite elements,

• If K, K ∈ Th have a common face F , then the degrees of (3.60)

freedom of K and K coincide on F .

• F itself becomes a ¬nite element (that is, the local interpo- (3.61)

lation problem is uniquely solvable) with the ansatz space

PK |F and the degrees of freedom on F .

We now choose Vh as follows:

v : „¦ ’ R v|K ∈ PK for K ∈ Th

Vh :=

(3.62)

and v is uniquely given in the degrees of freedom .

Analogously to the proof of Lemma 2.10, we can see that v ∈ Vh is con-

tinuous over the face of an element; thus Vh ‚ C(„¦), that is, Vh ‚ H 1 („¦)

¯

according to Theorem 3.20.

Further, u|F = 0 if F is a face of K ∈ Th with F ‚ ‚„¦ and the speci¬ca-

tions in the degrees of freedom of F are zero (Dirichlet boundary conditions

only in the nodes); that is, the homogeneous Dirichlet boundary conditions

are satis¬ed by enforcing them in the degrees of freedom. Due to the as-

sumption (T6), the boundary set “3 is fully taken into account in this

way.

Consequently, we the following theorem:

Theorem 3.23 Suppose Th is a conforming triangulation of d-simplices

or d-epipeds of a domain „¦ ‚ Rd . The elements are de¬ned as in one of

the examples (3.53), (3.55), (3.56), (3.59).

Let the degrees of freedom be given in the nodes a1 , . . . , aM . Suppose

they are numbered in such a way that a1 , . . . , aM1 ∈ „¦ ∪ “1 ∪ “2 and

aM1 +1 , . . . , aM ∈ “3 . If the ansatz space Vh is de¬ned by (3.62), then an

element v ∈ Vh is determined uniquely by specifying v(ai ), i = 1, . . . , M,

and

v ∈ H 1 („¦) .

If v(ai ) = 0 for i = M1 + 1, . . . , M , then we also have

v=0 on “3 .

Exactly as in Section 2.2 (see (2.32)), functions •i ∈ Vh are uniquely

determined by the interpolation condition

•i (aj ) = δij , i, j = 1, . . . , M .

By the same consideration as there and as for the shape functions (see

(3.54)) we observe that the •i form a basis of Vh , the nodal basis, since

126 3. Finite Element Methods for Linear Elliptic Problems

each v ∈ Vh has a unique representation

M

v(x) = v(ai )•i (x) . (3.63)

i=1

If for Dirichlet boundary conditions, the values in the boundary nodes

ai , i = M1 + 1, . . . , M , are given as zero, then the index has to run only up

to M1 .

The support supp •i of the basis functions thus consists of all elements

that contain the node ai , since in all other elements •i assumes the value 0

in the degrees of freedom and hence vanishes identically. In particular, for

an interior degree of freedom, that is, for some ai with ai ∈ int (K) for an

element K ∈ Th , we have supp •i = K.

Di¬erent element types can also be combined (see Figure 3.7) if only

(3.60) is satis¬ed, thus, for instance for d = 2 (3.59), k = 1, can be combined

with (3.53) or (3.59), k = 2, with (3.55).

.

. . . .

. .

. .

. .

.... . . .

.

.

. . .. . .

.

Figure 3.7. Conforming combination of di¬erent element types.

For d = 3 a combination of simplices and parallelepipeds is not possible,

since they have di¬erent types of faces. Tetrahedra can be combined with

prisms at their two triangular surfaces, whereas their three quadrilateral

surfaces (see Exercise 3.17) allow for a combination of prisms with paral-

lelepipeds. Possibly also pyramids are necessary as transition elements (see

[57]).

So far, the degrees of freedom have always been function values (Lagrange

elements). If, additionally, derivative values are speci¬ed, then we speak of

Hermite elements. As an example, we present the following:

Finite Element: Cubic Hermite Ansatz on the Simplex

K = conv {a1 , . . . , ad+1 } ,

3.3. Element Types and A¬ne Equivalent Triangulations 127

P = P3 (K) , (3.64)

Σ= p(ai ) , i = 1, . . . , d + 1 , p(ai,j,k ) , i, j, k = 1, . . . , d + 1 , i < j < k ,

∇p(ai ) · (aj ’ ai ) , i, j = 1, . . . , d + 1 , i = j .

Instead of the directional derivatives we could also have chosen the par-

tial derivatives as degrees of freedom, but would not have generated

a¬ne equivalent elements in that way. In order to ensure that directional

ˆ

derivatives in the directions ξ and ξ are mapped onto each other by the

transformation, the directions have to satisfy

ˆ

ξ = Bξ ,

where B is the linear part of the transformation F according to (3.57). This

is satis¬ed for (3.64), but would be violated for the partial derivatives, that

ˆ

is, ξ = ξ = ei . This has also to be taken into account for the question of

which degrees of freedom have to be chosen for Dirichlet boundary con-

ditions (see Exercise 3.19). Thus, the desired property that the degrees of

freedom be de¬ned “globally” is lost here. Nevertheless, we do not have a

C 1 -element: The ansatz (3.64) ensures only the continuity of the tangential,

not of the normal derivative over a face.

Finite Element: Bogner“Fox“Schmit Rectangle

The simplest C 1 -element is for d = 2 :

ˆ = [0, 1]2 ,

K

ˆ ˆ

P = Q3 (K) , (3.65)

= {p(a), ‚1 p(a), ‚2 p(a), ‚12 p(a) for all vertices a} ;

ˆ

Σ

that is, the element has 16 degrees of freedom.

In the case of Hermite elements, the above propositions concerning the

nodal basis hold analogously with an appropriate extension of the identity

(3.63).

Further, all considerations of Section 2.2 concerning the determination

of the Galerkin approximation as a solution of a system of equations (2.34)

also hold, since there only the (bi)linearity of the forms is supposed. There-

fore using the nodal basis, the quantity a(•j , •i ) has to be computed as

the (i, j)th matrix entry of the system of equations that has to be set up

for the bilinear form a. The form of the bilinear form (3.31) shows that

the consideration of Section 2.2, concerning that there is at most a nonzero

entry at position (i, j) if,

supp •i © supp •j = … , (3.66)

still holds.

Since in the examples discussed, supp •i consists of at most of those

elements containing the node ai (see Figure 3.10), the nodes have to be

adjacent, for the validity of (3.66); that is, they should belong to some

128 3. Finite Element Methods for Linear Elliptic Problems

common element. In particular, an interior degree of freedom of some ele-

ment is connected only with the nodes of the same element: This can be

used to eliminate such nodes from the beginning (static condensation).

The following consideration can be helpful for the choice of the element

type: An increase in the size of polynomial ansatz spaces increases the

(computational) cost by an increase in the number of nodes and an increase

in the population of the matrix.

As an example for d = 2 we consider triangles with linear (a) and

quadratic (b) ansatz (see Figure 3.8).

triangle with P1 triangle with P2

. .

.

. .

.

.

(a) (b)

. .

Figure 3.8. Comparison between linear and quadratic triangles.

In order to have the same number of nodes we compare (b) with the

discretization parameter h with (a) with the discretization parameter h/2

(one step of “red re¬nement”) (see Figure 3.9).

. .

.

. . .

.

. .

Figure 3.9. Generation of the same number of nodes.

However, this shows that we have a denser population in (b) than in (a).

. .

. .

. .

. . . .

. .

. .

. .

. . . .

. .

. .

supp •i supp •i

. .

Figure 3.10. Supports of the basis functions.

3.3. Element Types and A¬ne Equivalent Triangulations 129

To have still an advantage by using the higher polynomial order, the

ansatz (b) has to have a higher convergence rate. In Theorem 3.29 we will

prove the following estimate for a regular family of triangulations Th (see

De¬nition 3.28):

• If u ∈ H 2 („¦), then for (a) and (b) we have the estimate

u ’ uh ¤ C1 h . (3.67)

1

• If u ∈ H 3 („¦), then for (b) but not for (a) we have the estimate

u ’ uh ¤ C2 h2 . (3.68)

1

For the constants we may in general expect C2 > C1 .

In order to be able to make a comparison between the variants (a) and

(b), we consider in the following the case of a rectangle „¦ = (0, a) — (0, b).

The number of the nodes is then proportional to 1/h2 if the elements are

all “essentially” of the same size.

However, if we √ consider the number of nodes M as given, then h is

proportional to 1/ M .

Using this in the estimate (3.67), we get for a solution u ∈ H 2 („¦),

1

¤ C1 √ ,

u ’ uh/2

in the case (a) for h/2: 1

2M

¯1

¤ C1 √ .

u ’ uh

in the case (b) for h: 1

M

If both constants are the same, this means an advantage for the variant

(a).

On the other hand, if the solution is smoother and satis¬es u ∈ H 3 („¦),

then the estimate (3.68), which can be applied only to the variant (b),

yields

1

¤ C1 √ ,

u ’ uh/2

in the case (a) for h/2: 1

2M

1

u ’ uh ¤ C2

in the case (b) for h: .

1

M

By an elementary reformulation, we get

2

1 1 C2

< (<)C1 √ ⇐’ M > (>) 4 2 ,

C2

M C1

2M

which gives an advantage for (b) if the number of variables M is chosen,

depending on C2 /C1 , su¬ciently large. However, the denser population of

the matrix in (b) has to be confronted with this.

Hence, a higher-order polynomial ansatz has an advantage only if the

smoothness of the solution leads to a higher convergence rate. Especially

for nonlinear problems with less-smooth solutions, a possible advantage of

the higher-order ansatz has to be examined critically.

130 3. Finite Element Methods for Linear Elliptic Problems

Exercises

3.10 Prove the implication “’” in Theorem 3.20.

Hint: For v ∈ Vh de¬ne a function wi by wi |int(K) := ‚i v, i = 1, . . . , d,

and show that wi is the ith partial derivative of v.

3.11 Construct the element sti¬ness matrix for the Poisson equation on

a rectangle with quadratic bilinear rectangular elements. Verify that this

¬nite element discretization of the Laplace operator can be interpreted as

a ¬nite di¬erence method with the di¬erence stencil according to (1.22).

3.12 Prove that:

(a) dim Pk (Rd ) = d+k

.

k

(b) Pk (Rd )|K = Pk (K) if int (K) = ….

3.13 Prove for given vectors a1 , . . . , ad+1 ∈ Rd that a2 ’ a1 , . . . , ad+1 ’

a1 are linear independent if and only if a1 ’ ai , . . . , ai’1 ’ ai , ai+1 ’

ai , . . . , ad+1 ’ ai are linearly independent for some i ∈ {2, . . . , d}.

3.14 Determine for the polynomial ansatz on the cuboid as reference

element (3.59) the ansatz space P that is obtained by an a¬ne-linear

transformation to a d-epiped.

3.15 Suppose K is a rectangle with the (counterclockwise numbered) ver-

tices a1 , . . . , a4 and the corresponding edge midpoints a12 , a23 , a34 , a41 .

Show that the elements f of Q1 (K) are not determined uniquely by the

degrees of freedom f (a12 ), f (a23 ), f (a34 ), f (a41 ).

3.16 Check the given shape functions for (3.55) and (3.56).

3.17 De¬ne a reference element in R3 by

0 1 0

conv {ˆ1 , a2 , a3 } — [0, 1] with a1 =

ˆ

K = aˆˆ ˆ , a2 =

ˆ , a3 =

ˆ ,

0 0 1

p1 (x1 , x2 ) p2 (x3 ) p1 ∈ P1 (R2 ) , p2 ∈ P1 (R) ,

ˆ

P =

ˆ

Σ = p(ˆ) x = (ˆi , j) , i = 0, 1, 2 , j = 0, 1 .

xˆ a

Show the unique solvability of the local interpolation problem and describe

the elements obtained by a¬ne-linear transformation.

3.18 Suppose d + 1 points aj , j = 1, . . . , d + 1, in Rd are given with the

property as in Exercise 3.13. Additionally, we de¬ne as in (3.48), (3.49) the

barycentric coordinates »j = »j (x; S) of x with respect to the d-simplex

S generated by the points aj . Show that for each bijective a¬ne-linear

3.4. Convergence Rate Estimates 131

mapping : Rd ’ Rd , »j (x; S) = »j ( (x); (S)), which means that the

barycentric coordinates are invariant under such transformations.

3.19 Discuss for the cubic Hermite ansatz (3.64) and Dirichlet boundary

conditions the choice of the degrees of freedom with regard to the angle

between two edges of boundary elements that is either ± = 2π or ± = 2π.

3.20 Construct a nodal basis for the Bogner“Fox“Schmit element in

(3.65).

3.4 Convergence Rate Estimates

In this section we consider further a ¬nite element approximation in the

framework described in the previous section: The bounded basic domain

„¦ ‚ Rd of the boundary value problem is decomposed into conforming tri-

angulations Th , which may also consist of di¬erent types of elements. Here,

by an element we mean not only the set K ∈ Th , but this equipped with

some ansatz space PK and degrees of freedom ΣK . However, the elements

are supposed to decompose into a ¬xed number of subsets, independent

of h, each consisting of elements that are a¬ne equivalent to each other.

Di¬erent elements have to be compatible with each other such that the

ansatz space Vh , introduced in (3.62), is well-de¬ned. The smoothness of

the functions arising in this way has to be consistent with the boundary

value problem, in so far as Vh ‚ V is guaranteed. In the following we

consider only one element type; the generalization to the more general sit-

uation will be obvious. The goal is to prove a priori estimates of the form

u ’ uh ¤ C|u|h± (3.69)

with constants C > 0, ± > 0 and norms and seminorms · and | · |,

respectively.

We do not attempt to give the constant C explicitly, although in prin-

ciple, this is possible (with other techniques of proof). In particular, in

the following C has to be understood generically; that is, by C we denote

at di¬erent places di¬erent values, which, however, are independent of h.

Therefore, the estimate (3.69) does not serve only to estimate numerically

the error for a ¬xed triangulation Th . It is rather useful for estimating what

gain in accuracy can be expected by increasing the e¬ort, which then corre-

sponds to the reduction of h by some re¬nement (see the discussion around

(3.67)). Independently of the convergence rate ±, (3.69) provides the cer-

tainty that an arbitrary accuracy in the desired norm · can be obtained

at all. In the following, we will impose some geometric conditions on the

family (Th )h , which have always to be understood uniformly in h. For a

¬xed triangulation these conditions are always trivially satis¬ed, since here

132 3. Finite Element Methods for Linear Elliptic Problems

we have a ¬nite number of elements. For a family (Th )h with h ’ 0, thus for

increasing re¬nement, this number becomes unbounded. In the following

estimates we have therefore to distinguish between “variable” values like

the number of nodes M = M (h) of Th , and “¬xed” values like the dimen-

sion d or the dimension of PK or equivalence constants in the renorming

of PK , which can all be included in the generic constant C.

3.4.1 Energy Norm Estimates

If we want to derive estimates in the norm of the Hilbert space V underlying

the variational equation for the boundary value problem, concretely, in the

norm of Sobolev spaces, then C´a™s lemma (Theorem 2.17) shows that for

e

this purpose it is necessary only to specify a comparison element vh ∈ Vh

for which the inequality

u ’ vh ¤ C|u|h± (3.70)

holds. For · = · 1 , these estimates are called energy norm estimates

due to the equivalence of · 1 and · a (cf. (2.46)) in the symmetric

case. Therefore, the comparison element vh has to approximate u as well

as possible, and in genera,l it is speci¬ed as the image of a linear operator

Ih :

vh = Ih (u) .

The classical approach consists in choosing for Ih the interpolation oper-

ator with respect to the degrees of freedom. To simplify the notation, we

restrict ourselves in the following to Lagrange elements, the generalization

to Hermite elements is also easily possible.

We suppose that the triangulation Th has its degrees of freedom in the

nodes a1 , . . . , aM with the corresponding nodal basis •1 , . . . , •M . Then let

M

u(ai )•i ∈ Vh .

Ih (u) := (3.71)

i=1

For the sake of Ih (u) being well-de¬ned, u ∈ C(„¦) has to be assumed in

¯

order to ensure that u can be evaluated in the nodes. This requires a certain

smoothness assumption about the solution u, which we formulate as

u ∈ H k+1 („¦) .

Thus, if we assume again d ¤ 3 for the sake of simplicity, the embedding

theorem (Theorem 3.10) ensures that Ih is well-de¬ned on H k+1 („¦) for

k ≥ 1. For the considered C 0 -elements, we have Ih (u) ∈ H 1 („¦) by virtue

of Theorem 3.20. Therefore, we can substantiate the desired estimate (3.70)

to

u ’ Ih (u) ¤ Ch± |u|k+1 . (3.72)

1

3.4. Convergence Rate Estimates 133

Sobolev (semi) norms can be decomposed into expressions over subsets of

„¦, thus, for instance, the elements of Th ,

2 2

|u|2 = |‚ ± u| dx = |‚ ± u| dx = |u|2 ,

l l,K

„¦ |±|=l K |±|=l

K∈Th K∈Th

and, correspondingly,

2 2

u = u ,

l l,K

K∈Th

where, if „¦ is not basic domain, this will be included in the indices of

the norm. Since the elements K are considered as being closed, K should

more precisely be replaced by int (K). By virtue of this decomposition, it

is su¬cient to prove the estimate (3.72) for the elements K. This has some

analogy to the (elementwise) assembling described in Section 2.4.2, which

is also to be seen in the following. On K, the operator Ih reduces to the

analogously de¬ned local interpolation operator. Suppose the nodes of the

degrees of freedom on K are ai1 , . . . , aiL , where L ∈ N is the same for all

K ∈ Th due to the equivalence of elements. Then

Ih (u)|K = IK (u|K ) for u ∈ C(„¦) ,

¯

where

L

for u ∈ C(K) ,

IK (u) := u(aij )•ij

j=1

since both functions of PK solve the same interpolation problem on K (cf.

Lemma 2.10). Since we have an (a¬ne) equivalent triangulation, the proof

of the local estimate

u ’ IK (u) ¤ Ch± |u|k+1,K (3.73)

m,K

is generally done in three steps:

• Transformation to some reference element K,

ˆ

• Proof of (3.73) on K,

ˆ

• Back transformation to the element K.

To be precise, the estimate (3.73) will even be proved with hK instead of

h, where

hK := diam (K) for K ∈ Th ,

and in the second step, the ¬xed value hK is incorporated in the constant.

ˆ