Método de Householder

Ver Todos os Exercícios

Teoria

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!

Transformações de Householder

Matriz de Householder e Tridiagonalização

Exercícios Resolvidos

Exercício Resolvido #1

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.

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

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

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

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.

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

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

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

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

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

v 3 2 = 2 5

E o v 4 2 :

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

v 4 2 = 5 5

Vetor:

v =   0 0 2 5 5 5 T

Passo 3

Então calculamos:

P ( k ) = I - 2 v ( k ) v ( k ) T

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

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

P ( 2 ) = 1 0 0 0 0 1 0 0 0 0 - 3 / 5 - 4 / 5 0 0 - 4 / 5 3 / 5

Passo 4

Então calculamos:

A ( 2 ) = P 2 A P 2

1 0 0 0 0 1 0 0 0 0 - 3 / 5 - 4 / 5 0 0 - 4 / 5 3 / 5 . 4 1 - 2 2 1 2 0 1 - 2 0 3 - 2 2 1 - 2 - 1 . 1 0 0 0 0 1 0 0 0 0 - 3 / 5 - 4 / 5 0 0 - 4 / 5 3 / 5

A ( 3 ) = 4 - 3 0 0 - 3 10 / 3 - 5 / 3 0 0 - 5 / 3 - 33 / 25 68 / 75 0 0 68 / 75 149 / 75

Resposta

A ( 3 ) = 4 - 3 0 0 - 3 10 / 3 - 5 / 3 0 0 - 5 / 3 - 33 / 25 68 / 75 0 0 68 / 75 149 / 75

Exercício Resolvido #6

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

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

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 0 0 0 2 3 2 3 0 1 3 6 0 4 5 0 . 1 0 0 0 0 - 0,5 0 0 0 0 1 0 0 0 0 1

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

Resposta

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

Exercício Resolvido #7

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

A = 1 0 0 0 - 1 0,75 - 1 - 1,5 0 - 0,5 3 6 0 - 2 5 0

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 ) α )

α = - - 0,5 ∑ j = 3 4 a j 2 2 2 1 2 = 1,0308

r = 1 2 1,0308 2 - ( - 0,5 ) 1,0308 = 0 , 8882

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

v 3 2 = - 0,5 - 1,0308 ( 2 ) ( 0,8882 ) = - 0,8617

E o v 4 2 :

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

v 4 2 = - 2 ( 2 ) ( 0,8882 ) = - 1,1259

Vetor:

v =   0 0 - 0,8617 - 1,1259 T

Passo 3

Então calculamos:

P ( k ) = I - 2 v ( k ) v ( k ) T

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

P ( 2 ) = 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 - 2 0 0 - 0,8617 - 1,1259 0 0 - 0,8617 - 1,1259

P ( 2 ) = 1 0 0 0 0 1 0 0 0 0 - 0,4851 - 1,9404 0 0 - 1,9404 - 1,5353

Passo 4

Então calculamos:

A ( 2 ) = P 2 A P 2

1 0 0 0 0 1 0 0 0 0 - 0,4851 - 1,9404 0 0 - 1,9404 - 1,5353 . 1 0 0 0 - 1 0,75 - 1 - 1,5 0 - 0,5 3 6 0 - 2 5 0 . 1 0 0 0 0 1 0 0 0 0 - 0,4851 - 1,9404 0 0 - 1,9404 - 1,5353

A ( 3 ) = 1 0 0 0 - 1 0,75 3,3957 4,2434 0 4,1233 11,0595 23,1173 0 4,0408 29,1383 44,0652

Resposta

A ( 3 ) = 1 0 0 0 - 1 0,75 3,3957 4,2434 0 4,1233 11,0595 23,1173 0 4,0408 29,1383 44,0652

Exercício Resolvido #8

Aplique as transformações de Householder à matriz simétrica 4   × 4 para calcular A ( 2 ) na primeira iteração que produz uma matriz simétrica semelhante a A .

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

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:

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

r = 1 2 - 3 2 - 1 - 3 1 / 2 = 6

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 =   1 - ( - 3 ) 2 . 6 = 6 3

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 = - 2 2 . 6 = - 6 6

v 4 = 2 2 . 6 = 6 6

Vetor:

v 1 =   0 6 3 - 6 6 6 6 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 6 3 - 6 6 6 6 0 6 3 - 6 6 6 6

P ( 1 ) = 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

Passo 4

Então calculamos:

A ( 2 ) = P 1 A P 1

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 . 4 1 - 2 2 1 2 0 1 - 2 0 3 - 2 2 1 - 2 - 1 . 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

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

Resposta

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

Exercício Resolvido #9

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

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

v 3 2 = 2 5

E o v 4 2 :

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

v 4 2 = 5 5

Vetor:

v =   0 0 2 5 5 5 T

Passo 3

Então calculamos:

P ( k ) = I - 2 v ( k ) v ( k ) T

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

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

P ( 2 ) = 1 0 0 0 0 1 0 0 0 0 - 3 / 5 - 4 / 5 0 0 - 4 / 5 3 / 5

Passo 4

Então calculamos:

A ( 2 ) = P 2 A P 2

1 0 0 0 0 1 0 0 0 0 - 3 / 5 - 4 / 5 0 0 - 4 / 5 3 / 5 . 4 1 - 2 2 1 2 0 1 - 2 0 3 - 2 2 1 - 2 - 1 . 1 0 0 0 0 1 0 0 0 0 - 3 / 5 - 4 / 5 0 0 - 4 / 5 3 / 5

A ( 3 ) = 4 - 3 0 0 - 3 10 / 3 - 5 / 3 0 0 - 5 / 3 - 33 / 25 68 / 75 0 0 68 / 75 149 / 75

Resposta

A ( 3 ) = 4 - 3 0 0 - 3 10 / 3 - 5 / 3 0 0 - 5 / 3 - 33 / 25 68 / 75 0 0 68 / 75 149 / 75

Exercício Resolvido #10

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

A = 8 3 2 - 2 2 4 1 2 - 3 0 9 - 5 6 7 0 1

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 = - 14

r = 1 2 - 14 2 - 2 - 14 1 / 2 = 112

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 - ( - 14 ) 2 . 112 = 8 112

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 = - 3 2 . 112 = - 1,5 112

v 4 = 6 2 . 112 = 3 112

Vetor:

v 1 =   0 8 112 - 1,5 112 3 112 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 8 112 - 1,5 112 3 112 0 8 112 - 1,5 112 3 112

P ( 1 ) = 1 0 0 0 0 - 1 / 7 3 / 14 - 3 / 7 0 3 / 14 107,5 / 112 9 / 112 0 - 3 / 7 - 9 / 112 47 / 56

Passo 4

Então calculamos:

A ( 2 ) = P 1 A P 1

1 0 0 0 0 - 1 / 7 3 / 14 - 3 / 7 0 3 / 14 107,5 / 112 9 / 112 0 - 3 / 7 - 9 / 112 47 / 56 . 8 3 2 - 2 2 4 1 2 - 3 0 9 - 5 6 7 0 1 . 1 0 0 0 0 - 1 / 7 3 / 14 - 3 / 7 0 3 / 14 107,5 / 112 9 / 112 0 - 3 / 7 - 9 / 112 47 / 56

A ( 2 ) = 8 0,8571 2,7232 - 2,8036 - 3,5 1,6582 1,0922 0,1754 - 1,9687 3,5328 9,146 - 3,4977 4,4196 - 1,3333 - 0,2448 - 1,5535

Resposta

A ( 2 ) = 8 0,8571 2,7232 - 2,8036 - 3,5 1,6582 1,0922 0,1754 - 1,9687 3,5328 9,146 - 3,4977 4,4196 - 1,3333 - 0,2448 - 1,5535