The accuracy that is thrown away

Newton’s method for F(x) = 0 does one thing per step: it replaces F by its tangent at the current point and solves the linear problem exactly. Everything anybody knows about the method — that it doubles the correct digits, that it needs a good starting point, that it converges quadratically near a simple root — is a statement about that replacement rather than about the linear solve.

At the sizes where any of this is expensive, the linear solve is iterative and it stops when a tolerance says so. So there is a number to choose, it is called the forcing term, and the natural instinct is that it should be small: the step is what the method is made of, and a step computed badly is a bad step.

The instinct is wrong, and it is wrong by a factor that can be measured rather than argued about.

The plateau #

The measurement is direct and needs no theory to state. Take an iterate 3.719·10⁻² from the root of the model problem — a root that is known exactly, because the right-hand side was built from it. Solve the Newton system at that point to a relative residual of 10⁻³, and the point it steps to is 2.4966·10⁻³ from the root, at 354 conjugate gradient iterations. Solve the same system to 10⁻¹⁴, and the point it steps to is 2.4967·10⁻³ from the root, at 1,126.

Eleven decades of inner accuracy. Four parts in ten thousand of difference in the answer. A factor of 3.2 in work.

That is the whole essay and the rest of it is about why the floor is where it is, how far the effect extends, and what it costs to ignore.

Why there is a floor at all #

A Newton step solves J(x)·s = −F(x), and s is the exact correction for the linearised problem. The real problem is not linear. Expanding F about x,

F(x + s) = F(x) + J(x)s + ½·F″(ξ)[s, s]

and the step is chosen to kill the first two terms exactly, so what is left is the second-order term — of size proportional to ‖s‖², which near the root is proportional to the distance from it, squared.

The step therefore cannot land closer than a constant times d², where d is where it started, however exactly the linear system is solved. Below that, the accuracy of the linear solve is being spent on a difference between two points that are both the wrong point by the same amount.

That is a derivation, and this collection’s habit is to measure the thing rather than take the derivation’s word for it. Five iterates, five plateaus:

Fitted on log axes, the plateau’s height against the distance it started at has a slope of 1.82, against a predicted 2. Not 1, which is what a floor set by the linear solve’s own error would give, and not 0, which is what a floor set by the arithmetic would give. The constant is between 0.5 and 1.9 across the five, which is order one — so the floor is the linearisation and it is not an artefact of the conditioning, which runs to 10⁵ on this problem and does not appear — a conditioning that decides less than it is credited with, which is a recurring finding here.

The 1.82 is the fit, not the law #

A slope of 1.82 against a predicted 2 is close enough to report and far enough off to be worth explaining, and the explanation is in the same five rows rather than in anything further.

Take the constant rather than the exponent — the plateau divided by the square of the distance it started at — and it is not constant. It runs 0.481, 0.695, 1.165, 1.805, 1.925, rising monotonically and flattening at the end. A quantity with a drifting constant fitted as a pure power law returns an exponent that has absorbed the drift, which is exactly what 1.82 is.

The local slopes say the same thing and say it more usefully. Between the first pair of iterates the slope is 1.478, between the second 1.505, between the third 1.721, and between the last pair 1.976. The exponent is converging to 2 as the iteration approaches the root, which is what “the second-order term dominates near a simple root” means when it is written as a measurement rather than as a theorem.

So the far rows are not noise and they are not a failure of the model — they are the pre-asymptotic regime, where an iterate 1.03 away from the root is not close enough for the third-order term to be negligible against the second. The fit spans both regimes because five points is what was affordable, and reporting one number over both is what pulls it to 1.82.

That is worth carrying beyond this figure. A fitted exponent over a range that includes the approach to an asymptote is biased towards the pre-asymptotic value, always, and the diagnosis is always the same: plot the constant the fit assumed was constant, or take the slope pairwise. Both cost nothing once the data exist, and either would have said that the law here is 2 and the last decade of the measurement already knows it.

It also sharpens the claim the section makes. The alternatives it rules out are slope 1, which is what a floor set by the linear solve’s own error would give, and slope 0, which is what a floor set by the arithmetic would give. The measured sequence 1.478 → 1.976 is not near either of them anywhere, and it is approaching the third. A single 1.82 would leave a reader entitled to wonder whether the truth might be 1.5 and drifting; the pairwise slopes say it is 2 and arriving.

And the constant is what the rule needs #

The constant matters as well as the exponent, because the practical statement of this essay is a tolerance and a tolerance is a number rather than a scaling law.

