Gregory Friedman The Greg Wide Web on the name →

Case Study · Math · Dynamics

The Fractal Hiding in Newton's Method

2026

The idea

Newton’s method is the oldest good idea in numerical analysis, and it is disarmingly simple. You want a root of a function f. You guess. You stand at your guess, follow the tangent line down to where it crosses zero, and call that your next guess. Written out, the guess z updates to z − f(z)/f′(z), and if you started anywhere near a root the sequence closes in on it fast, doubling its correct digits at every step. Every calculator that finds a square root is doing this, and it usually just works.

The word doing the quiet labour there is near. Newton’s method is a local promise: close to a root it is wonderful, and it says nothing about what happens when you start far away. So here is the question this plate is built around. Take a function with several roots and ask, of every possible starting point, which root does Newton’s method eventually reach? Colour each start by its destination. You would guess, reasonably, that the plane splits into a few tidy territories, one per root, with clean borders between them. That guess is wrong in the most beautiful way I know.

The approach

The natural place to ask the question is the complex plane, because a polynomial that has only one real root has all its roots once you allow complex numbers, and Newton’s iteration z ← z − p(z)/p′(z) runs on complex numbers without a single change. The plate below takes p(z) = zⁿ − 1, whose roots are the n-th roots of unity: n points spaced evenly around the unit circle, known exactly, so there is no ambiguity about which root a start converged to. It runs the iteration on every pixel, decides which root that pixel reached, paints it in that root’s colour, and then darkens it by how many steps the trip took.

The three roots of z cubed minus one, the seeds of the classic Newton fractal, each the centre of one basin of attraction.
basin root angle
1 1.000 + 0.000i 0°
2 -0.500 + 0.866i 120°
3 -0.500 − 0.866i 240°

With JavaScript enabled this plate iterates Newton's method z ← z − a·p(z)/p′(z) over every pixel of the complex plane, colours each by the root it reaches, and darkens it by the number of steps that took. For z³ − 1 the three roots above split the plane into three basins whose shared boundary is a fractal: near it the smallest nudge sends a start to a different root, and all three basins meet along every piece of that edge at once.

Step through Newton's method

Plate I Newton's method on z to the n minus one, run over the complex plane. Each pixel is a starting point, coloured by which root it converges to and shaded by the number of steps: basin interiors converge in a step or two and stay bright, while the boundary needs many steps and fades into the page. The real and imaginary axes are labelled with ticks, and the roots sit ringed in their basin colours on the unit circle. Click the plane (or walk a marker with the arrow keys) to drop a starting point, then Step through the iteration z ← z − a·p(z)/p′(z) and watch the orbit march to a root. Switch the polynomial from three roots to five, and turn the relaxation dial a off its classical value of one to redraw the filigree. Roots of unity are known in closed form, so the colouring is exact.

That shading is the whole trick of reading the picture. Deep inside a basin, right next to a root, convergence takes one or two steps, so those regions glow in their root’s flat colour. The interesting pixels are the slow ones, the starts that dither for many iterations before committing, and those live along the borders between basins. Darkening by iteration count is what turns an invisible mathematical boundary into visible lace.

Two controls let you push on the mechanism. Detail is the cap on iterations: raise it and the machine is given more patience, which resolves finer and finer structure along the edges, because the boundary is precisely where more patience keeps changing the answer. Relaxation a generalizes the step to z ← z − a·p(z)/p′(z). At a = 1 you have classical Newton; under-relaxing (a < 1) takes cautious half-steps, over-relaxing (a > 1) leaps past the target and can spiral in, and both redraw the basins into different but equally fractal shapes. The standard method is one slice through a whole family.

And you can watch the mechanism one step at a time. Drop a starting point anywhere on the plane, by clicking or by walking a marker with the arrow keys, and Step advances Newton’s iteration once, tracing the path z₀ → z₁ → z₂ toward whichever root claims it. Playing the whole orbit shows in miniature what the colouring computes for every pixel at once: the bright basins are the starts that arrive in a step or two, and a point dropped near the boundary can wander for a dozen steps before it finally commits to a root. That march is the why behind each basin’s colour.

