Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Chebyshev basis — where it appears

Writing a polynomial in Chebyshev polynomials rather than in powers, so that its coefficients do not span orders on an interval. Its companion matrix is the comrade matrix, built from the three-term recurrence instead of from a shift.

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

263850627410⁻⁵10⁻³10⁻¹rows in the linearisation‖g − r‖ on the target setpolynomialrationalequal cost, two basesreach0.06largest size drawn78rational there2·10⁻⁵polynomial there0.0015the ratio73no winner on an easy targetand two orders on a hard one

Two approximants and one matrix size

A polynomial approximant linearises to nd rows and a rational one to n(m+1), so the fair contest fixes the matrix and varies the basis. On an easy target set the two are indistinguishable and the ordering flips with the noise; on one that reaches a branch point the rational pulls away by two orders.

polynomial · approximant choice 57911131517192110⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²degreerelative error of the worst rootmeasuredκ × ua polynomial is its coefficientsworst root, measured0.0076predicted, κ × u0.0023root condition number10¹³largest coefficient1.4·10¹⁹the roots are integersand the coefficients are not the roots

The roots are not the coefficients

A polynomial whose roots are the integers one to twenty, expanded exactly, handed to the routine every library uses. The computed roots are wrong in the third digit, the computation is backward stable for the matrix it factorised, and above degree eighteen the coefficients are not double-precision numbers at all.

error · conditioning

Named alongside it

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

Companion formCondition numberApproximation before linearisationBackward errorBranch pointCharacteristic polynomialComrade matrixExact ground truthFlop countLinearisationMatrix polynomialRational approximation

All concepts