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 sorgente]

La riflessione rispetto ad un iperpiano può essere definita da un versore u (un vettore di lunghezza 1) ortogonale all'iperpiano.

Se u è dato come un vettore colonna unità e I è la matrice identità, la trasformazione lineare descritta sopra è data dalla matrice di Householder (u^T denota il trasposto del vettore u)

U =I - 2vv^T

La matrice di Householder ha le seguenti proprietà:

  • è simmetrica: U = U^T
    Dimostrazione: U^T = (I - 2vv^T)^T = I -2(vv^T)^T = I-2((v^T)^Tv^T) = I - 2vv^T = U
  • è ortogonale: U^T = U^{-1}, cioè U^TU=I
    Dimostrazione: \begin{align}
U^TU &= UU = Q^2\\
 &= (I-2uu^T)(I-2uu^T) \\
 &= I - 4uu^T + 4u\underbrace{u^Tu}_{\lVert u \rVert = 1}u^T \\
 &= I -4uu^T+4uu^T \\
 &=I
\end{align}
  • Si è quindi dimostrato che è involutoria: U^2=I

Dato un vettore v \ne 0, si considera u come il suo versore, cioè \frac{v}{\|v\|}, e U = I- \frac{1}{\alpha}vv^T con \alpha = \frac{\|v\|^2}{2}.

In particolare U agisce su un vettore x (che rappresenta un punto X) nel modo seguente: Ux = (I - \frac{1}{\alpha}vv^T)x = x - \frac{v^Tx}{\alpha}v (v^Tx è il prodotto scalare fra v ed x, che definisce la distanza di X dall'iperpiano)

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

Applicazione della matrice di trasformazione[modifica | modifica sorgente]

La matrice di Householder U può essere usata per annullare tutte le componenti di un vettore tranne la prima, nel modo seguente:

Siano  x = \begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix} e e_1 = \begin{pmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix}, si definisce  \sigma = \|x\| e  v = x + \sigma e_1 = \begin{pmatrix} x_1+\sigma \\ x_2 \\ \vdots \\ x_n \end{pmatrix}, si dimostra che Ux = \begin{pmatrix} -\sigma \\ 0 \\ \vdots \\ 0 \end{pmatrix}:

Consideriamo \alpha della definizione che abbiamo dato in precedenza:

\alpha = \frac{\|v\|^2}{2} = \frac{v^Tv}{2}
= \frac{(x+\sigma e_1)^T(x+\sigma e_1)}{2} 
= \frac{\overbrace{x^Tx}^{\|x\|^2=\sigma^2} + 2 \sigma x_1 + \sigma^2}{2}
= \sigma^2 + \sigma x_1

Consideriamo ora Ux:  Ux = (I-\frac{1}{\alpha}vv^T)x 
= x - \frac{1}{\alpha}(x+\sigma e_1)(x+ \sigma e_1)^Tx
= x - \frac{1}{\alpha}(x+\sigma e_1)(\sigma^2 + \sigma x_1) 
= x - \frac{1}{\alpha}(x+\sigma e_1)\alpha
= x - x - \sigma e_1 = -\sigma e_1

Applicazione: fattorizzazione QR[modifica | modifica sorgente]

La matrice Q può essere usata per riflettere un vettore in modo tale che tutte le sue coordinate eccetto una scompaiono. Sia x un arbitrario vettore colonna m-dimensionale di lunghezza |α| (per la stabilità numerica si assume che α abbia lo stesso segno della prima coordinata di x).

Se e1 è il vettore (1,0,...,0)T, e se || ... || denota la norma euclidea, si considerano le costruzioni

u = x − αe1,
v = u / ||u||,
Q = I - 2 vvT .

Per la matrice di Householder Q si ha

Qx = (α,0,...,0)T.

Questo genere di trasformazione può essere usato per trasformare gradualmente una matrice A di tipo m × n nella forma triangolare superiore. Innanzitutto si moltiplica A per la matrice di Householder Q1 ottenuta scegliendo 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 la A mediante una matrice di Housholder Q2. Si noti che Q2 è più piccola della Q1. Poiché vogliamo che sia reale per operare su Q1A invece di A' abbiamo bisogno di 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 ad

R = Qt...Q2Q1A

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

Q = Q1Q2...Qt,

A = QR è una decomposizione QR di A.

Questo metodo risulta numericamente stabile.

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