CS 302 -- Numerical Computation for Algebraic Problems

Assignments/grading

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 .

Reading/further notes

• The handout from Lecture 1.
• The pdf and html (with MATLAB output) for Lecture 2.

• 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 rootfinding: Süli and Mayers, An introduction to Numerical Analysis, Chapter 1.
• The demo of the bisection method from Lecture 6.
• The matlab function of the bisection method from Lecture 7.
• The fixed point iteration demo from Lecture 8.
• The Newton's method as a fixed point iteration demo from Lecture 8.
• The geometric Newton's method demo from Lecture 8.

• 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).

• The matlab functions for interpolation and curve fitting.
• The matlab function for QR factorization by Gram-Schmidt.

• The matlab function for QR factorization by modified Gram-Schmidt.
• The matlab demo for QR factorization by Householder matrices.

• The matlab function for Jacobi iteration.

• The matlab function for Steepest Descent.
• The Steepest Descent notes.
• The matlab function for Conjugate Gradients.
• The matlab function which gives the polynomials in Conjugate Gradients.

• The matlab function which maps circles to ellipses for the geometric interpretation of the SVD.
• The New York Times article on the SVD in the Netflix prize.
• A matlab function to demo the power method.

• The matlab functions for the QR movie, QR movie with reduction to Hessenberg form and the QR movie with shifts.
• An article on Understanding the QR algorithm, by David Watkins

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:

• Ian Mitchell, Matlab Resources
• Kevin Murphy, Matlab Tips
• Ian Cavers, Introductory Guide to Matlab
• Mark S. Gockenbach, A Practical Introduction to Matlab

Outline Syllabus