aM1 +1 , . . . , aM ‚„¦ .

This kind of arrangement of the nodes is chosen only for the sake

of simplicity of the notation and is not essential for the following

considerations.

a• a8

•

a9 d

10

£d

• £

¨

¨t d

K1 £

K2 ¨

• K5

¨ £ K6 d

t

a11 t a1 ¨

•

¨ d

t£ $•

K3 $

K4

t ¡t a2 t £ $$$ 5 a7 5

K12 t$

t¡t • • 5

¢ a3 5

K10 f

t• K11t ¢

t¡ f K8¢ K7 5

a4

t• 5

K9 f

t ¢5

a5 f•

5

f¢

a 6

Figure 2.4. A conforming triangulation with N = 12, M = 11, M1 = 3, M2 = 8.

An approximation of the boundary value problem (2.1), (2.2) with linear

¬nite elements on a given triangulation Th of „¦ is obtained if the ansatz

space Vh is de¬ned as follows:

Vh := u ∈ C(„¦) u|K ∈ P1 (K) for all K ∈ Th , u = 0 on ‚„¦ .

¯ (2.27)

58 2. Finite Element Method for Poisson Equation

Here P1 (K) denotes the set of polynomials of ¬rst degree (in 2 variables)

on K; i.e., p ∈ P1 (K) ” p(x, y) = ± + βx + γy for all (x, y) ∈ K and for

¬xed ±, β, γ ∈ R.

Since p ∈ P1 (K) is also de¬ned on the space R — R, we use the short but

inaccurate notation P1 = P1 (K); according to the context, the domain of

de¬nition will be given as R — R or as a subset of it.

We have

Vh ‚ V .

This is clear for the case of de¬nition of V by (2.7) because ‚x u|K = const,

‚y u|K = const for K ∈ Th for all u ∈ Vh . If V = H0 („¦), then this inclusion

1

is not so obvious. A proof will be given in Theorem 3.20 below.

An element u ∈ Vh is determined uniquely by the values u(ai ), i =

1, . . . , M1 (the nodal values).

In particular, the given nodal values already enforce the continuity of the

piecewise linear composed functions. Correspondingly, the homogeneous

Dirichlet boundary condition is satis¬ed if the nodal values at the boundary

nodes are set to zero.

In the following, we will demonstrate these properties by an unnecessar-

ily involved proof. The reason is that this proof will introduce all of the

considerations that will lead to analogous statements for the more general

problems of Section 3.4.

Let Xh be the larger ansatz space consisting of continuous, piecewise

linear functions but regardless of any boundary conditions, i.e.,

Xh := u ∈ C(„¦) u|K ∈ P1 (K) for all K ∈ Th .

¯

Lemma 2.10 For given values at the nodes a1 , . . . , aM , the interpolation

problem in Xh is uniquely solvable. That is, if the values u1 , . . . , uM are

given, then there exists a uniquely determined element

u ∈ Xh such that u(ai ) = ui , i = 1, . . . , M .

If uj = 0 for j = M1 + 1, . . . , M , then it is even true that

u ∈ Vh .

Proof: (1) For any arbitrary K ∈ Th we consider the local interpolation

problem:

Find p = pK ∈ P1 such that p(ai ) = ui , i = 1, 2, 3 , (2.28)

where ai , i = 1, 2, 3, denote the vertices of K, and the values ui , i = 1, 2, 3,

are given. First we show that problem (2.28) is uniquely solvable for a

particular triangle.

ˆ

A solution of (2.28) for the so-called reference element K (cf. Figure 2.5)

with the vertices a1 = (0, 0), a2 = (1, 0), a3 = (0, 1) is given by

ˆ ˆ ˆ

p(x, y) = u1 N1 (x, y) + u2 N2 (x, y) + u3 N3 (x, y)

2.2. Linear Elements 59

y

1

^

K

0 1 x

ˆ

Figure 2.5. Reference element K.

with the shape functions

1’x’y,

N1 (x, y) =

N2 (x, y) = x, (2.29)

N3 (x, y) = y.

Evidently, Ni ∈ P1 , and furthermore,

1 for i = j ,

Ni (ˆj ) = δij =

a for i, j = 1, 2, 3 ,

0 for i = j ,

and thus

3

p (ˆj ) =

a ui Ni (ˆj ) = uj

a for all j = 1, 2, 3 .

i=1

The uniqueness of the solution can be seen in the following way: If p1 , p2

satisfy the interpolation problem (2.28) for the reference element, then for

p := p1 ’ p2 ∈ P1 we have

p (ˆi ) = 0 ,

a i = 1, 2, 3 .

Here p is given in the form p(x, y) = ± + βx + γy. If we ¬x the second

variable y = 0, we obtain a polynomial function of one variable

p(x, 0) = ± + βx =: q(x) ∈ P1 (R) .

The polynomial q satis¬es q(0) = 0 = q(1), and q ≡ 0 follows by the

uniqueness of the polynomial interpolation in one variable; i.e., ± = β = 0.

Analogously, we consider

q(y) := p(0, y) = ± + γy = γy ,