Why the boundary has to be a fractal

Look at the border between two basins in the z³ − 1 picture and try to trace it. You cannot, because it is not a curve. Zoom in and the boundary does not straighten out the way the edge of a circle eventually looks like a line; instead a whole new generation of bulbs and filaments appears, a copy of the structure you were already looking at, forever. This is the Julia set of the Newton map, and its roughness is not an artifact of the pixels. It is forced.

Here is the argument, and it is short. Suppose some smooth arc of boundary separated just the red basin from the green one. Then Newton’s map, applied to that arc, would have to send it into another piece of boundary, because the map sends basins to basins and so sends borders to borders. But the map is a polynomial ratio, an analytic function, and iterating it near the boundary stretches distances without bound: two starts a hair apart on opposite sides run off to different roots, which is the definition of sensitive dependence, the signature of chaos. A set that is stretched by every iteration and mapped onto itself cannot be smooth; if it had a tangent line the stretching would tear the tangent apart. So the boundary is self-similar under the map, which is to say fractal, and it is the same set for every basin at once.

That last clause is the genuinely strange part of z³ − 1, and it is worth staring at. With three roots you might expect the plane divided like a pie, three sectors meeting along three seams, each seam between two of the three. Instead every point of the boundary touches all three basins. Pick any spot on the edge and any neighbourhood of it, however small, and you will find starts that go to all three roots inside it. Three countries, and every inch of every border is a place where all three meet. This is called the Wada property, after the topologist who first exhibited such lakes, and Newton’s method on the simplest interesting polynomial produces it for free. The three-fold symmetry of the roots becomes a three-fold chaos on the boundary.

The same iteration, on a single line

The argument in the last section turns on sensitive dependence, and it does its work out of sight. The stretching happens on a set you cannot draw, and the conclusion arrives as a proof rather than as something you watched. So it is worth putting the complex plane down and running the same motif on the smallest stage that will hold it: one number, one dial, one rule. Take a number x between 0 and 1 and replace it by r·x·(1 − x). That is the logistic map, written down as a toy model of a population that grows in proportion to its size and is held back in proportion to how crowded it already is, and made notorious by Robert May’s 1976 survey of how badly such models can behave. It has no complex numbers, no derivative, no polynomial past degree two. It has a parabola and a growth rate, and it holds the whole story of how a well-behaved system stops being one.

Specimens
Cobweb · one orbit on the unit square
0 0 0.5 0.5 1 1 x f(x) y = x

step 40 · x = 0.7995 · settles on a 2-cycle: 0.5130, 0.7995 · Lyapunov exponent −0.916

Bifurcation · every attractor at once

With JavaScript enabled this panel sweeps r from 2.4 to 4, runs the same iteration a few hundred times at each of about three thousand values of r, throws the transient away, and plots what is left. A single attracting value splits into two at r = 3, into four at r ≈ 3.4495, into eight at r ≈ 3.5441, and the doublings accumulate at r ≈ 3.5699, after which the orbit fills whole intervals. The table of those parameters, below, is computed either way.

Window

marker at r = 3.200 · the cobweb to the left is this column

Two starts, one billionth apart

gap after 0 steps
1.00e−9
gap after 10 steps
2.28e−11
gap after 20 steps
2.55e−15
gap after 30 steps
0
gap after 40 steps
0

Both orbits start near 0.4. At r = 3.200 they merge: the same 2-cycle pulls both in, so an error in the tenth decimal place is forgotten rather than remembered. Raise r past 3.5699 and the same table reads the other way round.

Where each cycle doubles, and how fast the windows shrink

The parameter at which each cycle of the logistic map doubles, the width of the window it owned, and the ratio of successive widths, which converges to Feigenbaum's constant.
n period after rn rn − rn−1 ratio of gaps
1 2 3.000000000
2 4 3.449489743 4.494897e-1
3 8 3.544090360 9.460062e-2 4.751446
4 16 3.564407266 2.031691e-2 4.656251
5 32 3.568759420 4.352153e-3 4.668242
6 64 3.569691610 9.321903e-4 4.668739
7 128 3.569891259 1.996496e-4 4.669132
8 256 3.569934018 4.275900e-5 4.669183
9 512 3.569943176 9.157674e-6 4.669198
∞ 3.569945672 0 4.669201609

