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 decomposizione QR di una matrice.

Definizione e proprietà

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

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

Q = I − 2 vv^T.

La matrice di Householder ha le seguenti proprietà:

• è simmetrica: Q = Q^T
• è ortogonale: Q^-1 = Q^T
• quindi essa è anche involutoria: Q² = I.

Si trova che Q, agendo come descritto sopra, riflette effettivamente un punto X (che viene rappresentato con il suo vettore posizione x):

Qx = x − 2 vv^Tx = x − 2 <v,x> v,

dove il costrutto <...,...> denota il prodotto scalare. Si noti che <v,x> fornisce la distanza di X dall'iperpiano.

Applicazione: decomposizione QR

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 e₁ è il vettore (1,0,...,0)^T, e se || ... || denota la norma euclidea, si considerano le costruzioni

u = x − αe₁,

v = u / ||u||,

Q = I - 2 vv^T .

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 aspetto m × n nella forma triangolare superiore. Innanzitutto si moltipliplica A per la matrice di Householder Q₁ ottenuta sceglendo 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 la A mediante una matrice di Housholder Q'₂. Si noti che Q'₂ è più piccola della Q₁. Poiché vogliamo che sia reale per operare su Q₁A 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 = Q_t...Q₂Q₁A

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

Q = Q₁Q₂...Q_t,

A = QR è una decomposizione QR di A.

Questo metodo risulta numericamente stabile.