# Fractals/Iterations in the complex plane/periodic points

How to describe a cycle ( periodic orbit)
* period
* stability of a periodic Orbit ( cycle)
* (cyclic) permutation
* basin of attraction

## period

Here period means period of iterated function (map).
Point z has period p under f if :
    $z:\ f^{p}(z)=z$
or in other notation:
    $z_{p}=z_{0}$
The smallest positive integer p satisfying the above is called the prime period or least period of the point z.

## equation and polynomial F

So equation for periodic points:
    $f^{p}(z)=z$
or in other notation
    $F^{p}(z)=f^{p}(z)-z=0$

### degree

Degree d of polynomial is the highest of the degrees of the polynomial's monomials (individual terms) with non-zero coefficients.
Degree of rational function is the higher value from the degree of numerator and denominator
In case of iterated quadratic polynomial :
    $d=deg(f^{p})==2^{p}$

# How to find periodic points for given period?

* an algorithm for computing the exact n-cycles of some polynomials maps

## Visual check

Visual check of critical orbit helps to:
* understand dynamics
* find periodic points
* period 1 orbit with slow dynamics
* period 3 parabolic orbit
* period 3 orbit

## Symbolic methods

Complex quadratic map

### Standard polynomial Fp which roots are periodic z-points of period p and its divisors

* math notation : $\ F_{p}(z,c)=f_{c}^{(p)}(z)-z$
* ggplot
* Maxima CAS function :

### Function for computing reduced polynomial Gp which roots are periodic z-points of period p without its divisors

* math definition : $G_{p}(z,c)={\frac {F_{p}(z,c)}{\prod _{m|p,m<p}G_{m}(z,c)}}\,$
* Maxima function:

##### Finding equations for periodic points
###### Standard equations

Equation for periodic point for period $p\,$ is :
$\ F_{p}(z,c)=0\,$
so in Maxima :
Degree of standard equations is $2^{p}\,$
These equations give periodic points for period p and its divisors. It is because these polynomials are product of lower period polynomials $G_{p}\,$:
so
$\ F_{1}(z,c)=z^{2}-z+c=G_{1}\,$
$\ F_{2}(z,c)=(z^{2}-z+c)*(z^{2}+z+c+1)=G_{1}*G_{2}\,$
$\ F_{3}(z,c)=(z^{2}-z+c)*(z^{6}+z^{5}+3*c*z^{4}+z^{4}+2*c*z^{3}+z^{3}+3*c^{2}*z^{2}+3*c*z^{2}+z^{2}+c^{2}*z+2*c*z+z+c^{3}+2*c^{2}+c+1)=G_{1}*G_{3}\,$
$\ F_{4}(z,c)=G_{1}*G_{2}*G_{4}\,$
$\ F_{5}(z,c)=G_{1}*G_{5}\,$
Standard equations can be reduced to equations $G_{p}\,$ giving periodic points for period p without its divisors.
See also : prime factors in wikipedia

###### Reduced equations

Reduced equation is
$G_{p}(z,c)=0\,$
so in Maxima gives :
| period | degree Fp | degree Gp |
| 1 | 2^1 = 2 | 2 |
| 2 | 2^2=4 | 2 |
| 3 | 2^3 = 8 | 6 |
| 4 | 2^4 = 16 | 12 |
| p | d = 2^p | |

##### Computing periodic points

Definition in wikipedia

###### Fixed points ( period = 1 )

Equation defining fixed points :
in Maxima :
Define c value
Compute fixed points
Find which is repelling :
Show that sum of fixed points is 1
Draw points :
One can add point z=1/2 to the lists:
In C :

###### period 2 points

Using non-reduced equation in Maxima CAS :
Show that z1+z2 = -1
Show that z2+z3=1
Reduced equation :
so standard coefficient names of single-variable quadratic polynomial
    $ax^{2}+bx+c$
are :
One can use the quadratic formula to find the exact solution ( roots of quadratic equation):
where :
Another formula can be used to solve square root of complex number "
$s={\sqrt {d}}={\sqrt {r}}{\frac {d+r}{|d+r|}}$
where :
    $r=|d|$
so

###### Period 3 points

In Maxima CAS

## Numerical methods

* wolframalpha

### Newton method
#### find one root
##### algorithm

For given ( and fixed = constant values):
* period p
* parameter c
* initial aproximation $z_{0}$ = initial value of Newton iteration
find one periodic point $z$ of complex quadratic polynomial $f$:
where
Note that periodic point $z$ is only one of p points of periodic cycle.
To find periodic point one have to solve equation ( = find a single zero of a function F):
Lets call left side of this equation (arbitrary name) function $F$:
Derivative of function $F$ with respect to variable z :
It can be checked using Maxima CAS:
Newton iteration is :
gives sequence of $z_{n}$ points:
       $z_{0}$
       $z_{1}=z_{0}-N_{p}(z_{0})$
       $z_{2}=z_{1}-N_{p}(z_{1})$
       $z_{n+1}=z_{n}-N_{p}(z_{n})$
