Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

Exact ground truth — the series

4 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. H13 x = b, b formed exactly so that x = (1, 2, …, 13)12345678910111213exact1.00002.00003.00133.97865.18864.993010.46720.048921.2657-2.575319.21478.906013.5113computed6.6 correct digits4.8 correct digits3.4 correct digits2.3 correct digits1.4 correct digit0.8 correct digitno correct digitsno correct digitsno correct digitsno correct digitsno correct digits0.6 correct digit1.4 correct digitbackward error2.2·10⁻¹⁷κ = 1.7·10¹⁸The algorithm solved a neighbouring problem perfectly. That problem's answer is this one.right-hand side built in BigInt rationalsthe truth is known

    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.

    part 2 · error
  2. largest eigenvalue erroras given, order 960.043balanced, order 964.4·10⁻⁴symmetrised, order 962.2·10⁻¹²016324864809611210⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹order nlargest |computed − exact| eigenvaluean error of one: the integers are no longer told apartas givenbalancedsymmetrisedopen dots: complex pairs returned for a real spectrumevery entry is an integer, stored exactly

    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.

    part 3 · error
  3. 16243240485664728010⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹10⁴order nerrormiddle eigenvalues, errormiddle eigenvectorsworst eigenvector, componentwiseworst eigenvector, normwisefloored at 10⁻¹⁷the middle is the best of the spectrum

    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.

    part 4 · error
  4. 16243240485664728010⁻¹⁷10⁻¹⁵10⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³orderworst over the middleeigenvalue erroreigenvector, Schur routeeigenvector, inverse iterationmiddle eigenvalues, |λ| ≤ 5the route is the answer

    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.

    part 5 · error

All series