Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Eigenvalue condition number — where it appears

The reciprocal of the inner product of an eigenvalue's left and right eigenvectors, which is one for a normal matrix and unbounded for a defective one. It is computable from a pair of eigenvectors, it is one for a normal matrix, and it is what turns a rounding-level perturbation into a hundredth of a unit of movement.

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

110¹10²10³110¹10²10³off-diagonal entry ccondition number of the eigenvalue√(1 + c²)decoupled: 1measuredthree routes, one number‖A − ZTZᵀ‖/‖A‖1.7·10⁻¹⁵closed form100computed 1/|yᵀx|100worst measured movement46four eigenvalues, two conditioning numbersthe symmetric case has one, and it is 1

A condition number for one eigenvalue

In the symmetric case every eigenvalue has condition number exactly one. In this four-by-four matrix two of them have condition number 100.005 and the other two have exactly 1, and the number belongs to the eigenvalue rather than to the matrix.

spectra · Eigen conditioning darker is smaller: 10⁻¹⁰, 10⁻⁶, 10⁻³, 10⁻¹one spectrum, two matricesspectral radius0.8reach of the 10⁻³ level1.3eigenvalues, all at0.8the circle is |z| = 1and every eigenvalue is well inside it

The eigenvalues that are not there

For a normal matrix the resolvent norm is exactly one over the distance to the nearest eigenvalue, so a picture of it carries nothing the spectrum did not. Move one entry above the diagonal and the region a perturbation of 10⁻⁸ can put an eigenvalue into stops being a disc and reaches out past the unit circle, while every eigenvalue stays at 0.8.

spectra · Non-normality largest eigenvalue erroras given, order 960.043balanced, order 964.4·10⁻⁴symmetrised, order 962.2·10⁻¹²016324864809611210⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹order nlargest |computed − exact| eigenvaluean error of one: the integers are no longer told apartas givenbalancedsymmetrisedopen dots: complex pairs returned for a real spectrumevery entry is an integer, stored exactly

Balanced is not symmetric

The Sylvester–Kac matrix is made of small integers, so a double holds it exactly, and its eigenvalues are the integers from −(n − 1) to n − 1 in steps of two. Every digit an eigensolver loses on it is therefore the solver's own, and it loses them at exactly the rate first-order perturbation theory predicts: the median error is half the prediction across 1,568 eigenvalues. Balancing, the preprocessing libraries apply for this kind of matrix, divides every condition number by about sixty and leaves their growth untouched, and at order 112 the unbalanced solver returns eighteen complex eigenvalues for a spectrum of integers.

error · Exact ground truth 10¹10⁴10⁷10¹⁰10¹³10¹⁶10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹κ(B)relative error, and asymmetryvia B⁻¹Avia Choleskyasymmetry of B⁻¹Au · κ(B)against a spectrum known exactlyslope, via B⁻¹A0.92slope, via Cholesky0.98worst ratio between them2.3asymmetry of B⁻¹A1.1the symmetry claim is trueand it is not about the accuracy

Two matrices and one problem

Ax = λBx is what a finite element model, a structural vibration and a constrained optimisation actually produce, and it is not the one-matrix problem with a change of variables. Everybody is told not to form B⁻¹A because it is not symmetric. That is true, the departure from symmetry is about one, and it is not what decides the accuracy.

spectra · Pencil

Named alongside it

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

Non-normalityCondition numberOrthogonalityPerturbationPseudospectrumBackward errorCholeskyDeparture from normalityEigenvaluesExact ground truthFrancis's double shiftGeneralised eigenvalue problem

All concepts