Gram-Schmidt process

In linear algebra, the Gram-Schmidt process is method of orthogonalizing a set of vectors in an inner product space, most commonly the Euclidean space Rⁿ. Orthogonalization in this context means the following: we start with vectors v₁,...,v_k which are linearly independent and we want to find mutually orthogonal vectors u₁,...,u_k which generate the same subspace as the vectors v₁,...,v_k.

We denote the inner (dot) product of the two vectors u and v by (u . v). The Gram-Schmidt process works as follows:

u₁ = v₁

u₂ = v₂ - [(v₂ . u₁)/(u₁ . u₁)]u₁

u₃ = v₃ - [(v₃ . u₁)/(u₁ . u₁)]u₁ - [(v₃ . u₂)/(u₂ . u₂)]u₂

...

u_k = v_k - [(v_k . u₁)/(u₁ . u₁)]u₁ - [(v_k . u₂)/(u₂ . u₂)]u₂ - ... - [(v_k . u_k-1)/(u_k-1 . u_k-1)]u_k-1

To check that these formulas work, first compute (u₁ . u₂) by substituting the above formula for u₂: you will get zero. Then use this to compute (u₁ . u₃) again by substituting the formula for u₃: you will get zero. The general proof proceeds by mathematical induction.

Geometrically, this method proceeds as follows: to compute u_i, it projects v_i orthogonally onto the subspace U generated by u₁,...,u_i-1, which is the same as the subspace generated by v₁,...,v_i-1. u_i is then defined to be the difference between v_i and this projection, guaranteed to be orthogonal to all of the vectors in the subspace U.

If one is interested in an orthonormal system u₁,...,u_k (i.e. the vectors are mutually orthogonal and all have norm 1), then one can divide u_i by its norm (u_i . u_i).

When performing orthogonalization on a computer, the Householder transformation is usually preferred over the Gram-Schmidt process since it is more numerically stable, i.e. rounding errors tend to have less serious effects.