Eliminação de Gauss-Jordan

Índice

2.1 INTRODUÇÃO
- 2.1.1 A Evolução da Resolução de Sistemas de Equações Lineares
- 2.1.2 Eliminação de Gauss
2.2 AULA
2.3 EXEMPLOS
2.4 ILUSTRAÇÕES
EXERCÍCIOS

2.1 INTRODUÇÃO

**Figura 1.** Uma foto do planeta anão Ceres tirada em 2015 pela nave espacial Dawn da NASA.

2.1.1 A Evolução da Resolução de Sistemas de Equações Lineares

Sistemas de equações lineares já eram abordados há quatro mil anos por matemáticos babilônicos.¹ Eles eram capazes de resolver sistemas simples de equações com duas incógnitas como $x + y = 12$ , $x - y = 2$ . Matemáticos chineses, nos "Nove Capítulos sobre a Arte Matemática", levaram isso a sistemas de três equações e também a cenários de teoria dos números relacionados que aparecem na forma do teorema chinês do resto. O problema de resolver sistemas de equações apareceu também na análise, como ao maximizar funções com restrições. O método dos determinantes, pioneiro por Leibniz, levou com Gabriel Cramer a fórmulas de solução explícitas de sistemas de equações. A abordagem moderna para resolver sistemas de equações usa um processo de eliminação claro e distinto. Esse processo é extremamente rápido e foi formalizado por Carl Friedrich Gauss. É o método que ainda usamos hoje. Ele também permite calcular determinantes de forma eficaz.

2.1.2 Eliminação de Gauss

A eliminação era certamente usada muito antes de Gauss. Aprendemos desde cedo como eliminação comum. Por exemplo, resolver para uma variável e substituí-la nas demais para obter um sistema com menos incógnitas. O que Gauss fez foi escrever um processo formal de eliminação. Isso aconteceu por volta de 1809. Ele chamou a eliminação comum de "eliminationem vulgarem". O processo não surgiu do nada. O trabalho em problemas bastante aplicados deve ter levado a isso. Por exemplo, Gauss em 1801 foi capaz, em poucas semanas, de prever a trajetória do planeta menor Ceres a partir de $24$ medições publicadas no verão de 1801. Relata-se que Gauss precisou de mais de $100$ horas para determinar os $5$ parâmetros da órbita. Exercícios como esse definitivamente motivaram Gauss a escrever mais tarde procedimentos mais formais que permitiam resolver problemas lineares ou problemas mais gerais de ajuste de dados. O nome "eliminação de Gauss" foi usado pela primeira vez por George Forsythe, enquanto Alan Turing a descreveu da forma como a ensinamos hoje. Veremos aqui formalmente que o processo determina de forma única.²

2.2 AULA

2.2.1 Transformações Lineares e Equações

Se uma matriz $n \times m$ $A$ é multiplicada por um vetor $x \in ℝ^{m}$ , obtemos um novo vetor $A x$ em $ℝ^{n}$ . O processo $x \to A x$ define uma aplicação linear de $ℝ^{m}$ para $ℝ^{n}$ . Dado $b \in ℝ^{n}$ , pode-se pedir para encontrar $x$ que satisfaça o sistema de equações lineares $A x = b$ . Historicamente, essa porta de entrada para a álgebra linear foi atravessada muito antes de as matrizes serem conhecidas: existem raízes babilônicas e chinesas que remontam a milhares de anos. ³

2.2.2 Matrizes Aumentadas e Redução de Linhas

A melhor maneira de resolver o sistema é reduzir por linhas a matriz aumentada $B = [A ∣ b] .$ Esta é uma matriz $n \times (m + 1)$ pois agora existem $m + 1$ colunas. O algoritmo de eliminação de Gauss-Jordan produz a partir de uma matriz $B$ uma matriz reduzida por linhas $rref (B)$ . O algoritmo permite fazer três coisas: subtrair uma linha de outra linha, multiplicar uma linha por um escalar e trocar duas linhas. Se olharmos para o sistema de equações, todas essas operações preservam o espaço de soluções. Nosso objetivo é produzir pivôs “ $1$ ”, que são entradas da matriz iguais a $1$ que são a primeira entrada não nula em uma linha. O objetivo é chegar a uma matriz que esteja na forma escalonada reduzida por linhas. Isso significa:

toda linha que não é nula possui um pivô,
toda coluna com um pivô $1$ não possui outras entradas não nulas além do pivô. A terceira condição é
toda linha acima de uma linha com um pivô tem um pivô mais à esquerda.

2.2.3 Unicidade da Forma Escalonada Reduzida por Linhas

