Gram–Schmidt process - Wikipedia

Abstraction: Algorithm constructing orthonormal basis from linearly independent vectors

Key points:

• The Gram–Schmidt process iteratively projects each vector onto the orthogonal complement of the span of previous vectors, then normalizes; produces an orthonormal set spanning the same subspace.
• Applied to columns of a full-rank matrix, it yields the QR decomposition: A = QR with Q orthogonal and R upper triangular.
• Classical Gram–Schmidt (CGS) is numerically unstable due to accumulation of rounding errors; modified Gram–Schmidt (MGS) reorders subtractions to achieve greater orthogonality in finite precision.
• Cost is O(nk²) floating-point operations for k vectors of dimension n.
• A Cholesky-based alternative (compute R from A^T A = L L^T, then Q = A L^{-T}) is simple and efficient but amplifies condition number errors.
• Only Gram–Schmidt produces orthogonalized vectors incrementally, making it suitable for iterative methods like the Arnoldi iteration.

Connections: Gram Schmidt Process · Orthonormal Basis · Qr Decomposition · Numerical Stability

Source: http://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process