Linear Algebra and QR Factorization - Introduction to Scientific Computing

Linear Systems¶

Consider a system of $n$ equations in $n$ unknowns:

\begin{aligned} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n &= b_1 \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n &= b_2 \\ &\vdots \\ a_{n1}x_1 + a_{n2}x_2 + \cdots + a_{nn}x_n &= b_n \end{aligned}

In matrix form: $A\mathbf{x} = \mathbf{b}$ where $A \in \mathbb{R}^{n \times n}$ , and $\mathbf{x}, \mathbf{b} \in \mathbb{R}^n$ .

The Fundamental Theorem of Linear Algebra¶

Matrix Factorizations: The Key to Solving Linear Systems¶

The naive approach to solving $A\mathbf{x} = \mathbf{b}$ is to compute $A^{-1}$ and then $\mathbf{x} = A^{-1}\mathbf{b}$ . This is a bad idea:

Computing $A^{-1}$ is expensive ( $O(n^3)$ operations)
It’s numerically less stable than alternatives
It doesn’t exploit structure

Instead, we factorize the matrix: write $A$ as a product of simpler matrices that are easy to invert or solve with.

Why Factorizations?¶

Solve efficiently: Triangular systems are cheap ( $O(n^2)$ )
Reuse work: Once factored, solve for multiple right-hand sides cheaply
Reveal structure: Factorizations expose rank, conditioning, eigenvalues

The Big Three Factorizations¶

Factorization	Form	Best For
LU	$A = PLU$	Square systems, multiple RHS
QR	$A = QR$	Least squares, stability
SVD	$A = U\Sigma V^T$	Rank-deficient problems, analysis

This chapter focuses on QR, which handles rectangular matrices and least squares problems where LU doesn’t apply.

Learning Outcomes¶

After completing this chapter, you should be able to:

L4.1: State the fundamental theorem of linear algebra.
L4.2: Define and compute vector and matrix norms.
L4.3: Define condition number and explain its significance.
L4.4: Define orthogonality and compute inner products.
L4.5: State the best approximation theorem.
L4.6: Describe Gram-Schmidt and its instability.
L4.7: Explain Householder reflections.
L4.8: Write the QR factorization (full and reduced).
L4.9: Derive the normal equations.
L4.10: Explain why $\kappa(A^T A) = \kappa(A)^2$ .
L4.11: Solve least squares using QR.
L4.12: Compare normal equations vs QR stability.