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!

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s