Instructors

Lectures:

Labs:

Communication

, Jeramy Luo , Dylan Miller , jag@cs.ualberta.ca
Instructor hours: Directly after class Tue. TA hours: by appointment

Objectives

To obtain a working knowledge of how to apply numerical methods to real-world problems and a thorough understanding of the mathematics and properties of these methods.

Syllabus

Throughout the course examples of real world problems will be mathematically modeled and computationally solved.

Numerical Computing basics

Linear Equations Some real world applications and motivations, Systems of linear equations and LU factorization, Sensitivity and Conditioning, Overdetermined systems, Linear Least Squares, methods for QR factorisation, Linear Regression, Data Fitting and Interpolation, Eigenvalue Problems, methods for Eigen and SVD factorizations.

Nonlinear Equations and Optimization Basic 1D search methods with and without derivatives. Convergence rates and stopping criteria, Multidimensional root finding, Newton and Gauss-Newtons methods. Conditions for extrema, local and global min and max. Unconstrained optimization.

Numerical Quadrature (Integration) and Differentiation Numerical Quadrature, Numerical Differentiation, Richardson Extrapolation.

Numerical solution of Differential Equations Initial value problems, boundary value problems, partial differential equations.

Schedule

Grading

mymarks

See also CS department course policies We follow the cmput 201 collaboration policy in that document - essentially you can discuss problems orally or on the class forum, but not share solutions.

Literature

Michael T. Heath: Scientific Computing. An Introductory Survey, 2nd Ed, SIAM 2018
Heath provides a mathematically careful treatment of core topics.
(Optional) Cleve Moler Numerical Computing with MATLAB SIAM books 2004.
A more hands on introduction to numerical computing in Matlab

A message from the university administration:

The University of Alberta is committed to the highest standards of academic integrity and honesty. Students are expected to be familiar with these standards regarding academic honesty and to uphold the policies of the University in this respect. Students are particularly urged to familiarize themselves with the provisions of the Code of Student Behavior (online at www.ualberta.ca/secretariat/appeals.htm) and avoid any behavior which could potentially result in suspicions of cheating, plagiarism, misrepresentation of facts and/or participation in an offence. Academic dishonesty is a serious offence and can result in suspension or expulsion from the University. Policy can be found in §23.4(2) of the University Calendar.



Detailed topic listing:
-----------------------

Scientific computing in Matlab
  Evaluating expressions
  Using built-in functions
  Writing scripts and functions

Approximations in Scientific Computation
  Sources of Approximation
  Absolute Error and Relative Error
  Data Error and Computational Error
  Truncation Error and Rounding Error
  Sensitivity and Conditioning
  Stability and Accuracy 

Systems of Linear Equations

  Solving Linear Systems
    Problem Transformations
    Triangular Linear Systems
    Elementary Elimination Matrices
    LU Factorization
    Implementation of LU Factorization
    Complexity of Solving Linear Systems
  Existence and Uniqueness
  Sensitivity and Conditioning
    Vector Norms
    Matrix Norms
    Matrix Condition Number
    Error Bounds
    Residual 
   
Overdetermined Linear Systems
  Linear Least Squares Problems
    Existence and Uniqueness
    Normal Equations
    Normal Equations
    QR Factorization 
    Sensitivity and Conditioning

Interpolation and Approximation
  Existence, Uniqueness, and Conditioning
  Polynomial Interpolation
    Monomial Basis
    Interpolating Continuous Functions 
  Intro to splines

Eigenvalue Problems
  Eigenvalues and Eigenvectors
    Existence and Uniqueness
      Characteristic Polynomial
      Multiplicity and Diagonalizability
  Computing Eigenvalues and Eigenvectors
    Power Iteration
    Inverse Iteration
  SVD and Eigen values,vectors viewed as matrix factorizations.

Nonlinear Equations
    Existence and Uniqueness
    Sensitivity and Conditioning
    Convergence Rates and Stopping Criteria
    Nonlinear Equations in One Dimension
      Interval Bisection
      Fixed-Point Iteration
      Newton's Method
      Secant Method
    Systems of Nonlinear Equations
      Newton's Method
  
Optimization
  Optimization Problems
  Existence and Uniqueness
    Convexity
    Unconstrained Optimality Conditions
  Optimization in One Dimension
    Golden Section Search
    Newton's Method
  Multidimensional Unconstrained Optimization
    Direct Search
    Steepest Descent
    Newton's Method
  Nonlinear Least Squares
    Gauss-Newton Method
    Levenberg-Marquardt Method (Cursorly)
  
Numerical Integration and Differentiation
  Integration
    Existence, Uniqueness, and Conditioning
    Numerical Quadrature
      Newton-Cotes Quadrature
    Other Integration Problems
      Tabular Data
 
  Numerical Differentiation
    Finite Difference Approximations
    
Initial Value Problems (IVP) for Ordinary Differential Equations
  Ordinary Differential Equations (ODE)
  Existence, Uniqueness, and Conditioning
  Numerical Solution of ODEs
    Euler's Method

Boundary Value Problems (BVP) for ODE
  Shooting Method
  Finite Difference Method