Functional iteration is a simple idea. We start with a function \(f:\mathbb R \to \mathbb R\). That funky notation simply means that \(f\) accepts real numbers and returns real numbers. A really simple example is \(f(x)=x+1\). To iterate the function, we start with an initial seed - let's say \(1\). We plug that number in to get a result - in this case \(2\). We then plug that number back into the function to get another result, 3 in our example, and we repeat the process ad infinitum - or until we get tired. Either way, we're interested in studying the list of numbers that we generate. In our example, we get exactly the positive integers - every number is exactly the previous number plus one.
Notationally, we call the starting point or initial seed \(x_0\). We call the first point generated by the function \(x_1\); the next point we call \(x_2\); etc. In general, we can write
\[x_{n+1} = f(x_n).\]As another example, we might let \(f(x)=x^2\) and \(x_0=1/2\). Then, the first few iterates are
\(n\) | 0 | 1 | 2 | 3 | 4 | 5 |
\(x_n\) | 1/2 | 1/4 | 1/16 | 1/256 | 1/65536 | 1/4294967296 |
Note that each number is exactly the previous number squared.
The sequence we generate this way is sometimes called the orbit. In this particular case, it looks like the orbit is converging rather rapidly to zero. That's the kind of behavior we want to be able to identify. There are a number of kinds of potential behavior, though.
Here are a few iteration problems for you to try - by hand and (when necessary) by computational device.
After that, you might be ready to move to the computer.