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.
    1. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. October 13. NYU holiday.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. 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.
    13. 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.
    14. 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.
    15. December 8. Solving saddle point problems by preconditioned minimal residuals. An introduction to two modern domain decomposition methods: BDDC and FETI-DP.