Checkpoint: Linear Systems in Practice

By Better Wise

Quiz

You solve a least-squares problem with Householder QR and separately with the normal equations plus Cholesky. In exact arithmetic both give the same answer. What is the dominant difference in the computed solution when κ(A) = 10^8 in double precision?
- QR error is about ε·κ(A) ≈ 10^-8, while the normal-equations error is about ε·κ(A)^2 ≈ 1, so the normal-equations route loses essentially all digits.
- Cholesky is always more accurate because it exploits symmetry, so the normal-equations route has error about ε·κ(A)/2.
- Both routes have error about ε·κ(A) because both are backward stable, so the choice is purely about flop count.
- QR error is about ε·κ(A)^2 because Householder reflectors square the condition number, while the normal equations keep ε·κ(A).
A Cholesky factorization of a matrix you believe is SPD hits a negative pivot partway through. What is the correct interpretation and response?
- Switch to the normal equations, which are guaranteed to be positive definite in floating point.
- The input is not numerically positive definite; the matrix formation or the problem is wrong, so investigate or add jitter/ridge rather than forcing the factor.
- Take the absolute value of the pivot and continue; the resulting factor is still valid for the intended problem.
- This is normal roundoff and can be ignored as long as the final residual is small.
Which statements about the SVD-based pseudoinverse and truncation are correct? Select all that apply.
- The Frobenius reconstruction error of a rank-k truncation is the sum of the discarded singular values, not their squares.
- Singular values below roughly σ_max · max(m,n) · ε are float noise, so truncating there is bug avoidance rather than regularization.
- For a smooth power-law spectrum there is a unique correct truncation rank that the spectrum determines.
- The truncated SVD A_k is the optimal rank-k approximation in both Frobenius and spectral norm (Eckart-Young).
- x = A^+ b is the minimum-norm least-squares solution: it minimizes ||Ax − b|| and, among minimizers, minimizes ||x||.
Which statements about conditioning and ill-posed problems are correct? Select all that apply.
- κ_2(A) = σ_max/σ_min bounds the worst-case relative error amplification: ||δx||/||x|| ≤ κ(A)·||δb||/||b||.
- The condition number is scale invariant, so row and column equilibration cannot improve accuracy.
- A tiny residual does not imply a small error; the gap between residual and error is governed by κ.
- Discrete ill-posed problems typically violate continuous dependence on the data, with singular values decaying smoothly to the noise floor and no spectral gap.
- The Picard condition requires |u_i^T b| to decay slower than σ_i so the ratios grow.
Forming the normal equations replaces the condition number κ(A) with ____, which is why their accuracy degrades quadratically.
Tikhonov filter factors are f_i = ____, which tend to 1 for modes above λ and to 0 below it.
A defensible default tolerance for deciding whether a singular value is numerically nonzero is τ = σ_max · max(m,n) · ____, where ____ is the machine epsilon of the working precision.
You have a least-squares problem with m = 10^5, n = 10^3, and κ(A) = 10^3 in double precision. Explain which factorization you would pick, justify it with the error and flop estimates, and state what you would check afterward.
You are regularizing a discrete ill-posed problem with Tikhonov. Describe how you would choose λ, how you would sanity-check the result, and how you would report it.
You are given a matrix whose log singular value spectrum shows a clear gap: σ_k/σ_{k+1} ≈ 10^4. Explain how you would use the SVD to solve a least-squares problem with it, what you would report, and what could go wrong in code.