and we obtain from q(1) = 0 that γ = 0 and consequently p ≡ 0.

In fact, this additional proof of uniqueness is not necessary, because the

uniqueness already follows from the solvability of the interpolation problem

because of dim P1 = 3 (compare with Section 3.3).

Now we turn to the case of a general triangle K. A general triangle K is

ˆ

mapped onto K by an a¬ne transformation (cf. Figure 2.6)

F :K ’K,

ˆ F (ˆ) = B x + d ,

x ˆ (2.30)

where B ∈ R2,2 , d ∈ R2 are such that F (ˆi ) = ai .

a

60 2. Finite Element Method for Poisson Equation

B = (b1 , b2 ) and d are determined by the vertices ai of K as follows:

a1 = F (ˆ1 ) = F (0) = d ,

a

a2 = F (ˆ2 ) = b1 + d = b1 + a1 ,

a

a3 = F (ˆ3 ) = b2 + d = b2 + a1 ;

a

i.e., b1 = a2 ’ a1 and b2 = a3 ’ a1 . The matrix B is regular because a2 ’ a1

and a3 ’ a1 are linearly independent, ensuring F (ˆi ) = ai .

a

Since

3 3

K = conv {a1 , a2 , a3 } := »i ai 0 ¤ »i ¤ 1 , »i = 1

i=1 i=1

and especially K = conv {ˆ1 , a2 , a3 }, F [K] = K follows from the fact that

ˆ ˆ

aˆˆ

the a¬ne-linear mapping F satis¬es

3 3 3

F »i ai

ˆ = »i F (ˆi ) =

a »i ai

i=1 i=1 i=1

3

for 0 ¤ »i ¤ 1, i=1 »i = 1.

ˆ

In particular, the edges (where one »i is equal to 0) of K are mapped

onto the edges of K.

a3

y

^

y

1 K

a2

a1

^

K

x

0 1 ^

x

Figure 2.6. A¬ne-linear transformation.

Analogously, the considerations can be applied to the space Rd word for

word by replacing the set of indices {1, 2, 3} by {1, . . . , d + 1}. This will be

done in Section 3.3.

The polynomial space P1 does not change under the a¬ne transforma-

tion F .

(2) We now prove that the local functions u|K can be composed

continuously:

For every K ∈ Th , let pK ∈ P1 be the unique solution of (2.28), where

the values u1 , u2 , u3 are the values ui1 , ui2 , ui3 (i1 , i2 , i3 ∈ {1, . . . , M }) that

have to be interpolated at these nodes.

Let K, K ∈ Th be two di¬erent elements that have a common edge E.

Then pK = pK on E is to be shown. This is valid because E can be

mapped onto [0, 1] — {0} by an a¬ne transformation (cf. Figure 2.7). Then

2.2. Linear Elements 61

q1 (x) = pK (x, 0) and q2 (x) := pK (x, 0) are elements of P1 (R), and they

solve the same interpolation problem at the points x = 0 and x = 1; thus

q1 ≡ q2 .

0 1

E

Figure 2.7. A¬ne-linear transformation of E on the reference element [0, 1].

Therefore, the de¬nition of u by means of

for x ∈ K ∈ Th

u(x) = pK (x) (2.31)

is unique, and this function satis¬es u ∈ C(„¦) and u ∈ Xh .

¯

(3) Finally, we will show that u = 0 on ‚„¦ for u de¬ned by (2.31) if

ui = 0 (i = M1 + 1, . . . , M ) for the boundary nodes.

The boundary ‚„¦ consists of edges of elements K ∈ Th . Let E be such

an edge; i.e., E has the vertices ai1 , ai2 with ij ∈ {M1 + 1, . . . , M }. The

given boundary values yield u(aij ) = 0 for j = 1, 2. By means of an a¬ne

transformation analogously to the above one we obtain that u|E is a poly-

nomial of ¬rst degree in one variable and that u|E vanishes at two points.

2

So u|E = 0, and the assertion follows.

The following statement is an important consequence of the unique solv-

ability of the interpolation problem in Xh irrespective of its particular

de¬nition: The interpolation conditions

•i (aj ) = δij , j = 1, . . . , M , (2.32)

uniquely determine functions •i ∈ Xh for i = 1, . . . , M. For any u ∈ Xh ,

we have

M

for x ∈ „¦ ,

u(x) = u(ai )•i (x) (2.33)

i=1

because both the left-hand side and the right-hand side functions belong

to Xh and are equal to u(ai ) at x = ai .

M

The representation u = i=1 ±i •i is unique, too, for otherwise, a func-

tion w ∈ Xh , w = 0, such that w(ai ) = 0 for all i = 1, . . . , M would

exist. Thus {•1 , . . . , •M } is a basis of Xh , especially dim Xh = M . This

basis is called a nodal basis because of (2.33). For the particular case of a

piecewise linear ansatz space on triangles, the basis functions are called

62 2. Finite Element Method for Poisson Equation

pyramidal functions because of their shape. If the set of indices is re-

stricted to {1, . . . , M1 }; i.e., we omit the basis functions corresponding to

