Numerical Analysis

MATH-UA0252-1, Spring 2013,

Lectures: Tuesdays and Thursdays, 12:30 - 1:45 pm. WWH 312
Instructor: Olof Widlund
Office hours: 30 minutes before and after each class or by appointment.

Recitation sessions, Wednesdays, 8:00 - 9:15 am. Goddard Hall B03
Instructor: Juan Calvo
Office hours: WWH605, Wednesdays 1:00 - 1:45 pm and Thursdays 3:00 - 3:45 pm.

  • Coordinates of Olof Widlund
    Office: WWH 612
    Telephone: 998-3110
    Email: widlund at cims.nyu.edu

  • Coordinates of Juan Calvo
    Office: WWH 607
    Telephone: 998-3179
    Email: calvo at cims.nyu.edu

  • Exams
  • The first quiz was given on 2/21. Here it is with answers.
  • The second quiz was given on 3/12. Here it is with answers.
  • The midterm exam was given on Thursday March 28. It covered material covered in class before the Spring break. Here are some questions from old exams. And here is the midterm with solutions.
  • The third quiz was given on 4/16. Here it is with answers.
  • The fourth quiz was given on 5/2. Here it is with answers. It will cover floating point arithmetic and chapter 8.
  • The final exam, which will cover material from the whole semester, will be held on Thursday May 16 between 12noon and 1:50pm in WWH312. To the final you can bring two pages of notes covered on both sides with notes written by you. Here are some questions from old exams.

  • Homework
    There will be regular homework assignments, including programming using Matlab or any reasonable alternative. Scores will be made available on NYU Classes. When turning in programming assignments, please provide a listing of your program and output from runs with actual data that shows that your program works as intended. It is important that you do the homework yourself, but if you get stuck, I encourage you to consult with other students. 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. Please staple everything together and order the problems in the same order as given. The best way of turning in homework is to give it to me personally, in class or in my office. If I am not in my office, you can slide it under my door. Do not put homework in my mailbox.

  • Homework Assignments:
  • Homework set 1 Assigned February 6, due at 12:30 pm on Tuesday February 19.
  • Homework set 2 Assigned February 18, due at 12:30 pm on Tuesday March 5.
  • Homework set 3 Assigned February 28, due at 12:30 pm on Thursday March 14.
  • Homework set 4 Assigned March 26, due at 12:30 pm on Tuesday April 9 at 12:30 pm.
  • Homework set 5 Assigned April 9, due at 12:30 pm on Thursday April 18 at 12:30 pm.
  • Homework set 6 Assigned April 19, due at 12:30 pm on Thursday May 2 at 12:30 pm.

  • Required Text: An Introduction to Numerical Analysis by Endre Suli and David Mayers. Cambridge University Press.

  • Course content. All page and section references are to the textbook.
  • Note that you should make sure that you obtain and save all handouts; they should be an important part of your reading. Request copies if you miss any of them.
  • Week 1: Chapter 1 of the textbook. Finding roots of one nonlinear equation of one real variable. Brouwer's fixed point theorem. Contractions and the contraction mapping theorem. Rates of convergence. Linear and super-linear convergence. The bisection algorithm and its rate of convergence. Newton's method and its convergence rate in case of a simple root and a double root. The secant method. The Illinois method (handout).
  • Week 2: Further comments on the convergence of Newton's method, the secant method, and the Illinois method. Chapter 2: Solving linear systems of algebraic equations by Gaussian elimination. LU factorization for the case when pivoting is not required. An example of a two-by-two linear system where pivoting results in a greatly improved quality of the solution.
  • Week 3: LU factorization of non-singular matrices in the general case when pivoting is necessary or recommended. Partial pivoting. The conditioning of function evaluation: how does the relative error of the function values compare with the relative accuracy of the argument of the function. An introduction to vector norms. Proofs that the proposed ell-1 and ell-infinity norms are vector norms. Cauchy-Schwarz's inequality and the triangle inequality for the ell-2 norm. The case of general p, 1 < p < infinity: to establish the triangle inequality for those values of p, we formulate and prove Young's, Hoelder's, and Minkowski's inequalities. Those inequalities are also useful in many other contexts. Norms of matrices generated by different vector norms. Explicit formulas for p=1 and p=infinity in terms of the elements of the matrix. The case of p=2: the matrix norm is given by the square root of the largest eigenvalue of A^{T}A, a quantity much harder to compute. Conditioning of matrix-vector multiplication: ||A||*||A^{-1}|| appears.
  • Week 4: What linear systems of equations are difficult to solve? Those that are ill-conditioned, i.e., those for which ||A||*||A^{-1}|| is very large. Linear least squares problem; motivation and mathematical formulation. The normal equations. Fitting quadratic polynomials to given experimental data. How to solve a linear least squares problem if we have a QR factorization of the system matrix. Householder transformations; see subsection 5.5 of the text book. How to choose the vector v in the Householder transformation so that we eliminate the non-zeros below the first element in the transformed matrix? A choice of sign. Note the similarities and differences compared to Gaussian elimination. Solving tridiagonal systems of linear equations with and without pivoting. An appropriate storage scheme for this fast special version of Gaussian elimination. A few words on positive definite, symmetric matrices and how we can exploit this when developing Cholesky's algorithm, which is a variant of Gaussian elimination.
  • Week 5: Solving linear systems of equations with special matrices. Cholesky's algorithm; we save half the work and half the storage and do not need to pivot. We can also decide if a symmetric matrix is positive definite by attempting to use Cholesky's algorithm. Diagonal row dominant matrices; again no pivoting is needed. A proof that in the tridiagonal case, the matrices that remain to be factored are diagonally row dominant. Solving nonlinear systems of equations. Derivation of Newton's method in the case of two equations and two unknowns. The Jacobian. Brouwer's fixed point theorem and the method of simultaneous iterations. Eigenvalues and eigenvectors of symmetric real matrices; a review of basic results. First ideas of Jacobi's eigenvalue algorithm. Comments on the tridiagonal case; we can compute the eigenvalues of a symmetric matrix by first using a similarity transform which turns it into tridiagonal form and then solves the tridiagonal eigenvalue problem.
  • Week 6: Details on Jacobi's algorithm and a proof of its convergence. The Frobenius norm of a matrix. This norm does not change if a matrix is multiplied on the left or the right by an orthogonal matrix. Gerschgorin's circle theorem. Using a diagonal similarity transformation and Gerschgorin's theorem to locate eigenvalues of matrices with small off-diagonal elements such as those that arise after running the Jacobi method for sufficiently many steps. Using Householder transformations to reduce a real symmetric matrix to a tridiagonal matrix with the same eigenvalues. Cauchy's interlace theorem; cf. pp. 157-158 in the text book.
  • Week 7: Inverse iteration to find eigenvectors of symmetric matrices given an approximation of its eigenvalue. Rayleigh quotients and how to compute an accurate eigenvalue approximation from an approximation of its eigenvector. A bound for the eigenvalue in terms of the Euclidean norm of (A - \muI)u = w where u is a unit vector. The Bauer-Fike theorem. Sturm sequences based on Cauchy's interlace theorem and the bisection algorithm. A short introduction to the QR algorithm.
  • Week 8: Preparations for the midterm; some of the sample questions from older exams. A few words on polynomial interpolation. The midterm exam.
  • Week 9: Polynomial interpolation a la Lagrange and a la Newton. Handout on polynomial interpolation and numerical quadrature. The Newton table. A comparison with Taylor series. The coefficients in the Newton table in terms of derivatives of the function being interpolated. An error bound for polynomial interpolation. Runge's example of divergence of polynomial interpolation when using an increasing number of equidistant interpolation points. Further comments on Runge's example and on the use of an alternative set of points. Hermite interpolation: explicit formulas for the Hermite interpolation polynomials and how we also can use Newton's interpolation algorithm. Numerical differentiation using interpolation polynomials. Two numerical integration formulas which are exact for all linear functions; one uses the value at the midpoint of the interval and the other uses values at the two endpoints of the integration interval.
  • Week 10: Additional numerical quadrature rules, in particular Simpson's rule. How to determine the weights by using the Lagrange polynomial interpolation formula and by the method of undetermined coefficients. Error bounds for numerical quadrature using different error formulas for polynomial interpolation. The basis for adaptive Simpson. How to organize adaptive Simpson so that no function values are computed more than once. Comments on the examples in the homework. Using Hermite cubic interpolation to derive a numerical quadrature formula; the weights for the values of the first derivative are the same except for sign. In a composite schemes using subintervals of the same length, values of the first derivative are therefore only required at the end points of the overall interval. The basic idea underlying Romberg integration. Approximation using piece-wise polynomials; see hand-out and chapter 11 of the text book. Piece-wise linears and piece-wise Hermite interpolation. The basic idea behind cubic spline interpolation.
  • Week 11: Handout on computer arithmetic. More about linear and cubic spline interpolation. The special norms defined in terms of integrals of squares of first and second derivatives of functions; they give us alternative problems, which also give us the same piece-wise linear and cubic interpolants. The solution of the cubic spline interpolation problem requires the solution of a linear system with a positive definite, symmetric, tridiagonal matrix. Real numbers: integers, rational numbers, and irrational numbers. Base two systems. Bytes, words, and double words. Fixed point systems and their disadvantages. The Toy number system and the introduction of subnormal numbers. IEEE Single Format. The special meaning of the first and last lines of the table. Representing +/-infinity and NaN.
  • Week 12: More on IEEE floating point systems, in particular double precision, which is used in most numerical computations including Matlab. Rounding to nearest. Subnormal numbers. Computing Fibonacci numbers and trying to recover the initial values: why it works up to a point with relatively many steps of the recursion, when do we get overflow, and why do we get such extremely poor results in between. Normed linear space of infinite dimension; a pair of norms are generally not comparable. The best approximation in the maximum norm, over a bounded interval, of a continuous function by polynomials of degree n. Weierstrass' theorem. Existence of a min-max polynomial. Theorems 8.3 and 8.4 from the text book.
  • Week 13: The best approximation using polynomials of degree n, in the maximum norm, of x^{n+1}. Chebyshev polynomials. A three term recurrence. The error of polynomial interpolation revisited; why the set of zeros of a Chebyshev polynomial is a good choice. Orthogonality of the Chebyshev polynomials in an inner product with weight (1-x^2)^{-1/2}. Inner product spaces in particular those defined by a weight function and an interval of integration. Orthogonal polynomials with respect to these inner products. Three term recursion, which decreases the effort when computing these sets of polynomials. The Legendre polynomials and an alternative way of defining them as (d/dx)^n(x^2-1)^n.
  • Week 14: Examples of different sets of orthogonal polynomials. How to compute Laguerre polynomials by taking higher derivatives of certain functions; cf. problem 9.5 of the text book. A proof that all roots of orthogonal polynomials are real, simple, and lie in the open interval (a,b). Gaussian quadrature: counting the number of parameters and how to find the n+1 nodes that define the quadrature rule; they must be the zeros of the (n+1)th orthogonal polynomial for the relevant inner product. How to compute the weights for Gaussian quadrature. A discussion of one recent homework problem and some of the problems from previous exams; see the final line of "Exams".