Golden iteration

⋅

The expression

sqrt{1 + sqrt{1 + sqrt{1 + cdots}}}

converges to the golden ratio φ. Another way to say this is that the sequence defined by x0 = 1 and

x_{n+1} = sqrt{x_n + 1}

for n > 0 converges to φ. This post will be about how it converges.

I wrote a little script to look at the error in approximating φ by xn and noticed that the error is about three times smaller at each step. Here’s why that observation was correct.

The ratio of the error at one step to the error at the previous step is

frac{sqrt{x + 1} - varphi}{x - varphi}

If x = φ + ε the expression above becomes

frac{sqrt{varphi + epsilon + 1} - varphi}{epsilon} = frac{1}{sqrt{2(3 + sqrt{5})}} - frac{epsilon}{sqrt{8} (3 + sqrt{5})^{3/2}} + {cal O}(epsilon^2)

when you expand as a Taylor series in ε centered at 0. This says the error multiplied by a factor of about

frac{1}{sqrt{2(3 + sqrt{5})}} = 0.309016994ldots

at each step. The next term in the Taylor series is approximately −0.03ε, so the exact rate of convergence is a slightly faster at first, but essentially the error is multiplied by 0.309 at each iteration.

The post Golden iteration first appeared on John D. Cook.

Liked Liked