ˆ ˆ

formula is exact for P2k’2 (K):

ˆ

for all v ∈ P2k’2 (K) .

ˆv ˆ

E(ˆ) = 0 ˆ (3.128)

Then there exist some constant C > 0 independent of h > 0 and K ∈ Th

such that for l ∈ {1, k} the following estimates are given:

|EK (apq)| ¤ Chl a

(1) p q

k,∞,K l’1,K 0,K

K

for a ∈ W∞ (K) , p, q ∈ Pk’1 (K) ,

k

|EK (cpq)| ¤ Chl c

(2) p q

k,∞,K l’1,K 1,K

K

for c ∈ W∞ (K) , p ∈ Pk’1 (K) , q ∈ Pk (K) ,

k

|EK (rpq)| ¤ Chl r

(3) p q

k,∞,K l,K 1,K

K

for r ∈ W∞ (K) , p, q ∈ Pk (K) ,

k

|EK (f q)| ¤ Chk f 1/2

(4) k,∞,K vol (K) q 1,K

K

for f ∈ W∞ (K) , q ∈ Pk (K) .

k

The (unnecessarily varied) notation of the coe¬cients already indicates

the ¬eld of application of the respective estimate. The smoothness assump-

tion concerning the coe¬cients in (1)“(3) can be weakened to some extent.

We prove only assertion (1). However, a direct application of this proof to

assertions (2)“(4) leads to a loss of convergence rate (or higher exactness

conditions for the quadrature). Here, quite technical considerations includ-

ing the insertion of projections are necessary, which can be found to some

extent in [9, pp. 201“203]. In the following proof we intensively make use

of the fact that all norms are equivalent on the “¬xed” ¬nite-dimensional

ansatz space Pk (K). The assumption (3.128) is equivalent to the same con-

ˆ

dition on a general element. However, the formulation already indicates an

assumption that is also su¬cient in more general cases.

3.6. Convergence Rate Results in Case of Quadrature and Interpolation 159

Proof of Theorem 3.41, (1): We consider a general element K ∈ Th

and mappings a ∈ W∞ (K), p, q ∈ Pk’1 (K) on it and, moreover, mappings

k

a ∈ W∞ (K), p, q ∈ Pk’1 (K) de¬ned according to (3.75). First, the proof

kˆ ˆ

ˆ ˆˆ

is done for l = k. On the reference element K, for v ∈ W∞ (K) and q ∈

ˆ kˆ

ˆ ˆ

Pk’1 (K)), we have

ˆ

R

ωl (ˆq )(ˆl ) ¤ C v q

v q dˆ ’ ¤C v

ˆ vˆ

E(ˆq ) = ˆˆ x ˆ vˆ b ˆˆ ˆ q

ˆ ,

ˆ ˆ ˆ

∞,K ∞,K ∞,K

ˆ

K l=1

kˆ ˆ

where the continuity of the embedding of W∞ (K) in C(K) is used (see [8,

p. 181]). Therefore, by the equivalence of · ∞,K and · 0,K on Pk’1 (K),

ˆ

ˆ ˆ

it follows that

E(ˆq ) ¤ C v k,∞,K q 0,K .

ˆ vˆ ˆ ˆˆ ˆ

If a ¬xed q ∈ Pk’1 (K) is chosen, then a linear continuous functional G is

ˆ

ˆ

de¬ned on W∞ (K) by v ’ E(ˆq ) that has the following properties:

kˆ ˆ vˆ

ˆ

G ¤ C q ˆ and G(ˆ) = 0 for v ∈ Pk’1 (K) ˆ

ˆ v ˆ

0,K

by virtue of (3.128).

The Bramble“Hilbert lemma (Theorem 3.24) implies

E(ˆq ) ¤ C |ˆ|k,∞,K q 0,K .

ˆ vˆ v ˆˆ ˆ

According to the assertion we now choose

v = ap for a ∈ W k,∞ (K) , p ∈ Pk’1 (K) ,

ˆ ˆ

ˆ ˆˆ ˆ ˆ

and we have to estimate |ˆp|k,∞K (thanks to the Bramble“Hilbert lemma

aˆ ˆ

not ap k,∞,K ). The Leibniz rule for the di¬erentiation of products implies

ˆˆ ˆ

the estimate

k

|ˆp|k,∞,K ¤ C |ˆ|k’j,∞,K |ˆ|j,∞,K .

aˆ a ˆp (3.129)

ˆ ˆ

j=0

ˆ

Here the constant C depends only on k, but not on the domain K.

Since p ∈ Pk’1 (K), the last term of the sum in (3.129) can be omitted.

ˆ

ˆ

Therefore, we have obtained the following estimate holding for a ∈ W∞ (K),

kˆ

ˆ

p, q ∈ Pk’1 (K):

