Forward error — where it appears
Named by 50 essays across 16 fields — each of them below, with the objects they name alongside it.
The exact answer to a nearby problem
A good algorithm does not give an approximate answer to your problem. It gives the exact answer to a problem very close to yours — and once that is the definition, a wrong result has two possible authors and they can be measured apart.
Two ways to remove a constraint
A constrained system can be reduced by eliminating the multipliers or by eliminating the constrained directions. Both give the same answer in exact arithmetic and inherit different condition numbers — one of them squares the constraint's, and the other does not contain it at all.
A small residual is not a small error
Substituting the answer back and finding that it fits is the most natural check there is, and it verifies the wrong thing. A residual of 10⁻¹⁷ is entirely compatible with an answer whose second digit is wrong.
A backward-stable answer to a problem nobody asked
One quadratic eigenvalue problem, in nine systems of units, with a change of variable that is exact in both directions. The residual the solver prints stays at the rounding level at every stop. The answer loses eleven orders of magnitude, and the two facts are consistent.
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.
Buying the accuracy back
Factorise in single precision, then correct the answer using residuals computed in double, and the result is what a full double-precision solve would have given. Compute those residuals in single instead and the identical algorithm, at identical cost, recovers nothing.
When the matrix is wrong too
Every least-squares problem here has assumed A is exact and b is not, and moved b onto the column space of A. Where both were measured, the smallest correction that makes the system consistent moves the matrix as well — and on the problems where that answer is more accurate, it has the larger residual, by construction rather than by luck.
A correction cheaper than the problem
Sherman and Morrison's formula updates a solved system for a rank-one change to the matrix, at 4n² operations instead of (2/3)n³. It is exact algebra. On a problem whose updated matrix is the identity — condition number one, the easiest system there is — it returns a forward error of 2.5·10⁻⁴ where a direct solve returns 10⁻¹⁶.
A condition number sent to infinity
An interior-point method manufactures an ill-conditioned matrix on every iteration, deliberately, because the separating of a diagonal is how it discovers which constraints are active. Written one way the answer keeps fifteen digits at a condition number of 3·10¹⁵. Written the other way — the way almost every code writes it — it has none left.
The units the matrix is measured in
One linear system, written twice. The rows of the second are the rows of the first in different units, the solution is identical to the last bit, and the condition number has moved by eight orders of magnitude. One of those two numbers is a fact about the problem and the other is a fact about the notation.
A condition number scaling cannot move
Skeel's componentwise condition number is invariant under any row scaling — exactly, before any norm is taken, because two diagonal factors cancel entry by entry. It is never larger than the normwise one and can be arbitrarily smaller, and the ratio between them is a diagnostic for which kind of ill-conditioning a matrix has.
The problem the solver was actually given
A linearisation is exact — it has the polynomial's eigenvalues, with their multiplicities, and the whole loss is arithmetic. A nonlinear eigenvalue problem does not offer that. Every algorithm replaces the function first, and the term that replacement contributes is committed before any number is rounded and appears in no residual.
The inverse that is never formed
x = A⁻¹b is how the solution of a linear system is written and it is not how it is computed. The usual reason given is cost — three times the arithmetic. The real reason is that one of the two routes is backward stable and the other is not, and at κ = 10¹⁴ they differ by twelve orders of magnitude in the number that says whose fault a wrong answer is.
The gap refinement can close
Multiplying by a computed inverse is not backward stable, and refinement at the working precision repairs it. That much is settled. The claim beside it — that the forward error does not move — was read at one conditioning and four corrections too late. Swept over ten, it moves at every one, and it lands on the LU route's own number after a single correction.
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.
The two numbers a caller has
Choosing between the two least-squares methods is a statement about where the noise is, and the two quantities a caller can compute are both blind to it. The residual separates the answers by 0.14 per cent where their accuracies differ by 14, and κ(A) falls from 3.54 to 2.46 across a sweep in which the error rises by a factor of sixty-two.
An exact answer to a measured problem
The residual is the zero vector, nothing was rounded at any step, and the answer is wrong in its first digit. Data accurate to fourteen places, an exact solve of the system it defines, and an error of 10⁻⁵ — because conditioning was never a statement about arithmetic and removing the arithmetic error removes none of it.
The right-hand side as one more column
Modified Gram–Schmidt's Q is 4.3·10⁻⁹ from orthogonal at κ = 10⁸, and a least-squares solve that multiplies b by it is wrong by 0.13. Hand the same routine b as an extra column instead and the answer is right to 2.7·10⁻¹⁰ — closer than Householder's 4.0·10⁻⁹. Classical Gram–Schmidt gains nothing from the same trick, to the last bit.
Where the augmentation puts the cost
Add γAᵀA to the objective block of a saddle-point system and its Schur complement tends to I/γ, so the cheapest possible approximation becomes the right one and the golden-ratio spectrum arrives — within 7.6·10⁻⁶ at γ = 10⁶. MINRES falls from 21 steps to 6. The inner solve with the augmented block rises from 14 conjugate gradient steps to 43, their product does not fall at all, and the answer loses seven and a half digits on the way.
An accuracy that is a backward error
Every backward error measured so far is something an algorithm produced and somebody then measured. This one is a line in the program. Solving with a compressed matrix gives a residual that is the compression's own error, at a slope of 1.000 over ten decades, so the knob that sets the storage sets the backward error directly.
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.
A tensor that cannot be decomposed
Every member of a certain sequence is exactly a sum of two rank-one terms, and both terms are written down in closed form. A three-hundred-sweep fit from a random start does not find them, and stalls at the same one per cent however far the sequence goes — while a fit started at the answer loses digits exactly as 2n² says it should.
The knob that moved two things
Decide how many digits the answer needs, divide by the condition number, and compress to that. It is the one rule licensed in advance here, and its two factors are not the independent inputs it reads as: the partition's leaf moves neither of them and moves the answer by nearly a factor of three, and the only knob here that raises κ halves the ranks while it does so.
The number that cannot rank them
Levinson and Gaussian elimination are indistinguishable on the backward error a library reports — every one of ninety-six measurements between 1.16·10⁻¹⁷ and 5.73·10⁻¹⁷. The structured backward error separates them by up to a hundredfold, in whichever direction the point happens to give. Only the forward error ranks them, and only because this family's exact answer is known.
Two condition numbers of one matrix
κ₂ is a worst case over perturbations of a given norm, and a normwise perturbation may put its whole budget on the smallest entry. The componentwise number is a worst case over perturbations proportional to the entries, which is what a backward-stable factorisation actually makes. On one matrix they are 3·10¹³ and 13.3, and the error obeys the second.
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 circulant the problem did not contain
A matrix that differs from a circulant in two corner entries can be solved through the circulant, by a transform and a two-by-two correction, and the cost claim is exact. The accuracy claim is not. On tridiag(−1, 2 + σ, −1), whose condition number stops at 1,712, the correction is wrong by 1.2·10⁻⁴ at σ = 10⁻⁸ while elimination is right to 1.1·10⁻¹⁴ — because the periodic neighbour is singular at σ = 0 and the two-by-two system inherits that. Solved by Cramer's rule, as here, the two amplifications multiply; a later measurement found that a pivoted solve of the same two-by-two system removes the second.
Three errors and one number
This site's identity has two factors and a division of blame between them. Two fields have now added a third party and a fourth, and only one of the four is a property of anything — the others are decisions, made before the arithmetic, reported by nothing.
Two near-zeros cost less than one
Solve a well-conditioned tridiagonal matrix through a nearly singular wrap and the correction's accuracy is not set by how singular the wrap is. At κ = 4·10⁷ one wrap returns the answer to 8.8·10⁻¹¹ — better than κ·u — and another, at κ = 3.8·10⁷, returns it to 3.3·10⁻⁶. The difference is how many of its samples sit near the symbol's zeros. A real wrap lands on a conjugate pair, a rank-two correction absorbs the pair exactly, and its two-by-two system has condition number 1.00 — which mattered because that system was solved by Cramer's rule; solved with pivoting, the single landing costs what the pair costs.
The fifth author
Four authors of a wrong answer have been named already and each is a statement about one computation. The fifth is not: it is what separates two computations that are both correct, it is a backward error of measurable size, and no residual, bound or condition number contains it.
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.
One sequence and two recurrences
CGLS and LSQR compute the same iterates — the minimiser over a space is unique, so there is nothing to choose between them in the algebra. At κ = 10⁶ they cost 42 steps and 47. At κ = 10¹⁰ they cost 110 and 209, across four seeds, and the quantity that separates them is the orthogonality of a basis neither of them keeps.
The number that moves when the problem does
Two quantities are offered as the condition number of one eigenvalue. One is unmoved to eight digits by a change of variable that is exact in both directions, and grows like the square root of the chain's length. The other is inflated by ten orders by that change of variable, and is ten times too large before anything has been done at all.
Nine steps of pessimism
A proved bound is 8 to 26 times the error it bounds, at every precision from 16 to 40 significand bits. A carried interval is (√2)ᵐ times too wide after m re-enclosures. The two cross between eight and nine, so the method everybody warns against is the tighter of the two for a short computation.
An augmentation read in the smallest eigenvalue
An augmented Lagrangian preconditioner's least work sat at γ = 1, 10⁴ and 1 on three systems, and two of the three optima sat where the smallest generalised eigenvalue was about 0.06 — which suggested a rule written in ν rather than γ. On twenty-four systems whose norms are all one, the least-work γ spans seven decades and ν at the optimum spans a factor of thirty, so there is no one ν. There is still a rule: take the smallest γ at which ν reaches 0.03, and the median system pays 7 per cent over its least work and the worst 29, where the best single γ pays 61. Its price is digits — twelve times the best forward error on the median system, 4,561 times on the worst.
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.
A target the residual can promise
A caller who wants inexact Newton's answer to six digits usually passes 10⁻⁶ as the residual tolerance, and on five problems at four targets that misses by 7 to 35,000 times. Divide the target by a condition number and it is met on every cell where a residual can certify it — and the condition number need not be known: the Ritz values conjugate gradients produces on the way give the Jacobian's own, settled by the sixth Newton step and within eleven per cent of the truth at the end, and two to nineteen times below the linear part's. Stopped that way, with the usual floor under the forcing term, the run lands within a fifth of its target and is cheaper on 16 of 19 cells than the unfloored run stopped by someone who knows the answer.
The honest residual is not a stopping test
A conjugate-gradient run in reduced working precision reports a residual pinned near 10⁻¹² while its error spans eleven orders, and the repair was to recompute the residual in double. As a report it works: on thirty runs it lands within a factor of a quarter to five of the error. As the thing to stop on it fails outright: below 53 bits it is passed on none of twenty-five runs, which go on to the 300-step cap or until their own recurrence collapses — 7,694 products in all against 605. One clause fixes it. Stop also when two checks in a row fail to halve the double residual, and every run ends within thirty-six products, at the same error, reporting a number that means something — and at 8 and 11 bits on the larger grids, sooner than the recurrence's own test.
The switch is read before the solve
Scaling the constraint rows of a saddle-point system rescued the route to a constrained least-squares fit by changing which row partial pivoting takes at the second step. The scale at which it changes can be read before anything is solved: scaling multiplies every constraint row's candidate by s and leaves every other row's alone, so one unscaled elimination, recording the two kinds of candidate at each step, gives the switch exactly — on all forty-nine problems, to within one part in 10¹⁵ of what bisection finds, decided at the second step everywhere but at a coupling of one. A scale just past it removes the catastrophe where there was one. It does not make the route as good as eliminating the constraints first: on four problems every scale tried is thirty to thirty-nine times worse, and they are the problems where the unscaled route was too.
Two forcing terms, one floor
Inexact Newton's adaptive forcing rule comes in two versions, and every measurement of the floor under it used the second, which reads the ratio of the last two residuals. The first reads how wrong the linear model was at the last step, and it was natural to hope that a rule watching the model's own error would not solve its last step past what the stopping test needs. It does. Run without the floor on five problems at four forward targets, it over-solves its last step by a median of 34 times, against the second rule's 95; the floor saves 17.5 per cent of its inner work, against 16.0. Floored, the first rule is the cheaper by 4.6 per cent overall, and it buys that with Newton steps: two more on the median cell, a third less inner work on the strongly nonlinear problem, and 4.5 per cent more on the easy one.
The multipliers were a set
A crossover that solves the equality problem an interior-point iterate's diagonal suggests, then certifies the answer, refuses a guess with more active rows than unknowns — which a degenerate vertex produces as a matter of course. The two remedies a simplex code and a regularised solver would reach for, choosing a basis or regularising the extra rows, both return the right point from the first or second iterate, and both fail the certificate on most programmes, at almost every iterate. The point is never what fails. The certificate checks the one multiplier vector a solve happens to return, and at a degenerate vertex the multipliers are a set; asking whether the set holds a nonnegative vector certifies the same point at once.
The residual knew the error
A Sylvester solve's structured backward error climbed by a factor of 26,000 while its forward error did not move, and the reading was that the condition number belonging to those structured perturbations must fall by the same factor. It was predicted to fall by at least ten thousand across the sweep, and its product with the backward error to match the forward error within ten. Neither happens. The structured condition number rises, by a factor of 2.8 at every size of C, because it is a worst case over every direction a perturbation of that size could take, and the backward error's perturbation takes the most harmless one. Their product overstates the error by up to 3·10⁶ on one route and 9·10⁶ on the other. The relative residual times the plain inverse of the Kronecker matrix's smallest singular value is within a factor of 0.96 to 9.7 of the forward error on all 120 solves.
A later look is a worse stop
Every stopping test for reduced-precision conjugate gradients had read the residual, and the residual flattens tens of steps before the error stops falling. The method carries a cheap lower bound on its own energy error — the sum of each step's step length times its squared residual over a window of steps that follow — and a clause that stops when that bound falls below the working precision's share of the iterate stops twenty runs on the scaled Laplacian within 1.22 times their least error, a third of the residual clause's overrun. The prediction that it would stop within thirty steps of the least on the median run misses by three. And the window turns out to be a pure delay: in reduced precision the error creeps back up after its least, so the longer the window waits, the worse the stop.
The middle eigenvectors come back exact
The Sylvester–Kac matrix's eigenvectors are known exactly, and the middle ones were predicted to be lost before their eigenvalues, since the gap between neighbouring eigenvalues is only two. Started from the all-ones vector, inverse iteration seems to confirm it: half the middle eigenvectors are wholly wrong at order 80 while their eigenvalues keep five digits. But the all-ones vector has, in exact arithmetic, no component at all along every other eigenvector. From a random start the middle eigenvectors come back exact to fourteen digits at every order measured, while their eigenvalues lose up to eleven. What is lost is at the ends of the spectrum, in the smallest entries of eigenvectors whose entries span twenty decades — and never by more than three units of roundoff times that span.
The step before the reset
On the strongly nonlinear problem, inexact Newton's second forcing rule took two more Newton steps than the first and half as much work again, and the blame went to its safeguard, which let the forcing term jump back to 0.9 when the residual rose. Capping that jump at ten times the last forcing term was predicted to remove the two steps and bring the rule within five per cent of the first. It removes the steps, at three targets of four. It saves 0.7 per cent of the work, and leaves the rule 45 per cent dearer than the first. The reset was the cheap part: four loose steps for 55 inner iterations. The cost was the step before it, solved to a forcing term of 0.024 for 109 iterations, where the first rule spent 5 — and on the ill-conditioned problem, where the residual never rose at all, the cap costs ten per cent.
The row that was nearly there
Move the spare rows of a degenerate vertex off it by 10⁻⁶ to 10⁻¹⁴ and the set question still certifies the last iterate of every run, as predicted. It no longer certifies early. Between 10⁻⁶ and 10⁻¹⁰ it waits nine to seventeen iterates, because the basis it certifies holds a near row at zero and its point sits three to forty-eight times that row's slack outside the feasible set. At 10⁻¹² the same displacement falls under the certificate's tolerance and the set certifies from the first iterate. The basis turns when μ passes a tenth of the slack, while the diagonal still calls every near row active.
The gap was the square
Eisenstat and Walker's second forcing rule was a third dearer than the first on a strongly nonlinear problem, and the cost had been traced to one over-tight step: its safeguard is skipped below 0.1, so the forcing term fell to 0.024 and the step took 109 inner iterations. Applying the safeguard always was predicted to hold that step at 0.04, halve its cost and bring the rule within fifteen per cent of the first. It holds the step at 0.038 and saves twenty iterations; the rule stays forty per cent dearer. The residual still rises after that step, because at that point Newton's own step overshoots and any solve tighter than about 0.06 reproduces it. A line search removes the rise and the reset and still leaves the second rule thirty-six per cent above the first. What is left is the rule itself: 0.9 times the square of the last residual ratio, which after every fast fall asks for a solve far tighter than the next step needs.
The vector moves with its eigenvalue
The Sylvester–Kac matrix's middle eigenvectors came back exact to fourteen digits by inverse iteration while their eigenvalues lost eleven, and the route LAPACK uses — back substitution in the computed Schur form, then the accumulated orthogonal transformation — was predicted to lose them, at about the eigenvalue's error divided by the gap of two: 10⁻⁵ at order 80. It does, at 2.3·10⁻⁵, so the route is the whole of the difference: nine orders of magnitude between two ways of computing the same vectors from the same eigenvalues. The constant is not one over the gap. On all 274 eigenvectors whose eigenvalues are off by more than 10⁻¹¹, at every order from 40 to 80, the Schur route's error is 0.76 to 0.84 times its eigenvalue's error, and 0.79 is a number the exact vectors carry: how fast a unit Krawtchouk vector turns as its eigenvalue moves. The Schur route returns the right eigenvector of a wrong eigenvalue.
The error the method already knows
Summing the exponential's Taylor series throws away a known number of digits, and the number is on the machine while the sum is being formed. The largest term divided by the answer, times the unit roundoff, tracks the relative error that comes out — to within a factor of nine, across fourteen orders of magnitude of it — and nothing reports it.
Named alongside it
The objects these essays reach for when they reach for this one.
Condition numberBackward errorResidualExact ground truthStopping criterionConjugate gradientsSaddle-point systemsUnit roundoffHilbert matrixInexact newtonInterior-point methodIterative refinement