Orthogonalization
Encyclopedia
In linear algebra
, orthogonalization is the process of finding a set of orthogonal vectors that span a particular subspace
. Formally, starting with a linearly independent set of vectors {v1,...,vk} in an inner product space
(most commonly the Euclidean space
Rn), orthogonalization results in a set of orthogonal
vectors {u1,...,uk} that generate the same subspace as the vectors v1,...,vk. 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.
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 method
s like the Arnoldi iteration
.
The Givens rotation is more easily parallelized than Householder transformations.
Linear algebra
Linear algebra is a branch of mathematics that studies vector spaces, also called linear spaces, along with linear functions that input one vector and output another. Such functions are called linear maps and can be represented by matrices if a basis is given. Thus matrix theory is often...
, orthogonalization is the process of finding a set of orthogonal vectors that span a particular subspace
Linear subspace
The concept of a linear subspace is important in linear algebra and related fields of mathematics.A linear subspace is usually called simply a subspace when the context serves to distinguish it from other kinds of subspaces....
. Formally, starting with a linearly independent set of vectors {v1,...,vk} in an inner product space
Inner product space
In mathematics, an inner product space is a vector space with an additional structure called an inner product. This additional structure associates each pair of vectors in the space with a scalar quantity known as the inner product of the vectors...
(most commonly the Euclidean space
Euclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
Rn), orthogonalization results in a set of orthogonal
Orthogonality
Orthogonality occurs when two things can vary independently, they are uncorrelated, or they are perpendicular.-Mathematics:In mathematics, two vectors are orthogonal if they are perpendicular, i.e., they form a right angle...
vectors {u1,...,uk} that generate the same subspace as the vectors v1,...,vk. 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
Linear span
In the mathematical subfield of linear algebra, the linear span of a set of vectors in a vector space is the intersection of all subspaces containing that set...
.
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.
Orthogonalization algorithms
Methods for performing orthogonalization include:- Gram-Schmidt process, which uses projectionProjection (linear algebra)In linear algebra and functional analysis, a projection is a linear transformation P from a vector space to itself such that P2 = P. It leaves its image unchanged....
- Householder transformationHouseholder transformationIn linear algebra, a Householder transformation is a linear transformation that describes a reflection about a plane or hyperplane containing the origin. Householder transformations are widely used in numerical linear algebra, to perform QR decompositions and in the first step of the QR algorithm...
, which uses reflectionReflection (mathematics)In mathematics, a reflection is a mapping from a Euclidean space to itself that is an isometry with a hyperplane as set of fixed points; this set is called the axis or plane of reflection. The image of a figure by a reflection is its mirror image in the axis or plane of 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
Numerical stability
In the mathematical subfield of numerical analysis, numerical stability is a desirable property of numerical algorithms. The precise definition of stability depends on the context, but it is related to the accuracy of the algorithm....
, 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 method
Iterative method
In computational mathematics, an iterative method is a mathematical procedure that generates a sequence of improving approximate solutions for a class of problems. A specific implementation of an iterative method, including the termination criteria, is an algorithm of the iterative method...
s like the Arnoldi iteration
Arnoldi iteration
In numerical linear algebra, the Arnoldi iteration is an eigenvalue algorithm and an important example of iterative methods. Arnoldi finds the eigenvalues of general matrices; an analogous method for Hermitian matrices is the Lanczos iteration. The Arnoldi iteration was invented by W. E...
.
The Givens rotation is more easily parallelized than Householder transformations.