Transformació 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 e₁. La transformació de Householder calcula la reflexió per la línia de punts (que és la bisectriu de l'angle entre x i e₁). 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

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:

${\displaystyle x-2\langle x,v\rangle v=x-2v(v^{\text{H}}x)}$,

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

${\displaystyle P=I-2vv^{\text{H}}\,}$,

on I és la matriu identitat.

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

• és hermítica: ${\displaystyle P=P^{\text{H}}}$,
• és unitària: ${\displaystyle P^{-1}=P^{\text{H}}}$,
• per tant, és una involució: ${\displaystyle P^{2}=I}$.
• Una matriu de Householder té valors propis ${\displaystyle \pm 1}$. Per veure això, notem que si ${\displaystyle u}$ és ortogonal al vector ${\displaystyle v}$ que s'ha utilitzat per crear el reflector, llavors ${\displaystyle Pu=u}$, és a dir, 1 és un valor propi de multiplicitat ${\displaystyle n-1}$, ja que hi ha ${\displaystyle n-1}$ vectors independents ortogonals a ${\displaystyle v}$. Addicionalment, cal notar que ${\displaystyle Pv=-v}$ 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

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ó

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:

${\displaystyle \alpha =-\operatorname {sgn} (a_{21}){\sqrt {\sum _{j=2}^{n}a_{j1}^{2}}}}$;

${\displaystyle r={\sqrt {{\frac {1}{2}}(\alpha ^{2}-a_{21}\alpha )}}}$;

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

${\displaystyle v^{(1)}={\begin{bmatrix}v_{1}\\v_{2}\\\vdots \\v_{n}\end{bmatrix}}}$,

on ${\displaystyle v_{1}=0;}$, ${\displaystyle v_{2}={\frac {a_{21}-\alpha }{2r}}}$, i

${\displaystyle v_{k}={\frac {a_{k1}}{2r}}}$ per k = 3, 4, ..., n.

Llavors calculem:

${\displaystyle P^{1}=I-2v^{(1)}(v^{(1)})^{\text{T}}}$,

${\displaystyle A^{(2)}=P^{1}AP^{1}}$.

Un cop trobada ${\displaystyle P^{1}}$ i calculada ${\displaystyle A^{(2)}}$, es repeteix el procés per a k = 2, 3, ..., n-1 de la següent manera:

${\displaystyle \alpha =-\operatorname {sgn} (a_{k+1,k}^{k}){\sqrt {\sum _{j=k+1}^{n}(a_{jk}^{k})^{2}}}}$;

${\displaystyle r={\sqrt {{\frac {1}{2}}(\alpha ^{2}-a_{k+1,k}^{k}\alpha )}}}$;

${\displaystyle v_{1}^{k}=v_{2}^{k}=\cdots =v_{k}^{k}=0;}$

${\displaystyle v_{k+1}^{k}={\frac {a_{k+1,k}^{k}-\alpha }{2r}}}$

${\displaystyle v_{j}^{k}={\frac {a_{jk}^{k}}{2r}}}$ per j = k + 2, k + 3, ..., n

${\displaystyle P^{k}=I-2v^{(k)}(v^{(k)})^{\text{T}}}$

${\displaystyle A^{(k+1)}=P^{k}A^{(k)}P^{k}}$

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

Exemples

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

Sigui

${\displaystyle A={\begin{pmatrix}4&1&-2&2\\1&2&0&1\\-2&0&3&-2\\2&1&-2&-1\end{pmatrix}}}$

la matriu que volem tridiagonalitzar.

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

• La primera matriu de Householder:

${\displaystyle Q_{1}={\begin{pmatrix}1&0&0&0\\0&-1/3&2/3&-2/3\\0&2/3&2/3&1/3\\0&-2/3&1/3&2/3\end{pmatrix}}}$

• Calculem

${\displaystyle A_{1}=Q_{1}AQ_{1}={\begin{pmatrix}4&-3&0&0\\-3&10/3&1&4/3\\0&1&5/3&-4/3\\0&4/3&-4/3&-1\end{pmatrix}}}$

• Utilitzem ${\displaystyle A_{1}}$ per calcular

${\displaystyle Q_{2}={\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&-3/5&-4/5\\0&0&-4/5&3/5\end{pmatrix}}}$

• Finalment,

${\displaystyle A_{2}=Q_{2}A_{1}Q_{2}={\begin{pmatrix}4&-3&0&0\\-3&10/3&-5/3&0\\0&-5/3&-33/25&-68/75\\0&0&-68/75&149/75\end{pmatrix}}}$

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

Vegeu també: Rotació (matemàtiques)

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à UU^H=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:

${\displaystyle {\frac {{\text{Traça}}(UU^{\text{H}})}{N}}={\frac {\sum _{j=2}^{N}|\lambda _{j}|^{2}}{N}}=1}$

${\displaystyle \det(UU^{\text{H}})=\prod _{j=1}^{N}|\lambda _{j}|^{2}=1}$

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 UU^T=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

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

• LaBudde, C.D. «The reduction of an arbitrary real square matrix to tridiagonal form using similarity transformations». Mathematics of Computation. American Mathematical Society, 17, 84, 1963, pàg. 433–437. DOI: 10.2307/2004005. JSTOR: 2004005.
• Morrison, D.D. «Remarks on the Unitary Triangularization of a Nonsymmetric Matrix». Journal of the ACM, 7, 2, 1960, pàg. 185–186. DOI: 10.1145/321021.321030.
• Cipra, Barry A. «The Best of the 20th Century: Editors Name Top 10 Algorithms». SIAM News. Society for Industrial and Applied Mathematics, 33, 4, 2000, pàg. 1. Arxivat de l'original el 2018-03-28 [Consulta: 29 maig 2016].
• Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. «Section 11.3.2. Householder Method». A: Numerical Recipes: The Art of Scientific Computing. 3a edició. New York: Cambridge University Press, 2007. ISBN 978-0-521-88068-8.  Arxivat 2011-08-11 a Wayback Machine.

Vegeu també

• Factorització de matrius
• Factorització QR

Enllaços externs

• Householder Transformations Arxivat 2016-05-14 a Wayback Machine. a California State University, Fullerton