Introduction
The "Newton-Raphson" method is an algorithm for finding the roots of differentiable equations. See Wolfram or Wikipedia
It can be used to generate fractal images like these:
|
|
|
The interactive WebGL version is here
If you only want to solve polynomials, rather than draw pictures, visit the polynomials page.
The Patterns
The images in this section were drawn using the python script (no longer available).
|
This image shows a situation where the iterations converge on a cycle of 2 points. We are looking at the polynomial "x3-2.55x2-1 = 0 around the point (0.866,0). The attractors are:
|
|
The basic Newton Raphson equation can be modified by adding in a sort of damping factor, called 'a', see the "Generalisation" section on the Wikipedia page. In my code I call this "alpha". If you perform the calculations keeping the seed point constant and varying 'a' you can get patterns like the one on the left, showing the behaviour of the simple cubic x3 = 1 with the seed value (0.1,0). This calculation only converges when 'a' is in the circular region of radius 1 centred on the point (1,0). In the image the area outside this region is shaded grey. The white region inside this circle is the region where the calculations didn't converge. See the next image for more on this. |
|
The image on the left is the same calculation as in the previous image (x3 = 1) but this time these non-convergent points have been assigned colours according to the size of the loops they converge on. These colours as assigned at random, so I can't identify which colour corresponds to which loop size. It's possible the points in the purple region would converge if the calculation was given more time. |
|
This next image zooms in on the region towards the top right of the previous image, it is centered on the point 'a' = (1.81,-0.39). I've included this because I like it, especially as you can see some interesting structure in the "cyclic" region to the right of the image. The application parameters are "e1,0,0,-1 s1280x1024 i60000 b120 fpic1 l20 z0.1,0 m40 tA c1.81,-0.39 xI". The cyclic colours are assigned randomly so you probably won't get exactly the same image. |
|
In this "Alpha-map" version, if you choose as you seed point a value that doesn't converge on a root in the standard version, then you can find non convergent regions that look like the Mandelbrot set. This one was generated using the same polynomial as in the first image: "x3-2.55x2-1 = 0, with the seed point (0.866,0) and is centred around 'a' = (1,0). Note that the Mandelbrot isn't perfect, the amount of distortion depending on the value of the seed point. There is probably a value that produces a perfect image but I haven't worked out what it is. |
Bestiary
This section catalogs some of the common patterns. There are two columns, the first shows the standard iteration performed over different seed values, the second shows a example of the corresponding "alpha-map", formed by varying the 'α' parameter in the iteration Zn+1 = Zn− αF(Zn) ⁄ F'(Zn) while keeping the seed point constant.
Note: The original Python script didn't handle repeated roots very well as you will see below. The WebGL version is much better.
Two Real Roots
(z−1).(z−2)
Three Real Roots
(z+2).(z−1).(z−2)
Four Real Roots
(z+2).z.(z−1).(z−2)
Five Real Roots
(z+2).(z+1).z.(z−1).(z−2)
Five Real Roots (2)
(z+2).(z+1).(z−1).(z−2).(z−100)
Two repeated Real Roots
(z−1)2
Results are a bit random as algorithm finds two slightly different roots.
Two repeated Real Roots
(z−1)2.(z+1)
2×2 Repeated Real Roots
(z−1)2.(z+1)2
Three repeated Real Roots
(z+1)3
The algorithm fails completely.
Three repeated Real Roots)
z.(z+1)3
Algorithm finds the single root but not the repeats.
Two Imaginary
(z2+1)
One Real, Two Imaginary
(z2+1).(z-2)
Cyclic
900z3 − 2595z2 + 658z − 902
The small white region near the centre of the alpha plot shows the range of alpha values where the seed point (0.9) doesn't converge on a solution. If you zoom in on this region you can see that it looks very similar to the Mandelbrot set.
