A target the residual can promise

A floor with a cliff at one swept the constant in the floor that keeps inexact Newton from solving its last step more accurately than the outer test reads. Newton’s method solves each linear step only to a relative residual η, the adaptive rule chooses η from the ratio of the last two residuals, and the floor says never ask for less than $c \cdot \mathrm{tol}\cdot\lVert b\rVert/\lVert F\rVert$. With c = ½ the floor gave up forward accuracy by a factor that ran from nothing to 48,000 across five problems and four tolerances, which made it no number a caller could plan on.

The reason was not the floor. It was the tolerance. The floor gives up exactly the accuracy the residual tolerance said nobody wanted, and a residual tolerance says nothing directly about the forward error. The essay proposed starting from the other end: “If the caller wants the forward error below some δ, the last step’s relative residual should be about δ divided by the condition number, and the condition number can be estimated from quantities the Krylov solves already produce. … The measurement is what it costs against the unfloored run on the five problems here — and whether a Lanczos estimate of the condition number, which conjugate gradients carries for free, is good enough to set it.”

It is good enough, and the comparison with the unfloored run comes out the other way from what the question assumed.

Five ways to stop #

The problems are the forcing essays’ own: $F(x) = Ax + \lambda x^3 - b$ on 200 unknowns, $A$ symmetric positive definite, the root known. The standing problem has κ(A) = 10⁵ and λ = 3; the others move one knob — κ(A) of 10³ or 10⁷, λ of 0.3 or 30. Every run uses the adaptive forcing rule with the floor at ½, solves each step by conjugate gradients, and is stopped five ways for a target δ on the relative forward error $\lVert x - x^*\rVert/\lVert x^*\rVert$:

δ as the residual tolerance — stop when $\lVert F\rVert/\lVert b\rVert < \delta$, which is what a caller who wants δ usually types. δ over the known condition number — the tolerance $\delta/\kappa(A)$, available to whoever built $A$. δ over the Ritz estimate — the tolerance $\delta/\hat\kappa$, with $\hat\kappa$ the ratio of the largest to the smallest Ritz value every inner solve so far has produced. The effective rule — the tolerance $\delta\,\hat\lambda_{\min}\lVert x\rVert/\lVert b\rVert$, which is the bound $\lVert x - x^*\rVert \le \lVert J^{-1}\rVert\,\lVert F\rVert$ read with the smallest Ritz value standing for $1/\lVert J^{-1}\rVert$ and the current iterate standing for the root. The oracle — no floor, and stop the first time the true forward error is below δ: the cheapest run anybody could stop honestly, available only because the root is known here.

The Ritz values cost nothing. Conjugate gradients is the Lanczos process in disguise: its step lengths α and β assemble, step by step, a tridiagonal matrix whose eigenvalues approximate the Jacobian’s, the largest and smallest first. Every inner solve builds one, and its extreme eigenvalues come from a bisection on a matrix a few dozen rows long.

The tolerance that misses #

The figure is every cell where a residual can certify the target — nineteen of twenty, the twentieth is the last section’s — with the forward error divided by δ, so that the dashed line is the promise.

Passing δ as the residual tolerance misses it on every cell, by 7.3 times at best and 35,000 at worst. On the standing problem at δ = 10⁻⁸ the run stops with a forward error 190 times its target. Nothing malfunctioned. A small residual is not a small error made the general point: a residual and an error differ by a condition number, and here that condition number is between 289 and two million. The floor is innocent of most of it — removing the floor gave back accuracy only because the unfloored run over-solved its last step past the tolerance it was given.

The three rules that divide by a condition number meet the target on all nineteen cells. Divided by κ(A) the forward error lands between 0.0011 and 0.017 of δ — met with room to spare. Divided by the Ritz estimate, between 0.0069 and 0.058. The effective rule lands between 0.045 and 0.18: within a fifth of the target on every cell and closer to it than either, because its bound is tighter.

The estimate arrives early #

A rule that depends on an estimate is only as good as the estimate at the moment it stops, so the estimate has to be there by then. On every problem it starts far too small — after the first step, a factor between three hundred and two million below — because the first inner solves run at η = 0.9 and take a handful of iterations, too few for the Lanczos tridiagonal to have found the smallest eigenvalue. By the sixth step every estimate has jumped to within a factor of one and a half, and by the end it is within seven per cent of $\kappa(J^*)$ on four problems and eleven per cent high on the fifth, whose earlier Jacobians were stiffer than the last.

The early underestimate never mattered here, because no forward rule had a small enough residual to stop before its seventh step. It is the condition for the rule to be safe, and a code that used it would refuse to stop on an estimate fewer than a few inner solves old. An eigenvalue that arrives twice showed what else a Lanczos process in floating point does to its Ritz values — copies of converged ones — and none of that touches the ratio of the extremes, which is all this needs.

The badge in the corner is the second finding hidden in this figure. The condition number that matters is the Jacobian’s at the root, $A + 3\lambda\,\mathrm{diag}(x^{*2})$, and the cubic term lifts its smallest eigenvalue: κ(J*) is 1.6 to 19 times below κ(A). A caller who uses the condition number of the linear part — the number they actually know — divides by too much, and pays for it.

What meeting the target costs #

On the standing problem the run that passes δ as its residual tolerance takes 344, 709, 977 and 1,190 inner iterations at targets of 10⁻⁴ down to 10⁻¹⁰, and misses all four. The effective rule takes 947, 1,106, 1,334 and 1,522 and meets all four. Meeting a forward target costs 1.3 to 2.8 times what claiming one costs, and the gap is largest at the loose targets, where the condition number is a larger share of the decades the run has to cover. That is the honest price of six digits on a problem whose Jacobian has a condition number of 23,000.

Between the three rules that meet the target the differences are small and in a consistent order. On every certifiable cell the effective rule is cheapest, then the Ritz estimate, then κ(A); on the standing problem at 10⁻⁸ they take 1,334, 1,390 and 1,443. Turn the dial: on the hardest problem, κ(A) = 10⁷, dividing by κ(A) instead of the Ritz estimate costs 8,739 against 8,416 at 10⁻⁸; on the strongly nonlinear one, where κ(A) overstates κ(J*) by 19, 866 against 819. The ordering follows the conjugate-gradient arithmetic a guess worth two per cent found limiting every saving in this setting: a roughly constant number of iterations per decade of residual, so an over-tight tolerance costs only the decades it over-asks for, on the last step alone.

Why the effective bound is tighter #

The three rules that meet the target differ only in how pessimistic they are about the step from residual to error. The Ritz rule divides by $\kappa(J)$; the effective rule divides by $\lVert b\rVert\,\lVert J^{-1}\rVert/\lVert x\rVert$, the effective condition number, which replaces the largest singular value of $J$ by the ratio $\lVert b\rVert/\lVert x\rVert$ actually realised by this right-hand side. On the standing problem that is 5,458 against $\kappa(J^*) = 22{,}820$, a factor of 4.2; on the strong one 1,270 against 5,300. The same factor separates their landing points — the Ritz rule at about 0.02 of the target and the effective rule at about 0.06 — because each is a bound and each is loose by the remainder.

The remainder is the part of the bound no cheap estimate removes: $\lVert x - x^*\rVert \le \lVert J^{-1}\rVert\,\lVert F\rVert$ is attained only when the residual points along the Jacobian’s weakest direction, and a residual left by conjugate gradients is spread over many. The condition number is an amplifier measured κ as the largest ratio of output movement to input movement; any particular movement is smaller, and here the last residual’s is smaller by a factor of five to twenty. A rule that knew the residual’s direction could close that gap, and nothing here knows it. Within a fifth of the target is what a bound read with free estimates delivers.

A tolerance that reads its own residual built the adaptive forcing rule on the same kind of reasoning one level down — choosing each step’s η from what the residual history says about the convergence, rather than from a constant. The rules here finish that thought at the outer level: the stopping tolerance, too, should be read from the problem rather than typed in.

Cheaper than knowing the answer #

The essay that proposed this asked what it would cost “against the unfloored run”. The fair version of that run is the oracle: the adaptive rule with no floor, stopped at the first outer step whose true error meets δ. It cannot over-stop, because it reads the error itself. It should be the cheapest possible.

That earlier figure is why the oracle looks attractive. With a residual tolerance and no floor, the run’s forward error is anywhere from the floored run’s to 48,000 times better, and a caller who cares about accuracy is tempted to drop the floor and take whatever comes. But “whatever comes” is the problem: the premium is accuracy nobody chose, paid for with iterations nobody budgeted.

It is not the cheapest. The effective rule, floor and all, is cheaper on 16 of 19 cells, by up to a third — 0.67 of the oracle’s iterations on the easy problem at 10⁻¹⁰ — and dearer on three, by at most ten per cent. The oracle knows when to stop the outer loop; it does not know how hard to solve the last step, and with no floor the adaptive rule solves it to whatever the ratio of residuals suggests, which near the root is far tighter than anything the target needs. On the standing problem it reaches δ = 10⁻⁸ with an error of 5.7·10⁻¹³, seventeen thousand times better than asked, and pays 1,738 iterations for it against the effective rule’s 1,334. One line that buys a quarter of the run found that floor saving 9 to 27 per cent; set from the target instead of from a residual tolerance, it keeps the saving and loses nothing the caller asked for.

