A refinement that stops moving

The three rungs below this one all caught an estimator by comparing it with something outside itself: a closed form, a bound, an integration rule of a different kind. That is the honest way and it is not always available. Most of the time there is no closed form, no bound and no second method, and what a careful person does instead is refine.

Double the sample. Compute again. If the answer has stopped moving, it has converged. If it is still moving, extrapolate — the increments have a pattern, and Richardson’s construction turns a pattern of increments into a limit.

This rung is about the two ways that fails. The first is a matter of degree: the extrapolation needs the order, and assuming the wrong one buys a constant factor rather than a rate. The second is not a matter of degree at all.

Richardson, and the order it needs #

An estimate that depends on a spacing $h$ usually behaves like $L - c\,h^{p}$ for some order $p$. Two estimates at $h$ and $h/2$ then give two equations in the two unknowns $L$ and $c$, and eliminating $c$ gives

$$L \approx v_{h/2} + \frac{v_{h/2} - v_h}{2^{p} - 1}.$$

That is Richardson’s, and it is one of the most useful three lines in numerical analysis. It also has an input nobody supplies: $p$.

The default assumption is $p = 2$, because that is the order of every rule anybody writes down first — the midpoint rule, the trapezoid, a centred difference. It is the right assumption most of the time and it is wrong for exactly the case the first rung of this ladder is about, where the extreme being estimated sits on the region’s boundary and the order is one.

Measuring the order rather than assuming it costs one extra estimate — three instead of two — and gives 0.94 for the boundary case, which is the number the extrapolation needs.

Read the middle column down and it looks like a success. The error falls, the extrapolation is better than the raw estimate at every step, and somebody watching only that column would report a converged answer of 3.962 with a clear conscience.

Read it across and the failure is obvious. The middle column falls at exactly the rate of the left one — halving per doubling, order 0.99 against 0.94 — while the right one falls four times as fast. Extrapolating at the wrong order buys a constant and not a rate, so no amount of further refinement lets it catch up, and the gap between it and the truth stays proportional to the raw error forever.

The rejecting form of that statement is what the assertion checks, and it is a statement about slopes rather than about values. A test that compared two numbers would pass on a sequence that had genuinely converged.

The second failure has no rate at all #

The extrapolation problem is repairable: measure the order from three estimates instead of assuming it, which costs one extra evaluation and is what any careful implementation does.

The second failure is not repairable by anything the ladder can see, because the ladder never sees the thing it is missing.

The Robinson projection is not a formula. It is a table of parallel spacings at five-degree intervals with interpolation between, which is what a projection defined by a table has an interpolation in it is about: its first derivative jumps at every entry, so the second derivative is a spike there, and a small circle centred on an entry does not map to an ellipse at all.

The indicatrix is a limit measures what that does. At a table entry the departure of a small circle from its indicatrix is around eight parts in a thousand and does not shrink as the circle shrinks, because there is no limit for it to shrink to. A twentieth of a degree away, the departure at the same radius is sixty times smaller.

So the field being maximised over is a comb: twelve spikes, each of width zero, in sixty degrees of latitude.

The arithmetic that decides it #

A grid of $n$ cell centres over the band from 10° to 70° north puts its samples at

$$\varphi_i = 10° + 60°\,\frac{i + \tfrac12}{n}.$$

That is a multiple of five — a table entry — when $12(2i+1)/(2n)$ is an integer, which happens for some $i$ unless $n$ is a multiple of four. Every odd $n$ hits an entry. Every $n$ congruent to 2 modulo 4 hits an entry. And 4, 8, 16, 32, 64, 128 — the doubling ladder, the sequence every convergence study in every field runs — hits none of them, at any depth.

Increments of 7.1, 4.8, 2.7, 1.5 and 0.8 parts in a hundred thousand: falling by a factor of about 1.8 each time, which is a first-order convergent sequence to within the accuracy anybody checks such things. Richardson at the measured order 0.95 gives a limit of 4.74×10⁻⁴.

The grids that land on a table entry report 1.28×10⁻² and 1.66×10⁻². The converged answer is wrong by a factor of twenty-seven, and every diagnostic available inside the sequence says it is fine.

