Triangulación de matriz

Triangulación de matriz con los métodos de Gauss y Bareiss

Aquí abajo están las dos calculadoras para la triangulación de matriz.
La primera utiliza el método de Gauss, la segunda el método Bareiss. A continuación se realiza una descripción de los métodos y la teoría.

PLANETCALC, Triangulación de matriz (método de Gauss)

Triangulación de matriz (método de Gauss)

Dígitos después del punto decimal: 4
Matriz triangular (método de Gauss)
 
Matriz triangular (método de Gauss con selección máxima en una columna):
 
Matriz triangular (método de Gauss con una elección máxima en toda la matriz):
 



PLANETCALC, Triangulación de matriz (método Bareiss)

Triangulación de matriz (método Bareiss)

Dígitos después del punto decimal: 4
Matriz triangular (método Bareiss)
 
Matriz triangular (método Bareiss con selección máxima en una columna)
 
Matriz triangular (método Bareiss con una elección máxima en toda la matriz)
 



Así que primero daremos la noción de una matriz triangular o escalonada por filas.
La matriz es escalonada por filas si:

  1. Todas las filas cero, si las hay, pertenecen a la parte inferior de la matriz
  2. El primer coeficiente (el primer número no cero de la izquierda, también llamado pivote) de una fila no cero está siempre estrictamente a la derecha del primer coeficiente de la fila de arriba.
  3. Todas las filas que no son cero (filas con al menos un elemento no cero) están por encima de cualquier fila de todos los ceros

Ejemplo de matriz escalonada por filas:
1 0 2 5
0 3 0 0
0 0 0 4
La noción de matriz triangular es más estrecha y se utiliza sólo para matrices cuadradas. Es así: la matriz triangular es una matriz cuadrada donde todos los elementos debajo de la diagonal principal son cero. En realidad se llama matriz triangular superior, pero usaremos el término ya dado. Es obvio que la matriz triangular superior es también una matriz escalonada por filas.

Ejemplo de matriz triangular superior:
1 0 2 5
0 3 1 3
0 0 4 2
0 0 0 3
Por cierto, el determinante de una matriz triangular se calcula simplemente multiplicando todos sus elementos diagonales.

Usted puede preguntarse, ¿por qué son tan interesantes estas matrices escalonadas por filas (y triangulares), que todas las demás ocupan un rol secundario?
Tienen una propiedad asombrosa, ya que cualquier matriz rectangular puede ser reducida a una matriz escalonada por filas con las transformaciones elementales.

Usted puede preguntarse, ¿cuáles son las transformaciones elementales?
Las transformaciones elementales de la matriz son las siguientes operaciones:

  1. Cambio de fila (una fila dentro de la matriz puede ser cambiada por otra fila).
  2. Multiplicación de filas (Cada elemento de una fila puede ser multiplicado por una constante distinta de cero).
  3. Suma de filas (Una fila puede ser reemplazada por la suma de esa fila y un múltiplo de otra fila).

¿Y ahora qué?
Las transformaciones de matrices elementales conservan la equivalencia de las matrices. Y si recuerda que los sistemas de ecuaciones algebraicas lineales se escriben sólo en forma matricial, significa que las transformaciones matriciales elementales no cambian el conjunto de soluciones del sistema de ecuaciones algebraicas lineales que esta matriz representa.

Al triangular la matriz de ecuaciones lineales AX=B a A'X = B', es decir, con la correspondiente transformación de la columna B, se puede hacer lo que se llama "sustitución hacia atrás".

Para ser claros, usaremos la matriz triangular de arriba y reescribiremos el sistema de ecuaciones a una forma más común (he hecho la columna 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

Está claro que primero encontraremos x_4, luego lo sustituimos por la ecuación anterior, encontramos x_3 y así sucesivamente, pasando de la última ecuación a la primera. Eso es lo que se llama sustitución hacia atrás.
Este algoritmo de reducción de filas se llama método de Gauss. El método de Gauss es un método clásico para resolver sistemas de ecuaciones lineales. También se denomina eliminación de Gauss, ya que es un método de eliminación sucesiva de variables cuando los sistemas de ecuaciones se reducen a una forma escalonada por filas (o triangular), en la que se colocan todas las demás variables (empezando por la última) con la ayuda de transformaciones elementales.

Ahora unas palabras sobre este método.
¿Cómo puede quedar en cero la variable x_1 en la segunda ecuación?
Restando la primera de ella, multiplicada por un factor \frac{a_{21}}{a_{11}}
He aquí un ejemplo:

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

Cero x_1 en la primera ecuación

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

No hay x_1 en la segunda ecuación
En sentido general, el método de Gauss se puede representar de la siguiente manera:

 \begin{matrix}For\, j = 0,..., N-2 \\ \qquad \qquad For\,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}

donde N - dimensión de la fila,

\vec{a_i} - fila i,
a_{ij} - elemento en la fila i, columna j

Parece un gran método, pero hay algo a tener en cuenta. Es la división por a_{jj} que ocurre en la fórmula. Primero, si el elemento diagonal es igual a cero, este método no funcionará. Segundo, durante el cálculo la desviación aumentará y cuanto más aumente, más complicado será dicho cálculo. Así que el resultado no será preciso.
Para la reducción de la desviación, se utilizan las modificaciones del método de Gauss. Se basan en el hecho de que cuanto mayor sea el denominador, menor será la desviación. Estas modificaciones son el método de Gauss con selección máxima en una columna y el método de Gauss con selección máxima en toda la matriz. Como su nombre lo indica, ante cada tallo de exclusión de una variable se busca el elemento de máximo valor en una fila (toda la matriz) y se realiza la permutación de filas, por lo que se cambiará de lugar con a_{jj}.

Pero hay una modificación radical del método de Gauss - el método Bareiss.
¿Cómo puede deshacerse de la división? Multiplicando la fila \vec{a_i} por a_{jj} antes de restar. Entonces tiene que restar \vec{a_i}, multiplicado por a_{ij} sin ninguna división.
 \vec{a_i} \leftarrow a_{jj}\vec{a_i} - a_{ij} \vec{a_j} .
Parece bueno, pero hay un problema de aumento del valor del elemento durante los cálculos.

Bareiss ofreció dividir la expresión anterior por a_{j-1,j-1} y mostró que si los elementos iniciales de la matriz son los números enteros, entonces el número resultante será entero. También se supone lo mismo para la fila cero a_{-1,-1}=1.

Por cierto, el hecho de que el algoritmo Bareiss reduce los elementos integrales de la matriz inicial a una matriz triangular con elementos integrales, es decir, sin acumulación de desviaciones, es una característica bastante importante desde el punto de vista de la aritmética de la máquina.

El algoritmo Bareiss puede ser representado como:
 \begin{matrix} a_{-1,-1}=1 \\For\, j = 0,..., N-2 \\ \qquad \qquad For\,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 puede actualizarse, de forma similar a Gauss, con selección máxima en una columna (toda la matriz) y reordenación de las filas correspondientes (filas y columnas).

Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Triangulación de matriz

Comentarios