$$ \newcommand{\uex}{{u_{\small\mbox{e}}}} \newcommand{\uexd}[1]{{u_{\small\mbox{e}, #1}}} \newcommand{\vex}{{v_{\small\mbox{e}}}} \newcommand{\vexd}[1]{{v_{\small\mbox{e}, #1}}} \newcommand{\Aex}{{A_{\small\mbox{e}}}} \newcommand{\half}{\frac{1}{2}} \newcommand{\halfi}{{1/2}} \newcommand{\tp}{\thinspace .} \newcommand{\Ddt}[1]{\frac{D #1}{dt}} \newcommand{\E}[1]{\hbox{E}\lbrack #1 \rbrack} \newcommand{\Var}[1]{\hbox{Var}\lbrack #1 \rbrack} \newcommand{\Std}[1]{\hbox{Std}\lbrack #1 \rbrack} \newcommand{\xpoint}{\boldsymbol{x}} \newcommand{\normalvec}{\boldsymbol{n}} \newcommand{\Oof}[1]{\mathcal{O}(#1)} \newcommand{\x}{\boldsymbol{x}} \newcommand{\X}{\boldsymbol{X}} \renewcommand{\u}{\boldsymbol{u}} \renewcommand{\v}{\boldsymbol{v}} \newcommand{\w}{\boldsymbol{w}} \newcommand{\V}{\boldsymbol{V}} \newcommand{\e}{\boldsymbol{e}} \newcommand{\f}{\boldsymbol{f}} \newcommand{\F}{\boldsymbol{F}} \newcommand{\stress}{\boldsymbol{\sigma}} \newcommand{\strain}{\boldsymbol{\varepsilon}} \newcommand{\stressc}{{\sigma}} \newcommand{\strainc}{{\varepsilon}} \newcommand{\I}{\boldsymbol{I}} \newcommand{\T}{\boldsymbol{T}} \newcommand{\dfc}{\alpha} % diffusion coefficient \newcommand{\ii}{\boldsymbol{i}} \newcommand{\jj}{\boldsymbol{j}} \newcommand{\kk}{\boldsymbol{k}} \newcommand{\ir}{\boldsymbol{i}_r} \newcommand{\ith}{\boldsymbol{i}_{\theta}} \newcommand{\iz}{\boldsymbol{i}_z} \newcommand{\Ix}{\mathcal{I}_x} \newcommand{\Iy}{\mathcal{I}_y} \newcommand{\Iz}{\mathcal{I}_z} \newcommand{\It}{\mathcal{I}_t} \newcommand{\If}{\mathcal{I}_s} % for FEM \newcommand{\Ifd}{{I_d}} % for FEM \newcommand{\Ifb}{{I_b}} % for FEM \newcommand{\setb}[1]{#1^0} % set begin \newcommand{\sete}[1]{#1^{-1}} % set end \newcommand{\setl}[1]{#1^-} \newcommand{\setr}[1]{#1^+} \newcommand{\seti}[1]{#1^i} \newcommand{\sequencei}[1]{\left\{ {#1}_i \right\}_{i\in\If}} \newcommand{\basphi}{\varphi} \newcommand{\baspsi}{\psi} \newcommand{\refphi}{\tilde\basphi} \newcommand{\psib}{\boldsymbol{\psi}} \newcommand{\sinL}[1]{\sin\left((#1+1)\pi\frac{x}{L}\right)} \newcommand{\xno}[1]{x_{#1}} \newcommand{\Xno}[1]{X_{(#1)}} \newcommand{\yno}[1]{y_{#1}} \newcommand{\Yno}[1]{Y_{(#1)}} \newcommand{\xdno}[1]{\boldsymbol{x}_{#1}} \newcommand{\dX}{\, \mathrm{d}X} \newcommand{\dx}{\, \mathrm{d}x} \newcommand{\ds}{\, \mathrm{d}s} \newcommand{\Real}{\mathbb{R}} \newcommand{\Integerp}{\mathbb{N}} \newcommand{\Integer}{\mathbb{Z}} $$ next

Introduction to finite element methods

Introduction to finite element methods

Hans Petter Langtangen [1, 2]

[1] Center for Biomedical Computing, Simula Research Laboratory
[2] Department of Informatics, University of Oslo

Dec 16, 2013

PRELIMINARY VERSION

Table of contents

Approximation of vectors
      Approximation of planar vectors
            The least squares method
            The projection method
      Approximation of general vectors
            The least squares method
            The Galerkin or projection method
Approximation of functions
      The least squares method
      The projection (or Galerkin) method
      Example: linear approximation
      Implementation of the least squares method
      Perfect approximation
      Ill-conditioning
      Fourier series
      Orthogonal basis functions
      Numerical computations
      The interpolation (or collocation) method
            Example
      Lagrange polynomials
            Approximation of a polynomial
            Successful example
            Less successful example
            Remedy for strong oscillations
Finite element basis functions
      Elements and nodes
            Example
      The basis functions
            Construction principles
            Properties of \( \basphi_i \)
      Example on piecewise quadratic finite element functions
      Example on piecewise linear finite element functions
      Example on piecewise cubic finite element basis functions
      Calculating the linear system
            Calculating a specific matrix entry
            Calculating a general row in the matrix
      Assembly of elementwise computations
      Mapping to a reference element
      Example: Integration over a reference element
Implementation
      Integration
      Linear system assembly and solution
      Example on computing symbolic approximations
      Comparison with finite elements and interpolation/collocation
      Example on computing numerical approximations
      The structure of the coefficient matrix
      Applications
      Sparse matrix storage and solution
Comparison of finite element and finite difference approximation
      Finite difference approximation of given functions
      Finite difference interpretation of a finite element approximation
      Making finite elements behave as finite differences
            Computations in physical space
            Elementwise computations
            Terminology
A generalized element concept
      Cells, vertices, and degrees of freedom
      Extended finite element concept
      Implementation
      Computing the error of the approximation
      Example: Cubic Hermite polynomials
Numerical integration
      Newton-Cotes rules
      Gauss-Legendre rules with optimized points
Approximation of functions in 2D
      2D basis functions as tensor products of 1D functions
      Example: Polynomial basis in 2D
      Implementation
      Extension to 3D
Finite elements in 2D and 3D
      Basis functions over triangles in the physical domain
            Element matrices and vectors
      Basis functions over triangles in the reference cell
      Affine mapping of the reference cell
      Isoparametric mapping of the reference cell
      Computing integrals
Exercises
      Exercise 1: Linear algebra refresher I
      Exercise 2: Linear algebra refresher II
      Exercise 3: Approximate a three-dimensional vector in a plane
      Exercise 4: Approximate the exponential function by power functions
      Exercise 5: Approximate the sine function by power functions
      Exercise 6: Approximate a steep function by sines
      Exercise 7: Animate the approximation of a steep function by sines
      Exercise 8: Fourier series as a least squares approximation
      Exercise 9: Approximate a steep function by Lagrange polynomials
      Exercise 10: Define nodes and elements
      Exercise 11: Define vertices, cells, and dof maps
      Exercise 12: Construct matrix sparsity patterns
      Exercise 13: Perform symbolic finite element computations
      Exercise 14: Approximate a steep function by P1 and P2 elements
      Exercise 15: Approximate a steep function by P3 and P4 elements
      Exercise 16: Investigate the approximation error in finite elements
      Exercise 17: Approximate a step function by finite elements
      Exercise 18: 2D approximation with orthogonal functions
      Exercise 19: Use the Trapezoidal rule and P1 elements
      Problem 20: Compare P1 elements and interpolation
      Exercise 21: Implement 3D computations with global basis functions
      Exercise 22: Use Simpson's rule and P2 elements
Basic principles for approximating differential equations
      Differential equation models
      Simple model problems
      Forming the residual
      The least squares method
      The Galerkin method
      The Method of Weighted Residuals
      Test and Trial Functions
      The collocation method
            The subdomain collocation method
      Examples on using the principles
            The model problem
            Basis functions
            The residual
            The least squares method
            The Galerkin method
            The collocation method
            Comparison
      Integration by parts
            Weak form
      Boundary function
      Abstract notation for variational formulations
      Variational problems and optimization of functionals
Examples on variational formulations
      Variable coefficient
      First-order derivative in the equation and boundary condition
      Nonlinear coefficient
      Computing with Dirichlet and Neumann conditions
      When the numerical method is exact
Computing with finite elements
      Finite element mesh and basis functions
      Computation in the global physical domain
      Comparison with a finite difference discretization
      Cellwise computations
            The integral for the element matrix
            The integral for the element vector
            Detailed calculations of the element matrix and vector
            Contributions from the first and last cell
            Assembly
Boundary conditions: specified nonzero value
      General construction of a boundary function
      Example on computing with finite element-based a boundary function
            Computations in physical coordinates
            Cellwise computations on the reference element
      Modification of the linear system
            Computations in the physical system
      Symmetric modification of the linear system
      Modification of the element matrix and vector
Boundary conditions: specified derivative
      The variational formulation
      Boundary term vanishes because of the test functions
      Boundary term vanishes because of linear system modifications
      Direct computation of the global linear system
      Cellwise computations
Implementation
      Global basis functions
      Example: constant right-hand side
      Finite elements
Variational formulations in 2D and 3D
      Transformation to a reference cell in 2D and 3D
      Numerical integration
      Convenient formulas for P1 elements in 2D
Summary
Time-dependent problems
      Discretization in time by a Forward Euler scheme
            Time discretization
            Space discretization
      Variational forms
      Simplified notation for the solution at recent time levels
      Deriving the linear systems
      Computational algorithm
      Comparing P1 elements with the finite difference method
            Lumping the mass matrix
      Discretization in time by a Backward Euler scheme
            Time discretization
            Variational forms
            Linear systems
      Dirichlet boundary conditions
            Boundary function
            Finite element basis functions
            Modification of the linear system
      Example: Oscillating Dirichlet boundary condition
      Analysis of the discrete equations
            Forward Euler discretization
            Backward Euler discretization
            Comparing amplification factors
Systems of differential equations
      Variational forms
      A worked example
      Identical function spaces for the unknowns
            Variational form of each individual PDE
            Compound scalar variational form
            Decoupled linear systems
            Coupled linear systems
      Different function spaces for the unknowns
      Computations in 1D
Exercises
      Exercise 23: Refactor functions into a more general class
      Exercise 24: Compute the deflection of a cable with sine functions
      Exercise 25: Check integration by parts
      Exercise 26: Compute the deflection of a cable with 2 P1 elements
      Exercise 27: Compute the deflection of a cable with 1 P2 element
      Exercise 28: Compute the deflection of a cable with a step load
      Exercise 29: Show equivalence between linear systems
      Exercise 30: Compute with a non-uniform mesh
      Problem 31: Solve a 1D finite element problem by hand
      Exercise 32: Compare finite elements and differences for a radially symmetric Poisson equation
      Exercise 33: Compute with variable coefficients and P1 elements by hand
      Exercise 34: Solve a 2D Poisson equation using polynomials and sines
      Exercise 35: Analyze a Crank-Nicolson scheme for the diffusion equation

The finite element method is a powerful tool for solving differential equations. The method can easily deal with complex geometries and higher-order approximations of the solution. Figure 1 shows a two-dimensional domain with a non-trivial geometry. The idea is to divide the domain into triangles (elements) and seek a polynomial approximations to the unknown functions on each triangle. The method glues these piecewise approximations together to find a global solution. Linear and quadratic polynomials over the triangles are particularly popular.

Figure 1: Domain for flow around a dolphin.

Many successful numerical methods for differential equations, including the finite element method, aim at approximating the unknown function by a sum

$$ \begin{equation} u(x) = \sum_{i=0}^N c_i\baspsi_i(x), \tag{1} \end{equation} $$ where \( \baspsi_i(x) \) are prescribed functions and \( c_0,\ldots,c_N \) are unknown coefficients to be determined. Solution methods for differential equations utilizing (1) must have a principle for constructing \( N+1 \) equations to determine \( c_0,\ldots,c_N \). Then there is a machinery regarding the actual constructions of the equations for \( c_0,\ldots,c_N \), in a particular problem. Finally, there is a solve phase for computing the solution \( c_0,\ldots,c_N \) of the \( N+1 \) equations.

Especially in the finite element method, the machinery for constructing the discrete equations to be implemented on a computer is quite comprehensive, with many mathematical and implementational details entering the scene at the same time. From an ease-of-learning perspective it can therefore be wise to introduce the computational machinery for a trivial equation: \( u=f \). Solving this equation with \( f \) given and \( u \) on the form (1) means that we seek an approximation \( u \) to \( f \). This approximation problem has the advantage of introducing most of the finite element toolbox, but with postponing demanding topics related to differential equations (e.g., integration by parts, boundary conditions, and coordinate mappings). This is the reason why we shall first become familiar with finite element approximation before addressing finite element methods for differential equations.

First, we refresh some linear algebra concepts about approximating vectors in vector spaces. Second, we extend these concepts to approximating functions in function spaces, using the same principles and the same notation. We present examples on approximating functions by global basis functions with support throughout the entire domain. Third, we introduce the finite element type of local basis functions and explain the computational algorithms for working with such functions. Three types of approximation principles are covered: 1) the least squares method, 2) the \( L_2 \) projection or Galerkin method, and 3) interpolation or collocation.

next