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 $𝐱$ rispetto ad un iperpiano, definito come ortogonale ad un versore $𝐮$, è data da:

$𝐱-2⟨𝐱,𝐮⟩𝐮=𝐱-2𝐮({𝐮}^{\text{T}}𝐱)$

dove $⟨,⟩$ denota il prodotto scalare euclideo, analogo al prodotto tra matrici, che definisce la distanza di $𝐱$ dall'iperpiano, mentre ${𝐮}^T$ 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:

$U=I-2𝐮{𝐮}^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𝐮{𝐮}^T{)}^T=I-2(𝐮{𝐮}^T{)}^T=I-2(({𝐮}^T{)}^T{𝐮}^T)=I-2𝐮{𝐮}^T=U$

• è ortogonale, ovvero $U^T=U^{-1}$, cioè $U^{T}U=I$. Infatti:

$\begin{array}{cc}{U}^{T}U& =UU\\ & =(I-2𝐮{𝐮}^T)(I-2𝐮{𝐮}^T)\\ & =I-4𝐮{𝐮}^T+4𝐮\underset{\Vert 𝐮\Vert =1}{\underbrace{{𝐮}^T𝐮}}{𝐮}^T\\ & =I-4𝐮{𝐮}^T+4𝐮{𝐮}^T\\ & =I\end{array}$

• 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:

$𝐱=\left(\begin{array}{c}{x}_1\\ ⋮\\ x_n\end{array}\right){𝐞}_1=\left(\begin{array}{c}1\\ 0\\ ⋮\\ 0\end{array}\right)$

e si definisce:

$\sigma =\Vert 𝐱\Vert 𝐯=𝐱+\sigma {𝐞}_1=\left(\begin{array}{c}{x}_1+\sigma \\ x_2\\ ⋮\\ x_n\end{array}\right)$

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

$U𝐱=\left(\begin{array}{c}-\sigma \\ 0\\ ⋮\\ 0\end{array}\right)$

Infatti, definendo $\frac{1}{\lambda }=\alpha$ dove

$\alpha =\frac{\Vert 𝐯{\Vert }^2}{2}=\frac{{𝐯}^T𝐯}{2}=\frac{(𝐱+\sigma {𝐞}_1{)}^T(𝐱+\sigma {𝐞}_1)}{2}=\frac{\stackrel{\Vert 𝐱{\Vert }^2={\sigma }^2}{\overbrace{{𝐱}^T𝐱}}+2\sigma x_1+{\sigma }^2}{2}={\sigma }^2+\sigma x_1$

si ha:

$U𝐱=(I-\frac{1}{\alpha }𝐯{𝐯}^T)𝐱=𝐱-\frac{1}{\alpha }(𝐱+\sigma {𝐞}_1){(𝐱+\sigma {𝐞}_1)}^T𝐱=𝐱-\frac{1}{\alpha }(𝐱+\sigma {𝐞}_1)({\sigma }^2+\sigma x_1)=𝐱-\frac{1}{\alpha }(𝐱+\sigma {𝐞}_1)\alpha =𝐱-𝐱-\sigma {𝐞}_1=-\sigma {𝐞}_1$

La fattorizzazione QR

Template:Vedi anche Sia $𝐱$ 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 $𝐱$). Se ${𝐞}_1$ è il vettore $(1,0,\dots ,0{)}^T$, si considerino:

$𝐮=𝐱-\alpha {𝐞}_1𝐯=\frac{𝐮}{\Vert 𝐮\Vert }Q=I-2𝐯{𝐯}^t$

Data la matrice di Householder $Q$, per quanto detto sopra si ha:

$Q𝐱=(\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 $𝐱$ 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=\left[\begin{array}{cccc}{\alpha }_1& \star & \dots & \star \\ 0& & & \\ ⋮& & A^{\prime }& \\ 0& & & \end{array}\right]$

Questa modifica può essere ripetuta per $A^{\prime }$ 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^{\prime }$ è necessario espandere questa nella parte superiore sinistra, riempiendola di entrate 1, o in generale:

$Q_k=\left[\begin{array}{cc}{I}_{k-1}& 0\\ 0& {Q_k}^{\prime }\end{array}\right]$

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.

Bibliografia

• Template:Cita libro
• Template:EnHouseholder, A. S. Principles of Numerical Analysis. New York: McGraw-Hill, pp. 135–138, 1953.
• Template:EnLehoucq, R. B. "The Computation of Elementary Unitary Matrices." ACM Trans. Math. Software 22, 393-400, 1996.
• Template:EnTrefethen, L. N. and Bau, D. III. Numerical Linear Algebra. Philadelphia, PA: SIAM, 1997.

Voci correlate

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