# Transformação de Householder

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 v{\textstyle v} (um vetor de comprimento 1{\textstyle 1}) que é ortogonal ao plano. A reflexão de um ponto x{\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 v{\textstyle v} é dado como um vetor coluna unitário com conjugado transposto v$^H$.{\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 I{\textstyle I} é a matriz de identidade.

#### Propriedades

A matriz de Householder tem as seguintes propriedades:
* é Hermitiana: P=P$^H$, {\textstyle P=P^{\textsf {H}}, }
* é unitária: P$^{−1}$=P$^H$, {\textstyle P^{-1}=P^{\textsf {H}}, }
* consequentemente, é involutiva: P$^2$=I.{\textstyle P^{2}=I.}
* Uma matriz de Householder tem autovalores ±1.{\textstyle \pm 1.} Para ver isto, note que se u{\textstyle u} é ortogonal ao vetor v{\textstyle v} que foi utilizado para criar o refletor, então Pu=u, {\textstyle Pu=u, } ou seja, 1{\textstyle 1} é um autovalor de multiplicidade n−1, {\textstyle n-1, } uma vez que existem n−1{\textstyle n-1} vetores linearmente independentes ortogonais a v.{\textstyle v.} Além disso, observe que Pv=−v{\textstyle Pv=-v}e assim −1{\textstyle -1} é um autovalor com multiplicidade 1.{\textstyle 1.}
* O determinante de um refletor de Householder é −1, {\textstyle -1, } uma vez que o determinante de uma matriz é o produto de seus autovalores e, neste caso, um deles é −1{\textstyle -1} e o restante é 1{\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 (i, i){\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 r, {\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 r, {\textstyle r, } constrói-se o vetor v:{\textstyle v:}
$v^{(1)}={\begin{bmatrix}v_{1}\\v_{2}\\\vdots \\v_{n}\end{bmatrix}},$
em que v$_1$=0, {\textstyle v_{1}=0, } v$_2$=a$_{21}$−α/2r {\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 P$^1${\textstyle P^{1}} e calculado A$^{(2)}${\textstyle A^{(2)}} o processo é repetido para k=2, 3, …, n−2{\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$_3$ 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 A$_2${\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 v, {\textstyle v, } como já foi dito anteriormente. Uma transformação unitária U{\textstyle U} de ordem N{\textstyle N}-por- N{\textstyle N}satisfaz UU$^H$=I.{\textstyle UU^{\textsf {H}}=I.} O cálculo do determinante (N{\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 λ$_i${\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, UU$^T$=I.{\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.