mathr / blog / #

Newton's method for periodic points

Previously on mathr: Newton's method for Misiurewicz points (2015). This week I applied the same "divide by undesired roots" technique to the periodic nucleus Newton iterations. I implemented it GLSL in Fragmentarium, which has a Complex.frag with dual numbers for automatic differentiation (this part of the frag is mostly my work, but I largely copy/pasted from C99 standard library manual pages for the transcendental functions, Wikipedia for basic properties of differentiation like product rule, quotient rule, chain rule...).

Here's the improved Newton's method, with the newly added lines in bold:

vec2 nucleus(vec2 c0, int period, int steps) {
  vec2 c = c0;
  for (int j = 0; j < steps; ++j) {
    vec4 G = cConst(1.0);
    vec4 z = cConst(0.0);
    for (int l = 1; l <= period; ++l) {
      z = cSqr(z) + cVar(c);
      if (l < period && period % l == 0)
        G = cMul(z, G);
    }
    G = cDiv(z, G);
    c -= cDiv(G.xy, G.zw);
  }
  return c;
}

And some results, top half of the image is without the added lines, bottom half of the image is with the added line, from left to right the target periods are 2, 3, 4, 9, 12:

You can download the FragM source code for the images in this article: 2018-11-17_newtons_method_for_periodic_points.frag.