This course will focus on the continuous mathematics used in computer science (and EE) with a particular emphasis on the issues associated with designing, implementing and/or using numerical algorithms to solve equations. An underlying theme concerns the approximation issues associated with using floating-point numbers (as opposed to integers) in numerical algorithms.
Please refer all questions about course material and practices to the CAs before contacting Professor Fedkiw. If you have a question for the CAs, please make sure that it isn't answered on this webpage before contacting them. Also, please do not show up outside of scheduled office hours without first making an appointment. When emailing the CAs, make sure to include "CS205" somewhere in the subject of your message.
Please note that you may be able to take the course without owning the textbook but you are still required to be able to access a copy if needed. It is also an excellent resource (it was written by a Stanford graduate) and thus highly recommended.
|Sources and measure of numerical errors.
Accuracy and stability of numerical calculations
|Linear Systems. Existence and uniqueness of a solution.
Gaussian elimination and LU factorization. Pivoting.
|1 1/2 classes|
|Matrix norms and condition number||1/2 class|
|Cholesky factorization||1/2 class|
|Overconstrained systems. Normal Equations||1/2 class|
|QR factorization. Gram-Schmidt orthonormalization.
|Eigenvalue problems. Characteristic Polynomial. Similarity transforms. Jordan forms. Power Method||1 1/2 classes|
|Singular Value Decomposition||1/2 classes|
|Nonlinear equations. Fixed point iteration. Newton, secant and bisection methods. Convergence rate. Systems of nonlinear equations.||1 1/2 classes|
|Unconstrained optimization. Golden section search. Newton iteration. Steepest descent method.||1 class|
|Conjugate Gradients Method||2 1/2 classes|
|Constrained optimization. Lagrange multipliers||1/2 class|
|Function interpolation. Polynomial interpolants. Lagrange and Newton interpolation. Splines||1 class|
|Numerical quadrature. Newton-Cotes and Gaussian quadrature.||1/2 class|
|Initial value ODE problems. Stability and accuracy.||1/2 class|
|Forward and Backward Euler, Trapezoidal Rule. Runge-Kutta, TVD and multistep methods.||1 class|
|Newmark integrators. Staggered position/velocity grids.||1 class|
|Boundary value PDE problems. Discretization and solution of the Laplace Equation. The Heat Equation. CFL condition and stability.||1 class|
There will be a problem set assigned each week which will be posted on Thursday at 11:59 PM. The homework is due the following Thursday by 11:59 PM, and solutions will be posted promptly at that time. Homework is considered late if it is not in the box at the time the solutions are posted to the webpage, and late homework will receive no credit, with absolutely no exceptions.
Homework will be graded in coarse, half-point increments between 0 and 2 points. A sample midterm will be assigned in lieu of normal problems the week before each midterm and graded coarsely out of 3 points.
You may collaborate on homework assignments provided each student writes up his or her own solutions and clearly lists the names of all the students in the group.
Submission: Homework must be submitted physically in the bin outside Gates 210. If it is after hours and you cannot get onto the second floor of gates you can use your Student ID to get into the basement. There is a dropoff bin inside the Pup cluster. Please only use the bin in the pup cluster if it is after hours. You can also turn in homework the Thursday they are due in class.
No, we do not have a stapler that you can use. Don't even ask.
Homework is available for pickup in Gates 377 in the filing cabinet.
There will be two in-class midterm examinations on October 21st (Class 9) and December 4th (Last Class). Additionally there will be an optional cumulative final on December 8th from 12:15-3:15pm. If you choose not to take the final, your final exam grade will be determined by averaging your two midterm scores. All exams are closed book and closed notes. The final exam will be held in Skilling 193 (the usual classroom). The part of the exam corresponding to the first midterm will run from 12:15-1:30pm, there will be a 15 minute break, and then the part corresponding to the second midterm will run from 1:45-3:00pm.SVD: You are not required to know algorithms for finding the SVD of an arbitrarily complex matrix, but should be able to find the SVD for simple matrices such as those on the practice midterm. Keep in mind that the singular values of A are the square-roots of the eigenvalues of A^T A or A A^T. More generally, the columns of U and V are the eigenvectors of A A^T and A^T A, respectively.
|Midterm Exam 1||20%|
|Midterm Exam 2||20%|