Numerical Methods I

G22.2420, G63.2010
Fall 2004, Mondays 5-7 p.m., WWH Room 101

Note: the class will start at 5:10 p.m. on the first class meeting (Sept 13) and at 5:00 p.m. subsequent weeks.

Instructor: Michael L. Overton

  • Coordinates
  • Should you take this course?
    The course lectures take place only once a week, and this means they will move fast. The lectures will be quite mathematical at times, but we will also use the computer a lot in class to illustrate the concepts. The course is mostly about numerical linear algebra, a surprisingly rich subject that lies at the heart of modern scientific computing, but we will also cover other classical subjects of numerical analysis such as interpolation and quadrature. (ODE's and PDE's are covered in Numerical Methods II.) Hopefully, if you like math and computers, you will like this class. On the other hand, if your math background is weak, or you have no experience with computing, you are likely to find it very difficult. Don't hesitate to discuss these issues with me, after class or in my office.

  • Prerequisites
    A solid knowledge of undergraduate linear algebra, and experience with writing computer programs (in C or other language). Prior knowledge of Matlab is not required, but you will be expected to learn it as the course progresses.

  • Requirements
    Regular homework assignments, including programming assignments, primarily using Matlab, but also occasionally C (alternatively, Fortran or Java). 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
    Homework may be given to me in class or in my office, or left under my office door. Please do not leave homework in my lobby mailbox or send it by email. Please staple all pages together. Late homework will be penalized 20%. Homework will not be accepted more than one week late, except in special circumstances.
  • Matlab programs used in class

  • Tentative Lecture Schedule
    1. (Sept 13) The Singular Value Decomposition; IEEE Floating Point Representation
    2. (Sept 20) IEEE Arithmetic, including Inf, NaN; Low Rank Approx property of SVD and Image Compression
    3. (Sept 27) The QR factorization, Gram-Schmidt, Orthogonal Polynomials, Modified Gram-Schmidt
    4. (Oct 4) Householder Orthogonalization; calling C programs from Matlab via MEX
    5. (Oct 11) Least-Squares via QR, Normal Equations, SVD. Polynomial interpolation and Approximation
    6. (Oct 18) Conditioning
    7. (Oct 25) Stability
    8. (Nov 1) Gauss Elimination and LU Factorization
    9. (Nov 8) Cholesky Factorization and the Eigenvalue Problem
    10. (Nov 15) Householder reduction to Hessenberg form, and Power, Inverse Power, Block Power Methods for Eigenvalues
    11. (Nov 22) QR Method for Eigenvalues
    12. (Nov 29) Arnoldi Iteration for Eigenvalues
    13. (Dec 6) GMRES, Lanczos and Gauss Quadrature
    14. (Dec 13) Conjugate Gradients and Chebyshev Polynomials
  • ORAL FINAL EXAM: 25 minutes in my office. The emphasis will be on what you did for the homework. You pick one of the following topics and I pick one, and we will talk about what you learned about it. You do not have to memorize complicated details, but you should be able to explain the main ideas that we talked about in class and that you explored in the homework.
  • Official Syllabus
  • Books
  • Software
  • Math Computer Consultant
    There is a volunteer Math Computer Consultant (email: Please contact the consultant if you have trouble with the Courant computer facilities or questions about the software we are using. The consultant is there to help, but cannot debug programs for you.

  • Class Mailing List
    Important: you must join the class 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). If you do not want to use an NYU email address, be sure to notify me in person or by email from an NYU address about your preferred address, so I can add it to my spam filter.

  • Sun Account
    If you don't have a Sun workstation account, please request one, even if you plan to do most of the homework on your home computer. You will need it later. Request this account from petagna@cs if you are registered in G22.2420 and from the math department if you are registered in G63.G22.2420.
  • SIAM
    As an NYU graduate student you have the opportunity to join SIAM for free. SIAM is the main professional organization for applied and computational math, and offers a number of benefits to members. I've been a member since I was a graduate student, and have benefitted in many ways from my association with SIAM.

  • 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!