stringtranslate.com

Eliminación gaussiana

Animación de eliminación gaussiana. La fila roja elimina las filas siguientes, las filas verdes cambian su orden.

En matemáticas, la eliminación gaussiana , también conocida como reducción por filas , es un algoritmo para resolver sistemas de ecuaciones lineales . Consiste en una secuencia de operaciones por filas realizadas sobre la matriz de coeficientes correspondiente. Este método también se puede utilizar para calcular el rango de una matriz, el determinante de una matriz cuadrada y la inversa de una matriz invertible . El método recibe su nombre de Carl Friedrich Gauss (1777-1855). Para realizar la reducción por filas en una matriz, se utiliza una secuencia de operaciones elementales por filas para modificar la matriz hasta que la esquina inferior izquierda de la matriz se llene con ceros, tanto como sea posible. Hay tres tipos de operaciones elementales por filas:

Usando estas operaciones, una matriz siempre puede transformarse en una matriz triangular superior , y de hecho una que está en forma escalonada por filas . Una vez que todos los coeficientes principales (la entrada distinta de cero más a la izquierda en cada fila) son 1, y cada columna que contiene un coeficiente principal tiene ceros en el resto, se dice que la matriz está en forma escalonada por filas reducida . Esta forma final es única; en otras palabras, es independiente de la secuencia de operaciones por filas utilizada. Por ejemplo, en la siguiente secuencia de operaciones por filas (donde se realizan dos operaciones elementales en diferentes filas en el primer y tercer paso), la tercera y cuarta matrices son las que están en forma escalonada por filas, y la matriz final es la única forma escalonada por filas reducida.

El uso de operaciones de fila para convertir una matriz en una forma escalonada de fila reducida a veces se denominaEliminación de Gauss-Jordan . En este caso, el términoeliminación gaussianase refiere al proceso hasta que alcanza su forma triangular superior o escalonada por filas (sin reducir). Por razones computacionales, al resolver sistemas de ecuaciones lineales, a veces es preferible detener las operaciones por filas antes de que la matriz se reduzca por completo.

Definiciones y ejemplos de algoritmo

El proceso de reducción por filas hace uso de operaciones elementales por filas y se puede dividir en dos partes. La primera parte (a veces llamada eliminación hacia adelante) reduce un sistema dado a la forma escalonada por filas, a partir de la cual se puede saber si no hay soluciones, si hay una solución única o si hay infinitas soluciones. La segunda parte (a veces llamada sustitución hacia atrás ) continúa usando operaciones por filas hasta que se encuentra la solución; en otras palabras, pone la matriz en forma escalonada por filas reducida.

Otro punto de vista, que resulta muy útil para analizar el algoritmo, es que la reducción por filas produce una descomposición matricial de la matriz original. Las operaciones elementales por filas pueden verse como la multiplicación a la izquierda de la matriz original por matrices elementales . Alternativamente, una secuencia de operaciones elementales que reduce una sola fila puede verse como la multiplicación por una matriz de Frobenius . Entonces, la primera parte del algoritmo calcula una descomposición LU , mientras que la segunda parte escribe la matriz original como el producto de una matriz invertible determinada de forma única y una matriz escalonada reducida determinada de forma única.

Operaciones de fila

Hay tres tipos de operaciones de fila elementales que se pueden realizar en las filas de una matriz:

  1. Intercambiando dos filas.
  2. Multiplicar una fila por un escalar distinto de cero .
  3. Agregar un múltiplo escalar de una fila a otra.

Si la matriz está asociada a un sistema de ecuaciones lineales, estas operaciones no modifican el conjunto de soluciones. Por lo tanto, si el objetivo es resolver un sistema de ecuaciones lineales, el uso de estas operaciones por filas podría facilitar el problema.

Forma escalonada

Para cada fila de una matriz, si la fila no consta solo de ceros, entonces la entrada distinta de cero más a la izquierda se denomina coeficiente principal (o pivote ) de esa fila. Por lo tanto, si dos coeficientes principales están en la misma columna, se podría utilizar una operación de fila del tipo 3 para hacer que uno de esos coeficientes sea cero. Luego, utilizando la operación de intercambio de filas, siempre se pueden ordenar las filas de modo que, para cada fila distinta de cero, el coeficiente principal esté a la derecha del coeficiente principal de la fila superior. Si este es el caso, se dice que la matriz está en forma escalonada por filas. Por lo tanto, la parte inferior izquierda de la matriz contiene solo ceros, y todas las filas cero están debajo de las filas distintas de cero. La palabra "escalonado" se utiliza aquí porque se puede pensar aproximadamente en las filas clasificadas por su tamaño, con la más grande en la parte superior y la más pequeña en la parte inferior.

