34. Gram–Schmidt
Given a linearly independent set , the Gram–Schmidt process produces an orthonormal set that spans the same subspace.
It “straightens out” the basis: removes the parallel components between successive vectors so they become mutually orthogonal, then normalizes each.
34.1. The algorithm
Process the input vectors one at a time. For each new vector, subtract off its projection onto the orthonormal vectors already built, then normalize.
For :
The first step is just normalization: .
Example
, in .
Step 1: .
Step 2: project onto and subtract:
Normalize: .
Verify: and .
34.2. Why it works
After subtracting the projections, is orthogonal to every previously-built . Inductively, after step , the set is orthonormal and spans the same subspace as .
34.3. Numerical instability
Classical Gram–Schmidt (the version above) is unstable in floating point — small rounding errors compound, and the computed ‘s drift away from being truly orthogonal.
Better alternatives:
- Modified Gram–Schmidt — subtract projections one at a time as you go, instead of all at once; much more stable
- Householder reflections — used to compute QR in practice
- Givens rotations — for sparse / structured input
For pencil-and-paper or symbolic use, classical Gram–Schmidt is fine. For numerical libraries, Householder is standard.
34.4. Connection to QR
The Gram–Schmidt process is exactly the construction behind the QR decomposition: the orthonormal vectors form , and the projection coefficients form .