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.

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.

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.

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

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.

Matlab tutorials are available online from several sites, such as one at the University of Maine.

Project list.

An outstanding project from Numerical Computing (Spring 2010), by Antony Kaplan, is available here, with his permission.

Antony Kaplan's project.

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.

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.

Handout 2

Handout 3

Handout 4

Handout 5

Handout 6

Handout 7

Handout 8

Handout 9

Handout 10

Handout 11

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