Por ejemplo, la siguiente matriz está en forma escalonada y sus coeficientes principales se muestran en rojo:

Tiene forma escalonada porque la fila cero está en la parte inferior y el coeficiente principal de la segunda fila (en la tercera columna) está a la derecha del coeficiente principal de la primera fila (en la segunda columna).

Se dice que una matriz está en forma escalonada reducida si, además, todos los coeficientes principales son iguales a 1 (lo que se puede lograr utilizando la operación de fila elemental de tipo 2) y, en cada columna que contiene un coeficiente principal, todas las demás entradas en esa columna son cero (lo que se puede lograr utilizando operaciones de fila elementales de tipo 3).

Ejemplo del algoritmo

Supongamos que el objetivo es encontrar y describir el conjunto de soluciones del siguiente sistema de ecuaciones lineales:

La tabla siguiente muestra el proceso de reducción de filas aplicado simultáneamente al sistema de ecuaciones y su matriz aumentada asociada . En la práctica, no se suele tratar los sistemas en términos de ecuaciones, sino que se hace uso de la matriz aumentada, que es más adecuada para manipulaciones informáticas. El procedimiento de reducción de filas se puede resumir de la siguiente manera: eliminar x de todas las ecuaciones por debajo de L 1 y luego eliminar y de todas las ecuaciones por debajo de L 2. Esto pondrá el sistema en forma triangular . Luego, utilizando la sustitución hacia atrás, se puede resolver cada incógnita.

La segunda columna describe qué operaciones de fila se acaban de realizar. Por lo tanto, para el primer paso, se elimina la x de L 2 agregando 3/2L 1 a L 2 . A continuación, x se elimina de L 3 sumando L 1 a L 3 . Estas operaciones de fila están etiquetadas en la tabla como

Una vez que se elimina y de la tercera fila, el resultado es un sistema de ecuaciones lineales en forma triangular, y así se completa la primera parte del algoritmo. Desde un punto de vista computacional, es más rápido resolver las variables en orden inverso, un proceso conocido como sustitución hacia atrás. Se ve que la solución es z = −1 , y = 3 y x = 2. Por lo tanto, existe una solución única para el sistema de ecuaciones original.

En lugar de detenerse una vez que la matriz está en forma escalonada, se podría continuar hasta que la matriz esté en forma escalonada reducida por filas, como se hace en la tabla. El proceso de reducción por filas hasta que la matriz se reduce a veces se denomina eliminación de Gauss-Jordan, para distinguirlo de detenerse después de alcanzar la forma escalonada.

Historia

El método de eliminación gaussiana aparece –aunque sin prueba– en el texto matemático chino Capítulo ocho: matrices rectangulares de Los nueve capítulos sobre el arte matemático . Su uso se ilustra en dieciocho problemas, con dos a cinco ecuaciones. La primera referencia al libro con este título data del año 179 d. C., pero partes del mismo fueron escritas aproximadamente en el año 150 a. C. [1] [2] [3] Fue comentado por Liu Hui en el siglo III.

El método en Europa proviene de las notas de Isaac Newton . [4] [5] En 1670, escribió que todos los libros de álgebra que conocía carecían de una lección para resolver ecuaciones simultáneas, que Newton luego proporcionó. La Universidad de Cambridge finalmente publicó las notas como Arithmetica Universalis en 1707, mucho después de que Newton hubiera dejado la vida académica. Las notas fueron ampliamente imitadas, lo que hizo que (lo que ahora se llama) eliminación gaussiana fuera una lección estándar en los libros de texto de álgebra a fines del siglo XVIII. Carl Friedrich Gauss en 1810 ideó una notación para la eliminación simétrica que fue adoptada en el siglo XIX por las computadoras manuales profesionales para resolver las ecuaciones normales de los problemas de mínimos cuadrados. [6] El algoritmo que se enseña en la escuela secundaria recibió el nombre de Gauss solo en la década de 1950 como resultado de la confusión sobre la historia del tema. [7]

