Trasformazione di Householder

concetto dell'algebra lineare

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

La riflessione di un punto   rispetto ad un iperpiano, definito come ortogonale ad un versore  , è data da:

 

dove   denota il prodotto scalare euclideo, analogo al prodotto tra matrici, che definisce la distanza di   dall'iperpiano, mentre   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:

 

dove   è la matrice identità.

La matrice di Householder ha le seguenti proprietà:

 
  • è ortogonale, ovvero  , cioè  . Infatti:
 
  • Si è così dimostrato che   è un'involuzione, ovvero  .
  • Possiede soltanto autovalori uguali a  .
  • Il determinante (prodotto degli autovalori) è  .

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

Applicazione della matrice di trasformazioneModifica

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

 

e si definisce:

 

Si ha, per una  con   opportuno, che:

 

Infatti, definendo   dove

 

si ha:

 

La fattorizzazione QRModifica

  Lo stesso argomento in dettaglio: Decomposizione QR.

Sia   un arbitrario vettore colonna m-dimensionale di lunghezza   (per la stabilità numerica del metodo si assume che   ha lo stesso segno della prima coordinata di  ). Se   è il vettore  , si considerino:

 

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

 

e questo risultato può essere usato per trasformare gradualmente una matrice   di tipo   nella forma triangolare superiore: innanzitutto si moltiplica   per la matrice di Householder   ottenuta scegliendo   per la sua prima colonna. Questa risulta in una matrice   che presenta zeri nella colonna sinistra, ad eccezione della sola prima riga:

 

Questa modifica può essere ripetuta per   mediante una matrice di Housholder  . Si noti che   è più piccola di  . Poiché si vuole che sia reale, per operare su   invece di   è necessario espandere questa nella parte superiore sinistra, riempiendola di entrate 1, o in generale:

 

Dopo   iterazioni di questo processo, con  , si giunge a:

 

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

 

la decomposizione   è una decomposizione QR di  . Questo metodo risulta numericamente stabile.

BibliografiaModifica

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

Collegamenti esterniModifica

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