## Advanced Topics in Numerical Analysis: Finite Element Methods

##

###
MATH-GA.2011.004, CSCI-GA.2945.004

Fall 2016, Tuesdays 9:00 - 10:50am, WWH 512

Instructor: Olof
B. Widlund

** Coordinates **

Office: WWH 612

Telephone: 998-3110

Office Hours: Tuesdays 11:00am - 12:00 noon, or
drop by any time, or send email, or call for an appointment.

Email: widlund at cims.nyu.edu

** Main Text **

Finite Elements. Theory, Fast Solvers, and Applications in Solid Mechanics
by Dietrich Braess. Cambridge University Press. Third Edition. Via the
Bobcat facility, you can find two sources of this text. I have been told
that the entire book can be downloadable from one of them.

** Other Good Books **

The Mathematical Theory of Finite Elements by Susanne Brenner and Ridgway
Scott. Third Edition. Springer.

Numerical Analysis of the Finite Element Method by Philippe Ciarlet.
SIAM.

Numerical Solution of Partial Differential Equations by the Finite
Element Method by Claes Johnson. Cambridge University Press.

Domain Decompositon Methods -- Algorithms and Theory by Andrea Toselli
and Olof B. Widlund. Springer 2005.

** Final Class and Final Exam **

The last class will be on December 6. Note that December 13, classes will
meet on a Monday schedule.

This is a seminar course. Any student, who so desires, can sign up for
an individual oral exam at the end of the term.
Please send e-mail requesting a date and time.

