Householdertransformation
In mathematics, the Householder transformation describes the reflection of a vector to a hyperplane through zero in Euclidean space. In three-dimensional space it is therefore a reflection in a plane ( through the origin ). The presentation of this linear map by a matrix is called a Householder matrix. Finds use particularly in the numerical analysis, when using the orthogonal transformation matrices are formed selectively to particular columns vectors are mapped to the multiple of the first unit vector, in particular the method QR and QR decomposition.
The Householder transformation was introduced by the American mathematician Alston Scott Householder 1958.
- 3.1 Pseudocode
Definition and properties
Mirror hyperplane may be defined by a normal vector, ie a vector which is orthogonal to the hyperplane. Column vector and is given as the identity matrix, then the above-described linear transformation matrix is illustrated by the following:
Here, denotes the transpose of the column vector, ie, a row vector. The denominator is the scalar product of with itself, the dyadic product. The matrix describes the orthogonal projection onto the direction given by. Is normalized to length one, so that the formula is simplified to
The reflection property ersieht you from the fact that
Where the standard scalar called. The term corresponds to the distance of the point to the hyperplane. The vector x is thus divided into two orthogonal portions, the first portion lies in the hyperplane and second multiples of the vector v. Under the reflection of the proportion is left invariant in the plane, the component in the direction v, ie perpendicular to the plane is " flipped", so then subtracted instead of added.
The Householder matrix has the following properties:
- It is symmetrical:
- She is orthogonal:
- She is in involution: ( This follows from the symmetry and orthogonality. )
- It has the eigenvalues -1 ( with multiplicity 1 ) and 1 ( with multiplicity).
- Matrix-vector multiplications with H are quickly computable.
Construction of a specific reflection
It is a vector a given which is to be reflected to a multiple of the vector e, that is, a unit vector v is searched such that the following applies to the associated Householder matrix. Geometrically, the vector v e the direction of one of the two bisectors of the lines in a direction and in the direction of the bisector results by selecting on two straight points with the same distance from the zero point and designed on the link of these two points the center. Has the straight line through zero and then center the desired direction v, the vector v is obtained by normalizing this direction itself. The second bisector is obtained by the construction is carried out starting from a and -e.
For simplicity, let e be normalized. Then you have, because of the orthogonality of the mirror, apply. The desired reflection vector v is now obtained by normalizing the difference vector, ie
Both sign variants lead to the desired result (if the denominator is not zero ). The sign is chosen in such a For reasons of numerical stability, the denominator is the greatest, so true.
In the sample results
Example
Most often the case is considered in which the first canonical basis vector. Be broken in the first component and residual vector. Then for the norm. As a sign of the sign of is to choose the direction of reflection is then
The vector v is formed by normalizing this direction. After forming, the norm of the direction of presents as
Represents, and in this form only already calculated intermediate results are used. In the non-normalized version of the mirroring is more savings in computation steps arise.
Application: QR decomposition
Householder reflections can be used for stable calculation of QR decompositions of a matrix by first the first column of the matrix is mirrored with a reflection on the multiple of the first unit vector, as explained in the last section (now the index referred to but the number of mirroring ).
Then treated analogously with a mirror, the mirror is designed so that the first row and column of the transformation remain unaffected. This is achieved by making the first component of the reflection vector is set to zero. For the determination of the third step is analogous, only the main sub-array in the third diagonal element, the reflection vector is zero in the first two components, etc. in the i- th step, that is, the sub-matrix of the position (i, i) of the product equal to the reduced art, until the residual matrix has triangular shape. (In case sufficient steps since the last column does not need to be transformed. )
With true, so there is the QR decomposition
With
Note that here is a square matrix. Most matrices or not be calculated explicitly, but directly taking advantage of the product form. For this, the mirror has become vectors of the free space of the matrix are stored.
The number of operations for the QR decomposition of a matrix using the Householder method is:
Pseudocode
Since the explicit calculate of Q is not necessary for most calculations, it is sufficient to calculate only the matrix R. z is the left-hand column of the respective matrix. In the function below, the result is written directly to A, so that after execution of the algorithm, the R in A. The line R = A could thus be omitted.
Function sep (A) for k = 1 ... n z = A (k ... m, k) uk = z uk (1 ) = sign (z ( 1) ) * norm ( z) uk = uk / norm ( uk) vk = zeros (m) vk (k ... m ) = uk A = A- (2 * vk) * (vk ' * A) R = A return R literature
- Gene H. Golub, Charles F. van Loan: Matrix Computations. 2nd Edition. The Johns Hopkins University Press, 1989.
- Gerhard victims: Numerical mathematics for beginners. An introduction for mathematicians, engineers and computer scientists, 5th edition, Vieweg Teubner, Wiesbaden 2008, ISBN 978-3-8348-0413-6
- Martin Hermann: Numerical Analysis, 2nd revised and expanded edition, Oldenbourg Verlag, Munich, Vienna 2006, ISBN 3-486-57935-5, pp.159 -161
- Numerical linear algebra
- Transformation