CMSC/AMSC/MAPL 460 Computational Methods

 

Class:  TuTh......12:30pm- 1:45pm (CSI 1122)

 

Instructor: Ramani Duraiswami E-mail: ramani AT umiacs.umd.edu;

Office Hours:  Fridays 10:30 a.m. - noon, in AVW 3365. (confirm I am there before coming by emailing me)

 

Teaching Assistant: Yuancheng [mike] Luo; E-mail: yluo1 AT umd.edu

Office Hours: 2:30-4:00 p.m. Thursdays, AVW 3368.

 

Textbook (Required): Numerical Computing with MATLAB, by Cleve Moler, ISBN 0-89871-560-1

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 the 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. However, this requires a degree of computer savviness, and your are responsible for figuring this out ASAP.

Registered students should receive email with details on class accounts on the Grace computers.

 

Class Forum: for peer-to-peer discussions/assistance.

 

NO LAPTOPS IN CLASS

 

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%, Mid-Term 25%, Final 35%

Previous versions of this course: (for reference) Fall-2005 Spring-2007 Fall 2008

DATE

LECTURE

CONTENTS

01/26, 2010

(Tuesday)

Lecture 1

 

Chapter 1

Introduction to the course.

Rules. Introduction to MATLAB

 

01/28, 2010

(Thursday)

Lecture 2

 

Representing numbers on a computer, unsigned integers, signed integers, floating point numbers

02/02, 2010

(Tuesday) 

Lecture 3

 

Examples of computations sensitive to error; forward and backward error analysis; well-posed problems

Due 02/09, at the beginning of class

Homework 1

 

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

 

02/04, 2010

(Thursday)

Lecture 4

Chapter2

Vectors, Matrices; Matlab

02/09,2010

(Tuesday)

No Class

Snowmaggedon

02/11, 2010

(Thursday)

No Class

Snoverkill

02/16, 2010

(Tuesday)

Lecture 5

 

Diagonal solve, Triangular solves, Permutation Matrices, Gaussian Elimination, LU decomposition

02/18, 2010

(Thursday)

Lecture 6

 

 

Coding the LU decomposition; solving a linear system via LU; the Matlab backslash operatior

 

Due 02/25

Homework 2

2.7, 2.8, 2.11, 2.16, 2.18

 

CLASS FORUM

02/23, 2010

(Tuesday)

Lecture 7

 

 Chapter 3

 Wrap up of LU: Examples where not pivoting causes problems; Error analysis; relation between residual and error; Condition number; Wrap up

02/25, 2010

(Thursday)

Lecture 8

Mfile 1

Mfile 2 

 Polynomial Interpolation; Monomial Interpolation and Vandermonde Matrices; Lagrange Interpolation

 

03/02, 2010

(Tuesday)

Lecture 9

Matlab

 Lagrange Interpolation, Newton Interpolation, piecewise linear interpolation

03/04, 2010

(Thursday)

Lecture 10

 Cubic spline interpolation. End conditions.

Due

03/11, 2010

Homework 3

 

Hand data

1. Do the following problems: 3.3, 3.4, 3.7, 3.9

2. Read section 3.4 of the book, and summarize the shape-preserving 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.

03/09, 2010

(Tuesday)

Lecture 11

Chapter 4

Finding zeros of functions. Bisection. Modified secant method. Newton method, Secant Method

03/11, 2010

(Thursday)

Lecture 12

Inverse Quadratic Interpolation. Optimization. Golden search. Multi-dimensional Newton.

Least Squares

Due 03/25

Homework 4

Problems 4.3, 4.8, 4.9, 4.15, 4.18

03/16, 2010

(Tuesday)

NO CLASS

Spring Break

 

03/18, 2010

(Thursday)

NO CLASS

Spring Break.

March madness --- GO TERPS!

03/23, 2010

(Tuesday)

Lecture 13

 Least Squares: The normal equations

03/25, 2010

(Thursday)

Lecture 14

 MID TERM 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.

03/30

 

(Tuesday)

Lecture 15

Least Squares: The QR decomposition

04/01, 2010

(Thursday)

Lecture 16

Least Squares: Householder and Givens, SVD, Wrap up

Due 04/13

Homework 5

Do the following problems from the text: 5.5, 5.7, 5.8, 5.12. Also in 5.5 (a) do the same via a sequence of Givens rotations.

 

04/06, 2010

(Tuesday)

Lecture 17

 Integration: Trapezoid, Simpson formulae; Open and Closed formulae; Composite Rules; Adaptive Quadrature

04/08, 2010

(Thursday)

Lecture 18

Adaptive Quadrature, Romberg Integration, Gaussian Integration

 Due 04/20

Homework 6

 Problems 6.1, 6.3, 6.6

04/13, 2010

(Thursday)

Lecture 19

Ordinary differential equations:  Introduction. Standard form. Eulers Method

04/15, 2010

(Tuesday)

Lecture 20

 Eulerís Method, Runge Kutta, Adamís-Bashforth

04/20, 2010

(Thursday)

Lecture 21

 

 See lectures above and below

Due 04/29

Homework 8

 1. Do the following problems 7.2, 7.3, 7.12, 7.13

/__

__ 0 __

_ 1_

2. Let

y(0)=1

.

Convert to standard form.

Is the problem stable or unstable at t=0?

3. Apply three steps of the Euler and the modified Euler methods, with a step size of 0.1 for the above problem, and compute approximations for y(0.1), y(0.2) and  y(0.3)

04/20, 2010

(Tuesday)

Lecture 22

 

 Implicit Methods, Stability

04/22, 2010

(Thursday)

 Lecture 23

Lecture 23 EV

ODE Wrap up.

 

Eigenvalues and Eigenvectors. Shifts. Similar Matrices.

04/27, 2010

(Tuesday) 

Lecture 24

 

 

Power Method, QR Algorithm

04/29, 2010

(Thursday)

Lecture 25

QR Algorithm, Shifts, SVD

Due 05/11

Using the function eigshow provided with the book, answer the following questions for the different 2x2 matrices that are displayed in the drop down box

Which matrices are singular?

Which matrices have complex eigenvalues?

Which matrices have double eigenvalues?

In each case answer why, and comment on the graphical picture the function produces?

05/04, 2010

(Tuesday)

Lecture 26

 

 

 Fourier Series and the Discrete Fourier Transform

05/06/2010

Lecture 27

 Fast Fourier Transform

05/11/2010

Lecture 28

Review Grades

Sample final

05/18, 2010

(Tuesday)

FINAL EXAM

 

GRADES

Tuesday, May 18: 1:30pm-3:30pm in the same classroom

Material: things covered after the mid term, plus basic concepts from throughout the course.

You are allowed to bring two sheets of paper to the exam with any information you want on them. 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)

MATLAB resources (Most links are somewhat dated --- your book has a very good introduction):

Introductory Tutorials

MATLAB tutorial from University of Utah

MATLAB tutorial from Carnegie Mellon University

MATLAB tutorial from Indiana University

Slightly more advanced Tutorials

More complete references/tutorials/FAQs