Método de Francis

Teoria Completa

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 😊.

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.

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.

MOSTRAR SOLUÇÃO COMPLETA

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

Adaptado de Apostila da USP-ICMC de Cálculo numérico (Professora Neide Maria)

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

MOSTRAR SOLUÇÃO COMPLETA

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

Autoria do Responde Aí

Calcule os termos c   e s   das seguintes matrizes:

(a) 1 2 3 4

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

MOSTRAR SOLUÇÃO COMPLETA

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