Advanced Numerical Analysis: Finite Element Methods
G22.2945, G63.2040
Fall 2008, Mondays 1:25 - 3:15 pm, WWH 312
Instructor: Olof
B. Widlund
Coordinates
Office: WWH 712
Telephone: 998-3110
Office Hours: Mondays 11:30am - 12:30pm or
drop by any time, or send email or call for an appointment.
Email: widlund@cs.nyu.edu
Required Text
Finite Elements. Theory, Fast Solvers, and Applications in Solid Mechanics
by Dietrich Braess. Cambridge University Press. Third Edition.
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.
University of Montreal Press.
Numerical Solution of Partial Differential Equations by the Finite
Element Method by Claes Johnson. Cambridge University Press.
Final Exam
There will be individual oral exams lasting 30-40 minutes. They can be
taken any time between December 1 and December 18 or between January 8
and January 19. Please send e-mail requesting a date and time.
Homework
Lectures
These are short descriptions of the content of each lecture, after the
fact. Note that Monday October 13 is a university holiday and that
Wednesday November 26 runs on a Monday schedule. December 8 is the
last scheduled lecture of this course.
- September 8. A discussion of text books. Poisson's problem;
a simple scalar elliptic problem in operator form. Green's formula
and how to convert this problem into variational form. Dirichlet,
Neumann, and mixed boundary conditions. A few words on the Sobolev
space H^1. Lipschitz domains. The question of the existence of
a well defined trace, i.e., the restriction of an element of H^1
to the boundary of the domain; to be revisited. Partitioning the
domain into triangles and/or quadrilaterals (in 2D) and tetrahedra,
hexagons, and/ or prisms (in 3D). Piecewise linear continuous finite
element functions. Conforming finite elements; continuity between
elements are required. Basis functions of the P_1, P_2, and P_3
Lagrange finite element spaces. The Hermite cubics finite elements.
Agryris' P_5 element. It has 21 degrees of freedom and quintic
polynomials. The Agryris elements are C^1. Reduction to 18 degrees
of freedom by replacing the edge degrees of freedom with constraints.
- September 15. More discussion of different finite elements.
Barycentric coordinates; they are intimately related to the basis
functions for the P_1 space. An additional C^1 element on triangles;
the Hsieh-Clough-Tocher element. Why C^1 elements? Two variational
formulations, in H^2, that both lead to the biharmonic problem
which is used in 2D fluid dynamics and as a model for plates.
Quadrilateral elements and Q_k spaces. They are continuous if
the quadrilaterals line up with the coordinate axes. The Bogner-
Fox-Schmidt Q_3 element, which is C^1. Cea's lemma and the issues
that arise in its application. The Aubin-Nitsche result; a different
issue on the regularity of solutions arises.
- September 22. Comments on Cea's and Aubin-Nitsche's error bounds;
the latter requires a regularity theorem. All is fine for second order
elliptic problems if the domain is convex or has a sufficiently smooth
boundary. An example of a problem on a non-convex domain and a right
hand side in L^2 which does not have an H^2 solution. An example of
an unbounded function in two variables which is in H^1. A proof of
Poincare-Friedrichs' inequality for H^1_0 for a cube and any domain
which can be imbedded in the cube. How the bound depends on the side
length of the cube; a simple argument on the effect of a dilation.
Poincare's inequality for a cube. Rellish theorem and its application
in the proof of a generalized Poincare inequality which comes in handy
when developing error bounds for finite element solutions; the continuity
of the expression that augments the H^k-seminorm on the right hand side
is crucial. A more general Poincare-Friedrichs inequality which requires
the use of a trace theorem. The definition of W^k_p spaces for positive
non-integer k. Lipschitz domains and the trace theorem in H^1; there
is a short proof of that theorem in Braess' book. Sobolev imbedding in
a special case; under a suitable assumption, finite element interpolation
is well defined.
- September 29. Standard bounds for the finite element interpolation
error using generalized Poincare inequalities and a dilation argument.
These bounds are then combined with those of Cea and Aubin-Nitsche. Why
use discontinuous P_1 elements? The two lemmas by Strang to estimate
the effects of changing the bilinear form and the linear functional in the
right hand side and/or changing to a nonconforming finite element space. An
error bound for the discontinuous P_1 approximation of Poisson's
equation, with a proof which uses the trace theorem and a dilation argument.
- October 6. Using one of Strang's lemmas to analyze the effect of
curved boundaries. Isoparametric elements and the risk of not having one-to-one
mappings. The case of P_2 and triangles with one curved edge. Quadrilaterals:
we can use arbitrary quadrilaterals and Q_k spaces and maintain continuity
between elements if we use isoparametric elements. Mixed formulation for
flow in porous media; motivation, an additional variable, and a saddle point
problem. The equations of linear elasticity: in the almost incompressible
case, the standard finite element methods fail. A remedy is to introduce
a pressure variable and a mixed formulation. The spaces appropriate for
these mixed formulations.
- October 13. NYU holiday.
- October 20. Estimates for the solution of certain two-by-two block
systems of linear equations, which arise in mixed finite element
approximations of almost incompressible elasticity and incompressible
Stokes equations. There was a one page handout. Negative norms in
the matrix and Sobolev space cases. How to use the bounds for these
linear systems of equations to derive error bounds for the mixed
finite element problems. Finding a solution, with an appropriate bound,
for div u = f; there was a handout from Chapter 11 of Brenner-Scott's
book. Conforming finite element spaces for H(div), due to Raviart and
Thomas and which are used in mixed finite element approximations for
flow in porous media.
- October 27. Raviart-Thomas elements, which are conforming in
the H(div)-space. How to find the interpolant into these spaces.
The divergence of the interpolant in an element equals the average
over the element of the divergence of the function to be interpolated.
A suitable second space for the scalar variable in the mixed formulation
of flow in porous media and the inf-sub stability of this pair of
spaces using a technique due to Fortin. An error bound can then be
obtained by using the results of the first handout of 10/20. Remarks
on the Arnold-Brezzi approach; it reduces the saddle point problem
to a positive definite, symmetric problem. Korn's inequality and
ellipticity of the system of linear elasticity. An example of a pair
of spaces which are not inf-sup stable for incompressible Stokes
and almost incompressible elasticity and a catalog of pairs of spaces
which are inf-sup stable. (No details yet provided.) Handout: A paper
by Rolf Stenberg on how to verify inf-sup stability for mixed finite
element approximations of the incompressible Stokes problem.
- November 3. Reducing the mixed methods that use Raviart-Thomas
elements to a positive definite problem for a vector of Lagrange
multipliers; a one-page, two-sided handout. The use of Sylvester's
inertia theorem to prove that certain Schur complements are
negative definite. An unstable pair of
finite element spaces for incompressible Stokes' equations; following
Braess' book. A beginning of a discussion of Stenberg's paper.
- November 10. Inverse inequalities and its relation to the eigenvalues
of a symmetric generalized eigenvalue problem defined by the stiffness
matrix, of the Laplacian, and the mass matrix. Clement interpolation
to replace the standard interpolant into the finite element space;
this procedure is not completely local. (A more modern version of operators
of this kind are given in Scott and Zhang, Math. Comp., 1990,
vol. 54, 483-493. The main parts of the Stenberg paper was discussed
including his example 2. That example is about the lowest order Taylor-
Hood element. The discussion was not complete: A second velocity has to
be considered before we can conclude that the pressure is constant on
the three elements. (My apologies.) Handout: Most of chapter 1 of my
2005 monograph, coauthored with Andrea Toselli.
- November 17. Domain decomposition methods, mostly for problems on two
subdomains. An attempt to look at the continuous problem. Submatrices and
subvectors and sudomain Schur complements. Discrete flux vectors.
The Neumann-Neumann algorithm
and how to express it using Schur complements: the convergence rates of
the Richardson and conjugate gradient iterations are determined by a
generalized eigenvalue problem defined by the two subdomain Schur complements.
The quadratic forms of these Schur complements equal the energy of discrete
harmonic extensions of data given on the interface. A few comments on
alternative algorithms and algorithms for problems on
many subdomains; one version of the Neumann-Dirichlet algorithm is
successful.
- November 24. Schwarz's alternating procedure analyzed by using
projections and subspaces. An abstract Schwarz theory: additive and
multiplicative algorithms. Three core assumptions. Handout: Part of
chapter 2 of the 2005 monograph.
- November 26. A two-level additive overlapping Schwarz method. A
bound for a decomposition of arbitrary elements of the finite element
space. The use of averaging and interpolation to define the coarse
space component. A partitioning of unity and a bound of the L^2-norm
over narrow subsets defined by the intersection of the overlapping
subdomains. Handout: Part of chapter 3 of the monograph.
- December 1. Introduction to multigrid methods and some historical remarks.
Yserentant's work on hierarchical basis methods; it is perfect for one
dimension, pretty good for two, and not competitive for three. An outline
of the analysis using the abstract Schwarz theory. An outline of the
analysis of the V-cycle multigrid method following Zhang's 1992 Numer.
Math. paper. Compared with the hierarchical basis method, the subspaces
are richer which makes the lower bound, expressed in terms of C_0^2,
better, but the upper bound in terms of the strengthened Cauchy-Schwarz
inequalities harder to obtain. The bound for C_0^2 was only discussed
for the case of a convex domain which allows the use of the Aubin-Nitsche
result; Zhang's paper gives the full story without this assumption.
- December 8. Solving saddle point problems by preconditioned minimal
residuals. An introduction to two modern domain decomposition methods:
BDDC and FETI-DP.