Numerical Computing

Numerical Computing, V22.0421

New York University
Spring Semester 2010

Instructor: Margaret Wright, mhw@cs.nyu.edu

Office: Warren Weaver Hall (CIWW), Room 430

Office Hours: Tues 12:30-1:30pm, Thurs 10-10:45am, or by appointment

Class meetings: Tues-Thurs, 11am-12:15pm, in CIWW 317.
Last day of class: Thursday, April 29.
Final exam: Thursday, May 6, 10-11:50am, in CIWW 317.

Two review sessions (to answer questions), in CIWW 317.
May 4 and May 5, 11:00am-12:15pm.

Course Description

Numerical computing is an interconnected combination of computer science and mathematics in which we develop and analyze algorithms for solving important problems in science, engineering, medicine, and business---for example, designing a bridge, choosing a stock portfolio, or detecting tumors in medical images.

This class will cover several topics, including: one-dimensional nonlinear equations; understanding and dealing with sources of error; linear equations and linear least-squares; data fitting; and ordinary differential equations. As much as possible, numerical methods will be presented in the context of real-world applications.

Coursework

The course requirements include class attendance; written and programming homework assignments; a course project; and a final examination. All of these will count in your final grade. The final grade will be calculated by averaging the three elements (Homework, Project, Final Examination), with weights of 30%, 30%, 40%, where the weighting will be chosen for each student to maximize his/her grade.

Prerequisites

V22.0102 (introduction to computer science II), V63.0140 (linear algebra), and calculus (preferably V63.0122, Calculus II). Students without this background should check with the instructor for permission to take the class. Relevant background material about calculus and linear algebra will be passed out in class. Professor Gilbert Strang's famous linear algebra course at MIT can be found on the MIT open courseware website or on YouTube, with search terms ``Strang linear algebra MIT''.

Class mailing list

A class mailing list will be set up using a Web-based interface at http://www.cs.nyu.edu/mailman/listinfo/v22_0421_001_sp10

Textbook

Primary text: A First Course on Numerical Methods by Uri Ascher and Chen Greif, accessible through a password-protected website. Link to textbook.
Other material will be passed out as notes.

Final Examination

Date, time, and place: Thursday, May 6, 10-11:50am, in CIWW 317

A set of approximately 50 questions (containing all possible final exam questions) will be passed out in class on April 22 ,2010, two weeks before the final exam. At the time of the final exam, each student will receive a list of (approximately) 6 of these questions that he/she is to answer during the exam period. Each student will receive a different subset of questions to be answered.

During the final examination, students must use only their knowledge and a pencil/pen. Written or electronic answers prepared in advance must not be consulted in physical or electronic form during the exam, nor are students allowed to use laptops, cell phones, or any other communication device during the exam.

Programming

The instructor will use Matlab, an interactive software package and programming environment, for her own programs. If you prefer another language, this is fine as long as your code is intelligible. Matlab is a product of the Mathworks; a student version costs around $100 at the Computer Store, or you can use Matlab in a Courant computer lab. (You will need a CIMS account, which will be provided after the second class.) You can use Matlab remotely, with a few (solvable) complications if you wish to use its graphics capabilities. Matlab tutorials are available online from several sites, such as one at the University of Maine

Course Project

Each student is expected to choose and complete an individual project to demonstrate his/her creativity and mastery of the main concepts of numerical computing. List of possible projects.
Projects are due on April 13, 2010. Every project must be approved in advance by the instructor following an individual meeting with the student and a short ``prospectus'' submitted by the student.

Revised projects must be submitted by 12:15pm on Tuesday May 4.


Homework

HW1, due February 2, 2010
HW2, due February 11, 2010
HW3, due February 23, 2010
HW4, due March 11, 2010
HW5, due April 22, 2010
Homeworks may be submitted in written form or via email. They must be in the instructor's possession by 5pm on the due date. Without explicit permission from the instructor in advance, late homework will be marked down by 30% for every day of lateness.

Lectures

January 19 Course overview.
January 21One-dimensional nonlinear equations (1).
Chapter 3 of textbook (Ascher and Greif). Handout 1.
January 26 One-dimensional nonlinear equations (2).
First homework assignment, due February 2.
January 28 One-dimensional nonlinear equations (3).
February 2 Errors (1).
Chapters 1 and 2 of textbook (Ascher and Greif).
Second homework assignment, due February 11.
February 4 Errors (2). Floating-point systems.
February 9 IEEE arithmetic (1).
Handout 2.
February 11 IEEE arithmetic (2).
Second homework assignment, due February 12 (postponed one day by weather).
Third homework assignment, due February 23.
February 16 Linear algebra review. Direct methods for nonsingular linear systems (1).
Chapters 4 and 5 of Ascher and Greif.
February 23 Direct methods for nonsingular linear systems (2).
February 25 Direct methods for nonsingular linear systems (3).
Fourth homework assignment, due March 11.
March 2 LU factorization. The need for pivoting in Gaussian elimination.
List of possible projects handed out.
March 4 Pivoting strategies in Gaussian elimination.
Stability analysis of Gaussian elimination with partial pivoting.
March 9 NO CLASS.
March 11 Disadvantages of calculating the inverse.
Symmetric linear systems. Positive definite symmetric systems.
Fourth homework assignment due.
March 15-20 SPRING BREAK.
March 23 Positive definite symmetric systems. Symmetric indefinite systems.
Householder transformations and triangularization.
Chapter 6 of Ascher and Greif.
March 25 Householder transformations and triangularization.
Data fitting; linear least-squares.
Normal equations. QR factorization.
Chapter 6 of Ascher and Greif.
March 30 Normal equations. QR factorization.
April 1 Numerical rank estimation.
SVD. Rank-revealing QR.
April 6 Start interpolation and approximation.
Polynomial interpolation.
Chapters 10, 11, 12 of Ascher and Greif.
April 8 Polynomial interpolation.
Representations of the interpolating polynomial.
Polynomial interpolation at many equally spaced points.
April 13 Piecewise polynomial interpolation.
Splines.
April 15 Piecewise polynomial interpolation.
Piecewise cubic Hermite interpolation. Smoothing splines.
April 20 Numerical integration (quadrature).
Chapter 15 of Ascher and Greif.
April 22 Numerical integration (continued).
Composite quadrature rules. Romberg integration
April 27 Initial value problems in ordinary differential equations.
Chapter 16, Ascher and Greif.
April 29 Initial value problems in ordinary differential equations.
Short summary of course content.
May 4, 5 Review sessions (11:00am-12:15pm).