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

Solving Linear Systems Using QR

Applying QR decomposition to solve Ax = b by transforming it to the easier system Rx = Q^T b.

Solving Linear Systems Using QR

What You'll Learn

You'll learn how to solve the linear system Ax = b efficiently by using QR decomposition to transform it into a simpler triangular system.

The Core Idea

When you have a square, invertible matrix A, you can decompose it as A = QR where Q is orthogonal and R is upper triangular. This transforms your original problem into something much easier to solve.

Here's how it works:

Starting with Ax = b, substitute the QR decomposition:

QRx = b

Since Q is orthogonal, Q^T Q = I. Multiply both sides by Q^T:

Q^T QRx = Q^T b

This simplifies to:

Rx = Q^T b

Now you have an upper triangular system! Upper triangular systems are trivial to solve using back substitution — you start from the bottom row and work your way up.

Why This Matters

Think of it like converting a tough lock into an easier one. Instead of solving Ax = b directly (which might require Gaussian elimination), you:

  1. Compute Q^T b (just matrix-vector multiplication)
  2. Solve Rx = Q^T b by back substitution (fast and stable)

This approach is particularly valuable because:

  • It's numerically stable
  • It leverages the structure you've already computed (the QR decomposition)
  • Back substitution on triangular systems is computationally cheap

The Algorithm

  1. Decompose A = QR using Gram-Schmidt
  2. Compute c = Q^T b
  3. Solve Rx = c by back substitution

Key Takeaway: QR decomposition transforms Ax = b into the triangular system Rx = Q^T b, which you solve efficiently using back substitution, providing a numerically stable alternative to Gaussian elimination.