Numerical Analysis

MATH-UA0252-1, Spring 2016,

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

Recitation sessions: Wednesdays 8:00 - 9:15am starting February 3. CIWWH 317
Instructor: Shivam Verma
Office hours: Tuesdays, 2:50 - 4:50 pm in WWH 605.

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

  • Coordinates of Recitation Instructor Shivam Verma
    Telephone: 718-362-7836
    Email: shivamverma AT nyu.edu

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

  • Exams
    There will be a final, a midterm exam, and also some short quizzes. Scores are made available on NYU Classes.
  • The final exam will take place on Thursday May 12, 12:00 noon-1:50pm in our regular class room, CIWWH317. To the final you may bring two regular-sized pages covered by notes on both sides.
  • Here is a collection of problems given at finals in previous years.
  • The midterm was scheduled for Tuesday March 29. You could bring one page of notes, a regular-sized paper, covered on both sides. To the final, two pages of notes will be allowed.
  • Here is the March 29 midterm with solutions.
  • Here is last Spring's midterm without solutions.
  • Here is last Spring's midterm with solutions.
  • The first quiz was given on February 24. Here it is with solutions.
  • The second quiz, covering material related to homework sets 2 and 3, was given on Thursday March 10. Here it is with solutions.
  • The third quiz, covering material related to homework set 4, was given on Thursday April 14. Here it is with solutions.

  • Homework
    There will be regular homework assignments, including programming using Matlab, Octave, 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 7, due at 12:00 noon on Friday February 19.
  • Homework set 2 Assigned February 18, due at 12:00 noon on Tuesday March 1.
  • Homework set 3 Assigned February 29, due at 12:30 pm on Thursday March 10.
  • Homework set 4 Assigned March 31, due at 12:30 pm on Tuesday April 12.
  • Homework set 5 Assigned March 31, due at 12:30 pm on Thursday April 21.
  • Homework set 6 Assigned April 26, due at 12:30 pm on Tuesday May 3.

  • There are notes, developed by Shivam Verma and based on his recitations, available under Resources after accessing NYUClasses.

  • Course Content. All page and section references are to the textbook. For each week, there will be a short description of the content of the lectures. 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.
  • 1/26 and 1/28: A short introduction to numerical analysis. A look at the IEEE double precision floating point numbers; cf. a one page handout. This provides a finite but very large set of real numbers and also, interestingly, + and - infinity. We will later return for more details. Chapter 1: Solving one non-linear equation, f(x)=0, of one real function of one real variable. Basic iterations and conditions for convergence from a starting point close to the root. Newton's method and an estimate of its rapid rate of convergence provided that the first derivative of f(x) differs from zero at root. The secant method and an estimate of its rate of convergence. The bisection method, which is globally convergent but slow.
  • 2/2 and 2/4: The Illinois method, which in all iterations provide an interval in which the function f(x) will vanish; it shares the best features of the secant method and the bisection method. Chapter 2: Solving linear system of algebraic equations. A case against using determinants. Gaussian elimination in terms of factoring the system matrix into a product of a unit lower triangular matrix and an upper triangular matrix. How to solve triangular system of linear equations and how to spot if they are singular. A review of some basic linear algebra in particular linear dependence or linear independence of a set of vector, e.g., the columns of a matrix. The need for pivoting. Partial pivoting. Any nonsigular matrix A can, after a premutation of its rows, be factored int the product of a unit lower triangular and an invertible upper triangular matrix; partial pivoting will guarantee that all elements in the lower triangular matrix are less than or equal to 1 in absolute value. An example of a 2-by-2 linear system for which we will get a very accurate solution but only if we pivot. Tridiagonal matrices and how we can exploit the many zeros when factoring the matrix even if pivoting is required.
  • 2/9 and 2/11: More on tridiagonal matrices, in particular on diagonally dominant matrices for which pivoting is not needed. Norms of vectors in R^n. The ell_p norms; as for all norms three requirements must be met. Of these, the triangle inequality is the hardest to check. For p=2, we first establish the Cauchy-Schwarz inequality and then the triangle inequality. For p different from 1, 2, and infinity, we first establish Young's inequality, then Hoelder's, and finally, Minkowski's. Norms of matrices related to a vector norm. Simple formulas for the matrix-norms originating for p=1, and p=infinity. The case of p=2; the square-root of the largest eigenvalue of A^TA gives the answer. Simple inequalities for matrix norms. A bound of the relative error of the solution of a linear system of equations in terms of the relative change in the right hand side and the condition number of the matrix. A short review of the algebraic eigenvalue problem with special emphasis on the case of symmetric matrices.
  • 2/16 and 2/18: The effects of perturbing the coefficient matrix of a linear system of equations on the solution; the condition number of the matrix enter. Reexamining a two-by-two case showing that without pivoting the perturbation of the matrix is quite large while it is very small if we use partial pivoting; note that the matrix is quite well condtitioned. Comparing vector and matrix norms; factors linear in n, the dimension of the space, enters. Cholesky's algorithm for linear systems with positive definite, symmetric matrices; we are always able to take an additional factorization step since the matrix that remains to be factored is also positive definite, symmetric. Cholesky's algorithm can also be used to determine if a matrix is positive definite. A first introduction to least squares problems and the derivation of the normal equations. Revisiting Cholesky's algorithm; write the symmetric, positive definite matrix as a product of a lower triangular matrix and its transpose and derive and solve equations for the elements of the triangular matrix. Solving a linear least squares problem with a matrix with a square upper triangular matrix on top followed by rows of zeros. Factoring any matrix with more rows than columns into the product of an orthogonal matrix times a matrix of the special form just introduced. How to reduce a general least squares problem to the special case using such a factorization. Constructing such orthogonal matrices using Householder transformations of the form I - 2 vv^T/v^Tv; there are always two such matrices and why we should choose one of them. Note that Householder transformations are discussed on pp. 150--156 in the text book.
  • 2/23 and 2/25: Solving underdetermined systems of linear equations; they can also be reduced to a positive definite, symmetric linear system if the rows of the coefficient matrix are linearly independent. Further looks at how Householder transformations can be used to solve linear least squares problems. The transformations should be stored in terms of the vectors v instead of computing the matrix elements and there is no good reason to form products of the Householder matrices. How to use Householder matrices to turn a symmetric matrix into a tridiagonal matrix with the same eigenvalues; this is the first of two steps used in several algorithms to compute the eigenvalues of symmetric matrices; in the second step we compute the eigenvalues of the tridiagonal matrices. Polynomial fitting of data using least squares. An example used by Guass in an 1850 lecture to illustrate the least squares algorithm. Why we should not try to compute the eigenvalues of matrices by first finding its charcteristic polynomial and then computing the roots of that polynomial; two polynomials with roots were shown to be very sensitive to to tiny changes in their coefficients. Cauchy's interlace theorem and finding eigenvalues of tridiagonal matrices by Sturm sequences; see section 5.6 of the text book. A first discussion of Gerschgorin's first theorem; see pp. 145-146 of the text book.
  • 3/1 and 3/3: Gerschgorin's two theorems. What these theorem can be used for including a discussion of Theorem 5.6 on page 148. Inverse iteration to determine eigenvectors for eigenvalues which are approximately known; this involves an argument based on expanding arbitrary vectors using eigenvectors of symmetric matrices. The formulation of a perturbation theorem given as Theorem 5.15 on page 173.
  • 3/8 and 3/10: Rayleigh quotients and a proof of the two final theorems of chapter 5. Jacobi's algorithm and a proof that its classical variant converges. A short introduction to the QR algoithm; this algorithm can be used to find the eigenvalues of any matrix. How one can save work by first turning the matrix into tridiagonal or Hessenberg form. Solving systems of nonlinear equations by Newton's method; deriving this method by linearization and using Taylor's formula. Open and closed sets and Cauchy sequences. Contraction mappings and simultaneous iteration. A proof of contraction if the Jabobian of the function is diagonally dominant. Quadratic convergence of Newton's method provided that the Jacobian matrix is well conditioned.
  • 3/22 and 3/24 (lectures given by David Kelly): Sections 6.1 -- 6.4 in the text book. Lagrange and Hermite interpolation. Existence and uniqueness. Runge's phenomenon. Error bounds.
  • 3/29: Midterm exam.
  • 3/31: A few comments on the midterm problems; the exam with solutions are available on this home page. Computing Lagrange interpolation polynomials using barycentric formulas and a number of aritmetic operations which is linear in the degree of the polynomial; see the hand out given out 3/31. How to avoid Runge's phenomenon; see page 187 and Chapter 15 of the handout. The key is using Chebyshev point instead of equidistant points. A short introduction to some numerical quadrature rules based on lower order interpolation of the given function f(x) that we wish to integrate.
  • 4/5 and 4/7: Representing polynomials in terms of Chebyshev polynomials; they are particularly useful when we interpolate using the Chebyshev points x_j = cos(j\pi/n), 0 \leq j \leq n, since we can then use FFT to compute the coefficients. The Chebyshev polynomials and how they can be defined recursively. Orthogonality of these polynomials in a weighted inner product. An introduction to Fourier series and the inverse Fourier transform for Fourier series. The discrete Fourier transform and its inverse. The basic trick behind the FFT and the const.*nlog(n) work estimate. Adaptive Simpson numerical quadrature and its theoretical underpinnings. How to develop error bounds for different numerical quadrature formulas; see section 7.3. For some methods we can use the error bounds for polynomial interpolation and a mean value theorem from calculus, but for others, including Simpson's rule, a more elaborate argument is required. Interpolation with continuous, piecewise linear functions and cubic splines which have two continuous derivatives; see chapter 11. The derivation of natural cubic splines; we need to solve a linear system of equations. However, the system matrix is diagonally dominant, symmetric and tridiagonal.
  • 4/12 and 4/14: A proof of theorem 11.3 on cubic natural splines. Binary and decimal representation of real numbers. Two's complement representation of integers. Fixed point arithmetic. The toy floating point system and a discussion of the relative accuracy of real numbers if roundng to nearest and the numbers fall in the range of normalized floating point numbers. Single and double precision IEEE numbers. The first and last rows and their meaning in the two tables on single and double precision numbers. Subnormal numbers, NaN and infinity. Binary arithmetic and the danger of adding two numbers which have a sum much small than any of the two. The success of multiplication and division using floating point arithmetic. Note that most but not all these topics are covered in a 20-page handout.
  • 4/19 and 4/21: Inner product spaces of continuous functions defined by integrals over a finite or infinite interval [a,b] and a non-negative weight function. Orthogonal polynomials which provide bases of spaces of polynomials replacing the regular monomial basis 1, x, x^2, ... Properties of orthogonal polynomials: they can be generated by three-term recurrence formulas and all the roots of any of these polynomials lie in (a,b) and are simple. Derivation of Gaussian quadrature rules. Two formulas for the quadrature weights, one of which shows that they are all positive. The points where the functions are evaluated are the roots of a special orthogonal polynomial. The special cases w(x)=1, a =-1, and b=1, of w(x)=1, a=0, b=1, and of w(x)=e^{-x}, a=0, and b=infinty. The two point Gaussian quadrature rules where constructed for these three cases; the first two are closely related by using a simple linear transformation.
  • 4/26 and 4/28: Derivation of Radau quadrature rules as in section 10.6. Problem 9.5. A Gaussian quadrature rule based on Chebyshev polynomials A short introduction to chapter 8 and best approximation in the maximum norm. An application of this problem to the error formula for Lagrange interpolation given as Theorem 6.2; the best choice of the x_i are roots of a Chebyshev polynomial. A brief discussion of existence, uniqueness and a characterization of the best approximation; continued on 4/28. Weierstrass theorem and why we cannot prove it by using even a very good set of interpolation points such as the Chebyshev points. A proof of the existence of a best polynomial approximation in the max-norm. De La Vallee Poussin's theorem and the equal-oscillation theorem. Solving a special best approximation theorem for f(x)=x^{n+1} and why it is of interest when we consider the standard error bound for Lagrange interpolation.
  • 5/3 and 5/5: Review of material covered during the semester focusing on some of the homework problems.