CMSC/AMSC/MAPL 460 Computational Methods
Class: TuTh......12:30pm 1:45pm (CSI 1121)
Office Hours: Monday 1011:30 and by appointment, in AVW 3365.
Instructor: Ramani Duraiswami Email: ramani AT umiacs.umd.edu;
Office Hours: Monday 1011:30 and by appointment, in AVW
3365.
Teaching Assistant: Alison Teoh; Email: alison.lk.teoh AT gmail.com
Office Hours: 1:45 to 3:45 pm on Wednesdays.
Textbook (Required): Numerical Computing with MATLAB, by Cleve Moler, ISBN 0898715601
Individual Chapters may be downloaded from the author's web site at http://www.mathworks.com/moler/chapters.html
The book may be purchased from the bookstore, or from the web.
Software (required): MATLAB.
You will need reliable access to MATLAB and a printer for doing homework in
this course.
If you already do not have access to Matlab and have a PC, the best option would be to buy a student edition from the bookstore.
You can also get by without buying this copy and using the software which should be accessible from University computers.
Registered students should receive email with details on class accounts on the Grace computers.
Printing: Most homework will call for printing material (graphs, programs and the like off Matlab) and submitting it. Emailed homework is NOT acceptable.
Prerequisites: Programming, advanced calculus, linear algebra.
Description in the catalog: Basic computational methods for interpolation, least squares, approximation, numerical quadrature, numerical solution of polynomial and transcendental equations, systems of linear equations and initial value problems for ordinary differential equations. Emphasis on methods and their computational properties rather than their analytical aspects.
Homework will be given out periodically, and will be due on the first class in the following week from the date handed out. No late homework, without prior arrangement. Homework will be posted on this web page.
Collaboration Policy: You may study together and discuss problems and methods of solution with each other to improve your understanding. You are welcome to discuss assignments in a general way among yourselves, but you may not use other students' written work or programs. Use of external references for your work should be cited. Clear similarities between your work and others will result in a grade reduction for all parties. Flagrant violations will be referred to appropriate university authorities.
You are responsible for checking this page.
Policy: Honor code http://www.studenthonorcouncil.umd.edu/code.html
Grading: Homework 40%, MidTerm 25%, Final 35%
Previous versions of this course: (for reference) Fall2005 Spring2007
DATE 
LECTURE 
CONTENTS 
09/02, 2009 (Tuesday) 
Lecture 0 

09/04, 2008 (Thursday) 
Introduction to the course. Rules. Introduction to MATLAB 

09/09, 2008 (Tuesday) 

Errors. Well posed problems. Floating point representation. Keywords: fixed point, floating point, Mantissa, significand, exponent, sign, overflow, underflow, zero, Inf, NaN, float (single precision), double (double precision), IEEE 754 

Homework 1 Due 09/18 
Matlab: do the following problems in the text: 1.5, 1.6., 1.7, and 1.20 Floating point representation: 1.34, 1.35, 1.38, 1.39 
09/11, 2008 (Thursday) 

Recap of the floating point representation; examples of how representation errors can cause problems during calculations; forward and backward error analysis 
09/16,2008 (Tuesday) 

Matrices, vectors,


Homework 2
Due 09/25 
Do the following problems in the text: 2.7, 2.8, 2.11, 2.16, 2.18 Also for a small extracredit of one point register for the class forum and post something 
09/18, 2008 (Thursday) 

Solving diagonal and triangular systems Gaussian elimination LU decomposition 
09/23, 2008 (Tuesday) 

LU decomposition Permutation Matrices Matlab tricks, Wrap up 
09/25, 2008 (Thursday) 

Polynomial Interpolation Monomials & Vandermonde matrices Lagrange & Newton forms Instability of polynomial interpolation 
Due 10/07 
Homework 3

1. Do the following problems 3.3, 3.4, 3.7, 3.9 2. Read section 3.4 of the book, and summarize the shapepreserving piecewise cubic spline algorithm. How would a program to interpolate a spline using this algorithm differ from one using the cubic spline algorithm discussed in class. 
09/30, 2008 (Tuesday)


Error analysis of Polynomial interpolation Piecewise Linear Interpolation 
10/02, 2008 (Thursday) 

Cubic spline interpolation. Tridiagonal system solution. Horner’s rule. 
10/07, 2008 (Tuesday)


Zero finding, bisection. Secant method. Newton method.

Due 10/14 
Homework 4

1. Do the following problems: 4.3, 4.8, 4.9, 4.15, 4.18 
10/09, 2008 (Thursday) 
Wrap up of zero finding and optimization Least squares – normal equations 

10/14, 2008 (Tuesday)


Least Square – QR algorithm. Givens Rotations 
10/16, 2008 (Thursday) 
Least squares. QR via the Householder transform Reference: John Kerl’s article on Householder transforms. (local copy) 

Due 10/23 
Homework 5 
Least squares: Do the following problems from the text: 5.5, 5.7, 5.8, 5.12

10/21, 2008 (Tuesday)

Exam. 
You are allowed to bring a calculator and a single sheet of paper to the exam with any information you want on it. However, you should prepare the material on the sheet yourself, and submit it with the exam. 
10/23, 2008 (Thursday) 
Numerical Integration, NewtonCotes Formulae 

10/28, 2008 (Tuesday) 
Lecture 15 (notes above) 
Adaptive Integration, Richardson extrapolation, Romberg integration 
10/30, 2008 (Thursday) 
Lecture 16 (notes above) 
Gaussian Integration 
Due Thursday 11/11/2008 
Homework 6 
1. Problems 6.1, 6.3, 6.6 2. Derive error bounds for the approximation of the integral below via the Simpson 1/3 rule of integration in terms of the size of the domain of integration and derivatives of the function f(t):

11/04, 2008 (Tuesday)

Election Day … Go Vote! (if you are eligible to).
Ordinary differential equations; initial value problems, standard form, Euler method, modified Euler Method 

11/06, 2008 (Thursday) 

matlab: volteratest.m rabfox.m 
11/11, 2008 (Tuesday)

multistep methods; implicit methods; AdamsBashforth and Adams Moulton; notions of stability and stiffness matlab: stiff_ode.m 

Due 11/20 


11/13, 2008 (Thursday) 
Eigenvalues and Eigenvectors (background) 

11/18, 2008 (Tuesday) 
Lecture 21 (use link above) 
Power Algorithm, Rayleigh quotient, QR 
11/20, 2008 (Thursday) 
Lecture 22 (use link above) 
QR algorithm with shifts, Singular value decomposition 
Due 12/04 


11/25, 2008 (Tuesday)

Lecture 23 (use link below) 
Fourier Analysis 
11/27, 2008 (Thursday) 

Thanksgiving 
12/02, 2008 (Thursday) 

Fourier Analysis 
12/04, 2008 (Tuesday) 
Lecture 25 (use link above) 
FFT 
12/09, 2008 (Tuesday)

Lecture 26
Last Class 
Review 
12/19, 2008 (Friday) 
FINAL EXAM

Friday, Dec 19 1:30pm3:30pm in the same classroom Material: things covered after the mid term, plus basic concepts from throughout the course. You are allowed to bring a single sheet of paper to the exam with any information you want on it. However, you should prepare the material on the sheet yourself, and submit it with the exam. 
Useful Links
Previous versions of 460 offered.
Prof. O'Leary: Fall 2002 (some of my material is adapted from this course)
Prof. Elman:
MATLAB resources:
Introductory Tutorials
Slightly more advanced Tutorials
More complete references/tutorials/FAQs