# Basics of functional iteration

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.

• The orbit might be constant. Put another way, the initial seed never moved. This kind of point is called a fixed point. In the $$x^2$$ example, $$x_0=0$$ and $$x_0=1$$ are both fixed points.
• The orbit might converge to a point without ever hitting that limit exactly. In this case, the limit mut be a fixed point (assuming that $$f$$ is continuous). In the $$x^2$$ example with $$x_0=1/2$$ the orbit converges to the fixed point zero.
• The orbit might diverge to $$\infty$$. In the $$x^2$$ example with $$x_0=2$$ the orbit diverges quickly to $$\infty$$.
• The orbit might land on a fixed point exactly; then, of course, it must stay fixed. In the $$x^2$$ example with $$x_0=-1$$ the starting point moves directly to one and then stays there.
• The orbit might oscillate between two or three or even more points. Or the orbit might converge to points like this or even land on it exactly. This type of behavior is called periodic and we will take a closer look at it after we get a bit more experience.
• The orbit might meander quite aimlessly; this type of behavior is called chaotic.

### Problems

Here are a few iteration problems for you to try - by hand and (when necessary) by computational device.

1. $$f(x) = 2x + 1$$ with $$x_0=0$$
2. $$f(x) = x^2 - 1$$
1. with $$x_0=0$$
2. with $$x_0=1/2$$
3. with $$x_0=2$$
3. $$f(x) = x^2 - 2$$
1. with $$x_0=0$$
2. with $$x_0=1/2$$
3. with $$x_0=2$$
4. $$f(x) = \cos(x)$$ with $$x_0$$ equal to your favorite number.

After that, you might be ready to move to the computer.