Vés al contingut

Transformació de Householder

De la Viquipèdia, l'enciclopèdia lliure
(S'ha redirigit des de: Reflexió de Householder)
Transformació de Householder per una descomposició QR: l'objectiu és trobar una transformació lineal que canviï el vector x en un vector de la mateixa longitud i que sigui col·lineal a e1. La transformació de Householder calcula la reflexió per la línia de punts (que és la bisectriu de l'angle entre x i e1). L'angle màxim amb aquesta transformació és de 45 graus.

En el camp matemàtic de l'àlgebra lineal, una transformació de Householder (també coneguda com a reflexió de Householder) és una transformació lineal que descriu una reflexió respecte a un pla o hiperplà que conté l'origen. Les transformacions de Householder s'usen àmpliament en àlgebra lineal numèrica, com a eina per realitzar descomposicions QR i en el primer pas de l'algorisme QR. La transformació de Householder fou introduïda l'any 1958 per Alston Scott Householder.[1]

El concepte anàleg sobre espais prehilbertians generals és l'operador de Householder.

Definició i propietats

[modifica]
Un pla i dos dels seus vectors normals, ortogonals al pla

L'hiperplà de reflexió es pot definir mitjançant un vector unitari v (un vector de mòdul 1) que sigui ortogonal a l'hiperplà. La reflexió d'un punt x respecte a aquest hiperplà és:

,

on v està en forma de vector unitari columna amb transposat hermític vH. Això és una transformació lineal donada per la matriu de Householder:

,

on I és la matriu identitat.

La matriu de Householder té les següents propietats:

  • és hermítica: ,
  • és unitària: ,
  • per tant, és una involució: .
  • Una matriu de Householder té valors propis . Per veure això, notem que si és ortogonal al vector que s'ha utilitzat per crear el reflector, llavors , és a dir, 1 és un valor propi de multiplicitat , ja que hi ha vectors independents ortogonals a . Addicionalment, cal notar que , i per tant -1 és un valor propi amb multiplicitat 1.
  • El determinant d'un reflector de Householder és -1, ja que el determinant d'una matriu és igual al producte dels seus valors propis.

Aplicacions

[modifica]

En òptica geomètrica, la reflexió especular es pot expressar en termes de la matriu de Householder.

Hom pot emprar les reflexions de Householder per calcular descomposicions QR, fent primer una reflexió d'una columna de la matriu sobre un múltiple d'un vector de la base estàndard, calculant la matriu de la transformació, multiplicant-la per la matriu original, i després recorrent els menors (i, i) del producte i aplicant-hi el mateix procediment.

Les transformacions de Householder també s'utilitzen per tridiagonalitzar matrius simètriques, així com per transformar matrius no simètriques en una forma de Hessenberg.

Tridiagonalització

[modifica]

En el primer pas del procediment,[2] per tal de formar la matriu de Householder en cada pas, cal determinar α i r, que són:

;
;

A partir de α i r, construïm el vector v:

,

on , , i

per k = 3, 4, ..., n.

Llavors calculem:

,
.

Un cop trobada i calculada , es repeteix el procés per a k = 2, 3, ..., n-1 de la següent manera:

;
;
per j = k + 2, k + 3, ..., n

Continuant d'aquesta manera, hom obté la matriu tridiagonal i simètrica.

Exemples

[modifica]

En aquest exemple,[2] es transformarà la matriu donada en la matriu tridiagonal , semblant a la matriu original, mitjançant el mètode de Householder.

Sigui

la matriu que volem tridiagonalitzar.

Aplicant aquests passos del mètode de Householder, tenim:

  • La primera matriu de Householder:
  • Calculem
  • Utilitzem per calcular
  • Finalment,

Com podem veure, el resultat final és una matriu simètrica tridiagonal que és semblant a la matriu original. El procés finalitza després de dos passos.

Relacions computacionals i teòriques amb altres transformacions unitàries

[modifica]

La transformació de Householder és una reflexió respecte a un cert hiperplà, en concret l'hiperplà definit per un cert vector normal unitari v, com hem vist abans. Una transformació unitària U de dimensió N per N satisfà UUH=I. Prenent-ne el determinant (l'N-sima potència de la mitjana geomètrica) i la traça (proporcional a la mitjana aritmètica d'una matriu unitària, hom pot veure que els seus valors propis tenen mòdul 1. Això es pot veure de manera ràpida:

Com que la mitjana geomètrica i la mitjana aritmètica són iguals si els termes són iguals (vegeu Desigualtat entre les mitjanes aritmètica i geomètrica), hom té que els mòduls de tots els valors propis són iguals i, de fet, iguals a 1.

En el cas de matrius unitàries amb entrades reals, tenim matrius ortogonals, que verifiquen UUT=I. Hom pot veure fàcilment (vegeu Matriu ortogonal) que qualsevol matriu ortogonal es pot descompondre en un producte de rotacions 2×2, anomenades rotacions de Givens, i reflexions de Householder. Això és força intuïtiu, ja que la multiplicació d'un vector per una matriu ortogonal conserva la longitud del vector, i les rotacions i les reflexions són totes les operacions geomètriques (reals) que mantenen invariant la longitud d'un vector.

Està demostrat que les transformacions de Householder tenen una relació biunívoca amb la descomposició en classes laterals canòniques de matrius unitàries definida en teoria de grups, que es pot utilitzar per parametritzar els operadors unitaris d'una manera molt eficient.[3]

Finalment, cal notar que una sola transformació de Householder, de la mateixa manera que una sola transformació de Givens, pot actuar sobre totes les columnes d'una matriu, i així es pot veure el petit cost computacional quan s'apliquen a la descomposició QR i a la tridiagonalització. La contrapartida d'aquesta "optimalitat computacional" és que les operacions de Householder no es poden paral·lelitzar de manera eficient. Per això, hom prefereix utilitzar Householder sobre matrius denses en màquines seqüencials, mentre que hom prefereix Givens sobre matrius disperses, i en màquines paral·leles.

Referències

[modifica]
  1. Householder, A. S. «Unitary Triangularization of a Nonsymmetric Matrix». Journal of the ACM, 5, 4, 1958, pàg. 339–342. DOI: 10.1145/320941.320947.
  2. 2,0 2,1 Burden, Richard L.; Faires, J. Douglas. Numerical Analysis. 8a edició. Brooks Cole, 10 desembre 2004. ISBN 978-0534392000. 
  3. Cabrera, Renan; Strohecker, Traci; Rabitz, Herschel «The canonical coset decomposition of unitary matrices through Householder transformations». Journal of Mathematical Physics, 51, 8, 2010. DOI: 10.1063/1.3466798.

Bibliografia

[modifica]

Vegeu també

[modifica]

Enllaços externs

[modifica]