## Numerical Computing

###
V22.0421

Spring 2004, Tuesdays and Thursdays, 11:00am - 12:15 pm. WWH 101

Instructor: Olof
B. Widlund

** Coordinates **

Office: WWH 712

Telephone: 998-3110

Office Hours: Tuesdays 12:30 - 1:30 pm or drop by any time,
or send email or call for an appointment.

Email: widlund@cs.nyu.edu

** MATLAB **

Try out
A Free Matlab Online Tutorial or look for others by a web
search.

An outdated but still very useful Introductory Matlab Primer (3rd edition,
in pdf format).

** Homework **

There will be regular homework assignments, including programming
using Matlab or any reasonable alternative.
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 when you get stuck,
I encourage you to consult with other students
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. If you put your homework in my mailbox, it is at
your own risk.

** Homework Assignments **
Homework 1 Assigned February 2, due, with
full credit, February 13 at midnight.
Note on Exercise 1.4

Homework 2 Assigned February 18, due with
full credit, March 2 at 11:00 am.

Homework 3 Assigned March 9, due with
full credit, March 30 at 11:00 am.

Homework 4 Assigned April 3, due with
full credit, April 15 at 11:00 am.

Homework 5 Assigned April 7, due with
full credit, April 27 at 11:00 am.

** Handouts; if you miss some, send e-mail request. **

Chapter 6: Linear system: pp. 194-197 and pp. 208-211.
The Error of Interpolating Polynomials: pp. 50-53.
Piecewise-Polynomial Approximation: pp. 284-291.
Differentiation and Intergration: pp. 294-309 and pp. 328-331.
The solution of nonlinear equations: pp. 72-81, pp. 88-93, and pp.100-109.
Vector and matrix norms: pp. 170-173.

** Lectures **
January 20. General comments about numerical computing and
it role in some other areas of computer science such as graphics,
geometric modeling, etc. Gaussian elimination. Partial pivoting
and how to tell if a matrix is nonsingular. An example with
thee-decimal-digit arithmetic which leads to failure without
partial pivoting.
January 22. Gaussian elimination in terms of elementary row
operations and factorization of the coefficient matrix as a product
of a unit lower triangular matrix and an upper triangular matrix.
Permutation of the rows in between the basic steps of the algorithm.
Introduction to IEEE Floating Point Systems.
January 27. More about IEEE Floating Point. Symmetric positive
definite matrices. Cholesky's algorithm.
January 29. Demonstration of MATLAB. Computing Fibonacci numbers
and learning
something about floating point computations from the success
and failure in recovering the Fibonacci sequence by running the
recursion backwards. Three vector norms and their associated matrix norms.
If you did not get the handout about norms, send an e-mail
message.

Slides on Floating Point Systems (pdf file).

Second set of slides on Floating Point Systems (pdf file).

