Eliminação gaussiana - Gaussian elimination

Em matemática, a eliminação de Gauss , também conhecida como redução de linha , é um algoritmo para resolver sistemas de equações lineares . Consiste em uma seqüência de operações realizadas na matriz de coeficientes correspondente . Este método também pode ser usado para calcular a classificação de uma matriz, o determinante de uma matriz quadrada e o inverso de uma matriz invertível . O método tem 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 por volta de 179 DC.

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

  • Trocando duas linhas,
  • Multiplicando uma linha por um número diferente de zero,
  • Adicionando um múltiplo de uma linha a outra linha.

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

O uso de operações de linha para converter uma matriz em forma escalonada de linha reduzida é algumas vezes chamado de eliminação de Gauss-Jordan . Nesse caso, o termo eliminação gaussiana se refere ao processo até que ele alcance sua forma triangular superior ou escalonada em linha (não reduzida). Por razões 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 de linha elementares e pode ser dividido em duas partes. A primeira parte (às vezes chamada de eliminação direta) reduz um determinado sistema à forma escalonada de linha , 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 reversa ) continua a usar operações de linha até que a solução seja encontrada; em outras palavras, ele coloca a matriz na forma escalonada de linha reduzida .

Outro ponto de vista, que se mostra muito útil para analisar o algoritmo, é que a redução da linha produz uma decomposição 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 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 de forma única e uma matriz escalonada de linha reduzida determinada de forma única.

Operações de linha

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

  1. Troque as posições de duas linhas.
  2. Multiplique uma linha por um escalar diferente de zero .
  3. Adicione a uma linha um múltiplo escalar de outra.

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

Forma escalonada

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 líder (ou pivô ) dessa linha. Portanto, se dois coeficientes principais estão 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 de linhas . Portanto, a parte inferior esquerda da matriz contém apenas zeros e todas as linhas zero estão abaixo das linhas diferentes. A palavra "escalão" é usada 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á na forma escalonada de linha e seus coeficientes principais são mostrados em vermelho:

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).

Uma matriz é considerada em forma escalonada de linha reduzida se, além disso, todos os coeficientes principais forem iguais a 1 (o que pode ser alcançado usando a operação de linha elementar do tipo 2), e em cada coluna contendo um coeficiente líder, todos os 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 :

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 costumamos lidar com os sistemas em termos de equações, mas, em vez disso, fazemos uso da matriz aumentada, que é mais adequada para manipulações computacionais. O procedimento de redução de linha pode ser resumido da seguinte forma: elimine x de todas as equações abaixo de L 1 e, em seguida, elimine y de todas as equações abaixo de L 2 . Isso colocará o sistema em forma triangular . Então, usando a substituição reversa, cada incógnita pode ser resolvida.

Sistema de equações Operações de linha Matriz aumentada
A matriz agora está em forma escalonada (também chamada de forma triangular)

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

Uma vez que y também é eliminado da terceira linha, o resultado é um sistema de equações lineares em forma triangular e, portanto, a primeira parte do algoritmo está completa. Do ponto de vista computacional, é mais rápido resolver as variáveis ​​na ordem reversa, processo conhecido como substituição reversa. Vê-se que a solução é z = −1 , y = 3 e x = 2 . Portanto, há 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 de linha reduzida , como é feito na tabela. O processo de redução da linha até que a matriz seja reduzida é algumas vezes referido como eliminação de Gauss-Jordan , para distingui-lo da parada após atingir a forma escalonada.

História

O método de eliminação gaussiana aparece - embora sem prova - no texto matemático chinês Capítulo Oito: Matrizes Retangulares dos 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 DC, mas partes dele foram escritas aproximadamente em 150 AC. 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 que conhecia 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 didáticos de álgebra no final do século XVIII. Carl Friedrich Gauss, em 1810, desenvolveu 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 que é ensinado no ensino médio recebeu o nome de Gauss apenas na década de 1950, como resultado da confusão sobre a história do assunto.

Alguns autores usam o termo eliminação de Gauss para se referir apenas ao procedimento até que a matriz esteja na forma escalonada, e usam o termo eliminação de 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 independentemente.

Formulários

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

Determinantes de computação

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 linha mudam o determinante:

  • Trocar duas linhas multiplica o determinante por -1
  • Multiplicar uma linha por um escalar diferente de zero multiplica o determinante pelo mesmo escalar
  • Adicionar a uma linha um múltiplo escalar de outra não altera o determinante.

Se a eliminação gaussiana aplicada a uma matriz quadrada A produz uma matriz escalonada de linha 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 :

