Orthogonalization
From Wikipedia, the free encyclopedia
In linear algebra, orthogonalization means the following: We start with a linearly independent set of vectors {v1,...,vk} in an inner product space (most commonly the Euclidean space Rn), and we want to find a set of pairwise orthogonal vectors {u1,...,uk} that generate the same subspace as the vectors v1,...,vk. In other words, every vector in the new set is orthogonal to every other vector in the new set; and the new set and the old set have the same linear span.
In addition, if we want the resulting vectors to all be unit vectors, then the procedure is called orthonormalization.
Colloquially, orthogonalization is the process of splitting a problem or system into its distinct components.
[edit] Orthogonalization algorithms
Methods for performing orthogonalization include:
- Gram-Schmidt process, which uses projection
- Householder transformation, which uses reflection
- Givens rotation
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.
On the other hand, the Gram–Schmidt process produces the jth orthogonalized vector after the jth iteration, while orthogonalization using Householder reflections produces all the vectors only at the end. This makes only the Gram–Schmidt process applicable for iterative methods like the Arnoldi iteration.
The Givens rotation is more easily parallelized than Householder transformations.
Golden Days, Golden Ways - 2008
