How fast the staircase arrives

The slope at a crossing decides whether an orbit arrives: shallow and the staircase walks in, steep and it walks out. That is a yes-or-no question and the same number answers a quantitative one that matters more in practice.

How long does arriving take? The answer is that the distance to the fixed point is multiplied by the slope at every step — so the slope is not merely a threshold, it is a rate, and reading it that way turns a picture into a prediction.

The error obeys the derivative #

Write $p$ for the fixed point and $e_n = x_n - p$ for the error at step $n$. Then

$$e_{n+1} = f(p + e_n) - f(p) = f'(p)\,e_n + O(e_n^2),$$

which is the derivative doing what it is for: near enough to a point, a smooth function is its tangent line.

So once the error is small, each step multiplies it by $\lambda = f'(p)$. The distance falls geometrically, the number of correct decimal places grows by a fixed amount per step, and a logarithmic plot of the error is a straight line with gradient $\log|\lambda|$.

The figure measures that. It runs the logistic map at two parameters, computes $\lambda = 2 - r$ from the arithmetic, and compares it against the ratio of successive errors taken from the orbit — two numbers reached by different routes, required to agree.

Where that ratio is measured is part of the claim. The exact recurrence is $e_{n+1} = \lambda e_n - r e_n^2$, so the measured ratio is $\lambda - r e_n$ and equals $\lambda$ only once the error is small. At $r = 2.95$ the second term is still a twentieth after fourteen steps, which is more than the tolerance; taking the reading at a fixed step number therefore tests how fast the particular parameter happens to converge rather than the claim. The figure takes it at the last step before the error reaches the rounding floor, which is where the higher-order term is smallest.

What the rate is worth in digits #

Turning the factor into something usable: if the error is multiplied by $|\lambda|$ each step, the number of correct decimal places grows by $-\log_{10}|\lambda|$ per step.

At $|\lambda| = 0.5$, that is about $0.3$ places per step — three steps per digit. At $|\lambda| = 0.9$, about $0.046$ — twenty-two steps per digit. At $|\lambda| = 0.99$, two hundred and thirty steps per digit.

Convergence is a smooth function of the slope and usability is not. An iteration with $\lambda = 0.5$ is a tool; one with $\lambda = 0.99$ converges, in the sense that a proof is available, and is useless. The threshold at $|\lambda| = 1$ that the rung below is about is the boundary of a region in which the behaviour varies by three orders of magnitude.

The case where the slope is zero #

If $f'(p) = 0$ the linear term vanishes and the next one takes over:

$$e_{n+1} \approx \tfrac{1}{2}f''(p)\,e_n^2.$$

The error is squared each step, not multiplied. The number of correct digits doubles rather than growing by a fixed amount, and a few steps take a rough guess to machine precision.

Such a fixed point is called superattracting, and the standard way to reach one is Newton’s method. Solving $g(x) = 0$ by iterating

