Trasformazione di Householder

Da Wikipedia, l'enciclopedia libera.

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à[modifica | modifica wikitesto]

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

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
\begin{align}
U^TU &= 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{align}

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

Applicazione della matrice di trasformazione[modifica | modifica wikitesto]

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

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

Infatti, definendo \alpha:

\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[modifica | modifica wikitesto]

Exquisite-kfind.png Per approfondire, vedi Decomposizione 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_1A = \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.

Bibliografia[modifica | modifica wikitesto]

  • (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.
  • (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.

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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