The orbit a computer draws

Every figure in this field is computed, and a computed orbit of a chaotic map is wrong. Not slightly wrong in the way a plotted curve is: wrong in every digit within a few dozen steps, because nearby orbits separate exponentially and the rounding at each step is a small displacement to be amplified.

That is not a reason to distrust the pictures, and the reason it is not is more interesting than the problem. But there is one case where it is a reason, and telling the two apart is what this rung is for.

The tent map runs out of number #

The tent map at slope two is a shift of the binary places, exactly. Doubling moves every bit one place left; the fold takes care of the case where the leading bit was one.

A double-precision number carries fifty-three significant bits. Shift them left fifty-three times and there is nothing left: the value is exactly zero, and zero is a fixed point. Every starting point, without exception, reaches zero and stays there, in about as many steps as the arithmetic has bits.

That was measured rather than reasoned about. Building the histogram figure for the rung below with the tent map iterated directly gave sixty thousand steps of which 59,948 landed in the first bin — and it would have looked like an ordinary histogram to anybody who did not check the first bar.

The exact orbit does no such thing. A fraction $p/q$ with $q$ odd maps to $2p/q$ or $2(q-p)/q$, so the denominator never changes and the numerator walks around the whole numbers below $q$. That walk is eventually periodic, it never reaches zero, and the figure computes it in integer arithmetic and finds its period by looking for the repeat.

The failure is total and it is invisible. A dying orbit and a settling orbit look alike; the difference is that one is a property of the map and the other is a property of the machine.

Why the parabola survives and the tent does not #

The logistic map at four is conjugate to the tent map, so the two have the same dynamics — and one is computable and the other is not. That looks like a contradiction and is not.

The conjugacy is a topological statement. It preserves orbits and cycles and says nothing about arithmetic, and the change of coordinate $\sin^2(\pi y/2)$ does not carry a floating-point number to a floating-point number.

More concretely: the tent map’s rounding errors are structured. Every step discards exactly one bit off the bottom and shifts, so the errors all point the same way and accumulate into a total loss of information. The logistic map’s arithmetic — a multiplication and a subtraction — produces rounding errors that are not aligned with the map’s own stretching, and the orbit stays somewhere in the interval indefinitely.

So the computability of an orbit is a property of the formula rather than of the dynamics, and two formulas for the same map can behave completely differently. That is a statement worth carrying beyond this field: conjugate systems are numerically incomparable.

The lemma that rescues the other pictures #

If a computed chaotic orbit is wrong in every digit, the reasonable conclusion is that no picture in this field means anything. The reasonable conclusion is wrong, and the reason is a theorem.

The shadowing lemma. For a uniformly hyperbolic map, a pseudo-orbit — a sequence in which each step is correct to within $\delta$ — is shadowed by a genuine orbit: there is a true starting point whose orbit stays within $\varepsilon$ of the computed sequence for all time, with $\varepsilon$ small when $\delta$ is.

So a computed orbit is not the orbit of the point it was started from, and it is the orbit of some point very near it. Every statistical claim made from it — the histogram, the Lyapunov exponent, the density — is a claim about a genuine orbit of the map, which is all those claims ever needed.

Two conditions are doing the work and both matter. Uniform hyperbolicity: the map has to be expanding by a definite factor everywhere, with no neutral directions. And all time: the theorem gives a single true orbit shadowing the whole computed sequence, not a different one for each stretch.

The logistic map at four satisfies the first, which is why its histogram is trustworthy. Most maps of interest do not, and for them shadowing holds over finite stretches with the length depending on the map — which is a much weaker guarantee and is the honest state of the art.

What a figure in this field has to do #

The site’s standing rule is that every figure decides something by an argument that could fail, and the discipline this rung is about is the specific form that takes here.

Compute the claim independently of the picture. The invariant density is known in closed form, so the histogram is compared against exact bin masses rather than against itself. The conjugacy identity is checked at four hundred sampled points. The multiplier is computed from the derivative and compared against a measured ratio of errors.

