Numerical Methods II

G22.2421, G63.2020
Spring 2010, Thursdays 7:00-9:00pm, WWH 312

Instructor: Olof B. Widlund

  • Coordinates
    Office: WWH 712
    Telephone: 998-3110
    Office Hours: Drop by any time, or send email or call for an appointment
    Email: widlund at cims.nyu.edu
    Course URL: http://www.cs.nyu.edu/courses/spring10/G22.2421-001/index.html

  • Announcements
  • There will be individual oral exams at the end of the semester. You can arrange for an exam during the first two weeks of May or during the second week of June.
  • There will be no lecture on February 25. Instead, there will be a lecture on May 6, which is during the exam period.

  • Blackboard
    A Blackboard account has been activated and you can use it to keep track of homework scores. I will also use it to send e-mail occasionally. The assignments will only be available, in pdf format, via this course home page.

  • Requirements
    Regular homework assignments, including programming assignments, using Matlab or any reasonable alternative. It is important that you do the homework yourself, but when you get stuck, I encourage you to consult with other students, or me, to get help when necessary. However, when you get help, it's important to acknowledge it in writing. Passing off other people's work as your own is not acceptable.

  • Main Text Book
    A First Course in the Numerical Analysis of Differential Equations by Arieh Iserles. Cambridge University Press. Second Edition.
  • Two Additional Books of Interest
    Applied Numerical Linear Algebra by James W. Demmel. SIAM.
    Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations by Uri M. Ascher and Linda R. Petzold. SIAM.

  • Homework
  • Lectures These are descriptions of the content of each lecture, after the fact.
    1. January 21. A finite difference approximation of second order for a boundary value problem for simple second order ordinary differential equation. Computing the truncation error by using Taylor series. Increasing the accuracy by using a five-point stencil instead of one based on three points; it is inconvenient since we need to do something special on at two boundary points. A fourth order scheme based on three-point stencils for both the solution and the right hand side called the "Mehrstellenverfahren". The rate of convergence of these schemes by using an expansion in eigenfunctions and also by using a maximum principle. Richardson extrapolation and the basic idea of deferred corrections. The idea of rewriting any boundary value problem for ODEs as a first order system and then using just two point to approximate the derivative and the right hand side. The standard five-point of Poisson's equation on a rectangle and on a general domain. The truncation error can be computed by essentially the same formulas as for the one-dimensional case. Two recipes for the approximation at points that do not have all its next neighbors in the closure of the domain. Two nine-point formulas.
    2. January 28. Further comments on the maximum principle. Gershgorin's theorem. Irreducible matrices. A brief introduction to the matrix structure arising in finite element approximations with piecewise linear continuous functions. The piecewise quadratic case. The connection between the five- point formula and piecewise linear finite element on a very regular triangulation. A simple model problem on a square domain and the fill-in resulting when using Cholesky with a lexigraphic ordering. Band and profile Cholesky. A discussion of nested dissection ordering which gives an optimal algorithm. Handout: a SINUM paper by Alan George from 1973.
    3. February 4. Further comments on nested dissection ordering for two- and three-dimensional problems. Fast Poisson solvers and their relations to separation of variables. Methods based on FFT for rectangular and circular domains. Buneman's algorithms. Jacobi's Gauss-Seidel's and the successive overrelaxation methods for the iterative solution of linear systems of equations. Matrix norms and spectral radii of iteration matrices.
    4. February 11. Matrix splitting and classical iterative methods. Jacobi's, Gauss_Seidel's and the successive overrelaxation methods. If the coefficient matrix is strictly diagonal dominant, then Jacobi's and Gauss-Seidel's methods converges and Gauss-Seidel's is faster. Red-black ordering. The convergence rates for these methods for a simple model problem. A lower bound |\omega - 1| for the successive overrelaxation method. A proof that successive overrelaxation converges for all \omega in (0,2) if the matrix is positive definite. Property A and consistently ordered matrices. Expressing the eigenvalues of the successive overrelaxation method in terms of those of Jacobi's method for consistently ordered problems.
    5. February 18. Theory for the successive overrelaxation method for consistently ordered matrices. Conjugate gradient and preconditioned conjugate gradient algorithms and how to derive the latter from the former. Block Jacobi and line Jacobi preconditioners; the preconditioned system can be represented as a sum of projections. Schwarz's alternating method and the original motivation for it. Introduction to Schwarz methods, in particular, additive Schwarz methods. Proof of the basic bound for the convergence rate of the additive Schwarz methods. Handout on theory of Schwarz methods.
    6. February 25. No lecture. Replaced by a lecture on May 6.
    7. March 4. The original Schwarz alternating method and how to express its iteration error in terms of projections onto subspaces of H^1 associated with the two subdomains. Two level overlapping Schwarz methods with a coarse finite element subspace with elements with diameters comparable to those of the local subproblems.
    8. March 11. Two error bounds for finite element approximations: Cea's and the Aubin-Nitsche lemmas. Completion of the proof of an estimate of the convergence rate of a two-level overlapping Schwarz algorithm.
    9. March 25. The essence of a proof of fast convergence of multigrid methods based on the theory of general Schwarz methods: Two estimates namely of the parameter C_0^2 and the epsilons of the strengthened Cauchy-Schwarz inequalities. A bound for C_0^2 for the case of convex domains which allow the use of the Aubin-Nitsche lemma. Introduction for finite difference approximations of initial values of ordinary differential equations. Euler's method and a proof of convergence; it is first order. An expression of the error with the leading term determined by the solution of a linearized equation. The trapezoidal rule and the two families of Adams-Bashforth and Adams-Moulton methods.
    10. April 1. Characteristic polynomials of linear multistep schemes. The root condition. Constructing multistep schemes if one of those polynomials are given. Backward differentiation schemes. Dahlquist's two barrier theorems. The weak stability of the multistep schemes that are of maximal order. A- and A(alpha)-stability and the use of backward differentiation schemes for stiff problems. An introduction to Runge-Kutta methods.
    11. April 8. Implicit Runge-Kutta methods. Collocation: an equivalent formulation providing additional tools for the analysis of Runge-Kutta methods. Selecting the Gauss-Legendre nodes to achieve maximal accuracy. How to reduce the computation of a Runge-Kutta scheme to an question on a rational function. Pade approximation of the exponential function. The A-stability of the most accurate implicit Runge-Kutta schemes. A few words on error control: Milne's device and imbedded Runge-Kutta methods. A handout related to homework set 4.
    12. April 15. Initial value problems for partial differential equations. The role of the Fourier transform to analyze problems with constant coefficients. Four examples. Rewriting wave equations as first order hyperbolic systems. The energy method to establish that they are well posed even when the coefficients vary smoothly. The Petrowski condition: the real part of the eigenvalues of the symbol are bounded uniformly from above. An example illustrating that a change of variable of a particular system, which satisfies the Petrowski condition can lead to a system with constant coefficients which is provably ill posed. Another example, of a well-posed problem, which violates the Petrowski condition at some points. Parabolic problems and a maximum principle. A first introduction to finite difference approximations. The conditional stability of explicit parabolic difference schemes and a proof, by the energy method, that the trapezoidal rule, a.k.a. the Crank-Nicolson scheme, is stable in L_2. Three handouts.
    13. April 22. Domain of dependence and the CFL condition. Stability under perturbations with zero order terms; a necessity for handling variable coefficient problems. Huygens' principle and how it rules out stability in the maximum norm. Friedrichs' and Lax-Wendroff schemes and the increasing difficulty providing stability bounds when we go to systems, in particular with several space variables. Leapfrog and Milne's schemes; to be continued.
    14. April 29. Proofs of the stability and convergence of the Leapfrog and Milne's schemes. How to establish the necessary bound for a simple parabolic initial-boundary value problem by estimating the maximum of a function by its H^1-norm. Error bounds for parabolic finite element problems based on error bounds for elliptic problems and a priori bounds for the parabolic problem.
    15. May 6. More on error bounds for parabolic finite element problems following a new handout. The key ingredients are error bounds for related elliptic problems and a priori bounds for the continuous problem derived by the energy method. Splitting a la Strang and basic ideas fo alternating direction implicit methods. A variety of finite element methods and how to establish their continuity. Two higher order C^1 elements. Composite elements and a simple C^1 element on rectangular elements. Element stiffness matrices and how to use them to assemble stiffness matrices for the entire elliptic problem.