SISTEMAS LINEARES
SISTEMAS LINEARES
( 1ª AULA)
( AULA 3 )
ESFORÇO COMPUTACIONAL
O ESFORÇO COMPUTACIONAL ENVOLVIDO NO MÉTODO TRADICIONAL
(TEOREMA DE LAPLACE) DE CÁLCULO DE DETERMINANTES É MUITO
GRANDE
EXEMPLIFICANDO
SISTEMAS LINEARES
O CÁLCULO DO DETERMINANTE DE UMA MATRIZ DE ORDEM 4 EXIGE
QUE CALCULEMOS O DETERMINANTE DE 4 MATRIZES DE ORDEM 3.
O CÁLCULO DO DETERMINANTE DE UMA MATRIZ DE ORDEM 5 EXIGE
QUE CALCULEMOS O DETERMINANTE DE 5 MATRIZES DE ORDEM 4 E
PORTANTO 20 MATRIZES DE ORDEM 3.
( 1ª AULA)
O CÁLCULO DO DETERMINANTE DE UMA MATRIZ DE ORDEM 6 EXIGE
QUE CALCULEMOS O DETERMIANTE DE 6 MATRIZES DE ORDEM 5 E
PORTANTO 120 MATRIZES DE ORDEM 3.
O CÁLCULO DO DETERMINANTE DE UMA MATRIZ DE ORDEM 7 EXIGE
QUE CALCULEMOS O DETERMINANTE DE 7 MATRIZES DE ORDEM 6 E
PORTANTO 720 MATRIZES DE ORDEM 3.
E ASSIM SUCESSIVAMENTE . . .
SENDO Mn E An RESPECTIVAMENTE O NÚMERO DE MULTIPLICAÇÕES
E ADIÇÕES NECESSÁRIAS PARA O CÁLCULO DO DETERMINANTE DE
UMA MATRIZ QUADRADA DE ORDEM n PELO MÉTODO DE LAPLACE,
TEMOS :
M1 = 0
e
Mn = n + n . Mn-1
A = 0 e A = n-1
+ n. A
SISTEMAS
LINEARES
1
n
n-1
E O NÚMERO TOTAL DE OPERAÇÕES É DADO POR :
(Δ 1ª= M
AULA)
+A
n
n
n
n= 8:
Δ8 = 109.599
n = 10 : Δ10 = 9.234.099
T
3 horas
T 152 horas(
→
Δ6 = 1.955
→
n=6:
→
PARA CALCULAR MANUALMENTE O DETERMINANTE DE UMA MATRIZ
SUPONDO QUE O TEMPO MÉDIO PARA CADA OPERAÇÃO SEJA DE
5 SEGUNDOS TEMOS:
T
534 dias
6 dias)
VAMOS AGORA CALCULAR O ESFORÇO COMPUTACIONAL ENVOLVIDO
NO CÁLCULO DO DETERMINANTE DE UMA MATRIZ QUADRADA DE
ORDEM n COM O AUXÍLIO DE UM COMPUTADOR
n = 20 :
Δn
6,191. 10 18
► 1984: UTILIZANDO UM COMPUTADOR IBM370 (MODELO 158) O
TEMPO PARA REALIZAR UMA ADIÇÃO ERA DE 0,9 . 10 – 6
SEGUNDOS E O TEMPO PARA UMA MULTIPLICAÇÃO ERA DE
1,9 . 10 – 6 SEGUNDOS. CONSIDERANDO UM TEMPO MÉDIO DE
1,4 . 10 – 6 SEGUNDOS:
SISTEMAS LINEARES
( 1ª
AULA)
275.000
anos
T
► 2007: A INTEL VENCE A BARREIRA DOS 2 TeraFlops (2 TRILHÕES DE
OPERAÇÕES DE PONTO FLUTUANTE POR SEGUNDO)
T
36 dias
► 2008: O ROADRUNNER ENCABEÇA A LISTA TOP500. TRATA-SE DE
UM CLUSTER COM 122400 PROCESSADORES TRABALHANDO
COM 3200 MHz (12,8 GigaFlops)
T 1 hora(66 minutos)
O NÚMERO DE OPERAÇÕES ENVOLVIDAS NA RESOLUÇÃO DE UM
SISTEMA LINEAR QUADRADO DE ORDEM n, PELA REGRA DE CRAMER
(QUE UTILIZA MATRIZES) É DADO POR:
Sn = n +1 . Δn + n
ASSIM, PARA UM SISTEMA DE ORDEM 20, TEMOS:
n = 20
Sn = 1,3 . 10 20
→
SISTEMAS LINEARES
EM 1984 UM IBM370 (MODELO 158) DEMORARIA 15 MILHÕES DE ANOS
PARA CALCULAR ESTE SISTEMA.
(
1ª
AULA)
JÁ O NÚMERO DE OPERAÇÕES ENVOLVIDAS NA RESOLUÇÃO DE UM
SISTEMA LINEAR QUADRADO DE ORDEM n, PELA MÉTODO DE GAUSS
É DADO POR:
3
2
Gn =
4n +9n -7n
6
n = 20
→
ASSIM, PARA UM SISTEMA DE ORDEM 20, TEMOS:
Gn = 5.910
EM 1984 UM IBM370 (MODELO 158) DEMORARIA 0,02 SEGUNDOS PARA
CALCULAR ESTE SISTEMA.
INVERSÃO DE MATRIZES POR GAUSS-JORDAN
O PROCESSO APRESENTADO ANTERIORMENTE PARA INVERTER UMA
MATRIZ QUADRADA DE ORDEM n, NÃO É VIÁVEL SOB O PONTO DE
VISTA COMPUTACIONAL, TENDO EM CONTA QUE SERIA NECESSÁRIO
RESOLVER n SISTEMAS LINEARES CADA UM DELES COM n EQUAÇÕES
A n INCÓGNITAS.
SISTEMAS LINEARES
ASSIM SENDO, VAMOS APRESENTAR UM OUTRO MÉTODO QUE REDUZ
SENSIVELMENTE O ESFORÇO COMPUTACIONAL ENVOLVIDO.
( O1ªMÉTODO
AULA)
CONSIDEREMOS A MATRIZ:
A =  a i j  ∈ Mn R 
SE A MATRIZ A É INVERSÍVEL ENTÃO EXISTE UMA MATRIZ:
X = x
TAL QUE:
ij
 ∈ M R 
