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.

ˆ

The powers of hK are due to the transformation steps.

ˆ

Therefore, let some reference element K with the nodes a1 , . . . , aL be

ˆ ˆ

chosen as ¬xed. By assumption, there exists some bijective, a¬ne-linear

134 3. Finite Element Methods for Linear Elliptic Problems

mapping

F = FK : K ’ K ,

ˆ

(3.74)

F (ˆ) = B x + d ,

x ˆ

(cf. (2.30) and (3.57)). By this transformation, functions v : K ’ R are

mapped to functions v : K ’ R by

ˆˆ

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

ˆx x (3.75)

This transformation is also compatible with the local interpolation operator

in the following sense:

IK (v) = IK (ˆ) for v ∈ C(K) .

ˆv (3.76)

This follows from the fact that the nodes of the elements as well as the

shape functions are mapped onto each other by F .

For a classically di¬erentiable function the chain rule (see (2.49)) implies

∇x v(F (ˆ)) = B ’T ∇x v (ˆ) ,

x ˆˆ x (3.77)

and corresponding formulas for higher-order derivatives, for instance,

Dx v(F (ˆ)) = B ’T Dx v (ˆ)B ’1 ,

2 2

x ˆˆ x

2

where Dx v(x) denotes the matrix of the second-order derivatives. These

chain rules hold also for corresponding v ∈ H l (K) (Exercise 3.22).

The situation becomes particularly simple in one space dimension (d =

1). The considered elements reduce to a polynomial ansatz on simplices,

which here are intervals. Thus

F : K = [0, 1] ’ K = [ai1 , ai2 ] ,

ˆ

x ’ hK x + ai1 ,

ˆ ˆ

where hK := ai2 ’ ai1 denotes the length of the element. Hence, for l ∈ N,

‚x v(F (ˆ)) = h’l ‚x v (ˆ) .

l l

x K ˆˆ x

By the substitution rule for integrals (cf. (2.50)) an additional factor

| det(B)| = hK arises such that, for v ∈ H l (K), we have

2l’1

1

|v|2 |ˆ|2 K .

= v l, ˆ

l,K

hK

Hence, for 0 ¤ m ¤ k + 1 it follows by (3.76) that

2m’1

1 2

IK (v)|2

|v ’ v ’ IK (ˆ)

= ˆ ˆv .

ˆ

m,K m,K

hK

Thus, what is missing, is an estimate of the type

v ’ IK (ˆ) ¤ C|ˆ|k+1,K

ˆ ˆv v (3.78)

ˆ

ˆ

m,K

3.4. Convergence Rate Estimates 135

for v ∈ H k+1 (K). In speci¬c cases this can partly be proven directly but

ˆ

ˆ

in the following a general proof, which is also independent of d = 1, will be

sketched. For this, the mapping

G : H k+1 (K) ’ H m (K) ,

ˆ ˆ

(3.79)

v ’ v ’ IK (ˆ) ,

ˆ ˆ ˆv

is considered. The mapping is linear but also continuous, since

L

¤

IK (ˆ)

ˆv v (ˆi )•i

ˆa ˆ

ˆ

m,K

ˆ

i=1 k+1,K

(3.80)

L

¤ ¤C v

•i

ˆ v

ˆ ˆ ,

ˆ ˆ ˆ

∞,K

k+1,K k+1,K

i=1

ˆ ˆ

where the continuity of the embedding of H k+1 (K) in H m (K) (see

ˆ ˆ

(3.8)) and of H k+1 (K) in C(K) (Theorem 3.10) is used, and the norm

contribution from the ¬xed basis functions •i is included in the constant.

ˆ

ˆ is chosen in such a way that Pk ‚ P , then G has

ˆ

If the ansatz space P

the additional property

G(p) = 0 for p ∈ Pk ,

since these polynomials are interpolated then exactly. Such mappings sat-

isfy the Bramble“Hilbert lemma, which will directly be formulated, for

further use, in a more general way.

Theorem 3.24 (Bramble“Hilbert lemma)

Suppose K ‚ Rd is open, k ∈ N0 , 1 ¤ p ¤ ∞, and G : Wp (K) ’ R is a

k+1

continuous linear functional that satis¬es

for all q ∈ Pk .

G(q) = 0 (3.81)

Then there exists some constant C > 0 independent of G such that for all

v ∈ Wp (K)

k+1

|G(v)| ¤ C G |v|k+1,p,K .

2

Proof: See [9, Theorem 28.1].

Here G denotes the operator norm of G (see (A4.25)). The estimate

with the full norm · k+1,p,K on the right-hand side (and C = 1) would

hence only be the operator norm™s de¬nition. The condition (3.81) allows

the reduction to the highest seminorm.

For the application of the Bramble“Hilbert lemma (Theorem 3.24), which

was formulated only for functionals, to the operator G according to (3.79)

an additional argument is required (alternatively, Theorem 3.24 could be

generalized):

136 3. Finite Element Methods for Linear Elliptic Problems

