Eliminação gaussiana

Na matemática, a eliminação gaussiana, também conhecida como redução de linha, é um algoritmo para resolver sistemas de equações lineares. Consiste em uma sequência de operações realizadas na matriz de coeficientes correspondente. Esse método também pode ser usado para calcular o posto de uma matriz, o determinante de uma matriz quadrada e o inverso de uma matriz invertível. O método recebeu o nome de Carl Friedrich Gauss (1777–1855), embora alguns casos especiais do método - embora apresentados sem prova - fossem conhecidos pelos matemáticos chineses já por volta de 179 DC.

Para realizar a redução de linha em uma matriz, usa-se uma sequência de operações elementares de linha para modificar a matriz até que o canto inferior esquerdo da matriz seja preenchido com zeros, tanto quanto possível. Existem três tipos de operações de linha elementares:

• Despertando duas fileiras,
• Multiplicando uma linha por um número nonzero,
• Adicionando um múltiplo de uma linha para outra linha. (a subtração pode ser alcançada multiplicando uma linha com -1 e adicionando o resultado a outra linha)

Usando essas operações, uma matriz sempre pode ser transformada em uma matriz triangular superior e, de fato, em uma forma escalonada de linhas. Uma vez que todos os coeficientes líderes (a entrada diferente de zero mais à esquerda em cada linha) são 1, e cada coluna contendo um coeficiente líder tem zeros em outro lugar, diz-se que a matriz está na forma escalonada de linhas reduzidas. Esta forma final é única; em outras palavras, é independente da sequência de operações de linha usada. Por exemplo, na seguinte sequência de operações de linhas (onde duas operações elementares em linhas diferentes são feitas no primeiro e no terceiro passos), a terceira e a quarta matrizes são aquelas na forma escalonada de linhas, e a matriz final é a única linha reduzida forma escalonada.

Não.131911- Sim. - Sim. 11311535]→ → Não.13190- Sim. - Sim. 2- Sim. - Sim. 2- Sim. - Sim. 80228]→ → Não.13190- Sim. - Sim. 2- Sim. - Sim. 2- Sim. - Sim. 80000]→ → Não.10- Sim. - Sim. 2- Sim. - Sim. 301140000]{displaystyle {begin{bmatrix}1&3&1&1&9\1&1&-1&13&11&5&35end{bmatrix}}to {begin{bmatrix}1&3&1&9\0&-2&-2&-8&2&2&8end{bmatrix}}to (begin{bmatrix}1&3&1&9\0&-2&-2&-8&0&0end{bmatrix}}to (begin{bmatrix}1&0&-2&-3&1&1&4&0&0&0end{bmatrix}}}

O uso de operações de linha para converter uma matriz em uma forma escalonada de linha reduzida às vezes é chamado de eliminação de Gauss–Jordan. Nesse caso, o termo eliminação Gaussiana refere-se ao processo até que ele atinja sua forma triangular superior ou escalonada (não reduzida). Por motivos computacionais, ao resolver sistemas de equações lineares, às vezes é preferível interromper as operações de linha antes que a matriz seja completamente reduzida.

Definições e exemplo de algoritmo

O processo de redução de linha faz uso de operações elementares de linha e pode ser dividido em duas partes. A primeira parte (às vezes chamada de eliminação direta) reduz um determinado sistema à forma escalonada de linhas, a partir da qual se pode dizer se não há soluções, uma solução única ou infinitas soluções. A segunda parte (às vezes chamada de substituição inversa) continua a usar operações de linha até que a solução seja encontrada; em outras palavras, ele coloca a matriz na forma escalonada reduzida.

Outro ponto de vista, que acaba sendo muito útil para analisar o algoritmo, é que a redução de linhas produz uma decomposição matricial da matriz original. As operações elementares de linha podem ser vistas como a multiplicação à esquerda da matriz original por matrizes elementares. Alternativamente, uma sequência de operações elementares que reduz uma única linha pode ser vista como uma multiplicação por uma matriz de Frobenius. Em seguida, a primeira parte do algoritmo calcula uma decomposição LU, enquanto a segunda parte escreve a matriz original como o produto de uma matriz invertível determinada exclusivamente e uma matriz escalonada reduzida determinada exclusivamente.

Operações de linha

Existem três tipos de operações elementares com linhas que podem ser realizadas nas linhas de uma matriz:

1. Troque as posições de duas linhas.
2. Multiplique uma linha por um escalar não zero.
3. Adicionar a uma linha um escalar vários de outro.

Se a matriz estiver associada a um sistema de equações lineares, então estas operações não alteram o conjunto solução. Portanto, se o objetivo de alguém é resolver um sistema de equações lineares, usar essas operações de linha pode tornar o problema mais fácil.

Forma escalão

Para cada linha em uma matriz, se a linha não consistir apenas em zeros, a entrada diferente de zero mais à esquerda é chamada de coeficiente principal (ou pivot) dessa linha. Portanto, se dois coeficientes principais estiverem na mesma coluna, uma operação de linha do tipo 3 pode ser usada para tornar um desses coeficientes zero. Então, usando a operação de troca de linha, pode-se sempre ordenar as linhas de modo que, para cada linha diferente de zero, o coeficiente líder esteja à direita do coeficiente líder da linha acima. Se for esse o caso, diz-se que a matriz está na forma escalonada por linhas. Portanto, a parte inferior esquerda da matriz contém apenas zeros e todas as linhas zero estão abaixo das linhas diferentes de zero. A palavra "escalão" é usado aqui porque pode-se pensar aproximadamente nas linhas sendo classificadas por seu tamanho, com a maior no topo e a menor na parte inferior.

Por exemplo, a matriz a seguir está em forma escalonada de linhas e seus coeficientes líderes são mostrados em vermelho:

Não.021- Sim. - Sim. 100310000].{displaystyle {begin{bmatrix}0&color {red}{mathbf {2} }&1&-1\0&0&color {red}{mathbf {3} }&1&0&0&0end{bmatrix}}}

Está na forma escalonada porque a linha zero está na parte inferior e o coeficiente líder da segunda linha (na terceira coluna) está à direita do coeficiente líder da primeira linha (na segunda coluna).

Diz-se que uma matriz está na forma escalonada reduzida se, além disso, todos os coeficientes líderes são iguais a 1 (o que pode ser obtido usando a operação elementar de linha do tipo 2) e em cada coluna contendo um coeficiente líder, todas as outras entradas nessa coluna são zero (o que pode ser obtido usando operações de linha elementares do tipo 3).

Exemplo do algoritmo

Suponha que o objetivo seja encontrar e descrever o conjunto de soluções para o seguinte sistema de equações lineares:

2x+Sim.- Sim. - Sim. zangão.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =8(L1)- Sim. - Sim. 3x- Sim. - Sim. Sim.+2zangão.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =- Sim. - Sim. 11(L2)- Sim. - Sim. 2x+Sim.+2zangão.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =- Sim. - Sim. 3(L3){displaystyle {begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&qquad (L_{1})\-3x&{}-{}&y&{}+{}&2z&{}={}&-11&qquad (L_{2})\-2x&{}+{}&y&{}+{}&2z&{}={}&-3&qquad (L_{3})end{alignedat}}}

A tabela abaixo é o processo de redução de linha aplicado simultaneamente ao sistema de equações e sua matriz aumentada associada. Na prática, não se costuma tratar os sistemas em termos de equações, mas sim utilizar a matriz aumentada, que é mais adequada para manipulações computacionais. O procedimento de redução de linhas pode ser resumido da seguinte forma: elimine x de todas as equações abaixo de L₁ e, em seguida, elimine y de todas as equações abaixo de L₂. Isso colocará o sistema na forma triangular. Então, usando a substituição inversa, cada incógnita pode ser resolvida.

