Questions: Numerical Least Squares

Question 1

A numerical analyst uses the normal equations A^T A x = A^T b to solve a least squares problem. She checks and finds that A has condition number κ(A) = 10^6. What condition number should she expect for A^T A?

• A. 10^6 — the condition number does not change when forming A^T A
• B. 10^3 — the square root, because the matrix is now symmetric
• C. 10^12 — the condition number squares
• D. It depends on the specific values in A

Answer: (C)

κ(A^T A) = κ(A)^2, so a condition number of 10^6 becomes 10^12. In double precision arithmetic (which gives about 16 significant digits), a condition number of 10^12 means you lose 12 digits of accuracy — leaving only 4 reliable digits in the solution. This squaring of the condition number is the fundamental numerical hazard of the normal equations approach, and why QR decomposition is preferred for ill-conditioned problems.

Question 2

Why is QR decomposition preferred over normal equations for numerically solving least squares problems?

• A. QR is always faster, making it preferred for large problems
• B. QR avoids forming A^T A, so the condition number is not squared; orthogonal transformations preserve lengths and the problem reduces to a triangular solve
• C. QR finds the exact solution to Ax = b, while normal equations only approximate it
• D. QR is preferred only when A is square; for overdetermined systems, normal equations are still best

Answer: (B)

The key advantage of QR is numerical stability: factoring A = QR and solving Rx = Q^T b never forms A^T A, so the condition number remains κ(A) rather than κ(A)^2. Since Q is orthogonal, multiplying by Q^T is a rotation/reflection that preserves vector lengths. Both methods find the same least squares solution; QR just computes it more accurately when A is ill-conditioned. Option A is false (QR is often slower than forming normal equations for tall matrices); option D reverses the reality.

Question 3

The normal equations usually give an accurate least squares solution as long as A has full column rank.

• T. True
• F. False

Answer: False

Full column rank guarantees A^T A is invertible and a unique solution exists, but it does not guarantee numerical accuracy. If A has a large condition number, forming A^T A squares it, amplifying rounding errors far beyond what QR would produce. The issue is purely numerical: even when the mathematical problem is well-defined, the normal equations approach can produce a computed solution far from the true solution due to floating-point error accumulation.

Question 4

SVD provides the minimum-norm least squares solution when A is rank-deficient (has linearly dependent columns).

• T. True
• F. False

Answer: True

When A is rank-deficient, the least squares problem has infinitely many solutions. SVD via the pseudoinverse x* = V Σ^+ U^T b selects the one with minimum 2-norm among all solutions that minimize ‖Ax − b‖². Setting near-zero singular values' reciprocals to zero also regularizes the solution, preventing it from blowing up due to numerical rank deficiency. This is what makes SVD the most complete tool for least squares, especially in rank-deficient or near-rank-deficient cases.

Question 5

Explain why the condition number of A^T A matters for the accuracy of the least squares solution, and describe a numerically stable alternative to using the normal equations.

Model answer: Solving the normal equations requires inverting (or factoring) A^T A, and accuracy degrades proportionally to its condition number. Since κ(A^T A) = κ(A)^2, a moderately ill-conditioned A can produce a disastrously ill-conditioned normal equations system, wiping out many digits of accuracy. QR decomposition avoids this: it factors A = QR directly, reducing the problem to solving Rx = Q^T b. Because Q is orthogonal (length-preserving), this transformation does not amplify errors, and the condition number of the triangular system R is κ(A), not κ(A)^2.

The condition number measures how much a small change in input amplifies into a change in output. For a system with condition number κ, you lose approximately log_10(κ) digits of accuracy. Squaring the condition number doubles the digit loss — catastrophic for even mildly ill-conditioned problems. QR via Householder reflections is the standard workhorse for least squares in numerical software (LAPACK's dgelsd uses QR or SVD depending on rank), precisely because it avoids this squaring.