How to find periodic points non-algebraically

Question

For example, $f(x) = x - x^2$ by observation has a fixed point at $x = 0$, and an eventually periodic point at $x = 1$ (that goes to $0$). For the second iteration, to see if there's a periodic point of period $2$, we have to solve $f^2(x) = (x - x^2) - (x - x^2)^2 = x$, etc. for higher number periodic points. Instead of doing all this algebra, is there a way to figure out all the periodic points? What about some non-obvious functions, such as $f(x) = e^x$? We would have to iterate $e^{e^x}$, etc. and solve for $x = \ln(\ln(x))$, etc. and figuring out by observation what are the periodic points seem difficult.

Answer 1

Good question, but unfortunately there are very few quick and dirty techniques for finding periodic points. (I'm assuming your new to this study, but I'm also writing this for posterity, so don't feel offended if you feel like this is beneath you)

A periodic point is defined to be a point such that $f^n(x)=x$, where the exponent $n$ denotes function iteration (composition). The order of the period is given by the value n. It should also be noted that if a point $p$ is periodic so are the points $f^m(p)$ where $m$ is positive integer.

For instance, the function $f(x)=x-x^2$ has periodic points of order 1 that can be determined by finding values such that $x=x-x^2$. These values of x will always map onto themselves when inserted into $f(x)$. Solving in this case is easy, and we find that $x=0$ is the only periodic point of order 1, although its better to just call this a fixed point. To find eventually periodic points, you have to find values of x such that $f(x)=x_p$, where $x_p$ is a periodic point. In this case $0$ is the fixed point so solve $0=x-x^2$. We find that 1 is the only eventually periodic point of order 1 (I encourage you to ponder that last sentence for a moment. We can do very similar things to find the periodic and eventually periodic points of order, however you'll have to solve a quartic (4th order) equation to do so (recall that there is no general solution to polynomial equations of order 5 or above).

To discuss your question, there are methods to approximate periodic and eventually periodic points. One such method, is called Newton's method. It will find one solution (more on that in a minute) of a function $f(x)$.

$$x_{n+1}=x_n-{{f(x_n)} \over {f'(x_n)}}$$

To use the iteration, just manipulate the functions used above into a form such that $0=g(x)$ and then apply the method.

Newton's method only finds a single zero of a function. In addition, the method itself, is subject to periodic, chaotic, and non-convergent behaviors of its own, so fair estimates of the zeros need to made before applying the algorithm.