MATH 560 (Fall 2012)

Instructor's contact information

Michael Robinson
226 Gray Hall
michaelr at american {dot} edu
Office hours: Mondays 1:15-2pm, Tuesdays 11:30am-2pm, Wednesdays 9:30-10:15am, Thursdays 9:30-10:15am, or by appointment (please contact me 24 hours in advance to make arrangements)
My research website http://www.drmichaelrobinson.net/
Feel free to contact me with any questions (course-related or not)

Quick Links

Course description
Homework assignments
Course schedule
Concerning programming in this course
Information about exams
Some useful links
Course policies

Course description

This course covers basic numerical analysis, including solving nonlinear equations, interpolation, Fourier processing, numerical differentiation, and integration. It is a project-based class, in which students will be introduced to the topics by way of theoretical and programming practical exercises. Minimal programming experience is necessary, though familiarity with the concepts of computer programming is required.

Prerequisite(s): ability to program a computer (see below), or permission of instructor.

The course textbook is
Isaacson and Keller, Analysis of Numerical Methods, Dover edition.

In this course, students will

  1. Examine the kinds of effects that arise from the discretization of functions and operators on them,
  2. Reveal the centrality of interpolation by deriving several kinds of approximations to derivatives, integrals, and solutions to equations,
  3. Calculate precise bounds on the error performance of these approximations, and
  4. Gain practical experience in the implementation of these approximations.

Homework

Homework assignments consist of two parts: problems from the book (due every two weeks) and programming projects. A majority of each exam will be taken from these assignments (with slight modifications). You're therefore encouraged to ask me about them!

The programming projects will consist of some preliminary and background theory questions along with a set of guided programming exercises. Instructions and submission of all assignments will be elecronic via the course BlackBoard page! Check there often for updates.

Read the Matlab tutorial and get started on Project 1 early!

Homework 1 due September 6: p. 16: 2, 4; p. 96: 1, 2; p. 108: 1, 2
Homework 2 due September 20: p. 123, 1, 2, 3; p. 182: 1; p. 186: 1, 2
Homework 3 due October 4: p. 193: 1, 3; p. 218: 3, 5; p. 229: 1, 2
Homework 4 due October 18: p. 242: 1, 2, 3, 4
Homework 5 due November 1: p. 255: 3, 5; p. 260: 1, 2; p. 279: 1, 2
Homework 6 due November 15: p. 294: 1, 2; p. 21: 1, 2; p. 318: 2, 3
Homework 7 due December 6: p. 383: 1, 3; p. 394: 1, 3; p. 405: 1, 3

Course schedule

Unit 1: Solving equations numerically

After this unit, you should be able to
  1. Outline two kinds of methods that can be used to solve systems of equations on a computer
  2. Discuss the performance of these methods in terms of discretization error
  3. Implement one of these algorithms in Matlab to solve equations that arise in a physical application
Project 1: Ray tracing, due September 18

August 28: Chapter 1, section 1: Vectors, matrices, and Matlab
August 30: Chapter 3, section 1: Single equation iterations
September 4: Chapter 3, section 2: Single equations, Newton's method
September 6: Chapter 3, section 3: Systems of equations
September 11: No class (I am at a conference)
September 13: Chapter 3, section 3: Convergence for Newton's method

Unit 2: Interpolating and extrapolating

After this unit, you should be able to
  1. Explain what interpolation means for sets of data
  2. Describe the difference between interpolation and curve fitting
  3. Compute interpolation polynomials for small sets of data (by hand) and larger ones (by implementing a computer program)
Project 2: Image alignment, due October 4

September 18: Chapter 5, sections 0 and 1: Weierstrass approximation
September 20: Chapter 5, section 2: Interpolation with polynomials
September 25: Chapter 5, section 3: Least-squares polynomials
September 27: Chapter 5, section 3: continued
October 2: Chapter 5, section 4: Chebyshev polynomials

Unit 3: Fourier processing

