Numerical Analysis

MATH-UA0252-1, Spring 2015,

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 4. CIWWH 317
Instructor: Juan Calvo
Office hours: Wednesdays 10:00 - 11:00am and by appointment.

  • 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

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

  • Exams
    There will be a final on May 14, a midterm exam, and also some short quizzes. Scores are made available on NYU Classes. The midterm exam took place on Tuesday March 31. To the final you can bring two regular-sized papers covered on both sides with notes written by yourself. The textbook and other notes will not be allowed.
  • Here is a collection of midterm problems given in previous years.
  • Here is a collection of problems given at finals in previous years.
  • Here are five of those problems with answers.
  • The first quiz was held on 3/3. Here it is with solutions.
  • Here is the midterm given on March 31, with answers.
  • The second quiz was held on 4/16. Here it is with solutions.
  • The third quiz, on material from chapters 9,10, and 11, was held on Thursday April 30. 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 3, due at 12:00 noon on Wednesday February 18.
  • Homework set 2 Assigned February 11, due at 12:00 noon on Friday February 27.
  • Homework set 3 Assigned February 28, due at 12:00 noon on Friday March 13.
  • Homework set 4 Assigned March 23, due at 12:00 noon on Monday April 6.
  • Homework set 5 Assigned April 6, due at 12:00 noon on Friday April 17.
  • Homework set 6 Assigned April 14, due at 12:00 noon on Monday April 27.

  • 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/29: Material from the first chapter, essentially sections 1.1 and 1.2. A brief discussion of Newton's method stressing the importance of having a nonzero derivative df/dx at the solution of the equation f(x)=0 to have fast convergence.
  • 2/3 and 2/5: Newton's method and the secant method. Estimate of the local rates of convergence, i.e., how fast the error is decreased provided that we are close enough to the solution. The bisection method: reliable and very slow. The Illinois method, which also provide upper and lower bounds for the zero and which converges much faster than the bisection method. Relative errors and how to estimate the relative error of computing the value of a function in relation to the relative error of the input: by using simple calculus, we found that what is important if df(x)/dx*x/f(x), which we call the condition number of the problem; see pages 68-69. A short review of basic results on systems of linear algebraic equations; Ax=b, where A is n-by-n and x and b column vectors with n components. This problem cannot be solved by evaluating determinants; instead we use Gaussian elimination. Gaussian elimination can be described by using n-1 special unit lower triangular matrices. The non-trivial elements of these matrices are called mulitpliers and by inserting them below the diagonal in a unit lower triangular matrix L, after changing the sign, we obtain, if pivoting is not needed, a factorization of A = LU, where U is upper triangular. We note that triangular systems of equations are easy to solve.
  • 2/10 and 2/12: Why is pivoting necessary and how will pivoting effect Gaussian elimination? A tiny problem where pivoting is not necessary in exact artithmetic but leads to disaster if there is rounding errors. The partial pivoting strategy. A proof that we can factor PA for any non-singular matrix A into a product of L and U, where P is a permutation matrix which results in a reordering of the rows of A. Operation counts for the factorization and solution steps. Tridiagonal matrices and how we can then save arithmetic by exploiting and preserving the zeros of the matrix. How best to store and manipulate a tridiagonal matrix when we wish to solve a linear system with a tridiagonal matrix; the case when pivoting is not necessary and the case when we need to pivot. How to generalize all this to the case of band matrices. A scheme to store general sparse matrices, i.e., matrices with many zero elements. How zeros are lost when we carry out Gaussian elemination. Strictly diagonal dominant matrices; the tridiagonal case is discussed in Chapter 3 of the text book. Vector norms; three conditions are required. The ell_1, ell_infinity and ell_2 norms. Cauchy-Schwarz's inequality and the proof of the triangular inequality for the ell_2 norm.
  • 2/17 and 2/19: Proofs of Young's, Hoelder's, and Minkowski's inequalities. Matrix norms subordinate to vector norms. Condition numbers of matrices and how they play a role in the study of the effects of perturbations of the right hand side, e.g., caused by rounding errors, on the solution of a linear system of equations. Formulas for the matrix norms subordinate to the ell_1, ell_2, and l_infinity norms. Positive definite, symmetric matrices and Cholesky's algorithm to solve linear systems with such system matrices. Cholesky's algorithm can also be used to decide is a symmetric matrix is positive definite. Linear least squares problems; motivation for these problems and the normal equations.
  • 2/24 and 2/26: When solving linear least squares problems, we should avoid forming the matrix A^TA of the normal equations. Instead, we should work with a QR factorization. The QR factorization comes in two flavors. In the text there is proof that A=\hat{Q} \hat{R} where \hat{Q} is a rectangular matrix with orthogonal columns and \hat{R} is upper trinangular. In the lecture the alterantive A = QR was explored where Q is a square orthogonal matrix obtained as a product of Householder transformations; see pp. 150-156. Note that the resulting algorithm also provides a proof of the existence of such a factorization. A brief discussion of underdetermined linear systems of equations. When they have solutions, there is never uniqueness since the matrix has a null space. An observation that \hat{R}^T equals the lower triangular Cholesky factor of A^T A; using Householder transformations, this matrix can be computed without forming A^T A. More discussion of the use of Houesholder transformations; they are also used to turn symmetric matrices into symmetric tridiagonal matrices while preserving the eigenvalues. A review of standard results on the algebraic eigenvalue problem for symmetric matrices. They have a full set of orthonormal eigenvectors which can be combined into an orthogonal matrix. A similarity transformation using this matrix transforms the symmetric matrix into a diagonal with the eigenvalues on the diagonal. Solving systems of nonlinear equations using a simple fixed point iteration and Newton's method.
  • 3/3 and 3/5: Jacobi's eigenvalue alrgorithm for symmetric matrices with a proof that is converges whenever we select the largest off-diagonal matrix for elimination. Gerschgorin's theorems and Theorem 5.6. Cauchy's interlace theorem and Sturm sequences for symmetric tridiagonal matrices.
  • 3/10 and 3/12: How to get started with Sturm sequence computation; find and interval in which all eigenvalus by computing the infinity norm of the tridiagonal matrix. Computing eigenvectors corresponding to accurate eigenvalues by using inverse iteration. Rayleigh quotients. Two perturbation theorems given at the end of chapter 5. A brief introduction to the QR algorithm for computing the eigenvalues of matrices. The Lagrange interpolation problem; existence and uniqueness. Error bounds: Theorem 6.2 in the text book. Runge's phenomenon. Hermite interpolation.
  • 3/24 and 3/26 The barycentric interpolation formulas which allow us to compute the value of an n-th degree Lagrange interpolation polynomial at a point x using only O(n) aritmetic operations; cf. the handout marked Barycentric Interpolation Formula. Specific weight for the case when we interpolate at the Chebyshev points x_j = cos(j\pi/n), j=0,1,...,n. Chebyshev polynomials and how to solve the Lagrange interpolation problem using this alternative basis for the space of polynomials and the cosine-variant of FFT, the Fast Fourier Transform. (Look at the handout and on page 241 of the text book.) Estimating the Lagrange interpolation error as in Chapter 15 of the handout. Best approximation with polynomials of continuous functions and a few words how its error depends on the smoothness of the function. Finally, the Lebesgue constants for polynomial interpolation as in Theorem 15.2 of the handout. Conventional lower order approximation of integrals using lower order polynomial interpolation. Simpson's rule designed to be exact for all polynomials of degree 2 but which in fact also is exact for cubics. An error formula involving the fourth derivative of f(x). The idea of subdividing the interval of integration and using Simpson's rule over the subintervals and adding the results. How to authomated the partitioning of the interval by an adaptive procedure; compare the small handout as well as the fourth homework set.
  • 3/31 Midterm exam. 4/2 Taylor series and an alternative using divided difference. Applying the same machinery to obtain formulas for cubic Hermite interpolation; use two pairs of very close points and replace some to the first differences by first derivatives. Using the divided difference formulas, attributed to Newton, to obtain error bounds for numerical quadrature rules. We also use a meanvalue theorem from calculus to estimate the integral of f(x)g(x) under the assumption that g(x) does not change sign in the interval of integration. Note that error bounds for numerical quadrature is also discussed, using different tools, in th text book.
  • 4/7 and 4/9: Computer arithmetic, in particular IEEE floating point arithmetic following the twenty-page handout.
  • 4/14 and 4/16: Final remarks about floating point computation. Chapter 11: linear and cubic splines, a basis of hat-functions for the linear splines. Error bounds for linear splines and Theorem 11.2. Derivation of natural cubic splines, which results in a positive definite, symmetric tridiagonal system of equations which can be solved in linear time.
  • 4/21 and 4/23: More about splines: they minimize a certain norm among all functions that satisfy the interpolation conditions. An alternative basis for cubic splines using B-splines. Inner products and in particular those that are defined using an intergral over a specific interval and a weight function which is positive in the interior of the interval. Systems of orthogonal polynomials in particular the Legendre and Chebyshev polynomials. A proof that all zeros of any orthogonal polynomial are real and lie in the interior of the interval of integration. Gaussian quadrature designed to integrate all polynomials of degree 2n+1 exactly using just n+1 quadrature nodes.
  • 4/28 and 4/30: A discussion of the last problem on the homework set on floating point. Why does it work so perfectly up to a point? Why does it fail so badly thereafter and why to we get NaN when we go even further? Chapter 8: min-max polynomials, yet another way of approximating continuous fuctions by polynomials. Weierstrass theorem which show that we can decrease the error towards zero by increasing the degree of the polynomial. The existence of the best approximation in the max-norm. A theorem due to De la Vallee Poussin and the Oscillation theorem. The best approximation of x^{n+1} by p_n where p_n is a polynomial of degree n; the error is a 2^{-n}T_n(x) a multiple of the n-th Chebyshev polynomial. A discussion of how close we can get by using polynomial interpolation and the Chebyshev points; a recall of what is in an earlier hand-out marked Chapter 15.
  • 5/5 and 5/7: Final remarks on the material of chapters 8. Review of basic results covered during the entire course.