Trasformazione di Householder

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 ${\displaystyle \mathbf {x} }$ rispetto ad un iperpiano, definito come ortogonale ad un versore ${\displaystyle \mathbf {u} }$, è 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} )}$

dove ${\displaystyle \langle ,\rangle }$ denota il prodotto scalare euclideo, analogo al prodotto tra matrici, che definisce la distanza di ${\displaystyle \mathbf {x} }$ dall'iperpiano, mentre ${\displaystyle \mathbf {u} ^{T}}$ denota la trasposta (la trasposta coniugata nel caso complesso) del vettore ${\displaystyle \mathbf {u} }$ (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}}$

dove ${\displaystyle I}$ è la matrice identità.

La matrice di Householder ha le seguenti proprietà:

• è una matrice hermitiana (simmetrica), ovvero ${\displaystyle U=U^{T}}$. Infatti:

${\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}$

• è ortogonale, ovvero ${\displaystyle U^{T}=U^{-1}}$, cioè ${\displaystyle U^{T}U=I}$. 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}}}$

• Si è così dimostrato che ${\displaystyle U}$ è un'involuzione, ovvero ${\displaystyle U^{2}=I}$.
• Possiede soltanto autovalori uguali a ${\displaystyle \pm 1}$.
• Il determinante (prodotto degli autovalori) è ${\displaystyle -1}$.

Le matrici di Householder sono un caso particolare di matrici elementari.

La matrice di Householder ${\displaystyle U}$ 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}}}$

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}}}$

Si ha, per una ${\displaystyle U=I-\lambda \mathbf {v} \mathbf {v} ^{T}}$con ${\displaystyle \lambda }$ opportuno, che:

${\displaystyle U\mathbf {x} ={\begin{pmatrix}-\sigma \\0\\\vdots \\0\end{pmatrix}}}$

Infatti, definendo ${\displaystyle {\frac {1}{\lambda }}=\alpha }$ 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}}$

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}}$

Lo stesso argomento in dettaglio: Decomposizione QR.

Sia ${\displaystyle \mathbf {x} }$ un arbitrario vettore colonna m-dimensionale di lunghezza ${\displaystyle |\alpha |}$ (per la stabilità numerica del metodo si assume che ${\displaystyle \alpha }$ ha lo stesso segno della prima coordinata di ${\displaystyle \mathbf {x} }$). Se ${\displaystyle \mathbf {e} _{1}}$ è il vettore ${\displaystyle (1,0,\dots ,0)^{T}}$, 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}}$

Data la matrice di Householder ${\displaystyle Q}$, per quanto detto sopra si ha:

${\displaystyle Q\mathbf {x} =(\alpha ,0,\dots ,0)^{T}}$

e questo risultato può essere usato per trasformare gradualmente una matrice ${\displaystyle A}$ di tipo ${\displaystyle m\times n}$ nella forma triangolare superiore: innanzitutto si moltiplica ${\displaystyle A}$ per la matrice di Householder ${\displaystyle Q_{1}}$ ottenuta scegliendo ${\displaystyle \mathbf {x} }$ per la sua prima colonna. Questa risulta in una matrice ${\displaystyle QA}$ 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}}}$

Questa modifica può essere ripetuta per ${\displaystyle A'}$ mediante una matrice di Housholder ${\displaystyle Q_{2}}$. Si noti che ${\displaystyle Q_{2}}$ è più piccola di ${\displaystyle Q_{1}}$. Poiché si vuole che sia reale, per operare su ${\displaystyle Q_{1}A}$ invece di ${\displaystyle A'}$ è 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}}}$

Dopo ${\displaystyle t}$ iterazioni di questo processo, con ${\displaystyle t=\min(m-1,n)}$, si giunge a:

${\displaystyle R=Q_{t}\dots Q_{2}Q_{1}A}$

che è una matrice triangolare superiore. In tal modo, con:

${\displaystyle Q=Q_{1}Q_{2}\dots Q_{t}}$

la decomposizione ${\displaystyle A=QR}$ è una decomposizione QR di ${\displaystyle A}$. 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.

• Decomposizione di una matrice
• Decomposizione QR
• Matrice elementare
• Riflessione (matematica)

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica