, 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