title: Trasformazione di Householder
text: # 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.
  
  ## Definizione e proprietà
  
  La riflessione di un punto $\mathbf {x}$ rispetto ad un iperpiano, definito come ortogonale ad un versore $\mathbf {u}$, è data da:
  
      $\mathbf {x} -2\langle \mathbf {x} ,\mathbf {u} \rangle \mathbf {u} =\mathbf {x} -2\mathbf {u} (\mathbf {u} ^{\text{T}}\mathbf {x} )$
  
  dove $\langle ,\rangle$ denota il prodotto scalare euclideo, analogo al prodotto tra matrici, che definisce la distanza di $\mathbf {x}$ dall'iperpiano, mentre $\mathbf {u} ^{T}$ denota la trasposta (la trasposta coniugata nel caso complesso) del vettore $\mathbf {u}$ (inteso come matrice di una sola colonna). Si tratta di una trasformazione lineare che è rappresentata dalla matrice di Householder:
  
      $U=I-2\mathbf {u} \mathbf {u} ^{T}$
  
  dove $I$ è la matrice identità.
  
  La matrice di Householder ha le seguenti proprietà:
  
  * è una matrice hermitiana (simmetrica), ovvero $U=U^{T}$. Infatti:
  
      $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 $U^{T}=U^{-1}$, cioè $U^{T}U=I$. Infatti:
  
      ${\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 $U$ è un'involuzione, ovvero $U^{2}=I$.
  * Possiede soltanto autovalori uguali a $\pm 1$.
  * Il determinante (prodotto degli autovalori) è $-1$.
  
  Le matrici di Householder sono un caso particolare di matrici elementari.
  
  ## Applicazione della matrice di trasformazione
  
  La matrice di Householder $U$ può essere usata per annullare tutte le componenti di un vettore tranne la prima, nel modo seguente. Siano:
  
      $\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:
  
      $\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 $U=I-\lambda \mathbf {v} \mathbf {v} ^{T}$con $\lambda$ opportuno, che:
  
      $U\mathbf {x} ={\begin{pmatrix}-\sigma \\0\\\vdots \\0\end{pmatrix}}$
  
  Infatti, definendo ${\frac {1}{\lambda }}=\alpha$ dove
  
      $\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:
  
      $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}$
  
  ## La fattorizzazione QR
  
  Sia $\mathbf {x}$ un arbitrario vettore colonna m-dimensionale di lunghezza $|\alpha |$ (per la stabilità numerica del metodo si assume che $\alpha$ ha lo stesso segno della prima coordinata di $\mathbf {x}$). Se $\mathbf {e} _{1}$ è il vettore $(1,0,\dots ,0)^{T}$, si considerino:
  
      $\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 $Q$, per quanto detto sopra si ha:
  
      $Q\mathbf {x} =(\alpha ,0,\dots ,0)^{T}$
  
  e questo risultato può essere usato per trasformare gradualmente una matrice $A$ di tipo $m\times n$ nella forma triangolare superiore: innanzitutto si moltiplica $A$ per la matrice di Householder $Q_{1}$ ottenuta scegliendo $\mathbf {x}$ per la sua prima colonna. Questa risulta in una matrice $QA$ che presenta zeri nella colonna sinistra, ad eccezione della sola prima riga:
  
      $Q_{1}A={\begin{bmatrix}\alpha _{1}&\star &\dots &\star \\0&&&\\\vdots &&A'&\\0&&&\end{bmatrix}}$
  
  Questa modifica può essere ripetuta per $A'$ mediante una matrice di Housholder $Q_{2}$. Si noti che $Q_{2}$ è più piccola di $Q_{1}$. Poiché si vuole che sia reale, per operare su $Q_{1}A$ invece di $A'$ è necessario espandere questa nella parte superiore sinistra, riempiendola di entrate 1, o in generale:
  
      $Q_{k}={\begin{bmatrix}I_{k-1}&0\\0&Q_{k}'\end{bmatrix}}$
  
  Dopo $t$ iterazioni di questo processo, con $t=\min(m-1,n)$, si giunge a:
  
      $R=Q_{t}\dots Q_{2}Q_{1}A$
  
  che è una matrice triangolare superiore. In tal modo, con:
  
      $Q=Q_{1}Q_{2}\dots Q_{t}$
  
  la decomposizione $A=QR$ è una decomposizione QR di $A$. Questo metodo risulta numericamente stabile.
  
  