Skip to main content
Home

Linear Systems Solvers

Choose a solver below

Solving Systems

Decompositions

Vector Spaces

Need Help?

Check the educational content below each solver for detailed explanations.

View all tutorials →
Calculating...
Home Linear Systems Qr_Decomposition

QR Decomposition Calculator: Gram-Schmidt Orthogonalization

Perform QR Decomposition of a matrix A into orthogonal matrix Q and upper triangular matrix R: A = QR. Optionally solve the linear system Ax = b using the QR factorization.

Calculator

Enter your matrix below and click "Calculate" to see the step-by-step solution.

Rows (m) =
Cols (n) =
Maximum size: 6×6

QR decomposition works for any m×n matrix with full column rank

A Matrix A (m × n)

b Constant Vector b (Optional)

Performing Gram-Schmidt orthogonalization...

Enter a matrix A to compute its QR decomposition A = QR.

Optionally provide vector b to solve the system Ax = b.

Learn About Qr_Decomposition

Understanding the concepts behind the calculations.

📑 Quick Navigation

What is QR Decomposition?

QR decomposition (or QR factorization) factors a matrix A into the product of an orthogonal matrix Q and an upper triangular matrix R:

$$ \boxed{A = QR} $$

Where:

  • Q is an m×n matrix with orthonormal columns (QᵀQ = I)
  • R is an n×n upper triangular matrix (all entries below diagonal are zero)

Key Insight: QR decomposition orthogonalizes the columns of A, transforming them into a set of orthonormal basis vectors. This is the foundation of many numerical algorithms.

Visual Representation

$$ A_{m \times n} = Q_{m \times n} \cdot R_{n \times n} = \begin{bmatrix} | & | & & | \\ q_1 & q_2 & \cdots & q_n \\ | & | & & | \end{bmatrix} \begin{bmatrix} r_{11} & r_{12} & \cdots & r_{1n} \\ 0 & r_{22} & \cdots & r_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & r_{nn} \end{bmatrix} $$

The Gram-Schmidt Process

The most common method for computing QR decomposition is the Gram-Schmidt orthogonalization process. For a matrix A = [a₁, a₂, ..., aₙ]:

Step 1: Orthogonalization

For each column j, subtract its projections onto all previous orthogonal vectors:

$$ u_j = a_j - \sum_{i=1}^{j-1} \frac{a_j \cdot u_i}{u_i \cdot u_i} u_i $$

Step 2: Normalization

Convert orthogonal vectors to orthonormal by dividing by their length:

$$ q_j = \frac{u_j}{\|u_j\|} $$

Step 3: Build R Matrix

The entries of R come from the projections:

$$ r_{ij} = q_i \cdot a_j \quad \text{for } i \le j, \qquad r_{ij} = 0 \quad \text{for } i > j $$

💡 Intuition: Think of Gram-Schmidt as progressively "stripping away" components of previous vectors, leaving only the new orthogonal direction.

Complete Example

Problem: Find QR decomposition of A = [[1, 1, 0], [1, 0, 1], [0, 1, 1]]

Step 1: First column

$$ u_1 = a_1 = \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}, \quad \|u_1\| = \sqrt{1^2 + 1^2 + 0^2} = \sqrt{2}, \quad q_1 = \frac{u_1}{\|u_1\|} = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} $$

Step 2: Second column

$$ u_2 = a_2 - (a_2 \cdot q_1)q_1 = \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} - \left(\frac{1}{\sqrt{2}}\right)\frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 0.5 \\ -0.5 \\ 1 \end{bmatrix} $$
$$ \|u_2\| = \sqrt{0.5^2 + (-0.5)^2 + 1^2} = \sqrt{1.5} = \frac{\sqrt{6}}{2}, \quad q_2 = \frac{u_2}{\|u_2\|} = \frac{1}{\sqrt{6}}\begin{bmatrix} 1 \\ -1 \\ 2 \end{bmatrix} $$

Step 3: Third column

$$ u_3 = a_3 - (a_3 \cdot q_1)q_1 - (a_3 \cdot q_2)q_2 = \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix} - \frac{1}{\sqrt{2}}q_1 - \frac{1}{\sqrt{6}}q_2 = \begin{bmatrix} -\frac{2}{3} \\ \frac{1}{3} \\ \frac{1}{3} \end{bmatrix} $$

Step 4: Build R

$$ R = \begin{bmatrix} q_1 \cdot a_1 & q_1 \cdot a_2 & q_1 \cdot a_3 \\ 0 & q_2 \cdot a_2 & q_2 \cdot a_3 \\ 0 & 0 & q_3 \cdot a_3 \end{bmatrix} = \begin{bmatrix} \sqrt{2} & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ 0 & \frac{\sqrt{6}}{2} & \frac{1}{\sqrt{6}} \\ 0 & 0 & \frac{2}{\sqrt{3}} \end{bmatrix} $$

