Fractals from Iterated Root-Finding Methods

You can find a lot of fractals on the web that were generated using Newton's method. These fractals are called, not surprisingly, Newton fractals, and Simon Tatham has some nice material about them. In short, they are generated by first selecting a function from the complex numbers to the complex numbers, and by then using Newton's method to search for roots of the function. Each pixel in the final image is colored according to which root Newton's method converged to when started using the point "below that pixel". In addition, the faster Newton's method converged, the brighter the pixel will be. Such fractals typically look something like this:

You can find more information about Newton fractals in Simon Tatham's great article. Now Newton's method is just one of several iterative root finding methods. Here is a whole collection:

• Newton's method:
• Householder's method:
• Halley's method:
• Schröder's method:
• Steffensen's method:

It turns out these can be used to create beautiful fractals, too.

2x³ - 2x + 2

Polynomials are the "traditional" functions used for generating Newton fractals. Since a polynomial of degree 3 has exactly 3 roots in the complex numbers, each fractal consists of three parts, colored red, blue, and green. The black regions in the Steffensen fractal indicate regions where the method did not converge, or took too long to do so.

• 
  Newton fractal
• 
  Newton fractal (detail)

• 
  Householder fractal
• 
  Householder fractal (detail)

• 
  Halley fractal
• 
  Halley fractal (detail)

• 
  Schröder fractal
• 
  Schröder fractal (detail)

• 
  Steffensen fractal
• 
  Steffensen fractal (detail)

x³ - 3^x

While using polynomials as base functions is nice, Newton fractals show their real beauty when more complex functions are used. All fractals shown here contain some black areas, where no convergence occurred after 100,000 steps. The Schröder fractal is especially interesting, since it contains regions in which the convergence behaviour seems to be chaotic: in these areas, the behaviour changes rapidly, resulting in a noisy coloring.

• 
  Newton fractal
• 
  Newton fractal (detail)

• 
  Householder fractal
• 
  Householder fractal (detail)

• 
  Halley fractal
• 
  Halley fractal (detail)

• 
  Schröder fractal
• 
  Schröder fractal (detail)

• 
  Steffensen fractal
• 
  Steffensen fractal (detail)

cos(x)

Finally here are some details for the complex cosine. Since the cosine has infinitely many roots, colouring the fractals according to which root the method converged to does not make sense. It also turns out that the fractals are rather boring when viewed on a big scale. Thus only renderings of the more interesting details are included here.

• 
  Newton fractal (detail)
• 
  Householder fractal (detail)
• 
  Halley fractal (detail)
• 
  Schröder fractal (detail)
• 
  Steffensen fractal (detail)

Source Code

The images shown above were generated using a simple C program. It's released under the GPL and here's the source code.