Resolução de Sistemas
Lineares- Parte 1
• Exemplo 1: Problema da treliça
• Treliça: estrutura composta de barras (metálicas
ou de madeira) unidas por rótulas (nós) nas
suas extremidades.
• Determinar as componentes horizontal e vertical
das forças que atuam nas junções da treliça.
2
1
1
Fh
5
3
2
4
4
7
6
3
9
6
11
10
5
F1
8
F2
8
12
13
16
15
17
14
7
9
F3
10
Fh
• Forças que atuam na treliça: 17
• O número de junções (j) está relacionado com o
número de componentes da treliça (m):
2j-3 = m
Neste caso: 2 (10) – 3 = 17
• Logo, as componentes das forças são
determinadas pelas condições de equilíbrio nas
junções.
• Condições de equilíbrio:
• Junção 2:
 Fx  f1 cos

45

  f 4  f5 cos

45

  0

a
a

 Fx  a f1  f 4  a f5  0

 Fy   a f1  f3  a f5  0

• Junção 3:

 Fx   f 2  f 6  0


 Fy  f 3  F1  0
• Junção 4:

 Fx   f 4  f 8  0


 Fy   F7  0
• Junção 5:

 Fx   a f 5  f 6  a f 9  f 10  0


 Fy  a f 5  f 7  af9  F2  0
• Junção 6:

 Fx   f 8  a f 9  f12  a f13  0


 Fy  a f 9  f11  a f13  0
• Junção 7:
• Junção 8:
• Junção 9:
• Junção 10:

 Fx   f 10  f 14  0


 Fy F11  0

 Fx   f12  a f16  0


 Fy  a f15  af16  0

 Fx   a f 13  f 14  f 17  0


 Fy a f 13  f 15  f 10  0
 Fx  a f16  f17  0
Junção 10:
Junção 1:
 F
x
 F
x
 a f16  f17  Fh
 a f1  f 2  Fh
Sistema linear com 17 variáveis
( f1 , f 2 , f 3 ,..., f17 ) e 17 equações
Um sistema linear com m equações e
n incógnitas pode ser escrito na forma:
a11 x1  a12 x 2  ...  a1n x n  b1
a x  a x  ...  a x  b
 21 1
22 2
2n 2
2




 
a m1 x1  a m 2 x 2  ...  a mn x n  bn
coeficientes
a mn
constantes
bn
variáveis
xn
Resolver o sistema linear
Calcular os valores de x j ( j  1, 2, ...,n) , caso
existam, que satisfaçam as m equações.
• Notação matricial:
onde
 a11

 a 21
A


a
 m1
AX  B
a12
a 22

am2
é a matriz dos coeficientes.
 a1n 

 a2n 
 


 a mn 
 x1 
 
 x2 
X  

 
x 
 n
é o vetor das variáveis
 b1 
 
 b2 
B 

 
b 
 n
é o vetor dos termos independentes
• Consideremos a situação de duas equações e de duas
variáveis
2 x1  x 2  3
x1  3 x 2  2
2 x1  x 2  3
4 x1  2 x 2  6
2 x1  x 2  3
4 x1  2 x 2  2
1
x   
1

solução única
retas concorrentes
infinitas soluções
retas coincidentes
nenhuma solução
retas paralelas
  
   
x  
 3  2 

Comentário 1: no caso geral de m equações
e n variáveis também temos estas três situações: solução única, infinitas soluções e nenhuma solução.
Notação:
x  solução exata
x solução aproximada
RESOLUÇÃO DE SISTEMAS
LINEARES nxn
Métodos Diretos: fornecem solução exata, a
menos de arredondamentos e caso exista,
após um número finito de operações.]
Métodos Iterativos: geram uma seqüência de
vetores xk  , dada aproximação inicial x 0 ,
que converge para solução x , caso exista.
MÉTODOS DIRETOS
Método de Cramer pertence a esta classe.
Ax  b  A1 Ax  A1b  x  A1b onde A1 é a inversa de A
• Para calcular o determinante de um sistema
20x20 temos 21x20!x19 multiplicações, mais
este número de adições.
• Um computador de 1GHz (109 operações por
segundo) levaria 3X104 anos para calcular a
solução deste sistema
• Necessitamos de métodos mais eficientes!!!
MÉTODOS DIRETOS
ELIMINAÇÃO DE GAUSS
• O Método da Eliminação de Gauss consiste
em transformar o sistema linear original num
sistema linear equivalente com matriz dos
coeficientes triangular superior.
Sistemas equivalentes têm a mesma solução.
Sistema linear triangular tem solução imediata.
MÉTODOS DIRETOS
ELIMINAÇÃO DE GAUSS
Teorema 1: Seja Ax  b um sistema linear. Aplicando
sobre as equações deste uma seqüência de operações
elementares escolhidas entre:
a) trocar a ordem das equações,
b) multiplicar uma equação por constante,
c) adicionar um multiplo de uma equação a outra;
~ ~
obtemos um novo sistema Ax  b equivalente.
MÉTODOS DIRETOS
ELIMINAÇÃO DE GAUSS
• Suponha Det A  0 . A eliminação e efetuada por
colunas.
• O elemento a11 é denominado pivô na primeira etapa.
O elemento a 22 é o pivô da segunda etapa. O processo repete-se até termos um sistema linear triangular.
• Os elementos mi1  a1i a11 são os multiplicadores da
primeira etapa. Para gerar os zeros da coluna 1 linha i,
faça Li  Li  mi1 L1 na linha i. Repita o procso para a
coluna 2.
MÉTODOS DIRETOS
ELIMINAÇÃO DE GAUSS
Exemplo: seja o sistema linear
3x1  2 x 2  4 x3  1
x1  x 2  2 x3  2
4 x1  3x 2  2 x3  3
m21 
1
4
, m31 
3
3
L2  L2  m21 L1
L3  L3  m31 L1
3x1  2 x 2  4 x3  1
m32 
1/ 3
1
1/ 3
1 / 3x 2  2 / 3x3  5 / 3
 24 / 3x3  0
