Skip to content
0.46 -1.1 1.5 -0.47 0.2 -0.18 1.9 0.69 0.42 -0.16 0.028 -0.016 0 -1.5 0.16 0.88 0.099 -0.11 0 0.68 0.76 2.3 0.93 0.048 0 -0.25 0.11 0.95 2.1 1.5 0 0 0 0 1.5 2.3 after reflector 2 the highlighted entries are the bulge — the only thing that is not Hessenberg entries below the subdiagonal 3 reflectors used 2 reflectors in a whole step 5 the shifts are never formed — only their sum and product and both of those are real
Francis
1
Two shifts that are never formed
1 essay · spectra
condition numbers, on a logarithmic scale κ(P) 5.66·10¹⁸ κ(Q) 5.71·10¹⁸ √(κ(P)κ(Q)) — the SVD route 5.68·10¹⁸ κ(P)κ(Q) — the product route 3.23·10³⁷ 1/u 4.5·10¹⁵ the mean, or the product and only one of them fits
Gramian conditioning
1
A condition number that is not the model's
1 essay · reduction
-4 -2.35371 -0.707429 0.938857 2.58514 4.23143 5.87771 0 2 4 6 8 10 12 14 shift σ ν(σ) an answer that is an integer shifts 2000 disagreements 0 eigenvalues 14 steps 14 the marks are a Jacobi decomposition and the staircase never saw one
Inertia
1
An eigenvalue count that cannot be slightly wrong
1 essay · spectra
everything Ax can reach b = (1.1, 0.4, 1.5) Ax, the closest point r = b − Ax ‖Aᵀr‖ / (‖A‖‖r‖) 1.7·10⁻¹⁶ ‖b‖² − ‖Ax‖² − ‖r‖² 1.3·10⁻¹⁵ ‖r‖ 1.3 200 random nearby points of the plane were tried; none is closer. a 3×2 system, Householder QR perpendicularity is checked
Least squares
1
The projection and the right angle
1 essay · leastsquares
10⁻¹⁷ 10⁻¹⁵ 10⁻¹³ 10⁻¹¹ 10⁻⁹ 10⁻⁷ 10⁻⁵ 10⁻³ 10⁻¹ 10⁻¹⁴ 10⁻¹² 10⁻¹⁰ 10⁻⁸ 10⁻⁶ 10⁻⁴ 10⁻² 1 ε relative error in J(x)v forward central cancellation truncation against a derivative that is exact forward floor 1.3·10⁻¹⁰ central floor 1.1·10⁻¹² truncation slope, forward 1 truncation slope, central 2 no ε reaches the roundoff and the analytic derivative is free of the choice
Matrix-free
1
An operator with no entries
1 essay · iterative
10⁻⁸ 10⁻⁷ 10⁻⁶ 10⁻⁵ 10⁻⁴ 10⁻³ 10⁻² 10⁻¹ 10⁻⁹ 10⁻⁷ 10⁻⁵ 10⁻³ 10⁻¹ 10¹ ε in Läuchli's matrix (smaller ε, larger κ) relative error in the coefficients AᵀA exactly singular normal equations QR κ from 1.7·10⁸ to 17 the cliff is at √u = 2.4·10⁻⁴
Normal equations
2
The road that squares the problem
1 essay · leastsquares
3 0 0 0 0 0 0 1 2 0 0 0 0 -2 1 0 0 0 0 0 0 -0.5 -1.5 0 0 0 0 1.5 -0.5 0 0 0 0 0 0 -2 T = ZᵀAZ the highlighted boxes each hold one conjugate pair, and no real rotation removes them the form, and that it is one ‖A − ZTZᵀ‖/‖A‖ 1.8·10⁻¹⁵ ‖ZᵀZ − I‖ 2.5·10⁻¹⁵ worst eigenvalue error 2.7·10⁻¹⁵ surviving subdiagonal 2 6×6, spectrum chosen before the matrix was built quasi-triangular is as far as the reals go
Real schur
1
The form a real matrix can reach
1 essay · spectra
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 10⁻¹⁶ 10⁻¹³ 10⁻¹⁰ 10⁻⁷ 10⁻⁴ 10⁻¹ decay rate of the spectrum relative spread of the rank-k error the seed the machine two kinds of variation seeds drawn 8 partitionings 7 seed spread 0.31 machine spread 9.8·10⁻¹⁶ ratio 3.1·10¹⁴ one of these is recorded and it is the large one
Run-to-run variation
1
The variation that comes with a seed
1 essay · machine
-1 0 1 2 3 4 5 6 7 8 9 -1 0 1 λ branch point at −0.4 the closed form which of these is an answer eigenvalues returned 36 wanted 6 past the branch point 6 complex 24 worst against the closed form 7.7·10⁻⁴ all of them exact for a problem nobody asked
Spurious spectrum
1
The eigenvalues that are answers to nothing
1 essay · polynomial
0 150 300 450 600 750 900 10⁻¹³ 10⁻¹¹ 10⁻⁹ 10⁻⁷ 10⁻⁵ 10⁻³ 10⁻¹ iteration ‖r‖ / ‖b‖ Jacobi Gauss–Seidel SOR ω=1.78 closed form vs measured ρ Jacobi, exact 0.99 ρ measured 0.99 ρ Gauss–Seidel, exact 0.98 1D Laplacian, n = 24 ω optimal = 1.777
Stationary
1
A rate that is known in advance
1 essay · iterative
-5 -3.20611 -1.41221 0.381678 2.17557 3.96946 0 log₁₀ |λ| |λ| = 1 λλ′ = 1, in the algebra pairs 6 decades of spectrum 9.6 pairing error, general 3.3·10⁻⁹ pairing error, structured 2.2·10⁻¹⁶ a symmetry the solver never knew about and the half of the answer it decides
Structured spectrum
1
A spectrum that comes in reciprocal pairs
1 essay · polynomial
1 2 3 4 5 6 7 8 9 10⁻¹⁰ 10⁻⁸ 10⁻⁶ 10⁻⁴ 10⁻² 1 rank k of the approximation ‖A − Aₖ‖ measured, 2-norm σₖ₊₁, from theory measured, Frobenius the first two agree to 4.3·10⁻⁹ worst |‖A−Aₖ‖₂ − σₖ₊₁| / σₖ₊₁ 4.3·10⁻⁹ worst Frobenius discrepancy 4.3·10⁻⁹ κ = 10⁹; 30 random rank-3 matrices, none closer the error is σₖ₊₁
SVD
2
The best approximation there is
1 essay · spectra
1 10¹ 0 0.3 0.6 0.9 1.2 trust-region radius Δ share of the exact model decrease the exact subproblem 7 radii, n = 60 share at the smallest radius 0.95 share at the largest 0.3 products, at most 8 radii stopped by the curvature 4 a few products against an eigendecomposition and most of the decrease
Trust-region
1
The certificate that arrives soonest is worth least
1 essay · iterative
All essays