## 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.