Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Fixed-point iteration — where it appears

An iteration that stops when its input reproduces its output. Whether it has converged is a question about the condition it was defined by rather than about how far its last step moved, and the two are not the same test.

Named by 3 essays across 3 fields — each of them below, with the objects they name alongside it.

159131721252910⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹steprelative error in the orthogonal factorNewtonNewton, scaledNewton–Schulzone fixed point, three costsscaled Newton, steps7Newton–Schulz, steps28Newton at step 657scaled Newton at step 64.4·10⁻¹³a Newton step needs an inverseand a Schulz step needs two products

An iteration that only multiplies

Newton's iteration for the polar factor needs an inverse every step. Newton–Schulz needs only matrix products — nothing that reads an entry, nothing that pivots — and it converges if and only if every singular value is below √3. At 1.73205 it converges and at 1.73206 it returns an orthogonal matrix that is not the answer, with a residual of 5·10⁻¹⁶ and nothing to say so.

orthogonality · Polar decomposition 01234567891011121310⁻¹110¹10²10³iterationinterpolation point σa fixed point that is a conditionorder4iterations13σ against −λ(Aᵣ)2.8·10⁻¹²H₂ error4.3·10⁻⁵it stopped movingand the condition holds there

Interpolating at the model’s own poles

One choice of interpolation points is not arbitrary — the mirrored poles of the model about to be built. It is a fixed point rather than a guess, and when it is reached it beats a method costing O(n³) — by 0.4 per cent, which is the honest size of the whole contest.

reduction · Moment matching κ(A) = 3·10⁶23 of 24 rows, noise 10.29all 24, noise 13.3·10⁻⁹no correction, noise 19.4·10⁻⁴612182410⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1rows the correction reads, of 24relative error, medianno correction, noise 1noise 1noise 10⁻⁴noise 10⁻⁶no noisethe last row is worth nine decadesa correction needs every row

A correction that reads every row

A sliding least-squares window moves its answer by the update its entering and leaving rows imply and then corrects it once against all 24 rows it holds. The proposal was to read only the rows of highest leverage, a quarter of them, predicted to recover most of the full correction on a stationary stream. On every noisy stream it does the opposite: the answer ends with a relative error of order one — 2.8 at a noise level of one, where reading every row leaves 3.3·10⁻⁹ and not correcting at all leaves 9.4·10⁻⁴. Choosing the rows at random, by age or in rotation changes nothing. Leaving out one row of 24, the one of least leverage, still leaves 0.29. A correction is a Newton step whose fixed point is the answer only because the residual is orthogonal to all the columns summed over every row; read from some of the rows, its fixed point moves by the omitted rows' share of the residual, and the window settles there. Only on a stream with no noise, where every row's residual is zero at the answer, does a partial correction work.

sequence · Sequence stability

Named alongside it

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

Flop countBalanced truncationCondition numberConvergence rateExact ground truthFixed pointH2 normHermite interpolationIterative refinementLeast-squaresLeverageLow-rank update

All concepts