Algunos autores utilizan el término eliminación gaussiana para referirse únicamente al procedimiento hasta que la matriz está en forma escalonada, y utilizan el término eliminación de Gauss-Jordan para referirse al procedimiento que termina en forma escalonada reducida. El nombre se utiliza porque es una variación de la eliminación gaussiana descrita por Wilhelm Jordan en 1888. Sin embargo, el método también aparece en un artículo de Clasen publicado el mismo año. Jordan y Clasen probablemente descubrieron la eliminación de Gauss-Jordan de forma independiente. [8]

Aplicaciones

Históricamente, la primera aplicación del método de reducción de filas es para resolver sistemas de ecuaciones lineales. A continuación se presentan otras aplicaciones importantes del algoritmo.

Cálculo de determinantes

Para explicar cómo la eliminación gaussiana permite el cálculo del determinante de una matriz cuadrada, debemos recordar cómo las operaciones elementales de fila cambian el determinante:

Si la eliminación gaussiana aplicada a una matriz cuadrada A produce una matriz escalonada por filas B , sea d el producto de los escalares por los que se ha multiplicado el determinante, utilizando las reglas anteriores. Entonces el determinante de A es el cociente por d del producto de los elementos de la diagonal de B :

Computacionalmente, para una matriz n × n , este método necesita solo O( n 3 ) operaciones aritméticas, mientras que usar la fórmula de Leibniz para determinantes requiere operaciones (número de sumandos en la fórmula multiplicado por el número de multiplicaciones en cada sumando) , y la expansión recursiva de Laplace requiere O( n 2 n ) operaciones si los subdeterminantes se memorizan para ser calculados solo una vez (número de operaciones en una combinación lineal multiplicado por el número de subdeterminantes a calcular, que están determinados por sus columnas) . Incluso en las computadoras más rápidas, estos dos métodos son poco prácticos o casi impracticables para n por encima de 20.

Encontrar la inversa de una matriz

Una variante de la eliminación gaussiana llamada eliminación de Gauss-Jordan se puede utilizar para encontrar la inversa de una matriz, si existe. Si A es una matriz cuadrada n × n , entonces se puede utilizar la reducción por filas para calcular su matriz inversa , si existe. Primero, la matriz identidad n × n se aumenta a la derecha de A , formando una matriz de bloques n × 2 n [ A | I ] . Ahora, mediante la aplicación de operaciones elementales por filas, encuentre la forma escalonada reducida de esta matriz n × 2 n . La matriz A es invertible si y solo si el bloque izquierdo se puede reducir a la matriz identidad I ; en este caso, el bloque derecho de la matriz final es A −1 . Si el algoritmo no puede reducir el bloque izquierdo a I , entonces A no es invertible.

Por ejemplo, considere la siguiente matriz:

Para encontrar la inversa de esta matriz, se toma la siguiente matriz aumentada por la identidad y se reduce por filas como una matriz de 3 × 6:

Al realizar operaciones de fila, se puede verificar que la forma escalonada de fila reducida de esta matriz aumentada es

Podemos pensar en cada operación de fila como el producto de la izquierda por una matriz elemental . Denotando por B el producto de estas matrices elementales, mostramos, a la izquierda, que BA = I y, por lo tanto, B = A −1 . A la derecha, mantuvimos un registro de BI = B , que sabemos que es la inversa deseada. Este procedimiento para encontrar la inversa funciona para matrices cuadradas de cualquier tamaño.

Cálculo de rangos y bases

El algoritmo de eliminación gaussiana se puede aplicar a cualquier matriz m × n A . De esta manera, por ejemplo, algunas matrices de 6 × 9 se pueden transformar en una matriz que tiene una forma escalonada por filas como donde las estrellas son entradas arbitrarias y a , b , c , d , e son entradas distintas de cero. Esta matriz escalonada T contiene una gran cantidad de información sobre A : el rango de A es 5, ya que hay 5 filas distintas de cero en T ; el espacio vectorial abarcado por las columnas de A tiene una base que consiste en sus columnas 1, 3, 4, 7 y 9 (las columnas con a , b , c , d , e en T ), y las estrellas muestran cómo las otras columnas de A se pueden escribir como combinaciones lineales de las columnas de la base.

Todo esto se aplica también a la forma escalonada reducida, que es un formato escalonado particular.

Eficiencia computacional

El número de operaciones aritméticas necesarias para realizar la reducción de filas es una forma de medir la eficiencia computacional del algoritmo. Por ejemplo, para resolver un sistema de n ecuaciones para n incógnitas realizando operaciones de filas en la matriz hasta que esté en forma escalonada y luego resolviendo cada incógnita en orden inverso, se requieren n ( n + 1)/2 divisiones, (2 n 3 + 3 n 2 − 5 n )/6 multiplicaciones y (2 n 3 + 3 n 2 − 5 n )/6 restas, [9] para un total de aproximadamente 2 n 3 /3 operaciones. Por lo tanto, tiene una complejidad aritmética ( complejidad temporal , donde cada operación aritmética toma una unidad de tiempo, independientemente del tamaño de las entradas) de O( n 3 ) .

Esta complejidad es una buena medida del tiempo necesario para todo el cálculo cuando el tiempo para cada operación aritmética es aproximadamente constante. Este es el caso cuando los coeficientes están representados por números de punto flotante o cuando pertenecen a un cuerpo finito . Si los coeficientes son números enteros o racionales representados exactamente, las entradas intermedias pueden crecer exponencialmente, por lo que la complejidad de bits es exponencial. [10] Sin embargo, el algoritmo de Bareiss es una variante de la eliminación gaussiana que evita este crecimiento exponencial de las entradas intermedias; con la misma complejidad aritmética de O( n 3 ) , tiene una complejidad de bits de O( n 5 ) , y tiene por lo tanto una complejidad de tiempo fuertemente polinómica .

La eliminación gaussiana y sus variantes se pueden utilizar en sistemas informáticos con miles de ecuaciones e incógnitas. Sin embargo, el coste resulta prohibitivo para sistemas con millones de ecuaciones. Estos grandes sistemas se resuelven generalmente mediante métodos iterativos . Existen métodos específicos para sistemas cuyos coeficientes siguen un patrón regular (véase sistema de ecuaciones lineales ).

Algoritmo de Bareiss

El primer algoritmo de tiempo fuertemente polinomial para la eliminación gaussiana fue publicado por Jack Edmonds en 1967. [11] : 37  Independientemente, y casi simultáneamente, Erwin Bareiss descubrió otro algoritmo, basado en la siguiente observación, que se aplica a una variante sin división de la eliminación gaussiana.

En la eliminación gaussiana estándar, se resta de cada fila debajo de la fila pivote un múltiplo de por donde y son las entradas en la columna pivote de y respectivamente.

La variante de Bareiss consiste, en cambio, en reemplazar con Esto produce una forma escalonada de filas que tiene las mismas entradas cero que con la eliminación gaussiana estándar.

La observación principal de Bareiss es que cada entrada de matriz generada por esta variante es el determinante de una submatriz de la matriz original.

En particular, si se empieza con entradas enteras, las divisiones que se producen en el algoritmo son divisiones exactas que dan como resultado números enteros. Por lo tanto, todas las entradas intermedias y finales son números enteros. Además, la desigualdad de Hadamard proporciona un límite superior para los valores absolutos de las entradas intermedias y finales y, por lo tanto, un poco de complejidad en el uso de la notación O blanda .

Además, como se conoce un límite superior para el tamaño de las entradas finales, se puede obtener una complejidad con un cálculo modular seguido por el resto chino o el levantamiento de Hensel .

Como corolario, los siguientes problemas se pueden resolver en tiempo fuertemente polinomial con la misma complejidad de bits: [11] : 40 

Inestabilidad numérica

Un posible problema es la inestabilidad numérica , causada por la posibilidad de dividir por números muy pequeños. Si, por ejemplo, el coeficiente principal de una de las filas es muy cercano a cero, entonces para reducir por filas la matriz, uno necesitaría dividir por ese número. Esto significa que cualquier error que existiera para el número que estaba cerca de cero se amplificaría. La eliminación gaussiana es numéricamente estable para matrices diagonalmente dominantes o definidas positivas . Para matrices generales, la eliminación gaussiana generalmente se considera estable, cuando se usa pivoteo parcial , aunque hay ejemplos de matrices estables para las que es inestable. [12]

Generalizaciones

La eliminación gaussiana se puede realizar sobre cualquier campo , no sólo sobre los números reales.

El algoritmo de Buchberger es una generalización de la eliminación gaussiana a sistemas de ecuaciones polinómicas . Esta generalización depende en gran medida de la noción de orden monomial . La elección de un orden de las variables ya está implícita en la eliminación gaussiana, manifestándose como la elección de trabajar de izquierda a derecha al seleccionar las posiciones de pivote.

