Off[General::spell1];

beginAssignment;

Iteration of real functions 1

Imagine a function f:R->R.  If you feed it a real number a it spits back another real number f[a]; if you feed it the real number f[a] it spits back the real number f[f[a]].  Keep applying f in this way and you generate a sequence of real numbers.  How do such sequences behave?  The answer is much more complex and more interesting than you may expect.  In this notebook we begin to explore the question by looking at some examples which behave very nicely.

The main Mathematica functions used in this Notebook are Nest and NestList.

?Nest

Clear[f]

Nest[f,a,3]

?NestList

NestList[f,a,3]

Example 1

We start with a familiar function.

square[x_]:=x^2

With this choice of the function f, our question comes down to this:  what happens to a number a if you keep squaring it?

NestList[square,a,5]

Let's try some different starting values a.  If we start with 2 the sequence diverges to infinity:

NestList[square,2,5]

If we start with 1/2 the sequence converges to 0:

NestList[square,1/2,5]

Think about what other possibilities there are.  Then enter the following cells:

NestList[square,.9999,20]

NestList[square,1.0001,20]

NestList[square,-.9999,20]

NestList[square,-1.0001,20]

We can now make a complete description of what happens to a number a when you keep squaring it:

For -1 <= a <= 1 the sequence of iterates converges to 0;
For a > 1 the sequence of iterates diverges to Infinity;
For a < -1 the sequence of iterates  diverges to Infinity.

If you know the relevant definitions concerning limits of sequences you should be able to prove these three assertions.  If not don't worry.

Notice that the numbers 0 and 1 are fixed points of the function square:

square[0]==0

square[1]==1

In fact, they are the only fixed points, as you can see by solving the equation x^2=x.

There is a significant difference between the two fixed points: numbers near to 0 move towards 0 when you repeatedly square them whereas numbers near to 1 move away from 1 when you repeatedly square them.  We say that 0 is an attracting fixed point of the function square, while 1 is a repelling fixed point.

Let's consider some other simple functions:

identity[x_]:=x

addOne[x_]:=x+1

negate[x_]:=-x

fun[x_]:=x/(x+1)

You can check whether a number is a fixed point of fun by substituting the number for $$$ below and then entering the cell:

fun[$$$]

Example 2

Lets's look at a more interesting function f:

Clear[f]

f[x_]:=2x/(x^2+1)

Before plotting any graph its a good idea to think about what the graph will look like.  That way you will have a better chance of spotting errors that might be made, either by you or by Mathematica..

Plot[f[x],{x,-5,5}]

What are the fixed points of f?  We can easily work that out.  They are the solutions of the equation x == 2x/(x^2+1) or, equivalently, in standard notation, of x3-x=0.  Solving we get  -1, 0 and 1.

NestList[f,-1,10]

Here is another way of looking at the iterates of f.

Plot[Evaluate[NestList[f,x,4]],{x,-5,5},PlotRange->{-1,1},PlotStyle->{Hue[0.`,1,1],Hue[0.1`,1,1],Hue[0.3`,1,1],Hue[0.6`,1,1],Hue[0.8`,1,1]}]

One of these curves is the function you get by iterating f four times.  Which one?  You can see that f[f[f[f[x]]]] is close to 1 if x>0 and close to -1 if x<0.  That should confirm your answers to the previous exercise.

Here's a similar picture for the function square.

Plot[Evaluate[NestList[square,x,4]],{x,-2,2},PlotRange->{-1,4},PlotStyle->{Hue[0.`,1,1],Hue[0.1`,1,1],Hue[0.3`,1,1],Hue[0.6`,1,1],Hue[0.8`,1,1]}]

You can see that square[square[square[square[x]]]] is close to 0 if -1<x<1 and is large if x<-1 or x>0.  We see again that 0 is an attracting fixed point of the function square, while 1 is a repelling fixed point.

Example 3

Here's another function that behaves well when you iterate it.

g[x_]:=(x+1)/x

NestList[g,-100.,20]

Try a few different starting numbers in the above cell and you'll see that the number 1.61803... acts magically to attract the iterates of g no matter where you start.  Its a special number, the unique fixed point of the function g, and its called the golden ratio.

theGoldenRatio = ($$$+Sqrt[$$$])/$$$

You can check your answer by entering the next cell:

Reduce[ g[theGoldenRatio]==theGoldenRatio ]

Here's a decimal approximation to theGoldenRatio:

N[theGoldenRatio]

After entering the following cell, try running it again with starting numbers other than 0.3.

ListPlot[NestList[g,0.3`,20],PlotRange->{-5,5},PlotStyle->Hue[0.`,1,1]]

