Two errors, and whose fault they are
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.
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.
The condition number is an amplifier
κ is usually introduced as a definition and then quoted. It is a measurement: perturb the input by a known amount, look at how much the output moves, and the largest ratio you can find is the number.
An answer that is known
Almost every demonstration of numerical error estimates the error by computing the same thing more carefully. The Hilbert matrix does not need that: its inverse is a closed form in integers, so the true answer is available exactly and the error is measured rather than approximated.
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.
An estimate that can be fooled
Nobody computes a condition number, because forming an inverse costs more than the solve did. Every library estimates it instead, from four or five products with a factorisation already in hand. The estimate is exactly right on four random matrices out of five — and there is a matrix, three distinct entries wide, on which it returns a twentieth of the truth.
The number that decides nothing
The determinant is the first scalar anybody attaches to a matrix and the last one worth consulting. A tenth of the identity has a determinant of 10⁻⁶⁰ and a condition number of exactly one. The Hilbert matrix's determinant stops being right at n = 13 and stops being a number at n = 29, and nothing in between reports either.
The zero you are allowed to write
A deflation criterion sets a subdiagonal entry to zero because it is small. A drop tolerance discards an entry of a factor because it is small. A truncation discards a singular value because it is small. Three fields, three vocabularies, no shared arithmetic — and plotted as work saved against error accepted, one curve.
Deciding that a zero has arrived
The previous tolerances were offers — accept this much error, save this much work. A detection threshold is not an offer, because both directions are failures. One matrix here has three genuinely near-invariant subspaces, and the constant somebody typed decides which of them the recurrence stops at; at eight significand bits the same kind of constant produces a proof of something false.
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.
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.
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.
The roots are not the coefficients
A polynomial whose roots are the integers one to twenty, expanded exactly, handed to the routine every library uses. The computed roots are wrong in the third digit, the computation is backward stable for the matrix it factorised, and above degree eighteen the coefficients are not double-precision numbers at all.
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.
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 tolerance is priced by the problem
Three tolerances from three fields sit on one pair of axes and agree to within a factor of 5.74. That factor is the ratio of the two curves that cannot move. Change the only problem in the comparison and the third curve's fitted slope swings from 0.188 to 0.040 while the printed spread does not shift by a digit.
The tail a sample never reaches
Hager's estimator is exactly right on four random matrices in five, and that share is stable — between 80.5 and 87.5 per cent across nine sizes. The worst underestimate is not stable at all: it falls every time more matrices are drawn, from 0.746 at sixty to 0.377 at four hundred, and the matrix built to defeat the estimator sits five times below anything four hundred draws found.
Two columns see what one walk cannot
The condition estimator every library ships walks from the all-ones vector, and a matrix whose largest column cancels against that vector hides from it: at n = 24 it reports five per cent of the truth. The block estimator behind MATLAB's condest walks with two vectors, the second random. On the same matrix at three sizes it is exact on every one of twenty seeds. On four hundred random 8 × 8 matrices it is exact on 96.5 per cent where the single walk is exact on 83.0, and its worst case, 0.596, is reached in the first fifty draws and not lowered by the next 1,550. The single walk's worst was still falling at 1,600. Four vectors are exact on all 400.
Balanced is not symmetric
The Sylvester–Kac matrix is made of small integers, so a double holds it exactly, and its eigenvalues are the integers from −(n − 1) to n − 1 in steps of two. Every digit an eigensolver loses on it is therefore the solver's own, and it loses them at exactly the rate first-order perturbation theory predicts: the median error is half the prediction across 1,568 eigenvalues. Balancing, the preprocessing libraries apply for this kind of matrix, divides every condition number by about sixty and leaves their growth untouched, and at order 112 the unbalanced solver returns eighteen complex eigenvalues for a spectrum of integers.
Columns that steer a random start
A condition estimator whose first vector is random cannot be built against, and concentrating the hidden column did not hide it: its own entries steer the first sign vector onto it. Give the steering to other columns — each equal on both rows of every pair the hidden column alternates over — and the random start is fooled after all. The prediction was a factor of one over the square root of the number of steering columns, on a share of seeds that falls as they lose to the hidden column, and the block of two fooled as often. The factor is whatever the builder chooses; the share, at a fixed factor of one half, rises with every column added, from 9 per cent with four to 77 with thirty-four. And the block of two is not fooled as often: it is fooled on the square of the single start's share, and the block of four on its fourth power — independent guesses, which is the one thing that still works.
A first vector nobody can build against
The matrix built to fool a condition estimator is built against one vector, the all-ones vector its walk starts from, and the block estimator escaped it by adding a second, random one. Starting the single walk from random signs instead escapes it on every one of forty seeds at every size from 8 to 48, for the same 4.3 products, and loses nothing on random matrices — 86.5 per cent exact at size 8 against 84.0 from all ones, with tails that cross between sizes. The obvious way to build against a random start, a hidden column on few rows whose signs a random vector cancels half the time, fails on every seed: the hidden column writes itself into the walk's first product and turns the walk towards it. What the block of two's second vector buys is ten points of exact share, not the escape.
A basis that has to know where the roots are
Wilkinson's polynomial loses its roots in the third figure at degree twenty when they are computed from its monomial coefficients, and the repair offered was to change the basis: in Chebyshev coefficients, with the colleague matrix, the conditioning 'does not degrade exponentially with degree'. Expanded exactly in that basis and rounded once, the integers' roots come back ten orders better at degree twenty — 4.4·10⁻¹³ against 7.6·10⁻³ — and still degrade exponentially, at a third of a decade a degree, to 2.8·10⁻⁴ at forty. Place the same number of roots at the interval's Chebyshev points instead and they stay at 10⁻¹⁴ at every degree, while the monomial route loses them as fast as the integers. The basis does not repair the problem; it has to match where the roots are.
The second factor was the last row
Wilkinson's polynomial in Chebyshev coefficients loses its roots exponentially from the colleague matrix, and two factors accounted for the loss: the roots' own conditioning, and the size of the matrix's last row against the rest of it. A diagonal similarity by powers of two — balancing, which changes no eigenvalue and rounds nothing — removes the second factor entirely: the balanced error sits within a factor of two and a half of the conditioning at every degree from fourteen to forty, three and a half thousand times better than unbalanced at forty. What is left is the conditioning, still exponential. Balancing the monomial companion matrix takes its norm down by forty-five orders and gains nothing, because there the error was never the matrix's.
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 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.