Prefer exact arithmetic where the claim is exact. The orbits in the figure above are integers over a fixed denominator, so the period is a fact and not a measurement. The tail that squeezes $e$ is the same discipline in another field, and for the same reason: a claim that a quantity lies strictly inside an interval cannot be checked by an arithmetic that has already rounded it to the edge.

Assert the thing that would break. A chaotic figure looks the same whether or not the arithmetic behind it is right, so an assertion that merely reports the smear proves nothing. What is asserted has to be a quantity a wrong implementation would get wrong — an exact period, a closed-form density, a count of crossings.

Two orbits from one starting point #

The clearest demonstration that the arithmetic is doing the work costs nothing to run: compute the same orbit twice, with the two arithmetics differing only in the last bit.

Start the logistic map at four from $0.4$ and from $0.4000000000000001$. The two agree for about forty steps and then have nothing to do with each other. That is sensitive dependence and it is a property of the map — a genuine feature, and the reason the field exists.

Now start it at $0.4$ twice, once evaluating $4x(1-x)$ and once $4x - 4x^2$. The two expressions are equal in exact arithmetic and are not equal in floating point, because they round differently. The two orbits agree for about forty steps and then have nothing to do with each other, and this time the divergence is entirely an artefact.

The two experiments look identical and mean opposite things. In the first, the map amplified a real difference in the inputs. In the second, it amplified a difference that does not exist.

That is the practical reason a chaotic computation cannot be verified by re-running it. Agreement between two runs is evidence of nothing if both are computed the same way, and disagreement between two runs is evidence of nothing if the two ways round differently. The only useful check is against a quantity known independently — which is what the previous rung’s exact bin masses are for.

What is being rescued, and what is not #

The shadowing lemma justifies a specific class of conclusion and it is worth being precise about the boundary, because the licence is often taken more broadly than it is given.

Justified: statistics. Histograms, time averages, Lyapunov exponents, correlation decay. All are properties of a true orbit near the computed one, so the computation reports them correctly.

Justified: qualitative structure. That an attractor exists, roughly where it is, roughly what shape it has. A shadowing orbit stays close, so it visits the same regions.

Not justified: the state at a given time. No claim about where the true orbit of the given starting point is at step one thousand survives, and none is available by any amount of computation.

Not justified: existence of a periodic orbit. A computed orbit that appears to close up may be shadowing a genuine orbit that does not, and this is a real failure mode — spurious short cycles are common in low-precision iteration of chaotic maps and are entirely artefacts of the finite state space.

The last is worth a sentence more. A computer’s floating-point numbers are a finite set, so every computed orbit is eventually periodic, always, for every map. The period may be astronomically long or it may be four; nothing about the map determines it, and any conclusion drawn from a computed orbit closing up is a conclusion about the arithmetic.

The same problem outside this field #

The failure has a general shape and three neighbours are worth naming, because none of them involves chaos and all of them have the same cause.

Catastrophic cancellation. Subtracting two nearly equal numbers destroys the leading digits and promotes rounding error to the front. Solving a quadratic by the usual formula loses most of its precision when the two roots are far apart, and the repair is to compute one root by the formula and the other from the product of the roots.

Summation order. Adding a long list of numbers in a different order gives a different answer, and the difference can be large when the terms vary in size. That is why the exact rational arithmetic in the squeeze on $e$ is not fastidiousness: a claim about a strict inequality cannot survive an arithmetic that rounds one side of it.

Ill-conditioned systems. A linear system whose matrix nearly collapses amplifies input error by the ratio of the largest stretch to the smallest — which is what a map does to a circle, measured as a condition number. There is no iteration and no chaos; the amplification happens once.

In every case the diagnosis is the same. The problem amplifies, the arithmetic supplies something to amplify, and the answer’s error is the product of the two. Chaos is the case where the amplification is exponential in the number of steps, which makes the failure spectacular rather than different in kind.

How long a computed orbit is worth anything #

The practical question is how many steps can be trusted, and there is an arithmetic for it.

