Proof: As already known from Sections 3.4 and 3.6, the proof is done

locally in K ∈ Th and there transformed to the reference element K by ˆ

means of F (ˆ) = B x + d.

x ˆ

ˆ

Ad (1): All norms are equivalent on the local ansatz space P , thus also

· 0,K and the Euclidean norm in the degrees of freedom. Hence, there

ˆ

exist some C1 , C2 > 0 such that for v ∈ P ,

ˆˆ ˆˆ

1/2

L

¤ |ˆ(ˆi )|2 ¤ C2 v

ˆˆ ˆˆ

C1 v va .

ˆ ˆ

0,K 0,K

i=1

ˆ

Here, a1 , . . . , aL are the degrees of freedom in K. Due to (3.50) we have

ˆ ˆ

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

ˆ

and according to the de¬nition of hK and the regularity of the family (Th )h ,

˜

there exist constants Ci > 0 independent of h such that

C1 hd ¤ C3 ¤ | det(B)| ¤ C2 hd .

˜ ˜ ˜

d

K K K

By the transformation rule we thus obtain for v ∈ PK , the ansatz space on

K, that

1/2

L

1/2

C1 | det(B)|1/2 v ¤ C2 hd |ˆ(ˆi )|2

ˆ ˆ ˜

C1 v = ˆ va

0,K ˆ K

0,K

i=1

1/2

1/2 L

1/2

˜ 1/2 hd |v(ai )|2 |ˆ(ˆi )|2

˜K

= C2 hd

= C2 va

K

ai ∈K i=1

1/2 1/2

C2 | det(B)|’1/2 v

¤ ˜ ˆˆ ˜ ˆ

C2 hd = C2 hd

C2 v ˆ 0,K

K K

0,K

˜ 1/2 ˆ ˜ ’1/2 v

¤ C2 C2 C1 0,K .

This implies assertion (1).

Ad (2): Arguing as before, now using the equivalence of · 1,K andˆ

· 0,K in P , it follows by virtue of (3.86) for v ∈ PK (with the generic

ˆ

ˆ

constant C) that

¤ C h’1 v

¤ C | det(B)|1/2 B ’1 ¤ C B ’1

v v

ˆ v

ˆ

1,K 2 2 0,K 0,K

K

0,K

by Theorem 3.27 and the regularity of (Th )h , and from this, the assertion

2

(2).

In order to make the norm · 0,h comparable with the (weighted)

Euclidean norm we assume in the following:

• There exists a constant CA > 0 independent of h

such that for every node of Th , the number of elements (3.137)

to which this node belongs is bounded by CA .

3.7. Condition Number of Finite Element Matrices 165

This condition is (partly) redundant: For d = 2 and triangular elements,

the condition follows from the uniform lower bound (3.93) for the smallest

angle as an implication of the regularity. Note that the condition need not

be satis¬ed if only the maximum angle condition is required.

In general, if C ∈ RM,M is a matrix with real eigenvalues »1 ¤ · · · ¤

»M and an orthonormal basis of eigenvectors ξ 1 , . . . , ξ M , for instance a

symmetric matrix, then it follows for ξ ∈ RM \ {0} that

ξT Cξ

»1 ¤ T ¤ »M , (3.138)

ξξ

and the bounds are assumed for ξ = ξ 1 and ξ = ξ M .

Theorem 3.44 There exists a constant C > 0 independent of h such that

we have

d

h

κ(B) ¤ C

min hK

K∈Th

for the spectral condition number of the mass matrix B according to (3.135).

Proof: κ(B) = »M /»1 must be determined. For arbitrary ξ ∈ RM \ {0}

we have

2

ξ T Bξ ξT Bξ v 0,h

= ,

v2

ξT ξ ξT ξ

0,h

M

where v := i=1 ξi •i ∈ Vh . By virtue of ξ T Bξ = v, v 0 , the ¬rst factor on

the right-hand side is uniformly bounded from above and below according

to Theorem 3.43. Further, by (3.137) and ξ = (v(a1 ), . . . , v(aM ))T it follows

that

min hd |ξ|2 ¤ v ¤ CA hd |ξ|2 ,

2

K 0,h

K∈Th

and, thus the second factor is estimated from above and below. This leads

to estimates of the type

»1 ≥ C1 min hd , »M ¤ C2 hd ,

K

K∈Th

2

and from this, the assertion follows.

Therefore, if the family of triangulations (Th )h is quasi-uniform in the

sense that there exists a constant C > 0 independent of h such that

h ¤ C hK for all K ∈ Th , (3.139)

then κ(B) is uniformly bounded.

In order to be able to argue analogously for the sti¬ness matrix, we

