Resolução de sistemas linearesSME 0200 – Cálculo Numérico I
Docente: Prof. Dr. Marcos Arenales
Estagiário PAE: Pedro Munari
Introdução
� Sistemas lineares são de grande importância para a descrição e resolução de problemas que surgem nas mais diversas áreas da ciência e engenharia.
� Geometria� Redes elétricas, hidráulicas, de tráfego, ...� Distribuição de calor� Química� Economia� Otimização linear� Estatística� Jogos� ...(http://aix1.uottawa.ca/~jkhoury/system.html)
Introdução
� Por que utilizar um método?
=+++
=+++=+++
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
K
K
K
K
2211
22222121
11212111
Introdução
� Notação
bAx =
=+++
=+++=+++
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
K
K
K
K
2211
22222121
11212111
=
mnmm
n
n
aaa
aaa
aaa
A
K
MOMM
K
K
21
22221
11211
=
nx
x
x
xM
2
1
=
mb
b
b
bM
2
1
,nx ℜ∈,nmA ×ℜ∈ .mb ℜ∈
Número de soluções
� Dado um sistema linear, apenas uma das situações abaixo pode ocorrer:
� O sistema tem solução única
� O sistema tem infinitas soluções
� O sistema não admite solução
-0.5 0.5 1 1.5 2 2.5
-2
-1
1
2
3
4
Número de soluções
−=−=+
23
32
21
21
xx
xx2x
1x
Solução única
-2 -1 1 2 3 4 5
-6
-4
-2
2
4
6
Número de soluções
=+=+
624
32
21
21
xx
xx2x
1x
Infinitas soluções
-1 -0.5 0.5 1 1.5 2
-2
2
4
Número de soluções
=+=+
224
32
21
21
xx
xx2x
1x
Não admite solução
Número de soluções
� Graficamente...� Solução única:
� Retas concorrentes. A solução é o ponto onde as retas se cruzam.
� Infinitas soluções:
� Retas coincidentes. Todos os pontos sobre a reta são soluções do sistema.
� O sistema não admite solução:
� Retas paralelas. As retas não se cruzam e, portanto, não existe nenhum ponto que esteja sobre as duas ao mesmo tempo.
Número de soluções
� No caso geral...
� Precisamos analisar o Posto e a
Imagem da matriz A, de acordo com
suas dimensões m e n.
,nx ℜ∈bAx = ,nmA ×ℜ∈ .mb ℜ∈
-0.5 0.5 1 1.5 2 2.5
-2
-1
1
2
3
4
Número de soluções
2x
2)Im( ℜ=A
−=−=+
23
32
21
21
xx
xx
Solução única
2)( =Aposto
Número de soluções
� As colunas de A são Linearmente Independentes e formam uma base do R2.
� b pode ser escrito como combinação linear das colunas de A.
−=−=+
23
32
21
21
xx
xx)Im(Ab ∈
Sistema compatSistema compatíível determinadovel determinado
-2 -1 1 2 3 4 5
-6
-4
-2
2
4
6
Número de soluções
=+=+
624
32
21
21
xx
xx2x
1x
Infinitas soluções
2)Im( ℜ⊂A
1)( =Aposto
Número de soluções
� As colunas de A são Linearmente Dependentes e não formam uma base do R2.
� Basta uma coluna de A para escrever b.
=+=+
624
32
21
21
xx
xx)Im(Ab ∈
Sistema compatSistema compatíível vel inindeterminadodeterminado
-1 -0.5 0.5 1 1.5 2
-2
2
4
Número de soluções
=+=+
224
32
21
21
xx
xx
Não admite solução
2)Im( ℜ⊂A
1)( =Aposto
Número de soluções
� As colunas de A são Linearmente Dependentes e não formam uma base do R2.
� b não pode ser escrito como combinação das colunas de A.
=+=+
224
32
21
21
xx
xx)Im(Ab ∉
Sistema Sistema inincompatcompatíívelvel
Número de soluções
� Essas situações se estendem para o caso
geral, sempre que m = n.
� Quando m ≠ n, temos:
� posto(A) ≤ min{m, n}
� se m < n o sistema nunca pode ter solução
única, pois posto(A) < n
� se m > n o sistema pode não ter solução
Métodos de resolução
Métodos de resolução
� Veremos aqui métodos para a
resolução de sistemas com n linhas
e n variáveis (a matriz A deve ter posto completo).
� Os métodos de resolução podem ser divididos em dois grupos:� Métodos Exatos (ou Diretos)
� Métodos Iterativos
Eliminação de Gauss
=
=++=+++
mnmn
nn
nn
dxc
dxcxc
dxcxcxc
22222
11212111
O
K
K
(2)
Eliminação de Gauss
� Qual sistema é mais fácil de ser resolvido?
=+++
=+++=+++
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
K
K
K
K
2211
22222121
11212111
(1)
Resolução de sistema triangular
Algoritmo:
x[n] := b[n]/A[n][n];
Para i = n-1 até 1, faça
início
soma := 0;
Para j = i+1 até n, faça
soma := soma + A[i][j] * x[j];
x[i] := (b[i] - soma) / A[i][i];
fim
Eliminação de Gauss
� Consiste em transformar o sistema a ser
resolvido em um sistema triangular
equivalente, por meio de operações
elementares.
� A solução do sistema original é obtida
pela resolução desse sistema triangular.
Eliminação de Gauss
� Operações elementares:� Multiplicar uma equação por uma
constante não-nula;
� Adicionar um múltiplo de uma equação a uma outra equação;
� Trocar duas equações de posição.
� O sistema resultante tem as mesmas soluções que sistema o original
Eliminação de Gauss
nnnnn
n
n
b
b
b
aaa
aaa
aaa
M
K
MOMM
K
K
2
1
21
22221
11211
Eliminação de Gauss
)1(
)1(2
)1(1
)1()1(2
)1(1
)1(2
)1(22
)1(21
)1(1
)1(12
)1(11
nnnnn
n
n
b
b
b
aaa
aaa
aaa
M
K
MOMM
K
K
Eliminação de Gauss
)1(
)1(2
)1(1
)1()1(2
)1(1
)1(2
)1(22
)1(21
)1(1
)1(12
)1(11
nnnnn
n
n
b
b
b
aaa
aaa
aaa
M
K
MOMM
K
K
Zerar esses elementosutilizando operaçõeselementares
Eliminação de Gauss
)1(
)1(2
)1(1
)1()1(2
)1(1
)1(2
)1(22
)1(21
)1(1
)1(12
)1(11
nnnnn
n
n
b
b
b
aaa
aaa
aaa
M
K
MOMM
K
K
pivô
Zerar esses elementosutilizando operaçõeselementares
Eliminação de Gauss
)2(
)2(2
)1(1
)2()2(2
)2(2
)2(22
)1(1
)1(12
)1(11
0
0
nnnn
n
n
b
b
b
aa
aa
aaa
M
K
MOMM
K
K
Eliminação de Gauss
)2(
)2(2
)1(1
)2()2(2
)2(2
)2(22
)1(1
)1(12
)1(11
0
0
nnnn
n
n
b
b
b
aa
aa
aaa
M
K
MOMM
K
K
Zerar esses elementosutilizando operaçõeselementares
pivô
Eliminação de Gauss
� Ao fim do processo:
Eliminação de Gauss
)1(
)1(2
)1(1
)1()1(2
)1(1
)1(2
)1(22
)1(21
)1(1
)1(12
)1(11
nnnnn
n
n
b
b
b
aaa
aaa
aaa
M
K
MOMM
K
K
)1(11
)1(1
1 a
am i
i =Multiplicador
12122 LmLL −←
11LmLL nnn −←
...
Passo 1
Eliminação de Gauss
)2(
)2(2
)1(1
)2()2(2
)2(2
)2(22
)1(1
)1(12
)1(11
0
0
nnnn
n
n
b
b
b
aa
aa
aaa
M
K
MOMM
K
K
)1(11
)1()2(
)1(11
)1()2(
bmbb
amaa
iii
jiijij
−=
−=
Eliminação de Gauss – Algoritmo
Para k = 1 até n-1, faça
início
Para i = k+1 até n, faça
início
mult := A[i][k] / A[k][k];
A[i][k] := 0;
Para j = k+1 até n, faça
A[i][j] := A[i][j] - mult * A[k][j];
b[i] := b[i] - mult * b[k];
fim_para (i)
fim_para (k)
Resolva o sistema triangular resultante;
Eliminação de Gauss – Exemplo 1
� Resolva o sistema linear
=+−=+−
=+−
12 5
511296
20523
31
321
321
xx
xxx
xxx
Eliminação de Gauss – Exemplo 1
� Notação matricial
−−−
1
51
20
205
1296
523
Eliminação de Gauss – Exemplo 1
� Passo k = 1
−−−
1
51
20
205
1296
523
Eliminação de Gauss – Exemplo 1
� Passo k = 1� i = 2
12122 LmLL −←
−−−
1
51
20
205
1296
523
23
6
11
2121 ===
a
am
Eliminação de Gauss – Exemplo 1
� Passo k = 1� i = 2
12122 LmLL −←
−−−
1
51
20
205
1296
523
23
6
11
2121 ===
a
am
03*2611212121 =−=−= amaa
Eliminação de Gauss – Exemplo 1
� Passo k = 1� i = 2
12122 LmLL −←
−−−
1
51
20
205
1290
523
23
6
11
2121 ===
a
am
03*2611212121 =−=−= amaa
( ) 52*2912212222 −=−−−=−= amaa
Eliminação de Gauss – Exemplo 1
� Passo k = 1� i = 2
12122 LmLL −←
−−−
1
51
20
205
1250
523
23
6
11
2121 ===
a
am
03*2611212121 =−=−= amaa
( ) 52*2912212222 −=−−−=−= amaa
25*21213212323 =−=−= amaa
Eliminação de Gauss – Exemplo 1
� Passo k = 1� i = 2
12122 LmLL −←
−−−
1
51
20
205
250
523
23
6
11
2121 ===
a
am
1120*25112122 =−=−= bmbb
Eliminação de Gauss – Exemplo 1
� Passo k = 1
−−−
1
11
20
205
250
523
Eliminação de Gauss – Exemplo 1
� Passo k = 1� i = 3
−−−
1
11
20
205
250
523
13133 LmLL −←
3
5
11
3131
−==a
am
Eliminação de Gauss – Exemplo 1
� Passo k = 1� i = 3
−−−
1
11
20
205
250
523
13133 LmLL −←
3
5
11
3131
−==a
am
03*3
5511313131 =
−−−=−= amaa
Eliminação de Gauss – Exemplo 1
� Passo k = 1� i = 3
−−
1
11
20
200
250
523
13133 LmLL −←
3
5
11
3131
−==a
am
3
10)2(*
3
5012313232 −=−
−−=−= amaa
Eliminação de Gauss – Exemplo 1
� Passo k = 1� i = 3
−−−
1
11
20
23100
250
523
13133 LmLL −←
3
5
11
3131
−==a
am
3
31)5(*
3
5213313333 =
−−=−= amaa
Eliminação de Gauss – Exemplo 1
� Passo k = 1� i = 3
−−−
1
11
20
331
3100
250
523
13133 LmLL −←
3
5
11
3131
−==a
am
3
10320*
3
5113133 =
−−=−= bmbb
Eliminação de Gauss – Exemplo 1
� Passo k = 1
−−−
3103
11
20
331
3100
250
523
Eliminação de Gauss – Exemplo 1
� Passo k = 2
−−−
3103
11
20
331
3100
250
523
Eliminação de Gauss – Exemplo 1
� Passo k = 2� i = 3
−−−
3103
11
20
331
3100
250
523
23233 LmLL −←
3
2
22
3232 ==
a
am
Eliminação de Gauss – Exemplo 1
� Passo k = 2� i = 3
−−−
3103
11
20
331
3100
250
523
23233 LmLL −←
3
2
22
3232 ==
a
am
0)5(*3
2
3
1022323232 =−
−−=−= amaa
Eliminação de Gauss – Exemplo 1
� Passo k = 2� i = 3
−−
3103
11
20
33100
250
523
23233 LmLL −←
3
2
22
3232 ==
a
am
92*3
2
3
3123323333 =
−=−= amaa
Eliminação de Gauss – Exemplo 1
� Passo k = 2� i = 3
−−
3103
11
20
900
250
523
23233 LmLL −←
3
2
22
3232 ==
a
am
2711*3
2
3
10323233 =
−=−= bmbb
Eliminação de Gauss – Exemplo 1
� Passo k = 2� Sistema triangular obtido:
−−
27
11
20
900
250
523
Eliminação de Gauss – Exemplo 1
� Resolução do sistema triangular
−−
27
11
20
900
250
523
39
273 ==x
Eliminação de Gauss – Exemplo 1
� Resolução do sistema triangular
15
5
5
3*211
22
32322 −=
−=
−−=−=
a
xabx
−−
27
11
20
900
250
523
39
273 ==x
Eliminação de Gauss – Exemplo 1
� Resolução do sistema triangular
15
5
5
3*211
22
32322 −=
−=
−−=−=
a
xabx
−−
27
11
20
900
250
523
39
273 ==x
13
3
3
)3*5)1(*)2((20)(
11
31321211 ==+−−−=+−=
a
xaxabx
Eliminação de Gauss – Exemplo 1
� Logo,
é solução do sistema:
=+−=+−
=+−
12 5
511296
20523
31
321
321
xx
xxx
xxx
−=
3
1
1
3
2
1
x
x
x
Eliminação de Gauss – Exemplo 2
� Resolva o sistema linear:
−=+−−=++−
=++−−=++−
601082
48104
4111236
7532
432
4321
4321
4321
xxx
xxxx
xxxx
xxxx
Eliminação de Gauss – Exemplo 2
� Notação matricial:
−
−
−−−−−
60
4
4
7
10820
81014
111236
5312
Eliminação de Gauss – Exemplo 2
� Passo k = 1:
−
−
−−−−−
60
4
4
7
10820
81014
111236
5312
Eliminação de Gauss – Exemplo 2
� Passo k = 1:� i = 2
−
−
−−−−−
60
4
4
7
10820
81014
111236
5312
12122 LmLL −←
32
6
11
2121 ===
a
am
Eliminação de Gauss – Exemplo 2
� Passo k = 1:� i = 3
−
−
−−−
−−
60
4
25
7
10820
81014
4300
5312
13133 LmLL −←
22
4
11
3131 ===
a
am
Eliminação de Gauss – Exemplo 2
� Passo k = 1:� i = 4
−
−
−−−−
−
60
18
25
7
10820
2410
4300
5312
14144 LmLL −←
02
0
11
4141 ===
a
am
Eliminação de Gauss – Exemplo 2
� Passo k = 1:
−
−
−−−−
−
60
18
25
7
10820
2410
4300
5312
Eliminação de Gauss – Exemplo 2
� Passo k = 2:
−
−
−−−−
−
60
18
25
7
10820
2410
4300
5312
Eliminação de Gauss – Exemplo 2
� Passo k = 2:
−
−
−−−−
−
60
18
25
7
10820
2410
4300
5312
O pivô é nulo!
Estratégias de pivotamento
� O que acontece se o pivô for nulo?
� Pivô próximo de zero pode levar a resultados incorretos.
� Para contornar esses dois problemas deve-se adotar uma estratégia para a escolha de um “bom” pivô.
Estratégias de pivotamento
� Pivotamento parcial� Escolher para pivô o elemento de maior
módulo na coluna, dentre os que ainda irão atuar no processo de eliminação.
� Pivotamento completo� Escolher para pivô o elemento de maior
módulo dentre todos os elementos que ainda irão atuar no processo de eliminação.
Eliminação de Gauss – Exemplo 2
� Resolva o sistema linear a seguir, utilizando pivotamento parcial:
−=+−−=++−
=++−−=++−
601082
48104
4111236
7532
432
4321
4321
4321
xxx
xxxx
xxxx
xxxx
Eliminação de Gauss – Exemplo 2
� Notação matricial:
−
−
−−−−−
60
4
4
7
10820
81014
111236
5312
Eliminação de Gauss – Exemplo 2
� Passo k = 1:
−
−
−−−−−
60
4
4
7
10820
81014
111236
5312
Eliminação de Gauss – Exemplo 2
� Passo k = 1:� Qual o maior elemento (em módulo)?
−
−
−−−−−
60
4
4
7
10820
81014
111236
5312
Eliminação de Gauss – Exemplo 2
� Passo k = 1:� Qual o maior elemento (em módulo)?
−
−
−−−−−
60
4
4
7
10820
81014
111236
5312Troca de linhas(permutação)
Eliminação de Gauss – Exemplo 2
� Passo k = 1:� O pivô é o maior elemento da coluna!
−
−
−−−−−
60
4
7
4
10820
81014
5312
111236
Eliminação de Gauss – Exemplo 2
� Passo k = 1:� i = 2
−
−
−−−−−
60
4
7
4
10820
81014
5312
111236
12122 LmLL −←
3
1
6
2
11
2121 ===
a
am
Eliminação de Gauss – Exemplo 2
� Passo k = 1:� i = 3
−
−
−−−
−−
60
4
3333.8
4
10820
81014
3333.1100
111236
13133 LmLL −←
3
2
6
4
11
3131 ===
a
am
Eliminação de Gauss – Exemplo 2
� Passo k = 1:� i = 4
−
−
−−
−−
60
33333.1
3333.8
4
10820
66667.0210
3333.1100
111236
14144 LmLL −←
06
0
11
4141 ===
a
am
Eliminação de Gauss – Exemplo 2
� Passo k = 1:
−
−
−−
−−
60
33333.1
3333.8
4
10820
66667.0210
3333.1100
111236
Eliminação de Gauss – Exemplo 2
� Passo k = 2:
−
−
−−
−−
60
33333.1
3333.8
4
10820
66667.0210
3333.1100
111236
Eliminação de Gauss – Exemplo 2
� Passo k = 2:� Qual o maior elemento (em módulo)?
−
−
−−
−−
60
33333.1
3333.8
4
10820
66667.0210
3333.1100
111236
Eliminação de Gauss – Exemplo 2
� Passo k = 2:� Qual o maior elemento (em módulo)?
−
−
−−
−−
60
33333.1
3333.8
4
10820
66667.0210
3333.1100
111236
Troca de linhas(permutação)
Eliminação de Gauss – Exemplo 2
� Passo k = 2:� O pivô é o maior elemento da coluna!
−
−
−
−−−
3333.8
33333.1
60
4
3333.1100
66667.0210
10820
111236
Eliminação de Gauss – Exemplo 2
� Passo k = 2:� i = 3
−
−
−
−−−
3333.8
33333.1
60
4
3333.1100
66667.0210
10820
111236
Eliminação de Gauss – Exemplo 2
� Passo k = 2:� i = 4
−−
−
−−−−
−
3333.8
667.28
60
4
3333.1100
6667.5200
10820
111236
Eliminação de Gauss – Exemplo 2
� Passo k = 2:
−−
−
−−−−
−
3333.8
667.28
60
4
3333.1100
6667.5200
10820
111236
Eliminação de Gauss – Exemplo 2
� Passo k = 3:� O pivô é o maior elemento da coluna!
−−
−
−−−−
−
3333.8
667.28
60
4
3333.1100
6667.5200
10820
111236
Eliminação de Gauss – Exemplo 2
� Passo k = 3:� i = 4
−−
−
−−−−
−
3333.8
667.28
60
4
3333.1100
6667.5200
10820
111236
Eliminação de Gauss – Exemplo 2
� Passo k = 3:� Sistema triangular obtido:
−−
−−−−
−
6
667.28
60
4
5.1000
6667.5200
10820
111236
Eliminação de Gauss – Exemplo 2
� Resolução do sistema triangular:
−−
−−−−
−
6
667.28
60
4
5.1000
6667.5200
10820
111236
45.1
64 −=
−=x
Eliminação de Gauss – Exemplo 2
� Resolução do sistema triangular:
−−
−−−−
−
6
667.28
60
4
5.1000
6667.5200
10820
111236
32
6
2
)4(*6667.5667.28
33
43433 =
−−=
−−−−=−=
a
xabx
Eliminação de Gauss – Exemplo 2
� Resolução do sistema triangular:
−−
−−−−
−
6
667.28
60
4
5.1000
6667.5200
10820
111236
22
4
2
))4(*103*)8((60)(
22
42432322 −=
−=
−−+−−−=+−=
a
xaxabx
Eliminação de Gauss – Exemplo 2
� Resolução do sistema triangular:
−−
−−−−
−
6
667.28
60
4
5.1000
6667.5200
10820
111236
16
6
6
)44366(4)(
11
41431321211 ==−+−=++−=
a
xaxaxabx
Eliminação de Gauss – Exemplo 2
� Solução:
−
−=
4
3
2
1
4
3
2
1
x
x
x
x
Decomposição LU
Decomposição LU
� Decompor a matriz A em um produto de dois fatores:
� L: matriz triangular inferior
� U: matriz triangular superior
Ax = b LU x = b
A = LU
Decomposição LU
� U é a matriz triangular resultante na eliminação de Gauss.
� Quem é L então?
� Por que utilizar a decomposição LU se vamos obter a mesma matriz da eliminação de Gauss?