mathr / blog / #

Newton's method can be used to trace external rays in the Mandelbrot set. See:

An algorithm to draw external rays of the Mandelbrot set

Tomoki Kawahira

April 23, 2009

Abstract In this note I explain an algorithm to draw the external rays of the Mandelbrot set with an error estimate. Newton’s method is the main tool. (I learned its principle by M. Shishikura, but this idea of using Newton’s method is probably well-known for many other people working on complex dynamics.)

The algorithm uses \(S\) points in each dwell band, this number is called the "sharpness". Increasing the sharpness presumably makes the algorithm more robust when using the previous ray point \(c_n\) as the initial guess for Newton's method to find the next ray point \(c_{n+1}\) as the points are closer together.

I hypothesized that it might be better (faster) to use a different method for choosing the initial guess for the next ray point. I devised 3 new methods in addition to the existing one:

nearest

\( c_{n+1} := c_n \)

linear

\( c_{n+1} := c_n + (c_n - c_{n-1}) \)

hybrid

\( c_{n+1} := c_n + (c_n - c_{n-1}) \left| \frac{c_n - c_{n-1}}{c_{n-1} - c_{n-2}} \right| \)

geometric

\( c_{n+1} := c_n + \frac{(c_n - c_{n-1})^2}{c_{n-1} - c_{n-2}} \)

I implemented the methods in a branch of my mandelbrot-numerics repository:

git clone https://code.mathr.co.uk/mandelbrot-numerics.git
cd mandelbrot-numerics
git checkout exray-methods
git diff HEAD~1

I wrote a test program for real-world use of ray tracing, namely tracing rays of preperiod + period ~= 500 to dwell ~1000, with all 4 methods and varying sharpness. I tested for correctness by comparing with the previous method, which was known to work well with sharpness around 4 through 8.

Results were disappointing. The hybrid and geometric methods failed in all cases, no matter the sharpness. The linear method failed for sharpness below 7, but when it worked (sharpness 7 or 8) it took about 68% of the time of the nearest method. However, the nearest method at sharpness 4 took 62% of the time of nearest at sharpness 8, so this is not so impressive.

The nearest method seemed to work all the way down to sharpness 2, which was surprising, and warrants further investigation: nearest at sharpness 2 took only 41% of the time of nearest at sharpness 8, if it turns out to be reliable this would be a good speed boost.

You can download my raw data.

Reporting this failed experiment in the interests of science.