Numerical Computing

Numerical Computing, CSCI-UA.0421-001

New York University
Spring Semester 2018

Class meetings: Tues-Thurs, 3:30 - 4:45pm, in Warren Weaver Hall (CIWW) 102.
Last day of class: Thursday, May 3, 2018.
Final examination: Thursday, May 10, 2018, 4:00-5:50pm, in Warren Weaver 317. **Note the different room for the final exam!**

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

Office: Warren Weaver Hall (CIWW), Room 430

Office Hours: Tues 2:00-3:00pm, Thurs 2:00-3:00pm, 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; splines; numerical integration; ordinary differential equations; and elementary eigenvalue problems. 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; an in-class midterm,; and either a written final exam or an individual course project.

The final grade will be calculated by averaging the three elements (Homework, Midterm, Final Project/Final Examination), with weights of 40%, 35%, 25%, where the weighting will be chosen individually to maximize each student's grade.

Academic Integrity

Academic integrity is a core principle of education at NYU, including five fundamental values: honesty, trust, fairness, respect, and responsibility. For a discussion of academic integrity policy in the Computer Science Department, see the Computer Science website. In numerical computing, academic integrity includes individual completion of all assignments. If one students shows or gives his/her work to another, both students are considered to be cheating. Students may not use work provided by any person outside the class, or by any external course such as the Web. Students may not solicit other people to do assignments (in whole or in part) for them. External sources, including published materials or materials on the Web, must be explicitly cited if they are involved in any substantive part of an assignment. During an exam, students may not communicate in any way with anyone else, nor use materials or technology not permitted by the instructore. One student may not look at another student's test during an exam. If one student allows another to look at his/her test during the exam, both students are considered to be cheating.

Prerequisites

CSCI-UA.0102 (introduction to computer science II), MATH-UA.0140 (linear algebra), and calculus (preferably MATH-UA.0122, Calculus II).

Students without this background should check with the instructor for permission to take the class.

Professor Gilbert Strang's famous linear algebra courses at MIT can be found on the MIT open courseware website or on YouTube, with search terms ``Strang linear algebra MIT''.

Textbook

