Trasformazioni di Householder

Definizione

Dato un vettore $v\in {\mathbb{R}}^n,v\ne 0$, si definisce trasformazione elementare di Householder associata a $v$ la matrice $U=I-\frac{1}{\alpha }v{v}^T,\text{ con }\alpha =\frac{1}{2}||v|{|}^2$

$U$ è quindi simmetrica e ortogonale.

1. simmetria: $U^T=(I-\frac{1}{\alpha }v{v}^T{)}^T=I-\frac{1}{\alpha }(v{v}^T{)}^T=I-\frac{1}{\alpha }v{v}^T=U$
2. ortogonalità: $U^{T}U=I$

Complessità computazionale

Sia $U$ la trasformazione elementare di Householder associata al vettore $v\ne 0$, e $y\in {\mathbb{R}}^n$ un vettore. Si vuole calcolare $z=Uy$.

Non è necessario calcolare la matrice U, basta applicare la proprietà distributiva e associativa come:

$$z=Uy=(I-\frac{1}{\alpha }v{v}^T)y=y-\frac{1}{\alpha }v(v^{T}y)$$

Fattorizzazione

L’idea è quella di utilizzare le trasformazioni elementari come quelle di Guass, per eliminare gli elementi del triangolo inferiore della matrice A:

$$U_{n-1}...U_{1}A=R$$

Al passo k, ovviamente, la matrice $U_k$ è costruita in modo da eliminare nel prodotto tutti gli elementi della colonna k dalla riga k+1 alla riga n.

Proprietà

Dato $z\in {\mathbb{R}}^n$, $z\ne 0$ e $U$ definita come la trasformazione di Householder associata al vettore $v=z+\sigma e_1$, con $e_1$ prima colonna matrice identità di ordine $n$ e $\sigma =||z||$, si ha che:

$$Uz=-\sigma e_1=\left(\begin{array}{c}-\sigma \\ 0\\ ...\\ 0\end{array}\right)$$