That is the reversal. The floor was the thing that gave up accuracy without saying how much, and the cure for that was not to remove the floor but to feed it the right tolerance.

Where a residual cannot certify #

One cell of twenty is missing from the counts above. On the hardest problem, $\kappa(J^*) = 2.0\cdot 10^6$, a target of 10⁻¹⁰ asks for a relative residual of 5·10⁻¹⁷ — below the unit roundoff, below what the residual of a double-precision computation can be. Every residual rule runs to the outer limit of 80 steps and 30,000 inner iterations without stopping. The oracle, reading the error directly, stops after ten steps with an error of 4.2·10⁻¹¹: the target was reachable. It was not certifiable. A residual cannot be measured below the rounding in its own evaluation, and so it cannot vouch for an error smaller than the condition number times that rounding.

The estimate says so before the run starts to stall. $\hat\kappa\, u$ is $2.2\cdot 10^{-10}$ on that problem, above the target; on every other cell it is below. A rule built on the estimate can therefore report, at the fifth step, that the target is below what any residual test can certify, and stop with the best certifiable statement — here, about two parts in $10^{10}$ — instead of spending three and a half times the work of the oracle on a test that cannot be passed. The accuracy that is thrown away located the floor under a Newton step’s own accuracy at the square of where it started; this is the floor under what the residual can promise, and it is set by the conditioning rather than by the step.

What the interface should take #

Put together, the measurements say what an inexact-Newton routine should ask its caller for and what it should hand back. It should take the forward accuracy wanted, because that is the quantity the caller can state and the residual tolerance is a translation of it that the caller is in no position to make: on the easy problem δ as a residual tolerance misses by seven to sixteen times, on the hard one by four thousand to thirty-five thousand, and the caller cannot know which kind of problem they have without the condition number the routine is computing anyway.

It should set its stopping tolerance and its floor from that target and from the Ritz values, and not stop on an estimate younger than a few inner solves. And it should report three numbers at the end: the target, the condition-number estimate it divided by, and the tolerance that produced — so that a caller whose target fell below κ̂ times the unit roundoff is told, at the sixth step rather than the eightieth, that a residual cannot vouch for what they asked and what it can vouch for instead. Every one of those numbers is a by-product of the run as it stands; the change is in what is read off it and when.

The miss of the residual tolerance is itself predictable from the same numbers. On each problem it is roughly the effective condition number divided by the factor of five to twenty by which the bound overstates any particular residual: about 300 on the standing problem, where the effective condition number is 5,458, and about 10 on the easy one, where it is 93. A caller who already passes residual tolerances and wants to keep doing so can divide by the reported estimate and recover a forward statement — the same arithmetic, done after the fact instead of before.

What these runs do not show #

One family of problems, a cubic perturbation of a symmetric positive definite matrix, with conjugate gradients as the inner solver; five problems and four targets. The Ritz values are a property of conjugate gradients and of symmetric Jacobians; a nonsymmetric Jacobian solved by GMRES produces Hessenberg Ritz values whose smallest is a poorer guide to $\lVert J^{-1}\rVert$, and the effective rule’s bound would need a different estimate. The effective rule reads the current iterate for the root, which is fine here because by the time it can stop the iterate agrees with the root to the target; on a problem whose iterates wander far from the root before converging, the early tolerances would be wrong in both directions, harmlessly so long as the residual is too large to stop on.

Still open: a nonsymmetric Jacobian, and Eisenstat and Walker’s first rule #

GMRES and the harmonic Ritz values. With a nonsymmetric Jacobian the inner solver is GMRES, and its Arnoldi process produces Hessenberg Ritz values and harmonic Ritz values; the smallest harmonic Ritz value bounds the smallest singular value from above, which is the direction that makes the effective rule loose. The prediction with a sign is that on a mildly nonnormal Jacobian the effective rule built on harmonic Ritz values still meets the target, at a few per cent more work, and that on a strongly nonnormal one it misses — because the smallest singular value is not approximated by any Ritz value until late.

The first forcing rule. Eisenstat and Walker’s other choice of η reads the difference between the new residual and the linear model’s prediction of it. The question from the earlier essay stands, now with a target to set its floor from: whether that rule over-solves its last step the way the ratio rule does, and so whether the floor set from δ saves as much there.