Método de Francis

Ver Todos os Exercícios

Teoria

Faaaaaala meu jovem, tudo certinho?

Nós vimos até agora alguns métodos que servem para resolver sistemas lineares matriciais, até aí tudo ok né?

Mas existe um método que não é muito convencional...

Então, são poucas as universidades que abordam o tema. Se você não vê esse conteúdo, pode pular pro próximo!!!

Basicamente, o Método de Francis ou também conhecido como método QR determina todos os autovalores de uma matriz, sem determinar o polinômio característico (já vimos alguma coisa parecida antes né? É que na real é tudo meio parecido).

Mas, bora lá!

Temos uma matriz A quadrada e de ordem n , a clássica né! O nosso método vai construir uma sequência de matrizes A 1 , A 2 ... A n da seguinte forma: vamos decompondo A = A 1 no produto Q 1 R 1 onde Q 1 será ortogonal e R 1 será a matriz triangular superior.

Então:

A 1 = Q 1 R 1

O próximo passo é multiplicarmos as duas matrizes na ordem inversa pra formamos a matriz A 2 :

A 2 = R 1 Q 1

Após isso, fazemos a decomposição da matriz:

A 2 = Q 2 R 2

As matrizes são conjugadas e tem os mesmos autovalores, tudo em ordem aí?

Podemos definir a sequência de matrizes por L k = A k :

L k   =   R ( k - 1 ) . Q ( k - 1 )

Em que:

L k - 1   =   Q ( k - 1 ) . R ( k - 1 )

O processo só acaba quando termina HAHAHAHHAHAH

Vai acabar quando o maior valor absoluto da matriz A k (abaixo da diagonal principal) for menor que a precisão dada (ε).

Enquanto não atingimos a precisão necessária nós vamos tentando e encontrando novos Q k e R k .

E como é que eu faço isso?

Como encontramos Q e R?

Queremos A =   Q R

E para isso precisamos achar uma matriz U 1 e ortogonal, de modo que quando multiplicamos U 1   por A zera o elemento a 21 .

Vamos achar uma matriz U 2 , também ortogonal, para que a multiplicação de U 2 por U 1 A zere agora o elemento a 31 . Hmmmm beleza... vamos continuar nessa lógica!

Logo:

U n . . .   U 2 U 1 A   =     R

E todos esses valores U juntos formam Q .

A partir de agora, vamos usar uma parada chamada matriz rotacional!

Essa matriz é diferente da matriz identidade em 4 sentidos 😊

u q q =   u pp = cos ⁡ φ

Agora para outros termos:

u p q =   - u qp = sen ⁡ φ

Nesse caso para qualquer φ   e   p ≠ q .

Exemplo:

cos ⁡ φ 0 0 … sen ⁡ φ 0 ⋱ … … 0 0 0 1 ⋯ 0 0 0 0 ⋱ 0 - sen ⁡ φ 0 0 0 cos ⁡ φ

Exemplo de uma matriz 3 x 3! Para zerar a 21 fazemos U 1 A :

a' 21 = - sen ⁡ φ a 11 + cos ⁡ φ a 21

Quando queremos zerar os elementos a q p :

a' 21 = - sen ⁡ φ a p p + cos ⁡ φ a q p

Para zerar os elementos a p q :

a ' q p = - a p p 1 - cos 2 ⁡ φ + cos ⁡ φ a q p

Fazemos algo assim:

a p p 1 - cos 2 ⁡ φ = cos ⁡ φ a q p

a p p 2 ( 1 - cos 2 ⁡ φ ) = cos 2 ⁡ φ a q p 2

a p p 2 = ( a pp 2 + a qp 2 ) cos 2 ⁡ φ

Assim, temos:

c = cos ⁡ φ = a p p a p p 2 + a q p 2

s = sen ⁡ φ = - a q p a p p 2 + a q p 2

MAAAAAAAAAAAAAAAAAARCA BEM ESSAS DUAS EQUAÇÕES c ,   s !!!!!!!!!!!!

Primeiro Quando queremos, por exemplo, zerar o termo a 21 :

a' 21 = - s ⁡ a 11 + c   a 21 = 0

