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.