assume that we stay close to the symmetric case:

166 3. Finite Element Methods for Linear Elliptic Problems

Theorem 3.45 Suppose the sti¬ness matrix A (3.134) admits real eigen-

values and a basis of eigenvectors. Then there exists a constant C > 0

independent of h such that the following estimates for the spectral condition

number κ hold:

’2

’1

A) ¤

κ(B C min hK ,

K∈Th

’2

κ(A) ¤ C min hK κ(B) .

K∈Th

Proof: With the notation of (3.138), we proceed analogously to the proof

of Theorem 3.44. Since

ξ T Aξ ξ T Aξ ξ T Bξ

=T ,

ξT ξ ξ Bξ ξ T ξ

it su¬ces to bound the ¬rst factor on the right-hand side from above and

below. This also yields a result for the eigenvalues of B ’1 A, since we have

for the variable · := B 1/2 ξ,

· T B ’1/2 AB ’1/2 ·

ξ T Aξ

= ,

ξ T Bξ ·T ·

and the matrix B ’1/2 AB ’1/2 possesses the same eigenvalues as B ’1 A by

virtue of B ’1/2 (B ’1/2 AB ’1/2 )B 1/2 = B ’1 A. Here, B 1/2 is the symmet-

ric positive de¬nite matrix that satis¬es B 1/2 B 1/2 = B, and B ’1/2 is its

inverse.

Since ξT Aξ/ξT Bξ = a(v, v)/ v, v 0 and

≥ ≥± v

2 2

a(v, v) ±v ,

1 0

’2 (3.140)

¤ ¤C

2 2

a(v, v) Cv min hK v 0,

1

K∈Th

with a generic constant C > 0 (the last estimate is due to Theorem 3.43,

2), it follows that

’2

ξT Aξ

a(v, v) a(v, v)

±¤ ¤C

=T = min hK , (3.141)

v, v 0 v, v 0

ξ Bξ K∈Th

2

and from this the assertion.

The analysis of the eigenvalues of the model problem in Example 2.12

shows that the above-given estimates are not too pessimistic.

3.8. General Domains and Isoparametric Elements 167

3.8 General Domains and Isoparametric Elements

All elements considered so far are bounded by straight lines or plane sur-

faces. Therefore, only polyhedral domains can be decomposed exactly by

means of a triangulation. Depending on the application, domains with a

curved boundary may appear. With the available elements the obvious way

of dealing with such domains is the following (in the two-dimensional case):

for elements K that are close to the boundary put only the nodes of one

edge on the boundary ‚„¦. This implies an approximation error for the

domain, for „¦h := K∈Th K, there holds in general neither „¦ ‚ „¦h nor

„¦h ‚ „¦ (see Figure 3.14).

B

Figure 3.14. „¦ and „¦h .

As the simplest example, we consider homogeneous Dirichlet boundary

conditions, thus V = H0 („¦), on a convex domain for which therefore „¦h ‚

1

„¦ is satis¬ed. If an ansatz space Vh is introduced as in Section 3.3, then

functions de¬ned on „¦h are generated. Therefore, these functions must be

extended to „¦ in such a way that they vanish on ‚„¦, and consequently, for

the generated function space Vh , Vh ‚ V . This is supposed to be done by

˜˜

adding the domains B whose boundary consists of a boundary part of some

element K ∈ Th close to the boundary and a subset of ‚„¦ to the set of

elements with the ansatz space P (B) = {0}. C´a™s lemma (Theorem 2.17)

e

can still be applied, so that for an error estimate in · 1 the question of

how to choose a comparison element v ∈ Vh arises. The ansatz v = Ih (u),

˜ ˜

˜

where Ih (u) denotes the interpolation on „¦h extended by 0 on the domains

B, is admissible only for the (multi-)linear ansatz: Only in this case are all

nodes of an edge “close to the boundary” located on ‚„¦ and therefore have

homogeneous degrees of freedom, so that the continuity on these edges is

ensured. For the present, let us restrict our attention to this case, so that

u ’ Ih (u) 1 has to be estimated where u is the solution of the boundary

˜

value problem.

The techniques of Section 3.4 can be applied to all K ∈ Th , and by the

conditions assumed there about the triangulation, this yields

u ’ uh ¤ u ’ Ih (u)

C +u

1 1,„¦h 1,„¦\„¦h

¤ C h|u|2,„¦h + u .

1,„¦\„¦h

168 3. Finite Element Methods for Linear Elliptic Problems

If ‚„¦ ∈ C 2 , then we have the estimate

¤ Ch u

u 2,„¦

1,„¦\„¦h

for the new error part due to the approximation of the domain, and thus

the convergence rate is preserved. Already for a quadratic ansatz this is no

longer satis¬ed, where only

u ’ uh ¤ Ch3/2 u

1 3

holds instead of the order O(h2 ) of Theorem 3.29 (see [31, pp. 194 ¬]).

One may expect that this decrease of the approximation quality arises only

locally close to the boundary, however, one may also try to obtain a better

approximation of the domain by using curved elements. Such elements can

ˆ ˆˆ

be de¬ned on the basis of the reference elements (K, P , Σ) of Lagrange type

introduced in Section 3.3 if a general element is obtained from this one by

an isoparametric transformation; that is, choose an

F ∈ (P )d

ˆ (3.142)

that is injective and then

P := p —¦ F ’1 p ∈ P , Σ := F (ˆ) a ∈ Σ .

ˆ ˆˆ aˆˆ

K := F (K) , ˆ

Since the bijectivity of F : K ’ K is ensured by requirement, a ¬nite

ˆ

element is thus de¬ned in terms of (3.58). By virtue of the unique solvability

of the interpolation problem, F can be de¬ned by prescribing a1 , . . . , aL ,

L = |Σ|, and requiring

ˆ

F (ˆi ) = ai ,

a i = 1, . . . , L .

However, this does not in general ensure the injectivity. Since, on the other

hand, in the grid generation process elements are created by de¬ning the

nodes (see Section 4.1), geometric conditions about their positions that

characterize the injectivity of F are desirable. A typical curved element

that can be used for the approximation of the boundary can be generated

on the basis of the unit simplex with P = P2 (K) (see Figure 3.15).

ˆ ˆ

â3 a3

a1 3

â2 3 2

F ∈ P2 (K)

ˆ

â1 3 a2 3

E

a1

a2

â1 â2

â1 2 a1 2

Figure 3.15. Isoparametric element: quadratic ansatz on triangle.

Elements with, in general, one curved edge and otherwise straight edges

thus are suggested for the problem of boundary approximation. They are

3.8. General Domains and Isoparametric Elements 169

combined with a¬ne “quadratic triangles” in the interior of the domain.

Subparametric elements can be generated analogously to the isoparametric

elements if (the components of) the transformations in (3.142) are restricted

to some subspace PT ‚ P . If PT = P1 (K), we again obtain the a¬ne

ˆ ˆ ˆ ˆ

equivalent elements.

However, isoparametric elements are also important if, for instance, the

unit square or cube is supposed to be the reference element. Only the

isoparametric transformation allows for “general” quadrilaterals and hex-

ahedra, respectively, which are preferable in anisotropic cases (for instance

in generalization of Figure 3.11) to simplices due to their adaptability to

ˆ ˆ ˆ

local coordinates. In what follows, let K = [0, 1]d , P = Q1 (K).

In general, since also a ¬nite element (in Rd’1 ) is de¬ned for every face

S of K with P |S and Σ|S , the “faces” of K, that is, F [S], are already

ˆ ˆ ˆˆ ˆˆ ˆ

uniquely de¬ned by the related nodes.

Consequently, if d = 2, the edges of the general quadrilateral are straight

lines (see Figure 3.16), but if d = 3, we have to expect curved surfaces

(hyperbolic paraboloids) for a general hexahedron.

a3

â4 â3 a4

ˆ2

F ∈ Q1 (K)

E

a1 a2

â2

â1

Figure 3.16. Isoparametric element: bilinear ansatz on rectangle.

A geometric characterization of the injectivity of F is still unknown (to

our knowledge) for d = 3, but it can be easily derived for d = 2: Let the

nodes a1 , a2 , a3 , a4 be numbered counterclockwise and suppose that they

are not on a straight line, and thus (by rearranging) T = conv (a1 , a2 , a4 )

forms a triangle such that

2 vol (T ) = det(B) > 0 .

Here FT (ˆ) = B x + d is the a¬ne-linear mapping that maps the refer-

x ˆ

’1

ence triangle conv (ˆ1 , a2 , a4 ) bijectively to T . If a3 := FT (a3 ), then the

aˆˆ ˜

˜

quadrilateral K with the vertices a1 , a2 , a3 , a4 is mapped bijectively to K

ˆˆ˜ˆ

by FT .

The transformation F can be decomposed into

F = FT —¦ FQ ,

2

where FQ ∈ Q1 (K)

ˆ denotes the mapping de¬ned by

FQ (ˆi ) = ai ,

a ˆ i = 1, 2, 4 , FQ (ˆ3 ) = a3

a ˜

170 3. Finite Element Methods for Linear Elliptic Problems

(see Figure 3.17).

x2

^

x2

^

a4

1 1

â4 â3 â4

ã3

a3

FT

FQ ˜

^