After this unit, you should be able to
  1. Explain what features of a function are enhanced by the Fourier transform
  2. Explain the crucial insight that lead to the Fast Fourier transform
  3. Define the band pass, low pass and high pass filters
  4. Use the already-implemented functions in Matlab to develop an audio filtering processing chain
Project 3: Audio signal processing, due October 23

October 4: Chapter 5, section 5: Fourier series
October 9: Discrete Fourier transforms
October 11: Fast Fourier transforms
October 16: Filters for signals

October 18: Midterm Exam

Unit 4: Numerical differentiation

After this unit, you should be able to
  1. Discuss the benefits and costs of high-degree polynomials for interpolation in terms of functional variation
  2. Explain how the precise definition of interpolation methods leads to approximations of derivatives
  3. Discuss roundoff error and its implications for interpolation
Project 4: GPS tracks, due November 13

October 23: Chapter 6, section 1: Newton's interpolation polynomial
October 25: Chapter 6, section 2: Iterative linear interpolation
October 30: Chapter 6, section 3: Forward differences: formulae
November 1: Chapter 6, section 5: Numerical differentiation
November 6: Chapter 1, section 2: Floating point representation
November 8: Hacking session!

Unit 5: Numerical integration

After this unit, you should be able to
  1. Discuss how interpolation methods can be used to derive approximations for definite integrals
  2. Define Euler's method for solving first order differential systems
  3. Explain how difference method solvers are constructed, and how they propagate errors
Project 5: Riding a swing, due December 6

November 13: Chapter 7, section 1: Introduction to quadrature
November 15: Chapter 7, section 1: General error bounds for quadrature
November 27: Chapter 8, section 1: Euler's method
November 29: Chapter 8, section 2: Multistep solvers
December 4: Chapter 8, section 3: One-step solvers
December 6: Review for final exam

Final exam: December 13, 5:30-8:00pm

General comments on software and programming in the course

Generally speaking, knowledge of the general techniques of programming is expected, but I don't expect you to know the specifics of any particular language at the beginning of the course. There will be extensive programming required on the homeworks -- so you will be expected to know some basic programming when the course finishes.

If you don't have a strong preference, I will suggest that you learn some Matlab or Octave. I've heard that students can obtain Matlab relatively cheaply, though Octave is free to use. If you do have a strong preference for another programming language, you may be permitted to use it, but you must contact me first about it early in the course.

Matlab or GNU Octave Tutorials

I posted a short tutorial to BlackBoard that covers the basics of Matlab or Octave that you'll need in this course.

Relevant links

GNU Octave: http://www.gnu.org/software/octave/
Matlab: http://www.matlab.com/
Cleve Moler (the original author of Matlab) has written two books (Numerical computing with Matlab and Experiments with Matlab), freely available from http://www.mathworks.com/moler/, which serve as excellent introductions

Course policies

Exams

For each exam, you will be permitted to bring one 3"x5" index card with handwritten notes on it. Electronic calculators will not be permitted. However, mechanical calculators (such as this or these) are fine. Don't worry; I won't ask you about syntax on the exams! (You will be asked to provide precise algorithm descriptions in English, though.)

Absences

You are generally expected to attend the lectures. Please contact me in advance if you cannot attend, especially in the case of an exam. Late projects are not accepted, since they will be automatically collected through BlackBoard.

Grading

The course grade will be determined as follows:
25% Projects
25% Biweekly homework assignments
25% Midterm Exam
25% Final exam

Late homeworks will not be accepted, unless there is an official (University-approved) reason for doing so.

Academic dishonesty

Academic dishonesty is a serious offense. Read our University policies. As applied to this course, you may work together on homeworks, but the work you turn in must be your own. In so far as computer programs are concerned, you may not simply copy another student's program and put your name on it! I may use various technical countermeasures (for instance, MOSS http://theory.stanford.edu/~aiken/moss/) to detect instances of copied computer software. I am obligated to investigate suspected violations of academic integrity, and may ask you to explain or clarify sections of your program if I am unable to follow it.