Numerical Linear Algebra
where the algebra stops being the arithmetic
Theme

The thread: Measured, not asserted — page 15

Essays 337 to 339 of the 339 on this theme, in the same order.
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⁻¹⁵.

 22.32.62.910⁻⁴10⁻³10⁻²10⁻¹1log₁₀ numbers storeddistance to the dominant eigenvalueArnoldi, linearisedprojected quadraticper number heldstorage, linearised832storage, second-order416Ritz values, linearised26Ritz values, second-order52half the storageand twice the approximations Iterating, instead of factorising

The answer that arrives when the space runs out

A second-order Krylov recurrence holds vectors of length n for a problem with 2n eigenvalues, so it is exact at n steps where the linearised route needs 2n. The machine-precision reading at forty-four vectors on a chain of forty is that exhaustion rather than convergence, and it arrives through a basis whose ‖QᵀQ − I‖ is above one.

 110¹00.30.60.91.2trust-region radius Δshare of the exact model decreasethe exact subproblem7 radii, n = 60share at the smallest radius0.95share at the largest0.3products, at most8radii stopped by the curvature4a few products against an eigendecompositionand most of the decrease Iterating, instead of factorising

The certificate that arrives soonest is worth least

The more negative a Hessian's smallest eigenvalue, the sooner conjugate gradients meets a direction of negative curvature — and the less of the exact trust-region decrease that direction turns out to be worth. At λₘᵢₙ = −10 the step arrives after two products and gets 39.6 per cent; at −10⁻³ the same two products get 89.8, and the whole sweep costs eight.

All themes