s = sen ⁡ φ = a 21 a 11 2 + a 21 2

c = cos ⁡ φ = a 11 a 11 2 + a 21 2

A matriz das “letrinhas” e   U 1 :

  U 1 = c s 0 - s c 0 0 0 1

Matricialmente temos:

c s 0 - s c 0 0 0 1 a ' 11 a ' 12 a ' 13 a ' 21 a ' 22 a ' 23 a ' 31 a ' 32 a ' 33 = a ' 11 a ' 12 a ' 13 0 a ' 22 a ' 23 a ' 31 a ' 32 a ' 33

Segundo zeramos o termo a 31 :

Onde:

A matriz das “letrinhas” e   U 2 :

  U 2 = c 0 s 0 1 0 - s 0 c

c 0 s 0 1 0 - s 0 c a ' 11 a ' 12 a ' 13 0 a ' 22 a ' 23 a ' 31 a ' 32 a ' 33 = a ' 11 a ' 12 a ' 13 0 a ' 22 a ' 23 0 a ' 32 a ' 33

a' 31 = - s ⁡ a 11 + c   a 31 = 0

s = sen ⁡ φ = a 31 a 11 2 + a 31 2

c = cos ⁡ φ = a 11 a 11 2 + a 31 2

Terceiro zeramos o termo a 32 :

Onde:

A matriz das “letrinhas” e   U 3 :

  U 3 = 1 0 0 0 c s 0 - s c

1 0 0 0 c s 0 - s c a ' 11 a ' 12 a ' 13 0 a ' 22 a ' 23 0 a ' 32 a ' 33 = a ' 11 a ' 12 a ' 13 0 a ' 22 a ' 23 0 0 a ' 33

a' 32 = - s ⁡ a 22 + c   a 32 = 0

s = sen ⁡ φ = a 32 a 22 2 + a 32 2

c = cos ⁡ φ = a 22 a 22 2 + a 32 2

Agora, podemos obter Q e R

U n …   U 2 U 1 A   =     R

Então:

U 1 T   U 2 T U 3 T … U n T = Q

E o próximo A será:

A   =     R Q

Fazemos esse passo a passo até que os números abaixo da diagonal principal sejam menores que o erro!

Tudo ok por aqui???

Então, bora fazer exercício para fixar bem esse conteúdo 😊.

Exercícios Resolvidos

Exercício Resolvido #1

Sabe-se da importância da implementação de métodos numéricos, e por isso é muito importante definir-mos quais pontos são necessários para o funcionamento e implementação o que eu desejo obter. Portanto, defina as entradas e saídas para implementar um algoritmo sobre o método de Francis.

Passo 1

Entradas: n; o tamanho da matriz (A) e os termos que a compõem (a) e o número máximo de iterações (M).

Passo 2

Saídas: Valores característicos de A, uma divisão reconhecida de A e a mensagem que excedeu o número de iterações (tol).

Resposta

E: n, A, a, M.

S: A, tol.

Exercício Resolvido #2

Mostre que uma matriz A   e sua transposta A T possuem o mesmo polinômio característico:

Passo 1

A equação para encontrar o polinômio característico é:

det ⁡ A - I λ = 0

Sabendo que:

A = a 11 a 12 a 21 a 22

A T = a 11 a 2 1 a 1 2 a 22

Para ter o mesmo polinômio característico, a matriz A e a transposta devem ser simétricos!

A = A T

a 11 a 12 a 21 a 22 = a 11 a 21 a 12 a 22

Passo 2

Se as matrizes são simétricas, possuem o mesmo polinômio característico!

Resposta

Simétricas e igual polinômio característico.

Exercício Resolvido #3

Calcule os termos c   e s   das seguintes matrizes:

(a) 1 2 3 4

(b) 3 5 7 0 16 18 0 12 1

Passo 1

(a) 1 2 3 4

a' 21 = - s ⁡ a 11 + c   a 21 = 0

s = sen ⁡ φ = a 21 a 11 2 + a 21 2 = 3 1 2 + 3 2 = 0,9487

c = cos ⁡ φ = a 11 a 11 2 + a 21 2 = 1 1 2 + 3 2 = 0,3162

