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)