Newton’s Fractals – Generating Images from Roots
Fractals have always amazed me. Every time I see a fractal, I can get just as excited as the first time I saw the mandelbrot set. In this post, we’ll go through a method, which can generate beautiful structures from simple functions.
Link to the source code for this project: https://github.com/SSODelta/newtons-fractals
Sometimes however, a second degree equation does not have any real solutions. That is when . A quadratic equation will, however always have two solutions in the complex plane.
The complex plane is an extension of the real number line to a plane. The major new addition is the introduction of the imaginary unit , which is the unique number satisfying . This allows us to find solutions to equations such as , which otherwise wouldn’t have any real solutions. In the complex plane every single point has a unique complex number associated with it. A complex number consists of two parts, a real part and an imaginary part. This is usually stylized , where is the real part and is the imaginary part.
What does all this have to do with fractals?
To make a fractal, we need to assign a color code to each point in a plane, in this case the complex plane as discussed above. We decide on an initial size and a resolution . The size is the width and height of an image measured in pixels. The resolution is the “zoom-factor”, if you will. If , then we’ll deal with complex numbers in the range . And in general . To make it clear how to combine roots and points in the complex plane to make fractals, we need to introduce a very important method.
Introducing, Newton’s approximation for finding roots to a real-valued function (although it extends nicely to the complex plane, fortunately). For a function and an initial “guess” , a better guess will be , where is the derivative of . In fact, this can be generalized to the recursive formula . So how do we make fractals?
- Have a function , a size and a resolution .
- Assign a unique color to each root to .
- For every point in the image, make an inital guess .
- Use Newton’s approximation method to approximate a root as long as .
- Color the pixel the color which is assigned to the root which has just been approximated.
In practice, we’ll only deal with polynomials, though, because they’re easy to calculate and to calculate the derivative of.
Using this method gives us some stunning images:
Link to an album with more than 100 HD fractals: http://imgur.com/a/xOFyF#0
As a little extra feature I have also colored the points which converge faster darker as to create some variation in the images.
Inspiration for this post: http://www.reddit.com/r/math/comments/25nhy8/beautiful_symmetry_in_solving_x310_with_newtons/