Posted by: Gary Ernest Davis on: September 8, 2010

translation servicesTranslate | French translation Spanish translation translate German translate Chinese

This post is a slight variation on a theme of Cleve

Cleve uses MATLAB as the computational engine for his computational explorations. This makes sense because Cleve wrote the early versions of MATLAB to do numerical calculations, and the experiments in his book are, to some extent, a showcase and advertisement for MATLAB, suitable for school students and their teachers.

A drawback to using MATLAB is that it costs – currently $99 for US students.

There are many Open Source alternatives to MATLAB, at least for numerical computation.

For this project we will use a computational tool that, while lacking in high level numerical accuracy, is available to almost everyone: a spreadsheet.

If you do not have a spreadsheet on your computer you can use a Web-based spreadsheet at GoogleDocs, or download the freely available Open Office.

In the chapter on “Iteration” Cleve begins by repeatedly applying the function to a number. In fact, to be concrete, he starts by applying the function at and then repeatedly applies to the output. We can think of this schematically as follows:

We can do this easily in a spreadsheet, because a spreadsheet allows us to apply a formula to a previous output:

Starting value: x = | 3 | |

Number of times we apply the function F | Output | |

1 | 2 | |

2 | 1.732050808 | |

3 | 1.65289165 | |

4 | 1.628769981 | |

5 | 1.621348198 | |

6 | 1.619057812 | |

7 | 1.618350337 | |

8 | 1.618131743 | |

9 | 1.618064196 | |

10 | 1.618043323 | |

11 | 1.618036873 | |

12 | 1.61803488 | |

13 | 1.618034264 | |

14 | 1.618034074 | |

15 | 1.618034015 | |

16 | 1.618033997 | |

17 | 1.618033991 | |

18 | 1.61803399 | |

19 | 1.618033989 | |

20 | 1.618033989 | |

21 | 1.618033989 | |

22 | 1.618033989 | |

23 | 1.618033989 | |

24 | 1.618033989 | |

25 | 1.618033989 |

We see that after the iteration of the function the output does not change even in the decimal place.

A plot of the output versus the number of iterations of the function shows how rapidly the outputs approach the limiting value:

If you experiment with different starting values, other than 3, you will see that repeatedly applying the function to the output leads, after just a few iterations, to what seems to be the same decimal number.

An exception to this is if we choose a starting value less than -1, for example . For then, we would have to take the square root of a negative number (and to do this we would have to use complex numbers, and get into all sorts of hot water about which value of the square root to take).

When we carry out the iteration above we start with an input value, such as and get an output y-value .

We than use this output y-value as the new input x-value: . This, in turn, produces a new output y-value: .

We continue doing this – using the output y-value as the new input x-value – until the answer seems to stabilize.

There is a geometric way of seeing how this iteration process takes place, that helps us see how the output values stabilize.

Suppose we start with the x-value .

We draw the graphs of and :

Geometrically, we find the output y-value by drawing a vertical line from the input x-value, , up until it meets the (orange) graph of , and then drawing a horizontal line from that point to the vertical axis:

To take that output value as the input value we draw a horizontal line to the (blue) y=x line, and then drop a vertical line onto the x-axis:

By eliminating the repetitious drawing of lines to the y-axis and the x-axis we get the following cobweb diagram, which shows geometrically what the iterations of the function do to the starting point:

The iterates – the successive outputs – are converging rapidly to a number where . Using the formula for we see that the iterates converge to the solution of . Because this point of convergence is positive, this condition is equivalent to which tells us that the point of convergence is the positive root of the quadratic equation:

The quadratic formula tells us that this is .

Cleve mentions in his chapter on iteration that the equation for the fixed point of the function also satisfies as one easily sees by dividing the quadratic expression for by .

This double mention of on both sides of the expression allows us to write:

Applying that idea again we see that:

This makes it look like we should be able to write as an infinite continued fraction:

It is actually relatively easy to see that the fractions we get by terminating this infinite continued fraction at different points do converge to the positive root of .

These first few fractions are, successively:

The numerators and denominators of these approximating fractions should look familiar: they are just successive terms in the Fibonacci sequence

where if is the term of the sequence then

and

for .

Well I definitely liked studying it. This post offered by you is very useful for proper planning.

1 | Pancho

September 15, 2010 at 1:02 am

where’s dem wascally wabbits?