Why Gram-Schmidt isn't enough
In Volume I you built QR with the Gram-Schmidt process: orthogonalize the columns of A one at a time to get an orthogonal Q, with the projection coefficients forming the upper-triangular R. Mathematically perfect; numerically fragile. In finite precision, each subtraction leaks a little error, and the computed Q columns slowly drift out of orthogonality — exactly when columns are nearly dependent and you need accuracy most.
The professional QR decomposition flips the strategy. Instead of *building* orthogonal columns and hoping they stay orthogonal, it *applies* a sequence of operations that are exactly orthogonal — reflections and rotations — to grind A down to triangular form. Orthogonality is then a property of the tools, not a fragile output. The two tools are the Householder reflection and the Givens rotation.
Householder: zero a whole column in one shot
A Householder reflection is the mirror map H = I - 2 v v^T / (v^T v). It reflects every vector across the hyperplane perpendicular to v, and it is symmetric and orthogonal by construction (H^T H = I, H = H^T). The trick: given a column x, choose v so that reflecting x lands it exactly on a coordinate axis — i.e. Hx = (-/+ ||x||, 0, 0, ..., 0). One reflection annihilates an entire column below the diagonal at once.
# Goal: zero everything below the first entry of x = (3, 4)^T. # ||x|| = 5. Pick the sign to avoid cancellation: target = (-5, 0)^T. x = [ 3 ; 4 ] v = x - target = [ 3 - (-5) ; 4 - 0 ] = [ 8 ; 4 ] H = I - 2 v v^T / (v^T v) # v^T v = 64 + 16 = 80 H @ x = [ -5 ; 0 ] # the 4 is gone, in one reflection # Apply H1 to A's first column, H2 to the trailing 2nd column, ... # Q = H1 H2 ... Hn-1 (orthogonal), R = (last H ... H1) A (upper-tri).
Givens: zero one entry, surgically
A Givens rotation is a plane rotation that touches only two rows. Choosing the rotation angle by c = a/r, s = b/r with r = sqrt(a^2 + b^2) rotates the pair (a, b) to (r, 0), zeroing exactly one entry while leaving the rest of the matrix untouched. Where Householder clears a whole column, Givens is a scalpel — ideal when A already has structure (it is sparse, or you only need to fix up a few stray entries).
- To zero entry (i, j) using row k above it, look at the pair (a, b) = (A_kj, A_ij).
- Form r = sqrt(a^2 + b^2), c = a/r, s = b/r — that is the rotation that sends (a, b) -> (r, 0).
- Apply the 2x2 rotation [c, s; -s, c] to rows k and i only; entry (i, j) becomes 0.
Both reflections and rotations are orthogonal, so a product of them is orthogonal — that product *is* Q^T. The resulting QR is far more accurate than Gram-Schmidt's, which is exactly why every serious least squares solver and the eigenvalue machinery in the next guides are built on it. Householder for dense one-shot work; Givens when you want to preserve sparsity or parallelize.