ˆ

ˆˆ

k’1

¤ |ˆ|k’j,∞,K |ˆ|j,∞,K

ˆ a ˆˆ

E(ˆpq ) C a ˆp q

ˆ

ˆ ˆ

0,K

j=0

(3.130)

k’1

¤ |ˆ|k’j,∞,K |ˆ|j,K

C a ˆp ˆ q

ˆ .

ˆ

0,K

j=0

The last estimate uses the equivalence of · ∞ and · 0 on Pk’1 (K). ˆ

ˆ

We suppose that the transformation F of K to the general element K

has, as usual, the linear part B. The ¬rst transformation step yields the

160 3. Finite Element Methods for Linear Elliptic Problems

factor | det(B)| according to (3.115), and for the backtransformation it

follows from Theorem 3.26 and Theorem 3.27 that

C hk’j |a|k’j,∞,K ,

|ˆ|k’j,∞,K ¤

a ˆ K

C hj | det(B)|’1/2 |p|j,K ,

|ˆ|j,K ¤ (3.131)

pˆ K

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

¤

q

ˆ ˆ 0,K

0,K

for 0 ¤ j ¤ k ’ 1. Here a, p, q are the mappings a, p, q (back)transformed

ˆˆˆ

according to (3.75). Substituting these estimates into (3.130) therefore

yields

k’1

EK (apq) ¤ C |a|k’j,∞,K |p|j,K

hk q 0,K

K

j=0

and from this, assertion (1) follows for l = k.

If l = 1, we modify the proof as follows. Again, in (3.130) we estimate

by using the equivalence of norms:

k’1

¤C |ˆ|k’j,∞,K p

ˆ a ˆˆ

E(ˆpq ) a ˆˆ q

ˆ

ˆ ˆ

j,∞,K 0,K

j=0

k’1

¤C |ˆ|k’j,∞,K

a p

ˆ q

ˆ .

ˆ ˆ ˆ

0,K 0,K

j=0

The ¬rst and the third estimates of (3.131) remain applicable; the second

estimate is replaced with the third such that we have

k’1

EK (apq) ¤ C hK |a|k’j,∞,K ,p q

0,K 0,K

j=0

since the lowest hK -power arises for j = k ’ 1. This estimate yields the

2

assertion (1) for l = 1 .

Finally, we can now verify the assumptions of Theorem 3.38 with the

following result:

Theorem 3.42 Consider a family of a¬ne equivalent Lagrange ¬nite el-

ement discretizations in Rd , d ¤ 3, with P = Pk for some k ∈ N as local

ansatz space. Suppose that the family of triangulations is regular or sat-

is¬es the maximum angle condition in the case of triangles with k = 1.

Suppose that the applied quadrature formulas are exact for P2k’2 . Let the

function w satisfying the Dirichlet boundary condition and let the solution

u of the boundary value problem (3.12), (3.18)“(3.20) (with g3 = 0) belong

to H k+1 („¦).

¯

Then there exist some constants C > 0, h > 0 independent of u and w

such that for the ¬nite element approximation uh +wh according to (3.105),

¯

3.6. Convergence Rate Results in Case of Quadrature and Interpolation 161

¯

(3.121), it follows for h ¤ h that

d

u + w ’ (¯h + wh ) ¤Ch |u|k+1 + |w|k+1 +

k

u kij k,∞

1

i,j=1

d

+ ci +r u +w +f .

k,∞ k,∞ k+1 k+1 k,∞

i=1

¯

¯

Proof: According to (3.108), we aim at estimating u+w’(uh + Ih (w)) 1 ,

¯

where uh satis¬es (3.122).

By virtue of Theorem 3.29 or Theorem 3.35 (set formally “3 = …) we

have

w ’ Ih (w) ¤ Chk |w|k+1 .

¯ (3.132)

1

For the bilinear form ah de¬ned in (3.120), it follows from Theorem 3.41

for v, w ∈ Vh and l ∈ {0, k} that

d

a(v, w) ’ ah (v, w) ¤ EK (kij ‚j (v|K )‚i (w|K )) (3.133)

i,j=1

K∈Th

d

+ EK (ci ‚i (v|K )w) + EK (rvw)

i=1

d d

¤C hl kij + ci +r

k,∞,K k,∞,K k,∞,K

K

i,j=1 i=1

K∈Th

—v w

l,K 1,K

d d

¤ Ch l

kij + ci +r

k,∞ k,∞ k,∞

i,j=1 i=1

1/2

— 2

v w 1,

l,K

K∈Th

by estimating the · k,∞,K -norms in terms of norms on the domain „¦ and

then applying the Cauchy“Schwarz inequality with “index” K ∈ Th .

From this we obtain for l = 1 an estimate of the form

