Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Wilkinson polynomial — where it appears

The polynomial whose roots are the integers one to twenty, written out in its monomial coefficients. Wilkinson showed that changing one coefficient by about one part in two billion moves ten of the roots into the complex plane, which made it the standard example of roots badly determined by their coefficients.

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

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 612182430364210⁻¹⁶10⁻¹⁴10⁻¹²10⁻¹⁰10⁻⁸10⁻⁶10⁻⁴10⁻²1degree nworst relative root errormonomial, integersmonomial, Chebyshev pointsChebyshev, integersChebyshev, Chebyshev pointsred: monomial; blue and green: Chebyshevthe basis has to match the roots

A basis that has to know where the roots are

Wilkinson's polynomial loses its roots in the third figure at degree twenty when they are computed from its monomial coefficients, and the repair offered was to change the basis: in Chebyshev coefficients, with the colleague matrix, the conditioning 'does not degrade exponentially with degree'. Expanded exactly in that basis and rounded once, the integers' roots come back ten orders better at degree twenty — 4.4·10⁻¹³ against 7.6·10⁻³ — and still degrade exponentially, at a third of a decade a degree, to 2.8·10⁻⁴ at forty. Place the same number of roots at the interval's Chebyshev points instead and they stay at 10⁻¹⁴ at every degree, while the monomial route loses them as fast as the integers. The basis does not repair the problem; it has to match where the roots are.

error · Conditioning

Named alongside it

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

Backward errorCharacteristic polynomialChebyshev basisCompanion formCondition numberExact ground truthMatrix polynomialRepresentable numbersRunge phenomenon

All concepts