In matematica, una trasformazione di Householder in uno spazio tridimensionale è la riflessione dei vettori rispetto ad un piano passante per l'origine. In generale in uno spazio euclideo essa è una trasformazione lineare che descrive una riflessione rispetto ad un iperpiano contenente l'origine.
La trasformazione di Householder è stata introdotta nel 1958 dal matematico statunitense Alston Scott Householder (1905-1993). Questa può essere usata per ottenere una fattorizzazione QR di una matrice.
La riflessione di un punto
rispetto ad un iperpiano, definito come ortogonale ad un versore
, è data da:
![{\displaystyle \mathbf {x} -2\langle \mathbf {x} ,\mathbf {u} \rangle \mathbf {u} =\mathbf {x} -2\mathbf {u} (\mathbf {u} ^{\text{T}}\mathbf {x} )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/06ce84eb1c13d6fe0e67b88e1f1b21015e7d09bd)
dove
denota il prodotto scalare euclideo, analogo al prodotto tra matrici, che definisce la distanza di
dall'iperpiano, mentre
denota la trasposta (la trasposta coniugata nel caso complesso) del vettore
(inteso come matrice di una sola colonna). Si tratta di una trasformazione lineare che è rappresentata dalla matrice di Householder:
![{\displaystyle U=I-2\mathbf {u} \mathbf {u} ^{T}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3007c401d65b2cf2e3d9620d6cef32aedc6b4ede)
dove
è la matrice identità.
La matrice di Householder ha le seguenti proprietà:
![{\displaystyle U^{T}=(I-2\mathbf {u} \mathbf {u} ^{T})^{T}=I-2(\mathbf {u} \mathbf {u} ^{T})^{T}=I-2((\mathbf {u} ^{T})^{T}\mathbf {u} ^{T})=I-2\mathbf {u} \mathbf {u} ^{T}=U}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1f19bac2925b0ac7f859efe2e68a90878e097032)
- è ortogonale, ovvero
, cioè
. Infatti:
![{\displaystyle {\begin{aligned}U^{T}U&=UU\\&=(I-2\mathbf {u} \mathbf {u} ^{T})(I-2\mathbf {u} \mathbf {u} ^{T})\\&=I-4\mathbf {u} \mathbf {u} ^{T}+4\mathbf {u} \underbrace {\mathbf {u} ^{T}\mathbf {u} } _{\lVert \mathbf {u} \rVert =1}\mathbf {u} ^{T}\\&=I-4\mathbf {u} \mathbf {u} ^{T}+4\mathbf {u} \mathbf {u} ^{T}\\&=I\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e5582ee4b9643830424fbbaba32028e3a4e9ad93)
- Si è così dimostrato che
è un'involuzione, ovvero
.
- Possiede soltanto autovalori uguali a
.
- Il determinante (prodotto degli autovalori) è
.
Le matrici di Householder sono un caso particolare di matrici elementari.
La matrice di Householder
può essere usata per annullare tutte le componenti di un vettore tranne la prima, nel modo seguente. Siano:
![{\displaystyle \mathbf {x} ={\begin{pmatrix}x_{1}\\\vdots \\x_{n}\end{pmatrix}}\qquad \mathbf {e} _{1}={\begin{pmatrix}1\\0\\\vdots \\0\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4df3586d1e68d74f2cfa01dd8241a7ba3f0f940b)
e si definisce:
![{\displaystyle \sigma =\|\mathbf {x} \|\qquad \mathbf {v} =\mathbf {x} +\sigma \mathbf {e} _{1}={\begin{pmatrix}x_{1}+\sigma \\x_{2}\\\vdots \\x_{n}\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aed45f14eb4bbd4160dcb355f753cac0d5d199ee)
Si ha, per una
con
opportuno, che:
![{\displaystyle U\mathbf {x} ={\begin{pmatrix}-\sigma \\0\\\vdots \\0\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2decc8ebd7f33e20eaba11b7f78ef73ae02470aa)
Infatti, definendo
dove
![{\displaystyle \alpha ={\frac {\|\mathbf {v} \|^{2}}{2}}={\frac {\mathbf {v} ^{T}\mathbf {v} }{2}}={\frac {(\mathbf {x} +\sigma \mathbf {e} _{1})^{T}(\mathbf {x} +\sigma \mathbf {e} _{1})}{2}}={\frac {\overbrace {\mathbf {x} ^{T}\mathbf {x} } ^{\|\mathbf {x} \|^{2}=\sigma ^{2}}+2\sigma x_{1}+\sigma ^{2}}{2}}=\sigma ^{2}+\sigma x_{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a1459c42b068b4dd0afeee6d1ee76218bd7dbfc7)
si ha:
![{\displaystyle U\mathbf {x} =\left(I-{\frac {1}{\alpha }}\mathbf {v} \mathbf {v} ^{T}\right)\mathbf {x} =\mathbf {x} -{\frac {1}{\alpha }}\left(\mathbf {x} +\sigma \mathbf {e} _{1}\right)\left(\mathbf {x} +\sigma \mathbf {e} _{1}\right)^{T}\mathbf {x} =\mathbf {x} -{\frac {1}{\alpha }}\left(\mathbf {x} +\sigma \mathbf {e} _{1}\right)\left(\sigma ^{2}+\sigma x_{1}\right)=\mathbf {x} -{\frac {1}{\alpha }}\left(\mathbf {x} +\sigma \mathbf {e} _{1}\right)\alpha =\mathbf {x} -\mathbf {x} -\sigma \mathbf {e} _{1}=-\sigma \mathbf {e} _{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/55bef2fb0f785895822379ea7753bae2165c5a8b)
Sia
un arbitrario vettore colonna m-dimensionale di lunghezza
(per la stabilità numerica del metodo si assume che
ha lo stesso segno della prima coordinata di
). Se
è il vettore
, si considerino:
![{\displaystyle \mathbf {u} =\mathbf {x} -\alpha \mathbf {e} _{1}\qquad \mathbf {v} ={\frac {\mathbf {u} }{\|\mathbf {u} \|}}\qquad Q=I-2\mathbf {v} \mathbf {v} ^{t}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1ba147a38eb1d428d4cd027f6dec707c0ce6c55a)
Data la matrice di Householder
, per quanto detto sopra si ha:
![{\displaystyle Q\mathbf {x} =(\alpha ,0,\dots ,0)^{T}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6093aa3711a9d19f7cab97770443b7f3b17c541f)
e questo risultato può essere usato per trasformare gradualmente una matrice
di tipo
nella forma triangolare superiore: innanzitutto si moltiplica
per la matrice di Householder
ottenuta scegliendo
per la sua prima colonna. Questa risulta in una matrice
che presenta zeri nella colonna sinistra, ad eccezione della sola prima riga:
![{\displaystyle Q_{1}A={\begin{bmatrix}\alpha _{1}&\star &\dots &\star \\0&&&\\\vdots &&A'&\\0&&&\end{bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/39819d86bf38ddf93caca5b2853cc07d4414be24)
Questa modifica può essere ripetuta per
mediante una matrice di Housholder
. Si noti che
è
più piccola di
. Poiché si vuole che sia reale, per operare su
invece di
è necessario espandere
questa nella parte superiore sinistra, riempiendola di entrate 1, o in generale:
![{\displaystyle Q_{k}={\begin{bmatrix}I_{k-1}&0\\0&Q_{k}'\end{bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c4eb5b2dc8e2e895ca5214cd34fa7b87817e41e4)
Dopo
iterazioni di questo processo, con
, si giunge a:
![{\displaystyle R=Q_{t}\dots Q_{2}Q_{1}A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5580d208a40f56a8df3deb398c7e7206ed1834e8)
che è una matrice triangolare superiore. In tal modo, con:
![{\displaystyle Q=Q_{1}Q_{2}\dots Q_{t}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec0860887eea2f4ff5559f5f78f35907b8e639bb)
la decomposizione
è una decomposizione QR di
. Questo metodo risulta numericamente stabile.
- (EN) WH Press, SA Teukolsky, WT Vetterling e BP Flannery, Section 11.3.2. Householder Method, in Numerical Recipes: The Art of Scientific Computing, 3rd, New York, Cambridge University Press, 2007, ISBN 978-0-521-88068-8. URL consultato il 29 novembre 2014 (archiviato dall'url originale l'11 agosto 2011).
- (EN) Householder, A. S. Principles of Numerical Analysis. New York: McGraw-Hill, pp. 135–138, 1953.
- (EN) Lehoucq, R. B. "The Computation of Elementary Unitary Matrices." ACM Trans. Math. Software 22, 393-400, 1996.
- (EN) Trefethen, L. N. and Bau, D. III. Numerical Linear Algebra. Philadelphia, PA: SIAM, 1997.