3.3 Discretization (2/3)

Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

3.3 DISCRETIZATION 75

(This changes the model a little, of course, and adds some error to the

approximation error inherent in the finite element method.)

We shall use the following simple description of the mesh: (1) four

sets,

denoted N, E, Y, % for nodes, edges, faces, and tetrahedra; (2)

incidence relations,

on which more below;__(3) the

placement

of the mesh"

this isafunction n~x n,from N to D, givingforeachnode n its

position x n in D or on S. In the case of straight tetrahedra, this is

enough to determine the location of all

simplices

(the generic name for

node, edge, face, etc.), and no other placement parameters are needed.

Thanks to this placement, one can confuse under a single expression,

for example, "tetrahedron T", two conceptually different things: here

the element T of ~ which is a mere label, and the tetrahedron T, a part

of D, which is its image under the placement. It's a convenient and not

too dangerous abuse, 13 which I'll commit freely, for all simplices. Symbols

F(e), N(T), and other similar ones, will stand for, respectively, the subset

of all faces that contain edge e, the subset of all nodes that are contained

in tetrahedron T, and other similar subsets for various simplices. The

purpose of the incidence relations, which we shall wait until Chapter 5 to

describe in full detail, is to point to the faces of a given tetrahedron, the

edges of a given face, etc., and thus to give full knowledge of subsets like

Y-(e) or N(T). Finally, we shall denote by

D n

the subdomain of D

obtained by putting together all tetrahedra of the subset T(n), and use

similar notation for D and Dr, calling D s the

cluster

of tetrahedra

around

simplex s (Fig. 3.5). (No attempt is made to distinguish between

open and closed clusters, as that will be clear from context.)

FIGURE 3.5. Clusters of tetrahedra around simplex s (s being, from left to

right, node n, edge e, face f, and tetrahedron T). For better view, faces

containing the simplex are supposed to be opaque, and others transparent.

Let's now recall the notion of barycentric coordinates. Four points

x 1, x 2, x 3, x 4 in three-dimensional space are in

generic position

if the

determinant det(x 2 - x 1, x 3 - xl, x 4 - x~) does not vanish. In that case,

13Mathematicians use s for the simplex as an algebraic object and Is1 for its image.

76 CHAPTER 3 Solving for the Scalar Magnetic Potential

they form a tetrahedron. Four real numbers

~1, ~2, ~3, ~4

such that

Ei ~1 __

1 determine a point x, the

barycenter

of the xis for these

weights,

uniquely defined by

= Ki

(12) x

-- X 0 E i= 1,4 (xi- x0),

where x 0 is any origin (for instance, one of the xis). Conversely, any

point x has a unique representation of the form (12), and the weights ~',

considered as four functions of x, are the

barycentric coordinates

of x in

the

affine basis

provided by the four points. Note that x belongs to the

tetrahedron if Kl(x) > 0 for all i. The Kls are affine functions of x.

Remark 3.3. Consequently, a function p which is polynomial with

respect to the three Cartesian coordinates can be expressed as a polynomial

expression x ~ P(;~l(x),..., K4(x)) of the barycentric coordinates, where

P is another polynomial,

of the same maximum degree

as p, with four

variables. This possibility is often used, usually without warning.

Now, consider our paving of D by tetrahedra. To each node n of

the mesh, let us attribute a function, defined as follows: Its value at point

x is 0 if the cluster D n does not contain x, and if it does, it is the

barycentric coordinate of x with respect to n, in the affine basis provided

by the tetrahedron to which x belongs. (There is no ambiguity in that,

because if x belongs to a simplex s, and thereby, to all tetrahedra of the

cluster of s, its barycentric coordinates with respect to vertices of s are

all the same, whatever the tetrahedron one considers to reckon them.)

We shall reattribute to this

nodal function

the symbol ~n.__ Note that, by

construction, Kn(x) > 0, its support is

Dn,

