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.
- Homework 1, assigned Sept 13, due Sept 20
- Homework 2, assigned Sept 20, due Sept 27
- Homework 3, assigned Sept 27, due Oct 4
- Homework 4, assigned Oct 4, due Oct 14
- Homework 5, assigned Oct 11, due Oct 18
- Homework 6, assigned Oct 18, due Oct 25
- Homework 7, assigned Oct 25, due Nov 1
- Homework 8, assigned Nov 1, due Nov 8
- Homework 9, assigned Nov 8, due Nov 15
- Homework 10, assigned Nov 15, due Nov 22
- Homework 11, assigned Nov 22, due Dec 6
- Homework 12, assigned Dec 6, due Dec 13
Matlab programs used in class
Tentative Lecture Schedule
- (Sept 13) The Singular Value Decomposition; IEEE Floating Point Representation
- (Sept 20) IEEE Arithmetic, including Inf, NaN; Low Rank Approx property of SVD and Image Compression
- (Sept 27) The QR factorization, Gram-Schmidt, Orthogonal Polynomials, Modified Gram-Schmidt
- (Oct 4) Householder Orthogonalization; calling C programs from Matlab via MEX
- (Oct 11) Least-Squares via QR, Normal Equations, SVD. Polynomial interpolation and Approximation
- (Oct 18) Conditioning
- (Oct 25) Stability
- (Nov 1) Gauss Elimination and LU Factorization
- (Nov 8) Cholesky Factorization and the Eigenvalue Problem
- (Nov 15) Householder reduction to Hessenberg form, and Power, Inverse Power, Block Power Methods for Eigenvalues
- (Nov 22) QR Method for Eigenvalues
- (Nov 29) Arnoldi Iteration for Eigenvalues
- (Dec 6) GMRES, Lanczos and Gauss Quadrature
- (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.
- SVD, QR factorization and Least Squares (Text Lectures 4-11, not 18-19)
- Conditioning and Stability (Text Lectures 12-17, not 18-19, plus my book
Chapters 12-13)
- Systems of Equations (Text Lectures 20-23)
- Eigenvalues (Text Lectures 24-29, not 30-31), but generalized to the
general nonsymmetric case, as covered in class
- Iterative Methods (Text Lectures 32-38, not 39-40)
Official Syllabus
Books
Software
- MATLAB
We will use Matlab for most of the computing that we do in this course.
Matlab is by far the best environment for small-scale numerical
computing. Although by itself it is not the most efficient choice
for large-scale computing, it can be used to call compiled C and Fortran
routines and experiment with the results. Matlab is a product of
The MathWorks.
You can order your own copy of
Matlab for $99
or you can use Matlab on the Courant Sparcstation network (or dial in from home).
For Matlab documentation, type "helpdesk" at the Matlab prompt. To get started,
try out
A Free Matlab Online Tutorial or
Another Tuturial
or look for others by a web
search. You may want to look at a very outdated but still useful
Introductory Matlab Primer (3rd and last edition, postscript file).
There are many books on Matlab; I recommend
Matlab Guide, by
Higham and Higham, but you will find many other resources on the web,
including the latest information on Matlab 7.0.
- C
The lingua franca of computing.
You will learn how to call the BLAS from C and how to call
C routines from Matlab using the MEX interface.
Even if you are not a C programmer,
this is a good time to learn a little C.
More information.
- Fortran
Fortran is traditionally the language of numerical computing and is no
longer the dinosaur it used to be. It's still widely used in scientific
applications. Fortran 90, 95 and 2003
support vector operations and dynamic allocation and look a lot like Matlab.
But the updated versions of Fortran 77 are fine for most purposes,
especially when using the BLAS. Fortran routines can be called from Matlab
using the MEX interface. More information.
You don't need to use Fortran in this course, but it's an alternative
to using C.
- Java
Java is becoming a popular choice for numerical computing, but the strict
language requirements make it difficult to get good performance.
Java methods can be called directly from Matlab, without the complications
of the MEX interface.
More information.
You don't need to use Java in this course, but it's an alternative
to using C.
Math Computer Consultant
There is a volunteer
Math Computer Consultant (email: mconsult@cims.nyu.edu).
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!