Fractals/Iterations in the complex plane/q-iterations

< Fractals


Julia set drawn by inverse iteration of critical orbit ( in case of Siegel disc )
Periodic external rays of dynamic plane made with backward iteration

Iteration in mathematics refer to the process of iterating a function i.e. applying a function repeatedly, using the output from one iteration as the input to the next.[1] Iteration of apparently simple functions can produce complex behaviours and difficult problems.

One can make inverse ( backward iteration) :

  • of repeller for drawing Julia set ( IIM/J)[2]
  • of circle outside Jlia set (radius=ER) for drawing level curves of escape time ( which tend to Julia set)[3]
  • of circle inside Julia set (radius=AR) for drawing level curves of attract time ( which tend to Julia set)[4]
  • of critical orbit ( in Siegel disc case) for drawing Julia set ( probably only in case of Goldem Mean )
  • for drawing external ray

Repellor for forward iteration is attractor for backward iteration


Move during iteration in case of complex quadratic polynomial is complex. It consists of 2 moves :

  • angular move = rotation ( see doubling map)
  • radial move ( see external and internal rays, invariant curves )
    • fallin into target set and attractor ( in hyperbolic and parabolic case )



Backward iteration or inverse iteration


One can iterate ad infinitum. Test tells when one can stop

  • bailout test for forward iteration

Target set or trapEdit

Target set is used in test. When zn is inside target set then one can stop the iterations.


Dynamic plane f_0 for c=0Edit

Equipotential curves (in red) and integral curves (in blue) of a radial vector field with the potential function \phi(x,y) = \sqrt{x^2+y^2}

Lets take c=0, then one can call dynamical plane f_0 plane.

Here dynamical plane can be divided into :

  • Julia set =  \{  z : |z| = 1 \}
  • Fatou set which consists of 2 subsets :
    • interior of Julia set = basin of attraction of finite attractor =  \{  z : |z| < 1 \}
    • exterior of Julia set = basin of attraction of infinity =  \{  z : |z| > 1 \}

Forward iterationEdit

The 10 first powers of a complex number inside the unit circle
Exponential spirals
Principle branch of arg

z = r e^{i \theta} \,

where :

  • r is the absolute value or modulus or magnitude of a complex number z = x + i
  • \theta is the argument of complex number z (in many applications referred to as the "phase") is the angle of the radius with the positive real axis. Usually principal value is used


\theta = \arg(z) = \operatorname{atan2}(y,x) =
\arctan(\frac{y}{x}) & \mbox{if } x > 0 \\
\arctan(\frac{y}{x}) + \pi & \mbox{if } x < 0  \mbox{ and } y \ge 0\\
\arctan(\frac{y}{x}) - \pi & \mbox{if } x < 0 \mbox{ and } y < 0\\
\frac{\pi}{2} & \mbox{if } x = 0 \mbox{ and } y > 0\\
-\frac{\pi}{2} & \mbox{if } x = 0 \mbox{ and } y < 0\\
\mbox{indeterminate } & \mbox{if } x = 0 \mbox{ and } y = 0.


f_0(z) = z^2 = (r e^{i \theta})^2 = r^2  e^{i 2 \theta}\,

and forward iteration :[5]

f^n_0(z) =  r^{2^n}  e^{i 2^n \theta}\,

Forward iteration gives forward orbit = list of points {z0, z1, z2, z3... , zn} which lays on exponential spirals.[6] [7]

Escape testEdit

If distance between point z of exterior of Julia set and Julia set is :

distance(z, J_c) = 2^{-n} 

then point escapes ( measured using bailout test and escape time )

|z_n| > ER 

after :

See here for the precision needed for escape test

Backward iterationEdit

Backward iteration of complex quadratic polynomial with proper chose of the preimage

Every angle α ∈ R/Z measured in turns has :

  • one image = 2α mod 1 under doubling map
  • "two preimages under the doubling map: α/2 and (α + 1)/2." [9]. Inverse of doubling map is multivalued function.

Note that difference between these 2 preimages

\frac{\alpha}{2} - \frac{\alpha +1}{2} = \frac{1}{2}

is half a turn = 180 degrees = Pi radians.

