Método de Householder
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 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 da forma:
Essa forma é chamada de transformação de Householder e possui as propriedades de simetria e ortogonalidade.
Nós geralmente temos um vetor qualquer que é multiplicado por , e sua imagem é refletida no hiperplano .
A transformação de Householder é muito usada para zerar os elementos de um vetor. Esse e não deve ser nulo.
Com isso encontramos ficamos com:
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 , que são:
Com α e , construímos o vetor :
Em que :
Então calculamos:
Tendo encontrado e calculado , o processo é repetido para .
Usando as fórmulas abaixo:
, para
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
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.
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 e pedimos para o programa executar até atender o critério de parada.
Passo 2: Faça
Passo 3
Escrever passo aqui
Saídas: nesse caso saí a cada iteração uma matriz 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?
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:
- Não é uma matriz hermitiana e .
- É uma matriz unitária onte .
- A matriz de Householder tem autovalores diferentes de 1.
Passo 1
- Não é uma matriz hermitiana e .
- É uma matriz unitária onte .
- A matriz de Householder tem autovalores diferentes de 1.
Falso. A matriz é realmente uma matriz hermitiana que basicamente é aquela matriz que é idêntica a sua transposta.
Passo 2
Verdadeiro. Trata-se de uma matriz U que satisfaz.
Passo 3
Falso. 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, 1 autovalor de multiplicidade , uma vez que existem vetores linearmente independentes ortogonais a . Além disso, observe que e assim é 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 para calcular (primeira iteração).
Passo 1
Para a primeira aplicação de uma transformação de Householder temos que α e , que são:
No nosso caso, ainda estamos em :
Onde:
Passo 2
Para escrever o vetor fazemos:
Para :
Para o e o :
,
Vetor:
Passo 3
Então calculamos:
Passo 4
Então calculamos:
Resposta
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 do problema anterior. Lembrando que:
Passo 1
Para a primeira aplicação de uma transformação de Householder temos que α e , que são:
Como estamos em :
Passo 2
Para escrever o vetor fazemos:
Para o :
E o :
,
Vetor:
Passo 3
Então calculamos:
Passo 4
Então calculamos:
Resposta
Exercício Resolvido #6
Elaboração Própria
Aplique as transformações de Householder à matriz para calcular (primeira iteração).
Passo 1
Para a primeira aplicação de uma transformação de Householder temos que α e , que são:
No nosso caso, ainda estamos em :
Onde:
Passo 2
Para escrever o vetor fazemos:
Para :
Para o e o :
,
Vetor:
Passo 3
Então calculamos:
Passo 4
Então calculamos:
Resposta
Exercício Resolvido #7
Elaboração Própria
Continue com as transformações de Householder à matriz para calcular (primeira iteração).
Passo 1
Para a primeira aplicação de uma transformação de Householder temos que α e , que são:
Como estamos em :
Passo 2
Para escrever o vetor fazemos:
Para o :
E o :
,
Vetor:
Passo 3
Então calculamos:
Passo 4
Então calculamos:
Resposta
Exercício Resolvido #8
Adaptado de Burden, Richard L. Burden | J. Douglas Faires | Annette M. Análise Numérica - Tradução da 10ª edição norte-americana
Aplique as transformações de Householder à matriz simétrica para calcular na primeira iteração que produz uma matriz simétrica semelhante a
Passo 1
Para a primeira aplicação de uma transformação de Householder temos que α e , que são:
No nosso caso, ainda estamos em :
Onde:
Passo 2
Para escrever o vetor fazemos:
Para :
Para o e o :
,
Vetor:
Passo 3
Então calculamos:
Passo 4
Então calculamos:
Resposta
Exercício Resolvido #9
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 do problema anterior. Lembrando que:
Passo 1
Para a primeira aplicação de uma transformação de Householder temos que α e , que são:
Como estamos em :
Passo 2
Para escrever o vetor fazemos:
Para o :
E o :
,
Vetor:
Passo 3
Então calculamos:
Passo 4
Então calculamos:
Resposta
Exercício Resolvido #10
Elaboração Própria
Aplique as transformações de Householder à matriz para calcular (primeira iteração).
Passo 1
Para a primeira aplicação de uma transformação de Householder temos que α e , que são:
No nosso caso, ainda estamos em :
Onde:
Passo 2
Para escrever o vetor fazemos:
Para :
Para o e o :
,
Vetor:
Passo 3
Então calculamos:
Passo 4
Então calculamos: