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
Homework 1 Assigned January 28, due
on Friday February 12 at 4:00 pm.
Homework 2 Assigned February 11, due on Friday
February 26 at 4:00pm.
Homework 3 Assigned March 11, due on Friday
April 2 at 4:00pm.
Homework 4 Assigned April 8, due on Friday
April 23 at 4:00pm.
Lectures
These are descriptions of the content of each lecture, after the fact.
- 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.
- 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.
- 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.
- 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.
- 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.
- February 25. No lecture. Replaced by a lecture on May 6.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.