MATH-UA 252/MA-UY 4424 Numerical Analysis

Syllabus & Lecture Schedule

MATH-UA 252/MA-UY 4424

Numerical Analysis, Summer 2021

M T W Th: 11:10am–1:15pm

Instructor: Joseph Esposito

email: [email protected]

Description

This class covers classical topics in Numerical Analysis: The solution of linear and nonlinear equations, roundoff error, conditioning, least squares, numerical computation of eigenvalues, interpolation, function approximation, and quadrature. This course requires mathematical maturity and involves some advanced mathematical topics. While the course focuses on the analysis of numerical methods, there will be basic programming assignments in numerical software (typically in Matlab or Julia, but students are welcome to use Python/numpy) from the very start and throughout the course.

Prerequisites

MATH-UA 123 Calculus III or MATH-UA 213 Math for Economics III (for Economics majors) with grade C or better, and MATH-UA 140 Linear Algebra with a grade of B or better.

Topics

Basic programming in Matlab/Julia, nonlinear equations in one dimension (bisection, Newton), convergence, floating-point arithmetic and roundoff error, square systems of linear equations (LU/Cholesky factorizations, FLOP counts, conditioning), Newton method for nonlinear systems, linear least squares (linear regression, normal equations, QR factorization via Gram-Schmidt), eigenvalue decomposition (power method, inverse power method, Jacobi and/or QR method), singular value decomposition (conditioning, pseudoinverse, low-rank approximation), polynomial interpolation (Vandermonde system, Lagrange interpolant, (lack of) conver-gence, piecewise polynomial interpolation), function approximation (L2 approximation, orthogonal polynomials (Legendre, Chebyshev)), quadrature (trapezoidal, Simpsons, composite quadrature, Newton-Cotes, Gaussian quadrature).

Skills

Basic numerical programming. Understanding of convergence or algorithms and order of accuracy, conditioning, computational cost of algorithms, numerical linear algebra, polynomial approximation, numerical integration.

Materials

There is no required textbook for the course. However, we will be working with material from the following books.

• An Introduction to Numerical Analysis, Endre Suli and David Mayers, Cambridge University Press, 2003. Available in PDF format

• Numerical Methods: Design, Analysis, and Computer Implementation of Algorithms, Anne Greenbaum & Timothy P. Chartier, Princeton Press, 2012. Available in Electronic Format

• Numerical Analysis, Richard Burden, Douglas Faires, Annette Burden, Cengage, 2016. A bit expensive, but is a good mix of theory and applications.

• It is encouraged you use MatLab for the assignments. This can be obtained for free from NYU.

Structure

The course will consist of daily meetings M-Th. Lectures will be recorded and available for you to view. While you are not required to attend, there will be worksheets (not graded) done in class. These worksheets will help you cultivate a deeper understanding of the material and give you an opportunity to work with classmates. Lecture notes will be posted as well.

Homework

There will be weekly homework assignments due on Gradescope. No late homework will be accepted without prior approval with supporting documentation.

It is encouraged that you review the Acedemic Integrity Policy and note that:

• It is OK to discuss with other students the mathematical aspects, algorithmic strategy, code design, techniques for debugging, and compare results. You must however explicitly acknowledge any help that you receive from any source.

• Each student must write the solutions independently. Copying of any portion of someone else’s solution or allowing others to copy your solution is considered cheating.

• Code sharing is not allowed. You must type (or create from things you’ve typed using an editor, script, etc.) every character of code you use. There is no substitute for debugging your own code; looking at or copying someone else’s code is not the same.

Please see separate document posted on the submission of assignments.

Exams

There will be two exams. Details will be laid out in class.

• Midterm - July 22

• Final - August 12

Grading

• 40% Homework

• 25% Midterm

• 35% Final.

Disability Disclosure Statement

Academic accommodations are available for students with disabilities. The Moses Center website is www.nyu.edu/csd. Please contact the Moses Center for Students with Disabilities (212)-998-4980 or [email protected]) for fur-ther information. Students who are requesting academic accommodations are advised to reach out to the Moses Center as early as possible in the semester for assistance.

Lecture Schedule

Below is the tentative lecture schedule with the main topics listed for each week.

■ Week 1 ( 3 Meetings)

 Introduction to numerical analysis, basic Matlab for solving nonlinear equations in 1D, bisection.

 Convergence of nonlinear solvers in 1D, bisection, secant and Newton methods.

■ Week 2

 Roundoff error, floating-point numbers and arithmetic. Could do review of linear algebra.

 Linear systems: Gaussian elimination for LU, pivoting, computational complexity.

■ Week 3

 Linear systems: Matrix and vector norms, conditioning. Newton?s method for systems of nonlinear equations.

 Overdetermined linear systems and least squares fitting.

 Review, Midterm

■ Week 4

 Eigenvalues: (inverse) power method for dominant eigenvalues, and similarity- transform based meth-ods (Jacobi or QR method) for all eigenvalues.

 Singular value decomposition: conditioning, pseudo-inverse, low-rank approximation.

■ Week 5

 Polynomial interpolation: Vandermonde system for monomial basis, Lagrange interpolant, (lack of) convergence 

 Piecewise polynomial interpolation. L2 function approximation with monomial basis.

 Orthogonal polynomials: Legendre, Chebyshev via complex plane. Interpolation using Legendre or Chebyshev nodes.

■ Week 6

 Numerical quadrature: trapezoidal, Simpsons, composite quadrature, Newton-Cotes, Gaussian quadra-ture.

 Review

 Final exam