Gram-Schmidt orthogonalization

Any set of linearly independent vectors $v_{1},\ldots,v_{n}$ can be converted into a set of orthogonal vectors $q_{1},\ldots,q_{n}$ by the Gram-Schmidt process. In three dimensions, $v_{1}$ determines a line; the vectors $v_{1}$ and $v_{2}$ determine a plane. The vector $q_{1}$ is the unit vector in the direction $v_{1}$ . The (unit) vector $q_{2}$ lies in the plane of $v_{1},v_{2}$ , and is normal to $v_{1}$ (on the same side as $v_{2}$ . The (unit) vector $q_{3}$ is normal to the plane of $v_{1},v_{2}$ , on the same side as $v_{3}$ , etc.

In general, first set $u_{1}=v_{1}$ , and then each $u_{i}$ is made orthogonal to the preceding $u_{1},\ldots u_{i-1}$ by subtraction of the projections of $v_{i}$ in the directions of $u_{1},\ldots,u_{i-1}$ :

u_{i}=v_{i}-\sum_{j=1}^{i-1}\frac{u_{j}^{T}v_{i}}{u_{j}^{T}u_{j}}u_{j}

The $i$ vectors $u_{i}$ span the same subspace as the $v_{i}$ . The vectors $q_{i}=u_{i}/||u_{i}||$ are orthonormal. This leads to the following theorem:

Theorem.

Any $m\times n$ matrix $A$ with linearly independent columns can be factorized into a product, $A=QR$ . The columns of $Q$ are orthonormal and $R$ is upper triangular and invertible.

This “classical” Gram-Schmidt method is often numerically unstable, see [Golub89] for a “modified” Gram-Schmidt method.

References

•

Originally from The Data Analysis Briefbook (http://rkb.home.cern.ch/rkb/titleA.htmlhttp://rkb.home.cern.ch/rkb/titleA.html)

Golub89

Gene H. Golub and Charles F. van Loan: Matrix Computations, 2nd edn., The John Hopkins University Press, 1989.

Title	Gram-Schmidt orthogonalization
Canonical name	GramSchmidtOrthogonalization
Date of creation	2013-03-22 12:06:14
Last modified on	2013-03-22 12:06:14
Owner	akrowne (2)
Last modified by	akrowne (2)
Numerical id	9
Author	akrowne (2)
Entry type	Algorithm
Classification	msc 65F25
Synonym	Gram-Schmidt decomposition
Synonym	Gram-Schmidt orthonormalization
Synonym	Gram-Schmidt process
Related topic	HouseholderTransformation
Related topic	GivensRotation
Related topic	QRDecomposition
Related topic	AnExampleForSchurDecomposition