Transformação de Householder – Wikipédia, a enciclopédia livre
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7b/Householder.svg/220px-Householder.svg.png)
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.[1]
O seu análogo em espaços com produto interno mais gerais é o operador de Householder.
Definição
[editar | editar código-fonte]Transformação
[editar | editar código-fonte]O hiperplano de reflexão pode ser definido por um vetor unitário (um vetor de comprimento ) que é ortogonal ao plano. A reflexão de um ponto em relação a este hiperplano é a transformação linear:
em que é dado como um vetor coluna unitário com conjugado transposto
Matriz de Householder
[editar | editar código-fonte]A matriz construída a partir dessa transformação pode ser expressa em termos de um produto externo como:
é conhecida como a matriz de Householder, em que é a matriz de identidade.
Propriedades
[editar | editar código-fonte]A matriz de Householder tem as seguintes propriedades:
- é Hermitiana:
- é unitária:
- consequentemente, é involutiva:
- Uma matriz de Householder tem autovalores Para ver isto, note que se é ortogonal ao vetor que foi utilizado para criar o refletor, então ou seja, é um autovalor de multiplicidade uma vez que existem vetores linearmente independentes ortogonais a Além disso, observe que e assim é um autovalor com multiplicidade
- O determinante de um refletor de Householder é uma vez que o determinante de uma matriz é o produto de seus autovalores e, neste caso, um deles é e o restante é (como no ponto anterior).
Aplicações
[editar | editar código-fonte]Óptica geométrica
[editar | editar código-fonte]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
[editar | editar código-fonte]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
[editar | editar código-fonte]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 daquele produto.
Tridiagonalização
[editar | editar código-fonte]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 e que são:
A partir de e constrói-se o vetor
em que e
para cada
Então calcula-se:
Tendo encontrado e calculado o processo é repetido para como segue:
Continuando desta forma, forma-se a matriz tridiagonal e simétrica.
Exemplos
[editar | editar código-fonte]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 A3 usando o método de Householder.
Seguindo-se os passos método de Householder, tem-se:
A primeira matriz de Householder:
Usando para formar
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
[editar | editar código-fonte]A transformação de Householder é uma reflexão em relação a um hiperplano com vetor normal unitário como já foi dito anteriormente. Uma transformação unitária de ordem -por-satisfaz O cálculo do determinante (-é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 tem módulo um. Isso pode ser visto de forma rápida e direta:
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, 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.[2]
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
[editar | editar código-fonte]- ↑ «Unitary Triangularization of a Nonsymmetric Matrix». Journal of the ACM. 5. MR 0111128. doi:10.1145/320941.320947
- ↑ «The canonical coset decomposition of unitary matrices through Householder transformations». Journal of Mathematical Physics. 51. Bibcode:2010JMP....51h2101C. arXiv:1008.2477
. doi:10.1063/1.3466798
- «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