The exact solution of a 13×13 Hilbert system beside the computed one
At its defaults it draws the exact solution of a 13×13 hilbert system beside the computed one. Two columns of numbers: the exact answer, which is the integers one to thirteen, and the answer double-precision elimination returns, with the number of correct digits beside each.
exact-ground-truth is one function in lib/figures/error.js —
error — the backward one, the forward one, and the number between them. Everything below came out of it during this build, at
arguments taken from the essays rather than invented for this page. A figure here is the
figure a reader meets in an essay, and if the generator changes, this page changes with it.
At its defaults
Drawn even though every essay passes arguments — which on this site is every essay, at 100% of placements since the standard pass. A default nothing exercises is a trap for the next essay to call this with none, and this is the page where a default that has drifted from the figures around it becomes visible.
Two columns of numbers: the exact answer, which is the integers one to thirteen, and the answer double-precision elimination returns, with the number of correct digits beside each.
n: 13
The arguments are the ones A condition number sent to infinity passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Two columns of numbers: the exact answer, which is the integers one to thirteen, and the answer double-precision elimination returns, with the number of correct digits beside each.
show: "kac-error"
The arguments are the ones Balanced is not symmetric passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
The Kac matrix of order n has zeros on its diagonal, 1 to n − 1 above it and n − 1 to 1 below, and eigenvalues exactly the integers from minus n − 1 to n − 1 in steps of two. as given: largest error 1.6e-14 at order 8, 1.0e-6 at 64, 2.1e+0 at 120, with complex pairs from order 112; balanced: largest error 1.8e-14 at order 8, 1.5e-8 at 64, 1.8e+0 at 120, with complex pairs from order 120; symmetrised: largest error 2.0e-14 at order 8, 7.5e-13 at 64, 3.4e-12 at 120.
show: "kac-spectrum", n: 48
The arguments are the ones Balanced is not symmetric passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Dots: the computed eigenvalue's distance from the exact integer. Lines: the condition number of that eigenvalue times the unit roundoff times the matrix norm. as given: worst condition number 6.6e+5, at eigenvalue -1; largest error 3.0e-9, at eigenvalue -3; balanced: worst condition number 1.3e+4, at eigenvalue -11; largest error 4.7e-11, at eigenvalue -19.
show: "kac-ratio"
The arguments are the ones Balanced is not symmetric passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
1568 eigenvalues of Kac matrices of orders 8 to 112, as given and balanced, wherever the computed spectrum was still real. First-order perturbation theory puts each on the diagonal, error equal to condition number times unit roundoff times norm. The ratio of error to that prediction has median 0.51, a tenth of them below 8.0e-2, and the largest is 135.
show: "kac-kappa"
The arguments are the ones Balanced is not symmetric passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
The condition number of the worst-conditioned eigenvalue, from the eigenvectors of the similar symmetric matrix and the diagonal that symmetrises. As given it runs from 2.5 at order 8 to 2.3e+16 at 120; balanced, from 1.4 to 3.7e+14. Balancing divides it by 7.5 at order 24 and by 62 at 120, and both grow by a factor of about 15 every eight orders.
What it checked while drawing
Every figure above checked its own claims on the way to being drawn, and a claim that failed
would have stopped the picture rather than shipped a wrong one. Those checks used to leave
no trace at all: a passing one returned true and the only evidence the figure had
checked anything was that nothing crashed. The list below is what they actually said, collected
by running this generator with an observer installed — not a description of
what it is believed to check.
11 distinct claims across 6 sets of arguments, grouped below by shape — because most of them are one sentence with a different number in it, and how many separate times that sentence was put to the test is the informative part.
a route this file computes
an order between 2 and 200
an order the dial draws
an order the sweep draws
and at least one component has no correct digits at all
Jacobi needs a symmetric matrix
LU is for square matrices
matmul shapes agree
the right-hand side came from exact arithmetic agree
the runs carry their computed eigenvalues
the solve is backward stable even here
Against the rule
It calls a factoriser without drawing a factorisation
(solve),
so the rule is written down as not applying, with the reason:
shows a solution vector against the exact one; the badge carries the backward error instead
The exemption list is the interesting half of the rule rather than an escape hatch — it is
where a decision about a figure had to be argued in one line. residualcheck
refuses an exemption that is not doing work, and rejected ten of the fifteen written for the
expansion's figures on exactly that ground: a figure whose vertical axis is a residual
satisfies the rule by construction, and touching a factoriser does not by itself require an
entry.
Across the library: the rule bites on 217
of 397 generators —
199 print a residual and
18 are exempt with a published reason;
180 factorise nothing.
Read from lib/residual-rule.js, which is the same body the gate enforces from,
and the gate's last check fails the build if this page and it disagree about any generator.
Where it is called
Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.
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.
Structure, and the solver that cannot see itA limit the matrix never reaches
Szegő's theorem gives a Toeplitz family's condition number in closed form — ((1+ρ)/(1−ρ))², which is 81 at ρ = 0.8. The 8×8 section reaches 52% of it, the 128×128 reaches 98.9%, and none of them ever arrives. A statement about a family is not a statement about the matrix in front of you.
Two errors, and whose fault they areA 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.
Eigenvalues, singular values, rankAccurate is not a property of a method
A bidiagonal matrix whose every entry is 1 or 4096 has singular values spanning thirty decades. On it, the method recommended for small singular values loses the small one by one and a half per cent, the sweep with the theorem behind it does not converge at all, and the shift the theorem is a warning about gets every value to 5·10⁻¹⁶. Nothing there contradicts the theory.
Two errors, and whose fault they areAn 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.
Two errors, and whose fault they areBalanced 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.
Structure, and the solver that cannot see itThe 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.
The arithmetic underneathWhat a float can hold
The representable numbers are not a fine fuzz spread evenly over the line. They are evenly spaced inside each power-of-two interval and twice as far apart in the next one up, and almost everything else in this subject is a consequence of that one fact.