i/TITLE> Numerical Methods II
Numerical Methods II
G22.2421, G63.2020
Spring 2001, Thursdays 5:10-7:00pm, WWH Room 102
Instructor: Olof B. Widlund
Coordinates
Office: WWH 712
Telephone: 998-3110
Office Hours: Drop by any time, or send email or call for appointment
Email: widlund@cs.nyu.edu
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 the math computer
consultant, 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 called plagiarism and is not acceptable.
Homework
Lectures
- January 18. Polynomial interpolation, Newton's interpolation procedure,
numerical quadrature. Euler's method for initial value problems for ODE.
- January 25. Hermite cubic interpolation via Newton's interpolation
procedure, a proof of the error bound of polynomial interpolation.
One step difference approximations for initial value problems for ODE
including those based on Taylor's formula. The basic ideas behind
Runge-Kutta schemes. The Adams families and an introduction to linear
multistep formulas.
- February 1. Linear multistep schemes, Dahlquist's first barrier, weak
instability of stable schemes with maximum accuracy, backward
differentiation schemes, explicit Runge-Kutta schemes, implicit
Runge-Kutta methods.
- February 8. No class. Instructor will be 4000 miles away.
Make-up class to be held on May 3.
- February 15. Adaptive solvers and error control: the Milne device and
embedded Runge Kutta methods. Stiff problems and stability diagrams.
Collocation, Gaussian quadrature, and implicit Runge-Kutta methods.
- February 22. Finite difference approximations of Poisson's equation.
An error bound based on a maximum principle. Eigenvalues and eigenvectors
of the discrete five-point Laplacian on rectangles.
- March 1. Gerschgorin's theorem. Graphs of matrices and irreducible
matrices. Separating variables, in particular, Poisson's equation
on a disc. Buneman's algorithm, FFT, and FFT-based Fast Poisson solvers.
Remarks on one-way-dissection algorithms. (There were a number of
hand-outs.)
- March 8. Introduction to finite element approximation of elliptic
problems: Variational formulation of Poisson's equation, conforming
piecewise linear finite elements, triangulation, nodal basis functions,
Cea's lemma, and error bounds in H^1. The stiffness and mass matrices,
sparsity, subassembly of matrices, and basic properties of finite
element linear algebraic systems. Graphs of finite element matrices.
- March 22. Cancelled because of sudden illness of instructor.
- March 29. Classical theory of iterative methods. Regular splitting,
Jacobi and Gauss-Seidel and successive overrelaxation methods. Divergence
of successive overrelaxation for omega outside (0,2), convergence with
the parameter in that interval for positive definite, symmetric matrices.
Consistently ordered systems and a comparison between the rates of
convergence for Jacobi, Gauss-Seidel, and SORs.
- April 5. Chebyshev iterations. Bounds on the conjugate gradient method in
terms of Chebyshev polynomials. Splittings and preconditioning of conjugate gradients. Best approximation in the maximum norm by polynomials. The
results by De La Vallee-Poussin and Chebyshev; cf. Isaacson and Keller's
textbook, section 5.4.1-2. Extension of the theory to systems other than
the polynomials.
- April 12. Derivation of cubic spline interpolants. Solving nonlinear
equations by Newton's method, the bisection, secant, regula falsi, and
the Illinois methods. Superlinear convergence of Newton's and the secant
methods. Finding the minimum of a function by Newton's method and by
using a parabolic interpolant. Golden section search. A short introduction
to parabolic and hyperbolic initial value problems.
- April 19. The heat equation; exact solution, wellposedness in the maximum
norm. Stable finite difference equation of explicit and implicit type.
Convection equations, exact solutions, stable and unstable finite
difference approximations. The CFL condition. Choice of variables and norm
for wave equations. The Petrowski condition and its limitations.
- April 26. Wellposedness in the sense of Hadamard. The von Neumann
condition. Stability in L_p and strong stability; their equivalence for
problems with coefficients independent of t. Stability with respect to
lower order perturbations. Wellposedness of a heat equation problem with
general boundary conditions on an interval.
Required Text
A First Course in the Numerical Analysis of Differential Equations by Arieh Iserles. Cambridge University Press.
Class Mailing List
Important: you should join
the mailing list. There are two steps to joining the list; the
first is to follow the instructions on the web page (including picking
a password), and the second is to REPLY TO the confirmation message sent
to you by the system. This list will be used for important announcements.
You can also send questions or comments to this list yourself (contact me
if you have questions about when this is appropriate).
Sun Account
If you don't have a Sun workstation account, but you want one,
send me email.
Don't Hesitate to Ask for Help
If you have questions, send me email, give me a call, or drop by my office.
Don't wait until it's too late!