Numerical Analysis

MATH-UA0252-1, Spring 2012,

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

Recitation sessions, Wednesdays, 8:00 - 9:15 am. WWH 201
Instructor: Kellen Petersen
Office hours: Thursdays 3:30 - 4:15 pm and Fridays 11:30 am - 12:15 pm.

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

  • Coordinates of Kellen Petersen
    Office: WWH 718
    Email: kellen at cims.nyu.edu

  • Announcements
    The first class was on Tuesday January 24. Spring recess is March 12-16. The last class is on Thursday May 3. The final will cover material from the entire semester.
    Quiz 1 with solutions.
    Quiz 2 with solutions.
    Quiz 3 with solutions.
    Quiz 4 with solutions.
    March 6 midterm with solutions.
    Your worst score of the four quizzes will be thrown out.
    Midterm from 3/3, 2010 with answers. You can bring one regular size paper covered on both sides with notes for your private use during the exam.
    The final is scheduled for May 10, 12 noon - 1:50pm in WWH 201. To the final you can bring two pages of notes. Here is a four page review outline prepared by Kellen Petersen, which covers almost all the topics of this course; see also Course content section of this homepage for further information.

  • Homework
    There will be regular homework assignments, including programming using Matlab or any reasonable alternative. Scores will be made available on Blackboard. 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 or Mr. Petersen or me, to get help when necessary. 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 January 29, due at noon Friday February 10.
  • Homework set 2 Assigned February 17, due at 12:30 pm, sharp, on Tuesday February 28.
  • Homework set 3 Assigned February 17, due at noon on Friday March 9.
  • Homework set 4 Assigned March 21, due at 12:30pm on Tuesday April 3.
  • Homework set 5 Assigned April 5, due at 12:30pm on Tuesday April 17.
  • Homework set 6 Assigned April 19, due at 12:30pm on Tuesday May 1

  • 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: Polynomial interpolation as in Chapter 6, sections 1-3. Newton's method (a downloadable pdf file) for computing interpolation polynomials.
  • Week 2: Hermite interpolation. Basic methods for numerical quadrature as in Chapter 7: the midpoint, trapezoidal, Simpson, and corrected trapezoidal rules. Error bounds. A first introduction to adaptive Simpson with a a paper handout.
  • Week 3: The basic idea behind Romberg integration; it requires subintervals of the same length. More on adaptive Simpson. Linear spaces and normed linear spaces. Best approximation in the maximum (infinity) norm of a continuous function by polynomials. De la Vallee Poussin's and the Oscillation theorems. Best approximation of x^{n+1} by polynomials of degree n. Chebyshev polynomials.
  • Week 4: An estimate of the polynomial interpolation error using the zeros of Chebyshev polynomials and why that choice works much better than when equidistant points are used; cf. the first home work problem set. Inner products and inner product spaces. Examples of inner product spaces. Orthogonality. The Cauchy-Schwarz inequality. How to generate sets of orthogonal polynomials. Three term recurrences. The roots of any orthogonal polynomial are simple and are all in the interval of integration, which defines the inner product.
  • Week 5: More on orthogonal polynomials. The classical families associated with Legendre, Jacobi, Chebyshev, Hermite, and Laguerre. Gaussian quadrature: select the roots of a certain orthogonal polynomial as the nodes for the Gaussian quadrature rules. Error bounds for Gaussian quadrature. A proof that the values obtained by Gaussian quadrature converges to the exact value of the integral when the number of points increases and the function is continuous; Weierstrass' theorem and the positivity of the quadrature weights feature prominently in that argument. Radau and Lobatto versions of Gaussian quadrature.
  • Week 6: Interpolation using piecewise linear and piecewise cubics. Cubic splines: Derivation of a linear system with a tridiagonal matrix which determines the values of the second derivatives of a cubic spline. From these values, the restriction of the cubic spline to any subinterval -- a cubic polynomial -- can be determined. How to solve the linear system using on the order of n operations. A characterization of linear and cubic splines as minima of certain integrals.
  • Week 7: Midterm exam. More about piecewise linear and piecewise cubic approximations, in particular. A short overview of what will be done during the rest of the semester.
  • Week 8: Solving one nonlinear equation of one variable. Bisection, Newton's algorithm, the secant and the Illinois algorithms. Fixed points. Rates of convergence of the Newton and secant algorithms. Relative errors and absolute errors. The relative error of function evaluations.
  • Week 9: Linear system of algebraic equations in R^n. Solvability, if and only if the columns of the matrix are linearly independent. Otherwise, we either have no solution of infinitely many. The geometry for n=2 and n=3; what matters is if the normals to the lines/planes are linearly independent. Why not to use determinants fo compute the solution of linear systems. Norms in R^n: ell_1, ell_\infinity, ell_2, and ell_p norms and proofs that the first three of them are indeed norms sine they satisfy the triangle inequality and the other two requirements. A few words on norms of matrices. Guest lecture on Gaussian elimination with and without pivoting.
  • Week 10: More about vector and matrix norms. Proofs of the triangle inequality for ell_1, ell_infinity, ell_2 and for all p such that 1 < p < infinity: Cauchy--Schwarz's, Young's, Hoelder's, Minkowski's inequalities. Matrix norms for products of matrices. Condition numbers for matrix--vector products and solutions of linear systems. Concurrency of LU factorization; only one loop is necessary. Linear least squares solutions of overdetermined systems.
  • Week 11: A twenty-page handout on floating point arithmetic. Linear least squares solution and their solution using QR factorizations. Householder transformations and the underlying geometry. Orthogonal matrices. How to choose one of the two possible Householder reflectors. Connection of the resulting factorization to the QR factorization discussed in chapter 2 of the text book. Strictly diagonally dominant matrices; they are invertible. Cholesky factorizations and positive definite symmetric matrices; this factorization can be used to decide if a symmetric matrix is positive definite.
  • Week 12: More on Cholesky's algorithm; there is a good bound on the elements of the triangular factors. An example where the elements of the upper triangular matrix in Gaussian elimination grows exponentially in spite of using partial pivoting. Comments on how large elements in the upper triangular matrix can impact the quality of the numerical result. How to represent integers using 2's complement. Fixed point systems, now abandonded. A Toy floating point system. The relative error in the representation. Machine epsilon and what can happen when we add three floating point numbers. The subnormal numbers. Single precision IEEE floating point. How to represent zero and infinity. NaN, not a number. Comments about the Fibonacci numbers and how they grow in preparation for one of the home work questions.
  • Week 13: Further discussion of the IEEE floating point number systems, in particular, of double precision. Review of the algebraic eigenvalue problem; definitions of eigenvalues and eigenvectors. What happens if we have multiple eigenvalues? Solving simple linear systems of ordinary differential equations by using eigenvalue decompositions. Similarity transformations. Symmetric and other normal matrices. Schur's normal form. Using Householder transformations to construct similarity transformations which give us Hessenberg matrices. The symmetric case which gives us symmetric tridiagonal matrices. The eigenvalues of a symmetric tridiagonal matrix are distinct if the elements next the the diagonal all differ from zero.
  • Week 14: Computing the values of the characteristic polynomials of a symmetric tridiagonal matrix and all its leading principal minors. The sign of these values can be used to determine the number of eigenvalues that are larger than the parameter used in the computation. Why we should not compute the eigenvalue of matrices by using the characteristic polynomial; its roots can be very sensitive to small perturbations of its coefficients. An introduction of Jacobi's method for computing eigenvalues of symmetric matrices. Gershgorin's theorem which makes it possible to estimate the effect of small off-diagonal matrix elements on the eigenvalues of matrices.

  • Introductions to MATLAB. (Suggestions are welcome.)
  • Cambridge University Engineering Department -"Getting Started" and Example PDFs.
  • The official Matlab page - detailed with a lot of information.
  • Or from the same outfit
  • Wikipedia thread for Matlab - easy read, simple programs that are easy to comprehend