Numerical Analysis (CS 450) Spring 2024
What | Where |
---|---|
Time/place | Tue/Thu 11:00am--12:15pm [1404 Siebel Center] |
Class URL | https://relate.cs.illinois.edu/cs450-s24 |
Class recordings | https://mediaspace.illinois.edu/channel/channelid/330048022 |
Web forum | https://piazza.com/illinois/spring2024/cs450 |
Calendar | View Calendar » |
Quizzes
Posted here by start of each lecture. Due 7 days from start of lecture, Generally, we will go over all or most quiz questions during the lecture.
Quiz 1: Error, Conditioning, and Course Policies »
Quiz 2: Floating Point Arithmetic »
Quiz 3: Matrix Norms and Conditioning, Triangular Systems »
Quiz 4: Solving Linear Systems »
Quiz 5: Solving Linear Least Squares Problems »
Quiz 6: Linear Least Squares Problems and Low-Rank Approximation »
Quiz 7: Eigenvalues, Conditioning, and Power Iteration »
Quiz 8: Eigenvalue Decomposition Algorithms »
Quiz 10: Nonlinear Optimization »
Quiz 11: Constrained Nonlinear Optimization »
Quiz 13: Orthogonal Polynomials, Piecewise Interpolation, and Quadrature »
Quiz 14: Composite Quadrature and Numerical Differentiation »
Quiz 15: Characterization of ODEs and Euler Methods »
Quiz 16: Initial Value Problems for Ordinary Differential Equations »
Quiz 17: Boundary Value Problems for Ordinary Differential Equations »
Quiz 18: BVPs and Classification of PDEs »
Homework
Homework 5 (worth 2/3 value of regular homework, last question extra credit) »
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).
Course Outline
-
Chapter 1: Scientific Computing
- Notes (Michael T. Heath)
- Lecture Notes
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Chapter 10: Boundary Value Problems for ODEs
- Chapter 11: Partial Differential Equations
- Chapter 12: Fast Fourier Transform
- Chapter 13: Random Numbers and Simulation
Team
Nicolas Nytko
(TA)
Email: nnytko2@illinois.edu
Office: Siebel 4th floor atrium (outside 4102), Monday/Wednesday 2-3pm
Jiakun Yan
(TA)
Email: jiakuny3@illinois.edu
Office: Siebel 0209, Tuesday 3-4pm, Thursday 2:20-3:20pm
Jize Jiang
(TA)
Email: jizej2@illinois.edu
Office: Siebel 0207, Wednesday/Friday 10-11am
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