February 3, 5, 10, and 12. Exercise 1.3 which shows that diagonal
dominance is inherited by the matrix that remains to be factored after
one step of Gaussian elimination. The same result for Cholesky's algorithm
for symmetric, positive definite matrices; cf. the proof of Theorem 1.10.
The sensitivity of the solution of
linear systems of equations. Bounds on the relative error in terms of
the condition number of the matrix and the relative perturbation of
the right hand side and the matrix. Geometric meaning of ill-conditioning
of linear systems; cf. Figures 2.2 and 2.3. Avoiding subtraction of nearly
equal numbers: quadratic equation solving and the use of power series.
The use of multivariable calculus and vector and matrix norms
to derive formula (2.1).
Introduction to forward and backward error
analysis. Backward stability of triangular linear system solving. The
more modest results on LU factorizations of matrices.
Introduction to linear least squares
problems. The normal equations. Risk of loss of information if normal
equations are formed. The alternative given by QR factorization of
matrices. Solving least squares problems once the QR factorization
is known.
February 17. Givens and Householder transformations to compute QR
factorizations of matrices.
February 19. Sections 3.1.3 and 3.1.4: What can be said about the
condition of least squares problems? What do these bounds mean when we select
an algorithm? The problem with using the normal equations; we will have to
give up accuracy in many cases.
Setting up least squares problem for fitting polynomials
of degree higher than one; see Example 3.1 for the case of linear functions.
February 24. Comments on some aspects of Homework set 2. Topics from
chapter 7: Unique solvability of the classical polynomial interpolation
problem. Vandermonde matrices. Lagrange polynomials to provide the solution
of the problem. Lemma 7.4 on the recursive computation of the interpolating
polynomials; Neville's scheme. Lemma 7.11 in the special case when the
interpolation points are distinct.
February 26. Verification that Newton's scheme to compute interpolating
polynomials is correct. Review of the definition of the recursive definition
of divided differences. Comments on homework. Handout and discussion
illustrating
the use of matrix operations in matlab to eliminate ``for'' loops. Solving
triangular systems by rows and by columns.
March 2. Hermite cubic interpolation. Existence by an explicit
construction. Uniqueness by a linear algebra argument. Construction of
Hermite interpolating polynomials by Newton's method. Review of Taylor's
formula. Error bounds for the Lagrange interpolation as in a hand-out.
March 4. Midterm exam.
March 9. Discussion of homework problem 2.6 and of four of five
midterm questions.
March 11. Discussion of the remaining midterm question. Interpolation
by polynomials, piecewise cubic Hermite polynomials, and cubic splines.
(Handout about cubic Hermite polynomials and cubic splines.)
March 23. The dimension of the space of cubic splines. Derivation
of the tridiagonal linear system of equations which determines the
value of the first derivative of the spline interpolant at the interior
nodes. Different ways of selecting the additional two conditions. How
to make certain tridiagonal matrices symmetric. How to compute approximations
of first derivatives by using difference quotients and the effect of round off.
(Handout about numerical differentiation and numerical intergration including
adaptive numerical quadrature.)
March 25. Experiments with two formulas used for numerical differentiation.
Deriving numerical quadrature formulas by using interpolating polynomials
of different degrees. Error bounds for numerical quadrature formulas using
the standard error bound for polynomial interpolation.
March 30. Simpson's rule and the trapezoidal rule with end point
corrections. How to determine the coefficients of a quadrature formula
from the requirements that it should integrate a certain class of polynomials
exactly. Composite integration. Adaptive Simpson quadrature.
April 1. Section 7.1.4 of the text book. Chebyshev polynomials and
their role in selecting good interpolation points for polynomial interpolation;
cf. Theorem 7.16. Theorem 7.19 which shows that the roots of the Chebyshev
polynomials provide the best selection. A few words on trigonometric
interpolation; cf. Section 7.2 of the text book.
April 6. Interpolation with trigonometric polynomials. Unique solvability
follows from theory for polynomial interpolation or, alternatively from the
invertibility of the Vandermonde matrix. Fast computation of the trigonometric
interpolant on equidistant points by the fast Fourier Transform. Fast
computation of the coefficients by the same algorithm. Reference is pp. 197-203
of the text book.
April 8. Solving one nonlinear equation by bisection, Newton's method,
the secant method and regula falsi. Newton's method for systems of nonlinear
equations.
April 13. Second midterm.
April 15. More about the convergence of iterative methods for nonlinear
equations. Quadratic convergence of Newton's method and the almost quadratic
convergence of the secant method. Problems 4 and 5 of the second midterm.
April 20. Problems 1, 2, and 3 of the second midterm. Solving large
systems of linear algebraic equations with the Jacobi and Gauss-Seidel algorithms.
The use of eigenvalues and eigenvectors to estimate the rate of convergence
of such iterative methods. The convergence of Jacobi's method for diagonally
dominant matrices. See Section 8.1 of the text book.
April 22. Convergence of Gauss-Seidel's method for positive definite,
symmetric matrices. Approximation of Laplace's equations by finite differences.
Solvability of the resulting linear system.
April 27. Review of positive definite symmetric matrices: a symmetric
matrix is positive definite if Cholesky succeeds. Eigenvalues are real and positive.
Basic result on Gauss elimination. Why is Cholesky stable? Householder transformations.
Orthogonal matrices and their use in least squares problems. The use of Chebyshev
polynomials to accelerate the convergence of a basic iterative method for large
linear systems.
April 29. The Chebyshev and conjugate gradient methods for solving
large linear systems of algebraic equations with positive definite symmetric
coefficient matrices. Bounds in terms of the condition number of the matrices;
cf. sections 8.2 and 8.3 in the textbook. Practical aspects: the matrix needs
only be available in terms of a matrix-vector multiplication; there are short
term recurrence relations which makes it possible to save just a few vectors
throughout the iteration.

** Required Text **

Numerical Analysis in Modern Scientific Computing; An introduction
by Peter Deuflhard and Andreas Hohmann, Second Edition, Springer 2003.

** Announcements **

Class attendance is required .
Attendance will be taken occasionally.
If you must miss class, you must email me in advance with an
explanation. Thanks.

The first midterm was given on Thursday March 4.
Old midterm from 2001 (pdf file).

March 4, 2004 midterm (pdf file).

A second midterm was be given on April 13.
April 13, 2004 midterm (pdf file).
The midterm grade will be the
maximum score of the two exams. The second midterm covered
topics beginning with polynomial interpolation, i.e.,
the topics covered on February 24 and up to and including the fast Fourier
transform, i.e., topics covered on and before April 6.

Midterm grades were due in the department on Friday
March 12.

Spring break this year was March 15 -20.

March 29 was the last day for undergraduates to withdraw with a ``W''.
All students remaining will receive a grade.

The last class will be on April 29.

The final will be on
Thursday May 6, 10:00-11:50am in WWH 101. It will cover topics from the
entire semester.
Closed book, but you may bring one sheet of paper with your own notes.

Graded homework can be picked up in my office
now through 6:00 pm on Saturday May 1. Thereafter, look for instructions
on my office door.