1
P0 /2
x
y
y = cos x
y = x
MATH 163, Spring 2001 Due Date: Name(s):
Honors Project 1b: Iteration and Chaos
The Iteration Method and Newton's Method are examples of first-order iterative processes. In general, a
first-order iterative process involves starting with a quantity x0, applying some function f to x0 to arrive at
a quantity x1 = f(x0), applying f to x1 to arrive at x2 = f(x1), and so forth. The numbers x0, x1, x2, . . .
form an infinite sequence, and we will have much more to say about infinite sequences in MATH 164. The
following command lines, for example, produce the first 20 terms in the infinite sequence
x0 = 0.5, xn+1 = f(xn) = cos xn, n = 0, 1, 2, . . . .
(These are the same numbers you would get if you were to enter 0.5 into a scientific hand calculator, and
repeatedly press the "cos" key 20 times!)
> restart:
> f := x -> cos(x);
> x0 := 0.5;
> for n from 1 to 20 do f(%); od;
One way to visualize a first-order iterative process is with cobweb
diagrams as follows (see the figure to the right):
1. The vertical line through P0(x0, 0) meets the graph of y = cos x at the point P1(x0, x1) whose ycoordinate
is x1 = f(x0); label P1 now.
2. The horizontal line through P1(x0, x1) meets the line whose equation is y = x at the point P2(x1, x1);
label P2 now.
3. The vertical line through P2(x1, x1) meets the graph of y = cos x at the point P3(x1, x2) whose ycoordinate
is x2 = f(x1); label P3 now.
4. The horizontal line through P3(x1, x2) meets the line whose equation is y = x at the point P4(x2, x2);
label P4 now.
We continue to repeat the steps described above over, and over again. Can you see the geometric pattern?
Starting from P0, we go vertically to curve, horizontally to line, vertically to curve, horizontally to line,
vertically to curve, ... . The "limit" of the points on the graph of y = cos x and on the line whose equation is
y = x, is the point of intersection of the graphs of y = x and y = cos x; hence, we might label it P(x, x).
(Cob-web diagrams get their name from their cob-web-like appearance.)
The following code creates a Maple graphic of the above construction.
> restart: with(plots):
> f := x -> cos(x);
> x0 := 0.5;
> a := [x0,x0,x0,f(x0)];
> S := [seq(op(map((f@@j),a)),j=0..20)]:
> A := plot({x,f(x)},x=0..1,thickness=2):
> B := pointplot(S,color=blue,connect=true):
> display({A,B});
One of the reasons people study cob-web diagrams is in the hope that they might provide insight into
the behavior of iterative processes: while a great deal is known about iterative processes, a great deal is
also unknown about them. To illustrate some of the the subtle behavior of iterative processes, consider the
first-order iterative process
x0 = a, xn+1 = f(xn) = kxn(1 - xn), n = 0, 1, 2, . . . . ()
If k = 4 then for some values of a  [0, 1], xn converges, for some it repeats, and for others it wanders
aimlessly over the interval [0, 1]. (This type of behavior is known as chaos. The study of chaos is important
since chaotic behavior arises not only in many areas of science and engineering, but also in areas as diverse
as medicine -- for example, in the study of dynamic blood diseases -- and economics.) If, on the other hand,
k = 3.839 then for any value of a  [0, 1], xn eventually settles down to cyclically repeating -- or orbit --
the three numbers 0.149888, 0.489172, and 0.959299. (This type of behavior is known as periodicity.)
Problems
1. Confirm the assertions made above about the behavior of (*) both numerically and geometrically.
2. What can be said about the behavior of (*) if f(x) = x2
- 1: What happens if a = 0 or 1? What
happens if a takes on any other value?
3. What can be said about the behavior of (*) if f(x) = x3
?