Passo 2

(b) 3 5 7 0 16 18 0 12 1

a' 32 = - s ⁡ a 22 + c   a 32 = 0

s = sen ⁡ φ = a 32 a 22 2 + a 32 2 = 12 16 2 + 12 2 = 0,6

c = cos ⁡ φ = a 22 a 22 2 + a 32 2 = 1 6 16 2 + 12 2 = 0 , 8

Resposta

  1. s = 0,9487   e   c = 0,3162
  2. s = 0 , 6   e   c = 0 , 8

Exercício Resolvido #4

Determinar a primeira iteração para encontrar os autovalores da matriz com o método de Francis:

A = 2 0 1 0 1 0 1 0 1

Com ε < 0,1

Passo 1

Se:

A = 2 0 1 0 1 0 1 0 1

Como a 21 = 0 , devemos zerar apenas o elemento a 31 . Assim U 1 = I para obtermos U 2 :

Zeramos o termo a 31 :

Onde:

A matriz das “letrinhas” e   U 2 :

  U 2 = c 0 s 0 1 0 - s 0 c

a' 31 = - s ⁡ a 11 + c   a 31 = 0

s = sen ⁡ φ = a 31 a 11 2 + a 31 2 = 1 2 2 + 1 2 = 0,4472

c = cos ⁡ φ = a 11 a 11 2 + a 31 2 = 2 2 2 + 1 2 = 0,8944

Passo 2

Se:

c 0 s 0 1 0 - s 0 c a ' 11 a ' 12 a ' 13 0 a ' 22 a ' 23 a ' 31 a ' 32 a ' 33 = a ' 11 a ' 12 a ' 13 0 a ' 22 a ' 23 0 a ' 32 a ' 33

Agora temos que a 32 = 0 e então   U 3 = I ,   U 3   U 2   U 1 =   U 2 e, portanto U 2 T = Q .

Com isso:

A 1 = Q 1 R 1

A 2 = R 1 Q 1

A 2 = 2,236 0 1,3416 0 1 0 0 0 0,4472 0,8944 0 - 0,4472 0 1 0 0,4472 0 0,8944 = 2,5998 0 0,2 0 1 0 0,2 0 0,4

A 2 = 2,5998 0 0,2 0 1 0 0,2 0 0,4

O termo da matriz triangular inferior 0,2 > e r r o = 0,1

Isso significa que devemos fazer outra iteração.

Resposta

A 2 = 2,5998 0 0,2 0 1 0 0,2 0 0,4

Exercício Resolvido #5

Continue a iteração do exercício anterior:

A 2 = 2,5998 0 0,2 0 1 0 0,2 0 0,4

Com ε < 0,1

Passo 1

Se:

A 2 = 2,5998 0 0,2 0 1 0 0,2 0 0,4

Como a 21 = 0 , devemos zerar apenas o elemento a 31 . Assim U 1 = I para obtermos U 2 :

Zeramos o termo a 31 :

Onde:

A matriz das “letrinhas” e   U 2 :

  U 2 = c 0 s 0 1 0 - s 0 c

a' 31 = - s ⁡ a 11 + c   a 31 = 0

s = sen ⁡ φ = a 31 a 11 2 + a 31 2 = 0,2 2,5998 2 + 0,2 2 = 00767

c = cos ⁡ φ = a 11 a 11 2 + a 31 2 = 2,5998 2,5998 2 + 0,2 2 = 0,9971

Passo 2

Se:

c 0 s 0 1 0 - s 0 c a ' 11 a ' 12 a ' 13 0 a ' 22 a ' 23 a ' 31 a ' 32 a ' 33 = a ' 11 a ' 12 a ' 13 0 a ' 22 a ' 23 0 a ' 32 a ' 33

0,9971 0 0,0767 0 1 0 - 0,0767 0 0,9971 2,5998 0 0,2 0 1 0 0,2 0 0,4 = 2,607 6 0 0,2301 0 1 0 0 0 0,3 8 35 R

Agora temos que a 32 = 0 e então   U 3 = I e   U 3   U 2   U 1 = U 2

  U 2 T = Q

A 2 = Q 2 R 2

