Numerical Linear Algebra
where the algebra stops being the arithmetic
Theme

The thread: Whose fault is it — page 9

Essays 193 to 194 of the 194 on this theme, in the same order.
10⁻³10⁻²10⁻¹1024681012size of the negative eigenvalue, −λproducts before the test firesharder to find, and milder8 spectra, n = 50products at the largest λ3products at the smallest10smallest share of λ recovered0.14largest0.34the one that hidesis the one that matters least Iterating, instead of factorising

A proof that does not ask how large the matrix is

Proving a Hessian indefinite costs three matrix–vector products when the negative eigenvalue is 3 and nine to eleven when it is a thousandth, and that pair of numbers barely moves across a fourfold range in n. The factorisation that settles the same question costs a third of n³, which grows by a factor of sixty-four over the same range.

 10³10⁶10⁹10¹²10¹⁵10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1largest iterate on the way, ‖x‖difference between the two residualsthe bound, linear in ‖x‖what it does, slope 0.46a bound of one, a walk of a halffitted slope0.46the bound's slope1smallest gap measured3.9·10⁻¹⁵largest gap measured1.5·10⁻¹⁰share of the bound, near end9.1·10⁻⁴share of the bound, far end3.4·10⁻⁹the bound is rightand loose by a square root Iterating, instead of factorising

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⁻¹⁵.

All themes