Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Runge phenomenon — where it appears

The growth of a polynomial interpolant's error near the ends of an interval as its degree rises on equally spaced points. Their Lebesgue constant grows exponentially, so adding points makes the fit worse; Chebyshev points, clustered toward the ends, remove the growth.

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

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 124816equispaced points, σ = 0.01generalised cross-validationleave-one-outinformation criteriondiscrepancy principleChebyshev points, σ = 0.01generalised cross-validationleave-one-outinformation criteriondiscrepancy principleequispaced points, σ = 10⁻⁴generalised cross-validationleave-one-outinformation criteriondiscrepancy principleChebyshev points, σ = 10⁻⁴generalised cross-validationleave-one-outinformation criteriondiscrepancy principleequispaced points, σ = 10⁻⁶generalised cross-validationleave-one-outinformation criteriondiscrepancy principleChebyshev points, σ = 10⁻⁶generalised cross-validationleave-one-outinformation criteriondiscrepancy principleerror of the rule's degree over the best degree'sred: leave-one-out · logarithmic, cut at 16the points, not the rule

Chebyshev points make the two rules one

On 200 equispaced points leave-one-out cross-validation stopped a fit to |x| at degree 26, where the best was 120, because the end points' leverage had reached one and the score divides by what is left. On Chebyshev points the largest leverage stays at twice the average, and leave-one-out was predicted to follow the best degree to within five and cost within ten per cent. At small noise it lands on the best degree on the median draw at no cost at all; at one per cent it is six degrees off and within 1.06, which is as close as any rule gets there. What the prediction did not say is that it stops being a different rule: on Chebyshev points leave-one-out and generalised cross-validation choose the same degree on 86 to 100 draws in a hundred. And the earlier defence of the equispaced stop — that degree 26 was the honest degree for the ends — does not survive measuring the ends: there it costs the end points a thousand times the best they could have.

leastsquares · Fitting

Named alongside it

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

Backward errorCharacteristic polynomialChebyshev basisCompanion formCondition numberCross-validationExact ground truthGeneralised cross-validationInterpolationLeast squaresLeverageOrthonormal basis

All concepts