The latitude column is the tell, and it is the only one. The sequence’s argmax is marching steadily toward the top of the band, which is what an estimator does when the field is smooth and increasing — it is finding the general growth of the departure with latitude, and it will keep finding it forever, because the thing it is not finding has no width. Where the worst point is reads that column as a location, which is exactly the reading it cannot bear here.

What was computed, and how #

The comb is real and is drawn from the same machinery every other Robinson figure here uses; there is no synthetic function anywhere in this essay. The departure is mapCircle’s, at a radius of 0.0003 radians — about two kilometres on the ground — chosen because it is well inside the five-degree table spacing, so the off-node departures are the smooth ones and the ratio between a node and its neighbourhood is sixty-two.

The assertion carrying the rung has four parts and each could fail alone. The doubling ladder must miss every entry; the grids listed as hitting one must hit it; the ladder’s increments must fall by a factor between 1.4 and 2.6, so that it genuinely reads as convergent rather than merely as noisy; and its extrapolated limit must be at least eight times below what a hitting grid reports. A version of Robinson with a smoother interpolation would break the last, and would be a legitimate reason for this essay not to exist.

The extrapolation figure is checked against the closed form throughout, so nothing there depends on the refinement being trusted.

Why the doubling ladder is the worst possible choice #

There is a temptation to call the multiple-of-four business a coincidence, and it is worth resisting, because the same structure appears whenever a periodic feature is sampled by a grid whose size is refined by doubling.

A comb of features at spacing $s$ and a grid of spacing $h$ interact through the ratio $s/h$. Doubling $h$ preserves the ratio’s prime factorisation apart from powers of two, so a grid that misses because $s/h$ has a factor of two in the wrong place keeps missing at every doubling. Refining by a factor of three, or by adding one to the count, breaks the resonance immediately — the ladder 4, 5, 6, 7, 8 finds the spikes at four of its five steps.

So the standard convergence test is the one refinement schedule that cannot detect a periodic feature, and it is standard because doubling makes Richardson’s arithmetic simple. The two properties are the same property.

The general repair is to refine by a factor that is not an integer at all — 1.7, say — or to check one non-doubled grid at the end. Both cost one extra evaluation and neither is standard practice anywhere.

The condition in general, which is about powers of two #

The multiple-of-four rule is a fact about this band and this table, and the argument behind it generalises to a statement that can be checked before any sampling is done.

Put n cell centres across a band divided into m equal intervals. A sample lands on an interval boundary when m(2i + 1) = 2jn for some integers i and j. The left side is m times an odd number, so its power of two is exactly that of m; the right side’s is that of n, plus one. A solution therefore exists precisely when

$$v_2(n) \;<\; v_2(m),$$

with v₂ the number of times two divides a number.

Here m is 12, whose power of two is 2, so n must have a power of two below 2 — that is, n not divisible by four, which is the rule the table found. The doubling ladder has v₂(n) growing without bound, so it fails the condition from n = 4 onward and fails it forever.

The general form says two things the special case cannot.

Some interval counts can never be hit at all. If m is odd — a band of fifteen degrees divided at five-degree steps, say, or any table whose entries divide the sampled range into an odd number of pieces — then v₂(m) is zero and no n whatever satisfies the inequality. A cell-centre grid then misses every table entry at every resolution, and the doubling ladder is not the culprit: no schedule of any kind would help, and only moving the samples off the cell centres would.

And the fix is arithmetic rather than a matter of refining harder. Since the condition involves only the powers of two, a single grid whose count is odd finds every entry whenever m is even at all — one evaluation, chosen by a property of two integers both of which are known in advance. That is a stronger version of the check one grid off the ladder rule above: the grid to check is not an arbitrary non-doubled size but any odd one, and it is guaranteed rather than likely to work.

The uncomfortable half remains. Knowing m means knowing where the field is non-smooth, and a measurer who knew that would have sampled there on purpose. The condition is a tool for somebody who suspects a comb and not a detector for somebody who does not.

What a better test looks like #

That picture is the argument in one image, and it also contains the repair. Any schedule that visits a size not divisible by four finds the answer immediately, at a cost of one evaluation, and three quarters of all sizes qualify.

So the practical rules are short:

Measure the order, do not assume it. Three estimates instead of two, and the extrapolation is licensed rather than hopeful. The cost is one more evaluation and it turns the middle column of the table above into the right-hand one.

Refine by something other than two. A factor of 1.7, or a schedule that adds a fixed number rather than multiplying, breaks any resonance between the sampling and a periodic feature. Doubling is standard because it makes the extrapolation arithmetic tidy, and tidy arithmetic is a poor reason to adopt the one schedule that cannot see a comb.

Check one grid that is not on the ladder. The cheapest of the three, and the one this collection now does: after a doubling sequence has settled, evaluate once at a size chosen to have no factor in common with the others and see whether the answer moves.

And where a quantity is known to be non-smooth, sample its non-smooth places directly. Robinson’s table entries are at twelve known latitudes. Nothing about this failure survives evaluating there on purpose, and the reason nobody does is that the projection’s smoothness is a property of its definition rather than of its output, so it is not visible to anyone measuring it.

Where the model stops #

A sampled maximum is the statistic at risk here, and the first rung established why: it is a lower bound with a sign, so a feature it misses is a feature nothing else will report.

Not every quantity in this collection has a comb in it. Robinson’s table is the only projection in the library whose derivative jumps, and the interpolated members of the family defined by tables are a small minority. Everything else here is analytic, and for an analytic field the doubling ladder is exactly as trustworthy as it looks.

The failure needs the feature to be narrower than the sample. At a circle radius of 0.01 radians rather than 0.0003 the spikes are three degrees wide, every grid finds them, and there is nothing to report. So this is a statement about the ratio of a feature’s width to a spacing, not about Robinson.

And a maximum is the fragile statistic here, not a mean. A comb of twelve zero-width spikes contributes nothing to an integral, so every average computed over Robinson is unaffected — which is why the means in this collection are stable and its maxima are not. The two failures the first rung separated stay separated all the way down.

The generalisation #

The rule is one sentence and it is uncomfortable: a refinement sequence can only report on what its samples touch.

That sounds tautological and is not, because the whole point of a convergence test is to certify a limit rather than a sample — to make a statement about the continuum from a statement about a finite set. It is a valid inference when the quantity is smooth on the scale of the spacing, and it is not an inference at all when it is not, and nothing inside the sequence distinguishes the two cases.

The version of this that has bitten this collection elsewhere is the condition imposed at points, where a projection solved to satisfy a requirement at four hundred sample points satisfies it nowhere else and reports a residual of zero. That is the same statement with the arrow reversed: there, a solver’s samples decided what was true between them; here, a measurer’s samples decide what is true between them. Both are the claim that a finite set stands for a continuum, and in both cases the thing that fails is the report rather than the arithmetic.

Who found it, and when #

Richardson published the extrapolation in 1911, in a paper about finite differences for physical problems, and the requirement that the order be known is stated in it. Every textbook since repeats the requirement and every implementation defaults to two, because a default is needed and two is right for the rules the textbook has just introduced.

The comb is Robinson’s, from 1963, and Arthur Robinson never claimed his projection was smooth — he built it by hand, as a table, on the explicit ground that a formula would have made it worse. The consequences for its derivatives were noticed almost immediately by the people who had to implement it, and the standard implementations differ in their interpolation because there is no right answer.

What is not in either literature is the meeting: that the standard test for the accuracy of a numerical answer, applied to the standard interpolated projection, is guaranteed by the arithmetic of the two to miss the only interesting points in the domain. It takes a comb of period five, a band of width sixty and a habit of doubling, and each of those three was chosen for reasons that had nothing to do with the other two.

Where the ladder goes next #

Four rungs have shown that a sampled maximum is a lower bound, that a sampled mean can be a report on the sampler, that no arrangement of points is neutral, and that refining until the answer settles proves nothing. What that adds up to is a question about this collection: which of its published numbers are actually the sampler’s? The last rung of this ladder answers it by re-measuring them, and the answer is more comfortable than these four rungs suggest, for a reason that turns out to matter more than any of the individual failures.