CS 302 -- Numerical Computation for Algebraic Problems
Instructor: Tyrone Rees
Office: ICICS/CS 215
Lectures: Monday, Wednesday and Friday, 12:00-13:00, DMP 101
TAs: The TAs are Rob Hocking (email firstname.lastname@example.org) and
Josh Litven (email email@example.com )
Instructor office hour: Monday 10:00 - 11:00, ICICS/CS 247 (or by appointment)
TA office hour: Thursday 2:00 - 3:00, Scientific Computing Lab (ICICS/CS 246)
WebCT: Grades and discussion board here.
Fill out the course evaluation online (by 10th April): link
Assignment 1 Due in class on Monday January 24th. Solution.
Assignment 2 Updated 1/2/2011. Due in class on Monday February 7th. Solution.
Assignment 3 Updated 26/2/2011. Due in class on Monday March 7th. Solution.
Assignment 4 and the m-file ls_q1.m. Due in class on Monday March 21st. Solution.
Assignment 5 Updated 28/3/2011. Due in class on Monday April 4th. Solution..
- Grading scheme: Assignments -- 30%, Midterm -- 20%, Final exam -- 50%. Only the best four assignments will be counted towards the final grade. The instructor reserves the right to modify this at any time.
- In addition to a pass on the above scheme, a pass mark on the final exam is a must in order to pass the course.
- There will be a 10% deduction for every 24 hours an assignment is late, up to a maximum of four days. After four days a score of zero will be recorded for the assignment.
- Discussing the problems with others in the course is encouraged, but plagiarism is not. Please write the names of everyone you have worked with on top of your assignment.
Do not hand in someone else's work -- doing so may result in a grade of zero for that assignment.
- The midterm exam was on Monday, February 21st at noon. No books, calculators or 'cheat sheets' were allowed. Further information available here .
- Links to the midterm, and the solution. The average mark was 71%, and the histogram of grade distributions can be seen here.
- The final exam will be on Tuesday, April 12th at noon. No books, calculators or 'cheat sheets' are allowed. Further information available here .
The course will closely follow the notes (and soon to be textbook) A first course in Numerical Analysis by Ascher and Greif. Clicking on the link, and entering the username and password given in class, will allow you to download the relevant chapters. Optional recommended texts for further reading will be suggested as the course progresses.
- Handout on events in CS this week.
- Further reading on floating point numbers: Numerical Computing with IEEE Floating Point Arithmetic by Michael L. Overton.
- The m-file from Lecture 3 and the MATLAB function from Lecture 4 which 'plot' a floating point system.
- The handout on the patriot missile failure from Lecture 4.
- The m-file demonstrating cancellation error from Lecture 5.
- Further reading on linear algebra background: Schaum's outline's Linear Algebra, Lipschutz and Lipson. Or Wikipedia.
- An error and a blunder are very different things. An error is a small mistake, probably unavoidable even by a perfect mathematician or a
perfect computer. A blunder is much more serious, and larger by at least an order of magnitude. When the computer rounds off a number to
the eighth significant place, that is an error; but when a problem is so excruciatingly sensitive that this roundoff error completely changes
the solution, then almost certainly someone has committed a blunder. Our goal...is to analyze the effect of errors, so that blunders can be
avoided. -- Gil Strang, Linear Algebra and it's Applications
- The midterm feedback form -- if you missed this lecture and would like to give feedback, download the form and put it in my mailbox.
- Further reading on Numerical Linear Algebra: Numerical Linear Algebra by Trefethen and Bau.
- Handout on (asymptotically) more efficient GE algorithms. Link to SIAM news article.
- Handout showing an example of the LU decomposition.
- Gaussian elimination without pivoting demo.
- Paper: Gaussian Elimination with partial pivoting can fail in practice, Leslie V. Foster, SIAM Journal on Matrix Analysis and Applications,
Volume 15, Issue 4, Oct. 1994.
- Biography of Cholesky.
- The matlab function of Cholesky decomposition (although generally better to use chol() in MATLAB).
After reading the notes above, the best way to get started with Matlab is with their own guide Getting Started. Various other Matlab tutorials are available:
The content of the lectures will be the definitive syllabus, which will define what topics are in the final exam. An outline of the topics to be covered is given below; the instructor
reserves the right to change this as term progresses:
Introduction to Matlab
Floating point numbers and IEEE arithmetic
Nonlinear equations in one variable, including:
Review of linear algebra (vector and matrix norms, special classes of matrices...)
- Bisection method
- Fixed point iteration
- Newton's method and secant method
Direct methods for solving linear systems, including:
Linear least squares problems (normal equations and the QR factorization)
- Gaussian elimination and back substitution
- LU decomposition
- estimating errors and the condition number
- the Cholesky decomposition
Iterative methods for solving linear systems, including:
Eigenvalues and singular values, including:
- Stationary iterative methods
- Steepest descent
- Conjugate gradients
- the power method
- the inverse power method
- the QR algorithm
- the singular value decomposition