Numerical Analysis (CS 450) Fall 2018
| What | Where |
|---|---|
| Time/place | MW 3:30pm-4:45pm 1320 DCL / Catalog |
| Class URL | https://relate.cs.illinois.edu/course/cs450-f18/ |
| Class recordings | Echo 360 Video » |
| Web forum | View Piazza » |
| Calendar | View Calendar » |
Quizzes
The latest five quizzes will be posted below. To access all previous quizzes, go to (Participant, View Grades, follow desired flow grade link, follow arrow flow link). Quizzes will be due by the start of the subsequent lecture.
Quiz 19: Orthogonal and Piecewise Interpolation »
Quiz 18: Basics of Interpolation »
Quiz 17: Nonlinear Least Squares and Constrained Optimization »
Quiz 16: Multidimensional Unconstrained Optimization Algorithms »
Quiz 15: Optimization Problems and Algorithms for 1D Optimization »
Examlets
Three 1-hour examlets will be given electronically in CBTF during the semester and the final is also likley to be in CBTF. Please find information on examlet dates in the class calendar. Reserve your time slots in the testing facility as soon as possible--otherwise your preferred times may no longer be available.
Homework
There will be 6 Homework assignments, released/due on a biweekly basis. They will generally be due at 10 pm Fridays.
Homework 1 » 4-Credit Hour Addendum to Homework 1 »
Homework 2 » 4-Credit Hour Addendum to Homework 2 »
Homework 3 » 4-Credit Hour Addendum to Homework 3 »
Homework 4 » 4-Credit Hour Addendum to Homework 4 »
Homework 5 » 5-Credit Hour Addendum to Homework 5 »
Assignments for 4 Credit-Hour Section
If you are enrolled in CS 450 for 4 credit hours, you will need to complete an addendums for each of the first 5 Homeworks, which will be due one week after the main part of the homework. See the calendar for all homework due dates.
Course Outline
-
1. Chapter 1: Scientific Computing
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 1: Policies
- Quiz 2: Error, Conditioning, and Floating Point
- In-class Activity: Cancellation in Standard Deviation Computation
- 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
-
2. Chapter 2: Systems of Linear Equations
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 3: Floating Point, Matrix Norms, and Matrix Condition Number
- Quiz 4: Matrix Conditioning and Error in Linear Systems
- Quiz 5: Gaussian Elimination
- Quiz 6: Stability and Matrix Structure in Solving Linear Systems
- In-class Activity: Singular Value Decomposition and Norms
- 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
-
3. Chapter 3: Linear Least Squares
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 7: Least Squares and QR Factorization
- Quiz 8: Least squares algorithms and rank-deficiency
- In-class Activity: Householder QR
- In-class Activity: Rank Deficient Least Squares Problems
- 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
-
4. Chapter 4: Eigenvalue Problems
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 9: Conditioning and Basic Algorithms for Eigenvalue Problems
- Quiz 10: Canonical Forms for Eigenvalue Problems and Deflation
- Quiz 11: Schur Decomposition and QR Iteration
- Quiz 12: Tridiagonal Eigenproblems and Krylov Subspace Methods
- In-class Activity: Inverse Iteration with a Shift
- In-class Activity: Rayleigh Quotient Iteration
- In-class Activity: Calculating Eigenpairs of Triangular Matrix
- In-class Activity: Orthogonal Iteration
- In-class Activity: QR Iteration
- In-class Activity: Computing the Maximum Ritz Value
- In-class Activity: Approximation with Orthogonal Iteration and Lanczos
- Demo: Arnoldi Iteration with Complex Eigenvalues
- Demo: Arnoldi Iteration
- Demo: Arnoldi vs Power Iteration
- Demo: Householder Similarity Transforms
- Demo: Orthogonal Iteration
- Demo: Power iteration and its Variants
- Demo: Rounding in characteristic polynomial using SymPy
-
5. Chapter 5: Nonlinear Equations
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 13: Basic Methods for Solving Nonlinear Equations
- Quiz 14: Cost and Robustness of Methods for Solving Nonlinear Equations
- In-class Activity: Newton's Method for 2-by-2 System of Equations
- In-class Activity: Broyden's Method
- 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
- Code: three-quadratics.py
-
6. Chapter 6: Optimization
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 15: Optimization Problems and Algorithms for 1D Optimization
- Quiz 16: Multidimensional Unconstrained Optimization Algorithms
- Quiz 17: Nonlinear Least Squares and Constrained Optimization
- 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
-
7. Chapter 7: Interpolation
- Notes (Michael T. Heath)
- Lecture Notes
- Quiz 18: Basics of Interpolation
- Quiz 19: Orthogonal and Piecewise Interpolation
- In-class Activity: Monomial Interpolation
- 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
-
8. 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
- 9. Chapter 9: Initial Value Problems for ODEs
- 10. Chapter 10: Boundary Value Problems for ODEs
- 11. Chapter 11: Partial Differential Equations
- 12. Chapter 12: Fast Fourier Transform
- 13. Chapter 13: Random Numbers and Simulation
Team
Textbook
Michael T. Heath, Second Edition, McGraw-Hill.
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.
Virtual Machine Image
While you are free to install Python and Numpy on your own computer to do homework, the only supported way to do so is using the supplied virtual machine image.
Grading Policies
Previous Editions of CS 450
Additional Text Resources
- Linear Algebra and Its Applications Gilbert Strang, 4th Edition, Harcourt Brace, 1987 (on reserve at Grainger).
- Numerical Linear Algebra Lloyd Trefethen and David Bau, SIAM, 1997 (on reserve at Grainger).
- Applied Numerical Linear Algebra James Demmel, SIAM, 1997 (on reserve at Grainger).
- Matrix Computations Gene Golub and Charles Van Loan, 4th Edition, The John's Hopkins University Press, 2013.
- Numerical Recipes William Press, Saul Teukolsky, William Vetterling, and Brian Flannery, 3rd Edition, Cambridge University Press, 2007.
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)
Python Workshop Material
- Video: Located on Echo 360 along with the other class recordings
- Tutorial material
- Scipy lecture notes
- CSE workshop training 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
- Spyder (a Python IDE, like Matlab) is installed in the virtual machine. (Applications Menu > Development > Spyder)
- An introduction to Numpy and SciPy