Vamos praticar o processo em aula e no dever de casa. Aqui está um teorema

Teorema 1. Toda matriz $A$ possui uma única forma escalonada reduzida por linhas.

Prova. ⁴Usamos o método de indução em relação ao número $m$ de colunas da matriz. A hipótese de indução é o caso $m = 1$ onde existe apenas uma coluna. Pela condição B) pode haver zero ou $1$ entrada diferente de zero. Se não houver nenhuma, temos a coluna nula. Se for não nula, ela deve estar no topo pela condição C). Estamos na forma escalonada reduzida por linhas. Agora, suponhamos que todas as matrizes $n \times m$ possuam uma única forma escalonada reduzida por linhas. Tome uma matriz $n \times (m + 1)$ $[A ∣ b]$ . Ela permanece na forma escalonada reduzida por linhas, se a última coluna $b$ for deletada (veja lema). Remover a última coluna e reduzir por linhas é o mesmo que reduzir por linhas e depois deletar a última coluna. Assim, as colunas de $A$ são unicamente determinadas após a redução por linhas. Agora note que, para uma linha de $[A ∣ b]$ sem pivô no final, todas as entradas são zero, de modo que as últimas entradas também coincidem. Suponha que tenhamos duas reduções por linhas \left[A^{\prime} \mid b^{\prime}\right] e \left[A^{\prime} \mid c^{\prime}\right] onde A^{\prime} é a redução por linhas de $A$ . Um pivô “ $1$ ” na última coluna de \left[A^{\prime} \mid b^{\prime}\right] ) ocorre se e somente se a linha correspondente em $A$ era nula. Portanto, também \left[A^{\prime}, c^{\prime}\right] possui aquele pivô “ $1$ ” no final. Suponha agora que não haja pivô na última coluna e b_{k}^{\prime} \neq c_{k}^{\prime}. Temos então $x$ , uma solução para a equação A_{k q}^{\prime} x_{q}+A_{k, q+1}^{\prime} x_{q+1}+\cdots +A_{k, m}^{\prime} x_{m}=b_{k}^{\prime}. Como as soluções das equações permanecem soluções ao reduzir por linhas, também A_{k q}^{\prime} x_{q}+A_{k, q+1}^{\prime} x_{q+1}+\cdots+A_{k, m}^{\prime} x_{m}=c_{k}^{\prime}. Portanto b_{k}^{\prime}=c_{k}^{\prime}. ◻

2.2.4 O Lema do Particionamento de Matrizes na Construção de Provas

Um lema separado permite dividir a prova:

Se $[A ∣ b]$ está na forma escalonada reduzida por linhas, então $A$ está na forma escalonada reduzida por linhas.

Prova. Temos que verificar as três condições que definem a forma escalonada reduzida por linhas. ◻

2.2.5

Não é verdade que se $A$ está na forma escalonada reduzida por linhas, então qualquer submatriz está na forma escalonada reduzida por linhas. Você consegue encontrar um exemplo?

2.3 EXEMPLOS

Exemplo 1. Para reduzir por linhas, usamos os três passos e documentamos à direita. Para economizar espaço, às vezes informamos apenas depois de realizar dois passos. Circulamos o pivô $1$ . Note que não fomos imediatamente para o pivô $1$ escalonando a primeira. É uma boa ideia evitar frações tanto quanto possível.

imagem

