O método das potências

Teoria Completa

Nós revimos até agora, alguns métodos importantes para encontrar autovalores e autovetores de uma matriz. Mas, vimos também que demanda um tempo maior pra resolver tudo!

Mas relaxa, existem métodos (talvez nem tão triviais assim) que vão permitir encontrar autovalor em módulo e um autovalor associado, de uma matriz A, SEM PRECISAR DESCOBRIR O POLINÔMIO CARACTERÍSTICO!

Um curiosidade sobre essse método, é que ele é responsável pelo ranqueamento de páginas usadas pelo Google.

Maaaaaaaaaaaaaaaaaaaaas, o método serve pra determinar autovalores de módulos grandes ou separados dos demais. É um método da potência é uma técnica iterativa (sim, meus caros... novamente iterações), usada para determinar o autovalor dominante de uma matriz, que basicamente é um autovalor com maior módulo.

Mas a diferença desse método é que ele não encontra SÓ o autovalor, maaaaas, encontra também o autovetor associado.

“O método das potências deriva do fato que as iterações exageram o tamanho relativo dos módulos autovalores”.

Para que o método das potências encontre uma aproximação para o maior autovalor em móduelo de uma matriz A   ϵ   R n × n , podemos supor também que a matriz tem n autovalores λ 1 , λ 2 , … ,   λ n e um conjunto de autovetores associados { v 1 , v 2 , … , v n } e linearmente independente, devemos supor também que A só tenha valor maior em módulo:

| λ 1 | > λ 2 ≥ | λ n | ≥ 0

Vamos definir alguns termos:

y p 1 1 = | | y ( 1 ) | |

Desse modo, x ( 1 ) :

x ( 1 ) = 1 y p 1 1 y ( 1 ) = 1 y p 1 1 A x ( 0 )

Então:

x p 1 1 = 1 = | | x ( 1 ) | |

Agora defina:

y ( 2 ) = A x ( 1 ) = 1 y p 1 1 A 2 x ( 0 )

De modo análogo, defina a sequiencia de vetores { x ( m ) } m = 0 ∞   e { y ( m ) } m = 0 ∞ e uma sequencia de escalares { µ ( m ) } m = 0 ∞ da seguinte forma:

Então vamos para um exemplo para ficar mais claro!

Exemplo

Temos uma matriz A (2 X 2):

Para isso, o exercício dá um vetor inicial :

v ( 0 ) = [ x           y ] t

Então, fazemos o processo de normalização:

u ( x ) = x x = a

u ( y ) = y x = b

u = [ a           b ] t

Agora, multiplicamos a matriz A pela matriz de vetors normalizados:

a 11 a 12 a 21 a 22 a b = x ( 1 )

O teste de convergência :

x ( 1 ) - x ( 0 ) x ( 1 ) < ε

Expandir

Exercício Resolvido #1

Adaptado de Burden, RLB | .JDF | .AM Análise Numérica - Tradução da 10ª edição norte-americana 

Nós vimos outros métodos de encontrar autovalores e autovetores, mas, que esses métodos demandam um tempo computacional além do necessário em alguns casos. Rascunhe quais sãos as entradas e saídas necessárias para implementar o algorítimo para o método das potências.

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

A primeira coisa que devemos ter em mente é que para obter uma aproximação o para o autovalor dominante e autovetor associado da matriz A , n × n de um determinado vetor não nulo x.

Passo 2

Como ENTRADA:

Devemos primeiramente colocar ou pedir para que o usuário determine as dimensões n da minha matriz A .

Outro valor importante, é pedir os valores que irão compor a matriz A .

Além disso, devemos pedir o vetor x a tolerância (TOL) e o número máximo de iterações que queremos atingir.

Passo 3

Para Saída: Colocaremos o autovalor aproximado µ, o autovetor aproximado x ou uma mensagem dizendo que o número máximo de iterações foi excedido.

Resposta

ENTRADA: n , A , x , TOL, N.

SAÍDA: µ, x , N excedido.

Exercício Resolvido #2

Adaptado de Burden, RLB | .JDF | .AM Análise Numérica - Tradução da 10ª edição norte-americana 

Verdadeiro e falso:

Marque verdadeiro e falso, e corrija se necessário. Considere A como uma matriz n × n diagonalizável com um autovalor dominante λ .

  1. Seja x 0 = y 0 for um vetor inicial R n o maior componente deve ser 1.
  2. Para a maioria das escolhas de x 0 , m k converge para o autovalor dominante λ e y não converge para um autovalor dominante.
  3. O nome do Método da Potência deriva do fato de que as iterações exageram o tamanho relativo dos módulos dos autovalores.
MOSTRAR SOLUÇÃO COMPLETA

