<< . .

. 9
( : 59)



. . >>


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

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

<< . .

. 9
( : 59)



. . >>