Numerical Linear Algebra
where the algebra stops being the arithmetic
Series

Residual gap — the series

3 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 01428425670849811210⁻²²10⁻¹⁸10⁻¹⁴10⁻¹⁰10⁻⁶10⁻²conjugate gradient iterationrelative residualthe unit roundoff, 1.11·10⁻¹⁶the answer's residualthe residual reportedtwo residuals, one runreported, at its best6.9·10⁻²¹the answer's, at its best5.1·10⁻¹⁰unit roundoff1.1·10⁻¹⁶largest iterate on the way9.3·10¹³iterations drawn110the recurrence remembers every roundingand the stopping test is written in it

    The residual the method reports

    Conjugate gradients prints a relative residual of 6.9·10⁻²¹. The unit roundoff is 1.1·10⁻¹⁶, so that is not a small residual and not a large one — it is not a residual. The vector the method is holding at that step has ‖b − Ax‖/‖b‖ = 5.1·10⁻¹⁰, and nothing in the run says so.

    part 1 · iterative
  2. 051015202530354010⁻³10⁻¹10¹GMRES steprelative residualthe two curves are the same curvea number re-derived, not carriedworst reported/actual factor1.8at step40‖VᵀV − I‖ of the basis1.4reported at the last step0.041actual at the last step0.074the same family of methodsand only one of them lies

    The number that is re-derived

    GMRES prints a residual it never computes from its answer either. On the matrix that sends a conjugate gradient recurrence 7.3·10¹⁰ wrong, and on two others chosen to be worse, its number is never more than a factor of 2.86 out — while the basis it is computed from has lost orthogonality entirely. The disease is not iterative methods, and it is not floating point.

    part 2 · iterative
  3. 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

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

    part 3 · iterative

All series