Numerical Analysis (CS 450) Spring 2023
| What | Where |
|---|---|
| Time/place | Tue/Thu 11:00am--12:15pm [1404 Siebel Center] |
| Class URL | https://relate.cs.illinois.edu/cs450-s23 |
| Class recordings | https://mediaspace.illinois.edu/channel/channelid/282630042 |
| Web forum | https://campuswire.com/p/GB648CA0C (see lecture 1 recording or email instructor for join code) |
Quizzes
Due at the start of each lecture (latest 5 posted here), posted by 5 pm day of prior lecture.
Quiz 20: Composite Quadrature and Numerical Differentiation »
Quiz 21: Characterization of ODEs and Euler Methods »
Quiz 22: Initial Value Problems for Ordinary Differential Equations »
Quiz 23: Methods for Ordinary Differential Equation BVPs »
Quiz 24: BVPs and Classification of PDEs »
Homework
Homework 5 (Extra Credit for both sections, 1/3 value of main part of regular homework) »
4-Credit Hour Homeworks
For the 4-credit hour section, addendum problems are worth 1/4 of the total credit for each assignment. For the 3-credit hour section, these problems may be completed for extra credit, with half of the value (1/6 of the assignment value).
4-Credit Hour Addendum to Homework 1 »
4-Credit Hour Addendum to Homework 2 »
4-Credit Hour Addendum to Homework 3 »
4-Credit Hour Addendum to Homework 4 »
Course Outline
-
Chapter 1: Scientific Computing
- Notes (Michael T. Heath)
- Lecture Notes
- In-class Activity: Cancellation in Standard Deviation Computation
- Quiz 1: Policies
- Quiz 2: Error, Conditioning, and Floating Point
- Quiz 3: Floating Point Arithmetic, and Vector Norms
- Demo: Catastrophic Cancellation
- Demo: Conditioning of Evaluating tan
- Demo: Density of Floating Point Numbers
- Demo: Floating Point and the Series for the Exponential Function
- Demo: Floating Point vs Program Logic
- Demo: Floating point and the Harmonic Series
- Demo: Picking apart a floating point number
- Demo: Polynomial Evaluation Floating Point
- Demo: Truncation vs Rounding
- Demo: Vector Norms
-
Chapter 2: Systems of Linear Equations
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 4: Matrix Norms, Condition Number and, Conditioning of Linear Systems
- Quiz 5: Solving Linear Systems
- Quiz 6: LU decomposition and Partial Pivoting
- In-class Activity: Singular Value Decomposition and Norms
- In-class Activity: Forward Substitution
- In-class Activity: Sherman-Morrison-Woodbury Formula
- Demo: Coding back-substitution
- Demo: Complexity of Mat-Mat multiplication and LU
- Demo: Condition number visualized
- Demo: Conditioning of 2x2 Matrices
- Demo: Elimination Matrices I
- Demo: Elimination Matrices II
- Demo: LU factorization
- Demo: LU with Partial Pivoting
- Demo: Matrix norms
- Demo: Sherman-Morrison
- Demo: Vanilla Gaussian Elimination
-
Chapter 3: Linear Least Squares
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 7: Solving Linear Least Squares Problems
- Quiz 8: QR Factorization
- Quiz 9: Givens QR and Rank-Deficient Least-Squares
- In-class Activity: Solving the Normal Equations using a Singular Value Decomposition
- In-class Activity: Householder QR
- Demo: 3x3 Givens demo
- Demo: 3x3 Householder demo
- Demo: Gram-Schmidt and Modified Gram-Schmidt
- Demo: Gram-Schmidt--The Movie
- Demo: Image compression
- Demo: Interactive Polynomial Fit
- Demo: Issues with the normal equations
- Demo: Keeping track of coefficients in Gram-Schmidt
- Demo: Normal equations vs Pseudoinverse
- Demo: Polynomial fitting with the normal equations
- Demo: Relative cost of matrix factorizations
-
Chapter 4: Eigenvalue Problems
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 10: Eigenvalues, Conditioning, and Power Iteration
- Quiz 11: Eigenvalue Problems and Iterative Algorithms
- Quiz 12: Computing Many Eigenpairs at Once
- In-class Activity: Calculating Eigenpairs from a Schur Form
- In-class Activity: Rayleigh Quotient Iteration
- In-class Activity: Computing the Maximum Ritz Value
- Demo: Arnoldi Iteration with Complex Eigenvalues
- Demo: Arnoldi Iteration
- Demo: Arnoldi vs Power Iteration
- Demo: Exploring the Numerical Range
- Demo: Householder Similarity Transforms
- Demo: Orthogonal Iteration
- Demo: Power iteration and its Variants
- Demo: Rounding in characteristic polynomial using SymPy
-
Chapter 5: Nonlinear Equations
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 13: Nonlinear Equations
- Quiz 14: Solving Nonlinear Equations
- In-class Activity: Newton's Method for 2-by-2 System of Equations
- In-class Activity: Inverse Quadratic Interpolation
- Demo: Bisection Method
- Demo: Convergence of Newton's Method
- Demo: Convergence of the Secant Method
- Demo: Fixed point iteration
- Demo: Newton's Method
- Demo: Newton's method in n dimensions
- Demo: Rates of Convergence
- Demo: Secant Method
- Demo: Three quadratic functions
-
Chapter 6: Optimization
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 15: Nonlinear Optimization
- Quiz 16: Optimization Methods
- Quiz 17: Constrained Optimization and Interpolation
- In-class Activity: Golden Section Search
- In-class Activity: Gauss-Newton Method
- Demo: Conjugate Gradient Method
- Demo: Conjugate Gradient Parallel Tangents as Krylov Subspace Method
- Demo: Gauss-Newton
- Demo: Golden Section Proportions
- Demo: Nelder-Mead Method
- Demo: Newton's Method in 1D
- Demo: Newton's Method in n dimensions
- Demo: Sequential Quadratic Programming
- Demo: Steepest Descent
-
Chapter 7: Interpolation
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 18: Interpolation
- In-class Activity: Interpolation in Monomial Basis
- In-class Activity: Chebyshev Interpolation
- Demo: Chebyshev interpolation
- Demo: Choice of Nodes for Polynomial Interpolation
- Demo: Composite Gauss Interpolation Error
- Demo: Interpolation Error
- Demo: Interpolation with Radial Basis Functions
- Demo: Jump with Chebyshev Nodes
- Demo: Monomial interpolation
- Demo: Orthogonal Polynomials
-
Chapter 8: Numerical Integration and Differentiation
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 19: Quadrature
- Quiz 20: Composite Quadrature and Numerical Differentiation
- In-class Activity: Quadrature Rule with an Arbitrary Polynomial Basis
- In-class Activity: Richardson Extrapolation
- Demo: Accuracy of Newton-Cotes
- Demo: Finite Differences vs Noise
- Demo: Floating point vs Finite Differences
- Demo: Gaussian quadrature weight finder
- Demo: Newton-Cotes weight finder
- Demo: Richardson with Finite Differences
- Demo: Taking Derivatives with Vandermonde Matrices
-
Chapter 9: Initial Value Problems for ODEs
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 21: Characterization of ODEs and Euler Methods
- Quiz 22: Initial Value Problems for Ordinary Differential Equations
- In-class Activity: Backward Euler Method
- In-class Activity: Diagonally Implicit Runge-Kutta
- Demo: Backward Euler stability
- Demo: Dissipation in Runge-Kutta Methods
- Demo: Forward Euler stability
- Demo: Stability regions
- Demo: Stiffness
- Chapter 10: Boundary Value Problems for ODEs
- Chapter 11: Partial Differential Equations
- Chapter 12: Fast Fourier Transform
- Chapter 13: Random Numbers and Simulation
Team
Patrick Naughton
(TA)
Email: pn10@illinois.edu
Office: Siebel 0207, Thursday 2-3pm, Friday 2-3pm
Navjot Singh
(TA)
Email: navjot2@illinois.edu
Office: Siebel 0207, Wednesday 2-3pm, Friday 3-4pm
Statement on CS CARES, Values, and Code of Conduct
All members of the Illinois Computer Science department---faculty, staff, and students---are expected to adhere to the CS Values and Code of Conduct. The CS CARES Committee is available to serve as a resource to help people who are concerned about or experience a potential violation of the Code. If you experience such issues, please contact the CS CARES Committee. The instructor of this course are also available for issues related to this class.
Textbook
Michael T. Heath, Revised Second Edition, Society for Industrial and Applied Mathematics
Also see our class Piazza forum for a discount code for purchasing the book from SIAM.
Computing
We will be using Python with the libraries numpy, scipy and matplotlib for in-class work and assignments. No other languages are permitted. Python has a very gentle learning curve, so you should feel at home even if you've never done any work in Python.
Running Code on your Own Computer
While running code in this online system should technically suffice to do your work for this class, you may find it useful to also install Python on your own computer.
The recommended and perhaps one of the easier ways of doing so involves downloading the Anaconda Python distribution. Note that this is a commercial product (even if it is free of charge), and this is not intended as an endorsement of the company or the product. Note that we cannot promise to provide technical support for this installation.
Another way to obtain a Python installation is through a virtual machine image:
Grading Policies
Python Help
(see section 1 of the outline for more)
- Python tutorial
- Facts and myths about Python names and values
- Learn Python the hard way
- Project Euler (Lots of practice problems)
- From Python to Numpy
- PythonTutor (Execute Python step-by-step, with pictures)
Python workshop material
Numpy Help
(see section 1 of the outline for more)
- Introduction to Python for Science
- The SciPy lectures
- The Numpy MedKit by Stéfan van der Walt
- The Numpy User Guide by Travis Oliphant
- Numpy/Scipy documentation
- More in this reddit thread
- An introduction to Numpy and SciPy