Sistemas Lineares - Gauss

Prévia do material em texto

Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
– Método da Eliminação de Gauss
● Evita o cálculo da inversa de A
● Não apresenta problemas com tempo d execução
● Transforma o sistema original em um equivalente com a matriz
● dos coeficientes A triangular superior.
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
– Resolução de Sistemas Triangulares
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
– Resolução de Sistemas Triangulares
Seja Ax=b, onde A é uma matriz nxn triangular superior
{
a11 x1  a12 x2  a13 x3  ...  a1n xn = b1
a21 x2  a13 x3  ...  a2n xn = b2
a13 x3  ... a2n xn = b2
... ...
...  ann xn = bn
}
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
– Resolução de Sistemas Triangulares
Seja Ax=b, onde A é uma matriz nxn triangular superior
{
a11 x1  a12 x2  a13 x3  ...  a1n xn = b1
a21 x2  a13 x3  ...  a2n xn = b2
a13 x3  ... a2n xn = b2
... ...
...  ann xn = bn
}
Da ultima equação temos:
xn =
bn
ann
xn−1 =
bn−1 −an−1, n xn
an−1, n−1
... x1 =
b1 −a1,2 x2 −a1,3 x3 ... −a1, n xn
a1,1
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
– Algorítimo Resolução de Sistemas Triangulares
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
– Algorítimo Resolução de Sistemas Triangulares
Para i = n ,n-1, ..., 1 obtêm-se x
n
, x
n-1
, ..., x
1
 por meio de:
x i =
bn − ∑
k=i−1
n
ai , k xk
ai , i
, i=n ,n−1,... ,1
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
– Algorítimo Resolução de Sistemas Triangulares
Para i = n ,n-1, ..., 1 obtêm-se x
n
, x
n-1
, ..., x
1
 por meio de:
x i =
bn − ∑
k=i−1
n
ai , k xk
ai , i
, i=n ,n−1,... ,1
x(n)=b(n)/a(n,n);
for i=(n-1):1;
s=0;
for j=(i+1):n;
s=s+a(i,j)*x(j);
x(i)=(b(i)-s)/a(i,i);
end
end
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
– Método da eliminação de Gauss → Modifica o Sistema Linear através do 
seguinte teorema:
Teo: Seja Ax = b um sistema linear. Aplicando sobre as equações deste
 sistema uma sequência de operações elementares escolhidas entre:
i) trocar duas equações;
ii) multiplicar uma equação por uma cte não nula;
iii) adicionar um múltiplo de uma eq. a uma outra;
Obtemos um novo sistema A'x=b' e os sistemas Ax=b e A'x=b' são equivalentes
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
– Método da eliminação de Gauss → Modifica o Sistema Linear através do 
seguinte teorema:
Teo: Seja Ax = b um sistema linear. Aplicando sobre as equações deste
 sistema uma sequência de operações elementares escolhidas entre:
i) trocar duas equações;
ii) multiplicar uma equação por uma cte não nula;
iii) adicionar um múltiplo de uma eq. a uma outra;
Obtemos um novo sistema A'x=b' e os sistemas Ax=b e A'x=b' são equivalentes
●Desta forma o método da Eliminação de Gauss utiliza este teorema para triangularizar a 
matriz A .
●A eliminação é efetuada por colunas e chamaremos a etapa k do processo a fase em que 
eliminamos a variável x
k
 das eq. K+1, k+2, ..., n.
●Usaremos a notação a
ij
(k) para denotar o coeficiente da linha i e coluna j ao final da k-
ésima etapa, bem como b
i
(k) será o i-ésimo elemento do vetor constante no final da etapa k.
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
– Método da eliminação de Gauss → Descrição:
●Considerando que det(A)≠0, é sempre possível reescrever o sistema linear de forma
Que o elemento da posição a
11
 seja diferente de zero, usando apenas a operação
Elementar (i);
{
a11
0 a12
0 ... a1j
0 ... a1n b1
0
a21
0 a22
0 ... a2j
0 ... a2n b2
0
a31
0 a32
0 ... a3j
0 ... a3n b3
0
... ...
an1
0 an2
0 ... anj
0 ... ann bn
0}seja A0 /b0= A/b =
onde aij
0= aij , bi
0= bi e a11
0≠ 0
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
Etapa 1:
●Eliminação da variável x
1
 das equações i=2, ..., n:
Subtraímos a 1ª equação multiplicada por m
i1
, onde podemos observar que
para esta eliminação a única escolha possível é m
i1
= a
i1
(0)/a
11
(0) , i=2, ..., n
Os elementos m
i1 
são os multiplicadores e o elemento a
i1
(0) é o denominado pivô 
da 1 ª etapa
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
Etapa 1:
●Eliminação da variável x
1
 das equações i=2, ..., n:
