GramSchmidtprocedure

The Gram-Schmidt procedure is a method for converting a finite sequence of vectors into an orthonormal sequence that spans the same subspace. It is a fundamental tool in numerical linear algebra, used to construct bases for subspaces and to compute QR factorizations of matrices.

In the classical Gram-Schmidt process, given linearly independent vectors a1, a2, ..., an in an inner product space (often R^m), one builds an orthonormal set q1, q2, ..., qn as follows. Set u1 = a1 and q1 = u1 / ||u1||. For k from 2 to n, form w_k = a_k − sum_{j=1}^{k−1} (a_k · q_j) q_j, and then q_k = w_k / ||w_k||. The vectors q1, q2, ..., qn are mutually orthonormal and span the same subspace as the original vectors (assuming no w_k is zero, i.e., the a_k are linearly independent).

Modified Gram-Schmidt is a numerically more stable variant. It orthogonalizes the current vector against already computed q_js in a sequence that reduces error accumulation: compute r_{jk} = q_j^T a_k for j < k, update a_k := a_k − sum_{j<k} r_{jk} q_j, then set r_{kk} = ||a_k|| and q_k = a_k / r_{kk}. This approach is generally more robust in finite-precision arithmetic.

Applications and connections: Gram-Schmidt underpins the QR factorization A = QR, where Q has orthonormal columns and R is upper triangular. It is used in solving least-squares problems, in eigenvalue algorithms, and in forming orthonormal bases for column spaces. The method requires the input vectors to be linearly independent; if a vector becomes zero, the process signals a dependent column, which may be dropped or handled with pivoting or regularization.