Course contentsShow
← Mathematics
Lesson 2247 of 3,12146. Linear Algebra — Inner Products and OrthogonalityFree lesson

QR and Least Squares Problems

Using QR decomposition to efficiently solve overdetermined least squares problems without forming normal equations.

QR and Least Squares Problems

What You'll Learn

You'll learn how to solve overdetermined least squares problems efficiently using QR decomposition, bypassing the potential numerical issues of normal equations.

The Challenge with Normal Equations

When solving the least squares problem Ax = b (where A has more rows than columns), we've previously used the normal equations: AᵀAx = Aᵀb. While mathematically correct, forming AᵀA can amplify numerical errors because it roughly squares the condition number of A, making the problem more sensitive to rounding errors.

The QR Approach: A Better Path

If A = QR (where Q has orthonormal columns and R is upper triangular), we can bypass the normal equations entirely.

Here's why this works: The least squares solution minimizes ||Ax - b||. Since Q has orthonormal columns, multiplying by Qᵀ preserves distances (it's an isometry). Therefore:

||Ax - b|| = ||QRx - b|| = ||Rx - Qᵀb||

Now we just need to minimize ||Rx - Qᵀb||, which means solving the simpler triangular system:

Rx = Qᵀb

The Algorithm

  1. Compute the QR decomposition: A = QR
  2. Multiply: c = Qᵀb
  3. Solve the triangular system Rx = c using back-substitution

This avoids forming AᵀA entirely, maintaining better numerical stability while being computationally efficient.

Why It's Better

Think of AᵀA as taking a photograph of a photograph—quality degrades. The QR method works with the "original image" (A itself), preserving accuracy. You get the same mathematical answer but with significantly better numerical behavior, especially when A is ill-conditioned.

Key Takeaway: Using QR decomposition to solve least squares problems (Rx = Qᵀb) is numerically superior to normal equations because it avoids squaring the condition number and works directly with the original matrix structure.