2

If we have a function, say:

$$ f(x) = 3x $$

We can get output values based on linearly increasing input:

$$ f(1) = 3(1) = 3 $$ $$ f(2) = 3(2) = 6 $$ $$ f(3) = 3(3) = 9 $$ $$ ... $$

Or, we can "iteratate" over the function, by taking the last output as input:

$$ f(1) = 3(1) = 3 $$ $$ f(3) = 3(3) = 9 $$ $$ f(9) = 3(9) = 27 $$ $$ ... $$

But this is essentially equivalent to:

$$ f(x) = 3^x $$

So why iterate over a function when we can just define it in another way?

Is defining a function to be iterated over easier than defining for linear input?

Are there functions that cannot be defined a different way?

What is the practical purpose of iteration (eg. is there a branch of mathematics in which this is useful)?

kukac67
  • 303
  • 3
    The theory of dynamial systems is, in part, the study of iterations of functions. – Mariano Suárez-Álvarez Apr 12 '14 at 20:18
  • 1
    There is no reason to suspect iteration will be so nicely behaved for every function. In particular, a function might be defined in parts. For example, see the Collatz Function – Joseph Zambrano Apr 12 '14 at 20:20
  • 1
    There are many natural and interesting examples of functions which are defined by iteration. They may or may not have a simple formula, and it can be hard to tell. A good example is the Fibonacci sequence:

    $,,, f(1)=1, , f(2)=1, , f(n)=f(n-1)+f(n-2)$ for integers $n \ge 3$.

    This one does have a simple formula, but it is a rather astonishing one and one would not expect it to be true.

     – Lee Mosher Apr 12 '14 at 20:22

1 Answers1

3

Iteration of functions is an extremely useful technique in general. For ex. suppose we wish to find the square root of a number $a$. Then we start with an initial guess $x_0>0$ and use the following iteration $$f(x) = \frac{1}{2} \left( x + \frac{a}{x} \right)$$ Let's consider an example and try finding the square root of $2$ using this method. Start with a wild guess of say $x=100$. Then we obtain the following numbers after performing the iterations $$ 50.01$$ $$25.024996$$ $$12.55245805$$ $$6.355894695$$ $$3.335281609$$ $$1.967465562$$ $$1.49200089$$ $$1.416241332$$ $$1.414215014$$ $$1.414213562$$

This iteration converges rapidly to $\sqrt{2}$. Infact this algorithm dates back to the Babylonian era.

This was just one of the infinitely many applications of iterated functions and they are the starting point of the theory of dynamical systems and fractals.

Sandeep Thilakan
  • 2,271
  • I like the root 2 function! I suppose it is a function that cannot (easily at least) be defined for linear input (although in this case I guess that would be useless). – kukac67 Apr 12 '14 at 20:47