Big Ideas

Big Ideas: numerical stability

I will talk about the concept of numerical stability in algorithms. This is closely related to the use of floating point numbers.

I will present some very simple algorithms to get the discussion going, and then I will explain the notion of stability in solving ordinary differential equations. Some notes for the first lecture on 2 Oct 06 are here (in PDF) Similar material can be found in chapter 8 of the book Analysis of Numerical Methods, by Isaacson and Keller, a Dover Book that is available for a reasonable price.

There is no simple starting point for the concept of stability, but one of the key papers often cited is by Courant, Friedrichs and Lewy. Here is a review of that paper, with a commentary on what followed, by Peter Lax.

An endpoint for these lectures is for you to read and appreciate the key points of the following paper which relates to a topic of current interest in CS/AI.

As time permits, I will present a very simple, yet unsolved, problem in numerical stability that relates to fluid flow. As a homework problem, I want you to investiage the stability of backwards differentiation methods. Somewhere between order (k) five and ten, the BDF(k) method goes unstable. That is, BDF(k) is stable and BDF(k+1) is unstable. I want you to find the value of k via two steps:

Show that the BDF(k) method computes the solution to y'=-y^2 as in the class demonstrations. In particular, you should copy and edit the code bdfthre.m and demonstrate that it works. Doing this in Matlab may be easier since it is a bit clearer how to export an image. Also, report the maximum error for the interval [0,1].
Prove that BDF(k+1) is unstable by exhibiting a root of the characteristic polynomial that is bigger than one in absolute magnitude. You can copy and edit the code plotpthrd.m as an aide.

You are free to look up anything you want on the web, but you must submit your own codes and coefficients for BDF(k+1). It is not sufficient to say that "so and so says it is unstable". Writing a code to generate the BDF coefficients is a very good idea. If you do, submit that code as well.

I would really prefer a complete write-up in a pdf document. It should include all codes, graphs and explanation of what is going on. You are welcome to play with all the codes I used in class, which I have put in the following tar file as an aide.