Household transformation

from Wikipedia, the free encyclopedia

In mathematics , the household transformation describes the reflection of a vector at a hyperplane by zero in Euclidean space . In three-dimensional space it is therefore a reflection on a plane (through the origin). The representation of this linear mapping by a matrix is ​​called the Householder matrix . It is mainly used in numerical mathematics , when matrices are specifically reshaped using orthogonal transformations in such a way that certain column vectors are mapped to the multiple of the first unit vector , especially in the QR method and QR decomposition .

The household transformation was introduced in 1958 by the American mathematician Alston Scott Householder .

Definition and characteristics

Illustration of the householder transformation in 2D

The mirror hyperplane can be defined by a normal vector , i.e. a vector that is orthogonal to the hyperplane. If the column vector is given and the identity matrix is ​​given , then the linear mapping described above is represented by the following matrix:

The transpose of the column vector denotes 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 . If the length is normalized to one, that is , the formula is simplified to

The reflection property can be seen from the fact that

,

where denotes the standard scalar product. The term corresponds to the distance between the point and the hyperplane . The vector is broken down into two mutually orthogonal parts, the first part being in the hyperplane and the second being a multiple of the vector . Under the reflection, the portion in the plane is left invariant, the portion in the direction , i.e. perpendicular to the plane, is "flipped over", so now subtracted instead of added.

The householder matrix has the following properties:

  • It is symmetrical :
  • It is orthogonal :
  • It is involutor: (This follows from symmetry and orthogonality.)
  • It has the simple eigenvalue −1 for the eigenvector and the -fold eigenvalue 1. The eigenspace for the eigenvalue 1 is the mirror plane, i.e. the orthogonal complement of the one-dimensional subspace generated by .
  • Matrix-vector multiplications with can be calculated quickly.

Construction of a specific reflection

Let there be a vector that is to be mirrored onto a multiple of the vector , that is, a unit vector is sought , so that with the associated Householder matrix applies . Geometrically, the vector is the direction of one of the two bisectors of the straight line in direction and in direction . The bisector is obtained by choosing points on both straight lines with the same distance from the zero point and constructing the center point on the line connecting these two points. The straight line through the zero point and center point then has the direction sought , the vector itself is obtained by normalizing this direction. The second bisector is obtained by performing the construction starting from and .

For simplicity, it normalized . Then, because of the orthogonality of the reflection, must apply. The reflection vector you are looking for is now obtained by normalizing the difference vector , that is

.

Both sign variants lead to the desired result (provided that the denominator is different from zero). For reasons of numerical stability, the sign of is chosen in such a way that the denominator is the largest, i.e. the following applies.

In the sample it results

example

Most often the case is considered where is the first canonical basis vector. Be divided into first component and remainder vector. Then applies to the norm . The sign of is to be selected as the sign of , the direction of the reflection is then

.

It is

The vector is created by normalizing this direction. After forming, the norm of the direction arises as

, whereby only intermediate results that have already been calculated are used in this form. The non-standardized variant of mirroring results in further savings in computing steps.

Application: QR decomposition

Householder reflections can be used for the stable calculation of QR decompositions of a matrix by first mirroring the first column of the matrix with a reflection to the multiple of the first unit vector, as explained in the last section (but now the index denotes the number of the reflection ).

Thereafter, one treats with a reflection analogously, whereby the reflection is constructed in such a way that the first row and column remain unaffected by the transformation. This is achieved by setting the first component of the reflection vector to zero. To determine the third step, only the main sub-matrix under the third diagonal element is included, the reflection vector is zero in the first two components, etc. In the -th step, the sub-matrix under the position of the product is reduced in the same way until the remaining matrix is ​​triangular owns. (In this case, steps are sufficient , since the last column no longer needs to be transformed.)

With , the QR decomposition results

With

Note that there is a square matrix here. Usually the matrices or are not calculated explicitly, but the product shape is used directly. For this, the mirror vectors of the vacant space of the matrix stored.

The number of operations for the QR decomposition of a matrix using the Householder method is:

Pseudocode

Since the explicit calculation of is not necessary for most calculations , it is sufficient to only calculate the matrix . is the left column of the respective sub-matrix . In the below-mentioned function, the result is directly in written, so that after execution of the algorithm, in stands. The line could also be omitted.

  function GetR(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

However, should it be required, the above example can be easily expanded:

  function GetR(A)
    Q=eye(m) 
    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)
         Q=Q-Q*vk*(2*vk')
     R=A
     return R

See also

literature

  • Gene H. Golub , Charles F. van Loan: Matrix Computations . 2nd edition. The Johns Hopkins University Press, 1989.
  • Gerhard Sacrifice: 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 Mathematics , 2nd, revised and expanded edition, Oldenbourg Verlag, Munich, Vienna 2006, ISBN 3-486-57935-5 , pp. 159-161