Transformação de Householder

Origem: Wikipédia, a enciclopédia livre.
Saltar para a navegação Saltar para a pesquisa

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]

  1. «Unitary Triangularization of a Nonsymmetric Matrix». Journal of the ACM. 5. MR 0111128. doi:10.1145/320941.320947 
  2. «The canonical coset decomposition of unitary matrices through Householder transformations». Journal of Mathematical Physics. 51. Bibcode:2010JMP....51h2101C. arXiv:1008.2477Acessível livremente. doi:10.1063/1.3466798