At the last two iterates the constant is 1.81 and 1.92, so the plateau is very nearly 2d² — the step from distance d lands about twice d² from the root, whatever the inner solve does. That converts directly into the usable inner tolerance. The inner solve’s own contribution to the step’s error is about η·d, so it stops mattering when η·d falls below 2d², which is when η falls below about 2d.

At the iterate 3.719·10⁻² from the root that is η ≈ 0.07, and the table shows tolerances from 10⁻³ downwards all landing on the plateau — 10⁻³ is already more than an order below the threshold, which is why every row of it agrees. At the last iterate, 2.497·10⁻³ from the root, the threshold is η ≈ 5·10⁻³, and a tolerance of 10⁻² sits just above it and does land 22 per cent short.

Both of those are the same rule, and the rule needs no derivative and no norm: the usable tolerance is a small multiple of the distance to the root, and the distance to the root is what the ratio of consecutive residuals estimates. That is the quantity the next essay’s rule reads, and this section is the arithmetic that says what the multiple should be.

How much it costs to ignore #

One step is not a solve. The forcing term is chosen once and applies to every step, so the interesting quantity is the total inner work for a complete run to a stated outer tolerance.

The curve is a U and both of its arms are worth naming.

The left arm is oversolving. At η = 10⁻¹⁴ the run takes 9 Newton steps and 9,358 inner iterations. At η = 10⁻⁶ it takes the same 9 Newton steps and 4,382. The outer iteration is doing exactly the same thing — the same number of steps, landing in the same places to within the plateau — and one of the two runs is paying twice as much for it.

The right arm is starving the outer loop. At η = 0.5 each step is nearly free, but the steps stop being Newton steps: the quadratic convergence goes, the run takes 30 outer steps instead of 9, and the total climbs back to 1,178.

The bottom is at η ≈ 0.1, at 980 iterations, which is a factor of 9.5 below the fully solved run. Nine and a half times the work, for a final answer whose residual is below the same tolerance.

The one thing the tight run does buy #

An honest accounting has to say what the extra work is not wasted on, and there is one thing.

The run at η = 10⁻¹⁴ ends with a forward error of 2.79·10⁻¹⁰. The run at η = 0.1 ends with 2.43·10⁻⁸ — eighty-five times worse. Both satisfy the stopping test, which asks for a relative residual below 10⁻¹⁰, and neither is more correct than the other by that test.

The reason for the difference is not that the loose run was less careful. It is that a quadratically converging iteration overshoots its stopping test: the tight run’s last step lands at a residual of about 10⁻¹⁶, five orders of magnitude below what was asked for, because the step before it was at 10⁻⁸ and the next one squares that. All of that accuracy is free in the sense that it was not asked for, and it is expensive in the sense that the last inner solve is the most expensive one in the run.

So the tight constant is not buying nothing. It is buying digits nobody requested, at the highest price the run has to offer, on every step rather than on the last one.

That observation is what the essay on a rule that reads its own residual is about, and the shape of the answer is already visible here: what is wanted is a loose tolerance early and a tight one at the end, which no constant can be.

Where the plateau’s left edge is #

The tolerance at which the inner solve stops mattering is not machine precision and it is not a fixed number either. It sits at about the square root of the plateau — which is to say at about the distance to the root — because that is where the linear solve’s own error stops being smaller than the linearisation’s.

That has a consequence worth stating plainly: the correct inner tolerance is proportional to how far from the root the iteration currently is, and the iteration knows that quantity to within a constant, because it is roughly the ratio of consecutive residuals.

At the first step of the run drawn here, the iterate is 2.95 away from the root and the plateau is at 1.80. Any tolerance below about 0.1 is spent on nothing. At the last step the iterate is 2.5·10⁻³ away and the plateau is at 1.2·10⁻⁵; there a tolerance of 10⁻² lands at 1.4669·10⁻⁵ against the plateau’s 1.1999·10⁻⁵, a genuine 22 per cent shortfall, and one more decade closes it entirely.

The demand a step can use rises by two decades for every decade the outer iteration gains, and a constant is by construction wrong at one end of that or the other.

The plateau is a claim about where the inner solve stops buying anything, so it is worth watching across the whole outer iteration rather than at one step of it.

Both quantities are falling, and they are falling at different rates — which is the whole of the argument, and needs a third and fourth reading to establish.

The plateau converges on twice d², and it gets there from below. plateau ÷ d² runs 0.21, 0.32, 0.48, 0.70, 1.17, 1.81 and 1.93 — so far from the root the plateau is a fraction of d² and near the root it settles at about 1.9·d². The quantity the inner solve cannot help with is exactly the quantity the outer iteration was going to gain, and the identification is only clean in the limit the essay cares about.

