INTRODUCTION TO FINITE ELEMENT METHODS

1 INTRODUCTION TO FINITE ELEMENT METHODSLONG CHENF inite ELEMENT METHODS are based on the variational formulation of partial differentialequations which only need to compute the gradient of a function. Although unknowns arestill associated to nodes, the function composed by piece-wise polynomials on each ele-ment and thus the gradient can be computed ELEMENT -wise. FINITE ELEMENT spaces can thusbe constructed on general triangulations and this method is able to handle complex geome-tries and boundaries. Boundary condition is naturally build into the weak formulation orthe function space. The variational approach also give solid mathematical foundation andmake the error analysis more systematic. Generally speaking, FINITE ELEMENT METHODS isthe method of choice in all types of analysis for elliptic equations in complex GALERKINMETHODSThe FINITE ELEMENT METHODS have been introduced as METHODS for approximate solutionof variational problems.

2 Let us consider the model problem: Poisson equation with ho-mogenous Dirichlet boundary conditions(1) u=fin , u= 0on .Multiply a test functionv, integrate over , and use integration by parts to obtain thecorresponding variational formulation: Findu V=H10( ) :={v L2( )| v L2( ),v| = 0}, such that(2)a(u,v) = (f,v),for allv (3)a(u,v) = u vdx,(f,v) = fvdx,forf L2( )Clearly, in such casea( , )is bilinear and symmetric, anda(u,u) =|u|21, := u (u,u) = 0implies u= 0and consequentlyuis constant. Asu| = 0,this constant should be zero. Thereforea( , )defines an inner product onV, and thus theproblem (2) has a unique solution by the Riesz representation now consider a class of METHODS , known asGalerkin methodswhich are used toapproximate the solution to (2). Consider a FINITE dimensional subspaceVh V, andletVh= span{ 1.}

3 , N}. For any functionv Vh, there is a unique representation:v= Ni=1vi i. We thus can define an isomorphismVh =RNby(4)v=N i=1vi i v= (v1, ,vN) ,and callvthe coordinate vector ofvrelative to the basis{ i}Ni=1. Following the terminol-ogy in elasticity, we introduce thestiffness matrixA= (aij)N N,withaij=a( j, i),Date: Created on Oct 2007. Latest update November 26, CHENand theload vectorf={ f, k }Nk=1 RN. Then the coefficient vector can be obtainedby solving the following linear algebraic systemAu= definition, for two functionsu,v Vh, theira( , )-inner product is realized by thematrix product(5)a(u,v) =a( iui i, vj j)= i,ja( i, j)uivj=v for any vectoru RN,u Au=a(u,u) 0and equals0if and only ifuiszero. NamelyAis an SPD matrix and thus the solutionu=A 1fexists and FINITE ELEMENT METHODS is a special and most popular example of Galerkin methodsby constructing a FINITE dimensional subspaceVhbased on triangulations of the name comes from the fact that the domain is decomposed into FINITE number of TRIANGULATIONS ANDBARYCENTRICCOORDINATESIn this section, we discuss triangulations used in FINITE ELEMENT METHODS .

4 We wouldlike to distinguish two structures related to a triangulation: one is the topology of a meshdetermined by the combinatorial connectivity of vertices; another is the geometric shapewhich depends on both the connectivity and the location of vertices. Correspondingly thereare two basic data structures used to represent a simplex and (x1,i, ,xn,i) ,i= 1, ,n+1ben+ 1points inRn. We sayx1, ,xn+1do not all lie in one hyper-plane if then-vectorsx1x2, ,x1xn+1are independent. This is equivalent to the matrix:A= x1,1x1, x1,n+1x2,1x2, x2,n+ ,1xn, xn,n+ is non-singular. Given any pointx= (x1, ,xn) Rn, by solving the following linearsystem(6)A n n+1 = ,we obtain uniquen+ 1real numbers i(x),1 i n+ 1, such that for anyx Rn(7)x=n+1 i=1 i(x)xi,withn+1 i=1 i(x) = hullof thed+ 1pointsx1, ,xd+1inRn(8) :={x=d+1 i=1 ixi|0 i 1,i= 1 :d+ 1,d+1 i=1 i= 1} INTRODUCTION TO FINITE ELEMENT METHODS3is defined as ageometricd-simplexgenerated (or spanned) by the verticesx1, ,xd+ example, a triangle is a2-simplex and a tetrahedron is a3-simplex.

5 For an integer0 m d 1, anm-dimensional face of is anym-simplex generated bym+ 1verticesof . Zero dimensional faces are vertices and one-dimensional faces are called edges of .The(d 1)-face opposite to the vertexxiwill be denoted numbers 1(x), , d+1(x)are calledbarycentric coordinatesofxwith respectto thed+ 1pointsx1, ,xd+1. There is a simple geometric meaning of the barycentriccoordinates. Given ax , let i(x)be the simplex with verticesxireplaced byx. Then,by the Cramer s rule for solving (6),(9) i(x) =| i(x)|| |,where| |is the Lebesgue measure inRd, namely area in two dimensions and volume inthree dimensions. Note that i(x)is an affine function ofxand vanished on the (a) 1d simplexx (b) 2d simplexxxi(c) 3d simplexFIGURE1. Geometric explanation of barycentric is convenient to have a standard simplexsn Rnspanned by the vertices0,e1, ,enwhereei= (0, ,1, ,0).

