Instructors

Lectures: Martin Jagersand
Labs and Seminars: Daniel Laplante, Alex Ayoub, Steven Lu

Objectives

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

Schedule

Lectures: Tuesday, Thursday 11:00 - 12:20, CSC B10


Staffed labs Tuesday 8-10:50 CSC 1-59 (Workstations), Tue 5-7:50 (Your laptop)

Grading

Written in-class exams:

Exam 1 (20%) Midterm Dates, see "calendar" link
Exam 2 (20%) Final

20% Written assignments throughout the term (5% each, see detailed calendar link)
20% Lab assignments throughout the term. (4-6% each, see calendar link)
20% Project, see web link on left for suggested topics and how to get started.

Literature

• Michael T. Heath: Scientific Computing. An Introductory Survey, 2nd Ed McGraw Hill 2002

  Heath provides a mathematically careful treatment of core topics.

• (Optional) Cleve Moler Numerical Computing with MATLAB SIAM books 2004.

  A hands on tutorial on numerical computing in Matlab

Communication

Course web page: http://www.cs.ualberta.ca/~jag/courses/num/
Hours: Meetings directly after class Tue,

Short Syllabus

Numerical Computing basics Numerical representations, Computational accuracy and stability, software and hardware for numerical computing.

Linear Equations Some real world applications and motivations, Gauss and Gauss-Jordan Elimination, LU factorization, Sensitivity and Conditioning, Overdetermined systems and Linear Least Squares, Linear Regression, Data Fitting and Interpolation, Eigenvalue Problems.

Nonlinear Equations and Optimization Basic 1D search methods with and without derivatives. Convergence rates and stopping criteria, Multidimensional root finding. Conditions for extrema, local and global min and max. Unconstrained optimization. Constrained optimization, Comparison of root finding and optimization, Trust region methods, Homotopy methods and Embeddings.

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

Selected CS topics and Applications: Fast Fourier Transform and Dynamic Programming, Strassens algorithm, SwEng for numerical computing, Writing Vectorized code, Revisit of problem and algorithm sensitivity and stability.

Detailed Syllabus

Approximations in Scientific Computation
  Sources of Approximation
  Absolute Error and Relative Error
  Data Error and Computational Error
  Truncation Error and Rounding Error
  Forward and Backward 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 
  Solving Modified Problems
  Improving Accuracy 
  Special Types of Linear Systems
    Symmetric Positive Definite Systems
    Banded Systems 
    Iterative Methods for Linear Systems
    
Overdetermined Linear Systems
  Linear Least Squares Problems
    Existence and Uniqueness
    Normal Equations
    Orthogonality and Orthogonal Projectors 
  Sensitivity and Conditioning
  Problem Transformations
    Normal Equations
    Augmented System Method
    Orthogonal Transformations
    Triangular Least Squares Problems
    QR Factorization 
  Orthogonalization Methods (Overview coverage only)
    Householder Transformations
    Givens Rotations
    Gram-Schmidt Orthogonalization
  Singular Value Decomposition
    Other Applications of SVD 
  Comparison of Methods

Interpolation and Approximation
  Existence, Uniqueness, and Conditioning
  Polynomial Interpolation
    Monomial Basis
    Lagrange Interpolation
    Newton Interpolation
    Orthogonal Polynomials (Cursorly)
    Interpolating Continuous Functions 
  Piecewise Polynomial Interpolation
    Hermite Cubic Interpolation
    Cubic Spline Interpolation
    B-splines 

Eigenvalue Problems
  Eigenvalues and Eigenvectors
    Existence and Uniqueness
      Characteristic Polynomial
      Multiplicity and Diagonalizability
      Eigenspaces and Invariant Subspaces
      Properties of Matrices and Eigenvalue Problems
      Localizing Eigenvalues 
  Sensitivity and Conditioning
    Problem Transformations
    Diagonal, Triangular, and Block Triangular Forms 
  Computing Eigenvalues and Eigenvectors
    Power Iteration
    Inverse Iteration
    Deflation
    Simultaneous Iteration
    QR Iteration
    Jacobi Method
    Comparison of Methods 
    Generalized Eigenvalue Problems
  Computing the Singular Value Decomposition

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
      Safeguarded Methods      
    Systems of Nonlinear Equations
      Fixed-Point Iteration
      Newton's Method
      Secant Updating Methods
      Robust Newton-Like Methods 

Optimization
  Optimization Problems
  Existence and Uniqueness
    Convexity
    Unconstrained Optimality Conditions
    Constrained Optimality Conditions 
  Sensitivity and Conditioning
  Optimization in One Dimension
    Golden Section Search
    Newton's Method
    Safeguarded Methods 
  Multidimensional Unconstrained Optimization
    Direct Search
    Steepest Descent
    Newton's Method
    Quasi-Newton Methods
    Secant Updating Methods
    Conjugate Gradient Method
    Truncated or Inexact Newton Methods 
  Nonlinear Least Squares
    Gauss-Newton Method
    Levenberg-Marquardt Method 
  
Numerical Integration and Differentiation
  Integration
    Existence, Uniqueness, and Conditioning
    Numerical Quadrature
      Newton-Cotes Quadrature
      Gaussian Quadrature
      Composite Quadrature
      Adaptive Quadrature 
    Other Integration Problems
      Tabular Data
      Romberg Integration
      Double Integrals
      Multiple Integrals  
    Transforming Integrals
      Improper Integrals
    Integral Equations

  Numerical Differentiation
    Finite Difference Approximations
    Automatic Differentiation 
    Richardson Extrapolation

A message from the university administration: