Use o botão abaixo para reportar erros ou dar sugestões.

Cálculo Numérico - Versão GNU Octave

4.1 Eliminação gaussiana


A eliminação gaussiana, também conhecida como escalonamento, é um método para resolver sistemas lineares. Este método consiste em manipular o sistema através de determinadas operações elementares, transformando a matriz estendida do sistema em uma matriz trapezoidal (chamada de matriz escalonada do sistema). Uma vez triangularizado o sistema, a solução pode ser obtida via substituição regressiva. Naturalmente estas operações elementares devem preservar a solução do sistema e consistem em:

1.
multiplicação de um linha por uma constante não nula.
2.
substituição de uma linha por ela mesma somada a um múltiplo de outra linha.
3.
permutação de duas linhas.

Exemplo 4.1.1. Resolva o sistema

x + y + z = 1 4x + 4y + 2z = 2 2x + y - z = 0 (4.8)

pelo método de eliminação gaussiana.

Solução. A matriz estendida do sistema é escrita como

1 1 1 1 4 4 2 2 2 1 -1 0 (4.9)

No primeiro passo, subtraímos da segunda linha o quádruplo da primeira e subtraímos da terceira linha o dobro da primeira linha:

1 1 1 1 0 0 -2 -2 0 -1 -3 -2 (4.10)

No segundo passo, permutamos a segunda linha com a terceira:

1 1 1 1 0 -1 -3 -2 0 0 -2 -2 (4.11)

Neste momento, a matriz já se encontra na forma triangular (chamada de matriz escalonada do sistema). Da terceira linha, encontramos - 2z = -2, ou seja, z = 1. Substituindo na segunda equação, temos - y - 3z = -2, ou seja, y = -1 e finalmente, da primeira linha, x + y + z = 1, resultando em x = 1.

No GNU Octave, podemos fazer as computações acima da seguinte forma:

>> #matriz dos coeficientes  
>> A = [1 1 1;4 4 2;2 1 -1];  
>> #vetor dos termos constantes  
>> b = [1 2 0]’;  
>> #matriz estendida  
>> E = [A b]  
E =  
   1   1   1   1  
   4   4   2   2  
   2   1  -1   0  
 
>> #L2 <- L2 - (e21/e11)*L1  
>> E(2,:) = E(2,:) - E(2,1)/E(1,1) * E(1,:)  
E =  
   1   1   1   1  
   0   0  -2  -2  
   2   1  -1   0  
 
>> #L3 <- L3 - (e31/e11)*L1  
>> E(3,:) = E(3,:) - E(3,1)/E(1,1) * E(1,:)  
E =  
   1   1   1   1  
   0   0  -2  -2  
   0  -1  -3  -2  
 
>> #L2 <-> L3  
>> aux = E(2,:); E(2,:) = E(3,:); E(3,:) = aux  
E =  
   1   1   1   1  
   0  -1  -3  -2  
   0   0  -2  -2  
>> #resolvendo  
>> z = E(3,4)/E(3,3)  
z =  1  
>> y = (E(2,4) - E(2,3)*z)/E(2,2)  
y = -1  
>> x = (E(1,4) - E(1,3)*z - E(1,2)*y)/E(1,1)  
x =  1

Neste Exemplo 4.1.1, o procedimento de eliminação gaussiana foi usado para obtermos um sistema triangular (superior) equivalente ao sistema original. Este, por sua vez, nos permitiu calcular a solução do sistema, isolando cada variável, começando da última linha (última equação), seguindo linha por linha até a primeira.

Alternativamente, podemos continuar o procedimento de eliminação gaussiana, anulando os elementos da matriz estendida acima da diagonal principal. Isto nos leva a uma matriz estendida diagonal (chamada matriz escalonada reduzida), na qual a solução do sistema original aparece na última coluna.

Exemplo 4.1.2. No Exemplo 4.1.1, usamos o procedimento de eliminação gaussiana e obtivemos

1 1 1 1 4 4 2 2 2 1 -1 0 matriz estendida ~ 1 1 1 1 0 -1 -3 -2 0 0 -2 -2 matriz escalonada. (4.12)

Agora, seguindo com o procedimento de eliminação gaussiana, buscaremos anular os elementos acima da diagonal principal. Começamos dividindo cada elemento da última linha pelo valor do elemento da sua diagonal, obtemos

1 1 1 1 0 -1 -3 -2 0 0 1 1 (4.13)

Então, somando da segunda linha o triplo da terceira e subtraindo da primeira a terceira linha, obtemos

1 1 0 0 0 -1 0 1 0 0 1 1 (4.14)

Fixamos, agora, na segunda linha. Dividimos esta linha pelo valor do elemento em sua diagonal, isto nos fornece

1 1 0 0 0 1 0 -1 0 0 1 1 (4.15)

Por fim, subtraímos da primeira linha a segunda, obtendo a matriz escalonada reduzida

1 0 0 1 0 1 0 -1 0 0 1 1 (4.16)

Desta matriz escalonada reduzida temos, imediatamente, x = 1, y = -1 e z = 1, como no Exemplo 4.1.1.

No GNU Octave, podemos fazer as computações acima da seguinte forma:

>> #matriz escalonada  
>> E = [1 1 1 1;0 -1 -3 -2;0 0 -2 -2]  
E =  
 
   1   1   1   1  
   0  -1  -3  -2  
   0   0  -2  -2  
 
>> #L3 <- (1/e33)*L3  
>> E(3,:) = 1/E(3,3)*E(3,:)  
E =  
 
   1   1   1   1  
   0  -1  -3  -2  
  -0  -0   1   1  
 
>> #L2 <- L2 - (e23/e33)*L3  
>> E(2,:) = E(2,:) - E(2,3)/E(3,3)*E(3,:)  
E =  
 
   1   1   1   1  
   0  -1   0   1  
  -0  -0   1   1  
 
>> #L1 <- L1 - (e13/e33)*L3  
>> E(1,:) = E(1,:) - E(1,3)/E(3,3)*E(3,:)  
E =  
 
   1   1   0   0  
   0  -1   0   1  
  -0  -0   1   1  
 
>> #L2 <- (1/e22)*L2  
>> E(2,:) = 1/E(2,2)*E(2,:)  
E =  
 
   1   1   0   0  
  -0   1  -0  -1  
  -0  -0   1   1  
 
>> #L1 <- L1 - (e12/e22)L1  
>> E(1,:) = E(1,:) - E(1,2)/E(2,2)*E(2,:)  
E =  
 
   1   0   0   1  
  -0   1  -0  -1  
  -0  -0   1   1

Observação 4.1.1. O GNU Octave oferece a função rref (do inglês row reduced echelon form), a qual obtem a matriz escalonada reduzida de uma matriz estendida dada. No caso do Exemplo 4.1.1, temos:

>> E = [1 1 1 1;4 4 2 2;2 1 -1 0]  
E =  
 
   1   1   1   1  
   4   4   2   2  
   2   1  -1   0  
 
>> rref(E)  
ans =  
 
   1   0   0   1  
   0   1   0  -1  
   0   0   1   1

4.1.1 Eliminação gaussiana com pivotamento parcial


A eliminação gaussiana com pivotamento parcial consiste em fazer uma permutação de linhas de forma a escolher o maior pivô (em módulo) a cada passo.

Exemplo 4.1.3. Resolva o sistema

x + y + z = 1 2x + y - z = 0 2x + 2y + z = 1 (4.17)

por eliminação gaussiana com pivotamento parcial.

Solução. A matriz estendida do sistema é

1 1 1 1 2 1 -1 0 2 2 1 1 ~ 2 1 -1 0 1 1 1 1 2 2 1 1 ~ 2 1 -1 0 0 12 32 1 0 1 2 1 ~ 2 1 -1 0 0 1 2 1 0 12 32 1 ~ 2 1 -1 0 0 1 2 1 0 0 12 12 (4.18)

Encontramos 12z = 12, ou seja, z = 1. Substituímos na segunda equação e temos y + 2z = 1, ou seja, y = -1 e, finalmente 2x + y - z = 0, resultando em x = 1.

No GNU Octave, podemos fazer estas computações da seguinte forma:

E = [1 1  1 1;  
     2 1 -1 0;  
     2 2  1 1]  
 
#L2 <-> L1  
aux = E(2,:);  
E(2,:) = E(1,:);  
E(1,:) = aux  
 
#zera E(2:3,1)  
E(2:3,:) = E(2:3,:) - (E(2:3,1)/E(1,1))*E(1,:)  
 
#zera E(3,2)  
E(3,:) = E(3,:) - (E(3,2)/E(2,2))*E(2,:)  
 
#subs regressiva  
x = zeros(3,1);  
x(3) = E(3,4)/E(3,3);  
x(2) = (E(2,4) - E(2,3)*x(3))/E(2,2);  
x(1) = (E(1,4) - E(1,3)*x(3) - E(1,2)*x(2))/E(1,1)

A técnica de eliminação gaussiana com pivotamento parcial ajuda a evitar a propagação dos erros de arredondamento. Vejamos o próximo exemplo.

Exemplo 4.1.4 (Problema com elementos com grande diferença de escala). Resolva o seguinte sistema usando eliminação gaussiana sem e com pivotamento parcial. Discuta, em cada caso, o resultado frente à aritmética de ponto flutuante quando 0 < |ϵ|« 1.

ε 2 1 ε x y = 4 3 (4.19)

Solução. Vamos, primeiramente, executar a eliminação gaussiana sem pivotamento parcial para ε0 e |ε|« 1:

ε 2 4 1 ε 3 ~ ε 2 4 0 ε - 2 ε 3 - 4 ε (4.20)

Temos

y = 3 - 4ε ε - 2ε (4.21)

e

x = 4 - 2y ε (4.22)

Observe que a expressão obtida para y se aproximada de 2 quando ε é pequeno:

y = 3 - 4ε ε - 2ε = 3ε - 4 ε2 - 2 - 4 - 2 = 2,quandoε 0. (4.23)

Já expressão obtida para x depende justamente da diferença 2 - y:

x = 4 - 2y ε = 2 ε(2 - y) (4.24)

Assim, quando ε é pequeno, a primeira expressão, implementada em um sistema de ponto flutuante de acurácia finita, produz y = 2 e, consequentemente, a expressão para x produz x = 0. Isto é, estamos diante um problema de cancelamento catastrófico.

Agora, quando usamos a eliminação gaussiana com pivotamento parcial, fazemos uma permutação de linhas de forma a escolher o maior pivô a cada passo:

ε 2 4 1 ε 3 ~ 1 ε 3 ε 2 4 ~ 1 ε 3 0 2 - ε2 4 - 3ε (4.25)

Continuando o procedimento, temos:

y = 4 - 4ε 2 - ε2 (4.26)

e

x = 3 - εy (4.27)

Observe que tais expressões são analiticamente idênticas às anteriores, no entanto, são mais estáveis numericamente. Quando ε converge a zero, y converge a 2, como no caso anterior. No entanto, mesmo que y = 2, a segunda expressão produz x = 3 - εy, isto é, a aproximação x 3 não depende mais de obter 2 - y com precisão.

Exercícios resolvidos


ER 4.1.1. Resolva o seguinte sistema por eliminação gaussiana com pivotamento parcial.

2y + 2z = 8 x + 2y + z = 9 x + y + z = 6 (4.28)

Solução. A forma matricial do sistema dado é
0 2 2 1 2 1 1 1 1 x y z = 8 9 6 (4.29)

Construímos, então, a matriz completa e seguimos com o procedimento de eliminação gaussiana com pivotamento parcial: 0 2 2 8 1 2 1 9 1 1 1 6 ~ 1 2 1 9 0 2 2 8 1 1 1 6 ~ 1 2 1 9 0 2 2 8 0 - 1 0 - 3 (4.30) ~ 1 2 1 9 0 2 2 8 0 0 1 1 ~ 1 2 0 8 0 2 0 6 0 0 1 1 (4.31) ~ 1 0 0 2 0 2 0 6 0 0 1 1 (4.32)

Portanto x = 2, y = 3 e z = 1.

No GNU Octave, podemos fazer estas computações da seguinte forma:

>> #matriz estendida  
>> E = [0 2 2 8;1 2 1 9;1 1 1 6]  
E =  
 
   0   2   2   8  
   1   2   1   9  
   1   1   1   6  
 
>> #L1 <-> L2  
>> aux = E(1,:); E(1,:) = E(2,:); E(2,:) = aux  
E =  
 
   1   2   1   9  
   0   2   2   8  
   1   1   1   6  
 
>> #L3 <- L3 - (e31/e11)*L1  
>> E(3,:) = E(3,:) - E(3,1)/E(1,1)*E(1,:)  
E =  
 
   1   2   1   9  
   0   2   2   8  
   0  -1   0  -3  
 
>> #L3 <- L3 - (e32/e22)*L2  
>> E(3,:) = E(3,:) - E(3,2)/E(2,2)*E(2,:)  
E =  
 
   1   2   1   9  
   0   2   2   8  
   0   0   1   1  
 
>> #L2 <- L2 - (e23/e33)*L3  
>> E(2,:) = E(2,:) - E(2,3)/E(3,3)*E(3,:)  
E =  
 
   1   2   1   9  
   0   2   0   6  
   0   0   1   1  
 
>> #L1 <- L1 - (e13/e33)*L3  
>> E(1,:) = E(1,:) - E(1,3)/E(3,3)*E(3,:)  
E =  
 
   1   2   0   8  
   0   2   0   6  
   0   0   1   1  
 
>> #L1 <- L1 - (e12/e22)*L2  
>> E(1,:) = E(1,:) - E(1,2)/E(2,2)*E(2,:)  
E =  
 
   1   0   0   2  
   0   2   0   6  
   0   0   1   1  
 
>> #obtendo a solucão  
>> z = E(3,4)/E(3,3)  
z =  1  
>> y = E(2,4)/E(2,2)  
y =  3  
>> x = E(1,4)/E(1,1)  
x =  2

Exercícios


E 4.1.1. Resolva o seguinte sistema de equações lineares

x + y + z = 0 x + 10z = -48 10y + z = 25 (4.33)

Usando eliminação gaussiana com pivotamento parcial (não use o computador para resolver essa questão).

Resposta. Escrevemos o sistema na forma matricial e resolvemos: 1 1 1 0 1 0 10 - 48 0 10 1 25 ~ 1 1 1 0 0 - 1 9 - 48 0 10 1 25 ~ 1 1 1 0 0 10 1 25 0 - 1 9 - 48 ~ (4.34) ~ 1 1 1 0 0 10 1 25 0 0 9.1 - 45.5 ~ 1 1 1 0 0 10 1 25 0 0 1 - 5 ~ (4.35) ~ 1 1 0 5 0 10 0 30 0 0 1 - 5 ~ 1 1 0 5 0 1 0 3 0 0 1 - 5 ~ (4.36) ~ 1 0 0 2 0 1 0 3 0 0 1 - 5 (4.37)

Portanto x = 2, y = 3, z = -5

E 4.1.2. Resolva o seguinte sistema de equações lineares x + y + z = 0 (4.38) x + 10z = -48 (4.39) 10y + z = 25 (4.40)

Usando eliminação gaussiana com pivotamento parcial (não use o computador para resolver essa questão).

E 4.1.3. Calcule a inversa da matriz

A = 1 2 -1 -1 2 0 2 1 -1 (4.41)

usando eliminação gaussiana com pivotamento parcial.

E 4.1.4. Demonstre que se adbc, então a matriz A dada por:

A = a b c d (4.42)

é inversível e sua inversa é dada por:

A-1 = 1 ad - bc d -b -c a . (4.43)

Creative Commons License Este texto é disponibilizado nos termos da licença Creative Commons Atribuição-CompartilhaIgual 3.0 Não Adaptada (CC-BY-SA 3.0). Página gerada em 9/1/2020 às 15:16:14.

Informe erros ou edite você mesmo!