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 $v$ (um vetor de comprimento $1$) que é ortogonal ao plano. A reflexão de um ponto $x$ em relação a este hiperplano é a transformação linear:

$$x-2⟨x,v⟩v=x-2v\left(v^{\mathsf{\text{H}}}x\right),$$

em que $v$ é dado como um vetor coluna unitário com conjugado transposto $v^{\mathsf{\text{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-2v{v}^{\mathsf{\text{H}}}$$

é conhecida como a matriz de Householder, em que $I$ é a matriz de identidade.

Propriedades

A matriz de Householder tem as seguintes propriedades:

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

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

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

$$v^{(1)}=\left[\begin{array}{c}{v}_1\\ v_2\\ ⋮\\ v_n\end{array}\right],$$

em que $v_1=0,$ $v_2=\frac{a_{21}-\alpha }{2r}$e

$$v_k=\frac{a_{k1}}{2r}$$ para cada $k=3,4\dots n$

Então calcula-se:

$$\begin{array}{cc}{P}^1& =I-2v^{(1)}{\left(v^{(1)}\right)}^{\mathsf{\text{T}}}\\ A^{(2)}& =P^{1}A{P}^1\end{array}$$

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

$$\begin{array}{cc}\alpha & =-\mathrm{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}({\alpha }^2-a_{k+1,k}^k\alpha )}\\ 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,\dots ,n\\ P^k& =I-2v^{(k)}{\left(v^{(k)}\right)}^{\mathsf{\text{T}}}\\ A^{(k+1)}& =P^k{A}^{(k)}{P}^k\end{array}$$

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.

$$𝐀=\left[\begin{array}{cccc}4& 1& -2& 2\\ 1& 2& 0& 1\\ -2& 0& 3& -2\\ 2& 1& -2& -1\end{array}\right],$$

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

A primeira matriz de Householder:

$$\begin{array}{cc}{P}_1& =\left[\begin{array}{cccc}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{array}\right],\\ A_2=P_{1}A{P}_1& =\left[\begin{array}{cccc}4& -3& 0& 0\\ -3& 10/3& 1& 4/3\\ 0& 1& 5/3& -4/3\\ 0& 4/3& -4/3& -1\end{array}\right],\end{array}$$

Usando $A_2$ para formar

$$\begin{array}{cc}{P}_2& =\left[\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& -3/5& -4/5\\ 0& 0& -4/5& 3/5\end{array}\right],\\ A_3=P_2{A}_2{P}_2& =\left[\begin{array}{cccc}4& -3& 0& 0\\ -3& 10/3& -5/3& 0\\ 0& -5/3& -33/25& 68/75\\ 0& 0& 68/75& 149/75\end{array}\right],\end{array}$$

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,$ como já foi dito anteriormente. Uma transformação unitária $U$ de ordem $N$-por-$N$satisfaz $U{U}^{\mathsf{\text{H}}}=I.$ O cálculo do determinante ($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 ${\lambda }_i$ tem módulo um. Isso pode ser visto de forma rápida e direta: $$\frac{\mathrm{Trace}\left(U{U}^{\mathsf{\text{H}}}\right)}{N}=\frac{\sum _{j=2}^N{\left|{\lambda }_j\right|}^2}{N}=1,\det \left(U{U}^{\mathsf{\text{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, $U{U}^{\mathsf{\text{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

• Predefinição:Citar periódico
• Predefinição:Citar periódico
• Predefinição:Citar periódico (Aqui, a Transformação de Householder é citada como um dos 10 melhores algoritmos deste século)
• Predefinição:Citar livro