Eliminação de Gauss

Escolha qual linha servirá de pivô em cada coluna e observe a eliminação. No segundo exemplo, a escolha define a resposta: use o número minúsculo como pivô e x dará 0 em vez de 1.

As três operações elementares sobre linhas	$\begin{gathered}R_i\leftrightarrow R_j,\qquad R_i\to kR_i\ (k\neq0)\\R_i\to R_i+kR_j\end{gathered}$
Há uma única solução quando	$\operatorname{rank}A=\operatorname{rank}[A\,\|\,b]=n$

Exemplo resolvido — Eliminação de Gauss

Determinante	−1
Resíduo	8,8818 × 10⁻¹⁶

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Lição

A teoria — Eliminação de Gauss269 palavras

A eliminação transforma um sistema noutro equivalente triangular, que pode depois ser solucionado de baixo para cima. O seu valor não está em funcionar. Vários métodos funcionam. Está naquilo que custa, porque é esse custo que determina o método que a máquina vai realmente executar.

O que significa cada símbolo

n: o número de incógnitas, e a única coisa de que o custo depende.
pivot: o coeficiente pelo qual uma linha é dividida. A ordem fixada pelo algoritmo é o que torna o processo livre de decisões. O número que calha nesse lugar é o que assegura a sua sobrevivência em vírgula flutuante.

Pressupõe: Um sistema denso e sem qualquer estrutura explorável. Sistemas esparsos, em banda ou simétricos ficam mais baratos. Saber escolher o método especializado adequado resume grande parte da álgebra linear numérica.
Falha quando: O custo é cúbico. Cúbico é uma barreira. A eliminação sobre n incógnitas requer cerca de n³/3 multiplicações e igual número de adições. Contando diretamente numa eliminação real, temos 333.300 multiplicações com n = 100 face às 333.333 da estimativa. Aquilo que o expoente nos cobra é uma penalização fixa de crescimento: duplicar as incógnitas multiplica o trabalho por exatamente 8. Desse modo, 100 incógnitas requerem 333.300 multiplicações e 200 requerem 2.666.600. Uma máquina que despache mil incógnitas num segundo precisa de oito segundos para duas mil. Levará cerca de duas horas e um quarto para vinte mil. Esse é o formato da barreira. É a razão pela qual a pergunta interessante da álgebra linear numérica quase nunca passa por como resolver um sistema denso, mas sim como evitar sequer tê-lo.

Problemas resolvidos na íntegra

Resolver 2x + y − z = 8 e o custo em precisão 7 passos
Resolva 2x + y − z = 8, −3x − y + 2z = −11, −2x + y + 2z = −3 — e depois avalie o que a eliminação lhe custou em exatidão.

Abrir este problema na ferramenta
1. Escreva como uma matriz aumentada. As letras não fazem nenhum trabalho, por isso descarte-as e mantenha as colunas.
  
  $\begin{bmatrix} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{bmatrix}$
2. Faça o pivotamento pela maior entrada da primeira coluna, que é −3 na linha dois, e desloque-a para cima. Cada troca de linha inverte o sinal do determinante, portanto acompanhe a conta.
  
  $R_1 \leftrightarrow R_2 \quad (|-3| > |2|)$
3. Zere o restante da primeira coluna subtraindo múltiplos da linha do pivô.
  
  $R_2 \to R_2 - \tfrac{2}{-3}R_1, \qquad R_3 \to R_3 - \tfrac{-2}{-3}R_1$
4. Repita o procedimento na segunda coluna. A seguir, leia a última linha: ela contém uma incógnita e o seu valor.
  
  $R_2 \leftrightarrow R_3 \quad (\tfrac{5}{3} > \tfrac{1}{3}) \;\Rightarrow\; \tfrac{1}{5}z = -\tfrac{1}{5}$
5. Faça a substituição regressiva de baixo para cima. A última linha fornece z, a linha do meio dá y e a do topo revela x.
  
  $z = -1, \qquad y = 3, \qquad x = 2$
6. Multiplique os pivôs e aplique o sinal correspondente a duas trocas para obter o determinante. Verifique o resultado substituindo-o nas equações originais em vez das reduzidas.
  
  $\det = (-3)\left(\tfrac{5}{3}\right)\left(\tfrac{1}{5}\right)(-1)^2 = -1$
7. O resíduo aproxima-se de 10⁻¹⁶, o que não é zero. Trata-se do tamanho do arredondamento que um computador não consegue evitar, e é a medida honesta a relatar. Uma resposta anunciada como exata ou provém de aritmética inteira ou não está a prestar atenção. Altere o coeficiente principal para 10⁻¹⁷ com o pivotamento desligado e o mesmo resíduo passará a 1, o que equivale ao mesmo aviso a soar aos gritos.
  
  $\max_i |A_i x - b_i| \approx 9 \times 10^{-16}$
Resposta

x = 2, y = 3, z = −1, determinante −1. O resíduo perto de 10⁻¹⁶ significa que a aritmética foi tão exata quanto o ponto flutuante permite. Desligue o pivotamento num sistema mal escalonado e esse será o número a avisar que a resposta está errada.
Um determinante de 0, duas vezes, com dois significados diferentes 7 passos
Esta predefinição não tem solução e a seguinte tem uma infinidade delas, e ambas apresentam um determinante de 0. Determine o que realmente as separa e decida o que mudar o segundo membro alguma vez lhe poderia comprar.

Abrir este problema na ferramenta
Mostrar solução
1. A pivotagem parcial percorre a primeira coluna à procura do maior coeficiente. Encontra o 3 na última linha, pelo que o primeiro movimento é uma troca.
  
  $\begin{bmatrix} 1 & 1 & 1 & 3 \\ 2 & 2 & 2 & 7 \\ 3 & 1 & 2 & 5 \end{bmatrix} \xrightarrow{\;R_1 \leftrightarrow R_3\;} \begin{bmatrix} 3 & 1 & 2 & 5 \\ 2 & 2 & 2 & 7 \\ 1 & 1 & 1 & 3 \end{bmatrix} \qquad (|3| > |2| > |1|)$
2. Anule a coluna: subtraia ⅔ da nova primeira linha à segunda e ⅓ dela à terceira.
  
  $R_2 \to R_2 - \tfrac{2}{3}R_1, \quad R_3 \to R_3 - \tfrac{1}{3}R_1: \qquad \begin{bmatrix} 3 & 1 & 2 & 5 \\ 0 & \tfrac{4}{3} & \tfrac{2}{3} & \tfrac{11}{3} \\ 0 & \tfrac{2}{3} & \tfrac{1}{3} & \tfrac{4}{3} \end{bmatrix}$
3. Na segunda coluna, 4/3 já está acima de 2/3, portanto nada precisa de ser trocado. Subtraia metade da linha 2 à linha 3.
  
  $R_3 \to R_3 - \tfrac{1}{2}R_2: \qquad \begin{bmatrix} 3 & 1 & 2 & 5 \\ 0 & \tfrac{4}{3} & \tfrac{2}{3} & \tfrac{11}{3} \\ 0 & 0 & 0 & -\tfrac{1}{2} \end{bmatrix}$
4. A linha 3 fica agora vazia à esquerda e com −½ à direita, o que se lê 0 = −½. Foram colocados apenas dois pivôs, 3 e 4/3, onde três incógnitas exigem três, e um pivô em falta anula o produto.
  
  $\text{pivots } 3,\ \tfrac{4}{3} \ \text{— two, not three} \;\Longrightarrow\; \det A = 0, \qquad \text{last row: } 0 = -\tfrac{1}{2}$
5. O que o determinante esconde é a característica. A matriz dos coeficientes tem duas linhas independentes. A matriz ampliada tem três, porque aquele −½ que sobra é uma linha que nada consegue anular. Característica 2 contra característica 3 é o que significa «sem solução».
  
  $\operatorname{rank} A = 2 \;<\; \operatorname{rank}[A\,|\,b] = 3 \;\Longrightarrow\; \text{no solution}$
6. A predefinição Equação repetida faz a mesma aritmética e diz outra coisa. Cada linha é um múltiplo da primeira, pelo que ambas as características valem 1 e o determinante volta a ser 0. O conjunto das soluções tem 3 − 1 = 2 direções livres: o plano inteiro x + y + z = 3. A ferramenta diz «uma infinidade» sem dizer em quantas direções.
  
  $\text{Infinitely many: } \operatorname{rank} A = \operatorname{rank}[A\,|\,b] = 1, \quad \det A = 0, \quad \dim = 3 - 1 = 2 \quad (x+y+z=3)$
7. Mude um número e veja qual das grandezas se mexe. Coloque 6 onde está o 7, à direita da linha 2. A matriz dos coeficientes fica intacta, pelo que o determinante nem estremece, mas a característica da ampliada desce para 2 e a resposta passa de nenhuma solução para uma reta de soluções.
  
  $b_2 = 7 \to 6: \quad \operatorname{rank}[A\,|\,b] = 2 = \operatorname{rank} A \;\Longrightarrow\; \dim = 3 - 2 = 1$
Resposta

O determinante limita-se a dizer se a matriz dos coeficientes tem o conjunto completo de pivôs. Nunca olha para o segundo membro, e é por isso que não consegue separar as duas predefinições, ao passo que as duas características conseguem: sem solução quando discordam, e um conjunto de soluções de dimensão 3 − característica quando coincidem. Assim que o determinante é 0, nenhum segundo membro lhe comprará uma resposta única: obtém nenhuma ou toda uma família, e a escolha entre essas duas é tudo o que b decide. O cartão do resíduo apaga-se pela mesma razão por que existe: um resíduo precisa de uma solução para repor nas equações.

$\dim = n - \operatorname{rank} A \ \text{ when } \operatorname{rank}[A|b] = \operatorname{rank} A; \qquad \det A = 0 \;\Longrightarrow\; \text{no } b \ \text{gives exactly one}$
Três equações, à mão 5 passos
Resolve x + y + z = 6, 2x − y + z = 3, x + 2y − z = 2.

Abrir este problema na ferramenta
Mostrar solução
1. Elimina x da segunda linha: subtrai-lhe o dobro da primeira.
  
  $R_2\to R_2-2R_1:\quad-3y-z=-9$
2. Elimina x da terceira linha: subtrai-lhe a primeira.
  
  $R_3\to R_3-R_1:\quad y-2z=-4$
3. Elimina y da terceira linha usando um terço da nova segunda linha. Só resta z.
  
  $\begin{gathered}R_3\to R_3+\tfrac13R_2\\-\tfrac73z=-7\ \Rightarrow\ z=3\end{gathered}$
4. Faz a substituição retroativa: substitui z na segunda linha para obter y; depois, substitui y e z na primeira para obter x.
  
  $y=2,\qquad x=6-2-3=1$
5. Verifica o resultado nas duas equações que não usaste no último passo.
  
  $2-2+3=3,\qquad1+4-3=2\ \checkmark$
Resposta

x = 1, y = 2, z = 3. O determinante é 7, pelo que esta é a única solução.

$x=1,\quad y=2,\quad z=3$
Infinitas soluções expressas com um parâmetro 4 passos
Resolve x + y + z = 3, x − y + z = 1, 2x + 2z = 4.
Mostrar solução
1. Subtrai a primeira linha à segunda: y = 1.
  
  $R_2\to R_2-R_1:\quad-2y=-2\ \Rightarrow\ y=1$
2. Subtrai o dobro da primeira linha à terceira: obténs novamente a mesma equação, pelo que a terceira linha não acrescenta informação.
  
  $R_3\to R_3-2R_1:\quad-2y=-2$
3. Há duas linhas independentes para três incógnitas e nenhuma contradição: uma das incógnitas é livre.
  
  $\operatorname{rank}A=\operatorname{rank}[A\,|\,b]=2<3$
4. Toma z = t, com t arbitrário. A primeira linha permite então obter x.
  
  $z=t:\quad x=3-1-t=2-t$
Resposta

(x, y, z) = (2 − t, 1, t) para qualquer t. Para t = 0, obténs (2, 1, 0); para t = 2, obténs (0, 1, 2). Ambas as soluções satisfazem as três equações.

$(x,y,z)=(2-t,\ 1,\ t),\quad t\in\mathbb{R}$

Problemas suplementares, só com a resposta

Resolve x + y + z = 2, y + z = 1, z = −1.

Mostrar resposta

z = −1, y = 2, x = 1. O sistema já é triangular, pelo que basta fazer a substituição retroativa.

$z=-1,\quad y=2,\quad x=1$
Resolve x + 2y + z = 4, 2x + y − z = −1, x − y + 2z = 7.

Mostrar resposta

x = 1, y = 0, z = 3.

$x=1,\quad y=0,\quad z=3$
Mostra que o sistema x + y + z = 1, x + 2y + 3z = 2, 2x + 3y + 4z = 5 não tem solução.

Mostrar resposta

A operação R₃ − R₁ − R₂ dá 0 no primeiro membro e 2 no segundo, mas 0 = 2 é impossível.

$R_3-R_1-R_2:\quad0=2$

Os mesmos dois passos, numa ordem que elimina qualquer escolha

Duas equações exigiam um único passo: subtrair um múltiplo de uma linha de outra. Três equações requerem esse mesmo passo e mais um, e a lista de passos indica ambos: uma troca, para colocar um número útil no pivô, e uma eliminação. A ordem é fixa: anular a primeira coluna, depois a segunda, ler o resultado na última linha e resolver de baixo para cima. Siga esta sequência e nunca precisará de engenho para escolher a equação a atacar. Reside aqui a diferença entre um enigma e um procedimento, e é por esse motivo que o método ganha escala: executar a mesma rotina sobre mil incógnitas é o que alimenta qualquer programa de engenharia no mundo, sessenta anos depois de ter merecido um nome.

O determinante é o produto dos pivôs

Acompanhe os pivôs durante a eliminação e multiplique-os. Depois, inverta o sinal uma vez por cada troca de linha. Esse é o determinante. Ele decorre do trabalho que você já estava a realizar. A maioria das pessoas aprende determinantes pela expansão de cofatores. Vale a pena entender o motivo pelo qual ninguém os calcula assim na prática: os cofatores custam cerca de n! operações perante as n³ da eliminação. Numa matriz 20 × 20, isso significa 2 × 10¹⁸ contra 8.000. Um fator de 10¹⁴ decide qual dos métodos se pode razoavelmente pedir a uma máquina. A primeira fórmula ensinada a todos é justamente aquela que nenhum computador jamais utilizou.

Uma escolha dentro do procedimento altera a resposta

Prima Pivotagem desligada. O coeficiente principal é 10⁻¹⁷, o algoritmo divide por ele obedientemente e devolve 0 para x quando a verdadeira resposta é 1. Nada falhou e nenhuma regra foi violada. Dividir por um valor tão pequeno multiplica os erros de arredondamento pré-existentes. Quando o cálculo atinge o topo da substituição regressiva, o erro já devorou a resposta. É um precipício, não uma encosta: reduzindo o coeficiente, 10⁻¹² ainda produz quatro algarismos corretos e 10⁻¹⁵ dá três, mas depois 10⁻¹⁶ devolve 2,22 e 10⁻¹⁷ devolve 0. O limite situa-se no épsilon da máquina, o salto entre 1 e o número seguinte que um double pode representar. Assinale a caixa e o algoritmo passará a dividir pelo maior número disponível, resolvendo cada um desses casos com exatidão. É para isso que o cartão de resíduos se encontra na página. Ele reintroduz a resposta nas equações originais, assumindo-se como a única via para distinguir uma solução real de um resultado puramente convicto.

Percurso de aprendizagem

Isolar o x, a partir do sinal de menos

Referências (1)

Two centuries of the method being reinvented and misattributed, including how Gauss's name came to be on it: J. F. Grcar, "How ordinary elimination became Gaussian elimination." Historia Mathematica 38:2 (2011), 163–218.

Pela equipa 7 Raven Room · Verificado com fontes publicadas. Correções bem-vindas.