Every rn above is solved for, not quoted: the parameter is found where the multiplier of the 2n−1-cycle passes through −1. The second row is 1 + √6 = 3.449489743 to every digit shown. The last column is (rn−1 − rn−2) / (rn − rn−1), and its limit δ = 4.669201609 is the same number for the sine map, for the Hénon map, and for a dripping tap.

Plate II Two pictures of one iteration, x ← r·x·(1 − x). On the left the cobweb: a vertical move to the parabola applies the map, a horizontal move to the diagonal feeds the answer back in, so every corner on the diagonal is one step. The default r = 3.2 has already settled onto a two-box loop. On the right the bifurcation diagram, which runs the same iteration at a few thousand values of r, discards the transient, and plots whatever the orbit is still doing, so the cascade from one point to two to four to a filled interval reads at a glance. The two are linked: the r you set on the left is the marked column on the right, and clicking the right sets the left. Try r = 3.5 for a 4-cycle, 3.56 for an 8-cycle, and 3.835 for the window of period 3 that opens in the middle of the chaos; the buttons under the diagram narrow the sweep onto the cascade and onto that window. The panels below run two starts a billionth apart, so sensitive dependence stops being a phrase and becomes a column of numbers, and solve for the parameter at which each cycle doubles, whose gap ratios close on Feigenbaum's δ.

The cobweb is the iteration drawn rather than tabulated. From a starting value on the horizontal axis, go vertically to the parabola (that is the map being applied) and horizontally to the diagonal (that is the output becoming the next input), and repeat. Below r = 3 the staircase spirals into the single crossing at x* = 1 − 1/r and stops there, because the parabola meets the diagonal at slope 2 − r, and a crossing whose slope lies between −1 and 1 pulls its neighbours in. At r = 3 that slope reaches −1 exactly, the crossing stops holding, and the staircase settles instead into a rectangle that alternates between two values forever. Raise r again and those two values become four at r = 1 + √6 ≈ 3.4495, then eight at 3.5441, then sixteen at 3.5644, and the doublings arrive faster and faster.

Faster by how much is the question with the surprising answer. Each window is about 4.67 times narrower than the one before it, and the ratio of successive widths converges to δ = 4.669201609…, the Feigenbaum constant, which the plate computes rather than quotes: it solves for the parameter where each cycle’s multiplier passes through −1 and then divides one gap by the next, so a reader watching 4.7514, 4.6563, 4.6682, 4.6687 come up the table is watching arithmetic rather than being handed a fact. The windows shrink geometrically, so infinitely many doublings fit into a finite stretch of r and are all finished by r∞ ≈ 3.5699457. What made this famous in 1978, when Mitchell Feigenbaum published it (Pierre Coullet and Charles Tresser found it independently), is that δ has nothing to do with parabolas. Any smooth map with a single hump of the same rounded shape doubles its cycles at parameters spaced by the same constant: the sine map does it, the Hénon map does it, and the number turned up in convection and oscillator experiments within a few years. The route is a property of the shape of the hump and not of the formula, which is the kind of universality one expects from thermodynamics and not from a quadratic.

Past r∞ the orbit stops closing up at all, and this is where the plate earns its second panel. Set r to 3.9, and two starts a billionth apart hold together for twenty-odd steps and then part company completely, which is the whole content of sensitive dependence: nine correct decimal places buy you about thirty steps of prediction, and the next nine buy about thirty more. The Lyapunov exponent under the cobweb is that rate as a single number, positive when the gap doubles and negative when the orbit is being pulled onto a cycle. And the chaos is not solid. The blank vertical bands in the diagram are windows where order returns, the widest of them opening at exactly 1 + 2√2 ≈ 3.8284 with a cycle of period 3, which then runs its own doubling cascade into 6 and 12 and a small copy of the entire diagram. Period 3 is the sharpest possible thing to find there: Sharkovskii proved in 1964 that a continuous map of an interval with a point of period 3 has points of every other period as well, and it was Li and Yorke’s 1975 note on that fact, “Period Three Implies Chaos”, that gave the subject its name.