Passo 1

  1. Seja x 0 = y 0 for um vetor inicial R n o maior componente deve ser 1.
  2. Essa premissa é verdadeira, o vetor inicial é sempre normalizado e transformado em valores vetor

    Passo 2

  3. Para a maioria das escolhas de x 0 , m k converge para o autovalor dominante λ e y não converge para um autovalor dominante.
  4. Essa premissa é falsa.

    O método da potência é uma técnica iterativa, usada para determinar o autovalor DOMINANTE de uma matriz, e converge para um autovalor dominante.

    Passo 2

  5. O nome do Método da Potência deriva do fato de que as iterações exageram o tamanho relativo dos módulos dos autovalores.

Verdadeiro.

Resposta

  1. V
  2. F
  3. V

Exercício Resolvido #3

Adaptado de Burden, RLB | .JDF | .AM Análise Numérica - Tradução da 10ª edição norte-americana 

Resolva a primeira iteração da matriz abaixo, pelo método das potências, considerando o vetor inicial:

x ( 0 ) = 1 1 1 t

A = - 4 14 0 - 5 13 0 - 1 0 2

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Primeiro passo é fazer:

A x = y

Se:

A = - 4 14 0 - 5 13 0 - 1 0 2

x ( 0 ) = 1 1 1 t

Então:

- 4 14 0 - 5 13 0 - 1 0 2 . 1 1 1 = - 4 + 14 - 5 + 13 - 1 + 2 = 1 0 8 1

Passo 2

No próximo passo, devemos transformar a matriz calculada em uma matriz normalizada .

10 8 1

Onde µ será o termo maior 10, que servirá para normalizar:

x ( 1 ) = y ( 1 ) 10

x ( 1.1 ) = 10 10 = 1

x ( 1 . 2 ) = 8 10 = 0,8

x ( 1 . 3 ) = 1 10 = 0,1

O vetor x ( 1 ) , passa a ser

x ( 1 ) = 1 0,8 0 , 1 t

Resposta

x ( 1 ) = 1 0,8 0,1 t

Exercício Resolvido #4

Adaptado de documento da Faculdade de Engenharia Resende (Dom Bosco)

Resolva a segunda iteração da matriz abaixo, pelo método das potências, considerando o vetor inicial:

x ( 0 ) = 1 1 t

A = 3 4 2 - 1

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Primeira iteração:

A x = y

Se:

A = 3 4 2 - 1

x ( 0 ) = 1 1 t

Então:

3 4 2 - 1 . 1 1 = 3 + 4 2 - 1 = 7 1

No próximo passo, devemos transformar a matriz calculada em uma matriz normalizada .

7 1

Onde µ será o termo maior 7, que servirá para normalizar:

x ( 1 ) = y ( 1 ) 7

x ( 1.1 ) = 7 7 = 1

x ( 1.2 ) = 1 7 = 0 , 1429

O vetor x ( 1 ) , passa a ser

x ( 1 ) = 1 0 , 1429 t

Passo 2

Segunda iteração:

A x = y

Se:

A = 3 4 2 - 1

x ( 1 ) = 1 0,1429 t

Então:

3 4 2 - 1 . 1 0,1429 = 3 + 0,5716 2 - 0,1429 = 3 , 5716 1,8571

No próximo passo, devemos transformar a matriz calculada em uma matriz normalizada .

3,5716 1,8571

Onde µ será o termo maior 3,5716 , que servirá para normalizar:

x ( 2 ) = y ( 2 ) 3,5716

x ( 2.1 ) = 3,5716 3,5716 = 1

x ( 2.2 ) = 1,8571 3,5716 = 0,5199

O vetor x ( 1 ) , passa a ser

x ( 2 ) = 1 0,5199 t

Resposta

Após 2 iterações:

A u t o v a l o r = λ = 3,5716

A u t o v e t o r = x ( 2 ) = 1 0,5199 t

Exercício Resolvido #5

Adaptado de documento da Faculdade de Engenharia Resende (Dom Bosco)

Resolva a segunda iteração da matriz abaixo, pelo método das potências, considerando o vetor inicial e calcule o erro:

x ( 0 ) = 1 1 t

A = 34,4 12,5 2 5,9 67,3

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Primeira iteração:

A x = y

Se:

A = 34,4 12,5 25,9 67,3

x ( 0 ) = 1 1 t

Então:

34,4 12,5 25,9 67,3 . 1 1 = 3 4,4 + 12,5 2 5,9 + 67,3 = 46,9 93,2

No próximo passo, devemos transformar a matriz calculada em uma matriz normalizada .

46,9 93,2

Onde µ será o termo maior 93,2 , que servirá para normalizar:

x ( 1 ) = y ( 1 ) 93,2

x ( 1.1 ) = 46,9 93,2 = 0,5032

x ( 1.2 ) = 93,2 93,2 = 1

O vetor x ( 1 ) , passa a ser

x ( 1 ) = 0,5032 1 t

Passo 2

Segunda iteração:

A x = y

Se:

A = 34,4 12,5 25,9 67,3