Numerical Methods (CS 357) Fall 2016
What | Where |
---|---|
Time/place | In-Person Section (M): TTh 9:30am-10:45am 1404 Siebel / Catalog |
Online Section (N): Watch lectures at the link below. | |
Class URL | https://bit.ly/cs357-f16 |
Class recordings | Watch » |
Web forum | Discuss » · Suggestions · Instant message |
Calendar | View » |
Quizzes
Please find the quizzes under their corresponding lecture in the class calendar.
Exams
Please find information on our upcoming exams in the corresponding section of 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
- Homework Set 0
- Homework Set 1 (Part 1) (120% credit if completed by the early deadline)
- Homework Set 1 (Part 2)
- Homework Set 2 (Part 1) (120% credit if completed by the early deadline)
- Homework Set 2 (Part 2)
- Homework Set 3 (Part 1) (120% credit if completed by the early deadline)
- Homework Set 3 (Part 2)
- Homework Set 4 (Part 1) (120% credit if completed by the early deadline)
- Homework Set 4 (Part 2)
- Homework Set 5 (Part 1) (120% credit if completed by the early deadline)
- Homework Set 5 (Part 2)
- Homework Set 6 (Part 1) (120% credit if completed by the early deadline)
- Homework Set 6 (Part 2)
Course Outline
-
Part 1: Models, Errors, and Numbers
-
Objectives
- Use numpy for more efficient computations
- Construct examples that show the benefits of contigous memory (numpy arrays)
- Identify the advantages of numerical libraries
- Create a numerical experiment that measures the cost of basic array operations
- Represent a real number in a floating point system
- Measure the error in rounding numbers in the IEEE-754 floating point standard
- Compute floating point vaules in different portions of the floating point range
- Use the IEEE-754 standard to quantify error floating point arithmetic
- Compute the memory storage of single versus double precision
- Describe the accuracy of several examples in terms of machine epsilon
- Determine whether data grows algebraically versus exponentially and at which rate
- Design a numerical experiment with reproducibility, randomness, consistent timing in mind
- Compute a random process
- Use randomness to confirm a numerical hypothesis
- Approximate a function using a Taylor series approximation
- Quantify the error in using a Taylor series approximation at several points
- 0. Introduction
-
1. Python, Numpy, and Matplotlib
- Notes (complete)
- Activity: Image Processing
- Quiz: Big O and Python (Quiz 03)
- Demo: 1-1-Python-Types
- Demo: 1-2-Python-Names and Values
- Demo: 1-3-Python-Indexing
- Demo: 1-4-Python-Control flow
- Demo: 1-5-Python-Functions
- Demo: 1-6-Python-Objects
- Demo: 1-7-Python-A few more things
- Demo: 2-1-numpy-Introduction
- Demo: 2-2-numpy-Indexing
- Demo: 2-3-numpy-Broadcasting
- Demo: 2-4-numpy-Tools
- Demo: 2-5-numpy-Data Storage
- Code: gvmagic.py
- Code: objgraph.py
- Code: objgraph_helper.py
-
2. Making Models with Polynomials
- Notes (complete)
- Activity: Taylor Series
- Activity: Interpolation
- Quiz: Taylor Series and Python (Quiz 04)
- Quiz: Taylor Series and Error (Quiz 05)
- Quiz: Interpolation (Quiz 06)
- Demo: Computing π with Interpolation
- Demo: Computing π with Taylor
- Demo: Polynomial Approximation with Derivatives
- Demo: Polynomial Approximation with Point Values
-
3. Making Models with Monte Carlo
- Notes (complete)
- Activity: Monte Carlo Methods
- Quiz: Random Variables and Monte Carlo (Quiz 07)
- Quiz: Sampling (Quiz 08)
- Quiz: Sampling 2 (Quiz 09)
- Demo: Computing π using Sampling
- Demo: Counter-Based Random Number Generation
- Demo: Errors in Sampling
- Demo: Playing around with Random Number Generators
- Demo: Plotting Distributions with Histograms
- 4. Error, Accuracy and Convergence
-
5. Floating Point
- Notes (complete)
- Activity: Floating Point
- Activity: Floating Point 2
- Quiz: Floating Point 1 (Quiz 11)
- Quiz: Floating Point 2 (Quiz 12)
- Demo: Catastrophic Cancellation
- Demo: Density of Floating Point Numbers
- Demo: Floating Point vs Program Logic
- Demo: Floating point and the Harmonic Series
- Demo: Picking apart a floating point number
-
Objectives
-
Part 2: Arrays--Computing with Many Numbers
-
Objectives
- Take a linear algebra operation and apply the operation in a computational setting
- Represent a problem description in terms of matrices and vectors
- Load a collection of data into matrix and vector data structures
- Compute the solution to a linear system of equations
- Detail the pieces of an LU factorization of a linear system
- Use an LU factorization to solve a problem with many right-hand sides
- Measure the number of digits of accuracy for poorly conditioned problems
- Compute eigenvalues/eigenvectors for different applications
- Use the Power Method to find a specific eigenvector
- Compute singular value decomposition for different applications
- Use singular values to identify dominant subspaces
- Represent a linear system as a sparse linear system
- Represent a graph as a sparse system
- Compute the cost of a sparse matrix-vector multiply
-
6. Modeling the World with Arrays
- The World in a Vector
- What can matrices do?
- Graphs
- Sparsity
- 7. Norms and Errors
-
8. The 'Undo' Button for Linear Operations: LU
- Notes (complete)
- Quiz: Review (Quiz 17)
- Quiz: LU factorization (Quiz 18)
- Quiz: Pivoting (Quiz 19)
- Activity: LU Factorization
- Activity: LU Factorization 2
- Demo: Coding back-substitution
- Demo: Complexity of Mat-Mat multiplication and LU
- Demo: Elimination Matrices I
- Demo: Elimination Matrices II
- Demo: LU factorization
- Demo: Vanilla Gaussian Elimination
-
9. LU: Applications
- Linear Algebra Applications
-
Interpolation
- Notes (complete)
- Activity: Interpolation 2
- Activity: Finite differences/Quadrature
- Quiz: LU Applications (Quiz 20)
- Quiz: Advanced Interpolation (Quiz 21)
- Quiz: Differentiation and Quadrature (Quiz 22)
- Demo: Accuracy of Simpson's rule
- Demo: Chebyshev interpolation
- Demo: Choice of Nodes for Polynomial Interpolation
- Demo: Computing the weights in Simpson's rule
- Demo: Finite Differences
- Demo: Interpolation with Radial Basis Functions
- Demo: Monomial interpolation
- Demo: Orthogonal Polynomials
- Demo: Taking Derivatives with Vandermonde Matrices
- 10. Repeating Linear Operations: Eigenvalues and Steady States
- 11. Eigenvalues: Applications
- 12. Approximate Undo: SVD
-
13. SVD: Applications
- Solving Funny-Shaped Linear Systems
- Data Fitting
- Norms and Condition Numbers
- Low Rank Approximation
- Demo: Data Fitting with Least Squares
- Demo: Image compression
- Demo: Least Squares using the SVD
- Demo: Pseudoinverse and Least Squares
- Demo: Rank-1 approximation
-
Objectives
-
Part 3: Approximation: When the Exact Answer is Out Of Reach
-
Objectives
- Interpolate or fit a piece of data with a given model (or function)
- Find the derivative of noisy data
- Compute the intgral of a data set
- Use least-squares data fit to determine a trend
- Calculate the the cost of a least-squares solution
- Measure the error in a least-squares solution
- Approximate the minimum to an objective function
- Approximate the minimum to an objective function in multiple dimensions
- 14. Iteration and Convergence
- 15. Solving One Equation
- 16. Solving Many Equations
- 17. Finding the Best: Optimization in 1D
- 18. Optimization in n dimensions
-
Objectives
CAUTION!
These scribbled PDFs are an unedited reflection of what I wrote during class. They need to be viewed in the context of the class discussion that led to them. See the lecture videos for that.
If you would like actual, self-contained class notes, look in the outline above.
These scribbles are provided here to provide a record of our class discussion, to be used in perhaps the following ways:
- as a way to cross-check your own notes
- to look up a formula that you know was shown in a certain class
- to remind yourself of what exactly was covered on a given day
By continuing to read them, you acknowledge that these files are provided as supplementary material on an as-is basis.
- scribbles-2016-08-23.pdf
- scribbles-2016-08-25.pdf
- scribbles-2016-08-30.pdf
- scribbles-2016-09-01.pdf
- scribbles-2016-09-06.pdf
- scribbles-2016-09-08.pdf
- scribbles-2016-09-13.pdf
- scribbles-2016-09-15.pdf
- scribbles-2016-09-20.pdf
- scribbles-2016-09-22.pdf
- scribbles-2016-09-27.pdf
- scribbles-2016-09-29.pdf
- scribbles-2016-10-04.pdf
- scribbles-2016-10-06.pdf
- scribbles-2016-10-11.pdf
- scribbles-2016-10-13.pdf
- scribbles-2016-10-18.pdf
- scribbles-2016-10-20.pdf
- scribbles-2016-10-25.pdf
- scribbles-2016-10-27.pdf
- scribbles-2016-11-01.pdf
- scribbles-2016-11-03.pdf
- scribbles-2016-11-08.pdf
- scribbles-2016-11-10.pdf
- scribbles-2016-11-15.pdf
- scribbles-2016-11-17.pdf
- scribbles-2016-11-29.pdf
- scribbles-2016-12-01.pdf
- scribbles-2016-12-06.pdf
Team







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 this class
Python Help
(see section 1 of the outline for more)
- The Scipy Lectures
- Dive into Python 3
- Learn Python the hard way
- Python tutorial
- Facts and myths about Python names and values
- CSE workshop training material
Numpy Help
- Introduction to Python for Science
- Numpy/Scipy documentation
- More in this reddit thread
- An introduction to Numpy and SciPy
- 100 Numpy exercises
- The Numpy MedKit by Stéfan van der Walt
Statistics (goes beyond class material)
- Statistics for Hackers by Jake VanderPlas
Optimization (goes beyond class material)
- An Interactive Tutorial on Numerical Optimization by Ben Frederickson