Embed Size (px)
Citation preview
Tópicos de
Métodos Numéricos em
Sistemas de Equações
Lineares
Rodolfo Maduro Almeida
Sistemas de Equações Lineares
• Os sistemas de equações lineares
aparecem em inúmeros problemas de
modelagem computacional em engenharias
e ciências.
• O que é um sistema linear?
– Conjunto formado por duas ou mais equações
lineares definidas nas mesmas incógnitas.
Sistemas de Equações Lineares
Forma geral:
nnnnnnn
nn
nn
bxaxaxaxa
bxaxaxaxa
bxaxaxaxa
332211
22323222121
11313212111
n , 2, ,1, ji
teindependen termo:b
escoeficient :a
incógnitas :x
i
ij
i
Sistemas de Equações Lineares
Forma matricial:
nnnnn
n
n
b
b
b
x
x
x
aaa
aaa
aaa
2
1
2
1
221
22221
11211
bxA
matriz de
coeficientes
vetor de
incógnitasvetor de
termos
independentes
Classificação dos SistEqLin
A classificação é feita em função do número de
soluções que o sistema admite.
• Sistema Possível ou Consistente: possui
pelo menos uma solução:
– Determinado: admite uma única solução.
– Indeterminado: admite mais de uma solução.
• Sistema Impossível ou Inconsistente: não
admite solução.
Classificação dos SistEqLin
Admite única solução: (x,y) = (4,2) que equivale ao
ponto de intersecção das retas.
Sistema possível e determinado
Classificação dos SistEqLin
Infinitas soluções: todos os pares de pontos (x,y)
sobre as retas coincidentes.
Sistema possível indeterminado
Classificação dos SistEqLin
Não admite solução: retas paralelas (não se interceptam).
Sistema impossível
ATENÇÃO:
Neste curso iremos trabalhar com a solução numérica de sistemas
de equações lineares que admitem uma única solução!
Classificação dos SistEqLin
Sistemas equivalentes
Solução numérica dos SistEqLin
• Métodos exatos: Buscam encontrar a solução
exata do sistema de equações lineares.
– Eliminação de Gauss
– Decomposição LU
• Métodos iterativos: Conjunto de
procedimentos que são executados a medida
que se obtém sucessivas aproximações da
solução do sistema.
– Método de Jacobi
– Método de Gauss-Seidel
MÉTODOS EXATOS
• Eliminação de Gauss
• Decomposição LU
Solução numérica dos SistEqLin
Solução de sistemas triangulares
Solução de sistemas triangulares
Solução de um sistema triangular inferior:
Solução de sistemas triangulares
Solução de sistemas triangulares
Substituição progressiva:
Solução de sistemas triangulares
• Implementar a solução do seguinte sistema
linear triangular inferior:
Solução de sistemas triangulares
A = [ 1 0 0; 0 1 0; 0.5 0.5 1];
b = [9 1 7];
n = 3;
x = zeros(n,1);
x(1) = b(1)/A(1,1);
for i=2:n
soma = 0.0;
for j=1:i-1
soma = soma + A(i,j)*x(j);
end
x(i) = (b(i)-soma)/A(i,i);
end
disp('Solucao encontrada: ')
disp(x)
Solução de sistemas triangulares
Solução de um sistema triangular superior:
Solução de sistemas triangulares
Substituição retroativa:
Solução de sistemas triangulares
• Implementar a solução do seguinte sistema
linear triangular superior:
Solução de sistemas triangulares
A = [2 1 3; 0 -1 1; 0 0 1];
b = [9 1 2];
n = 3;
x = zeros(n,1);
x(n) = b(n)/A(n,n);
for i=n-1:-1:1
soma = 0.0;
for j=i+1:n
soma = soma + A(i,j)*x(j);
end
x(i) = (b(i)-soma)/A(i,i);
end
disp('Solucao encontrada: ')
disp(x)
Solução de Sistemas Triangulares
• Vimos que é simples a solução de um
sistema linear quando este está na forma
triangular.
• Existem métodos para solução de sistemas
lineares que se aproveitam desta facilidade.
• Consistem em executar operações sobre a
matriz de coeficientes A de modo a deixá-la
na forma triangular superior ou inferior
• Exemplos:
– Método da eliminação de Gauss
– Método da decomposição LU
Método da Eliminação de Gauss
bxA '' bxA
sistema linear
originalsistema triangular superior
equivalente
Método da Eliminação de Gauss
• Resolver o sistema linear
2223
742
80484
321
321
321
xxx
xxx
xxx
Método da Eliminação de Gauss
• Resolver o sistema linear
22
7
80
213
412
484
3
2
1
x
x
x
Método da Eliminação de Gauss
• Matriz aumentada:
L1
L2
L3
pivô
22213
7412
80484
22213
7412
80484
Método da Eliminação de Gauss
• Matriz aumentada:
L1 = L1/4
22213
7412
20121
Método da Eliminação de Gauss
• Matriz aumentada:
L2 = L2 - 2 x L1
L3 = L3 - 3 x L1
38170
33630
20121
Método da Eliminação de Gauss
• Matriz aumentada:
L2 = L2/(- 3)
38170
11210
20121
Método da Eliminação de Gauss
• Matriz aumentada:
L3 = L3 + 7 x L2
391300
11210
20121
Método da Eliminação de Gauss
• Matriz aumentada:
L3 = L3/13
3100
11210
20121
Método da Eliminação de Gauss
• Matriz aumentada:
• Sistema triangular superior equivalente:
Resolvido via substituição retroativa:
Solução :
3
112
202
3
32
321
x
xx
xxx
Método da Eliminação de Gauss
3
5
7
3
2
1
x
x
x
Método da Decomposição LU
Essência do método: Fatoração LU
A = L·U
Logo:
A·x = b (L·U)·x = b
matriz de coeficientesmatriz triangular
inferior
matriz triangular
superior
Método da Decomposição LU
• Método de Doolittle (matriz L com diagonal
unitária):
Método da Decomposição LU
Método da Decomposição LU
• Efetue a decomposição LU da matriz:
311
413
125
A
Método da Decomposição LU
Passo 1: Decompõe a matriz de coeficientes
como o produto entre duas matrizes: uma
triangular inferior L e outra triangular superior U:
A = L·U
Logo:
A·x = b (L·U)·x = b
Passo 2: define U·x = y e resolve L·y = b via
substituição progressiva e encontra o valor de y.
Passo 3: resolve U·x = y via substituição
retroativa e encontra a solução x.
Método da Decomposição LU
Resolva o seguinte sistema linear pelo
método da decomposição LU:
5
7
0
311
413
125
z
y
x
Script solução (linhas 1 a 31)
Script solução (linhas 32 a 54)
Solução
-->exec('decomposicao_lu.sce',0)
Forneca a matriz de coeficientes A[n x n]: [5 2 1; 3 1 4; 1 1 3]
A =
5. 2. 1.
3. 1. 4.
1. 1. 3.
Forneca o vetor de termos independentes: b[n x 1] [0; -7; -5]
b =
0.
- 7.
- 5.
L:
1. 0. 0.
0.6 1. 0.
0.2 - 3. 1.
U:
5. 2. 1.
0. - 0.2 3.4
0. 0. 13.
L x U:
5. 2. 1.
3. 1. 4.
1. 1. 3.
Solucao encontrada
- 4.441D-16
1.
- 2.