✓ Verification: A = QR — multiply Q and R to confirm you recover the original matrix!

Solving Systems with QR

QR decomposition provides an efficient way to solve linear systems, especially when A is not square:

For Square Systems (Ax = b)

  1. Decompose: A = QR
  2. Multiply both sides by Qᵀ: QᵀAx = Qᵀb → Rx = Qᵀb (since QᵀQ = I)
  3. Back substitute to solve the upper triangular system Rx = Qᵀb

For Overdetermined Systems (Least Squares)

When solving Ax = b with more equations than unknowns, QR gives the least squares solution:

$$ x = R^{-1}Q^Tb $$

This minimizes ‖Ax - b‖₂ (the sum of squared errors).

Why QR for least squares? Unlike normal equations (AᵀAx = Aᵀb), QR doesn't square the condition number, making it more stable for ill-conditioned problems.

Applications

📊 Least Squares Regression

Finding the best-fit line/curve when data exceeds parameters. QR is the preferred numerical method.

📈 Principal Component Analysis (PCA)

QR is used in the first step of many PCA algorithms for dimensionality reduction.

🔢 QR Algorithm for Eigenvalues

The most widely used algorithm for computing all eigenvalues of a matrix (Francis 1959-1961).

📡 Signal Processing

Adaptive filtering, subspace tracking, and array processing applications.

🔄 Recursive Least Squares

QR updates for real-time parameter estimation in control systems.

🔬 Scientific Computing

Solving linear systems, computing matrix ranks, and orthonormal bases.

QR vs LU: Which to Use?

Feature QR Decomposition LU Decomposition
Numerical Stability ✓ Very stable (even without pivoting) Requires pivoting
Non-square matrices ✓ Works for m×n (any shape) ✗ Requires square matrices
Orthogonal Q ✓ QᵀQ = I (preserves length) ✗ No orthogonal factor
Best for Least squares, eigenvalues, ill-conditioned problems Solving square systems, multiple right-hand sides
Computational cost (n×n) ≈ 2n³/3 operations ≈ 2n³/3 operations

Recommendation: Use QR for least squares and ill-conditioned problems. Use LU for solving multiple square systems with the same A (more efficient when factoring once).

Variants & Numerical Stability

Three Main Algorithms

  • Classical Gram-Schmidt (CGS) - Simple but numerically unstable (loses orthogonality)
  • Modified Gram-Schmidt (MGS) - More stable, standard for small to medium matrices
  • Householder Reflections - Most stable, preferred for large or ill-conditioned matrices
  • Givens Rotations - Good for sparse matrices or when updating QR

Stability Comparison

$$ \text{Normal equations: } \kappa(A^TA) = \kappa(A)^2 \quad \text{(bad!)} $$ $$ \text{QR: } \kappa(R) = \kappa(A) \quad \text{(good!)} $$

This means QR preserves the condition number, while normal equations square it—potentially causing catastrophic rounding errors.

⚠️ Warning: For very ill-conditioned matrices (κ(A) > 10¹⁰), even QR may struggle. Consider using SVD or specialized algorithms.

Frequently Asked Questions

Q: Is QR decomposition unique?

A: For full-rank matrices, Q and R are unique if we require positive diagonal entries in R. Otherwise, signs can vary (multiplying Q by -1 and R by -1 gives another decomposition).

Q: Why is QR better than normal equations for least squares?

A: Normal equations compute AᵀA, which squares the condition number, causing loss of precision. QR avoids this by working directly with A.

Q: Can QR handle rank-deficient matrices?

A: Basic QR assumes full column rank. For rank-deficient matrices, use QR with column pivoting or SVD instead.

Q: How does QR compare to SVD?

A: SVD is more general (handles rank deficiency, gives singular values) but slower. QR is faster and sufficient for most least squares problems.

Q: Why is Q orthogonal?

A: Orthogonality preserves vector lengths (‖Qx‖ = ‖x‖). This is crucial for numerical stability and geometric interpretations.

Try It Yourself!

Use the calculator above to compute QR decompositions:

  1. Enter your matrix A (up to 4×4)
  2. Click "Calculate" to see:
    • The orthogonal matrix Q (with orthonormal columns)
    • The upper triangular matrix R
    • Verification that A = QR
    • Step-by-step Gram-Schmidt process

📐 Try these examples:

  • 2×2: [[3, 1], [1, 2]] - Simple QR decomposition
  • 3×3: [[1, 1, 0], [1, 0, 1], [0, 1, 1]] - The example from this guide
  • Rectangular (overdetermined): [[1, 1], [1, 2], [1, 3]] - Watch Q be m×n!

💡 Pro Tip: For least squares problems, QR is the gold standard. Use it instead of normal equations for better numerical accuracy!