Sistema de equações	Operações de linha	Matriz aumentada
2x+Sim.- Sim. - Sim. zangão.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =8- Sim. - Sim. 3x- Sim. - Sim. Sim.+2zangão.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =- Sim. - Sim. 11- Sim. - Sim. 2x+Sim.+2zangão.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =- Sim. - Sim. 3{displaystyle {begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&z&{}={}&8&\-3x&{}-{}&y&{}+{}2z&{}={}={}======================================================================================================================================================================================		Não.21- Sim. - Sim. 18- Sim. - Sim. 3- Sim. - Sim. 12- Sim. - Sim. 11- Sim. - Sim. 212- Sim. - Sim. 3]{displaystyle left[{begin{array}{rrr|r}2&1&-1&8\-3&-1&2&-11\-2&1&2&-3end{array}}right]}
2x+Sim.- Sim. - Sim. zangão.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =812Sim.+12zangão.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =12Sim.+zangão.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =5{displaystyle {begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&&&&&{tfrac {1}{2}}y&{}+{}&{tfrac {1}{2}}z&{}={}&1&&&&2y&{}+{}&z&{}={}&5&end{alignedat}}}}}	L2+32L1→ → L2L3+L1→ → L3- Sim. {3}{2}}L_{1}&to L_{2}\L_{3}+L_{1}&to L_{3}end{aligned}}}	Não.21- Sim. - Sim. 180121210215]{displaystyle left[{begin{array}{rrr|r}2&1&-1&8&{frac {1}{2}}&{frac {1}{2}}&1&2&1&5end{array}}right]}
2x+Sim.- Sim. - Sim. zangão.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =812Sim.+12zangão.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1- Sim. - Sim. zangão.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1{displaystyle {begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&&&&&{tfrac {1}{2}}y&{}+{}&{tfrac {1}{2}}z&{}={}&1&&&&&&&&-z&{}={}&1&1&end{alignedat}}}}}}}	L3+- Sim. - Sim. 4L2→ → L3Não. L_{3}+-4L_{2}to L_{3}}	Não.21- Sim. - Sim. 1801212100- Sim. - Sim. 11]{displaystyle left[{begin{array}{rrr|r}2&1&-1&8&{frac {1}{2}}&{frac {1}{2}}&1&0&-1&1end{array}}right]}
A matriz está agora em forma de echelon (também chamada forma triangular)
2x+Sim.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =712Sim.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =32- Sim. - Sim. zangão.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1{displaystyle {begin{alignedat}{4}2x&{}+{}&y&&{}={}7&&&{tfrac {1}{2}}y&&&&{}={}{tfrac {3}{2}}&\&&&&{}-{}&z&{}={}1&end{alignedat}}}}}	L2+12L3→ → L2L1- Sim. - Sim. L3→ → L1- Sim. {1}{2}}L_{3}&to L_{2}\L_{1}-L_{3}&to L_{1}end{aligned}}}	Não.210701203200- Sim. - Sim. 11]{displaystyle left[{begin{array}{rrr|r}2&1&0&7&{frac {1}{2}}&0&{frac {3}{2}}&0&-1&1end{array}}right]}
2x+Sim.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =7Sim.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =3zangão.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =- Sim. - Sim. 1{displaystyle {begin{alignedat}{4}2x&{}+{}&y&quad &&{}={}&7&&&&y&quad &&{}={}&3&&&&&quad &z&{}={}&-1&end{alignedat}}}	2L2→ → L2- Sim. - Sim. L3→ → L3{displaystyle {begin{aligned}2L_{2}&to L_{2}\-L_{3}&to L_{3}end{aligned}}}	Não.21070103001- Sim. - Sim. 1]{displaystyle left[{begin{array}{rrr|r}2&1&0&7&1&0&3\0&0&1&-1end{array}}right]}
x= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =2Sim.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =3zangão.= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =- Sim. - Sim. 1{displaystyle {begin{alignedat}{4}x&quad &&quad &&{}={}&2&\quad &y&quad &&&{}={}&3&&quad &&quad &&quad &z&{}={}={}&-1&end{alignedat}}}	L1- Sim. - Sim. L2→ → L112L1→ → L1{displaystyle {begin{aligned}L_{1}-L_{2}&to L_{1}\{tfrac {1}{2}}L_{1}&to L_{1}end{aligned}}}	Não.10020103001- Sim. - Sim. 1]{displaystyle left[{begin{array}{rrr|r}1&0&0&0&2&1&0&3\0&0&1&-1end{array}}right]}

A segunda coluna descreve quais operações de linha acabaram de ser executadas. Portanto, para a primeira etapa, o x é eliminado de L ₂ adicionando 3/2L₁ para L₂. Em seguida, x é eliminado de L₃ adicionando L₁ a L ₃. Essas operações de linha são rotuladas na tabela como

L2+32L1→ → L2,L3+L1→ → L3.- Sim. {3}{2}}L_{1}&to L_{2},L_{3}+L_{1}&to L_{3}.end{aligned}}}

Uma vez que y também é eliminado da terceira linha, o resultado é um sistema de equações lineares em forma triangular, e assim a primeira parte do algoritmo está completa. Do ponto de vista computacional, é mais rápido resolver as variáveis na ordem inversa, processo conhecido como back-substitution. Vê-se que a solução é z = −1, y = 3, e x = 2. Portanto, existe uma solução única para o sistema de equações original.

Em vez de parar quando a matriz estiver na forma escalonada, pode-se continuar até que a matriz esteja na forma escalonada reduzida, como é feito na tabela. O processo de redução de linha até que a matriz seja reduzida às vezes é chamado de eliminação de Gauss-Jordan, para distingui-lo da parada após atingir a forma escalonada.

História

O método da eliminação Gaussiana aparece – embora sem provas – no texto matemático chinês Capítulo Oito: Arranjos Retangulares dos Os Nove Capítulos sobre a Arte Matemática. Seu uso é ilustrado em dezoito problemas, com duas a cinco equações. A primeira referência ao livro com este título é datada de 179 AD, mas partes dele foram escritas por volta de 150 BC. Foi comentado por Liu Hui no século III.

O método na Europa deriva das notas de Isaac Newton. Em 1670, ele escreveu que todos os livros de álgebra conhecidos por ele careciam de uma lição para resolver equações simultâneas, que Newton então forneceu. A Universidade de Cambridge acabou publicando as notas como Arithmetica Universalis em 1707, muito depois de Newton ter deixado a vida acadêmica. As notas foram amplamente imitadas, o que tornou (o que agora é chamado) a eliminação gaussiana uma lição padrão nos livros de álgebra no final do século XVIII. Carl Friedrich Gauss em 1810 criou uma notação para eliminação simétrica que foi adotada no século 19 por computadores manuais profissionais para resolver as equações normais de problemas de mínimos quadrados. O algoritmo ensinado no ensino médio recebeu o nome de Gauss apenas na década de 1950, como resultado de uma confusão sobre a história do assunto.

Alguns autores usam o termo eliminação Gaussiana para se referir apenas ao procedimento até que a matriz esteja na forma escalonada, e usam o termo eliminação Gauss-Jordan para se referir ao procedimento que termina na forma escalonada reduzida. O nome é usado porque é uma variação da eliminação gaussiana descrita por Wilhelm Jordan em 1888. No entanto, o método também aparece em um artigo de Clasen publicado no mesmo ano. Jordan e Clasen provavelmente descobriram a eliminação de Gauss-Jordan de forma independente.

Aplicativos

Historicamente, a primeira aplicação do método de redução de linha é para resolver sistemas de equações lineares. Abaixo estão algumas outras aplicações importantes do algoritmo.

Determinantes computacionais

Para explicar como a eliminação Gaussiana permite o cálculo do determinante de uma matriz quadrada, temos que lembrar como as operações elementares de linhas alteram o determinante:

• Despertar duas linhas multiplica o determinante por −1
• Multiplicando uma linha por um escalar nonzero multiplica o determinante pelo mesmo escalar
• Adicionar a uma linha um escalar múltiplo de outra não altera o determinante.

Se a eliminação gaussiana aplicada a uma matriz quadrada A produz uma matriz escalonada de linhas B, seja d o produto dos escalares pelos quais o determinante foi multiplicado, usando as regras acima. Então o determinante de A é o quociente por d do produto dos elementos da diagonal de B:

- Não.(A)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =? ? Diagnóstico⁡ ⁡ (B)D.{displaystyle det(A)={frac {prod operatorname {diag} (B)}{d}}.}

Computacionalmente, para um n × n matriz, este método só precisa O(n) operações aritméticas, ao usar a fórmula Leibniz para determinantes requer On! operações (número de somas na fórmula) e expansão Laplace recursiva requer O(2)ⁿ) operações (número de subdeterminantes para computar, se nenhum é computado duas vezes). Mesmo nos computadores mais rápidos, esses dois métodos são impraticáveis ou quase impraticáveis para n acima de 20.Não.

Encontrando a inversa de uma matriz

