You solve a linear system whose matrix has condition number 10^8 in IEEE double precision. How many correct significant digits should you expect in the solution, and what changes if you form the normal equations A^T A x = A^T b instead of using a QR factorisation of A?

You solve a linear system whose matrix has condition number 10^8 in IEEE double precision. How many correct significant digits should you expect in the solution, and what changes if you form the normal equations A^T A x = A^T b instead of using a QR factorisation of A?

Approach: Combine the machine epsilon of double precision with the relative error amplification given by the condition number, then track what squaring the condition number does to that budget.

About 8 correct significant digits with a stable solver, and about none left if you form the normal equations. Double precision has machine epsilon 2.2e-16, so roughly 16 digits. A backward stable solver returns the exact answer to a perturbed problem of relative size epsilon, and the condition number amplifies that to a relative error near kappa * epsilon = 10^8 * 10^{-16} = 10^{-8}, which is 8 correct digits. The normal equations square the conditioning, kappa(A^T A) = kappa(A)^2 = 10^16, so the error estimate becomes of order one and no correct digits survive. A QR factorisation of A works with kappa(A) directly and keeps the 8 digits, at about twice the flop count of the normal equations, which is the standard trade for a least squares problem on close to collinear factors.

Follow-up: A factor matrix has two nearly identical columns. What does ridge regularisation with penalty lambda do to the condition number, and how large must lambda be to buy back four digits?

Key concepts: condition number, machine epsilon, normal equations, qr factorisation.