$$N(x) = x - \frac{g(x)}{g'(x)}$$

gives a map whose derivative at a simple root is exactly zero — a short computation, and the whole reason the method is fast.

The figure runs it on $x^2 - 2$, from $1.9$, and asserts two things rather than one. Exactly: $e_{n+1} = e_n^2/(2x_n)$, which is algebra on the Newton step and holds at every step to the last bit. Approximately: the ratio $e_{n+1}/e_n^2$ approaches $1/(2\sqrt2)$, which is the limiting constant everybody quotes.

Asserting the second at every step would fail on the first, by a third — $x_0$ is $1.9$ and $\sqrt2$ is $1.414$. That is not an error in the iteration; it is an error about which of the two statements is a theorem, and the two are separated here for that reason.

What quadratic buys, in numbers #

From an error of $0.5$:

Five steps of the quadratic method exhaust double precision. Five steps of the linear one have gained one and a half digits.

That gap is the reason the distinction is not academic. Every root-finding method in use is chosen for its order of convergence, and the orders available are a small list: bisection is linear with $\lambda = 1/2$; the secant method is of order $1.618$, the golden ratio, because its error obeys a Fibonacci-like recurrence; Newton is quadratic; and Halley’s method, using the second derivative, is cubic.

Reading the rate off a picture nobody drew for it #

The rate is available from the cobweb itself, which is worth knowing because the logarithmic plot needs the answer in advance and the staircase does not.

Near the crossing the curve is nearly its tangent, so the staircase’s steps form a near-geometric sequence: each horizontal run is $|\lambda|$ times the one before. So the ratio of consecutive step widths is the rate, and it can be measured with a ruler on a drawing where the fixed point is not marked.

The sign shows up as the shape. A positive slope gives a staircase that walks in from one side, monotonically; a negative one gives a spiral, with the orbit alternating either side of the crossing. That distinction is visible immediately and is invisible in the error plot, where only $|\lambda|$ appears.

So the two pictures carry complementary information. The staircase shows the sign and the qualitative behaviour and reads the rate badly; the error plot reads the rate precisely and loses the sign. Neither is a substitute, and the site’s habit is to draw both when both matter.

Why a fast method can still be a bad one #

The order of convergence is the wrong thing to optimise on its own, and it is worth saying why before the table above is read as a ranking.

Newton needs the derivative. If it is unavailable or expensive, the secant method’s lower order may be reached in less total work — its order is $1.618$ but each step costs one function evaluation rather than two.

Newton is not global. Quadratic convergence is a statement about what happens near the root, and starting elsewhere the method may cycle, diverge, or land in the basin of a different root — which is what Newton’s basins are a picture of. Bisection, at $\lambda = 1/2$, is the slowest method on the list and the only one that cannot fail.

Order says nothing about a multiple root. At a root where $g$ and $g'$ both vanish, Newton’s derivative at the fixed point is not zero but $1 - 1/m$ for a root of multiplicity $m$ — so the method degrades from quadratic to linear, and to linear with a rate that approaches one as the multiplicity grows.

That last is the sharpest case and it is worth having as a warning. A method’s advertised order is a property of the generic case, and the situations where a fast method is actually needed are frequently the degenerate ones where it does not have it.

The neutral case, where the rate is not a rate #

At $|\lambda| = 1$ the linear term neither shrinks nor grows and the behaviour is decided by what comes after — which means it is not geometric at all.

Take $f(x) = x - x^3$ near zero, whose derivative at zero is exactly one. The orbit does converge to zero, and it converges like $1/\sqrt{n}$: the error after $n$ steps is about $1/\sqrt{2n}$, so reaching three decimal places takes half a million steps.

That is qualitatively unlike either case above. There is no factor per step; the rate itself decays; and a logarithmic plot of the error against the step number is a curve, not a line, bending the wrong way.

The neutral case is also where the sign of the higher term decides everything. $x - x^3$ converges to zero from either side; $x + x^3$ leaves it. Both have $\lambda = 1$, and no amount of information about the derivative separates them.

Where the linear term is silent, the answer is not a rate but a different kind of question. That is the standing situation at every threshold in this field: the logistic map at $r = 3$ has a neutral fixed point and takes thousands of steps to settle, and the same is true at every parameter where a doubling happens.

Cycles have a rate too, and it is a product #

A cycle of length $k$ is a fixed point of $f$ applied $k$ times, so its multiplier is the derivative of the composed map — which by the chain rule is the product of the slopes at the cycle’s points.

That has a consequence worth stating, because it is not obvious from the definition. A cycle can be attracting while every one of its points sits where the map is expanding, provided the product of the slopes is small enough — and it can be repelling while some of its points are in flat regions. The rate belongs to the cycle rather than to any of its points.

It also explains why the doublings accelerate. Each new cycle’s multiplier is a product of twice as many numbers, so it sweeps through the interval from $0$ to $-1$ over a shorter range of the parameter; the cascade’s geometric spacing is that acceleration measured.

The same arithmetic outside this field #

The rate is not about the logistic map or about roots, and three places it turns up with a different name are worth naming because they are the same calculation.

Contraction mappings. A map that shrinks everything by a factor $k < 1$ has a unique fixed point and orbits reach it at rate $k$ — which is this section’s linear case with the derivative bound replaced by a uniform one. The theorem gives existence as well as the rate, and the price of the uniformity is that the rate is the worst one anywhere rather than the one at the fixed point.

Iterative solvers for linear systems. Solving $Ax = b$ by repeatedly applying an affine map converges at a rate set by the largest eigenvalue in size of the iteration matrix — the multiplier generalised to several dimensions. One number again, and the same threshold at one, with the same catastrophe as it is approached.

Markov chains. How fast a chain forgets where it started is set by the second-largest eigenvalue of its transition matrix, and the mixing time is the reciprocal of the gap below one. The vocabulary is entirely different and the arithmetic is identical.

In every case the pattern is: linearise about the answer, find the factor, and the factor is the rate. That the same object — a derivative, a matrix’s spectrum, an eigenvalue — plays the part in all three is the reason this rung is worth having as a rung rather than as a remark inside another essay.

What the picture cannot show #

The figure plots the error, which requires knowing the answer. That is available here because the fixed points are known in closed form, and in every situation where an iteration is actually used it is not — so the picture is a diagnostic drawn after the fact rather than something a practitioner sees.

It also cannot show the floor. Every curve stops where the error reaches the rounding limit, and past that point the plotted quantity is a fact about arithmetic rather than about the iteration. The Newton curve reaches it in five steps, which is why it is drawn for five and not for twenty.

And a logarithmic axis makes a straight line out of a constant factor, which is what makes the rate legible — and makes the early steps, where the linear approximation is not yet valid, look like a defect in the data. They are not. They are the higher-order terms, and they are the reason the figure measures its rate at the far end.

Where the ladder goes next #

Above: two maps that turn out to be one map in different coordinates, which is how a hard iteration is turned into an easy one; the statistics an orbit leaves behind when no single step is worth reporting; and what a computer’s arithmetic does to an orbit it cannot represent.

One debt. The order of the secant method is quoted here as the golden ratio and the Fibonacci recurrence behind it is named rather than derived. It is a short derivation and it is one of the more surprising places that number appears, and it belongs on the golden ratio’s own ladder rather than on this one.

What the slope was measuring all along #

The derivative at a fixed point is the factor the error is multiplied by, and everything about how an iteration performs follows from it.

Below one in size, the orbit arrives and the rate is that number. At zero, the linear term is gone and the error squares, which is what makes Newton’s method the tool it is. At one, there is no rate at all and the answer depends on what the derivative could not see. Three regimes, one number, and the picture that shows which is the same staircase the bottom of this ladder drew.