Sistemas equivalentes e escalonamento

Como alterar um sistema linear, tornando-o mais simples

Vamos lá?

Já vimos que resolver sistemas triangulares é simples. Que bom seria se todo sistema linear fosse assim, não? Pois é, nesta aula veremos que até que é possível.

Matemáticos adoram converter um problema "novo" em um problema "velho" que já sabem como resolver. Como já sabemos resolver sistemas lineares com matrizes triangulares superiores, a estratégia para resolver um sistema qualquer é convertê-lo em outro sistema linear cuja matriz seja triangular e que preserve as soluções do sistema original. Sistemas lineares que tenham exatamente as mesmas soluções são ditos sistemas equivalentes. Feito isto, bastará aplicar o algoritmo visto anteriormente.

Por exemplo, os dois sistemas abaixo são equivalentes, dado que toda solução do primeiro é solução também do segundo e vice-versa. $$ \left\{ \begin{array}{rcrcr} x & - & y & = & 0 \\ x & + & y & = & 2 \end{array} \right. \qquad\qquad \left\{ \begin{array}{rcrcr} x & + & y & = & 2 \\ 2x & + & y & = & 3 \end{array} \right. $$ Observe agora esses outros dois sistemas lineares. $$ \left\{ \begin{array}{rcrcr} x & - & y & = & 0 \\ x & + & y & = & 2 \end{array} \right. \qquad\qquad \left\{ \begin{array}{rcrcr} x & + & y & = & 2 \\ 2x & + & 2y & = & 4 \end{array} \right. $$ A solução do sistema da esquerda é $x=y=1,$ que também é solução do sistema da direita. Porém $x=2$ e $y=0$ é outra solução para o sistema da direita, que não é solução para o sistema da esquerda, quebrando assim a equivalência entre eles.

A chave para esse processo de transformar um sistema linear em outro sistema equivalente são as operações elementares. Operações elementares são operações que podem ser realizadas com as equações de um sistema linear sem alterar seu conjunto solução. Ou seja, apesar de alterar as equações do sistema linear, o sistema modificado continua tendo as mesmas soluções do sistema original, e nenhuma outra.

A primeira operação elementar é multiplicar uma das equações do sistema linear por uma constante não nula. Claramente, a igualdade é preservada.

Trocar a ordem das equações de um sistema linear também não altera suas soluções.

Por fim, somar ou subtrair uma equação de outra também não alterar as soluções do sistemas, visto que ao fazer isso, na verdade, está se somando/subtraindo uma constante nos dois lados de uma equação.

O processo de escalonamento, também conhecido como processo de eliminação de Gauss, consiste em utilizar as operações elementares para converter o sistema linear original e outro sistema equivalente, mas com matriz de coeficientes triangular superior. As operações elementares são aplicadas de maneira que se produzam zeros abaixo da diagonal da matriz de coeficientes. Além disso, a ordem com que essas operações são realizadas também é bem determinada, de modo que depois seja possível traduzir o processo todo em um algoritmo bem definido.

No escalonamento, trabalha-se por colunas, da primeira até a penúltima, e em cada coluna, trabalha-se em ordem crescente nas linhas abaixo da diagonal, denominado pivô. Como as operações elementares aplicam-se a equações do sistema linear, toda manipulação feita nos coeficientes da matriz deve igualmente ser feita nos coeficientes do vetor independente. Por isso, é conveniente operar com a matriz estendida (ou aumentada) do sistema, que nada mais é que a matriz de coeficientes do sistema linear acrescida de uma coluna para abrigar o vetor independente.

No vídeo trabalhamos com o seguinte sistema linear (já representado por sua matriz aumentada). $$ \left[ \begin{array}{cccccr} 2&3&1&1&\vdots&3\\ 4&7&4&3&\vdots&6\\ 4&7&6&4&\vdots&4\\ 6&9&9&8&\vdots&3 \end{array} \right] $$

Esquematicamente, a $i$-ésima linha da matriz é representada por $\ell_i.$ Para zerar os elementos da primeira coluna, abaixo do elemento na diagonal, utilizando a terceira operação elementar descrita anteriormente. Por exemplo, para introduzir um zero na posição $(2, 1)$ da matriz, somamos à linha 2, um múltiplo apropriado da linha 1. Com efeito, $\ell_2 \leftarrow −2\ell_1 + \ell_2.$ O mesmo é feito com as linhas 3 e 4, através das operações $\ell_3 \leftarrow −2\ell_1 + \ell_3$ e $\ell_4 \leftarrow −3\ell_1 + \ell_4.$ Após essas três operações, ficamos com a nova matriz aumentada abaixo. $$ \left[ \begin{array}{cccccr} 2&3&1&1&\vdots& 3\\ 0&1&2&1&\vdots& 0\\ 0&1&4&2&\vdots&-2\\ 0&0&6&5&\vdots&-6 \end{array} \right]. $$

Para introduzir “zeros” nas posições $(3, 2)$ e $(4, 2)$ vamos utilizar múltiplos da linhas 2 e o novo pivô é o elemento na posição $(2,2).$ Veja que se continuássemos utilizando múltiplos da linha 1, “estragarı́amos” os zeros já introduzidos na primeira coluna. Por uma eventualidade, alguns diriam até mesmo sorte, o elemento $(4, 2)$ já é zero. Assim, a única operação necessária é $\ell_3 \leftarrow −\ell_2 + \ell_3.$ Assim, a matriz atualizada é $$ \left[ \begin{array}{cccccr} 2&3&1&1&\vdots& 3\\ 0&1&2&1&\vdots& 0\\ 0&0&2&1&\vdots&-2\\ 0&0&6&5&\vdots&-6 \end{array} \right]. $$

Agora o pivô é o elemento em na posição $(3,3).$ Resta apenas zerar o coeficiente $(4, 3),$ o que é feito com a operação $\ell_4 \leftarrow −3\ell_3 + \ell_4.$ Obtendo finalmente a matriz $$ \left[ \begin{array}{cccccr} 2&3&1&1&\vdots& 3\\ 0&1&2&1&\vdots& 0\\ 0&0&2&1&\vdots&-2\\ 0&0&0&2&\vdots& 0 \end{array} \right]. $$

Concluído o escalonamento da matriz (que agora está na forma escada), basta resolver um sistema triangular superior, para o qual já vimos algoritmo antes.

Operações elementares no Octave

No Octave podemos facilmente representar uma linha de uma matriz e, inclusive operar com ela. Isso facilita bastante realizar as operações elementares que discutimos e usamos nessa aula.

Vejamos como o exemplo dessa aula teria sido refeito usando o Octave.

# Matriz A e vetor independente b
A = A = [2 3 1 1; 4 7 4 3; 4 7 6 4; 6 9 9 8];
b = [3; 6; 4; 3];

# Matriz estendida
C = [A b]         # Adicionamos a coluna b à matriz A e a guardamos em C
C =

   2   3   1   1   3
   4   7   4   3   6
   4   7   6   4   4
   6   9   9   8   3

A notação A(i,j) representa no Octave o elemento da linha $i$ e coluna $j$ da matriz $A$. Podemos também usar intervalos, tanto para linhas como colunas (veja a segunda aula sobre Octave). Por exemplo:

A(1,2:4)   # vetor da 1ª linha de A, entre as 2ª e 4ª colunas
ans =

   3   1   1

A(1:4,2)   # toda a segunda coluna de A
ans =

   3
   7
   7
   9

A(:,2)     # forma alternativa de representar o intervalo completo das linhas
ans =

   3
   7
   7
   9

Usando essa notação, a primeira operação que realizamos na matriz estendida durante o processo de escalonamento, $\ell_2 \leftarrow −2\ell_1 + \ell_2,$ fica implementada como

C(2,:) = -2 * C(1,:) + C(2,:)
C =

   2   3   1   1   3
   0   1   2   1   0
   4   7   6   4   4
   6   9   9   8   3

Para seguir com o processo de escalonamento, faríamos:

C(3,:) = -2 * C(1,:) + C(3,:);
C(4,:) = -3 * C(1,:) + C(4,:);

# Escalonamento da segunda coluna
C(3,:) = -1 * C(2,:) + C(3,:);

# Escalonamento da terceira coluna
C(4,:) = -3 * C(3,:) + C(4,:)
C =

   2   3   1   1   3
   0   1   2   1   0
   0   0   2   1  -2
   0   0   0   2   0

A resolução do sistema triangular superior seria concluída com:

U = C(:,1:4)       # Matriz triangular superior
U =

   2   3   1   1
   0   1   2   1
   0   0   2   1
   0   0   0   2

y = C(:,5)         # Vetor independente
y =

   3
   0
  -2
   0

x = U\y            # Solução do sistema Ux=y
x =

  -1
   2
  -1
   0

Essa facilidade para operar com linhas e colunas de matrizes faz do Octave um ambiente bem confortável para a escrita de algoritmos de álgebra linear computacional.

1. Utilizando operações elementares, escalone o sistema abaixo e resolva-o. $$ \left[ \begin{array}{rrrr} 3 & -2& 1 & 1\\ -3 & 2& -2 & 0\\ -18 & 13& -5 & -2\\ -33 & 24& -8 & 4 \end{array} \right] x = \left[ \begin{array}{r} -10\\\ 3\\\ 56\\\ 85 \end{array} \right] $$

O sistema escalonado fica $$ \left[ \begin{array}{rrrr} 3& -2& 1& 1\\ 0& 1& 1& 4\\ 0& 0& -1& 1\\ 0& 0& 0& 8 \end{array}\right]x = \left[ \begin{array}{r} -10\\\ -4\\\ -7\\\ -24\end{array}\right],$$ cuja solução é $x = (-1,4,4-3)^T.$

2. Utilizando o processo de eliminação de Gauss, encontre a solução dos sistemas lineares $$ \left[ \begin{array}{rrrr} 2 & 1 & 1 & 3 \\ -2 & -2 & 1 & 1 \\ 6 & 5 & 2 & 2 \\ -4 & -3 & 6 & 5 \end{array}\right] x = \left[ \begin{array}{r} -2 \\\ -3 \\\ 5 \\\ -9 \end{array} \right] \quad \mbox{e} \quad \left[ \begin{array}{rrrr} 2 & 1 & 1 & 3 \\ -2 & -2 & 1 & 1 \\ 6 & 5 & 2 & 2 \\ -4 & -3 & 6 & 5 \end{array}\right] x = \left[ \begin{array}{r} 0 \\\ -4 \\\ 0 \\\ -15 \end{array} \right]. $$ O que você observou de peculiar na resolução desses dois sistemas?

A solução do primeiro sistema é $x = (2,-1,1,-2)^T$ e a solução do segundo sistema é $x = (-1, 2,-3,1)^T.$