
Iterative Functions and the HP48, Part 1

A look at the remarkable effects that can happen when you repeatedly
give a function its own output (the foundation of chaos/fractal theory),
some sobering facts on calculator precision, and lots of demo programs
for the HP48.
                                       (c) Bill Markwick, Revised May/99
                                           bd628@torfree.net


       Brief Table of Contents
       -----------------------

       Part 1
       ------

       1.0  Introduction to Iterative Function Systems (IFS)
       1.1  Newton's Method - Program: NEWT
       1.2  Precision versus Accuracy - Program: PRDEMO
       1.3  Notation
       1.4  Attracting and Repelling
       1.5  N-cycles

       Part 2
       ------

       2.1  Verhulst's Logistics Function
       2.2  Dynamic Conditions - Program: DOTS
       2.3  Bifurcations
       2.4  Orbit Animation - Program: STAIRS
       2.5  Using Other Expressions - Programs: STA2, CANT

       Part 3
       ------

       3.1  Feigenbaum and Bifurcations - Program: FEIG
       3.2  Full Screen Version
       3.3  Feigenbaum's Number
       3.4  Sierpinski's Gasket - Programs: GASK, SWALL
       3.5  Pascal's Triangle - Programs: BNOM1, BNOM2
       3.6  Pascal Meets Sierpinski - Program: PASC
       ---  References


1.0 Introduction to Iterative Function Systems (IFS)
----------------------------------------------------

If you set radian mode, enter any small number (3, say), and repeatedly
press COS a whole bunch of times, you'll eventually start seeing numbers
beginning with .739. If you have nothing to do today, press COS 70 times
and you'll be at the number .739085133215. Further presses have no
effect, and neither does pressing ACOS. Also, it doesn't seem to matter
what the starting number is, as long as you're willing to do those 70
keypresses. You always get .739085133215. What's going on?

What's happening is that by hooking the COS function's output to its
input, you have generated a series of numbers, called an "orbit", that's
heading for a final value called a "fixed point", or FP. The FP, if it
exists, is defined as the point on the function's curve where f(X) = X.
It's easy enough to solve for the FP with f(X)-X = 0, and you'll get the
above number.