** Lectures **
These are short descriptions of the content of each lecture, after the
fact.
September 6: Green's formula and how to convert second order elliptic
problems into variational form; the natural space of functions will then
be H^1(\Omega), with a norm that involves only the L_2-norms of the function
and its first derivatives. Dirichlet, Neumann and mixed boundary conditions.
Variational formulation of the biharmonic equation with Dirichlet boundary
conditions, i.e., the function and its normal derivative are prescribed
on the boundary and the space is H^2, a subspace of H^1, with all second
derivatives in L_2. Conforming finite element spaces defined on a triangulation
of the domain \Omega of the elliptic problem; such spaces are subspaces of
H^1 or H^2 depending of the order of the elliptic problem. The finite element
functions are piecewise polynomials and to be conforming need to be continuous
or even C^1. Examples of conforming finite elements for second order elliptic
problems: Lagrange elements and Hermitian cubics and for the biharmonic
two complicated elements that are locally of order 5 and one which is of
order 3 but defined on the union of three subtriangles; cf. page 66 of Braess'
book. Cea's lemma which reduces the error bound for a conforming finite
element problem to one on the interpolation error; this is desirable since
the interpolation error reduces to an argument over single elements. A few
words on how to construct basis functions for the finite element spaces.
September 13: Additional comments on how to decide that the interpolation
problem associated with a finite element methods has a unique solution. Finite
element spaces for rectangular (and hexagonal) elements. The support of basis
functions, i.e, the sets where they have nonzero values, and how to determine
if a particular element of the stiffness matrix can be non-zero. Poincare's
inequality and its relation to the eigenvalue problem for the Laplacian with
Neumann boundary condtions. How this inequality helps us establish that the
Neumann problem for Poisson's equation is elliptic on the subspace of H^1 of
elements with zero average. Sobolev space based on L_2 norms of functions and
some of its derivatives. An example for two dimensions of a function which
belongs to H^1 but which is unbounded. The much simpler way of showing that
minus the Lapacian with Dirichlet boundary values have only positive eigenvalues
which can be estimated by considering a rectangle into which the domain of the
problem has been imbedded. A proof of Poincare's inequality for a square
region; a proof for Lipschitz domains will follow. The definition of Lipschitz
domains and an example of a domain which is not Lipschitz. The formulation of
a trace theorem which shows that the L_2-norm of the restriction of a function
is bounded by the H^1-norm of the function over a Lipschitz domain. A few words
of what will be needed to use Cea's lemma as a stepping stone for a proof
of error bound for conforming finite element solutions.
September 20: Further comment on how to assemble stiffness and mass
matrices; we are talking about adding quadratic forms where each term originates
from an element. What happens to Poicare's inequality if we dilate the domain?
(Dilation represents a very simple rescaling of all variables.) If we start
with a domain with diameter 1 and then shrink it to have a diameter h, a power
of h appears in the right hand side of Poincare's and generalized Poincare
inequalities. Derivation of generalized Poincare inequalities which form the
basis for error bounds for finite element methods. The core technical tool is
Rellish's theorem and we proceed with a proof by contradiction. Aubin-Nitsche's
bound for the L_2-error of the finite element solution of second order elliptic
problem; we pick up an additional power of h provided that a certain regularity
theorem is valid. This holds if the boundary of the domain is convex or if the
boundary of the domain is smooth enough. A motivation for proving a trace
theorem; it is needed in order to establish ellipticity for a second order
elliptic problem with Dirichlet boundary conditions on part of the boundary
and a Neumann condition of the rest. A proof by simple means that the L_2-norm
of the restriction to the boundary of a function in H^1 is bounded.
September 27: Mass and stiffness matrices and their conditioning. Some
final remarks on the error bounds for conforming finite elements; they require
the use of a Sobolev inequality to bound the maximum of funcions. Strang's
two lemmas, which are useful in deriving error bounds resulting from quadrature
errors and non-conforming finite element approximations. An error bound for the
non-conforming P_1 elements; the trace theorem is an important ingredient.
What do when a domain of an elliptic problem cannot be exactly represented by
a union of triangles or tetrahedra? A proof of one such result, using Strang's
second lemma, will follow. A short introduction to isoparametric elements which
allow us to approximate the domain by elements with edges that are not straight.
October 4: Appoximation of Poisson's equation using P_1 finite elements
with elements with one curved side using Strang's lemma #2; cf. pp. 112-114 in
Braess' book. A few more remarks on isoparametric elements. The equations of
incompressible Stokes and linear elasticity. A transformation which turns
the equations of almost incompressible elasticity into a saddle point problem,
which is very similar to incompressible Stokes. Negative norm spaces, which are
dual to the H^m Hilbert spaces; the H^{-1}-norm naturally arises when we write down the most basic bound for Poisson's equation. Developing bounds for the
solution of the linear system of almost incompressible elasticity assuming a
bound which turns out to be equivalent to the LBB inf-sup condition of Babuska, Brezzi, and Ladyzhenskaya; to be continued.
October 11: More on linear elasticity. Ellipticity requires the use of
Korn's inequality. Rigid body modes; a six dimensional space of translations
and rotations which forms the nullspace of the elasticity operator in three
dimensions. The inf-sup condition and what is means in terms of a matrix
inequality. A saddle-point system arising when linear elasticity is approximated
by using a mixed method after introducing an extra variable, the pressure,
p = -\lambda div(u). A discussion of the content of a one-page hand-out which
provides bounds for the norms of the displacement u and the pressure in terms
of the right hand sides, the Lame parameters, and the inf-sup constant. Another
appearance of the inf-sup constant when solving more general variational
problems and their finite element approximations; error bounds can be developed
similar to those of Cea's lemma. This reduces the error bound to a best
approximation problem, which we have previously considered. Two mixed methods
for the solution of Poisson problem. For the first, the inf-sup conditions
is very easy to establish for the continuous problem as well as for a natural
choice of finite element spaces. The second leads to the introduction of
the H(div) space and the Raviart-Thomas elements; to be continued. Note that
most of this material can be found in chapter III of Braess' book.
October 18: Further comments on the second mixed method for Poisson's
equation. In itself, it does not make a lot of sense but if we turn to Darcy's
law, a second order elliptic problem, often with very nasty coefficients, a
good case can be given for using mixed methods; the additional scalar pressure
field is of very direct interest in applications. A proof of Necas' result
for two dimensions and smooth boundaries borrowed from the Brenner-Scott book.
Raviart-Thomas elements, in particular those of the lowest order; they are
H(div)-conforming vector-valued functions with P_1 components and with
continuous normal components across the interface between elements.
Incompressible Stokes problem; we start out with a saddle point problem where
the unknowns are the velocity components in H^1(\Omega) and the pressure in
L_2(\Omega) subject to having a zero average. The problem, which is close to
that of almost incompressible elasticity, can be formulated as a minimization
problem with a constraint that the velocity field is divergence free; the
pressure then technically is a Lagrange multiplier. Definitions of two
families of inf-sup stable finite element pairs: i) continuous (Q_k)^n,
discontinuous P_{k-1} (not Q_{k-1}) and ii) Taylor Hood elements,
continuous (P_k)^n and continuous P_{k-1}. Here n is the dimension of the space,
i.e., n-=2 or 3.
October 25: Finite elements for incompressible Stokes equations,
essentially following Braess' Chapter III, section 7. An example of a pair of
finite element spaces, (Q_1)^2 cross Q_0, which is not inf-sup stable; it can
be fixed but results in an akward linear system of equations. Two families
of Taylor-Hood elements; they have contiuous pressure spaces and are inf-sup
stable. So is (Q_2)^n cross discontinuous P_1 on rectangular elements; n is
the dimension of the space. The mini-elements and a short discussion of Fortin
interpolation; see pp. 136-137 of Braess' book. The divergence-free discontiuous
P_1 space. Solving finite element positive definite, symmetric linear systems
using Cholesky's algorithm. For three dimensional problems, the cost of
factoring is quadratic in the number of variables; we will return to this topic
at a later time. Handout on domain decomposition, the first three chapters of
the Toselli-W 2005 monograph.
November 1: Introduction to domain decomposition algorithms covering part
of the content of Chapter 1 of the handout. The difference between the
continuous problem, which makes sense only if the solutions are known to have
some extra smoothness beyond H^1, and the finite element case, which always
works out. Schur complements and their role in the algorithms and analysis of
the domain decomposition algorithms. The Dirichlet-Neumann algorithm for two
subdomains; the sum of two Schur complements associated with the two subdomains
is effectively the matrix of a linear system for the values on the interface
between the subdomains and one of the subdomain Schur complements serves as
a preconditioner for the conjugate gradient algorithm. A convergence rate
independent of the mesh size can be established. The need for a global componentof the preconditioner in order to make the convergence rate independent on the
number of subdomains. The Dirichlet-Neumann algorithm for many subdomains; it is
assumed that we have a red-black ordering of the subdomains and that the local
subdomain Neumann problems are glued together at the cross points of the
interface providing a global component of the preconditioner. A first
introduction to the Schwarz alternating algorithm. The algorithm is sequential
with two substeps per iteration if there are two overlapping subdomains. The
error propagation can conveniently be written in terms of two operators related
to the Dirichlet problems on the two overlapping subdomains.
November 8: Expressing the error propagation of multiplicative and additive
Schwarz methods in terms of projections for the problem considered by
H.A. Schwarz. Block Jacobi methods and how they can be analyzed; the crucial
part is a bound related to the decomposition of an arbitrary element of the
finite element space into contributions from subspaces. Some remarks on
the results discussed at the end of the first chapter of the hand-out. Abstract
Schwarz theory with a special emphasis on the additive algorithms; three
parameters enter into an upper bound for the condition number. A bound for the
multiplicative variant expressed by the same three parameters.
November 15: Two-level overlapping additive Schwarz methods as in Chapter
3 of the hand-out. The method as presented there works with two independent
meshes, a large global fine triangulation, which is decomposed into many
subdomains and a coarse mesh used for the global coarse problem. An analysis
of this domain decomposition algorithm except for a proof of Lemma 3.10 in the
handout.
November 22: A proof of Lemma 3.10. A discussion of a paper by Xuejun Zhang that appeared in Numer. Math. vol 63, pp. 521--539, 1992. How to derive an
upper bound for the BPX operator which is the additive Schwarz algorithm variant
of the standard V-cycle multigrid.
November 29: The main contribution of Zhang's paper, namely the lower bound
which completes the proof of the optimaility of BPX and V-cycle multigrid with
bounds independent on the number of mesh levels. Introduction of a classical
domain decomposition algorithm due to Bramble, Pasciak, and Schatz, Math. Comp.
vol. 47, pp.103--134, 1986. It is developed for scalar elliptic problems in the
plane and is analyzed in the frame work of Schwarz methods as in Chapter 2 of
the handout. The condition number bound, which cannot be improved, is of the
form C(1+log(H/h))^2 where H/h is the maximum number of elements across any
subdomain. The proof depends crucially on a finite element Sobolev inequality
which bounds, in two dimension, the square of the maximum of a finite element
function in terms of C(1+log(H/h)) times its energy.
December 6: Completion of the analysis of the algorithm due to Bramble et
al. The core is a bound comparing the energy of a function defined on one
edge of a subdomain boundary and extended by zero to the rest of the boundary
and the energy of the function with an extension which provides the smallest
energy. Using Cholesky's algorithm to solve the linear systems arising in
finite element work. How fill-in occurs and the idea of minimal degree
algorithms. How fill-in occurs for a regular problem on a regular grid and
using Q_1 elements: for 2D, the factorization cost grows as N^{3/2}, where
N is the number of degrees of freedom. The number of non-zeros is on the order
of N log(N); this provides an estimate of the work needed to solve the two
triangular system of equations since any nonzero element in the triangular
systems is used exactly once. The bounds for 3D problems are much worse.
Factorization costs grow as C N^2 and the number of non-zeros in the triangular
factors in proportion to N^{4/3}. A short introduction to BDDC, a competitive
algorithm which for 2D can be anlyzed using the same tools at the algorithm
by Bramble et al.