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