Numerical Linear Algebra
where the algebra stops being the arithmetic
Theme

The thread: Exact ground truth — page 5

Essays 97 to 101 of the 101 on this theme, in the same order.
00.250.50.75100.250.50.751xuexact at ε = 0.005exact at ε(1 + Pe)the upwind answeran exact answer to a different question‖upwind(ε) − central(ε(1+Pe))‖/‖·‖0distance to the problem it solves0.026distance to the problem posed0.36the added diffusion is h/2 = 0.001953, whatever ε isso refining removes it Iterating, instead of factorising

A different equation on every grid

Upwinding is the exact discretisation of a convection–diffusion problem with diffusion ε + h/2, entry for entry, at a relative difference of between 0 and 1.26·10⁻¹⁶ on every mesh from 15 points to 511. The equation it is exact for is chosen by the mesh and not by ε — the added diffusion is 0.01563 on a 31-point grid whether ε is 0.2 or 0.001.

 01020304050607010⁻⁶10⁻³110³10⁶10⁹k‖Aᵏ/k!‖‖e^A‖ = 2.6largest term 1.4·10⁷what the series throws awaylargest term1.4·10⁷‖e^A‖2.6digits cancelled away5.4·10⁶error after the sum5.2·10⁻⁹every term is computed correctlyand the sum has lost seven digits Eigenvalues, singular values, rank

The error the method already knows

Summing the exponential's Taylor series throws away a known number of digits, and the number is on the machine while the sum is being formed. The largest term divided by the answer, times the unit roundoff, tracks the relative error that comes out — to within a factor of nine, across fourteen orders of magnitude of it — and nothing reports it.

 σ14.87σ22.55σ31.08σ40.782σ58.04·10⁻¹⁷σ610⁻¹⁸σ710⁻¹⁸n = 7, and det(A − λB) has degree 4an integer, and a judgementdegree of det(A − λB), exactly4infinite eigenvalues, from the degree3singular values below the cut3largest gap in the spectrum∞a degree cannot be nearly threeand a singular value can be nearly zero Eigenvalues, singular values, rank

The largest gap is inside the null space

The rule recommended for counting a pencil's infinite eigenvalues is to cut at the largest gap in the singular values of B. On integer pencils, with no perturbation anywhere and an exact answer available from the characteristic polynomial, it returns the wrong count on nine of twenty-five — because the singular values that are mathematically zero come back spread over a hundred and forty orders of magnitude, and the largest ratio in the list is between two of them.

 00.7853981.57082.356193.1415900.250.50.751frequency θdamping |g(θ)|the oscillatory half →⅓ — the symmetric optimumno convectionwith convectionits imaginary parta modulus, not a valuesmoothing factor at this ω0.71best over every ω0.71the symmetric operator's, at ω = 2/30.33the imaginary part does not depend on ωso no ω removes it Iterating, instead of factorising

A smoother that stops being one

Weighted Jacobi's smoothing factor on the convection–diffusion operator is a function of the cell Péclet number and nothing else — identical to eight digits at five grid sizes at matched Pe. It is 0.3335 at Pe = 0.016, exactly 1/√2 at Pe = 1, and 5.2190 at Pe = 7.8, where the sweep amplifies the modes it exists to remove.

 22.32.62.910⁻⁴10⁻³10⁻²10⁻¹1log₁₀ numbers storeddistance to the dominant eigenvalueArnoldi, linearisedprojected quadraticper number heldstorage, linearised832storage, second-order416Ritz values, linearised26Ritz values, second-order52half the storageand twice the approximations Iterating, instead of factorising

The answer that arrives when the space runs out

A second-order Krylov recurrence holds vectors of length n for a problem with 2n eigenvalues, so it is exact at n steps where the linearised route needs 2n. The machine-precision reading at forty-four vectors on a chain of forty is that exhaustion rather than convergence, and it arrives through a basis whose ‖QᵀQ − I‖ is above one.

All themes