n
A.X = I n = X.A
A MATRIZ X SE DENOMINA MATRIZ INVERSA DE A E É REPRESENTADA
POR A - 1
 a11

 a 21
.

 an1
a12 . . . a1n 
 x 11


a 22 . . . a 2n 
x
.  21
.
. . . . .


a n2 . . . a nn 
 x n1
x 12 . . . x 1n 
1 0 . .


x 22 . . . x 2n 
= 0 1 . .
. . . . .
. . . .


x n2 . . . x nn 
0 0 . .
X
. 0

. 0
. . 

. 1
In
SISTEMAS LINEARES
A
NOTEMOS AGORA QUE AO MULTIPLICAR A MATRIZ A PELA j-ÉSIMA
1 ≤ j ≤ n 
MATRIZ I n
 a11

 a 21
.

 an1
COLUNA DA MATRIZ X OBTEMOS A j-ÉSIMA COLUNA DA
(
1ª
AULA)
, OU SEJA:
a12 . . . a1n 

a 22 . . . a 2n 
.
. . . . .

a n2 . . . a nn 
 xi j 


x
 2j
. 


. 
 x 
 nj 
0
 
. 
= 1 
 
. 
0
 
a11x 1j + . . . + a1n x nj = 0

. . . . . . . . . . . . . . . . . .

S j = a j1x 1j + . . . + a jn x nj = 0