An error grows by a factor of $e^{\lambda}$ per step, with $\lambda$ the Lyapunov exponent. Starting from a rounding error of about $10^{-16}$ and asking when it reaches the size of the interval gives

$$n \approx \frac{16\ln 10}{\lambda},$$

which for $\lambda = \ln 2$ is about fifty-three steps. That is the number of steps for which the computed orbit tracks the true orbit of its own starting point, and it is the same fifty-three that the tent map runs out at — for a related but not identical reason.

Doubling the precision buys twice as many steps, which is a poor exchange: a hundred and six steps for double the memory and several times the arithmetic. This is the central practical fact about chaotic systems and it is why long-range prediction is not a computing problem. A weather model with a doubling time of a day and a hundred times better initial data gains about a week, which is the same arithmetic the Lyapunov exponent reports read as a schedule rather than as a rate.

Prediction is linear in the precision and the precision is logarithmic in the effort. Everything anybody has ever wanted from a chaotic system that is not a statistic runs into that.

Computing with enclosures instead of numbers #

There is a way to make a computed statement about a chaotic system into a theorem, and it works by giving up on numbers.

Interval arithmetic replaces each value by a pair — a lower and an upper bound, each rounded outward — and defines the operations so that the true answer is guaranteed to lie inside the resulting interval. An orbit computed this way is a sequence of intervals, each certainly containing the true iterate, and the intervals grow.

For a chaotic map they grow fast, so a naive interval orbit becomes the whole state space within a few dozen steps and says nothing. What makes the method work is not following an orbit at all: it is proving a statement about a region — that a certain box maps into another, that a certain map has a fixed point in a certain box, that a certain derivative is bounded away from one on a set.

That is how the Lorenz attractor was established. Smale’s fourteenth problem asked whether the equations really have the attractor the pictures show; Warwick Tucker settled it in 1998 with a rigorous interval computation, checking that a carefully chosen region maps into itself with the right expansion properties. The computation is enormous, every step is an enclosure rather than an estimate, and the conclusion is a theorem.

The general lesson is to move the question. A computed orbit cannot be trusted and a computed statement about a region can be, because a region is large enough to absorb the rounding. Every rigorous result about a chaotic system takes that route, and the ones that do not are statistics justified by shadowing.

What the picture cannot show #

The figure draws two orbits and the shadowing lemma is about a third — the true orbit near the computed one, which is not the exact orbit drawn and is not the float orbit either. There is no way to draw a point that is not known, and the whole content of the lemma is that such a point exists.

It cannot show the bits. What is happening in the float orbit is that the mantissa is emptying, and the drawing shows the value, which stays plausible until the moment it is zero. A figure with the binary places on it would be more honest and would be about a representation rather than about a map.

And the exact orbit is only available because the starting point is a fraction. Almost every real number is not, so for almost every starting point there is no exact orbit to compare against and the comparison this figure makes cannot be made. The case that can be checked is the case that is not typical, which is the standing situation whenever a computation is verified at all.

Where the ladder goes next #

Above: interval arithmetic and computer-assisted proof, where the machine carries a rigorous enclosure of the orbit rather than an approximation of it, and produces theorems — the proof that the Lorenz attractor exists is of that kind. And the numerical analysis of shadowing, which turns the lemma into a computable bound for a particular orbit.

One debt. Uniform hyperbolicity is quoted here as the hypothesis of the shadowing lemma and is not defined properly. It is the condition that the map expands by a definite factor in every direction at every point, and the maps of most interest — including the one with two lobes — do not satisfy it.

What the arithmetic decided #

A computed chaotic orbit is not the orbit it was started from, and the question is whether it is anybody’s.

Where the map is uniformly expanding, it is: some nearby point has exactly that orbit, and every statistical claim survives. Where the arithmetic is a bit shift, it is not anybody’s — the orbit dies, no true orbit does that, and the picture is of the machine. The two cases are indistinguishable from the drawing, which is why the discipline is to compute the claim by a second route and compare.