Images and preimages under doubling map d
\alpha d^1(\alpha) d^{-1}(\alpha)
\frac{1}{2} \frac{1}{1} \left \{ \frac{1}{4} , \frac{3}{4} \right \}
\frac{1}{3} \frac{2}{3} \left \{ \frac{1}{6} , \frac{4}{6} \right \}
\frac{1}{4} \frac{1}{2} \left \{ \frac{1}{8} , \frac{5}{8} \right \}
\frac{1}{5} \frac{2}{5} \left \{ \frac{1}{10} , \frac{6}{10} \right \}
\frac{1}{6} \frac{1}{3} \left \{ \frac{1}{12} , \frac{7}{12} \right \}
\frac{1}{7} \frac{2}{7} \left \{ \frac{1}{14} , \frac{4}{7} \right \}

On complex dynamical plane backward iteration using quadratic polynomial f_c

f_c(z) = z^2 + c

gives backward orbit = binary tree of preimages :

z \,

 -\sqrt{z-c} ,  +\sqrt{z-c} \,

 -\sqrt{-\sqrt{z-c} -c} ,  +\sqrt{-\sqrt{z-c} -c}, -\sqrt{+\sqrt{z-c} -c}, +\sqrt{+\sqrt{z-c} -c} \,

One can't choose good path in such tree without extra informations.

Not that preimages show rotational symmetry ( 180 degrees)

For other functions see Fractalforum[10]

Dynamic plane for f_cEdit

Level curves of escape timeEdit

Preimages of circle under fc

Julia set by IIM/JEdit

In escape time one computes forward iteration of point z.

In IIM/J one computes:

  • repelling fixed point[11] of complex quadratic polynomial Z_0=\beta_c \,
  • preimages of Z_0\, by inverse iterations

Z_{n-1} = \sqrt{Z_n - C}

Because square root is multivalued function then each Z_{n}\, has two preimages Z_{n-1}\,. Thus inverse iteration creates binary tree.

Root of treeEdit

  • repelling fixed point[12] of complex quadratic polynomial Z_0=\beta_c \,
  • - beta
  • other repelling periodic points ( cut points of filled Julia set ). It will be important especially in case of the parabolic Julia set.

"... preimages of the repelling fixed point beta. These form a tree like

                    beta                                            -beta
   beta                         -beta                    x                     y

So every point is computed at last twice when you start the tree with beta. If you start with -beta, you will get the same points with half the number of computations.

Something similar applies to the preimages of the critical orbit. If z is in the critical orbit, one of its two preimages will be there as well, so you should draw -z and the tree of its preimages to avoid getting the same points twice." (Wolf Jung )

Variants of IIMEdit

  • random choose one of two roots IIM ( up to chosen level max). Random walk through the tree. Simplest to code and fast, but inefficient. Start from it.
    • both roots with the same probability
    • more often one then other root
  • draw all roots ( up to chosen level max)[13]
    • using recurrence
    • using stack ( faster ?)
  • draw some rare paths in binary tree = MIIM. This is modification of drawing all roots. Stop using some rare paths.
    • using hits table ( while hit(pixel(iX,iY)) < HitMax )[14]
    • using derivative ( while derivative(z) < DerivativeMax)[15]

Examples of code :

Compare it with:


  1. wikipedia : Iteration
  2. Inverse Iteration Algorithms for Julia Sets by Mark McClure
  3. Complex iteration by Microcomputadoras
  4. On rational maps with two critical points by John Milnor, fig. 5
  5. Real and imaginary parts of polynomial iterates by Julia A. Barnes, Clinton P. Curry and Lisbeth E. Schaubroeck. New York J. Math. 16 (2010) 749–761.
  6. Complex numbers by David E Joyce
  7. Powers of complex numbers from Suitcase of Dreams
  8. Parabolic Julia Sets are Polynomial Time Computable by Mark Braverman
  10. Query about general Julia set IFS for higher powers.
  11. wikipedia : repelling fixed point
  12. wikipedia : repelling fixed point
  13. Fractint documentation - Inverse Julias
  14. Image and c source code : IIMM using hit limit
  15. Exploding the Dark Heart of Chaos by Chris King