3x1  2 x 2  4 x3  1
1 / 3x 2  2 / 3x3  5 / 3
1 / 3x 2  22 / 3x3  5 / 3
  3
 
x   5 
 0
 
MÉTODOS DIRETOS
ELIMINAÇÃO DE GAUSS
Problema: Pivô nulo ou próximo de zero!!!!
Estratégia de pivoteamento parcial
• No início de cada eliminação de Gauss,
trocando as linhas, escolher para o pivô o
maior a ij da coluna j.
MÉTODOS DIRETOS
ELIMINAÇÃO DE GAUSS
Estratégia de pivoteamento total
• No início de cada eliminação de Gauss,
escolher para o pivô o maior a ij entre todos
elementos que atuam no processo de
eliminação.
• Problema: Muitas operações de comparação!!
MÉTODOS DIRETOS
ELIMINAÇÃO DE GAUSS
Pivoteamento Parcial X Pivoteamento total
3 x1  2 x 2  1x3  x 4  5
0 x1  1x 2  0 x3  3 x 4  6
0 x1  3 x 2  5 x3  7 x 4  7
0 x1  2 x 2  4 x3  0 x 4  15
3 x1  2 x 2  1x3  x 4  5
0 x1  1x 2  0 x3  3 x 4  6
0 x1  3 x 2  5 x3  7 x 4  7
0 x1  2 x 2  4 x3  0 x 4  15
parcial
3 x1  2 x 2  1x3  x 4  5
0 x1  3 x 2  5 x3  7 x 4  7
continuar
0 x1  1x 2  0 x3  3 x 4  6
0 x1  2 x 2  4 x3  0 x 4  15
total
3 x1   x 4  1x3  2 x 2  5
0 x1  7 x 4  5 x3  3 x 2  7
0 x1  3 x 4  0 x3  1x 2  6
0 x1  0 x 4  4 x3  2 x 2  15
continuar
MÉTODOS DIRETOS
FATORAÇÃO LU
Seja o sistema linear A x  b . Este processo de
fatoração consiste em decompor a matriz A em
Um produto de dois ou mais fatores.
Exemplo: Seja A  C D , então resolver A x  b
É equivalente a resolver C y  b e depois
Dx y .
MÉTODOS DIRETOS
FATORAÇÃO LU
Na fatoração A  L U a matriz L é
triangular inferior com diagonal unitária
e a matriz U é triangular superior.
MÉTODOS DIRETOS
FATORAÇÃO LU
Teorema da fatoração LU
Dada uma matriz quadrada nxn. Se Det A  0
então existe uma única matriz triangular inferior
L  mij , com diagonal principal unitária, e uma
única matriz triangular superior U  uij , tais
que L U  A
n
u ii
, e det A 

i 0
MÉTODOS DIRETOS
FATORAÇÃO LU
Exemplo de fatoração LU. Considere
3x1  2 x 2  4 x3  1
x1  x 2  2 x3  2
4 x1  3x 2  2 x3  3
onde
 3 2 4


A   1 1 2
 4 3 2


Do método de Gauss sem pivoteamento:
FATORAÇÃO LU
 3 2 4


A   1 1 2
 4 3 2


4 
3 2


0 1/ 3 2 / 3 
 0 1 / 3  10 / 3 


2
4 
 3


 1/ 3 1/ 3 2 / 3 
 4 / 3 1 / 3  10 / 3 


No último passo foi acrescentados os multiplicadores mij
Os multiplicadores são definidos como segue: da
equação (linha) j subtraímos a equação (linha) i
multiplicada por mij , de modo a escalonar a matriz A
Continuando o processo:
FATORAÇÃO LU
 3 2 4


A   1 1 2
 4 3 2


2
4 
 3


 1/ 3 1/ 3 2 / 3 
 4 / 3 1 / 3  10 / 3 


2
4 
 3


 1 / 3 1 / 3 2 / 3
4 / 3 1  4 