its domain is D (but doesn't

go beyond), and

(13) ~

n~N ~n(x)--1

for all x ~ D.

The K~s themselves are often called

"barycentric coordinates", though they

coincide with the previous ~'s only

for the nodes around x. This abuse is

harmless, but I'll stick to "nodal

functions", notwithstanding.

A shorter way to describe them is

to say:

is the only

piecewise affine

function 14 that takes the value 1 at

node n and 0 at all other nodes. The inset shows the pattern of level

lines of Kn in the 2D case (triangulation of a plane domain D). It is easy

14 Meaning: affine by restriction to each tetrahedron. I will use

"mesh-wise"

in such

cases: mesh-wise affine, mesh-wise quadratic, etc. (this is not standard terminology).

3.3 DISCRETIZATION 77

from this to imagine the graph of the corresponding function, and to

understand why the )vns are often called "hat functions".

Exercise 3.8. Prove that the hat functions are linearly independent.

Exercise 3.9. Compute the average of

)~n over

(1) an edge e, (2) a face

f, (3) a tetrahedron T, all containing n.

Remark 3.4. Two things are essential in this construction: (1) each )~n is

supported on the cluster of n, (2) they form a

partition of unity

over D,

~n_ 1, relation (13). The affine character is secondary, and is

i.e., ~ ~N

lost in case of curved tetrahedra. 15 But it considerably simplifies the

programming, in conjunction with Remark 3.3, as we'll see. ~)

Well, that's all:

The finite element method is the Ritz-Galerkin method,

the basis functions being a partition of unity associated with a mesh,

as above.

There are many ways to devise such a partition of unity, and the use

of barycentric functions is only the simplest. When one refers to "a"

finite element, it's this whole procedure one has in mind, not only the

analytical expression of the basis functions. However, the latter suffices

in many cases. Here, for instance, the restrictions of the )vns to individual

tetrahedra are affine functions, that is, polynomials of maximum degree

1 of the Cartesian coordinates (one calls them ,,p1 elements" for this

reason), and this is enough characterization. 16

Let us give another example, which demonstrates the power of this

notation. What

are ,,p2

elements"? This means functions with small

support, like the above )vns, which restrict to each tetrahedron as a second-

degree polynomial, and therefore (Remark 3.3) are in the span of the

products )vn)~ m. This is enough to point to the partition of unity, for the

set {)vn)v m" n ~ N, m ~ N } is perfect in this respect: We do have

n m n

~n=l

~n,m~N ~n~m___ ~ ~ N[~n(~ ~ N ~m)] = ~ ~ N

after (13), and the support of )v n)v m is either the cluster of n, if n = m, or

the cluster of edge n to m, if n and m are neighbors (the inset, next

page, shows the level lines of )vn)vm). Note how the coefficients q~n m in

the expansion q0

= ~n, m

q~nm Kn~m are determined by the values of q0 at

15What is affine, then, is the "pull-back" of K n onto the reference tetrahedron. For this

notion, push a little forward (Note 7.9).

16There is in finite element theory a traditional distinction between "basis functions",

like the )n, and "shape functions", which are their restrictions to mesh volumes. As one

sees here, shape functions are more simply characterized. Theory, on the other hand, is

easier in terms of basis functions.

78 CHAPTER 3 Solving for the Scalar Magnetic Potential

the nodes and the mid-edges (Exer. 3.11).

Exercise

3.10. Compute the averages of

;~nKm and ~n ~m ~ on a tetrahedron, in

all cases, n ~ m, n = m, etc.

Exercise

3.11. Devise a set of p2 functions

Wmn such that

Wmn --

1 at the middle of

edge {m, n}, or at node n if n = m, and

0 at all other nodes and mid-edges.

Exercise

3.12 (Gaussian quadrature

formulas). The average of an affine

function over a tetrahedron is the average

of its nodal values. The average of a

quadratic

function is a