Calcular el rango de un tensor de orden mayor que 2 es NP-difícil . [13] Por lo tanto, si P ≠ NP , no puede haber un análogo de tiempo polinomial de la eliminación gaussiana para tensores de orden superior (las matrices son representaciones de matrices de tensores de orden 2).

Pseudocódigo

Como se explicó anteriormente, la eliminación gaussiana transforma una matriz A m × n dada en una matriz en forma escalonada .

En el siguiente pseudocódigo , A[i, j]denota la entrada de la matriz A en la fila i y columna j con los índices comenzando desde 1. La transformación se realiza en el lugar , lo que significa que la matriz original se pierde para ser eventualmente reemplazada por su forma escalonada por filas.

h := 1 /* Inicialización de la fila pivote */k := 1 /* Inicialización de la columna pivote */mientras h ≤ m y k ≤ n /* Encuentra el pivote k-ésimo: */ i_max := argmax (i = h ... m, abs(A[i, k])) si A[i_max, k] = 0 /* No hay pivote en esta columna, pasar a la siguiente columna */ k := k + 1 De lo contrario,  intercambiar filas (h, i_max) /* Hacer para todas las filas debajo del pivote: */ para i = h + 1 ... m: f := A[i, k] / A[h, k] /* Rellenar con ceros la parte inferior de la columna pivote: */ A[i, k] := 0 /* Hacer para todos los elementos restantes en la fila actual: */ para j = k + 1 ... n: A[i, j] := A[i, j] - A[h, j] * f /* Aumentar fila y columna de pivote */ h := h + 1 k := k + 1

Este algoritmo difiere ligeramente del que se analizó anteriormente, ya que se elige un pivote con el mayor valor absoluto . Este pivote parcial puede ser necesario si, en el lugar del pivote, la entrada de la matriz es cero. En cualquier caso, la elección del mayor valor absoluto posible del pivote mejora la estabilidad numérica del algoritmo, cuando se utiliza el punto flotante para representar números. [14]

Al finalizar este procedimiento, la matriz estará en forma escalonada y el sistema correspondiente podrá resolverse mediante sustitución hacia atrás.

Véase también

Referencias

  1. ^ "DOCUMENTA MATHEMATICA, Vol. Extra Volume: Optimization Stories (2012), 9-14". www.emis.de . Consultado el 2 de diciembre de 2022 .
  2. ^ Calinger 1999, págs. 234-236
  3. ^ Timothy Gowers; June Barrow-Green; Imre Leader (8 de septiembre de 2008). The Princeton Companion to Mathematics. Princeton University Press. pág. 607. ISBN 978-0-691-11880-2.
  4. ^ Grcar 2011a, págs. 169-172
  5. ^ Grcar 2011b, págs. 783–785
  6. ^ Lauritzen, pág. 3
  7. ^ Grcar 2011b, pág. 789
  8. ^ Althoen, Steven C.; McLaughlin, Renate (1987), "Reducción de Gauss-Jordan: una breve historia", The American Mathematical Monthly , 94 (2), Asociación Matemática de América: 130–142, doi : 10.2307/2322413, ISSN  0002-9890, JSTOR  2322413
  9. ^ Farebrother 1988, pág. 12
  10. ^ Fang, Xin Gui; Havas, George (1997). "Sobre la complejidad del peor caso de la eliminación gaussiana de enteros". Actas del simposio internacional de 1997 sobre computación simbólica y algebraica . ISSAC '97. Kihei, Maui, Hawái, Estados Unidos: ACM. págs. 28–31. doi :10.1145/258726.258740. ISBN . 0-89791-875-4.
  11. ^ ab Grötschel, Martín ; Lovász, László ; Schrijver, Alexander (1993), Algoritmos geométricos y optimización combinatoria, Algoritmos y combinatoria, vol. 2 (2ª ed.), Springer-Verlag, Berlín, doi :10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, Sr.  1261419
  12. ^ Préstamo Golub y Van 1996, §3.4.6
  13. ^ Hillar, Christopher; Lim, Lek-Heng (7 de noviembre de 2009). "La mayoría de los problemas tensoriales son NP-hard". arXiv : 0911.1393 [cs.CC].
  14. ^ Kurgalin, Sergei; Borzunov, Sergei (2021). "Álgebra y geometría con Python". SpringerLink . doi :10.1007/978-3-030-61541-3.

Obras citadas

Enlaces externos