Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Seminormal equations — where it appears

Solving least squares with the triangular factor R of a QR factorisation but without its orthogonal factor, by two triangular solves on the normal equations. It saves storing Q and squares the condition number in the solve, which one step of refinement from the rows' own residual repairs.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

10²10³10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹steps takenlargest relative error in a coefficientcarried factorrecomputedcarried + one correction+ a second correctionHouseholder QR, same rowsdrift of the factorafter 2875 stepsκ(A) of the window2·10⁴carried factor2.8·10⁻⁸recomputed5.8·10⁻⁹carried + one correction7.1·10⁻¹³+ a second correction3.7·10⁻¹²Householder QR, same rows1.1·10⁻¹²measured against the coefficients in exact rationalsthe refresh repairs the factor, not the answer

The repair the drift did not need

A sliding window's carried Cholesky factor drifts 3.9·10⁻¹⁴ from its data, and multiplying by κ(AᵀA) predicts eight lost digits in the coefficients, a stream conditioned at 10¹² losing the answer, and a periodic refresh of the factor as the default repair. Measured against coefficients computed exactly in rationals, all three come out differently. On a stream made ill-conditioned by scaling, the conditioning never reaches the coefficients. On a collinear stream, a freshly recomputed factor is as wrong as the drifted one. And one correction from the window's own rows reaches Householder's accuracy for a fraction of a refresh's cost.

sequence · Sequence stability noise none, mediansthe answer's step0fresh start, corrected6.2·10⁻⁹carried start, corrected1.3·10⁻¹¹0200400600800100010⁻¹²10⁻¹⁰10⁻⁸steps along the streamlargest relative coefficient errorfresh solve, one correctioncarried answer, one correctionfresh solve, two correctionsHouseholder on the rowseach correction contracts its start by the same factorthe nearer start wins

The answer the last window left

A sliding window that corrects its least-squares answer at every step could start each correction from the previous step's corrected answer instead of from a fresh solve: the two windows share all but one row. On a stream with any noise in it, that start is three orders worse. The window's exact answer moves by 0.79 of itself in one step at κ(A) = 3·10⁶, a fresh seminormal solve is wrong by only 1.8·10⁻⁴, and one correction contracts either start by the same factor — so the fresh start ends at 2.2·10⁻⁸ and the carried one at 3.7·10⁻⁵. Only on data that agree exactly does carrying win.

sequence · Sequence stability

Named alongside it

The objects these essays reach for when they reach for this one.

Backward errorCholesky factorisationCondition squaringExact ground truthIterative refinementLow-rank updateRecursive least-squaresComponentwise condition numberWarm start

All concepts