Exemplo 2. Termine o seguinte problema de Sudoku, que é um jogo onde se deve preencher matrizes. As regras são que em cada um dos quatro subquadrados $2 \times 2$ , em cada uma das quatro linhas e em cada uma das quatro colunas, as entradas de $1$ a $4$ devem aparecer e, portanto, somar $10$ . $[\begin{matrix} 2 & 1 & x & 3 \\ 3 & y & z & 1 \\ 4 & 3 & a & 2 \\ b & c & d & e \end{matrix}]$ Temos as equações \left\{\begin{aligned} &2+1+x+3=10,\\ &3+y+z+1=10,\\ &4+3+a+2=10,\\ &b+c+d+e=10, \end{aligned}\right. para as linhas, \left\{\begin{aligned} &2+3+4+b=10,\\ &1+y+3+c=10,\\ & x+z+a+d=10,\\ &3+1+2+e=10 \end{aligned} \right. para as colunas e \left\{ \begin{aligned} &2+1+3+y=10,\\ &x+3+z+1=10,\\ &4+3+b+c=10,\\ & a+2+d+e=10 \end{aligned}\right. para os quatro quadrados. Poderíamos resolver o sistema escrevendo a matriz aumentada correspondente e depois fazendo a redução por linhas. A solução é $[\begin{array}{cccc} 2 & 1 & 4 & 3 \\ 3 & 4 & 2 & 1 \\ 4 & 3 & 1 & 2 \\ 1 & 2 & 3 & 4 \end{array}] .$

2.4 ILUSTRAÇÕES

O sistema de equações
\left\{\begin{aligned} &x\phantom{+y+z}+u\phantom{+v+w}&=3\\ &\phantom{x+}y\phantom{+z+u}+v\phantom{+w}&=5\\ &\phantom{x+y+~}z\phantom{+u+v}+w&=9\\ &x+y+z\phantom{+u+v+w}&=8\\ &\phantom{x+y+z+}u+v+w&=9 \end{aligned} \right.
é um problema de tomografia. Esses problemas aparecem em imagens por ressonância magnética. Um precursor foi a Tomografia Computadorizada por Raios-X (TC) pela qual Allen MacLeod Cormack recebeu o Nobel em 1979 (Cormack tirou um período sabático em Harvard em 1956-1957, onde a ideia surgiu). Cormack viveu até 1998 em Winchester MA. Ele originalmente era físico. Seu trabalho teve um tremendo impacto na medicina.

**Figura 2.** Um scanner de ressonância magnética pode medir médias das densidades dos tecidos ao longo de linhas. A RM (Ressonância Magnética) é uma técnica de imagem radiológica que evita a exposição à radiação do paciente). Resolver um sistema de equações permite calcular as densidades reais e, assim, fazer a mágica de "ver dentro do corpo".

Construímos a matriz aumentada $[A ∣ b]$ e reduzimos por linhas. Primeiro remova a soma das três primeiras linhas da 4ª, depois troque o sinal da 4ª coluna: \begin{aligned} \left[\begin{array}{ccccccc} \boxed{1} & 0 & 0 & 1 & 0 & 0 & 3 \\ 0 & \boxed{1} & 0 & 0 & 1 & 0 & 5 \\ 0 & 0 & 1 & 0 & 0 & 1 & 9 \\ 1 & 1 & 1 & 0 & 0 & 1 & 8 \\ 0 & 0 & 0 & 1 & 1 & 1 & 9 \end{array}\right] &\Rightarrow\left[\begin{array}{ccccccc} \boxed{1} & 0 & 0 & 1 & 0 & 0 & 3 \\ 0 & \boxed{1} & 0 & 0 & 1 & 0 & 5 \\ 0 & 0 & \boxed{1} & 0 & 0 & 1 & 9 \\ 0 & 0 & 0 & \boxed{1} & 1 & 1 & 9 \\ 0 & 0 & 0 & 1 & 1 & 1 & 9 \end{array}\right]\\ &\Rightarrow\left[\begin{array}{ccccccc} \boxed{1} & 0 & 0 & 0 & -1 & -1 & -6 \\ 0 & \boxed{1} & 0 & 0 & 1 & 0 & 5 \\ 0 & 0 & \boxed{1} & 0 & 0 & 1 & 9 \\ 0 & 0 & 0 & \boxed{1} & 1 & 1 & 9 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right] \end{aligned}

Agora podemos ler as soluções. Vemos que $v$ e $w$ podem ser escolhidos livremente. Eles são variáveis livres. Escrevemos $v = r$ e $w = s$ . Então basta resolver para as variáveis:

\begin{aligned} x & =-6+r+s \\ y & =5-r \\ z & =9-s \\ u & =9-r-s \\ v & =r \\ w & =s \end{aligned}

**Figura 3.** Este é um poliedro com $F = 540$ faces. No dever de casa você calcula, somente a partir desse conhecimento, o número de vértices $V$ e o número de arestas $E$ . As equações que valem são $V - E + F = 2$ e $3 F = 2 E$ .

EXERCÍCIOS

Exercício 1. Para um poliedro com $v$ vértices, $e$ arestas e $f$ faces triangulares, Euler provou sua famosa fórmula $V - E + F = 2$ . Uma outra relação \(3 F

Eu verifiquei com Ajak, que também deu a entender que Phastos pode ter vazado a eliminação de Gauss-Jordan. A cena de abertura do mais novo filme da Marvel mostra os eternos chegando aqui em 5000 a.C.↩︎
J.F. Grcar, Mathematicians of Gaussian Elimination, Notices of the AMS, 58, 2011.↩︎
Para mais informações, veja a exposição no site do Math 22a de 2018.↩︎
A prova é bem conhecida: i.e., Thomas Yuster, Mathematics Magazine, 1984.↩︎