Método de Householder

Teoria Completa

Introdução

Faaaaaaaala meus caros, nós acabamos de ver o método de Francis, certo? Ele também era conhecido como QR (e nós já vimos bem o motivo disso, já que consistia em transformar tudo em Q e R).

Nós utilizamos o método Q R para reduzir uma matriz tridiagonal simétrica a uma matriz semelhante que seja quaaaaaaaaaaaase diagonal.

Onde os elementos na diagonal da matriz reduzida são aproximações para os autovalores da matriz dada.

Mas no caso do método desenvolvido por um tal de Alston Householder que serve para reduzir a matriz simétrica arbitrária a uma matriz tridiagonal semelhante. Mesmo que pareçam muiiito, há nuances em um que não são observadas em outros hahaha.

O método de Householder é utilizado para achar uma matriz B tridiagonal semelhante a uma dada matriz simétrica A. Para isso, é necessário fazer algumas transformações!!!

Transformações de Householder

Uma matriz P   ∈   R n × n da forma:

P = I -   2 v v T

Essa forma é chamada de transformação de Householder e possui as propriedades de simetria e ortogonalidade.

Nós geralmente temos um vetor qualquer x que é multiplicado por P , e sua imagem é refletida no hiperplano v .

A transformação de Householder é muito usada para zerar os elementos de um vetor. Esse x ∈   R n e não deve ser nulo.

Com isso encontramos P x ficamos com:

P x = x - 2 v ( v T x )

Chamamos isso de hiperplano de reflexão e pode ser definido como um vetor unitário que é ortogonal ao plano, oooooooooooooooou seja neném, é a sua transformação linear.

Matriz de Householder e Tridiagonalização

Para transformar a matriz Householder para cada etapa a primeira coisa necessária é determinar α e r , que são:

α = - s g n ( a 21 ) ∑ j = 2 n a j 1 2

r = 1 2 ( α 2 - a 21 α )

Com α e r , construímos o vetor v :

v ( 1 ) = v 1 v 2 ⋮ v n

Em que :

v 1 = 0

v 2 = a 21 - α 2 r

v k = a k 1 2 r

k = 3,4 … n

Então calculamos:

P 1 = I -   2 v 1 v 1 T

A ( 2 ) = P 1 A P 1

Tendo encontrado P e calculado A , o processo é repetido para k =   2 ,   3 . . .   n - 2 .

Usando as fórmulas abaixo:

α = - s g n a k + 1 ,     k k ∑ j = k + 1 n a j k k 2 1 2

r = 1 2 α 2 - a k + 1 ,   k k α

v 1 1 = v 2 2 = v 3 3 = … = v k k = 0

v k + 1 k = a k + 1 , k k - α 2 r

v j k = a j k k 2 r , para j = k + 2 ,   k + 3 , … n

P k = I - 2 v k v k T

A k + 1 = P k A k P k

Repetimos o processo até que a variação seja menor que o erro!

Bora calcular exercícios que você já vai entender!

Expandir

Exercício Resolvido #1

Adaptado de Burden, Richard L. Burden | J. Douglas Faires | Annette M. Análise Numérica - Tradução da 10ª edição norte-americana.

Existe um modelo de algoritmo que executa o método de Householder (apesar da multiplicação de matrizes poder ser contornada). Descreva as entradas, saídas e e passos 1 e 2 para a implementação desse método.

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Entrada: A primeira coisa que fazemos para definir e implementar um algoritmo é definir quais são as entradas do meu programa.

Nesse caso vamos precisar colocar no programa, ou pedir para que o usuário insira o tamanho/dimensão da matriz e coloque valores para a matriz A (para ocupar cada termo da matriz).

Passo 2

Passo 1 : Definimos a quantidade de termos k = 1 ,   . . .   ,   n - 1 e pedimos para o programa executar até atender o critério de parada.

Passo 2: Faça

q = ∑ j = k + 1 n ( a j k ( k ) ) 2

Passo 3

Escrever passo aqui

Saídas: nesse caso saí a cada iteração uma matriz A ( n - 1 ) e A a cada passo pode ser sobrescrita e substituída pelo atual.

Resposta

Entrada: Dimensão n, matriz A.

Passos: k e somatório.

Saída: A novo.

Exercício Resolvido #2

Burden, Richard L. Burden | J. Douglas Faires | Annette M. Análise Numérica - Tradução da 10ª edição norte-americana.

As transformações de Householder preservam ângulos e comprimentos? Por que sim ou Por que não?

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Sim.

Passo 2

Sim, já que trata-se da multiplicação de um vetor por uma matriz ortogonal e matrizes ortogonais preservam ângulos e comprimentos.

Resposta

Sim.

Exercício Resolvido #3

Adaptado de Burden, Richard L. Burden | J. Douglas Faires | Annette M. Análise Numérica - Tradução da 10ª edição norte-americana e Wikipédia.

Verdadeiro e falso.

