Transformação de Householder

Householder reflection for QR decomposition

Em álgebra linear, uma transformação de Householder (também conhecida como uma reflexão de Householder ou refletor elementar) é uma transformação linear que descreve uma reflexão em relação a um plano ou hiperplano que contém a origem. A transformação de Householder foi introduzida em 1958 por Alston Scott Householder.

O seu análogo em espaços com produto interno mais gerais é o operador de Householder.

Definição

Transformação

O hiperplano de reflexão pode ser definido por um vetor unitário ${\textstyle v}$ (um vetor de comprimento ${\textstyle 1}$) que é ortogonal ao plano. A reflexão de um ponto ${\textstyle x}$ em relação a este hiperplano é a transformação linear:

$$x-2\langle x,v\rangle v=x-2v\left(v^{\textsf {H}}x\right),$$

em que ${\textstyle v}$ é dado como um vetor coluna unitário com conjugado transposto ${\textstyle v^{\textsf {H}}.}$

Matriz de Householder

A matriz construída a partir dessa transformação pode ser expressa em termos de um produto externo como:

$$P=I-2(v\otimes v)=I-2vv^{\textsf {H}}$$

é conhecida como a matriz de Householder, em que ${\textstyle I}$ é a matriz de identidade.

Propriedades

A matriz de Householder tem as seguintes propriedades:

• é Hermitiana: ${\textstyle P=P^{\textsf {H}},}$
• é unitária: ${\textstyle P^{-1}=P^{\textsf {H}},}$
• consequentemente, é involutiva: ${\textstyle P^{2}=I.}$
• Uma matriz de Householder tem autovalores ${\textstyle \pm 1.}$ Para ver isto, note que se ${\textstyle u}$ é ortogonal ao vetor ${\textstyle v}$ que foi utilizado para criar o refletor, então ${\textstyle Pu=u,}$ ou seja, ${\textstyle 1}$ é um autovalor de multiplicidade ${\textstyle n-1,}$ uma vez que existem ${\textstyle n-1}$ vetores linearmente independentes ortogonais a ${\textstyle v.}$ Além disso, observe que ${\textstyle Pv=-v}$e assim ${\textstyle -1}$ é um autovalor com multiplicidade ${\textstyle 1.}$
• O determinante de um refletor de Householder é ${\textstyle -1,}$ uma vez que o determinante de uma matriz é o produto de seus autovalores e, neste caso, um deles é ${\textstyle -1}$ e o restante é ${\textstyle 1}$ (como no ponto anterior).

Aplicações

Óptica geométrica

Em óptica geométrica, a reflexão especular pode ser expressa em termos da matriz de Householder (reflexão especular#Formulação vetorial).

Álgebra linear numérica

As transformações de Householder são amplamente utilizadas na álgebra linear numérica, para realizar decomposiçes QR e são o primeiro passo do algoritmo QR. Elas também são amplamente utilizadas para a tridiagonalização de matrizes simétricas e para a transformação de matrizes não-simétricas para a forma de Hessenberg.

Decomposição QR

As reflexões de Householder podem ser usadas para calcular a decomposição QR refletindo primeiramente uma coluna de uma matriz sobre um múltiplo de um vetor da base canônica, calculando a matriz de transformação, multiplicando-a com a matriz original e, então, continuando recursivamente com os menores ${\textstyle (i,i)}$daquele produto.

Tridiagonalização

Este procedimento é retirado do livro de Análise Numérica, de Burden e Faires, 8ª Edição. No primeiro passo, para formar a matriz de Householder de cada etapa é preciso determinar ${\textstyle \alpha }$ e ${\textstyle r,}$ que são:

$${\begin{aligned}\alpha &=-\operatorname {sgn} \left(a_{21}\right){\sqrt {\sum _{j=2}^{n}a_{j1}^{2}}};\\r&={\sqrt {{\frac {1}{2}}\left(\alpha ^{2}-a_{21}\alpha \right)}};\end{aligned}}$$

A partir de ${\textstyle \alpha }$ e ${\textstyle r,}$ constrói-se o vetor ${\textstyle v:}$

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

em que ${\textstyle v_{1}=0,}$ ${\textstyle v_{2}={\frac {a_{21}-\alpha }{2r}}}$e

$$v_{k}={\frac {a_{k1}}{2r}}$$

para cada $k=3,4\ldots n$

Então calcula-se:

$${\begin{aligned}P^{1}&=I-2v^{(1)}\left(v^{(1)}\right)^{\textsf {T}}\\A^{(2)}&=P^{1}AP^{1}\end{aligned}}$$

Tendo encontrado ${\textstyle P^{1}}$ e calculado ${\textstyle A^{(2)}}$ o processo é repetido para ${\textstyle k=2,3,\ldots ,n-2}$ como segue:

$${\begin{aligned}\alpha &=-\operatorname {sgn} \left(a_{k+1,k}^{k}\right){\sqrt {\sum _{j=k+1}^{n}\left(a_{jk}^{k}\right)^{2}}}\\r&={\sqrt {{\frac {1}{2}}\left(\alpha ^{2}-a_{k+1,k}^{k}\alpha \right)}}\\v_{1}^{k}&=v_{2}^{k}=\cdots =v_{k}^{k}=0\\v_{k+1}^{k}&={\frac {a_{k+1,k}^{k}-\alpha }{2r}}\\v_{j}^{k}&={\frac {a_{jk}^{k}}{2r}}{\text{ for }}j=k+2,\ k+3,\ \ldots ,\ n\\P^{k}&=I-2v^{(k)}\left(v^{(k)}\right)^{\textsf {T}}\\A^{(k+1)}&=P^{k}A^{(k)}P^{k}\end{aligned}}$$

Continuando desta forma, forma-se a matriz tridiagonal e simétrica.

Exemplos

Este exemplo foi tirado do livro de Análise Numérica, de Richard L. Burden (Autor), J. Douglas Faires. Neste exemplo, a dada matriz é transformada em uma matriz semelhante tridiagonal A₃ usando o método de Householder.

$$\mathbf {A} ={\begin{bmatrix}4&1&-2&2\\1&2&0&1\\-2&0&3&-2\\2&1&-2&-1\end{bmatrix}},$$

Seguindo-se os passos método de Householder, tem-se:

A primeira matriz de Householder:

$${\begin{aligned}P_{1}&={\begin{bmatrix}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{bmatrix}},\\A_{2}=P_{1}AP_{1}&={\begin{bmatrix}4&-3&0&0\\-3&10/3&1&4/3\\0&1&5/3&-4/3\\0&4/3&-4/3&-1\end{bmatrix}},\end{aligned}}$$

Usando ${\textstyle A_{2}}$ para formar

$${\begin{aligned}P_{2}&={\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&-3/5&-4/5\\0&0&-4/5&3/5\end{bmatrix}},\\A_{3}=P_{2}A_{2}P_{2}&={\begin{bmatrix}4&-3&0&0\\-3&10/3&-5/3&0\\0&-5/3&-33/25&68/75\\0&0&68/75&149/75\end{bmatrix}},\end{aligned}}$$

Como se pode ver, o resultado final é uma matriz tridiagonal simétrica, que é similar à original. O processo é concluído depois de duas etapas.

Relação teórica e computacional com outras transformações unitárias

A transformação de Householder é uma reflexão em relação a um hiperplano com vetor normal unitário ${\textstyle v,}$ como já foi dito anteriormente. Uma transformação unitária ${\textstyle U}$ de ordem ${\textstyle N}$-por-${\textstyle N}$satisfaz ${\textstyle UU^{\textsf {H}}=I.}$ O cálculo do determinante (${\textstyle N}$-ésima potência da média geométrica) e do traço (proporcional à média aritmética) de uma matriz unitária revela que seus autovalores ${\textstyle \lambda _{i}}$ tem módulo um. Isso pode ser visto de forma rápida e direta:

$${\frac {\operatorname {Trace} \left(UU^{\textsf {H}}\right)}{N}}={\frac {\sum _{j=2}^{N}\left|\lambda _{j}\right|^{2}}{N}}=1,\quad \operatorname {det} \left(UU^{\textsf {H}}\right)=\prod _{j=1}^{N}\left|\lambda _{j}\right|^{2}=1.$$

Como as médias aritmética e geométrica são iguais se as variáveis são constantes (ver a desigualdade entre as médias aritmética e geométrica), pode-se estabelecer a alegação de que o módulo é um.

Para o caso de matrizes unitárias reais obtém-se matrizes ortogonais, ${\textstyle UU^{\textsf {T}}=I.}$ Segue-se diretamente (ver matriz ortogonal) que qualquer matriz ortogonal pode ser decomposta em um produto de rotações 2 por 2, chamadas de rotações de Givens, e reflexões de Householder. Isso tem um grande apelo intuitivo, já que a multiplicação de um vetor por uma matriz ortogonal preserva o comprimento do vetor, e as rotações e reflexões esgotam o conjunto de operações geométricas (com valores reais) que preservam o comprimento dos vetores.

Demonstrou-se que a transformação de Householder tem uma relação biunívoca com a decomposição canônica em cosets das matrizes unitárias definida em teoria de grupos, o que permite que os operadores unários sejam parametrizados de uma forma muito eficaz.

Finalmente, nota-se que uma única transformação de Householder, ao contrário de uma única transformação de Givens, pode atuar em todas as colunas de uma matriz e, como tal, apresenta o menor custo computacional para a decomposição QR e a tridiagonalização. O aspecto negativo desta optimalidade computacional é, naturalmente, que as operações de Householder não podem ser paralelizadas tão profundamente ou eficientemente. Como tal, é preferível usar Householder para matrizes densas em máquinas sequenciais, enquanto que Givens é preferível em matrizes esparsas, e/ou máquinas paralelas.

Referências

• «The reduction of an arbitrary real square matrix to tridiagonal form using similarity transformations». Mathematics of Computation. 17. JSTOR 2004005. MR 0156455. doi:10.2307/2004005 
• «Remarks on the Unitary Triangularization of a Nonsymmetric Matrix». Journal of the ACM. 7. MR 0114291. doi:10.1145/321021.321030 
• «The Best of the 20th Century: Editors Name Top 10 Algorithms». 33  (Aqui, a Transformação de Householder é citada como um dos 10 melhores algoritmos deste século)
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP. «Section 11.3.2. Householder Method». Numerical Recipes: The Art of Scientific Computing. [S.l.: s.n.] ISBN 978-0-521-88068-8