Generally, for w ∈ H m (K) (as in every normed space) we have

ˆ

ˆ

w

ˆ = sup •(w) ,

ˆ (3.82)

ˆ

m,K

ˆ

•∈(H m (K))

• ¤1

where the norm applying to • is the operator norm de¬ned in (A4.25).

For any ¬xed • ∈ (H m (K)) the linear functional on H k+1 (K) is de¬ned

ˆ ˆ

by

for v ∈ H k+1 (K) .

˜v ˆ

G(ˆ) := •(G(ˆ))

v ˆ (3.83)

˜

According to (3.80), G is continuous and it follows that

G¤•

˜ G.

˜

Theorem 3.24 is applicable to G and yields

|G(ˆ)| ¤ C • G |ˆ|k+1,K .

˜v v ˆ

By means of (3.82) it follows that

¤ C G |ˆ|k+1,K .

G(ˆ)

v v

ˆ ˆ

m,K

The same proof can also be used in the proof of Theorem 3.31 (3.94).

Applied to G de¬ned in (3.79), the estimate (3.80) shows that the

operator norm Id ’ IK can be estimated independently from m (but

ˆ

dependent on k and the •i ) and can be incorporated in the constant that

ˆ

gives (3.78) in general, independent of the one-dimensional case.

Therefore, in the one-dimensional case we can continue with the

estimation and get

2m’1

1

IK (v)|2

|v ’ ¤ C|ˆ|2 K ¤ C(hK )1’2m+2(k+1)’1 |v|2

v k+1, ˆ k+1,K .

m,K

hK

Since due to Ih (v) ∈ H 1 („¦) we have for m = 0, 1

|v ’ IK (v)|2

m,K = |v ’ Ih (v)|m ,

2

K∈Th

we have proven the following Theorem:

Theorem 3.25 Consider in one space dimension „¦ = (a, b) the polyno-

mial Lagrange ansatz on elements with maximum length h and suppose that

for the respective local ansatz spaces P , the inclusion Pk ‚ P is satis¬ed

for some k ∈ N. Then there exists some constant C > 0 such that for all

v ∈ H k+1 („¦) and 0 ¤ m ¤ k + 1,

1/2

|v ’ IK (v)|2 ¤ Chk+1’m |v|k+1 .

m,K

K∈Th

If the solution u of the boundary value problem (3.12), (3.18)“(3.20) belongs

to H k+1 („¦), then we have for the ¬nite element approximation uh according

3.4. Convergence Rate Estimates 137

to (3.39),

u ’ uh ¤ Chk |u|k+1 .

1

Note that for d = 1 a direct proof is also possible (see Exercise 3.21).

Now we address to the general d-dimensional situation: The seminorm

| · |1 is transformed, for instance, as follows (cf. (2.49)):

B ’T ∇x v · B ’T ∇x v | det(B)| dˆ .

|v|2 = |∇x v|2 dx = ˆˆ ˆˆ x (3.84)

1,K

ˆ

K K

From this, it follows for v ∈ H 1 (K) that

ˆ

ˆ

|v|1,K ¤ C B ’1 | det(B)|1/2 |ˆ|1,K .

vˆ

Since d is one of the mentioned “¬xed” quantities and all norms on Rd,d

are equivalent, the matrix norm · can be chosen arbitrarily, and it is

also possible to change between such norms. In the above considerations K

and K had equal rights; thus similarly for v ∈ H 1 (K), we have

ˆ

|ˆ|1,K ¤ C B | det(B)|’1/2 |v|1,K .

vˆ

In general, we have the following theorem:

Theorem 3.26 Suppose K and K are bounded domains in Rd that are

ˆ

mapped onto each other by an a¬ne bijective linear mapping F , de¬ned in

(3.74). If v ∈ Wp (K) for l ∈ N and p ∈ [1, ∞], then we have for v (de¬ned

l

ˆ

in (3.75)), v ∈ Wp (K), and for some constant C > 0 independent of v,

lˆ

ˆ

| det(B)|’1/p |v|l,p,K ,

|ˆ|l,p,K ¤ l

v CB (3.85)

ˆ

C B ’1

|v|l,p,K ¤ | det(B)|1/p |ˆ|l,p,K .

l

v (3.86)

ˆ

2

Proof: See [9, Theorem 15.1].

For further use, also this theorem has been formulated in a more general

way than would be necessary here. Here, only the case p = 2 is relevant.

Hence, if we use the estimate of Theorem 3.24, then the value B (for

some matrix norm) has to be related to the geometry of K. For this, let

for K ∈ Th ,

:= sup diam (S) S is a ball in Rd and S ‚ K .

K

Hence, in the case of a triangle, hK denotes the longest edge and K the

diameter of the inscribed circle. Similarly, the reference element has its

ˆ

(¬xed) parameters h and ˆ. For example, for the reference triangle with

ˆ

the vertices a1 = (0, 0), a2 = (1, 0), a3 = (0, 1) we have that h = 21/2 and