Subtraímos a 1ª equação multiplicada por m
i1
, onde podemos observar que
para esta eliminação a única escolha possível é m
i1
= a
i1
(0)/a
11
(0) , i=2, ..., n
Os elementos m
i1 
são os multiplicadores e o elemento a
i1
(0) é o denominado pivô 
da 1 ª etapa
Ao final desta etapa temos:
A1 /b1= {
a11
1 a12
1 ... a1j
1 ... a1n
1 b1
1
0 a22
1 ... a2j
1 ... a2n
1 b2
1
0 a32
1 ... a3j
1 ... a3n
1 b3
1
... ...
0 an2
1 ... anj
1 ... ann
1 bn
1}
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
Etapa 2:
●Devemos agora ter pelo menos um elemento a
i2
(0)≠0, caso contrario det(A(1)) =0
O que implica que det(A)=0;
●No entanto como domamos det(A)≠0 por hipótese é então possível reescrever a
matriz A(1) sem alterar a posição da linha 1 de forma que o pivô, a
22
(1)≠0
●Os multiplicadores desta etapa serão m
i2
= a
i2
(1)/a
22
(2) , i=3, ..., n
●X
2
 é eliminada das eq. i=3,...,n quando subtraímos a eq. i da segunda eq.
Multiplicada por m
i2
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
Etapa 2:
●Devemos agora ter pelo menos um elemento a
i2
(0)≠0, caso contrario det(A(1)) =0
O que implica que det(A)=0;
●No entanto como domamos det(A)≠0 por hipótese é então possível reescrever a
matriz A(1) sem alterar a posição da linha 1 de forma que o pivô, a
22
(1)≠0
●Os multiplicadores desta etapa serão m
i2
= a
i2
(1)/a
22
(2) , i=3, ..., n
●X
2
 é eliminada das eq. i=3,...,n quando subtraímos a eq. i da segunda eq.
Multiplicada por m
i2
Ao final desta etapa temos:
A1 /b1= {
a11
2 a12
2 ... a1j
2 ... a1n
2 b1
2
0 a22
2 ... a2j
2 ... a2n
2 b2
2
0 0 ... a3j
2 ... a3n
2 b3
2
... ...
0 0 ... anj
2 ... ann
2 bn
2}onde aij2= aij1 para i=1,2 j=i , ... , nbi2= bi1 para i=1,2aij2= aij1−mi2 .a2j1 i=3,... , n e j=2,... , n
bi
2= bi
1−mi1 .b2
0 i=3,... , n
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
Etapa 3 a (n-1):
●Seguindo este raciocínio procedemos até a etapa (n-1) onde a matriz ao
final desta etapa será:
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
Etapa 3 a (n-1):
●Seguindo este raciocínio procedemos até a etapa (n-1) onde a matriz ao
final desta etapa será:
A1 /b1= {
a11
2 a12
n−1 ... a1j
n−1 ... a1n
n−1 b1
n−1
0 a22
n−1 ... a2j
n−1 ... a2n
n−1 b2
n−1
0 0 ... a3j
n−1 ... a3n
n−1 b3
n−1
... ...
0 0 ... 0 ... ann
n−1 bn
n−1}
●Onde o Sistema linear A(n-1)x=b(n-1) triangular superior e equivalente ao
sistema linear original.
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
– Método da eliminação de Gauss → Código:
for k=1:(n-1);
for i=k+1:n
m=A(i,k)/A(k,k)
A(i,k)=0;
for j=(k+1):n;
A(i,j)=A(i,j) - m*a(k,j);
b(i)=b(i)-m*b(k);
end
end
end
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
– Algorítimo para solução de sistemas lineares por eliminação de Gauss:
for k=1:(n-1);
fori=k+1:n
m=A(i,k)/A(k,k)
A(i,k)=0;
for j=(k+1):n;
A(i,j)=A(i,j) - m*a(k,j);
b(i)=b(i)-m*b(k);
end
end
end
} Eliminação
} Resolução
x(n)=b(n)/a(n,n);
for i=(n-1):1;
s=0;
for j=(i+1):n;
s=s+a(i,j)*x(j);
x(i)=(b(i)-s)/a(i,i);
end
end
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
– Algorítimo para solução de sistemas lineares por eliminação de Gauss:
●O algorítimo efetua a fase de eliminação em (4n3 + 3n2 -7n)/6 operações
 e resolve o sistema triangular superior em n2 operações