Assim, as matrizes L e U são
 1 0 0


L  1/ 3 1 0
 4 / 3 1 1


4 
3 2


U   0 1 / 3 2 / 3
0 0  4 


LU  A
FATORAÇÃO LU
Resolvendo o sistema A x  b por fatoração LU:
3x1  2 x 2  4 x3  1
x1  x 2  2 x3  2
4 x1  3x 2  2 x3  3
L yb
y1  1
1 / 3 y1  y 2  2
4 / 3 y1  y 2  y 3  3
Continuando
U x y
3x1  2 x 2  4 x3  1
1 / 3 x 2  2 / 3 x3  5 / 3
 4 x3  0
  3
 
x 5 
 0 
 
 1 


y   5 / 3
 0 


FATORAÇÃO LU + PIVOTEAMENTO
Fatoração LU com pivoteamento parcial.
Fatoração LU com pivoteamento total.
O pivoteamento pode ser implementado por
meio da matriz de permutação.
Definição: Uma matriz quadrada de ordem n é uma
matriz de permutação se pode ser obtida da matriz
identidade de ordem n permutando-se suas linhas
(ou colunas).
FATORAÇÃO LU + PIVOTEAMENTO
 0 1 0


Exemplo de matriz permutação P   0 0 1 
1 0 0


 3 1 4


Seja A   1 5 9 
 2 6 5


 0 1 0  3 1 4  1 5 9

 
 

Note: P A   0 0 1    1 5 9    2 6 5 
 1 0 0  2 6 5  3 1 4

 
 

FATORAÇÃO DE CHOLESKY
Definição: Uma matriz quadrada A de ordem n é
T
n
x
A
x

0

x


definida positiva se
.
Definição: A fatoração de Cholesky de uma matriz A,
simétrica positiva, é dada por
A  G GT
onde G : n  n ,
com G uma matriz triangular inferior com elementos da
diagonal estritamente positivos.
FATORAÇÃO DE CHOLESKY
Do teorema LU, temos A  L D U , onde D é uma
matriz diagonal de ordem n. Ainda, se A for simétrica,
então U  LT e a fatoração escreve-se como:
A  L D LT  L DD LT
Portanto, G  L D
onde dii  d ii
FATORAÇÃO DE CHOLESKY
Considere a matriz
 16  4 12  4 


 4 2 1 1 
A
12  1 14  2 


  4 1  2 83 


Calculando os fatores L U
0
 16  4 12  4   1

 
  4 2  1 1    1/ 4 1
A

12  1 14  2   3 / 4
2

 
  4 1  2 83    1 / 4 0

 
0
0
1
1
0  16  4 12  4 
 

0  0
1
2
0 

0  0
0 1
1 
 



1  0
0
0 81 
FATORAÇÃO DE CHOLESKY
Calculando os fatores L D e L D U
0
 16  4 12  4   1

 

4
2

1
1

   1/ 4 1
A

12  1 14  2   3 / 4
2

 
  4 1  2 83    1 / 4 0

 
0
 1

  1/ 4 1
A
3/ 4
2

  1/ 4 0

0
0
1
1
0  16
 
0  0

0  0
 
1   0
0
1
0
0
0
0
1
1
0  16  4 12  4 
 

0  0
1
2
0 

 LU
0  0
0
1
1 
 



1  0
0
0 81 
0 0  1  1/ 4 3 / 4  1/ 4
 

0 0  0
1
2
0 

 L D LT


1 0
0
0
1
1
 



0 81  0
0
0
1 
FATORAÇÃO DE CHOLESKY
Enfim,
0
 1

  1/ 4 1
A
3/ 4
2

  1/ 4 0

0
0
1
1
0  4
 
0  0

0  0
 
1   0
0
1
0
0
0
0
1
0
0  4
 
0  0

0  0
 
9   0
0
1
0
0
0
0
1
0
0 1  1/ 4 3 / 4  1/ 4
 

0  0
1
2
0 

 L D D LT



0
0
0
1
1
 



9 0
0
0
1 
Ou ainda,
 4

1
A
3

1

0
1
2
0
0
0
1
1
0  4  1
 
0  0 1


0
0 0
 
9   0 0
3  1

2 0
 G GT

1 1

0 9 
FATORAÇÃO DE CHOLESKY
Teorema da Fatoração de Cholesky
Se A é uma matriz simétrica positiva definida,
então existe uma única matriz triangular inferior
G com diagonal estritamente positiva, tal que
AGG
T
FATORAÇÃO DE CHOLESKY
Resolução de sistemas lineares é semelhante
T
ao método LU. Seja A  G G , então resolver
A x  b é equivalente a resolver G y  b e
depois G T x  y .
COMPARAÇÃO DOS MÉTODOS
Fatoração de Cholesky: Primeiro verificar se
uma matriz simétrica é definida positiva. Em
caso positivo, continuar com o método de
Cholesky.
O método de Cholesky requer
aproximadamente a metade das operações
necessárias para a fatoração LU, da ordem
de n3/6 operações.