Notebooks · posts/newton-basins

Which root does Newton's method find?

Adam Zettel · September 21, 2026 · written with an agent

Solve $z^{3} = 1$ by Newton's method from every point of a square and color each start by the root it reaches. Near a root the answer is obvious. Along the lines between them it is a fractal: every boundary point touches all three basins.

z_{k + 1} = z_{k} - \frac{z _{k}^{3} - 1}{3 z _{k}^{2}}

Newton's step for $z^{3} - 1$ is $z \to z - (z^{3} - 1) / (3 z^{2}) = (2 z^{3} + 1) / (3 z^{2})$ . It commutes with complex conjugation, so the picture is symmetric top to bottom, and the two complex roots must attract exactly the same number of grid points; the test checks that the counts are equal, not merely close.

Look inside this program

Atlas
The program’s map: every function and which calls which.
There’s no recorded run of this program yet.

Shift+Enter in a cell runs it and moves to the next. Running a cell runs every cell above it too, as one program.

[1]lines 17–75

pi = 3.141592653589793
N = 128
SPAN = 1.6
STEPS = 40
# the cube roots of 1
NROOTS = 3.0

#| Which cube root of 1 Newton's method reaches from x + iy: 0, 1 or 2; -1 if none in STEPS.
def basin(x, y) {
    z = complex(x, y)
    for s to STEPS {
        z = (2.0 * z * z * z + 1.0) / (3.0 * z * z)
    }
    found = -1.0
    for k to NROOTS {
        dx = re(z) - cos(2.0 * pi * k / 3.0)
        dy = im(z) - sin(2.0 * pi * k / 3.0)
        if dx * dx + dy * dy < 1.0e-12 {
            found = k
        }
    }
    return found
}

# the grid is offset by half a cell, so no start sits on the real axis or at z = 0
CELL = 2.0 * SPAN / N
grid = zeros(N, N)
# one count per root, and count[0] for the starts that reach none
count = zeros(NROOTS + 1.0)
for i to N {
    for j to N {
        x = -SPAN + (j + 0.5) * CELL
        y = SPAN - (i + 0.5) * CELL
        b = basin(x, y)
        grid[i, j] = b
        count[b + 1.0] = count[b + 1.0] + 1.0
    }
}
show count

# the window gives the picture real axes; "pixels" because a cell is a category,
# and blending two of them would invent a third
figure("Basins of the three cube roots of 1", "Re z", "Im z", -1.6, 1.6, -1.6, 1.6, "pixels")
plot2d(grid, "root reached: 0, 1 or 2")

test "each root is a fixed point of the Newton step" {
    for k to NROOTS {
        assert_near(basin(cos(2.0 * pi * k / 3.0), sin(2.0 * pi * k / 3.0)), k, 0.0)
    }
}
test "every start on the grid has reached a root within 40 steps" {
    assert_near(count[0], 0.0, 0.0)
}
test "the two complex roots attract the same number of grid points, because the step commutes with conjugation" {
    assert_near(count[2], count[3], 0.0)
}

# SPDX-License-Identifier: MIT OR Apache-2.0
# SPDX-FileCopyrightText: 2026 The Viv authors

pi = 3.141592653589793
N = 128
SPAN = 1.6
STEPS = 40
# the cube roots of 1
NROOTS = 3.0

#| Which cube root of 1 Newton's method reaches from x + iy: 0, 1 or 2; -1 if none in STEPS.
def basin(x, y) {
    z = complex(x, y)
    for s to STEPS {
        z = (2.0 * z * z * z + 1.0) / (3.0 * z * z)
    }
    found = -1.0
    for k to NROOTS {
        dx = re(z) - cos(2.0 * pi * k / 3.0)
        dy = im(z) - sin(2.0 * pi * k / 3.0)
        if dx * dx + dy * dy < 1.0e-12 {
            found = k
        }
    }
    return found
}

# the grid is offset by half a cell, so no start sits on the real axis or at z = 0
CELL = 2.0 * SPAN / N
grid = zeros(N, N)
# one count per root, and count[0] for the starts that reach none
count = zeros(NROOTS + 1.0)
for i to N {
    for j to N {
        x = -SPAN + (j + 0.5) * CELL
        y = SPAN - (i + 0.5) * CELL
        b = basin(x, y)
        grid[i, j] = b
        count[b + 1.0] = count[b + 1.0] + 1.0
    }
}
show count

# the window gives the picture real axes; "pixels" because a cell is a category,
# and blending two of them would invent a third
figure("Basins of the three cube roots of 1", "Re z", "Im z", -1.6, 1.6, -1.6, 1.6, "pixels")
plot2d(grid, "root reached: 0, 1 or 2")

test "each root is a fixed point of the Newton step" {
    for k to NROOTS {
        assert_near(basin(cos(2.0 * pi * k / 3.0), sin(2.0 * pi * k / 3.0)), k, 0.0)
    }
}
test "every start on the grid has reached a root within 40 steps" {
    assert_near(count[0], 0.0, 0.0)
}
test "the two complex roots attract the same number of grid points, because the step commutes with conjugation" {
    assert_near(count[2], count[3], 0.0)
}

# SPDX-License-Identifier: MIT OR Apache-2.0
# SPDX-FileCopyrightText: 2026 The Viv authors