Georg Stadler

Courant Institute of Mathematical Sciences

New York University

Fall 17: Numerical Methods I @ NYU Courant

Instructor and organization:

Georg Stadler, Warner Weaver Hall Office #1111

Course numbers: MATH-GA 2010.001/CSCI-GA 2420.001

Lectures: Thursday 5:10-7:00pm; If you are interested in the class and are not registed, please email me.

Location: Warren Weaver Hall #101

Office Hours: To be announded or by appointment-please send an email.

If you email me about the class, please add [num1] in your subject line, or use this link.

We will use Piazza for as email list and discussion forum for this class. If you are registered for this class you will receive an invitation to join the course on Piazza at the beginning of the semester. Otherwise please email me and I will add you.

Literature

Note that all Springer books are available from NYU’s campus and you can order a MyCopy softcover print for 25$.

Deuflhard, P. & Hohmann, A. (2003). Numerical Analysis in Modern Scientific Computing. Texts in Applied Mathematiks [Series, Bk. 43]. New York, NY: Springer-Verlag.

Further Reading (available on reserve at the Courant Library.):

Quarteroni, A., Sacco, R., & Saleri, F. (2006). Numerical Mathematics (2nd ed.) Texts in Applied Mathematics [Series, Bk. 37]. New York, NY: Springer-Verlag.

Bau III, D., & Trefethen, L.N. (1997). Numerical Linear Algebra. Philadelphia, PA: Society for Industrial & Applied Mathematics.

M. Overton (2004): Numerical Computing with IEEE Floating Point Arithmetic, SIAM.

If you need to brush up your MATLAB:

Gander, W., Gander, M.J., & Kwok, F. (2014). Scientific Computing - An Introduction Using Maple and MATLAB. Texts in Computation Science and Engineering [Series, Vol. 11]. New York, NY: Springer-Verlag.

Moler, C: (2004) Numerical Computing with Matlab, SIAM.


Class list

1) Sep 7: Organization; Overview of research on numerical methods at CIMS; Motivational examples; Conditioning of problems; Sources of errors; Intro slides, iPad notes on conditioning

2) Sep 14: Stability of algorithms, measure of convergence speed; Computer representation of numbers; Slides, iPad notes on floating point representation

3) Sep 21: Solving linear systems; forward/backward substitution, LU decomposition, Choleski, solver libraries in Matlab; Slides.

4) Sep 28: Data fitting and linear least squares problems, normal equations, QR factorization. Slides. Reading: Deuflhard/Hohmann, Sec 3.1

5) Oct 5: Givens and Householder (D/H, Sec 3.2); Solution of nonlinear equations (D/H, Sec 4.1-4.2): Fixed points and Newton’s method for system of equations Slides; Fixed point MATLAB example file from class.

6) Oct 12: Convergence and examples of Newton’s methods, Nonlinear least squares (D/H, Sec 4.3). Slides; MATLAB example file for Newton method in 2D from class.

7) Oct 19: Data fitting with different objectives; Nonlinear optimization, optimality conditions, convexity, descent methods. Slides;

8) Oct 26: Newton method in optimization, linesearch, convergence of descent methods. Introduction to eigenvalues. For slides see link from previous class. Summary of quadratic forms and convergence of steepest descent method. Descent with line search Matlab file.

9) Nov 2: Eigenvalues and eigenvectors, power method and variants, QR algorithm. Slides

10) Nov 9: SVD, orthongonal polynomials. Slides

11) Nov 16: Polynomial bases, interpolation, divided differences, convergence. Slides

12) Nov 30: Trigonometric interpolation, Quadrature. Slides on interpolation, and Slides on quadrature

13) Dec 7: Quadrature, Solution of large linear systems, Jacobi, Gauss-Seidel. Updated quadrature slides see above. Slides on iterative solvers

14) Dec 14: Solution of large linear systems; Relaxation of stationary iterative solvers, matrix-free methods, conjugate gradients. See (updated) slides from previous lecture.

15) Dec 21: Class final


Homework assignments

*) Homework #1 (as PDF); You can also get the TEX file to use as starting point if you want to type your solutions in LaTeX.

*) Homework #2 (as PDF) and the LaTeX file.

*) Homework #3 (as PDF) and the LaTeX file.

*) Homework #4 (as PDF) and the LaTeX file.

*) Homework #5 (as PDF) and the LaTeX file.

*) Homework #6 (as PDF) and the LaTeX file.

*) Homework #7 (as PDF) and the LaTeX file.


FAQs:

1) I am a master student and am undecided if I should take your class or the one-term Scientific Computing class. What’s the difference? In Numerical Methods I and II, more mathematical details are presented as they are mainly intended for PhD students. The Scientific Computing class covers most parts of Numerical Methods I and some parts of Numerical Methods II. If you do not intend to take the second part of Numerical Methods I, it makes more sense to take Scientific Computing instead.

2) Can you give a rough outline of the content for Numerical Methods I and II? The first part focuses on many aspects of numerical mathematics (sources of errors, solution of linear and nonlinear systems, least-squares problems, interpolation and quadrature) but does not include the numerical solution of differential equations (ODEs and PDEs), which is the main topic of part II in the spring semester.

3) Can I use Octave/Python instead of Matlab? Sure.

4) What is the work load in this class? There will be a long-ish homework assignment every two weeks, which involves a mix of theoretical and numerical and programming exercises. These will expose you to the material covered in class and I consider them critical to understanding the methods and algorithms we discuss in class.

5) Will there be exams? There will be a final that will count for about 50% of our grade. The homeworks you hand in amount to the remaining 50% of our grade.

6) I don’t have any programming experience in Matlab/Python. Can I take your class? I will discuss coding aspects, but this is not a programming class. You are expected to have basic Matlab/Python knowledge by the beginning of the class. If you are not sure about your background, go through the first chapters of the above recommended Matlab books (e.g., C. Moler’s book), and talk to me. About half of the homework assignments will require basic Matlab/Python plotting, computing or scripting. This is an important part of the class.

7) Do I need to know a compiled language (C,C++,Fortran) for your class? No. However, I will encourage you to experiment with compiled languages, most likely through a few (simple) extra credit homework problems.

8) Can we collaborate for the homework assignments? You are welcome to discuss problems and talk to your colleagues, but you must write every line of code and of your homework solutions yourself. See also NYU’s policy on Academic Integrity.

9) How can I get access to Matlab? CIMS has computer rooms you can use. You can also purchase a student license for Matlab from the computer store. There are also free alternatives to Matlab, e.g., Octave or Python.


© G.St.