|a(v, w) ’ ah (v, w)| ¤ Ch v w

1 1

such that the estimate required in Lemma 3.39 holds (with C(h) = C · h).

Therefore, there exists some ¯ > 0 such that ah is uniformly Vh -elliptic

h

¯ Hence, the estimate (3.126) is applicable, and the ¬rst addend,

for h ¤ h.

the approximation error, behaves as asserted according to Theorem 3.29 or

Theorem 3.35 (again, choose v = Ih (u) for the comparison element).

In order to estimate the consistency error of ah , a comparison element

v ∈ Vh has to be found for which the corresponding part of the norm in

162 3. Finite Element Methods for Linear Elliptic Problems

(3.133) is uniformly bounded. This is satis¬ed for v = Ih (u), since

1/2 1/2

¤ u ’ Ih (u)

2 2

Ih (u) u +

k

k,K k,K

K∈Th K∈Th

¤ + Ch|u|k+1 ¤ u

u k k+1

due to Theorem 3.29 or Theorem 3.35.

Hence, the consistency error in a behaves as asserted according to (3.133),

so that only the consistency error of l has to be investigated: We have

l ’ lh = b ’ bh ’ a(w, ·) + ah (Ih (w), ·) ,

¯

where bh is de¬ned in (3.120).

If v ∈ Vh , then

a(w, v)’ah (Ih (w), v) ¤ a(w, v)’a(Ih (w), v) + a(Ih (w), v)’ah (Ih (w), v) .

¯ ¯ ¯ ¯

For the ¬rst addend the continuity of a implies

a(w, v) ’ a(Ih (w), v) ¤ C w ’ Ih (w)

¯ ¯ v ,

1

1

so that the corresponding consistency error part behaves like w ’ Ih (w) 1 ,

¯

which has already been estimated in (3.132). The second addend just cor-

responds to the estimate used for the consistency error in a (here, the

¯

di¬erence between Ih and Ih is irrelevant), so that the same contribution to

the convergence rate, now with u k+1 replaced by w k+1 , arises. Finally,

Theorem 3.41, (4) yields for v ∈ Vh ,

|b(v) ’ b(vh )| ¤ |EK (f v)| ¤ C hk vol (K)1/2 f v

k,∞,K 1,K

K

K∈Th K∈Th

¤ C hk |„¦|1/2 f v

k,∞ 1

by proceeding as in (3.133). This implies the last part of the asserted

2

estimate.

If the uniform Vh -ellipticity of ah is ensured in a di¬erent way (perhaps

by Lemma 3.40), one can dispense with the smallness assumption about h.

If estimates as given in Theorem 3.41 are also available for other types of

elements, then triangulations consisting of combinations of various elements

can also be considered.

3.7. The Condition Number of Finite Element Matrices 163

3.7 The Condition Number of Finite Element

Matrices

The stability of solution algorithms for linear systems of equations as de-

scribed in Section 2.5 depends on the condition number of the system

matrix (see [28, Chapter 1]). The condition number also plays an impor-

tant role for the convergence behavior of iterative methods, which will be

discussed in Chapter 5. Therefore, in this section we shall estimate the

spectral condition number (see Appendix A.3) of the sti¬ness matrix

A = a(•j , •i ) (3.134)

i,j=1,...,M

and also of the mass matrix (see (7.45))

B= •j , •i , (3.135)

0 i,j=1,...,M

which is of importance for time-dependent problems. Again, we consider a

¬nite element discretization in the general form of Section 3.4 restricted to

Lagrange elements. In order to simplify the notation, we assume the a¬ne

equivalence of all elements. Further we suppose that

• the family (Th )h of triangulations is regular.

We assume that the variational formulation of the boundary value problem

leads to a bilinear form a that is V -elliptic and continuous on V ‚ H 1 („¦).

As a modi¬cation of de¬nition (1.18), let the following norm (which is

also induced by a scalar product) be de¬ned in the ansatz space Vh =

span{•1 , . . . , •M }:

1/2

|v(ai )|

hd 2

v := . (3.136)

0,h K

ai ∈K

K∈Th

Here, a1 , . . . , aM denote the nodes of the degrees of freedom, where in order

to simplify the notation, M instead of M1 is used for the number of degrees

of freedom. The norm properties follow directly from the corresponding

properties of | · |2 except for the de¬niteness. But the de¬niteness follows

from the uniqueness of the interpolation problem in Vh with respect to

degrees of freedom ai .

Theorem 3.43 (1) There exist constants C1 , C2 > 0 independent of h

such that for v ∈ Vh :

¤v ¤ C2 v

C1 v .

0 0,h 0

(2) There exists a constant C > 0 independent of h such that for v ∈ Vh ,

’1

¤C

v min hK v 0.

1

K∈Th