Uma variante da eliminação gaussiana chamada eliminação Gauss-Jordan pode ser usada para encontrar a inversa de uma matriz, se ela existir. Se A for um n × n matriz quadrada, então pode-se usar a redução de linhas para calcular sua matriz inversa, se ela existir. Primeiro, a matriz de identidade n × n é aumentada à direita de A, formando uma matriz de blocos n × 2n [A | Eu]. Agora, por meio da aplicação de operações elementares de linhas, encontre a forma escalonada reduzida dessa matriz n × 2n. A matriz A é invertível se e somente se o bloco esquerdo puder ser reduzido à matriz identidade I ; neste caso, o bloco direito da matriz final é A⁻¹. Se o algoritmo não conseguir reduzir o bloco esquerdo para I, então A não é invertível.

Por exemplo, considere a seguinte matriz:

A= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =Não.2- Sim. - Sim. 10- Sim. - Sim. 12- Sim. - Sim. 10- Sim. - Sim. 12].Não. A={begin{bmatrix}2&-1&0\-1&2&-1\0&-1&2end{bmatrix}}.}

Para encontrar o inverso desta matriz, toma-se a seguinte matriz aumentada pela identidade e a reduz por linhas como uma matriz 3 × 6:

Não.A|Eu...]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =Não.2- Sim. - Sim. 10100- Sim. - Sim. 12- Sim. - Sim. 10100- Sim. - Sim. 12001].Não. [A|I]=left[{begin{array}{ccc|ccc}2&-1&0&1&0&0&0\-1&2&-1&0&1&0&-1&2&0&0&0&0&1end{array}}right].}

Ao realizar operações de linha, pode-se verificar que a forma escalonada de linha reduzida desta matriz aumentada é

Não.Eu...|B]= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =Não.10034121401012112001141234].Não. [I|B]=left[{begin{array}{rrr|rrr}1&0&0&0&{frac {3}{4}}&{frac {1}{2}}&{frac {1}{4}}&1&0&0&{frac {1}{2}}&1&{frac {1}{2}}&0&1&{frac {1}{2}}&{frac {3}{4}}end{array}}right].}

Pode-se pensar em cada operação de linha como o produto à esquerda por uma matriz elementar. Denotando por B o produto dessas matrizes elementares, mostramos, à esquerda, que BA = I e, portanto, B = A⁻¹ . À direita, mantivemos um registro de BI = B, que sabemos ser o inverso desejado. Este procedimento para encontrar o inverso funciona para matrizes quadradas de qualquer tamanho.

Calculando fileiras e bases

O algoritmo de eliminação gaussiana pode ser aplicado a qualquer matriz m × n A. Desta forma, por exemplo, algumas matrizes 6 × 9 podem ser transformadas em uma matriz que tem uma forma escalonada de linhas como

T= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =Não.um∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ 00b)∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ 000c∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ 000000D∗ ∗ ∗ ∗ 00000000e000000000],Não. &0 &0 &0 &0

onde as estrelas são entradas arbitrárias, e a, b, c, d , e são entradas diferentes de zero. Esta matriz escalonada T contém uma riqueza de informações sobre A: a classificação de A é 5, pois há 5 linhas diferentes de zero em T; o espaço vetorial gerado pelas colunas de A tem uma base que consiste em suas colunas 1, 3, 4, 7 e 9 (o colunas com a, b, c, d, e em T), e as estrelas mostram como as outras colunas de A pode ser escrito como combinações lineares das colunas base. Isso é consequência da distributividade do produto escalar na expressão de um mapa linear como uma matriz.

Tudo isso também se aplica à forma escalonada reduzida, que é um formato escalonado particular.

Eficiência computacional

O número de operações aritméticas necessárias para executar a redução de linha é uma forma de medir a eficiência computacional do algoritmo. Por exemplo, para resolver um sistema de equações n para n incógnitas executando operações de linha na matriz até que ela esteja na forma escalonada e, em seguida, resolvendo cada incógnita na ordem inversa, requer n(n + 1)/2 divisões, (2n³ + 3n² − 5n)/6 multiplicações e (2n³ + 3n² − 5n)/6 subtrações, para um total de aproximadamente 2n³/3 operações. Portanto, ele tem uma complexidade de tempo de O(n³).

