Numerical Computing

Numerical Computing, CSCI-UA.0421

New York University
Spring Semester 2012

Class meetings: Tues-Thurs, 2pm-3:15pm, in Warren Weaver Hall (CIWW) 201.
Last day of class: Thursday, May 3, 2012.

Three sittings of final exam:
Tuesday, May 8, 2pm-4pm, CIWW 201.
Monday, May 14, 2pm-4pm, CIWW 201.
Tuesday, May 15, 2pm-4pm, CIWW 201.

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

Office: CIWW, Room 430

Office Hours: Tues 3:30-4:30pm, Thurs 1pm-1:55pm, or by appointment.

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''.

Textbook

Primary text: A First Course in Numerical Methods by Uri Ascher and Chen Greif, published by the Society for Industrial and Applied Mathematics, available at the NYU Bookstore or directly from SIAM.

NYU is an academic member of SIAM, and NYU students are therefore eligible for a 30% discount off the list price of the book. Other material will be passed out as notes.

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. Students must meet individually with the instructor to receive approval of all course projects; this approval should be received by March 27. The projects are due by 11:59pm on Sunday, April 29.
Project list.
An outstanding project from Numerical Computing (Spring 2010), by Antony Kaplan, is available here, with his permission.
Antony Kaplan's project.

Final Examination

All the questions to appear on the final exam were handed out in class on Thursday, April 26.

The questions will NOT be posted on the Web.

At the time of the final exam taken by a particular student (chosen from the offering dates listed above), each student will receive an individual list of the problems that he/she will need to answer. These lists will vary from student to student.

Homework

HW1, due February 7, 2012
HW2, due February 16, 2012
HW3, due February 21, 2012
HW4, due March 3, 2012
HW5, due March 9, 2012
HW6, due March 29, 2012
HW7, due April 10, 2012
HW8, due April 19, 2012
Without explicit permission from the instructor in advance, late homework will be marked down by 30% for every day of lateness.

Handouts

Handout 1
Handout 2
Handout 3
Handout 4
Handout 5
Handout 6
Handout 7
Handout 8
Handout 9
Handout 10
Handout 11

Lectures

January 24 (Lecture 1) Overview of numerical computing.
January 26
(Lecture 2)
One-dimensional nonlinear equations (1).
Bisection. Newton's method. Chapter 3 of textbook (Ascher and Greif). Handout 1.
January 31
(Lecture 3)
One-dimensional nonlinear equations (2). Secant method. Issues in numerical software reliability. False position.
Homework 1, due February 7.
February 2
(Lecture 4)
Condition of a mathematical problem. Computable measures of goodness. Forward and backward stability. Absolute and relative error.
February 7
(Lecture 5)
Floating-point systems. Representable numbers. Properties of floating-point calculation. Cancellation error.
Chapters 1 and 2 of Ascher and Greif.
Homework 2, due February 14.
February 9
(Lecture 6)
The IEEE floating-point standard.
Handout 4.
Section 2.4 of Ascher and Greif.
February 14
(Lecture 7)
Review of relevant linear algebra. Vector and matrix norms.
Chapter 4 of Ascher and Greif.
Homework 3, due February 21.
February 16
(Lecture 8)
Matrix norms (continued). Singular value decomposition. Condition of a matrix.
Chapter 4 of Ascher and Greif.
February 21
(Lecture 9)
More on the SVD. Triangular systems. Gaussian elimination. Elementary matrices.
Chapter 5 of Ascher and Greif.
Homework 4, due March 1.
February 23
(Lecture 10)
Gaussian elimination. LU factorization. The need for pivoting. Permutation matrices.
Chapter 5 of Ascher and Greif.
February 28
(Lecture 11)
Partial pivoting. Growth. Backward error analysis.
Chapter 5 of Ascher and Greif.
March 1
(Lecture 12)
Backward error bound for Gaussian elimination with partial pivoting. Why GEPP (with no growth) produces a small residual. Symmetric positive definite matrices. The Cholesky factorization and its stability.
Deadline for Homework 4 extended to March 3.
Homework 5, due March 9.
March 6
(Lecture 13)
Linear least-squares problems. Formulation in terms of range and null spaces. The normal equations. Condition of the normal equations.
Chapter 6 of Ascher and Greif.
March 8
(Lecture 14)
Orthogonal triangularization of a matrix. Householder transformations.
Chapter 6 of Ascher and Greif.
March 12-16 NYU spring break.
March 20
(Lecture 15)
Short review of linear least-squares. Orthogonal triangularization; the QR factorization. Using the QR factorization to solve a least-squares problem.
Handout 5.
Homework 6, due March 29.
March 22
(Lecture 16)
Condition of a non-square matrix.
Condition of the linear least-squares problem.
Handout 6.
Estimation of numerical rank. The effects of rank-estimation strategies.
March 27
(Lecture 17)
Short review of matrix factorizations and their uses. Handout 7 (on norms and their properties). Next topics: interpolation and approximation. Function norms as distinct from vector norms.
The interpolating polynomial.
Evaluation of a polynomial using Horner's rule.
Finding coefficients for polynomials in monomial form. Vandermonde matrices.
Chapters 10, 11, and 12 of Ascher and Greif.
March 29
(Lecture 18)
The Lagrangian form of the interpolating polynomial. Error in the interpolating polynomial at non-interpolated points. Perils of equally spaced points; the error factor polynomial.
Runge's famous function. Handout 8.
Polynomial approximation using function norms. Chebyshev equioscillation theorem.
April 3
(Lecture 19)
Matching function and derivative values. Hermite interpolation.
Introduction to piecewise polynomials.
Piecewise linear interpolation. Interpolating cubic splines.
Homework 7, due April 10.
April 5
(Lecture 20)
Three common varieties of splines and their properties.
Matlab's `pchip' interpolation and its calculation.
Comparing interpolation approximation with different techniques.
B-splines (terse summary). Handout 9.
April 10
(Lecture 21)
Numerical integration, aka quadrature.
Quadrature rules and their degree.
Newton--Cotes formulas: midpoint, trapezoidal, Simpson's rule, and their comparative accuracy.
April 12
(Lecture 22)
The general principle of interpolatory quadrature.
Gaussian quadrature. Clenshaw--Curtis quadrature. Handout 10.
Composite quadrature methods.
Homework 7, due April 19.
April 17
(Lecture 23)
Adaptive quadrature. Estimating error via composite quadrature rules.
Romberg quadrature. Introduction to ordinary differential equations.
Stability of an initial value problem. Motivating the forward Euler method.
April 19
(Lecture 24)
Forward Euler. The accuracy of an ODE method.
Deriving higher-order one-step methods.
Runge--Kutta formulas; derivation of simple R-K formulas; the RK4 formula.
The idea of implicit methods. Backward Euler.
The benefits of implicit methods. Multistep methods, explicit and implicit. Handout 11.