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.

PLANETCALC, Triangulação de matriz (método de Gauss)

Triangulação de matriz (método de Gauss)

Dígitos após o ponto decimal: 4
Matriz triangular (método de Gauss)
 
Matriz triangular (método de Gauss com seleção máxima em uma coluna)
 
Matriz triangular (método de Gauss com escolha máxima na matriz inteira):
 



PLANETCALC, Triangulação de matriz (método de Bareiss)

Triangulação de matriz (método de Bareiss)

Dígitos após o ponto decimal: 4
Matriz triangular (método de Bareiss)
 
Matriz triangular (método de Bareiss com seleção máxima em uma coluna)
 
Matriz triangular (método de Bareiss com escolha máxima na matriz inteira)
 



Primeiramente, daremos uma noção de uma matriz escalonada triangular ou linear:
A matriz possui uma forma escalonada de linha se:

  1. todas as linhas zero, se houver, pertencem à parte inferior da matriz
  2. 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
  3. 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:

  1. Troca de linha (uma linha dentro da matriz pode ser trocada por outra linha)
  2. Multiplicação de linha (cada elemento em uma linha pode ser multiplicado por uma constante diferente de zero)
  3. 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):

1*x_1 + 0*x_2 + 2 * x_3 + 5 * x_4 = 10 \\ 0*x_1 + 3*x_2 + 1 * x_3 + 3 * x_4 = 7 \\ 0*x_1 + 0*x_2 + 4 * x_3 + 2 * x_4 = 5 \\ 0*x_1 + 0*x_2 + 0 * x_3 + 3 * x_4 = 9

É claro que primeiro encontraremos x_4, em seguida, substituímos pela equação anterior, encontramos x_3 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 x_1 na segunda equação?
Subtraindo o primeiro dele, multiplicado por um fator \frac{a_{21}}{a_{11}}
Aqui está um exemplo:

2*x_1 + 3*x_2 + 4 * x_3 = 10 \\ 6*x_1 + 3*x_2 - 4 * x_3 = 7

Zero x_1 na primeira equação

6*x_1 + 3*x_2 - 4 * x_3 - \frac{6}{2}(2*x_1 + 3*x_2 + 4 * x_3)= 7 - \frac{6}{2}10 \\ 6*x_1 + 3*x_2 - 4 * x_3 - 6*x_1 - 9*x_2 - 12 * x_3 = 7 - 30 \\ -6*x_2 - 16 * x_3 = -23

Não existe x_1 na segunda equação
De maneira generalizada, o método de Gauss pode ser representado da seguinte forma:

 \begin{matrix}Para\, j = 0,..., N-2 \\ \qquad \qquad Para\,i = j + 1,..., N - 1 \\ \qquad \qquad \qquad \vec{a_i} \leftarrow \vec{a_i} - \frac{a_{ij}}{a_{jj}} \vec{a_j} \end{matrix}

onde N – dimensão da linha,

\vec{a_i} - linha-i,
a_{ij} - elemento na linha i, coluna j

Parece ser um ótimo método, porém, há uma coisa – sua divisão por a_{jj} 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 a_{jj}.

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 \vec{a_i} by a_{jj} antes da subtração. Então você tem que subtrair \vec{a_i}, multiplicado por a_{ij} sem qualquer divisão.
 \vec{a_i} \leftarrow a_{jj}\vec{a_i} - a_{ij} \vec{a_j} .
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 a_{j-1,j-1} 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_{-1,-1}=1.

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:
 \begin{matrix} a_{-1,-1}=1 \\Para\, j = 0,..., N-2 \\ \qquad \qquad Para\,i = j + 1,..., N - 1 \\ \qquad \qquad \qquad \vec{a_i} \leftarrow \frac{a_{jj}\vec{a_i} - a_{ij} \vec{a_j}}{a_{j-1,j-1}} \end{matrix}

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

URL copiado para a área de transferência
PLANETCALC, Calculadoras de triangulação matricial

Comentários