MrMineev

The Newton Fractal - is a boundary set in the complex plane, characterized by Newton's method applied to a fixed polynomial. Let's break this down and figure out what each part means. First of all, what is Newton's method? Well, Newton's method, also known as the The Newton-Raphs method is a root-finding algorithm that produces excellent approximations for the roots of a real-valued function. Let's take an example of a function f(x) = x^3 - 8 * x^2, then the graf of function f is going to look like this:

As you can see, there are only two roots: f(0) = 0 and f(1) = 1. Let's try finding these roots with Newton's method. Pick a random real number N from -∞ to +∞. Then follow these steps:

 1. Find the derivative of f(N).

 2. N = where the derivative line intersects the x-axis.

 3. Go to step 1

Let's start with N=-4, then the derivative is

Now to calculate the new N we have to follow the following formula which does what i described earlier.

The N₂ is a far better estimate for the equations root. If we continue like this calculating N₃, N₄, ..., we will get closer and closer to the real root of the function. Here is the OCaml code for this algorithm

          let rec pow (x: float) (y: float) =
  if y > 0.0 then
    x *. pow x (y -. 1.0)
  else
    1.0
in

let f (x : float) =
  (pow x 3.0) -. 8.0 *. (x 2.0)
in

let f x =
  3.0 *. (pow x 2.0) -. 16.0 *. x
in

let rec newtons n x max_n =
  if x >= max_n then
    n
  else
    newtons (n -. (f n) /. (fp n)) (x +. 1.0) max_n
in

print_float (newtons (4.0) 0.0 100.0);;

Now, how about instead of picking a real number N and applying the algorithm, we will pick a complex number N and use the algorithm? Well, then, first of all, we have to write a formula that describes everything in the algorithm. So let's take thousands of points on the complex plane and see where these points go and see which complex routs this algorithm finds. Here the algorithm is going to try to solve the equation x^5 - 1 = 0.

(All the code for the animations is located in the GitHub link down bellow)

In this animation the blue points are different points from which we are running the algorithm. As you can see closer to the end there are 5 different groups of points that are closely positioned to each other, each of these groups is an approximation for a certain solution for this equation.

Now, let's go through each point and then color it based on which solution is the closest to it. Then let's rewind everything and go from the end state of the algorithm to the start. Now we can see which points found which solutions on the complex plane. For the equation x^5 - 1 = 0 (the one in the animation) here is what we get after doing this:

These are some other examples for other equations.

  1. Equation x^3 - x = 0

  2. Equation x^4 + x^3 - x^2 - 5

Wikipedia   https://www.wikiwand.com/en/Newton_fractal

GitHub   https://github.com/MrMineev/the-newton-fractal