Another, graphical way of demonstrating the fixed point: since X = f(X)
and y = f(X), then y = X; ie, the FP lies at (X,X). If you join the
point (X,X) with the origin, you've just drawn the line y = X. You could
therefore plot the function along with y = X; the FP will be at the
intersection. Try storing this in EQ and plotting it with the default
settings (and radian mode - radians are assumed throughout the article):

     { 'COS(X)' 'X' }

  (Please note that I haven't translated small programs' HP48 symbols
   because it's faster to type them in than to transfer them.)

You can use zooming and the plotter's (x,y) coordinate display to
confirm that the intersection of the cosine function and y = X (called
the "bisector") lies at (.74,.74), which is close enough to the .739
number without a lot of zooms.

Another one: repeated pressings of SIN for any input will make it head
towards zero, its only FP, although it will take many thousands of
keypresses. You can do this if you want to - drop us a line from time to
time and let us know how close you're getting. The orbit of a sine turns
up again later in the section on the STA2 program that tracks the orbit
graphically.


1.1 Newton's Method
-------------------

The direct iterative method is obviously a slow way to get anywhere.
Newton realized this (along with, apparently, everything else worth
knowing, and all at once, too) and he formalized an iterative function
that had been around for a while, making it really efficient by using
the derivative:

     Xn+1 = Xn - ( f(Xn) / f'(Xn) )

You don't really need the following program, since anything it can do
can be done by the HP48's built-in functions, but it's a good
demonstrator of the power of the IFS. It converges to the answer in a
remarkably short time; it can take SIN(X) to zero from a guess of 1 in
only 5 iterations.

Since its purpose is to find a value that yields f(X) = 0, it's great
for finding a root. As for multiple roots - how it deals with those is a
subject for another article (or a book about fractals). In the meantime,
we'll use it to show what you can do when you feed an output back to an
input.


Program: NEWTM   Finds X for f(X)=0, for any f   Execution time: varies

%%HP: T(3)A(R)F(.);
\<< DUP 'X' \.d \-> n f d    @ Dupe the function, enter 'X' and find the
  \<< 1 n                    @ derivative; n=number of iterations,
    FOR N \-> x              @ f=function, d=derivative, x=guess.
      \<< 'x-f/d'
EVAL 'X' x 2 \->LIST         @ Solve for X using the "where" command
| DUP                        @ and put the answer on the stack.
      \>>
    NEXT DROP                @ Use the answer as input for another pass.
  \>>                        @ Leave all iteration results on the stack.
\>>

  Stack:
  level 3: the initial guess X0
  level 2: the number of iterations
  level 1: the function (must be in X)


It isn't foolproof, as you'll probably find out if you try it enough. If
the derivative is zero, you'll get an error message. If the guess X0 is
too far away, it might appear to fail. Sometimes it *has* failed, but
sometimes it just needs a better guess, or more iterations.

Here's an example shoplifted from Al Shenk's book (see References at the
end of the article).

  level 3: 10
  level 2: 10
  level 1: 'X^3-3*X^2+5'

With the above inputs, NEWTM gives 2.8395..., which is a long way from
the expected root of approximately -1.1. Raising the iterations to 25
gets there correctly. A guess of -5 arrives in 7 iterations.

If you use NEWTM to solve 'SIN(X)-X' to find the expected FP of 0 (see
preceding section), you'll get a very small number, but not zero. It
runs out of digits within a few passes, and repeats this number over and
over (the Leftshift-Solve-Solve Equation function returns the answer of
zero right away). This leads into precision versus accuracy.


1.2 Precision versus Accuracy
-----------------------------

Precision is the maximum number of digits you can calculate with, and
accuracy is how many of those digits are correct. You can find other
definitions in math dictionaries, but this one particularly suits our
purposes. There's a drawback to iterative functions that can have
serious or subtle effects, depending on circumstances. All calculators
and computers work with a limited number of digits ("fixed precision");
the HP48 uses 12. If the iterative process should make numbers grow
rapidly, errors due to roundoff can occur without announcing themselves.

Even something as simple as X^2 can lead to roundoff very quickly. Try
putting a short version of pi, 3.14, on the stack and pressing the X^2
key repeatedly. In only three presses, you'll be at 9450.11698108 -
twelve digits. Roundoff is now inevitable on the next squaring.
  Of course, you could say that this doesn't matter since you only
started with two decimal places, but the many passes of an IFS can
result in significant errors, as you'll see below.

Sometimes the effects can go from subtle to weird. I lifted the following
demonstration from "Chaos and Fractals" by Heinz-Otto Peitgen et al (who
*is* that guy Al? He's written some great stuff). See the book listing
at the end of the article.

Key in or transfer the following program if you want to, though I've
summarized the results in a following table.


Program: PRDEMO   Demonstrates errors in precision   Execution time: varies

%%HP: T(3)A(R)F(.);     @ Iterates expression for N passes and
\<< \-> N               @ P = start number.
  \<< 1 N               @ For demo of accuracy, compare using
    FOR N \-> P 'P+3*   @ start of .01 and 10, 20, 30, 40
P*(1-P)' EVAL           @ and 50 iterations.
    NEXT                @ Then user replaces expression with '4*P-3*P^2'
  \>>                   @ and repeats test.
\>>

  Stack:
  level 2: .01
  level 1: number of iterations

The demonstration test takes two runs. The first uses the program as it
is above. The second requires you to replace the expression in quote
marks with '4*P-3*P^2', which is exactly the same thing mathematically,
but with terms multiplied out. Both use .01 as an initial value.

Here's what you'll get, slightly condensed to save typing:


     Iterations   'P+3*P*(1-P)'  '4*P-3*P^2'
     ----------   -------------  -----------
         1           .0397          .0397
        10           .722914        .722914
        20           .596528 <--    .596529 <--
        30           .374647        .374647
        40           .143971       6.580924
        50           .225758        .007312


You can see from the above arrows that roundoff problems begin fairly
early and get pretty serious pretty fast (note that the .596529 oddity
in the right column is one-time - the next numbers agree). Which output
is correct? That's a good question; perhaps neither one. Why did two
mathematically identical functions suffer from different roundoff errors?
The answer is known only to those who understand the finer points of
efficient algorithms. But you see the point: Caveat iterator.

  Important note: the above is not meant to be a criticism of the HP48
  internals. All calculators and computers have similar limits on their
  accuracy unless special higher-precision software can be used.

At the end of the article, roundoff error will turn up in a demonstrator
program that shows a simple fractal coming unglued.


1.3 Notation
------------

If you enter an initial number X0 and solve a function for that number,
you're really finding f(X0). Run the function on this new output and
you'll have f(f(X0)), and then f(f(f(X0))), etc. A widely-used notation:

  f[n](X0) is the nth iterate of X0 for the function f.

The [n] should be a superscript and is sometimes seen as (n);
confusingly, sometimes there are no parentheses at all, making it look
like a power. An example of bracketed notation:

  For function X^2 and X0 = 2, then f[3](X0) = 256, or f[3](2) = 256.
    The orbit is X0, X1, X2, X3, which is 2, 4, 16, 256.

Other: I generally use "X" to represent an element in an iterative
series and "x" or "y" to refer to its plotted coordinates. Since (-1,1)
can refer to either coordinates or an open interval, I'll be sure to put
the word "interval" in front to avoid confusion. As for all my other
stuff that causes confusion, not much I can do at this stage.


1.4 Attracting and Repelling
----------------------------

Sometimes you can start an iterative series knowing that it's going to
go somewhere, if slowly, as with our sine and cosine examples. In other
cases, the output numbers take off wildly, perhaps for plus or minus
infinity (said to be "escaping" iterates). Often such results depend on
the value of the starting number.

Iterating X^2 around the interval (0,1) gives an example.

     << -> X 'X^2' >>

  Incidentally, the HP48 will write the above program for you. Put this
  on the stack, where "name" is your name for the variable:

     'name(X)=X^2'

  and press DEF. The program is now in the variable "name".

For any initial number between 0 and 1 exclusive, the output grows
smaller and is steering for zero. It's fixed for X0 = 0 and X0 = 1, with
outputs that stay at 0 or 1 regardless of the number of iterations. For
numbers greater than one, the output rapidly grows towards infinity.

Zero is called an "attracting point" or "attractor" for all numbers in
the open interval (0,1) (memory-jogger: an open interval excludes the
endpoints, in this case 0 and 1). It's also one of the fixed points of
X^2.

The other fixed point of X^2 is (1,1). It's considered to be repelling -
although f(1) won't go anywhere if you iterate it, as soon as you get
above 1, the output rapidly increases towards infinity. And of course,
as soon as you get below 1, it's on its way to zero. In other words,
there's no orbit that will get you to 1  - unless you enter it directly
as X0. In that case, the function goes straight to the FP and sticks
there (I suppose you could say that the FP is attracting for its own
value and repelling for all other numbers). Part 2 has a program that
will show this graphically (STA2).

There's a rule for determining whether a point P is attracting or
repelling. Find the expression's derivative, solve for the point in
question, and take the absolute value. If:

     | f'(P) | < 1  the point attracts iterates
     | f'(P) | > 1  the point repels iterates
     | f'(P) | = 1  indeterminate - can be either or neither

Taking our example X^2: the derivative is 2*X. The fixed point at X = 1
has an absolute value of 2*1 = 2. Therefore (1,1) is repelling.
Similarly, f'(0) is zero, so it's attracting.

And finally: for X^2, any number between -1 and 1 (exclusive) will
generate an orbit that heads to the attractor 0 (negative signs
disappear with the first squaring). The open interval (-1,1) is called
the "basin of attraction" for 0, and its notation is B0, or Bp for any
point p.

The new terminology can get a little strange. Here's my guess as to
where "basin" came from:

       * plot 'X^2' with the defaults
       * move the cursor left to (-1,0)
       * press the "times" key to set a mark
       * move the cursor right to (1,0)
       * press FCN and Shade
       * there be yer basin, guv, sorta.

Basins of attraction play an important part in fractals - the basins for
Newton's Method as it searches for complex roots is a favorite
demonstrator.


1.5 An N-cycle Built for Two
----------------------------

Not all iterative functions have a fixed point; X^2 + 1 will go to
infinity for any real number. If you plot { 'X^2+1' 'X' }, you'll see
that the curve misses the bisector entirely. In other cases, a function
will endlessly cycle between two values:

   Given the X0 value of 1 or -1, -X^3 will oscillate forever
   between the two.

   For X0 = 1 or -1, X^2-1 will oscillate between 0 and -1.

The two cases above are called 2-cycles since they switch between two
points, while other functions may be 3-cycle in nature and so on; the
general term is "n-cycle". The points 1 and -1 are called "periodic
points", since they lead the function into periodic behavior. If you
start X^2-1 with 5, say, it doesn't show periodic behavior, but just
goes off to infinity.

If you plot { 'X^2-1' 'X' } you'll see two fixed points, one at 1.618033
and the other at -.618033, which you can determine by solving 'X^2-1-X'
as described earlier on. The derivative rule shows that both points are
repelling.

         << -> X 'X^2-1' >>

Experiment with various values of X0 and as many iterations as your
key-pushing finger can stand (we automate this in the next few sections
of Part 2). Some produce the 2-cycle behavior and some go to infinity
(or really, MAXR on the HP48). The basin of attraction is the closed
interval [-1.61803398875, 1.61803398875]. I admit that I found Bp
empirically - I haven't yet absorbed a good method for finding it
otherwise. Stay tuned.

We've come to the end of Part 1. In Part 2, we finally get to the good
stuff - HP48 graphics -  as we wring out more iterative functions.

Bill Markwick
Toronto, Ontario, Canada
bd628@torfree.net