where:
* n is a number of Newton iteration
* p is a period ( fixed positive integer)
* $z_{0}$ is an initial aproximation of periodic point
* $z_{n}$ is a final aproximation of periodic point
* $f_{p}(z_{n})$ is computed using quadratic iteration with $z_{n}$ as a starting point
* $f'_{p}(z_{n})$ is a value of first derivative . It computed using iteration
* $N_{p}$ is called Newton function. Sometimes different and shorter notation is used : $N_{p}(z_{n})=z_{n}-{\frac {F_{p}(z_{n})}{F'_{p}(z_{n})}}$

##### stoping criteria

* $\epsilon _{succes}$ : predefined accuracy threshold ( succes = converged )
* $n_{max}$ : maximal number of iterations ( fail to converge)
$\epsilon =|z_{n+1}-z_{n}|$
Usually one starts with :
for long double floating point number format

##### precision

Precision is proportional to the degree of polynomial F, which is proportional to the period p
so
| IEEE 754 - 2008 | Common name | C++ data type | Base $b$ | Precision $r$ | Machine epsilon = $b^{-(r-1)}$ |
| binary16 | half precision | short | 2 | 11 | 2$^{−10}$ ≈ 9.77e-04 |
| binary32 | single precision | float | 2 | 24 | 2$^{−23}$ ≈ 1.19e-07 |
| binary64 | double precision | double | 2 | 53 | 2$^{−52}$ ≈ 2.22e-16 |
| | extended precision | _float80 | 2 | 64 | 2$^{−63}$ ≈ 1.08e-19 |
| binary128 | quad(ruple) precision | _float128 | 2 | 113 | 2$^{−112}$ ≈ 1.93e-34 |
where :
* precision = number of fraction's binary digits
* accuracy < machine epsilon
Relation between accuracy and degree d:
* accuracy = 1/d
* accuracy = 1/(2 d log d)
Compare:
* precision for computing centers with Maxima CAS
* precision for zoom

##### code

* cpp from mandel

###### c

* m-attractor from mandelbrot-numerics library

###### Maxima CAS

output:

#### find all roots

Methods:
* The iterated refinement Newton method
* the Ehrlich-Aberth iteration ( Mpsolve )
Number:
* number of all roots = degree of polynomial ( Fundamental Theorem of Algebra )
* degree = $2^{p}$ where p is a period
| period | degree | number of all roots |
| 1 | 2^1 = 2 | 2 |
| 2 | 2^2=4 | 4 |
| 3 | 2^3 = 8 | 8 |
| p | d = 2^p | d |

##### test

"Viete tests on the roots found:
* if p is any polynomial of degree d and normalized (i.e. the leading coefficient is 1), then the sum of all roots of p must be equal to the negative of the coefficient of degree d − 1.
* Moreover, the product of the roots must be equal to (−1)^d times the constant coefficient. If one root vanishes, then the product of the remaining d − 1 roots is equal to (−1)^(d−1) times the linear term. "
$z_{1}+z_{2}+\dots +z_{d-1}+z_{d}=-{\dfrac {a_{d-1}}{a_{d}}}$
$z_{1}z_{2}\dots z_{d}=(-1)^{d}{\dfrac {a_{0}}{a_{d}}}$
"The sum of all roots should be 0 = the coefficient a of the degree d − 1 term of our polynomial. "
$a_{d-1}=0$
$a_{d}=1$
The constant term is a0. Its value depends on the period (degree).

###### example results

The equation for period p=2 cycle is :
so d-1 = 3 coefficient is 0
$a_{d-1}=a_{3}=0$
$a_{0}=c^{2}+c$
Degree d :
The four roots for c= -0.965 + 0.085*i are :
their sum is :
their product :
So results have passed Viete's tests

# How to compute stability of periodic point ?
## stability of periodic points (orbit) - multiplier

The multiplier (or eigenvalue, derivative) $m(f^{p},z_{0})=\lambda \,$ of a rational map $f\,$ iterated $p$ times at cyclic point $z_{0}\,$is defined as:
    $m(f^{p},z_{0})=\lambda ={\begin{cases}f^{p\prime }(z_{0}),&{\mbox{if }}z_{0}\neq \infty \\{\frac {1}{f^{p\prime }(z_{0})}},&{\mbox{if }}z_{0}=\infty \end{cases}}$
where $f^{p\prime }(z_{0})$ is the first derivative of$\ f^{p}$ with respect to $z\,$ at $z_{0}$.
Because the multiplier is the same at all periodic points on a given orbit, it is called a multiplier of the periodic orbit.
The multiplier is:
* a complex number;
* invariant under conjugation of any rational map at its fixed point;
* used to check stability of periodic (also fixed) points with stability index $abs(\lambda ).\,$
A periodic point is
* attracting when $abs(\lambda )<1;\,$
** super-attracting when $abs(\lambda )=0;\,$
** attracting but not super-attracting when $0<abs(\lambda )<1;\,$
* indifferent ( neutral) when $abs(\lambda )=1;\,$
** rationally indifferent or parabolic or weakly attractive if $\lambda \,$ is a root of unity;
** irrationally indifferent if $abs(\lambda )=1\,$ but multiplier is not a root of unity;
* repelling when $abs(\lambda )>1.\,$
Periodic points
* that are attracting are always in the Fatou set
* that are repelling are in the Julia set;
* that are indifferent fixed points may be in one or the other. A parabolic periodic point is in the Julia set.

## code
### Maxima CAS

results:

# How to compute period of given periodic point ?

How is it possible to calculate the true period?
* Robert Munafo's polygon iteration method described in Mu-Ency
* Knighty's Taylor ball iteration method
Both find the lowest period nucleus in a region. If there is no nucleus in the region (either 100% exterior, or 100% interior not surrounding a nucleus) then I don't know what happens.
The polygon method can be adapted to pre-periodic Misiurewicz points. Probably the Taylor ball method can be too. A version of the ball method can be adapted to Burning Ship etc. using Jacobians, where the polygon method can sometimes fail due to early folds.

## marcm200

( marcm200)

## Knighty's Taylor ball iteration method

Finding the roots of the SA polynomial as suggested by knightly is a totally different approach. Which of the many polynomial root finding algorithms do you use?
You can take a look at the codes attached to below programs
* mandelroots program by Knighty
* SuperMB program by Knighty
See this note

# How to find basin of attracting point ?

* The Newton-Raphson fractal

# What is the relation between Julia set and periodic point ?

* Parameter-Plane Dynamics of Fixed Points and Their Preimages For Standard Quadratic Julia Sets
* Quadratic Julia sets and periodic cycles

# See also

* critical_orbit in wikibooks

# code

* On a method for detecting periods and repeating patterns in time series data with autocorrelation and function approximation Author: Tim Breitenbach a b, Bartosz Wilkusz b, Lauritz Rasbach b, Patrick Jahnke
** Lauritz R: period-detection in python
** python period-detection

# References

* ↑ Very badly ordered cycles of interval maps by Sourav Bhattacharya, Alexander Blokh
* ↑ Periodic_point in wikipedia
* ↑ Period of critical orbit with slow dynamics
* ↑ Numerical Methods for Finding Periodic Orbits at Scholarpedia
* ↑ Fixed points in ggplot2 by Eric
* ↑ wikipedia : Periodic_points_of_complex_quadratic_mappings#Finite_fixed_points
* ↑ wikipedia : Quadratic function
* ↑ math.stackexchange question : how-to-find-the-solution-of-a-quadratic-equation-with-complex-coefficients
* ↑ wikipedia : Quadratic equation
* ↑ math.stackexchange question how-do-i-get-the-square-root-of-a-complex-number
* ↑ Newton's method in practice: finding all roots of polynomials of degree one million efficiently Dierk Schleicher, Robin Stoll
* 1 2 Floating Types - Using the GNU Compiler Collection (GCC)
* 1 2 Newton's method in practice II: The iterated refinement Newton method and near-optimal complexity for finding all roots of some polynomials of very large degrees by Robin Stoll, Dierk Schleicher
* ↑ wikipedia : MPSolve
* ↑ wikipedia : Vieta's formulas
* ↑ Newton's method in practice: finding all roots of polynomials of degree one million efficiently by Dierk Schleicher, Robin Stoll
* ↑ Alan F. Beardon, Iteration of Rational Functions, Springer 1991, ISBN 0-387-95151-2, p. 41
* ↑ Alan F. Beardon, Iteration of Rational Functions, Springer 1991, ISBN 0-387-95151-2, page 99
* ↑ Monireh Akbari, Maryam Rabii, Real cubic polynomials with a fixed point of multiplicity two, Indagationes Mathematicae, Volume 26, Issue 1, 2015, Pages 64-74, ISSN 0019-3577, https://doi.org/10.1016/j.indag.2014.06.001. (https://www.sciencedirect.com/science/article/pii/S0019357714000536) Abstract: The aim of this paper is to study the dynamics of the real cubic polynomials that have a fixed point of multiplicity two. Such polynomials are conjugate to fa(x)=ax2(x−1)+x, a≠0. We will show that when a>0 and x≠1, then |fan(x)| converges to 0 or ∞ and, if a<0 and a belongs to a special subset of the parameter space, then there is a closed invariant subset Λa of R on which fa is chaotic. Keywords: Multiplicity; Chaotic; Cubic polynomial; Schwarzian derivative
* ↑ Some Julia sets by Michael Becker