●Assim o total de operações para se resolver em um sistema linear pelo método
da eliminação de Gauss é (4n3 + 9n2 – 7n)/6
●Se um sistema tiver 50 equações, o mesmo tem de realizar 87025 operações
supondo que uma operação possa ser efetuada em uma determinada maquina 
em 10-12 s o tempo de processamento seria de 8,7x10-8 s.
●No algorítimo de eliminação de Gauss, é necessário que a
kk
(k)≠0, 
ou seja, os pivôs devem ser não nulo.
●Se ocorrer o caso de a
kk
(k) = 0 deve-se efetuar a troca da linha k por outra abaixo
dela de modo que o elemento que fará o papel de pivô seja não nulo.
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
– Algorítimo para solução de sistemas lineares por eliminação de Gauss:
●Implementar no Matlab um algorítimo para a solução de um sistema Linear 
através do método da eliminação de Gauss.
●Utilizando os comandos round e fix implemente uma função que realiza uma 
mudança de precisão no sistema para um número c de casas decimais.
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
– Algorítimo para solução de sistemas lineares por eliminação de Gauss:
●Implementar no Matlab um algorítimo para a solução de um sistema Linear 
através do método da eliminação de Gauss.
●Utilizando os comandos round e fix implemente uma função que realiza uma 
mudança de precisão no sistema para um número c de casas decimais.
 function numero = ardncd(x,n)
%Arredonda o numero x com n casas decimais.
 n=round(n);
 format long;
 numero = (round(x*(10^n)))/(10^n)
 format short;
 
 end
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
Considere os seguinte sistema de equações:
0,000100 x  y = 1
x  y = 2
x  y = 2
0,000100 x  y = 1
e
{0,000100 1 11 1 2}
{ 1 1 20,000100 1 1}
O resultado exato do sistema é x=1,00010 e y=0,99990. No entanto qual seria
os resultado utilizando método de eliminação de gauss para uma precisão de
 3 casas decimais?
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
Considere os seguinte sistema de equações:
0,000100 x  y = 1
x  y = 2
x  y = 2
0,000100 x  y = 1
e
{0,000100 1 11 1 2}
{ 1 1 20,000100 1 1}
x = 1 e y = 0
x = 1 e y = 1
Aceitável!
Absurdo!
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
– Pivoteamento
●Para assegurar a estabilidade numérica no método de eliminação de Gauss,
frequentemente é necessário linhas e/ou colunas não somente quando o pivô é nulo,
mas também quando ele é próximo de zero. 
●Vimos que o algorítimo para o método da Eliminação de Gauss requer o cálculo dos
multiplicadores em cada etapa do processo k:
mik =
aik
k−1
akk
k−1 , i = k1, ... , n
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
– Pivoteamento
●Para assegurar a estabilidade numérica no método de eliminação de Gauss,
frequentemente é necessário linhas e/ou colunas não somente quando o pivô é nulo,
mas também quando ele é próximo de zero. 
●Vimos que o algorítimo para o método da Eliminação de Gauss requer o cálculo dos
multiplicadores em cada etapa do processo k:
mik =
aik
k−1
akk
k−1 , i = k1, ... , n
●Como já observamos, além de ser impossível de se trabalhar com um pivô nulo, pivôs 
próximos de zero condizem a resultados totalmente imprecisos. Isto porque em qualquer
calculadora ou computador os cálculos são efetuados com precisão finita, e pivôs perto
de zero dão origem a multiplicadores bem maiores que a unidade que por sua vez
origina em uma ampliação dos erros de arredondamento.
●Para se contornar estes problemas deve-se adotar uma estrategia de pivoteamento,
ou seja, um processo de seleção dalinha e/ou coluna pivotal.
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
– Pivoteamento Parcial
●Esta estratégia consiste em:
i) No início de cada etapa k da fase de eliminação, escolher para pivô o elemento de
maior valor absoluto entre os coeficientes: a
ik
(k-1) , i=k, k+1, ..., n;
ii) Trocar as linha k e i se for necessário.
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
– Pivoteamento Completo ou Total
● Nesta estratégia,no início da etapa k é escolhido para pivô o elemento de maior módulo
entre todos os elementos que ainda atuam o processo de eliminação:
max ∣aijk−1∣=∣arsk−1∣ a rsk−1
para todo i , j≥k
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
– Pivoteamento Completo ou Total
● Nesta estratégia,no início da etapa k é escolhido para pivô o elemento de maior módulo
entre todos os elementos que ainda atuam o processo de eliminação:
max ∣aijk−1∣=∣arsk−1∣ a rsk−1
para todo i , j≥k
●Salvo raríssimas exceções a estratégia de pivoteamento total não é empregada pois
envolve a comparação extensa dos elementos a
ij
(k-1), i,j>k e troca de linhas e colunas.
Assim é evidente que este método acarreta um esforço computacional maior que a
estratégia do pivoteamento parcial. 
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28