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
1. January 18. Polynomial interpolation, Newton's interpolation procedure, numerical quadrature. Euler's method for initial value problems for ODE.
2. 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.
3. 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.
4. February 8. No class. Instructor will be 4000 miles away. Make-up class to be held on May 3.
5. 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.
6. 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.
7. 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.)
8. 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.
9. March 22. Cancelled because of sudden illness of instructor.
10. 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.
11. 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.
12. 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.
13. 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.
14. 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!