PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Very high Entry average rating: High
Householder transformation (Algorithm)

This entry describes the Householder transformation $ u=Hv$, the most frequently used algorithm for performing QR decomposition. The key object here is the Householder matrix $ H$, a symmetric and orthogonal matrix of the form

$\displaystyle H = I - 2xx^T, $

where $ I$ is the identity matrix and we have used any normalized vector $ x$ with $ \vert\vert x\vert\vert _2^2 = x^Tx = 1$.

The Householder transformation zeroes the last $ m-1$ elements of a column vector below the first element:

$\displaystyle \begin{bmatrix}v_1 \\ v_2 \\ \vdots \\ v_m \end{bmatrix} \rightarrow \begin{bmatrix}c \\ 0 \\ \vdots \\ 0 \end{bmatrix}$   with$\displaystyle \; c = \pm \vert\vert v\vert\vert _2 = \pm \left(\sum_{i=1}^m v_i^2\right)^{1/2} $

One can verify that

$\displaystyle x = f \begin{bmatrix}v_1 - c \\ v_2 \\ \vdots \\ v_m \end{bmatrix}$   with$\displaystyle \; f=\frac{1}{\sqrt{2c(c-v_1)}} $

fulfils $ x^Tx=1$ and that with $ H=I-2xx^T$ one obtains the vector $ \begin{bmatrix}c & 0 & \cdots & 0 \end{bmatrix}^T$.

To perform the decomposition of the $ m \times n$ matrix $ A = QR$ (with $ m \ge n$) we construct an $ m \times m$ matrix $ H^{(1)}$ to change the $ m-1$ elements of the first column to zero. Similarly, an $ m-1 \times m-1$ matrix $ G^{(2)}$ will change the $ m-2$ elements of the second column to zero. With $ G^{(2)}$ we produce the $ m \times m$ matrix

$\displaystyle H^{(2)} = \begin{bmatrix}1 & 0 & \cdots & 0 \\ 0 & \; & \; & \; \\ \vdots & \; & G^{(2)} & \; \\ 0 & \; & \; & \; \end{bmatrix}.$

After $ n$ such orthogonal transformations ($ n-1$ times in the case that $ m=n$), we let

$\displaystyle R = H^{(n)}\cdots H^{(2)}H^{(1)}A.$

$ R$ is upper triangular and the orthogonal matrix $ Q$ becomes

$\displaystyle Q = H^{(1)}H^{(2)} \cdots H^{(n)}.$

In practice the $ H^{(i)}$ are never explicitly computed.

References



"Householder transformation" is owned by mathcam. [ full author list (2) | owner history (1) ]
(view preamble)

View style:

See Also: Gram-Schmidt orthogonalization

Other names:  Householder reflection, Householder matrix
Keywords:  matrix orthogonalization
Log in to rate this entry.
(view current ratings)

Cross-references: upper triangular, orthogonal transformations, column, matrix, decomposition, column vector, vector, identity matrix, orthogonal matrix, symmetric, object, QR decomposition, algorithm
There are 5 references to this entry.

This is version 6 of Householder transformation, born on 2002-01-04, modified 2006-06-20.
Object id is 1210, canonical name is HouseholderTransformation.
Accessed 23324 times total.

Classification:
AMS MSC65F25 (Numerical analysis :: Numerical linear algebra :: Orthogonalization)
 15A57 (Linear and multilinear algebra; matrix theory :: Other types of matrices )

Pending Errata and Addenda
None.
[ View all 3 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add example | add (any)