We see again that the sequence of g-iterates of any number converges to theGoldenRatio.  There's a simple theorem underlying this phenomenon:

When repeated application of a continuous function f to some number a converges to a fixed number b, that number must be a solution of the equation f[x]=x.  Indeed:
                  b = lim fn[a] = lim fn+1[a] = f[lim fn[a]] = f[b].
This fact is turned on its head in the fixed point algorithm:  to solve the equation f[x]=x, repeatedly apply f to some initial value a.  This only works under special circumstances like those specified in the fixed point theorem.

Make sure you can see where the continuity of f is used in the above argument.  Note that f does not have to be continuous everywhere; all that is needed is that f is continuous near to b.

Example 4

NestList[Cos,-100.,20]

Here's a global picture of the iterates of Cos:

Plot[Evaluate[NestList[Cos,x,5]],{x,-2 π,2 π},PlotRange->{-1,1.5`},PlotStyle->{Hue[0.`,1,1],Hue[0.1`,1,1],Hue[0.2`,1,1],Hue[0.3`,1,1],Hue[0.6`,1,1],Hue[0.8`,1,1]},BaseStyle->{RGBColor[0.1`,0.2`,0.1`]}]

The successive iterates get closer and closer to being a constant function.  What constant?

Cobwebs

Fixed points of a function f satisfy the equation f[x]=x; hence they are precisely the x-coordinates of the points where the graph of f cuts the graph of the identity function.  For example, the following command produces graphs of both the cosine function and the identity function.  The picture shows us that Cos has exactly one fixed point.

Plot[{Cos[x],x},{x,-8,8}]

This brings us to yet another way of picturing what happens when you repeatedly apply a function to a number; its called a cobweb diagram.

The function we need for drawing cobwebs is defined under here.  There's no need to look at the definition unless you really want to.

The heart of the following is a function F that transforms lists in a certain way:
F[{a,b,c,d,e}]->{{a,b},{b,b},{b,c},{c,c},{c,d},{d,d},{d,e},{e,e}}

cobweb::usage = "
cobweb[function,start,numberOfSteps,xMin,xMax] 
generates a picture of numberOfSteps iterations of function, 
starting at the number start; the graph goes from 
xMin to xMax. cobweb[function,start,numberOfSteps] 
generates a picture of numberOfSteps iterations of function, 
starting at start; the graph goes from 0 to 1.";

cobweb[function_,start_,numberOfSteps_,xMin_:0.0,xMax_:1.0]:=
Module[{list,quad,points},
list=NestList[function,start,numberOfSteps];
quad[x_]:=Transpose[{x,x,x,x}];
points=
Partition[Flatten[Prepend[quad[Rest[list]],First[list]]],2];
Plot[{x,function[x]},{x,xMin,xMax},
PlotRange->{xMin,xMax},
AspectRatio->Automatic,
Epilog->{Hue[.0,1,1],PointSize[.03],
         Point[{start,function[start]}],Line[points]}] ]

?cobweb

cobweb[Cos,0.1,10,-3,3]

Starting at the large dot the cobweb goes repeatedly from a point on the graph of Cos to a point on the graph of the identity function.  The successive points are: 
{0.1,Cos[0.1]}, {Cos[0.1],Cos[0.1]}, 
{Cos[0.1],Cos[Cos[0.1]]},{Cos[0.1],Cos[Cos[0.1]]},
{Cos[Cos[0.1]],Cos[Cos[Cos[0.1]]]}, ...
Think about it and you will see that the x-coordinates of the vertical segments of the cobweb are the successive iterates of the starting number 0.1 under the function Cos (and so are the y-coordinates of the horizontal segments).

Here's what happens if you start at -2.

cobweb[Cos,-2,10,-3,3]

Zoom in:

cobweb[Cos,-2,10,0,1]

Zoom in again:

cobweb[Cos,-2,20,0.73,0.75]

One of those two 'straight lines' is the graph of the cosine function.  That's what it means for a function to be differentiable:  if you look at at a piece of its graph through a microscope the graph is straight.

What do the next two pictures tell us about the fixed point 1 of the function square?

cobweb[square,.999,12,-2,2]

cobweb[square,1.001,12,-1,10]

Let's ask Mathematica to remind us about two of the functions we defined:

?f

?g

You can use the following cell many times to look at the iterative behaviour of these functions from the point of view of cobwebs.

cobweb[f,.001,10,-2,2]

What next?

The behaviour of functions under iteration is not always so nice as for the examples we considered in this Notebook.  In other Oz MATH Notebooks we look at situations where the best word to describe the behaviour is chaos.  It's an important active research topic in mathematics.