And the premium for over-solving falls as the iteration converges. Solving to 10⁻¹⁴ instead of 0.3 costs 25.5× the inner iterations at the first outer step and 10.4× at the last — the ratio runs 25.5, 21.2, 16.0, 12.9, 12.1, 10.3, 10.4. So the proportional waste is worst early, when the plateau is largest and there is genuinely nothing to buy.

In absolute terms it is worst late. At the seventh iterate the loose tolerance costs 109 inner iterations and the tight one 1,129 — 1,020 extra iterations, more than at any earlier step, spent resolving a correction below a plateau of 1.2·10⁻⁵. And the loose column has stopped growing: 109 at both the sixth and the seventh iterate, to the unit. The inner work under a sensible forcing term converges; under a fixed tight tolerance it does not.

What the sweep costs to make #

It is worth saying what the U above is, because a curve of twelve points where each point is a whole solve is a different kind of object from a curve where each point is an evaluation.

Every point on it is a complete inexact Newton run on the same 200×200 problem to the same outer tolerance: nine to thirty outer steps, each with its own conjugate gradient solve, and the vertical coordinate is the sum of every inner iteration in the run. Nothing is estimated and no step count is extrapolated. The adaptive point drawn beside the curve is a thirteenth complete run under a different rule, and it is a point rather than a curve because it is not a constant and there is no axis it belongs on.

The reason to say so is that the two arms of a U are usually a fit through a model. These are measurements of runs, and the asymmetry between the arms is a measurement too: the left arm rises smoothly, because oversolving costs a predictable number of extra iterations per decade, and the right arm rises in jumps, because a Newton step either survives being solved that loosely or the run needs another whole step.

What this is not #

Three readings to rule out, because each of them is available from the figure and each is wrong.

Not that the inner solve does not matter. It matters enormously; it is where all the work is. What does not matter is the part of its accuracy that lies below the linearisation error, and that part is most of the accuracy a default tolerance asks for.

Not that this is about conjugate gradients. The plateau is a property of the outer method. Any inner solver put in its place meets the same floor; what changes is how much a decade of tolerance costs, and that only moves the vertical distance between the points on the plateau, not the plateau.

Not that the effect is small on well-conditioned problems. It is invisible on well-conditioned problems, which is different: there the inner solve costs a handful of iterations at any tolerance, so the waste is real and cheap. The effect scales with how expensive the inner solve is, which is to say it is largest exactly where it is worth having.

Two numbers a solver could report and does not #

The measurement suggests two things an inexact Newton implementation could print, neither of which is expensive and neither of which is usual.

The linearisation error of the step just taken, which is ‖F(x + s)‖ compared against what the linear model predicted. It costs nothing extra — the residual at the new point is evaluated anyway on the next step — and it is exactly the floor this essay is about. A solver that printed it would be telling its user how much inner accuracy the next step can use.

And the share of the inner solve that was spent below that floor, which is the difference between the tolerance asked for and the tolerance the floor justified. On the runs here that share is most of the work, and it is invisible in any log a solver currently writes.

Neither is a new algorithm and neither changes an answer. They are both the collection’s standing habit applied to somebody else’s code: a quantity that decides something should be printed beside the thing it decided, so that a reader can see whether the decision was a good one.

The refusal #

The claim that a Newton step landing short of the root was solved too loosely is a claim about which of two quantities is the binding one, and it is fed here the case where the answer is the other one.

At the iterate 3.719·10⁻² from the root, the seven tolerances from 10⁻³ down to 10⁻¹⁴ land between 2.4966·10⁻³ and 2.4967·10⁻³. The assertion that the shortfall belongs to the inner solve is fed those numbers and required to fail, which it does. Then the same assertion is fed the first Newton step from a cold start — where the tolerance genuinely does move the answer, because the linearisation error there is the size of the iterate — and it passes, which is what makes the first result a measurement rather than a tautology.

What it means for the rest of the field #

The plateau is the first of the four assets this field is about, and it is the one with no downside at all. A tolerance is not an object that has to be built, so choosing it badly costs nothing but work; there is no risk of a wrong answer, no cliff, and no case where being too loose destroys anything that cannot be recovered on the next step.

That is exactly why it is first. The other three — the factorisation, the preconditioner, the pivot order — are objects with a construction cost, and each of them adds a failure mode that a tolerance does not have.