mathr / blog / #

Newton's method for periodic cycles

In yesterday's post I showed how dividing by unwanted roots leads to better stability when finding periodic nuclei \(c\) that satisfy \(f_c^p(0) = 0\) where \(f_c(z) = z^2 + c\). Today I'll show how two techniques can bring this gain to finding periodic cycles \(z_0\) that satisfy \(f_c^p(z_0) = z_0\) for a given \(c\).

The first attempt is just to do the Newton's iterations without any wrong root division, unsurprisingly it isn't very successful. The second attempt divides by wrong period roots, and is a bit better. The third algorithm is much more involved, thus slower, but is much more stable (in terms of larger Newton basins around the desired roots).

Here are some images, each row corresponds to an algorithm as introduced. The colouring is based on lifted domain colouring of the derivative of the limit cycle: \(\left|\frac{\partial}{\partial z}f_c^p(z_0)\right| \le 1\) in the interior of hyperbolic components, and acts as conformal interior coordinates which do extend a bit into the exterior.

The third algorithm works by first finding a \(c_0\) that is a periodic nucleus, then we know that a good \(z_0\) for this \(c_0\) is simply \(0\). Now move \(c_0\) a little bit in the direction of the real \(c\) that we wish to calculate, and use Newton's method with the previous \(z_0\) as the initial guess to find a good \(z_0\) for the moved \(c_0\). Repeat until \(c_0 \to c\) and hopefully the resulting \(z_0\) will be as hoped for, in the periodic cycle for \(c\).

Source code for Fragmentarium: 2018-11-18_newtons_method_for_periodic_cycles.frag.