Homework 1: Chaos or Exploring the Logistic Difference Equation

Background and Motivation

James Gleick's book Chaos: Making a New Science (Penguin Books, 1987) is a delightful account of the emerging science of ``chaos theory''. Chaos theory which is largely concerned with nonlinear systems, like our weather.

An early inspiration for chaos theory comes from biology (see pages 62-64 of Gleick's book). Biologists use the logistic difference equation to model the growth of a population over time. For simplicity, one can represent a population, say of fish in a pond, as a fraction between 0 and 1. The fraction 0 represents extinction, while 1 represents the greatest conceivable population of fish that will fit in the pond. A simple linear function, L(x) = r * x, that gives the population for the next year in terms of the current year's population, x, is inadequate, since it does not take limited resources into account. Instead, some biologists in the 1950s started to use a non-linear equation: the logistic difference equation:

P(r, x) = r * x * (1-x)

• this year's population, x,
• a parameter, r, which represents the amount of ``nonlinearity'', and
• a factor, 1-x, that keeps the population from getting too big.

For example, if r is 2.7 and the population at year 0 is 0.02. The population at year 1 is 0.05292 = 2.7 * 0.02 * (1 - 0.02). The population at year 2 is about 0.1353. If you keep computing, you'll see that the population eventually reaches an equilibrium of about 0.6296.

To describe the process more concisely, we'll introduce a bit of notation. The notation is for iterations of a binary function f. Let iterate(f,r,0,x) = x, and for all integers k > 0, let iterate(f,r,k,x) = f(r, iterate(f,r,k-1,x)). The claim above is that for sufficiently large k and x > 0, iterate(P,2.7,k,x) is approximately 0.6296.

Does iterating the logistic difference equation always converge on a equilibrium population? Surprisingly, the answer is no! This is what you will investigate in your homework.

What to Read

Read chapter 1, and refer to chapters 11 and 6 as needed in The Java Programming Language by Arnold and Gosling (Addison-Wesley, 1996).

Or read chapter 4 of Just Java by van der Linden (Prentice-Hall, 1997).

For reference, see also chapter 22 of The Java Language Specification by Gosling, Joy, and Steele (Addison-Wesley, 1996).

For information about running Java on the department machines, downloading, etc, see How to run Java at Iowa State, where you can also find links to other information about Java, including on-line tutorials.

Directions

This homework, like the others in this seminar, will be open-ended and somewhat ill-defined. we'll try to give you some idea of the difficulty/effort involved in each part. Do what you feel you have time for. For this first homework, I've chosen a very easy first part, since we'll be also learning Java syntax, and the Java compilers, linkers, etc. (Please do the entire first part before going on to the other parts).

The problems start out having you write programs. Eventually you can switch over to writing applets. It's best to do both, even if you don't get very far.

Bring a printout of your code to class, and be prepared to discuss it with other people in the class.

Problems

1. (easy) Write a program (application, not an applet) that reads a value for r and x from standard input and prints P(r,x) on standard output. If you have trouble with figuring out how to read a floating-point number from System.in, look in the course newsgroup for a hint.
2. (easy) Add error checking to your program; write error messages to standard error output and return a non-zero return code when your program detects an error or 0 if it worked okay. (These are standard Unix conventions).
3. (easy) Modify your program to prompt for the values of r and x.
4. (easy) Modify your program to take a number k, and print iterate(P,r,0,x), iterate(P,r,1,x), ..., iterate(P,r,k,x) writing the outputs one per line on standard output. Use your program to try larger and larger numbers for r. (Don't start with 100; start small, say around 2 and increase slowly so you can see what happens.) Can you see where the iterates no longer reach equilibrium? What do the iterates look like? What happens if you keep going higher?
5. (moderate) Write a program that searches for the smallest r for which P(r,x) does not reach equilibrium for a fixed x. (The value of x will be an input.) Be sure to watch out for infinite loops!
6. (moderate) This one is for efficiency nuts. Find out how to profile your java code. Where is most of the time being spent in your program? What algorithmic improvements can you make to improve it?
7. (moderate) This one is for numerical analysis buffs. What criteria are being used to decide on convergence in your program? Is the ultimate result affected by round-off errors? Try running your code using different precisions, and be sure to try this with values of r that produce chaos. What does the phrase ``sensitive dependence on initial conditions'' mean to you? (Harder: implement even larger precisions for floating point numbers as new C++ classes.)
8. (moderate) Change your program (at whatever stage) into an applet that prompts the user and writes to a window.
9. (harder) Write an applet that plots a graph of r versus the values of P(r,x) for a fixed initial population x. You'll have to use features of the AWT to do this.
10. (harder) Plot r versus the equilibrium value (or values) of the population.