PHYSICS · Multi-part · Fermi University Physics · Mathematical Methods for Physics · Numerical and computational mathematics · Numerical and computational mathematics
Error, Chance and the Machine, Ch Linear systems, least squares and the singular value decomposition
Problem
A dense 100×100 system Ax=b, with condition number κ(A)=500, is solved in binary64 by LU factorisation with partial pivoting. The observed growth factor is ρ100=8.
((a)) The bound Eq. (2.5), η≤cnρnu, carries a factor cn that the random matrices of order 60 in Section 2.2 showed to be pessimistic: their growth factors were near 4 and their backward errors within a small multiple of u. Taking the working estimate η∼ρnu, estimate the relative backward error η of the computed LU solution, and say by what factor the bound itself, with c=1, exceeds it.
((b)) Using the forward-error bound of Chapter 1 (forward error ≲κ(A)× backward error), estimate the relative forward error in the computed solution x.
((c)) A design matrix with the same condition number κ=500 is used to fit a small-residual least-squares problem, once by QR and once by forming and solving the normal equations, both in binary64. State the forward-error bound for each method and evaluate it numerically.
((d)) Rank the three computed results (LU solve, QR least squares, normal-equations least squares) from most to least accurate. Say which gap in the ranking is decisive and which lies within the constants the estimates drop, and why the decisive one follows the power of κ each method carries.