The course material will be based on lectures, handouts containing lecture notes, and the textbooks A First Course in Numerical Methods by Uri M. Ascher and Chen Greif, published by the Society and Industrial Mathematics (SIAM) and Numerical Computing with Matlab by Cleve Moler. (Individual chapters of the latter can be downloaded from the Mathworks website.

Programming

Most homework assignments will include problems requiring you to write programs in Matlab, an interactive software package and programming environment. Matlab is a product of the Mathworks. Personal copies of Matlab are free for NYU students. Details can be found here .

Matlab tutorials are available online from several sites. For example, there is an array of tutorial and other educational resources for students at the MathWorks website .

Homework

HW1, due February 11, 2018.

HW2, due February 23, 2018 (24-hour extension of original deadline).

HW3, due March 4, 2018.

HW4, due April 5, 2018.

HW5, due April 17, 2018.

HW6, due May 1, 2018.

Final Examination

The scheduled final examination will take place on Thursday, May 10, 2018, from 4:00--5:50pm.

Course Project

Students must decide by April 26, 2018 whether they wish to take the final or submit a project. Course projects are due by 4:00pm, May 10, 2018 (when the final exam begins). General information about projects, including a list of possible topics and useful links, is here.

A brief LaTeX document containing a template for projects is here.

Lectures

January 23
(Lecture 1)
Introduction. Overview of numerical computing. Nonlinear equations in one dimension. Bisection. Chapter 3 of textbook (Ascher and Greif).
January 25
(Lecture 2)
Newton's method. Rate of convergence. Pure secant method.
January 30
(Lecture 3)
Properties of the secant method. Regula falsi and Wheeler's method. Inverse quadratic interpolation. Brent's method (zeroin). Starting and stopping.
February 1
(Lecture 4)
More details about Wheeler's method, inverse quadratic interpolation, and Brent's method (fzero). Starting and stopping.
February 6
(Lecture 5)
Chapters 1 and 2 of Ascher and Greif. General ideas in numerical computing. A generic model of floating-point computation. IEEE arithmetic.
February 8
(Lecture 6)
IEEE double-precision arithmetic.
February 13
(Lecture 7)
Review of HW1. More on IEEE double-precision arithmetic. Introduction to numerical linear algebra. Ascher and Greif, Chapters 4 and 5.
February 15
(Lecture 8)
More discussion of issues in graded HW1. Matrix norms. Diagonal linear systems. Triangular linear systems. Analysis of solving a lower triangular system, showing backward stability. Condition number of a matrix.
February 20
(Lecture 9)
Gaussian elimination with elementary matrices. LU factorization. Pivot size and its effects. Growth.
February 22
(Lecture 10)
Variations on partial pivoting. Symmetric positive definite matrices. The Cholesky factorization and its favorable numerical properties. Failure when the matrix is not ``sufficiently'' positive definite.
February 27
(Lecture 11)
The singular value decomposition (SVD) and what it reveals. Connections with the 2-norm of Ax and (A inverse); maximizing and minimizing the 2-norm. Significance of the columns of V and the columns of U. Estimating the rank of a matrix. Liberal and conservative rank-estimation strategies and their consequences.
March 1
(Lecture 12)
Linear least-squares problems. Linear least squares in mathematical modeling. Properties of the least-squares residual. The normal equations and concerns about conditioning. Orthogonal triangularization and its differences from Gaussian elimination.
March 6
(Lecture 13)
Householder transformations and their properties. Using Householder transformations to reduce an m times n matrix to upper triangular form. QR factorization.
March 8
(Midterm)
March 12-16 (Spring break)
March 20
(Lecture 15)
Solving least-squares problems using the QR factorization. Backward error analysis of the QR factorization. Some effects of perturbations. QR with column interchanges. Estimating rank with the QR factorization. Condition of the least-squares problem.
March 22
(Lecture 16)
Introduction to interpolation and approximation in one dimension. Ascher and Greif, Chapters 10 and 11. Functional norms. Horner's method for evaluating a polynomial. Uniqueness of the interpolating polynomial. The Vandermonde matrix. Lagrange and Newton forms of the interpolating polynomial. Weierstrass's Theorem.
March 27
(Lecture 17)
The error factor polynomial. Runge's function. The Runge phenomenon. Polynomial approximations based on function norms. Quick look at Chebyshev polynomials and Chebyshev points. Hermite osculating polynomials.
March 29
(Lecture 18)
Splines. Piecewise linear interpolation. Piecewise cubic splines. Conditions that define a spline. Natural splines, `clamped' splines and `not a knot' splines. polynomial. Piecewise cubic Hermite a la Matlab (pchip). Comparing different interpolants.
April 3
(Lecture 19)
Numerical integration (quadrature). The midpoint and trapezoid rules, and their connection with polynomial interpolation. Error estimates. Simpson's rule. The roles of Legendre polynomials and the Lagrange form of the interpolating polynomial. Clenshaw--Curtis quadrature.
April 5
(Lecture 20)
Composite quadrature; adaptive quadrature. Romberg quadrature. Introduction to initial value problems in ordinary differential equations. The test equation. The forward Euler method and its error estimate. Introduction to Runge-Kutta methods.
April 10
(Lecture 21)
Runge-Kutta methods. Transforming problems with higher serivatives into systems of first-order equations. Implicit methods. Backward Euler. Multistep methods. Adams-Bashforth and Adams-Moulton methods. Backward differentiation methods.
April 12
(Lecture 22)
Derivation of backward differentiation methods. Predictor-corrector methods. Stiffness. Stability. The Milne-Simpson method. Linear difference equations. Numerical issues. ODE software.
April 17
(Lecture 23)
Background theorems and results about eigenvalues and eigenvectors. The power method.
April 19
(Lecture 24)
The power method with shifts. The inverse power method (inverse iteration). The Rayleigh quotient; Rayleigh quotient iteration. The QR method. The pedagogical QR method.
April 24
(Lecture 25)
More on the pedagogical QR method. A diversion about PageRank and its connection with eigenvalues.
April 26
(Lecture 26)
Example of the pedagogical QR method. Finding the eigenvectors of a triangular matrix. Reduction to upper Hessenberg form.
May 1
(Lecture 27)
The implicit QR method; the implicit Q theorem. Plane rotations. Chasing the bulge. Some useful theory. The QR algorithm for symmetric matrices. Using bisection to find eigenvalues.
May 3
(Lecture 28)
Review of material covered in the course.