A matriz de Householder ter as seguintes características:

  1. Não é uma matriz hermitiana e P ≠ P H .
  2. É uma matriz unitária onte P - 1 = P H .
  3. A matriz de Householder tem autovalores diferentes de 1.
MOSTRAR SOLUÇÃO COMPLETA

Passo 1

  1. Não é uma matriz hermitiana e P ≠ P H .
  2. Falso. A matriz é realmente uma matriz hermitiana que basicamente é aquela matriz que é idêntica a sua transposta.

    Passo 2

  3. É uma matriz unitária onte P - 1 = P H .
  4. Verdadeiro. Trata-se de uma matriz n × n U que satisfaz   U * U = U U * = I n .

    Passo 3

  5. A matriz de Householder tem autovalores diferentes de 1.

Falso. Uma matriz de Householder tem autovalores ±   1 . Para ver isto, note que se u é ortogonal ao vetor v   que foi utilizado para criar o refletor, então P   u   =   u , ou seja, 1 autovalor de multiplicidade n   -   1 , uma vez que existem n   -   1 vetores linearmente independentes ortogonais a v   . Além disso, observe que P   v   =   -   v e assim –   1 é um autovalor com multiplicidade.

Resposta

(a) F

(b) V

(c) F

Exercício Resolvido #4

Elaboração Própria

Aplique as transformações de Householder à matriz 4   × 4 para calcular A ( 2 ) (primeira iteração).

A = 1 1 1 1 2 3 4 2 0 0 6 - 5 0 0 2 1

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Para a primeira aplicação de uma transformação de Householder temos que α e r , que são:

α = - s g n a k + 1 ,     k k ∑ j = k + 1 n a j k k 2 1 2

r = 1 2 α 2 - a k + 1 ,   k k α

No nosso caso, ainda estamos em k = 1 :

α = - s g n ( a 21 ) ∑ j = 2 n a j 1 2

r = 1 2 ( α 2 - a 21 α )

Onde:

α = - 2 ∑ j = 2 4 a j 1 2 1 2 = - 4

r = 1 2 - 4 2 - 2 - 4 1 / 2 = 12

Passo 2

Para escrever o vetor v 1 fazemos:

v 1 =   0

Para v 2 :

v k + 1 k = a k + 1 , k k - α 2 r

v 2 =   2 - ( - 4 ) 2 . 12 = 12 4

Para o v 3 e o v 4 :

v j k = a j k k 2 r , j = k + 2 ,   k + 3 , … n

v 3 = 0 2 . 12 = 0

v 4 = 0 2 . 12 = 0

Vetor:

v 1 =   0 12 4 0 0 T

Passo 3

Então calculamos:

P k = I - 2 v k v k T

P 1 = I -   2 v 1 v 1 T

P ( 1 ) = 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 - 2 0 12 4 0 0 0 12 4 0 0

P ( 1 ) = 1 0 0 0 0 - 0,5 0 0 0 0 1 0 0 0 0 1

Passo 4

Então calculamos:

A ( 2 ) = P 1 A P 1

1 0 0 0 0 - 0,5 0 0 0 0 1 0 0 0 0 1 . 1 1 1 1 2 3 4 2 5 0 6 - 5 0 0 2 1 . 1 0 0 0 0 - 0,5 0 0 0 0 1 0 0 0 0 1

A ( 2 ) = 1 - 0,5 1 1 - 1 0,75 - 2 - 1 5 0 6 - 5 0 0 2 1

Resposta

A ( 2 ) = 1 - 0,5 1 1 - 1 0,75 - 2 - 1 5 0 6 - 5 0 0 2 1

Exercício Resolvido #5

Adaptado de Burden, Richard L. Burden | J. Douglas Faires | Annette M. Análise Numérica - Tradução da 10ª edição norte-americana

O exercício anterior foi bem extenso né? Mas ainda falta um bom tanto para acabar. Agora, utilizando o exercício anterior, calcule o A ( 3 ) do problema anterior. Lembrando que:

A ( 2 ) = 4 - 3 0 0 - 3 10 / 3 1 4 / 3 0 1 5 / 3 - 4 / 3 0 4 / 3 - 4 / 3 - 1

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Para a primeira aplicação de uma transformação de Householder temos que α e r , que são:

α = - s g n a k + 1 ,     k k ∑ j = k + 1 n a j k k 2 1 2

r = 1 2 α 2 - a k + 1 ,   k k α

Como estamos em k = 2 :

α = - s g n ( a 32 ( 2 ) ) ∑ j = 3 n a j 2 2 2

r = 1 2 ( α 2 - a 32 ( 2 ) α )

α = - 1 ∑ j = 3 4 a j 2 2 2 1 2 = - 5 3

r = 1 2 - 5 3 2 - a 32 2 - 5 3 = 2 5 3

Passo 2

Para escrever o vetor v ( 2 ) fazemos:

v 1 2 =   0

v 2 2 = 0

Para o v 3 2 :

v k + 1 k = a k + 1 , k k - α 2 r