Stopping criterion — where it appears
Named by 40 essays across 10 fields — each of them below, with the objects they name alongside it.
A parameter that counts steps
The regularisation field's knob is a positive real number chosen by one of three rules. The iterative field's is an integer nobody called a knob — where to stop. On the same problem the best step is 20 and the best λ is 0.025, and they reach 0.1426 and 0.1406.
A tolerance that reads its own residual
The cheapest constant forcing term costs 980 inner iterations and arrives with a hundred times the forward error of the dearest, which costs 9,358. A rule that sets each step's tolerance from the ratio of the last two residuals costs 1,009 and arrives with neither problem — and it is not a constant, so it does not appear on the curve the constants are compared on.
The part of a solver that may be rounded
A preconditioner computed and applied with a three-bit significand still returns thirteen correct digits — it costs seventeen extra iterations and nothing else. Round the working arithmetic instead and the step count barely moves while the answer loses exactly the digits the format dropped.
The step that stops mattering
Regularise the problem the iteration has built rather than the problem it was given, and the error curve stops turning. The unregularised run ends 1,127 times above its own best; the same run with a penalty inside it ends 1.000000000003 times above.
A parameter chosen on a smaller problem
Inside a hybrid method the regularisation parameter is chosen on a 25×24 problem rather than a 64×64 one. The rule that reads a residual transfers exactly; the rule that reads a trace is biased by exactly two grid steps at twenty-four steps and one at forty, at every noise level from 10% to 0.1%.
What a rebuild is worth
One sequence, one drift, one preconditioner — and six different right answers, because the cheapest rebuild period depends on what a rebuild cost to build and on nothing else. The optimum walks from every member to every twelfth as the setup gets dearer, and the free rule that reads the iteration count beats it in the middle of that range and loses at both ends.
An expiry date the noise does not move
The polynomial description of conjugate gradients leaves the level of rounding at step 17 or 18 on this operator, at every noise level from 10% to 0.1%. The step worth stopping at moves from 3 to 44 across the same range. They coincide at about 1% noise, which is where the coincidence was first read, and it is a fact about the noise rather than about the method.
A preconditioner that arrives past the answer
On a system that is solved to convergence a preconditioner changes how fast the answer arrives and not what it is. On a problem regularised by stopping it changes where every step lands. Conjugate gradients preconditioned by AᵀA + αI reaches its best answer in one step at α = 10⁻³, and at α = 10⁻⁶ its best answer is its first step, with an error of 1.35 against the unpreconditioned run's 0.1426 — while the count of eigenvalues it has clustered at one rises from 22 to 32.
The accuracy worth paying for
Used as a preconditioner, a hierarchical representation gets better at every accuracy — the iteration count falls monotonically all the way to the tightest tolerance. The total work does not. Its minimum sits at a rank-one preconditioner on an easy problem and six decades further along on a hard one.
A step that is not a unit of work
Landweber's iteration reaches conjugate gradients' best answer on the same deconvolution — 0.1414 against 0.1426 — at step 1,778 instead of step 20, and at 0.1% noise at step 56,234 instead of 44. Each step costs the same two products. And within 10% of its best it runs from step 7 to step 6,310, where conjugate gradients runs from 4 to 26: the slow method is the one that forgives a late stop.
The active set before the digits
An interior-point method takes fifteen iterations on a quadratic programme with forty constraints, and its iterate has eight correct digits at the eleventh. Take the constraints its diagonal calls active at the first iterate, solve the equality problem they define once, and check the answer against the conditions for optimality. It passes, to thirteen digits. The step's matrix had a condition number of 43 at that iterate, and 7·10¹⁵ at the last.
A stopping test is a race
One matrix, one right-hand side, one tolerance, thirteen partition counts — and eleven different iteration counts between 674 and 690. Every run converged, every answer is right to the accuracy asked for, and what differs is the bill.
A stopping rule that follows the run it is given
A preconditioner that reaches the answer four times sooner leaves four steps within 10% of its best instead of sixteen, and a rule that stops by the residual ought to miss so narrow a window more often. Over forty draws of the noise it misses it less: the discrepancy principle stops at 1.030 times the preconditioned run's best against 1.073 times the plain run's. And past the edge it stops within a factor of 1.7 of a run whose own best is 5.5 times Tikhonov's — faithful to a run that has already failed.
A warm start is degree zero
The previous answer used as the next member's starting point costs 160 inner steps over twenty members. The line through the last two answers costs 12 — a factor of thirteen, for three vector operations and no extra storage. The parabola through the last three costs 26, which is worse than the line and better than the point.
Bracketing an error nobody can measure
The error of a low-rank Gramian factor is the one quantity a caller cannot compute, because computing it needs the Gramian the factor exists to avoid forming. Two numbers that can be computed sit either side of it — a rational factor known before the run, and a residual known after — and they stay a factor of four apart across a fourfold change of size.
The tolerance that buys no agreement
Ask for four more orders of accuracy and you get them — the answers improve by a factor of 1.5 million. The ratio between the best and the worst run is 1.34, 1.48, 1.71 and 1.17 across the same sweep. The band falls and it does not close.
Keeping the vectors, and losing the bound
Thick restarting keeps the Ritz vectors instead of filtering the starting vector — the same eigenvalues for a third of the products with A. Its residual bound reaches 9.4·10⁻⁴¹ while the residual it bounds sits at 5.7·10⁻⁵, and the eigenvalues are correct to 4.3·10⁻¹⁴ the whole time, so nothing reports it.
Two repairs for one symptom
Rescale a quadratic programme's constraint rows over six decades and the crossover that certified its answer at iterate 1.5 first certifies at 69.8, with two of six programmes never certifying at all. Normalising the rows removes the spread completely — the same numbers at 10¹, 10² and 10³ either way. Starting the method at the magnitudes the rows imply repairs the iteration count completely and the identification only halfway. They are two repairs and they fix different halves.
The parameter neither knob is
A preconditioned run has a cutoff and a step count, and neither is the regularisation parameter. The parameter is the effective dimension of the iterate: every cutoff that works puts its own best at 23.7 to 24.3 of it, where the unpreconditioned run's best sits at 23.2, and what the cutoff buys is the rate — 1.27 of it a step with no preconditioner and 3.53 with one. The edge is where a single stride is longer than the distance left.
A rule that reads only its own probes
A trace estimator is a mean of independent samples, so its own standard error is estimable from the samples and a stopping rule needs nothing the estimator does not already have. Over forty draws it is calibrated in the middle and not at the edge: at a target relative standard error of 1% the median error reached is 5.3·10⁻³ and the worst of forty is 2.9·10⁻² — three times the target. And the cost of the target is the estimator's own square root: tightening it from 3% to 1% takes the median probe count from 75 to 696.
One line that buys a quarter of the run
The adaptive forcing rule has a floor on it that no published statement of the rule carries: do not solve a step to an accuracy the outer loop will not use. Removing it costs 9 to 27 per cent of the whole inner run. Keeping it costs between 23 and 2,600 times the forward error — accuracy the residual test never asked for and both runs satisfy the test either way. The line is a trade between a residual and an error, and which of the two the caller meant decides whether it is a saving.
A test with no tolerance in it
An interior-point method's own stopping test is a tolerance on μ, and at the tightest it can be set to it stops after 15 iterations with 1.6·10⁻¹². A crossover from the iterate at 1.5 returns a point whose error is 1.8·10⁻¹⁴ — ten times sooner and a hundred times better, from an iterate carrying one correct digit. One attempt costs an eighth of a step, and the guess's own margin says which iterate to spend it on.
The test that is a deadline
The quantity that separates a boundary from slow convergence fires on every run that has nothing to reach, at sweep 21 of four thousand, and on no ordinary fit. It also fires on every badly conditioned fit that does converge — at sweep 758. No threshold between 0.10 and 0.40 separates those two, and the sweep it fires at separates them by a factor of thirty-six.
The rank a certificate charges
A randomised range finder can choose its own rank: grow the basis a column at a time and stop when ten fresh probes all come back short. With the published safety factor it never stopped early in any draw measured, and on a matrix whose singular values fall by 0.8 a step it stopped at rank 30 for a tolerance the best rank-11 approximation already meets. The nineteen extra columns are three separate prices — four for building the basis from random vectors, five because a probe reads more than the spectral norm, and ten for the constant — and the spectrum decides which of them dominates.
A straight path has nothing for a parabola to fit
The line through the last two answers beat the parabola through the last three on a drifting sequence, and the reason offered was that the parabola amplifies the stored answers' error. Tightening the solve tolerance from 10⁻⁶ to 10⁻¹⁴ should have reversed that, and it does not: the line needs 7 to 18 inner steps over twenty members at every tolerance and the parabola 14 to 23. The sequence's roots move along a straight line, so the line is exact and there is nothing else to fit. Bend the path by a part in ten thousand and the parabola wins below 10⁻⁹, by 105 steps to 75 at 10⁻¹⁴.
The degree the history chooses
A sequence of solves can start each member from the line through its last two answers or the parabola through its last three, and which is better depends on how much its path bends — which a code does not know. Over thirty runs of bend and tolerance, always taking the line costs 456 inner steps more than the better choice; always taking the parabola costs 33. A free rule reading the stored answers closes that to 11. A rule that evaluates the residual at both starts picks the better one on 29 runs of 30, and pays 135 steps for the evaluations.
The rank a sweep can vouch for
To decide a tensor's rank, fit it at one rank after another and stop where something changes. Three things can be read off each rank's fits — the error, how nearly parallel the terms are, and whether fits from different starting points agree — and over six planted rank-three tensors at four noise levels they decide it 24, 12 and 15 times out of 24; the ratio of consecutive errors, which needs nothing, decides it 24 times. The error is right every time and has to be told the noise level. The collinearity is a coin toss. Agreement among starts is never wrong and, under noise, cannot decide on nine of the twenty-four — and the rank past the answer, where every decision is made, costs ten times the answer.
A spectral radius that grows first
ρ(A) below one guarantees that the powers of A go to zero and says nothing about what they do on the way. Here they rise by a factor of twenty thousand before turning over, and the peak is bracketed above and below by a constant computed from the resolvent norms outside the unit circle — two routes to one number, one through the plane and one through the powers.
A fit that has an answer and cannot stop
Fit a noisy rank-three tensor with four terms and the prediction was that the spare term would find real structure in the noise and stop pairing off with the others. It does not: the largest cosine between two fitted terms has a median of 0.977 at 1% noise against 0.975 without noise. What changes is the solver. Without noise the four-term fit stops in fifty sweeps; with noise it never stops: its error keeps moving by a part in a million a sweep for six thousand sweeps, while on most tensors its terms stand still. The extra term takes exactly its share of the noise, and the error is settled by sweep 150.
The miss a normal table already priced
A trace estimator that stops when its own standard error reaches a target misses the target on about a third of draws, and the essay that measured it read the loose targets as the worst calibrated. Over 400 draws the loose target is the better covered — 76% at 10% against 64% at 3% — because the warm-up stops most of its runs with probes to spare. Where the criterion decides, the misses are a normal distribution's: a margin of c on the standard error buys what a normal table says, 94.8% at 1.96, and costs c² in probes, 3.86 times.
A floor with a cliff at one
Inexact Newton's adaptive forcing rule is used with a floor: never ask the inner solve for less than c times the outer tolerance, relative to the current residual, with c a half. Swept from a hundredth to ten, the constant trades with no knee at all — the forward error rises in proportion to c, the inner work falls by a few per cent a decade — and then, just past one, the run stops converging: at c = 3 it hits the outer limit on four problems of five, having asked every step for less than the stopping test needs. And the accuracy the floor gives up at c = ½ is no planning number: across five problems and four tolerances it runs from nothing to a factor of 48,000.
A still error is not a settled one
A CP fit with one term too many on a noisy tensor never meets the usual stopping test, and its error has settled by sweep 150. A test that asks only whether the error has moved by less than δ of itself over ten sweeps stops those fits by sweep 25, and over twenty-four noisy tensors it names the same rank as the usual test every time, at δ = 10⁻² for 30,250 sweeps against 311,458. But δ = 10⁻² is the tolerance a rank decision states, and on a slow fit that converges it stops five starts of six on a plateau ten orders above the answer and names the wrong rank for four tensors of six. A tenth of the decision's tolerance keeps every decision on both families.
A fit wins where the steps were few
The line through the last two answers of a sequence of solves amplifies their stored error by √5, and the parabola through the last three by √19. A least-squares line through five amplifies it by 1.05 and a parabola through six by 1.79, and on a straight path both beat their interpolants at every tolerance: 12 inner steps against 17 at 10⁻¹⁴. On a bent path they lose, by exactly the ratio of their truncation constants, and they lose in the runs that cost a hundred steps rather than ten. Over thirty runs no fitted start beats the parabola through three, and the best of eight starts chosen per run saves 58 steps out of 1,212.
A spread measured on probes it does not average
A trace estimator that stops on its own standard error misses its target a few points more often than a normal table says, because the runs that stop earliest are the ones that underestimated their noise. Spend a pilot of probes only on the spread, fix the number of probes to average in advance, and the selection is gone: with Student's margin the two-stage rule covers 64.8 to 73.3 per cent at one standard error where the table says 68.3. With the normal's margin and a pilot of four it covers 58.5. At one standard error it recovers one to five points for a fifth to two fifths more probes; at 1.96 there was nothing to recover, and the guarantee costs a tenth to double.
The reading that never moves
Across thirty runs — five grids from 36 to 196 unknowns, six working precisions from 53 significand bits down to 8 — the residual conjugate gradients stops on stays between 1.10·10⁻¹³ and 9.95·10⁻¹³. Over the same thirty runs the error of the answer spans a factor of 2.39·10¹¹, and the step count more than doubles. The one number the run publishes is the only one that responds to neither axis.
The residual the method reports
Conjugate gradients prints a relative residual of 6.9·10⁻²¹. The unit roundoff is 1.1·10⁻¹⁶, so that is not a small residual and not a large one — it is not a residual. The vector the method is holding at that step has ‖b − Ax‖/‖b‖ = 5.1·10⁻¹⁰, and nothing in the run says so.
The number that is re-derived
GMRES prints a residual it never computes from its answer either. On the matrix that sends a conjugate gradient recurrence 7.3·10¹⁰ wrong, and on two others chosen to be worse, its number is never more than a factor of 2.86 out — while the basis it is computed from has lost orthogonality entirely. The disease is not iterative methods, and it is not floating point.
A run that is over at step five
A conjugate gradient whose every iterate is cut to a rank budget reaches the floor that budget allows at step 5, 36, 42 or 59, and then does nothing for the rest of the run. Four times the iterations move the floor by a factor of 1.8, and past the answer's own rank they move it the wrong way.
The same budget, spent five ways
A restarted method has one budget — products with A — and two ways to spend it, in many short cycles or a few long ones. At about a hundred and forty products the answer is the same to a factor of seven whichever split is chosen, and the residual bound the method reports spans ten orders of magnitude across the same five runs.
A walk needs a length
The gap between the two residuals grows as the square root of something, and a square root needs a length. Two quantities are candidates — how far the iterates travelled and how many steps were taken — and only a second sweep separates them. Across a fourfold change in size the iteration count goes from 39 to 96 and the gap goes from 5.04·10⁻¹⁵ to 5.33·10⁻¹⁵.
Named alongside it
The objects these essays reach for when they reach for this one.
Conjugate gradientsFlop countCondition numberKrylov subspaceNewton iterationResidualExact ground truthForward errorIterative regularisationPreconditioningSemi-convergenceTikhonov regularisation