So the same phenomenon that forces the Newton boundary to be a fractal is here in a form you can dial through and measure. Notice where the two pictures put their fractal, though, because they do not put it in the same place. The Newton plate is a map of state space, and the intricacy lives in the plane of starting points. The bifurcation diagram is a map of parameter space, and its self-similarity, each window holding a shrunken copy of the whole cascade, is intricacy in the dial rather than in the state. Two different axes, one habit of iteration, and the same refusal to resolve into anything smooth.

Where else a rule gets fed its own output

Both plates on this page belong to a family that runs all through the site, because the motif underneath them is iteration: apply a rule, feed the output back in, and watch where repetition carries you. Newton’s method is that motif with a particularly well-behaved rule almost everywhere and a fractal catastrophe on a thin set. Change the rule and you change the atlas.

The slope-fields plate is the continuous cousin: instead of a discrete map it integrates a vector field, and its Euler stepper shows the same lesson from the other side, that a method trusted in the small can blow up in the large once the step is too greedy, which is exactly what over-relaxing Newton risks. The Collatz plate iterates a rule on the integers whose orbits nobody can prove always come home, the same question of long-run destination the Newton plate answers pixel by pixel for a polynomial. Gradient descent, the workhorse behind the machine-learning work, is Newton’s poorer relative: it steps downhill along the gradient rather than along the tangent to zero, and its basins around the minima of a nonconvex loss have the same character, tidy near the bottoms and tangled in between, which is why where you start a network’s weights can decide where it ends. And the Fourier plate shares the deeper theme, that a global object (a spectrum, a basin map) can carry information no local look at the function reveals.

What the figures claim, and what they leave for later

The Newton plate colours each start by its nearest root after a bounded number of steps, which is exact for the roots of unity: their positions are known in closed form, so a converged orbit is attributed without ambiguity. The delicate cases sit just outside that frame by design. For some polynomials Newton’s method has whole regions that fall into cycles and never reach a root, black holes in the picture, and zⁿ − 1 is a clean choice precisely because it is free of them; a companion plate for the cyclic cases is a natural sequel.

The compute runs at a capped resolution and upscales, a deliberate trade for a fractal that redraws the instant you move a dial. The finest lace is therefore a touch softer than the pixel grid could carry, and a true zoom, diving into the boundary to watch the same structure repeat scale after scale, is the horizon this plate points toward. The step-through is a first move in that direction: it lets you follow a single orbit by hand and see why a basin has its colour, one iteration at a time. The convergence test is a threshold on the step size, a practical stand-in for the analytic fact of convergence and more than accurate enough at this scale.

The relaxation dial is the single generalization past plain Newton, and it already opens a family of pictures from one method. The richer road, letting the polynomial itself vary or following Newton into the theory of rational maps as dynamical systems, is a subject of its own, and this figure is a good doorway into it.

The logistic plate makes a stronger numerical claim and should say how it earns it. The doubling parameters are solved for rather than quoted: for each cycle the plate tracks the periodic point with Newton’s method on fm(x) − x, which keeps working after the cycle turns repelling, and then bisects for the parameter where the cycle’s multiplier passes through −1. The check is that r₂ comes back as 1 + √6 to twelve digits without ever being told so. Two limits are worth naming. The bifurcation sweep discards a fixed number of iterations before plotting, so parameters very close to a doubling look slightly smeared, since convergence there is genuinely slow and no amount of patience would be enough; that blur is the mathematics, not the renderer. And the period readout gives up past period 64 and reports a long transient rather than chaos when the Lyapunov exponent is negative, which is the accurate report and not the same as knowing. Underneath both sits the arithmetic the bases project is about: at r = 4 the map is conjugate to doubling the binary digits of x, so each step shifts one bit off the end of the mantissa, and after about fifty iterations a double-precision orbit is following an orbit of the map rather than the orbit of the point you asked for.

Keys on this page

A figure's keys are its own: they answer once the figure has focus, so tab to it or click it first. Esc closes this sheet.