A 3 = R 2 Q 2

A 3 = 2,607 6 0 0,2301 0 1 0 0 0 0,3 8 35 0,9971 0 - 0,0767 0 1 0 0,0767 0 0,9971 = 2 , 6177 0 0 , 0 2 94 0 1 0 0 , 0 2 94 0 0 , 3824

A 3 = 2,617 7 0 0,02 94 0 1 0 0,0 2 94 0 0,3 8 24

O termo da matriz triangular inferior 0,0 294 < e r r o = 0,1

Então, os autovalores são os elementos da diagonal principal:

λ 1 = 2,617 7

λ 2 = 1

λ 3 = 0,3 8 24

Resposta

λ 1 = 2,617 7

λ 2 = 1

λ 3 = 0,3 8 24

Exercício Resolvido #6

Usando o método de Francis na matriz:

A = 7 5 6 0 3 - 1 0 1 9

É possível estimar seus autovalores aplicando o método uma única vez?

Passo 1

Se:

A = 7 5 6 0 3 - 1 0 1 9

Não precisamos zerar nem o a 21 nem o a 31 , pois eles já são 0 . Logo, U 1 = U 2 = I . Devemos zerar apenas o elemento a 32 . Assim U 3 :

Zeramos o termo a 32 :

Onde:

A matriz das “letrinhas” e   U 3 :

  U 3 = 1 0 0 0 c s 0 - s c

a' 32 = - s ⁡ a 22 + c   a 32 = 0

s = sen ⁡ φ = a 32 a 22 2 + a 32 2 = 1 3 2 + 1 2 = 0,3162

c = cos ⁡ φ = a 22 a 22 2 + a 32 2 = 3 3 2 + 1 2 = 0,9487

Passo 2

Se:

1 0 0 0 c s 0 - s c a 11 a 12 a 13 0 a 22 a 23 0 a 32 a 33 = a 11 a 12 a 13 0 a ' 22 a ' 23 0 0 a ' 33

1 0 0 0 0,9487 0,3162 0 - 0,3162 0,9487 7 5 6 0 3 - 1 0 1 9 = 7 5 6 0 3,1623 1,8971 0 0 8,8545 R

E então   U 3 = 1 0 0 0 0,9487 0,3162 0 - 0,3162 0,9487 e, portanto:

Q 1 = U 3 T = 1 0 0 0 0,9487 - 0,3162 0 0,3162 0,9487

Com isso:

A 1 = Q 1 R 1

A 2 = R 1 Q 1

A 2 = 7 5 6 0 3,1623 1,8971 0 0 8,8545 1 0 0 0 0,9487 - 0,3162 0 0,3162 0,9487 = 7 6,6407 4,1112 0 3,6 0,8 0 2,8 8 , 4

Opa, como podemos ver, o erro (valor absoluto abaixo da diagonal principal) desse método após uma iteração NÃO deu zero! Logo, NÃO achamos o valor dos autovalores de primeira!!

Resposta

Não

Exercício Resolvido #7

Determinar a primeira iteração para encontrar os autovalores da matriz com o método de Francis:

A = 5 3 2 0 9 0 8 0 1 0

Passo 1

Se:

A = 5 3 2 0 9 0 8 0 10

Como a 21 = 0 , devemos zerar apenas o elemento a 31 . Assim U 1 = I para obtermos U 2 :

Zeramos o termo a 31 :

Onde:

A matriz das “letrinhas” e   U 2 :

  U 2 = c 0 s 0 1 0 - s 0 c

a' 31 = - s ⁡ a 11 + c   a 31 = 0

s = sen ⁡ φ = a 31 a 11 2 + a 31 2 = 8 5 2 + 8 2 = 0,848

c = cos ⁡ φ = a 11 a 11 2 + a 31 2 = 5 5 2 + 8 2 = 0 , 53

Passo 2

Se:

c 0 s 0 1 0 - s 0 c a 11 a 12 a 13 0 a 22 a 23 a 31 a 32 a 33 = a ' 11 a ' 12 a ' 13 0 a 22 a 23 0 a ' 32 a ' 33

0,53 0 0,848 0 1 0 -