Instructors

Lectures:

Labs:

, Nhat Nguyen , Sergey Khlynovskiy , Martin McLaren , Chen Jiang , Ilya Nalivaiko

Communication

Martin Jagersand 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