# Computation and the golden mean

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

Cleve Moler and the logo for Experiments with MATLAB

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.

#### Repeatedly applying a function to its own output

In the chapter on “Iteration” Cleve begins by repeatedly applying the function $F(x)=sqrt{1+x}$ to a number. In fact, to be concrete, he starts by applying the function $F$ at $x=3$ and then repeatedly applies $F$ to the output. We can think of this schematically as follows:

Repeatedly taking the output of the function and feeding it back as input.

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 $19^{th}$ iteration of the function $F$ the output does not change even in the $9^{th}$ decimal place.

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

#### (Almost) any starting value will give the same result

If you experiment with different starting values, other than 3, you will see that repeatedly applying the function $F(x)=sqrt{1+x}$ 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 $x=-2$. 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).

#### Cobwebs

When we carry out the iteration above we start with an input value, such as $x=3$ and get an output y-value $y=sqrt{1+3}=2$.

We than use this output y-value as the new input x-value: $x= 2$. This, in turn, produces a new output y-value: $y=sqrt{1+2}=sqrt{3}approx 1.732051$.

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 $x=2.5$.

We draw the graphs of  $y=sqrt{1+x}$ and $y=x$:

Geometrically, we find the output y-value by drawing a vertical line from the input x-value, $x=2.5$, up until it meets the (orange) graph of $F(x)=sqrt{1+x}$, 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 $F$ do to the starting point:

The iterates – the successive outputs – are converging rapidly to a number $phi$ where $F(phi)=phi$. Using the formula for $F(x)$ we see that the iterates converge to the solution of $sqrt{1+x}=x$. Because this point of convergence is positive, this condition is equivalent to $1+x=x^2$ which tells us that the point of convergence $x$ is the positive root of the quadratic equation:

$x^2-x-1=0$

The quadratic formula tells us that this is $phi=frac{1+sqrt{5}}{2} approx 1.618033989$.

#### Continued fraction

Cleve mentions in his chapter on iteration that the equation for the fixed point $phi$ of the function $F$ also satisfies $phi= 1+frac{1}{phi}$ as one easily sees by dividing the quadratic expression for $phi$ by $phi$.

This double mention of $phi$ on both sides of the expression $phi= 1+frac{1}{phi}$ allows us to write:

$phi=1+frac{1}{1+frac{1}{phi}}$

Applying that idea again we see that:

$phi=1+frac{1}{1+frac{1}{frac{1}{1+phi}}}$

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

$x=1+frac{1}{1+frac{1}{frac{1}{1+ldots}}}$

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 $x^2-x-1=0$.

These first few fractions are, successively:

$1=frac{1}{1}$

$1+frac{1}{1} =frac{2}{1}$

$1+frac{1}{1+frac{1}{1}}=frac{3}{2}$

$1+frac{1}{1+frac{1}{1+frac{1}{1}}}=frac{5}{3}$

$1+frac{1}{1+frac{1}{1+frac{1}{1+frac{1}{1}}}}=frac{8}{5}$

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

$1, 1, 2, 3, 5, 8, 13,ldots$

where if $F_n$ is the $n^{th}$ term of the sequence then

$F_0=1,F_1=1$

and

$F_n=F_{n-1}+F_{n-2}$

for $ngeq 2$.

### 2 Responses to "Computation and the golden mean"

where’s dem wascally wabbits?

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