the boundary nodes, then a basis of Vh will be obtained and dim Vh = M1 .

Summary: The function values u(ai ) at the nodes a1 , . . . , aM are the de-

grees of freedom of u ∈ Xh , and the values at the interior points a1 , . . . , aM1

are the degrees of freedom of u ∈ Vh .

The following consideration is valid for an arbitrary ansatz space Vh with

a basis {•1 , . . . , •M }. The Galerkin method (2.23) reads as follows: Find

M

uh = i=1 ξi •i ∈ Vh such that a(uh , v) = b(v) for all v ∈ Vh . Since

M

v = i=1 ·i •i for ·i ∈ R, this is equivalent to

b(•i ) for all i = 1, . . . , M ⇐’

a(uh , •i ) =

«

M

a ξj •j , •i b(•i ) for all i = 1, . . . , M ⇐’

=

j=1

M

b(•i ) for all i = 1, . . . , M ⇐’

a (•j , •i ) ξj =

j=1

Ah ξ = qh (2.34)

T

with Ah = (a(•j , •i ))ij ∈ RM,M , ξ = (ξ1 , . . . , ξM ) and q h = (b(•i ))i .

Therefore, the Galerkin method is equivalent to the system of equations

(2.34).

The considerations for deriving (2.34) show that, in the case of equiva-

lence of the Galerkin method with the Ritz method, the system of equations

(2.34) is equivalent to the minimization problem

Fh (ξ) = min Fh (·) · ∈ RM , (2.35)

where

1T

· Ah · ’ q T · .

Fh (·) = h

2

Because of the symmetry and positive de¬niteness, the equivalence of (2.34)

and (2.35) can be easily proven, and it forms the basis for the CG methods

that will be discussed in Section 5.2.

Usually, Ah is called sti¬ness matrix, and q h is called the load vector.

These names originated from mechanics. For our model problem, we have

∇•j · ∇•i dx ,

(Ah )ij = a(•j , •i ) =

„¦

(qh )i = b(•i ) = f •i dx .

„¦

By applying the ¬nite element method, we thus have to perform the

following steps:

(1) Determination of Ah , q h . This step is called assembling.

2.2. Linear Elements 63

(2) Solution of Ah ξ = q h .

If the basis functions •i have the property •i (aj ) = δij , then the solution

of system (2.34) satis¬es the relation ξi = uh (ai ), i.e., we obtain the vector

of the nodal values of the ¬nite element approximation.

Using only the properties of the bilinear form a, we obtain the following

properties of Ah :

• Ah is symmetric for an arbitrary basis {•i } because a is symmetric.

• Ah is positive de¬nite for an arbitrary basis {•i } because for u =

M

i=1 ξi •i ,

M M M

ξT Ah ξ = i,j=1 ξj a(•j , •i )ξi = j=1 ξj a •j , i=1 ξi •i

M M

=a j=1 ξj •j , i=1 ξi •i = a(u, u) > 0

(2.36)

for ξ = 0 and therefore u ≡ 0.

Here we have used only the positive de¬niteness of a.

Thus we have proven the following lemma.

Lemma 2.11 The Galerkin method (2.23) has a unique solution if a is a

symmetric, positive de¬nite bilinear form and if b is a linear form.

In fact, as we will see in Theorem 3.1, the symmetry of a is not necessary.

• For a special basis (i.e., for a speci¬c ¬nite element method), Ah is a

sparse matrix, i.e., only a few entries (Ah )ij do not vanish. Evidently,

” ∇•j · ∇•i dx = 0 .

(Ah )ij = 0

„¦

This can happen only if supp •i © supp •j = …, as this property is

again necessary for supp ∇•i © supp ∇•j = … because of

(supp ∇•i © supp ∇•j ) ‚ (supp •i © supp •j ) .

The basis function •i vanishes on an element that does not contain

the node ai because of the uniqueness of the solution of the local

interpolation problem. Therefore,

supp •i = K,

K∈Th

ai ∈K

cf. Figure (2.8), and thus

’ ai , aj ∈ K for some K ∈ Th ;

(Ah )ij = 0 (2.37)

i.e., ai , aj are neighbouring nodes.

64 2. Finite Element Method for Poisson Equation

If we use the piecewise linear ansatz space on triangles and if ai is an interior

node in which L elements meet, then there exist at most L nondiagonal

entries in the ith row of Ah . This number is determined only by the type

of the triangulation, and it is independent of the ¬neness h, i.e., of the

number of unknowns of the system of equations.

supp • i

ai

Figure 2.8. Support of the nodal basis function.

Example 2.12 We consider again the boundary value problem (2.1), (2.2)

on „¦ = (0, a) — (0, b) again, i.e.

’∆u =f in „¦ ,

u =0 on ‚„¦ ,

under the condition (1.4). The triangulation on which the method is based

is created by a partition of „¦ into squares with edges of length h and by

a subsequent uniform division of each square into two triangles according

to a ¬xed rule (Friedrichs“Keller triangulation). In order to do this, two

possibilities (a) and (b) (see Figures 2.9 and 2.10) exist.

(a) (b)

d d

d

d d d

d

d d