Introduction to Numerical Methods - APMA 4300 - Syllabus and Course Information

Purpose

Welcome to your first course in numerical methods (maybe). Numerical methods and computational science and engineering have often been said to comprise the "third" pillar of science if that gives you a scope for its applicability, so that's exciting. We will cover a wide variety of topics to give you at least a taste as to the wide variety of uses these methods can have, exploring a large variety of these applications while studying each of the different topics.

Goals and Scope

Our goal in this course is that you will be able to

1. Understand the numerical algorithms and related mathematical concepts presented including ideas like complexity, stability, and convergence for each,
2. Select an appropriate method for a given problem,
3. Implement the selected numerical algorithm, and
4. Test and debug the numerical implementation.

In order to accomplish this we will use a variety of learning approaches that may be different from what you are used to:

• This course will be partially "flipped", i.e. you will be expected to watch course lectures outside of class time and class time instead will be devoted to working on guided group work and programming as this is the "real" way to learn the material. This is a bit of an experiment but wider experience has suggested this is the most effective way to learn this material.

• Peer-review of homework will be part of your grade. This will be randomly assigned and will based on simple completion of the review which will be handed back to the writer of the code. This will hopefully enable you to get a broader idea of how others approached the problem, improve your ability to read others code (a key component to any job where you might be working on numerical related problems), and hopefully improve your success at writing readable, maintainable, and clear code.

• This course will be taught via IPython/Jupyter notebooks. This will include the course notes (in lieu of a text-book), homework assignments, and various other notes.

Pre-requisites

The following subjects will be used extensively so it is best that you have had at least one course in each of the following:

• classes in calculus and vector calculus in particular,
• a class on linear algebra,
• a class on solving ordinary differential equations, and
• programming experience at the level of COMS 100x (introduction to computer science and programming)

Textbook(s)

• Required: None!
• Possible useful references - Note that these are in no way required!
  • Numerical Analysis, 2nd edition, W. Gautschi
  • Numerical recipes
  • A Primer on Scientifc Programming with Python by H. P. Langtangen.
  • Python scripting for computational science by H. P. Langtangen.
  • Numerical Linear Algebra by L.N. Trefethen and D. Bau, and
  • Numerical Methods: Design, analysis and computer implementation of algorithms, A. Greenbaum and T. P. Chartier. This text is on reserve at the library.

General Topic Coverage

1. Introduction and Motivation: Modeling and methods for scientific computing
2. Overview of basic toolkit for computational science in Python
   • NumPy and SciPy
   • How to write the code
     • IPython/Jupyter notebooks
     • Spyder, canopy, wakari, sage-math-cloud
     • Text editors
   • Basic tools and best practices, version control (git) and code hosting (bitbucket/github)
   • Best practices for writing code and how to peer review code
3. Sources of error
   • Floating point vs. truncation error
   • Definition of errors - absolute, relative and precision
   • Other sources of error - model error and uncertainty
4. Root finding and optimization
   • Fixed point iteration
   • Basic algorithms: bracketing and bisection, Newton, secant, inverse interpolation
   • Combined methods: Brent's method
   • Optimization of 1-D functions: Basic algorithms, golden section search, Newton's method, parabolic interpolation
5. Interpolation and approximation
   • Polynomial interpolation, Lagrange and monomial basis
   • Pitfalls of large order - Chebyshev polynomials
   • Piecewise polynomial interpolation - $C^0$, $C^1$, $C^2$
   • SciPy interpolation routines
   • Data approximation by linear least squares
6. Numerical differentiation and integration (quadrature)
   • Numerical differentiation
     • Basic finite difference methods
     • Method of undetermined coefficients
     • Higher order spectral (Chepyshev) methods
   • Numerical quadrature
     • Newton-Cotes and error estimates: Mid-point, trapezoidal, and Simpson's
     • Arbitrary order and method of undetermined coefficients
     • Gauss quadrature
     • Extended Newton-Cotes
     • Adaptive quadrature
7. Numerical solution of ODE's - Initial value problems (IVP)
   • Motivation
   • Application of quadrature: Single step schemes - Euler, midpoint, Runge-Kutta 4 and errors
   • Error control and adaptive stepping
   • Systems of ODE's
   • Stiff systems: example and symptoms
   • Implicit methods: backwards Euler, backwards difference schemese (BDF) schemes
8. Solving non-linear systems of equations
   • N-Dimensional Taylor's theorem and Newton's method
   • Packages and libraries (fsolve, PETSc)
9. Numerical linear algebra part 1: Direct methods, LU, QR, and least-squares
   • Motivation: $A x = b$ is everywhere
   • Existance, uniqueness and condition number: vector and matrix norms
   • Direct methods: Gaussian elimination and the LU decomposition with partial pivoting
   • Special matrices: symmetric, tridiagonal, sparse matrices
   • Lease-squares and QR
   • Orthogonalization: Graham-Schmidt, Householder, Givens transformations
10. Numerical linear algebra part 2 - Methods for Eigenproblems
    • Motivation, $A x = \lambda x$
    • Basic algorithms - power method, inverse power method, shifts
    • Advanced algorithms - an introduction (a.k.a. what is often used)
11. Solution of ODEs part 2 - two-point boundary value problems (BVP) and a small taste of PDEs
    • Motivation - numerical PDEs and discrete vs. continuous approximations
    • Two-point BVPs - Shooting and finite difference methods

Schedule

Course Grading

• Homework (60%)
  • Written exercises graded by T.A.s
  • Coding exercises graded for correctness and peer reviewed - Note that every coding assigment will be run through an anti-plaigerism database
  • Peer-review
    • Participation based (just do it)
    • Only applied to the homeworks and will be anonymous and randomly selected
• Exams (40%), midterm and final equally weighted
  • Half of each exam will be an in-class written exam evaluating theory based knowledge
  • Other half will be a take-home coding based exam

Contact Info