weighted

average of its nodal and mid-edge values. Which weights? What about

triangles?

Finite elements with degrees of freedom attached to specific points

(cf. Note 10), like the p1 and p2 elements, are called

Lagrangian

[CR].

There are other varieties, built on hexahedra or other shapes, or with

derivatives as DoFs (those are

Hermitian

elements), and so forth. Refer

to specialized books such as [Ci]. There are also vector-valued finite

elements, to which we shall return in Chapters 5 and 6.

3.3.3 The linear system

Generated by these basis elements, the finite dimensional subspace

contains all functions of the form

(14)

q) = ~n~N~n ~n .

There is one degree of freedom q~n for each node n, equal to the value of

q0 at node n. The family q~ = {q~n : n ~ N} can be construed as a vector

of an N-dimensional space, where N = # N is the number of nodes in

the mesh. We shall denote this vector space by • (it should rather be

~m' but we may drop the m without any risk of confusion while we are

dealing with

one

mesh at a time). Of course ~ and • are isomorphic,

but they are objects of different kinds, and we shall keep the difference in

mind. To stress it, let us call Pm the injective map from • into

defined by (14), which sends q~ to q~m = Pm(~)" Then, ~m = pm(~). Similar

notation will be used throughout, with capitals for spaces, and boldface

connoting degrees of freedom and the vector spaces they span. In

particular, we shall denote with bold parentheses the Euclidean scalar

3.3 DISCRETIZATION

product of two elements of ~, like this:

(15)

(q~, i~') = ~ne N q}n {~'n"

• I • h

To introduce ~ m' first call N (S) the set of all boundary nodes that

h • • • h b

belong to S, including those on the frontier between S and S. Formally,

h h .

N(S )= {n ~ N : Xn ~ cl(S )}, where cl stands for the closure relative to

h h ....

S. Let N(S 0) and N(S 1) similarly be defined. Then, define

(16) ~i= {(p ~ ~. (Pn = 0 if n ~ N(Sh0), (Pn = I if n ~ N(sh)}

and, similarly, ~0, two parallel subspaces of ~. Finally, let us set

(17) ~0

1110 (i)I

m = Pro( )' m = Pm((1)I)"

I ~0

Relation (10), ~Im = q0 m + m' has a counterpart here. Let us construct

q~l, a special vector, with all components q)

n =

0 except for n e N(Shl),

where they are set to 1. Then, with

11)I

defined as (pi = I q)l,

(18)

11)I ~-- q}I q- I[I ~0 .

Remark 3.5. If you try to check (7) at this stage, you will see that it fails if

the faces at the boundary do not fit it exactly. Cf. the inset: a piecewise

affine function that vanishes at n and m, but not

at g, cannot be zero at x. Because of this tiny

difference, ~im is not contained in ~i, and applying

the geometrical reasonings suggested by Fig. 3.4

would be a "variational crime", in the sense of Strang

and Fix [SF]. This (jocular) charge should not deter

anyone from using a mesh similar to the one in

inset in case of a curved boundary. This is perfectly right! What is not,

and would constitute the crime, would be to apply the simple convergence

proof that will follow to such a situation, which calls for more cumbersome

treatment. Thanks to our decision to deform D into a polyhedron

before meshing, we do have ~i = ~

n (I)I

and ~0 = ~ n ~0, as

m m m m

announced in (7). But this will not be effectively used before we address

convergence and error analysis, and what immediately follows does not

depend on the truth of these assertions. ~)

We want now to interpret problem (9), that is,

(9')

) m

in algebraic terms. Since ~I m = P m(~)' this is a linear system with respect

find g3 m

~ lff£ )I

such

that

ID ~ grad q0 m . grad q0' = 0 V q0'~ ~0

m m I

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 3.3 Discretization (2/3)

Create new playlist

Sign In

Sign Up

Table of Contents for
3.3 Discretization (2/3)