Gram-Schmidt orthogonalization

Gram-Schmidt is the textbook way to turn a set of slanted, possibly redundant vectors into a clean set of mutually perpendicular unit vectors that span the same space. You take the vectors one at a time. The first you simply normalize. For each new vector, you subtract off its shadows along all the directions you have already fixed, leaving only the genuinely new, perpendicular part, then normalize that. It is how you build an orthonormal basis by hand — and how you build the Q of a QR factorization column by column.

Step by step, given columns a_1, a_2, ...: set q_1 = a_1 / ||a_1||. For a_2, remove its component along q_1: v_2 = a_2 - (q_1^T a_2) q_1, then q_2 = v_2 / ||v_2||. For a_3, remove its components along both q_1 and q_2, and so on. The coefficients you peel off (the q_i^T a_j) are exactly the entries of the upper-triangular R, so Gram-Schmidt produces A = Q R directly and gives the same least-squares machinery as the other QR methods. It is the most intuitive of the three.

Here is the honest catch: the naive 'classical' Gram-Schmidt is numerically fragile. When vectors are nearly parallel, the subtractions involve catastrophic cancellation and the computed q's drift away from orthogonality. The fix is 'modified Gram-Schmidt' (MGS), which subtracts the projections one at a time using the freshly updated vector rather than all at once — algebraically identical, numerically far better. Even so, for the highest accuracy Householder QR is preferred; Gram-Schmidt earns its keep for intuition, for sparse settings, and inside Krylov methods like Arnoldi where orthogonalizing against a growing basis is the core operation.