Essa complexidade é uma boa medida do tempo necessário para toda a computação quando o tempo para cada operação aritmética é aproximadamente constante. Este é o caso quando os coeficientes são representados por números de ponto flutuante ou quando pertencem a um corpo finito. Se os coeficientes forem inteiros ou números racionais representados com exatidão, as entradas intermediárias podem crescer exponencialmente, de modo que a complexidade do bit é exponencial. Porém, existe uma variante de eliminação gaussiana, chamada de algoritmo de Bareiss, que evita esse crescimento exponencial das entradas intermediárias e, com a mesma complexidade aritmética de O(n ³), tem um pouco de complexidade de O(n⁵).

Este algoritmo pode ser usado em um computador para sistemas com milhares de equações e incógnitas. No entanto, o custo torna-se proibitivo para sistemas com milhões de equações. Esses grandes sistemas são geralmente resolvidos usando métodos iterativos. Existem métodos específicos para sistemas cujos coeficientes seguem um padrão regular (ver sistema de equações lineares).

Para colocar uma matriz n × n na forma escalonada reduzida por operações de linha, é necessário n³ operações aritméticas, que são aproximadamente 50% mais etapas de computação.

Um possível problema é a instabilidade numérica, causada pela possibilidade de divisão por números muito pequenos. Se, por exemplo, o coeficiente líder de uma das linhas estiver muito próximo de zero, então, para reduzir a linha da matriz, seria necessário dividir por esse número. Isso significa que qualquer erro que existisse para o número que fosse próximo de zero seria amplificado. A eliminação gaussiana é numericamente estável para matrizes diagonalmente dominantes ou positivas definidas. Para matrizes gerais, a eliminação gaussiana é geralmente considerada estável, quando se usa pivotamento parcial, embora existam exemplos de matrizes estáveis para as quais ela é instável.

Generalizações

A eliminação gaussiana pode ser realizada em qualquer corpo, não apenas nos números reais.

O algoritmo de Buchberger é uma generalização da eliminação gaussiana para sistemas de equações polinomiais. Essa generalização depende muito da noção de ordem monomial. A escolha de uma ordenação das variáveis já está implícita na eliminação gaussiana, manifestando-se na escolha de trabalhar da esquerda para a direita ao selecionar as posições dos pivôs.

Calcular a classificação de um tensor de ordem maior que 2 é NP-difícil. Portanto, se P ≠ NP, não pode haver um análogo de tempo polinomial da eliminação Gaussiana para tensores de ordem superior (matrizes são representações de matrizes de tensores de ordem 2).

Pseudocódigo

Como explicado acima, a eliminação Gaussiana transforma uma dada matriz m × n A em uma matriz na forma escalonada de linha.

No seguinte pseudocódigo, A[i, j] denota a entrada da matriz A na linha i e na coluna j com os índices a partir de 1. A transformação é realizada no lugar, significando que a matriz original é perdida por ser eventualmente substituída por sua forma escalonada de linhas.

: Inicialização da linha dinâmica *
Não. 1 /* Inicialização da coluna pivô *

enquanto h ≤ m e k ≤ n
Não. Encontre o pivô k-th: *
i_max:= argmax (i = h... m, abs(A[i, k]))
 se A[i_max, k] = 0
Não. Nenhum pivô nesta coluna, passe para a próxima coluna *
: = k + 1
 mais linhas de swap(h, i_max)
Não. Faça para todas as linhas abaixo pivô: *
 para i = h + 1... m:
Não. A[i, k] / A[h, k]
Não. Preencha com zeros a parte inferior da coluna pivô: *
A [i, k] 0
Não. Faça para todos os elementos restantes na linha atual: *
 para j = k + 1... n:
A [i, j]: A[i, j] - A[h, j]
Não. Aumentar a linha dinâmica e coluna *
: = h + 1
: = k + 1

Este algoritmo difere um pouco do discutido anteriormente, escolhendo um pivô com o maior valor absoluto. Tal giro parcial pode ser requerido se, no lugar do pivô, a entrada da matriz for zero. De qualquer forma, escolher o maior valor absoluto possível do pivô melhora a estabilidade numérica do algoritmo, quando o ponto flutuante é usado para representar números.

Após a conclusão deste procedimento, a matriz estará na forma escalonada de linhas e o sistema correspondente poderá ser resolvido por substituição inversa.