Computacionalmente, para um n × n matriz, este método necessita apenas de O ( n 3 ) operações aritméticas, enquanto utilizando fórmula Leibniz para determinantes exige O ( N !) Operações (Número de summands na fórmula), e recursiva expansão Laplace requer O ( 2 n ) operações (número de subdeterminantes a calcular, se nenhum for calculado 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.

Encontrando o inverso de uma matriz

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

Por exemplo, considere a seguinte matriz:

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

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

Pode-se pensar em cada operação de linha como o produto esquerdo de uma matriz elementar . Denotando por B o produto dessas matrizes elementares, mostramos, à esquerda, que BA = I e, portanto, B = A −1 . À 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.

Classes e bases de computação

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

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, uma vez que existem 5 linhas diferentes de zero em T ; o espaço vetorial estendido pelas colunas de A tem uma base consistindo em suas colunas 1, 3, 4, 7 e 9 (as colunas com a , b , c , d , e em T ), e as estrelas mostram como as outras colunas de A podem ser escritos como combinações lineares das colunas de base. Isso é uma consequência da distributividade do produto escalar na expressão de um mapa linear como uma matriz .

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

Eficiência computacional

O número de operações aritméticas necessárias para realizar a redução de linha é uma forma de medir a eficiência computacional do algoritmo. Por exemplo, para resolver um sistema de n equações para n incógnitas realizando operações de linha na matriz até que esteja na forma escalonada e, em seguida, resolvendo para cada incógnita na ordem inversa, requer n ( n + 1) / 2 divisões, (2 n 3 + 3 N 2 - 5 N ) / 6 multiplicações, e (2 N 3 + 3 N 2 - 5 N ) / 6 subtracções, para um total de cerca de 2 N 3 /3 operações. Assim, ele tem complexidade aritmética de O ( n 3 ) ; veja Big O notação .

Essa complexidade aritmética é uma boa medida do tempo necessário para todo o cálculo quando o tempo de cada operação aritmética é aproximadamente constante. Esse é 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 exatamente, 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 3 ) , possui uma complexidade de bits de O ( n 5 ) .

Este algoritmo pode ser usado em um computador para sistemas com milhares de equações e incógnitas. No entanto, o custo se torna 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 um n × n matriz em forma escalonada reduzida por operações de linha, é necessário n 3 operações aritméticas, que é 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 é 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 existente para o número próximo a zero seria amplificado. A eliminação gaussiana é numericamente estável para matrizes diagonalmente dominantes ou definidas positivamente . Para matrizes gerais, a eliminação gaussiana é geralmente considerada estável, ao usar pivotamento parcial , embora haja exemplos de matrizes estáveis ​​para as quais é instável.

Generalizações

A eliminação gaussiana pode ser realizada em qualquer campo , 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 uma ordem monomial . A escolha de uma ordenação nas variáveis ​​já está implícita na eliminação gaussiana, manifestando-se como a escolha de trabalhar da esquerda para a direita ao selecionar as posições do pivô.

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 no tempo polinomial da eliminação gaussiana para tensores de ordem superior (matrizes são representações de matriz de tensores de ordem 2).

Pseudo-código

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

No pseudocódigo a seguir , A[i, j]denota a entrada da matriz A na linha ie coluna j com os índices começando em 1. A transformação é realizada no local , significando que a matriz original é perdida por ser eventualmente substituída por sua forma escalonada de linha.

h := 1 /* Initialization of the pivot row */
k := 1 /* Initialization of the pivot column */

while h ≤ m and k ≤ n
    /* Find the k-th pivot: */
    i_max := argmax (i = h ... m, abs(A[i, k]))
    if A[i_max, k] = 0
        /* No pivot in this column, pass to next column */
        k := k+1
    else
         swap rows(h, i_max)
         /* Do for all rows below pivot: */
         for i = h + 1 ... m:
             f := A[i, k] / A[h, k]
             /* Fill with zeros the lower part of pivot column: */
             A[i, k] := 0
             /* Do for all remaining elements in current row: */
             for j = k + 1 ... n:
                 A[i, j] := A[i, j] - A[h, j] * f
         /* Increase pivot row and column */
         h := h + 1
         k := k + 1

Este algoritmo difere ligeiramente do discutido anteriormente, por escolher um pivô com o maior valor absoluto . Esse pivô parcial pode ser necessário se, no local do pivô, a entrada da matriz for zero. Em qualquer caso, a escolha do 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 linha e o sistema correspondente pode ser resolvido por substituição reversa .

Veja também

Referências

Trabalhos citados

links externos