Newton Fractal

Newton's method looks for the place where a curve crosses zero, which is called a root. It repeats one step: at your current guess, draw the straight line that follows the curve's slope, and take the place where that line crosses zero as your next guess.1 Close to the guess the line is a simple approximation of the curve, so its crossing is much easier to find than the curve's.

The curve below is x3−1x^3-1, and its root is at 11. Under the graph, the current step is worked out by hand. Try starting at 22, then at 0.50.5.

Improve a guess
Tangent to x cubed minus one at x = 2.00000012x47f(x) = x³ − 1next x

2 − (2³ − 1) / (3 × 2²) = 1.41667

Now start at 0.10.1. The curve is nearly flat there, so the line crosses zero far away and the next guess is 33.433.4. From out there, each step takes the guess to about two thirds of its distance. Start at 00 and the line is flat, so it never crosses zero and there is no next guess.

The same rule works with complex numbers, which have a horizontal and a vertical coordinate, and with those z3−1=0z^3-1=0 has three roots, marked below. Move your pointer over the plane to choose a first guess, or tap on a phone. The line runs through every guess until one reaches a root.

Follow a guess

(0.5, 0.7). Reaches the red root after 10 jumps. Its farthest guess is 9.2 from the center.

Close to a root, the guesses go straight in. Close to the center, they fly off the picture, come back, and can land on any root.

Because the first guess decides which root you reach, every pixel can get a color. The large picture at the top of this page tries a first guess at every pixel and gives it the color of the root it reaches. Below is the same picture, and each dot on the ring is a first guess, colored the same way.

Test a border

(0.4, 0.7)
Zoom ×1
The ring reaches 3 roots.

Move the ring into a patch of color and every dot agrees. Move it onto a border between two colors and the third color nearly always appears. Click or tap to keep a spot on a border, then press Zoom in. The ring stays the same size on screen, so it now tests starts four times closer together. Put it on a border and zoom again, and the third color keeps appearing, because all three regions share one boundary: however closely you look at a boundary point, starts leading to all three roots are nearby.1

The flat spot at 00 causes this. Press Around 0, and the ring meets each color twice.

A guess near 00 lands far away, at minus twice its angle from the line pointing right.2 So when a start goes once around a small circle, the landing spot goes twice around a huge circle, the other way. Guesses on that huge circle come back toward the center, each toward the root it faces, and going twice around means all three roots, twice.

Any start whose guesses land near 00 gets thrown out in the same way, so the same thing happens around that start, on a smaller scale. The ring opens beside one: (0.397,0.687)(0.397, 0.687) lands on 00 in one jump. Each spot where six slices of color meet is one of these starts, and they are packed along the whole boundary.3

The large picture stops each calculation after 96 steps. A guess that has not reached a root by then uses the nearest root's color, so some pixels near a border can have the wrong color. The ring's picture leaves those pixels dark.

Further exploring

Videos

Reading

Sources and notes

  1. À la recherche des racines perdues (In Search of Lost Roots). Section 3 covers the shared boundary.
  2. Calculation: z−(z3−1)/(3z2)=23z+1/(3z2)z-(z^3-1)/(3z^2)=\tfrac23z+1/(3z^2). Near 00 the last term is far larger than the rest. Far from 00 the first term is, which is why each step keeps about two thirds of the distance.
  3. Dynamics in One Complex Variable: Introductory Lectures. Theorem 3.9 says the starts that land on a point of the boundary are dense in it; Problem 3-2 says each region's boundary is that same set.