Tuesday, September 16, 2008

Newton Fractal and Durand Kerner method

Newton Fractal and Durand Kerner method

I had known about Newton Fractal for a long enough time, even before I wrote the code for RTC7681 and RTC7683. But it is impossible to do, as long as I don't know what numerical method people use to get the complex roots of complex polynomial function.

Anyway I just decided to ask the question in Yahoo!Answer recently and several people was kind enough to answer my question. Too bad I can only choose one best answer. Internet is a really helpful thing to have, just imagine how many knowledge do millions of user around the world can have. So I just need to transform Durand-Kerner method into computer code and voila I have my Newton Fractal.

All pictures showed below is a actually Newton Fractal plot of the same complex polynomial function, but different pictures showed different level of detail. The complex polynomial function used is f(x) = x8 + x6 + 5i x5 + ( 3 + 2i )x4 + ( 3 + 5i )x2 -1. The value of a used is 1 + 1i.

The picture above is the Newton Fractal plot of the complex polynomial function mentioned earlier. The plot range is between -300-300i and 300+300i. Even though this is the least detailed plot of the fractal, this one is drawn the latest as that was the last thing I am curious about. If I wasn't too curious about the geometry of the Newton Fractal in big range, I would probably never care to plot it. Anyway the prospect of being able to get the same small detail in big scale win my curiousity.

This particular Newton Fractal was plotted with plot range between -3-3i and 3+3i. So this one have about 100 times more detailed, than the previous Newton Fractal plot result. This is the first plot I told my cute little computer to execute, as that is the range I used to test the program with different polynomial function and a value.

Curious what would happen if we take a look on those little blob in plot range between -2.3-0.3i and -1.7+0.3i ? I was curious as well. So I decided to spend about 8 hours of my computer time to plot the function in high resolution ( 8000x8000 pixels2 ). I have ordered the ( 70x70 cm2 glossy paper print of the plot result and planned to use it as a poster in my room. Too bad I can't share either the 183 MB BMP file or 20.7 MB JPG File due to the upload speed where I live. But if you click the image, you can still view it in 2000x2000 pixels2 detail.

Extreme Resolution

I was still curious about bigger picture of the Newton Fractal, so I decided to do more experiments. The first extreme experiment result was the picture above, depicting the plot result with range between -3e5-3e5i and 3e5+3e5i. It seems that the greater range we go, the less detail we can expect to get.

And on the range of -3e8-3e8i and 3e8+3e8i, you will get no complex picture at all. See the picture above and you will realize that the pictur consist of only 5 different color, instead of 8. This means that in the big picture of things, the probability to get 5 roots out of 8 from x8 + x6 + 5i x5 + ( 3 + 2i )x4 + ( 3 + 5i )x2 -1 = 0 using Newton-Raphson method is great. To get the other 3 roots however will be almost impossible.

On the other hand, it is not easy to get a plot result with good complexity on the micro scale either. Most of the time you are going to Fall into the Sea, but by using a numerical method called Bisection combined with low resolution exploration, we can expect to arrive in some Island of Complexity. The plot result above for example, was drawn with plot range between -2.2113+0.0002i and -2.2117+0.0006i.

No comments: