Advanced Numerical Analysis: Finite Element Methods

G22.2945, G63.2040
Spring 2006, Mondays 9:20 - 11:10 am

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. Second Edition.

  • Other Good Books
    The Mathematical Theory of Finite Elements by Susanne Brenner and Ridgway Scott. Second 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.

  • Lectures
    1. January 23. Variational formulation of Poisson's equation. Dirichlet and Neumann boundary conditions. V-ellipticity. Bilinear form and linear functionals representing the data. Triangulation of the region. Piece-wise polynomial, continuous finite element spaces. Conforming finite elements in H^1; continuity between elements required. Examples of finite elements with increasing degrees of the polynomials. The interpolation problem and its role in the construction of basis elements for the finite element spaces. Cea's lemma.
    2. January 30. The biharmonic problem with Dirichlet boundary conditions. The equations of linear elasticity. C^1 elements, which are conforming in H^2. Barycentric coordinates; reference elements and affine mappings to the elements of the triangulation. Sparsity of the stiffness matrix. An example of an elliptic problem with a harmonic solution and smooth boundary values which has a singularity at a point on the boundary. An example of function in H^1 which is unbounded.
    3. February 6. Lipschitz regions. Poincare and Friedrichs inequalities derived by elementary means and by using Rellish's theorem. Interpretation in terms of the first and second eigenvalues of certain elliptic problems with different boundary conditions. The use of Poincare's inequality to bound the interpolation error on individual elements and the use of these results to obtain bounds on the error of the finite element solution. A trace theorem for H^1. Sobolev spaces including those with fractional order. Sobolev's inequality, in particular the order required to guarantee continuity everywhere.
    4. February 13. Aubin-Nitsche's bounds for the L_2-error of the finite element solution; the role of regularity of the solution and convexity of Lipschitz regions. An example of a nonconforming but useful element due to Crouzeix and Raviart. Motivation. Variational crimes, regions which are not unions of regular elements, numerical quadrature and nonconforming elements. Strang's first and second lemmas.
    5. February 20. NYU holiday.
    6. February 27. Strang's second lemma. Error bound for non-conforming piece-wise linear finite elements. Comments on Morley elements. How to turn data on the coordinates of the elements into stiffness matrices; the process of assembling element stiffness matrices. Data structures for the stiffness matrices. Band matrices and a different format for storing sparse matrices. Best possible bounds on the work and storage required to solve the linear systems arising in finite element approximations.
    7. March 6. A mesh model for understanding fill-in when using Cholesky's method. Nested dissection ordering. Isoparametric elements based on triangles and quadrilaterals with one curved side. Incompressible stationary Stokes equations and a mixed formulation of flow in porous media. Approximation of saddle point problems with pairs of finite element spaces. Error bounds for the first unknown using a Strang lemma. (Note that a good introduction to mixed finite element is Chapter 12 of the second edition of the Brenner Scott text book listed above on this home page.)
    8. March 13. Spring recess.
    9. March 20. Solving div(u) = g in two dimensions and on a region with reasonable boundary. The inf-sup condition and its relation to the previous result. Description of Taylor-Hood elements. Almost incompressible elasticity and mixed finite elements. Matrix analysis of the resulting saddle-point problem providing bounds on the solution components in terms of the inf-sup constant and the Lame parameters of linear elasticity. The inf-sup constant as the smallest eigenvalue of a generalized eigenvalue problem with a Schur complement and a mass matrix.
    10. March 27. A possibly new error bound for mixed finite element methods relying of the stability result established lst week. Mixed finite element formulation of almost incompressible elasticity. Verifying inf-sup stability using an approach due to Rolf Stenberg.
    11. April 3. Introduction to iterative methods for system of algebraic equations arising from finite element problems. Overlapping Schwarz methods. Block Jacobi methods. An outline of the abstract Schwarz theory. Handout: Chapter 1 of the Toselli and Widlund monograph.
    12. April 10. More on the abstract Schwarz theory. Two level overlapping Schwarz methods. Theory in the abstract frame work.
    13. April 17. Iterative substructuring methods for two subdomains, in particular the Dirichlet-Neumann algorithms. A few words about alternative algorithms; cf.\ chapter 1 of the Toselli and Widlund monograph. An algorithm due to Bramble, Pasciak, and Schatz for many subdomains and two dimensions. An outline of how we can estimate the C_0 parameter which gives a lower bound on the eigenvalues of the preconditioned operator.
    14. April 24. Recent research on iterative substructuring methods, in particular, dual-primal FETI methods and BDDC algorithms. The spectra of dual-primal FETI and BDDC methods are almost the same for the same set of primal constraints.
    15. May 1. No class. I will be celebrating my sister's birthday in Stockholm.
    16. May 8. Make-up class to replace the lecture of May 1. Review of multi-grid algorithms in the perspective of the abstract Schwarz theory. Basic ideas; smoothing with damped Jacobi and Gauss-Seidel. Recursive definition of multigrid methods. Yserentant's hierarchical basis method and an outline of its theory. Why it fails in three dimensions. Outline of the theory for V-cycle multi-grid.