. . . . . . . . . . . . . . . . . .
a n1x ij + . . . + ann x nj = 0
GAUSS-JORDAN :
A
Ic j 
→
ASSIM PARA DETERMINAR OS ELEMENTOS DA j-ÉSIMA COLUNA DA
MATRIZ A DEVEMOS RESOLVER O SISTEMA SJ , OU SEJA DEVEMOS
RESOLVER UM SISTEMA COM n EQUAÇÕES A n INCÓGNITAS.
I
Xc j 
n
SISTEMAS LINEARES
OPERAÇÕES
ELEMENTARES
COLUNA j DE I n
ORA, COMO:
COLUNA j DE X
1≤ j ≤ n
( 1ª AULA)
GAUSS-JORDAN :
A
MATRIZ I n
I n
→
CONCLUÍMOS QUE PARA OBTER TODOS OS ELEMENTOS DA MATRIZ X
DEVEMOS RESOLVER n SISTEMAS CADA UM DELES COM n EQUAÇÕES
A n INCÓGNITAS.
PORÉM, COMO TODOS ESTES SISTEMAS POSSUEM A MESMA MATRIZ
DE COEFICIENTES (MATRIZ A), PODEMOS UTILIZAR O ARTIFÍCIO:
I
n
OPERAÇÕES
ELEMENTARES
X

MATRIZ A - 1
EXEMPLO
DETERMINE SE POSSÍVEL A INVERSA DA MATRIZ:
SOLUÇÃO
INICIALMENTE CONSTRUÍMOS A MATRIZ:
4
1

2 5
1 - 3

3
A
1 4 3


A = 2 5 4
 1 -3 -2 


I3 
1 0 0

0 1 0
0 0 1 
SISTEMAS LINEARES
4
-2
( 1ª AULA)
A IDÉIA AGORA É APLICAR SOBRE ESTA MATRIZ UMA SEQÜÊNCIA DE
OPERAÇÕES ELEMENTARES COM O OBJETIVO DE TRANSFORMAR A
MATRIZ A EM UMA MATRIZ IDENTIDADE DE ORDEM 3:
4
1

2 5
1 - 3

3
4
-2
1 0 0

0 1 0
0 0 1 
A
I3
OPERAÇÕES
→
ELEMENTARES
1

0
0

0
0
2
-1
1
0
8
-5
0
1
- 11
7
I3
A-1
RECOMENDAÇÃO
CONVÉM AGORA VERIFICAR QUE DE FATO A . A – 1 = I 3 A FIM DE
EVITAR ERROS DE CÁLCULO
1

2
- 3 
CÁLCULO DE DETERMINANTES POR GAUSS
O PROCESSO SE BASEIA EM DOIS TEOREMAS:
TEOREMA I
O DETERMINANTE DE UMA MATRIZ QUADRADA:
SISTEMAS LINEARES
► TROCA DE SINAL QUANDO SE APLICA SOBRE A MATRIZ UMA
OPERAÇÃO DO TIPO E i j
► RESULTA MULTIPLICADO POR α QUANDO SE APLICA SOBRE A
MATRIZ UMA OPERAÇÃO DO TIPO E i ( α)
( 1ª AULA)
► NÃO SE ALTERA QUANDO SE APLICA SOBRE A MATRIZ UMA
OPERAÇÃO DO TIPO E i j (α)
TEOREMA II
O DETERMINANTE DE UMA MATRIZ TRIANGULAR É IGUAL AO
PRODUTO DOS ELEMENTOS DA DIAGONAL PRINCIPAL
EXEMPLO
CALCULE O DETERMINE DA MATRIZ:
2

1

A =
3

1
4
2
-1
1
-1
-1
1
1
*
*
K2
*
0
K3
0
0
2

2
1

1
ROTEIRO DA SOLUÇÃO
2

1
3

1
4
2
-1
1
-1
-1
1
1
2

2
1

1
 K1
OPERAÇÕES 
0


0
ELEMENTARES 
0

* 

* 
* 

K4 
SISTEMAS LINEARES
( 1ª AULA)
ASSIM O DETERMINANTE DA MATRIZ A É DADO POR:
K1 . K2 . K3 . K 4
CUIDADO:
NÃO SE ESQUEÇA DE:
► TROCAR O SINAL DO PRODUTO K1 . K 2 . K 3 . K 4 TODA VEZ QUE FOR
UTILIZADA UMA OPERAÇÃO DO TIPO E i j
► DIVIDIR O PRODUTO K1 . K 2 . K 3 . K 4 POR α TODA VEZ QUE FOR
UTILIZADA UMA OPERAÇÃO DO TIPO E i ( α)
RESPOSTA: - 18