Calculadoras de triangulação matricial
Triangulação de matriz usando métodos de Gauss e Bareiss.
A seguir estão duas calculadoras para triangulação de matrizes.
A primeira usa o método de Gauss, a segunda o método de Bareiss. Uma descrição de seus métodos e teorias estão abaixo.
Primeiramente, daremos uma noção de uma matriz escalonada triangular ou linear:
A matriz possui uma forma escalonada de linha se:
- todas as linhas zero, se houver, pertencem à parte inferior da matriz
- O coeficiente líder (o primeiro número diferente de zero da esquerda, também chamado de pivô) de uma linha diferente de zero está sempre estritamente à direita do coeficiente líder da linha acima dele
- Todas as linhas diferentes de zero (linhas com pelo menos um elemento diferente de zero) estão acima de quaisquer linhas de todos os zeros
Exemplo de matriz escalonada de linha:
1 0 2 5
0 3 0 0
0 0 0 4
A noção de matriz triangular é mais estreita e é usada somente para matrizes quadradas. Funciona da seguinte maneira: a matriz triangular é uma matriz quadrada onde todos os elementos abaixo da diagonal principal são zero.
Exemplo de uma matriz triangular superior:
1 0 2 5
0 3 1 3
0 0 4 2
0 0 0 3
A propósito, o determinante de uma matriz triangular é calculado simplesmente através da multiplicação de todos os seus elementos diagonais.
Você pode perguntar o que há de tão interessante nessas matrizes escalonadas (e triangulares) de linha? Bem, elas têm uma propriedade incrível - qualquer matriz retangular pode ser reduzida a uma matriz escalonada de linha com as transformações elementares.
Então, você pode perguntar, quais são as transformações elementares?
As transformações elementares de matriz são as seguintes operações:
- Troca de linha (uma linha dentro da matriz pode ser trocada por outra linha)
- Multiplicação de linha (cada elemento em uma linha pode ser multiplicado por uma constante diferente de zero)
- Adição de linha (uma linha pode ser substituída pela soma dessa linha e um múltiplo de outra linha)
E agora?
As transformações elementares de matriz retêm a equivalência de matrizes. E, se você lembrar que os sistemas de equações algébricas lineares são escritos somente na forma de matriz, isso significa que as transformações elementares da matriz não mudam o conjunto de soluções do sistema de equações algébricas lineares que esta matriz representa.
Ao triangular a matriz de equação linear AX=B para A'X = B', ou seja, com a transformação da coluna correspondente a B, você pode fazer a chamada "substituição reversa".
Para explicar, iremos usar a matriz triangular acima e reescrever o sistema de equações de uma forma mais comum (criei a coluna B):
É claro que primeiro encontraremos , em seguida, substituímos pela equação anterior, encontramos
e assim por diante - movendo da última equação para a primeira. Isso é chamado de substituição reversa.
Esse algoritmo de redução de linha é conhecido como método de Gauss. O método de Gauss é um método clássico para resolver sistemas de equações lineares. Ele também é chamado de eliminação de Gauss, pois é um método de eliminação sucessiva de variáveis, quando com a ajuda de transformações elementares os sistemas de equações são reduzidos a uma forma escalonada (ou triangular) de linha, na qual todas as outras variáveis são posicionadas (a partir do último).
Agora, algumas reflexões sobre este método.
Como você pode zerar a variável na segunda equação?
Subtraindo o primeiro dele, multiplicado por um fator
Aqui está um exemplo:
Zero na primeira equação
Não existe na segunda equação
De maneira generalizada, o método de Gauss pode ser representado da seguinte forma:
onde N – dimensão da linha,
- linha-i,
- elemento na linha i, coluna j
Parece ser um ótimo método, porém, há uma coisa – sua divisão por ocorrendo na fórmula. Em primeiro lugar, se um elemento da diagonal for igual a zero, este método não irá funcionar. Em segundo lugar, durante o cálculo, o desvio aumentará e quanto mais longe, maior. Portanto, o resultado não será preciso.
Para a redução do desvio, são utilizadas as modificações do método de Gauss. Elas se baseiam no fato de que quanto maior o denominador, menor o desvio. Essas modificações são o método de Gauss com seleção máxima em uma coluna e o método de Gauss com escolha máxima em toda a matriz. Como o nome indica, antes de cada radical de exclusão de variável, o elemento com valor máximo é procurado em uma linha (matriz inteira) e a permutação de linha é realizada, então ela trocará de lugar com .
Entretanto, há uma modificação radical do método de Gauss - o método de Bareiss.
Como você pode se livrar da divisão? Através da multiplicação da linha by
antes da subtração. Então você tem que subtrair
, multiplicado por
sem qualquer divisão.
.
Parece bom, mas há um problema de aumento do valor do elemento durante os cálculos
Bareiss propôs dividir a expressão acima por e mostrou que onde os elementos iniciais da matriz são os números inteiros, então o número resultante será inteiro. Também é assumido que para a linha zero
.
A propósito, o fato de o algoritmo de Bareiss reduzir elementos integrais da matriz inicial a uma matriz triangular com elementos integrais, ou seja, sem acumulação de desvio, é uma característica muito importante do ponto de vista da aritmética de máquina.
O algoritmo de Bareiss pode ser representado como:
Este algoritmo pode ser atualizado, similarmente a forma que Gauss, com seleção máxima em uma coluna (matriz inteira) e rearranjo das linhas correspondentes (linhas e colunas).
Comentários