6 Then anyn-simplex Rncan be thought as an image ofsnthrough an affine mapB:sn withB(ei) =xi. See Figure 2. The simplexsnisalso often calledreference 1(a) A standard simplex inR1110s2!B1(b) A standard simplex inR2111 s3yzx(c) A standard simplex inR3 FIGURE2. Reference simplexes inR1, CHENLet be a polyhedral domain inRd,d 1. A geometric triangulation (also calledmesh or grid)Tof is a set ofd-simplices such that T = ,and i j= ,i6= this course, we restrict ourself to simplicial triangulations. There are othertype of meshes by partition the domain into quadrilateral (in 2-D), cubes, prisms (in 3-D),or polytopes in are two conditions that we shall impose on triangulations that are important in thefinite ELEMENT computation. The first requirement is a topological property. A triangulationTis calledconformingorcompatibleif the intersection of any two simplexes and inTis either empty or a common lower dimensional simplex (nodes in two dimensions, nodesand edges in three dimensions).

7 (a)Bisectatriangle(b) (a) A triangulation with a hanging node(a)Bisectatriangle(b) (b) A conforming triangulationFIGURE3. Two triangulations. The left is non-conforming and the rightis second important condition depends on the geometric structure. A set of triangula-tionsTis calledshape regularif there exists a constantc0such that(10)max Tdiam( )d| | c0,for allT T,wherediam( )is the diameter of and| |is the measure of inRd. In two dimensions,it is equivalent to the minimal angle of each triangulation is bounded below uniformly inthe shape regular class. We shall defineh =| |1/nfor any T T. By (10),h hdiam( )represents the size of an ELEMENT Tfor a shape regular triangulationT addition to (10), if(11)max T| |min T| | ,for allT T,Tis calledquasi-uniform. For quasi-uniform grids, define the mesh size ofTashT:=max Th.

8 It is used to measure the approximation rate. In FEM literature, we oftenwrite a triangulation simplex and simplicial distinguish the topological structurewith the geometric one, we now understand the points as abstract entities and introduceabstract simplexorcombinatorial simplex. The set ={v1, ,vd+1}ofd+ 1abstractpoints is called an abstractd-simplex. A face of a simplex is a simplex determined bya non-empty subset of . Ak-face hask+ 1points. A proper face is any face differentfrom . INTRODUCTION TO FINITE ELEMENT METHODS5 LetN={v1,v2, ,vN}be a set ofNabstract points. Anabstract simplicial complexTis a set of simplices formed by FINITE subsets ofNsuch that if Tis a simplex, thenany face of is also a simplex inT. By the definition, a two dimensional combinatorialcomplexTcontains not only triangles but also edges and vertices of these triangles.

9 Ageometric triangulation defined before is only a set ofd-simplex not its faces. By includingall its face, we shall get a simplicial subsetM Tis a subcomplex ofTifMis a simplicial complex itself. Importantclasses of subcomplex includes thestarorringof a simplex. That is for a simplex Tstar( ) ={ T, }.If two, or more, simplices ofTshare a common face, they are calledadjacentorneigh-bors. The boundary ofTis formed by any proper face that belongs to only one simplex,and its associating the set of abstract points with geometric points inRn,n d, we ob-tain a geometric shape consisting of piecewise flat simplices. This is called a geometricrealization of an abstract simplicial complex or, using the terminology of geometry, theembedding ofTintoRn. The embedding is uniquely determined by the identification ofabstract and geometric would like to emphasize that they are two different structures of a triangulationT:one is the topology of a mesh which is determined by the combinatorial connectivity ofvertices; another is the geometric shape which depends on the location of the vertices.

10 Forexample, a planar triangulation is a two dimensional abstract simplicial complex which canbe embedded intoR2and thus called2-D triangulation. A 2-D simplicial complex couldalso be embedding intoR3and result a triangulation of a surface. For these two differentembedding, they have the same combinatory structure as an abstract simplicial complexbut different geometric structure by representing a flat domain inR2or a surface LINEARFINITEELEMENTSPACESIn this section we introduce the simplest linear FINITE ELEMENT space ofH1( )and usescaling argument to estimate the interpolation FINITE ELEMENT space and the nodal a shape regulartriangulationThof , we setVh:={v|v C( ),andv| P1, Th},whereP1( )denotes the space of polynomials of degree1(linear) on Th. See Fig. 4for illustration of linear FINITE ELEMENT functions in 1-D and 2-D.