 # Some things about iterative sequences

How would one, using only pen and paper, construct a sequence of rational numbers that approaches the number $\sqrt{2}$ ? This is not a simple question for many, as nowadays most people haven’t had to calculate approximations for square roots without a calculator. A simple way to solve this problem is by noting that, if x is any positive rational number, then the number $\sqrt{2}$ is always between the numbers x and 2/x. So, we can make the sequence by starting with $a_0 = 1$ and then calculating the number $a_n$ as the average value of $a_{n-1}$ and $2/a_{n-1}$: $a_1 = \frac{1}{2}(1 + \frac{2}{1}) = 3/2 = 1.5$ $a_2 = \frac{1}{2}(3/2 + 2/(3/2)) = 17/12 \approx 1.416666$ $a_3 = \frac{1}{2}(17/12 + 2/(17/12)) = 577/408 \approx 1.414216$

This sequence approaches the number $\sqrt{2} = 1.414213562$ rather quickly. The square root of some other integer m could be calculated with the same method by using the iteration rule $a_n = \frac{1}{2}(a_{n-1} + m/a_{n-1})$. This method also produces error bars for the approximate results, as we always have $a_n \leq \sqrt{m} \leq m/a_n$ or $m/a_n \leq \sqrt{m} \leq a_n$

More generally, if one wants to find an iterative sequence that approaches a number x that has some desired property described by the equation $f(x) = 0$, the iteration rules to try are of the form $a_n = a_{n-1} + cf(a_{n-1})$, where c is some positive or negative constant. Note that the number x is a “fixed point” of this iteration, which means that if for some n, the number $a_n$ is already exactly $a_n = x$, then all the numbers $a_k$ with k>n are equal to x.

Depending on the choice of the initial guess $a_0$ and the factor c, these iterations can converge towards the desired result either quickly (like the iteration for $\sqrt{2}$ above), slowly or not at all. Suppose we want to find a solution for the cubic equation $P(x) = x^3 + 3x^2 -3x - 9 = 0$ by iteration. If we try to set $a_0 = 1$ and $a_n = a_{n-1}+P(a_{n-1})$, we get the quickly diverging sequence $a_1 = -7$ $a_2 = -191$ $a_3 = -6858055$

and so on. If we choose $a_n = a_{n-1} + 0.1P(a_{n-1})$ instead, the sequence converges towards the solution $x = -\sqrt{3} \approx -1.732050808$, but rather slowly: $a_0 = 1$ $a_1 = 0.2$ $a_2 = -0.7472$ $a_3 = -1.29726$ $a_8 = -1.71421$

Sometimes this kind of iterations can also get “stuck in a loop”, bouncing between two values and not converging towards any number, like the sequence $a_0 = 1$, $a_1 = 2$, $a_2 = 1$, $a_3 = 2$, $a_4 = 1$, …

Sometimes the property that defines the number that we’re seeking is not defined by a polynomial equation. For example, the Lambert W function W(x) is defined by $x = W(x)e^{W(x)}$.

Obviously, if we want to find an approximation of W(x) for some x, we could try an iteration with rule $a_n = a_{n-1} + c(x-a_{n-1}e^{a_{n-1}})$ where c is some positive or negative number between -1 and 1. But this, of course doesn’t produce rational number approximations like the iterations in the examples above did. Other things that have to be calculated iteratively, are the solutions of transcendental equations like $e^x = 3x$, which appear in the quantum theory of finite potential wells and the analysis of nonlinear electronic circuits (those that have diodes or other nonlinear components in them).

So, if you have to keep a presentation about convergence and iterations in some maths course, playing with this kind of calculations is a good way to construct multiple example cases of slowly or quickly converging sequences!