Matpic
mathematics, in pictures
Series

Iteration — the series

9 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. the logistic map at 3.2, iterated from 0.2. A map drawn as a curve with the diagonal across it, and the staircase that iterating it produces.

    The staircase that shows the whole orbit

    Take a number, feed it to a rule, feed the answer back in. There is a way of drawing that on the rule's own graph which turns the entire future of a starting point into a shape — and the shape is legible.

    part 1 · dynamics
  2. How fast an iteration arrives. The distance from the fixed point plotted against the step number on a logarithmic vertical axis, for two ordinary iterations and for Newton's method, whose curve bends downward.

    How fast the staircase arrives

    The slope at a crossing decides whether an orbit reaches it. The same number decides how fast — and when the slope is zero the arithmetic changes kind, from a fixed factor per step to a doubling of the correct digits.

    part 2 · dynamics
  3. The tent map and the logistic map, joined by a change of coordinate. Two cobweb diagrams side by side — the tent map at slope two and the logistic map at four — with the orbit of one carried to the orbit of the other by a curve drawn between them.

    The same map in different coordinates

    The tent map and the logistic map at four look nothing alike and are the same map, carried onto each other by a change of variable. Everything either one does the other does, and the change of variable is a sine squared.

    part 3 · dynamics
  4. Where a long orbit of the logistic map spends its time. A histogram of 60000 iterates in 32 bins, with the density the map preserves drawn over it as the exact share each bin should hold.

    The histogram an orbit leaves

    When no single step of an orbit is worth reporting, what is left is where it spends its time. That distribution is not uniform, it does not depend on where the orbit started, and it can be computed in closed form.

    part 4 · dynamics
  5. The orbit a computer draws, and the orbit. Two orbits of the tent map from the same starting fraction plotted against the step number — one computed exactly in whole-number arithmetic and periodic, one computed in double precision and reaching zero.

    The orbit a computer draws

    A chaotic orbit computed in floating point is not the orbit of the point it started from. Sometimes it is the true orbit of a nearby point, which is enough; sometimes the arithmetic simply runs out, and the picture is of the rounding.

    part 5 · dynamics
  6. How long four orbits of the doubling map spend in each quarter. Grouped bars for four starting points of the doubling map, each group showing the fraction of time the orbit spends in each quarter of the unit interval, against a dashed line at one quarter.

    Almost every orbit is fair

    Double a number and keep the fractional part, and do it again, and again. Where the orbit goes is written in the number's binary digits, and for almost every starting point it spends exactly a quarter of its time in each quarter of the interval. The proof is a short argument about Fourier coefficients being pushed to infinity — and it leaves room for a set of exceptions with no length at all, which includes every fraction and, for all anyone can prove, every number anyone has ever named.

    part 6 · dynamics
  7. The Chebyshev maps T₂, T₃, T₄ and T₅. Four small square plots of the Chebyshev polynomials of degrees two to five on the interval from minus one to one, each with the diagonal drawn; the graph of degree n sweeps between the bottom and top of the square n times.

    A solvable chaos of every degree

    The logistic map at four is chaotic and, through a change of coordinates, completely solvable: its orbits are cosines of doubling angles. The trick is not a one-off. For every whole number n there is a polynomial of degree n that multiplies angles by n instead of 2, and every one of them is exactly as solvable, has exactly nᵏ points of period k, and preserves the same distribution — and any two of them commute, which almost no two polynomials do.

    part 7 · dynamics
  8. The cosines of the powers of two. cos(2^k) for k < 600, with a histogram of 20,000 points against the arcsine density.

    The cosines of the powers of two

    Start at cos 1 and apply x ↦ 2x² − 1 over and over. The map is chaotic and exactly solvable: the k-th point is cos(2ᵏ), the cosine of two to the k radians. Iterate it in floating point and the computed orbit leaves the true one after 51 steps. Read the binary digits of 1/(2π) instead and the true orbit can be followed for as long as digits can be computed — here 262,080 steps — and at that length it is as fair as any orbit can look. Whether it stays fair is a question about those digits, and nobody can answer it.

    part 8 · dynamics
  9. Differences round a ring. Four numbers 0,7,3,1 under repeated differences round a ring, reaching zero in 7 steps: 0 7 3 1 / 7 4 2 1 / 3 2 1 6 / 1 1 5 3 / 0 4 2 2 / 4 2 0 2 / 2 2 2 2 / 0 0 0 0.

    Differences round a ring

    Write four numbers at the corners of a square and put on each side the difference of its two corners. Repeat with the new square. Whatever the four whole numbers are, the process reaches nought within a few steps. Write five numbers and it almost never does. Rings whose size is a power of two always finish, and every other ring settles into a cycle whose length depends on how a polynomial factors over two elements: 7 at seven, 341 at eleven, 31 at thirty-one.

    part 9 · dynamics

All series