Off[General::spell1];

beginAssignment;

Iteration of real functions 2:
a fixed point theorem

The simplest thing a function can do to an input that it receives is to pass it on without changing it.  Such an input is called a fixed point of the function.  The concept is a very general one, and fixed point theorems are of importance in various parts of mathematics.  In this Notebook we meet a fixed point theorem for real functions.

The main Mathematica function used in this Notebook is NestList.

?NestList

NestList[Cos,a,3]

Fixed points of Cos

Look at the picture generated by the following input:

Plot[{Cos[x],x},{x,-2 π,2 π}]

Think about the point {x,y} where the two graphs cross. Necessarily y equals Cos[x] (because the point is on the graph of the cosine function) and y equals x (because the point is on the graph of the identity function).  Hence Cos[x] equals x.  In other word the number x is fixed under the function Cos; somewhat confusingly we call it a fixed point  of the function.   From the picture it appears, then, that the function Cos has a fixed point between 0 and 1.

A picture is not a proof.  How can we prove that Cos has a fixed point between 0 and 1?

Consider the function f given by

f[x_]:= Cos[x]-x

It is continuous, and satisfies

f[0.0]>0

and

f[1.0]<0

Hence, by the Intermediate Value Theorem, f has a zero between the numbers 0 and 1.  If L is the zero, then f[L]==0, or equivalently, Cos[L]==L.  Thus  L satisfies 0 <= L <= 1 and is fixed under Cos.

Exp[-1.0] - 1.0

Exp[-0.0] - 0.0

Plot[{Exp[-x],x},{x,0,1}]

Iteration of Cos

Here are the first fifty-one numbers that you get if you start with the number 0.5 and repeatedly apply the function Cos to it:

iteratates = NestList[Cos,0.5,50]

You can see that the sequence of iterates seems to converge.  Its limit will be closely approximated by:

Last[iteratates] // FullForm

The following calculation shows that this number is indeed very close to being a fixed point of Cos:

Cos[Last[iteratates]] - Last[iteratates]

We are looking at an example of a general 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].
Can you see where the continuity of f is used here?

A sequence is just a function on the natural numbers.  Hence it has a graph, like the following one, with a point on the graph corresponding to each natural number.

ListPlot[NestList[Cos,0.5`,50],PlotRange->{-1,1},PlotStyle->RGBColor[1,0,0]]

You can see the convergence.  Let's zoom in:

list1=ListPlot[NestList[Cos,0.5`,25],PlotRange->{0.73`,0.75`},PlotStyle->{RGBColor[1,0,0],PointSize[0.015`]}]

The terms of the sequence seem to alternate between being greater than the limit and being less than it.

Here are similar plots starting with -0.1 and 100.0.

list2=ListPlot[NestList[Cos,-0.1`,25],PlotRange->{0.73`,0.75`},PlotStyle->{RGBColor[0,0,1],PointSize[0.015`]}]

list3=ListPlot[NestList[Cos,100.`,25],PlotRange->{0.73`,0.75`},PlotStyle->{RGBColor[0,0.5`,0],PointSize[0.015`]}]

It looks as though all three limits are the same.  If we put the graphs on a single sheet that's very clear:

Show[{list1,list2,list3}]

As a matter of fact it does not matter what number you start with; the sequence of Cos-iterates always converges to that number 0.739085...   Try running the next cell with a few starting values different from 1993.0:

Nest[Cos,1993.0,200] // FullForm

A fixed point theorem

What we observed at the end of the previous section is no more than an experimental fact.  The very next starting number you try might give a completely different result.  In this section we will prove that this cannot happen.

Let a be any particular real number.  Consider the first few terms of the sequence (a , Cos[a] , Cos[Cos[a]] , ...).  We see that -1 ≤ Cos[a] ≤ 1 and hence 
0 ≤ Cos[Cos[a]] ≤ 1; can you see why?  Clearly all terms after the third one also lie between 0 and 1.

We are going to prove that the sequence (A1 , A2 , A3 , ...), where A1=a and,  for each n >1 , An= Cos[An-1], converges to L.  By the previous paragraph, we may assume without loss of generality that 0 ≤ a ≤ 1.  According to the Mean Value Theorem, there exists c in the interval (0,1) such that
		| An - L |   = | Cos[An-1] - Cos[L] | 
			 = | Cos'[c] | . | An-1 - L | 
			 = Sin[c] | An-1 - L |
			 ≤ K | An-1 - L |,
where K=Sin[1] (the maximum value of Sin on [0,1]).  Repeatedly applying this, we see that
		|An - L |  ≤ K | An-1 - L | 
	   		≤ K2  | An-2 - L | 
   			≤ ... 
  		 	≤ (K^(n-1)) | A1 - L |
			 -> 0   as n -> infinity, 
since 0<K<1 .  Thus the sequence converges to L .  Note that the limit is L , independently of the starting value A1= a.

The argument here only depends on certain features of the cosine function, and works for other functions with those features.  We have effectively proved a general fixed point theorem.  The proof does not merely establish that there exists a fixed point it shows how to calculate it: repeatedly apply f  to some initial value a .  That's called the fixed point algorithm.