eliminación gaussiana

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 aplicadas a 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 una reducción de filas en una matriz, se utiliza una secuencia de operaciones elementales de fila para modificar la matriz hasta que la esquina inferior izquierda de la matriz se llene con ceros, en la medida de lo posible. Existen tres tipos de operaciones elementales de fila:

intercambiando dos filas,
multiplicar una fila por un número distinto de cero, y
agregar un múltiplo de una fila a otra fila.

Mediante estas operaciones, una matriz siempre puede transformarse en una forma escalonada reducida por filas : cada fila no nula se encuentra encima de cada fila nula, cada fila no nula tiene su primer elemento no nulo igual a 1, las columnas que contienen estos primeros 1 tienen todos los demás elementos iguales a 0, y el primer 1 de cada fila no nula se encuentra a la derecha del primer 1 de la fila anterior. Esta forma final es única; es decir, 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 filas diferentes en el primer y tercer paso), la tercera y la cuarta matriz son las que están en forma escalonada por filas, y la matriz final es la única forma escalonada reducida por filas. ${\begin{bmatrix}1&3&1&9\\1&1&-1&1\\3&11&5&35\end{bmatrix}}\to {\begin{bmatrix}1&3&1&9\\0&-2&-2&-8\\0&2&2&8\end{bmatrix}}\to {\begin{bmatrix}1&3&1&9\\0&-2&-2&-8\\0&0&0&0\end{bmatrix}}\to {\begin{bmatrix}1&0&-2&-3\\0&1&1&4\\0&0&0&0\end{bmatrix}}$

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

Definiciones y ejemplo de algoritmo

El proceso de reducción de filas utiliza operaciones elementales de fila y se divide en dos partes. La primera (a veces llamada eliminación hacia adelante) reduce un sistema dado a la forma escalonada de filas, lo que permite determinar si no hay soluciones, si existe una solución única o si existen infinitas soluciones. La segunda parte (a veces llamada sustitución hacia atrás ) continúa utilizando operaciones de fila hasta encontrar la solución; es decir, transforma la matriz a la forma escalonada de filas reducida.

Otro punto de vista, que resulta muy útil para analizar el algoritmo, es que la reducción de filas produce una descomposición matricial de la matriz original. Las operaciones elementales de fila 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 considerarse como una multiplicación por una matriz de Frobenius . 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 de filas también determinada de forma única.

Operaciones en fila

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

Intercambiar dos filas.
Multiplicar una fila por un escalar distinto de cero .
Sumar 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 solución. Por lo tanto, si el objetivo es resolver un sistema de ecuaciones lineales, el uso de estas operaciones de fila podría facilitar el problema.

Forma escalonada

En una matriz, si cada fila no está compuesta únicamente por ceros, el elemento distinto de cero situado más a la izquierda se denomina elemento principal (o pivote ) de esa fila. Si dos elementos principales se encuentran en la misma columna, se puede utilizar una operación de fila de tipo 3 para convertir uno de ellos en cero. Mediante la operación de intercambio de filas, se pueden ordenar las filas de manera que, para cada fila distinta de cero, el elemento principal se encuentre a la derecha del elemento principal de la fila superior. En este caso, se dice que la matriz está en forma escalonada . En esta forma, la parte inferior izquierda de la matriz contiene solo ceros, y todas las filas de ceros se encuentran debajo de las filas distintas de cero. El término "escalonada" se utiliza aquí porque se puede considerar que las filas están ordenadas según su tamaño, con la mayor en la parte superior y la menor en la inferior.

Por ejemplo, la siguiente matriz está en forma escalonada por filas, y sus entradas principales se muestran en rojo: ${\begin{bmatrix}0&\color {red}{\mathbf {2} }&1&-1\\0&0&\color {red}{\mathbf {3} }&1\\0&0&0&0\end{bmatrix}}.$

Está dispuesta en forma escalonada porque la fila cero está en la parte inferior y la primera entrada de la segunda fila (en la tercera columna) está a la derecha de la primera entrada de la primera fila (en la segunda columna).

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

Ejemplo del algoritmo

Supongamos que el objetivo es encontrar y describir el conjunto de soluciones del siguiente sistema de ecuaciones lineales: ${\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\qquad (L_{1})\\-3x&{}-{}&y&{}+{}&2z&{}={}&-11&\qquad (L_{2})\\-2x&{}+{}&y&{}+{}&2z&{}={}&-3&\qquad (L_{3})\end{alignedat}}$

La tabla que se muestra a continuación ilustra el proceso de reducción de filas aplicado simultáneamente al sistema de ecuaciones y a su matriz aumentada asociada . En la práctica, no se suele trabajar con los sistemas en términos de ecuaciones, sino que se utiliza la matriz aumentada, 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$ $L1$ y, a continuación, eliminar $y$ de todas las ecuaciones por debajo de $L2$ $.$ Esto transformará el sistema en una matriz triangular . Posteriormente, mediante sustitución regresiva, se puede resolver cada incógnita.

$La segunda columna describe qué operaciones de$ fila se acaban de realizar. Para el primer paso, $x$ se elimina de $L 2$ sumando $3 / 2 L 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 ${\begin{aligned}L_{2}+{\tfrac {3}{2}}L_{1}&\to L_{2},\\L_{3}+L_{1}&\to L_{3}.\end{aligned}}$

Una vez eliminada también la $variable y de la tercera fila, el resultado es un sistema de ecuaciones lineales en forma triangular, completando así la primera parte del algoritmo. Desde el 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 observa que la solución es$ $z = -1$ , $y = 3$ y $x = 2.$ En particular, en este caso existe una solución única para el sistema de ecuaciones original.

En lugar de detenerse una vez que la matriz está en forma escalonada por filas, se puede continuar hasta que la matriz esté en forma escalonada reducida por filas, como se muestra en la tabla. El proceso de reducción por filas hasta que la matriz se reduce se conoce a veces como 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 demostración— en el capítulo ocho del texto matemático chino « Matrices rectangulares» de «Los nueve capítulos sobre el arte matemático» . Su uso se ilustra en dieciocho problemas, con entre dos y cinco ecuaciones. La primera referencia al libro con este título data del año 179 d. C., pero algunas partes fueron escritas ya alrededor del año 150 a. C. ^{[ 1 ]}^{[ 2 ]}^{[ 3 ]} Fue comentado por Liu Hui en el siglo III.

Según Grcar ^{[ 4 ],} la solución de ecuaciones lineales por eliminación se inventó de forma independiente en varias culturas de Eurasia desde la antigüedad, y en Europa ya se publicaron ejemplos concretos del procedimiento a finales del Renacimiento (en la década de 1550). Es muy posible que ya entonces los matemáticos consideraran el procedimiento elemental y que no necesitara explicación para los profesionales, por lo que quizás nunca conozcamos su historia detallada, salvo que para entonces ya se practicaba en al menos algunos lugares de Europa.

El método en Europa proviene de las notas de Isaac Newton . ^{[ 4 ]}^{[ 5 ]} En 1669-1670, Newton escribió que todos los libros de álgebra que conocía carecían de una lección para resolver ecuaciones simultáneas, la cual él mismo proporcionó. La Universidad de Cambridge finalmente publicó las notas como Arithmetica Universalis en 1707, mucho después de que Newton hubiera abandonado la vida académica. Las notas fueron ampliamente imitadas, lo que convirtió (lo que ahora se llama) eliminación gaussiana en una lección estándar en los libros de texto de álgebra a finales del siglo XVIII. Carl Friedrich Gauss ideó en 1810 una notación para la eliminación simétrica que fue adoptada en el siglo XIX por los computadores manuales profesionales para resolver las ecuaciones normales de problemas de mínimos cuadrados. ^{[ 6 ]} El algoritmo que se enseña en la escuela secundaria recibió el nombre de Gauss recién 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 el término eliminación de Gauss-Jordan para referirse al procedimiento que finaliza 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. Es probable que Jordan y Clasen descubrieran 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 fue 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 calcular el determinante de una matriz cuadrada, debemos recordar cómo las operaciones elementales de fila modifican el determinante:

Intercambiar dos filas multiplica el determinante por −1.
Multiplicar una fila por un escalar distinto de cero multiplica el determinante por el mismo escalar.
Sumar a una fila un múltiplo escalar de otra no cambia 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$ : $\det(A)={\frac {\prod \operatorname {diag} (B)}{d}}.$

Computacionalmente, para una matriz $n \times n , este método solo necesita$ $O(n³)$ operaciones aritméticas, mientras que usar $la$ fórmula de Leibniz para determinantes requiere $(n\,n!)$ operaciones (número de sumandos en la fórmula por el número $de$ multiplicaciones en cada sumando) , y la expansión recursiva de Laplace requiere $O$ $(n²n)$ operaciones si los subdeterminantes se memorizan para ser calculados solo una vez (número de operaciones en una combinación lineal 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$ mayor que 20.

Hallar la inversa de una matriz

Una variante de la eliminación gaussiana, denominada eliminación de Gauss-Jordan, puede utilizarse para hallar la inversa de una matriz, si existe. Si $A$ es una matriz cuadrada $de n \times n$ , se puede utilizar la reducción por filas para calcular su matriz inversa , si existe. Primero, la matriz identidad $de n \times n$ se incrementa a la derecha de $A$ , formando una matriz de bloques $de n$ $\times 2n$ $[$ $A$ $|$ $I$ $]$ $.$ A continuación, mediante la aplicación de operaciones elementales por filas, se halla la forma escalonada reducida de esta matriz de $n$ $\times 2n$ $.$ La matriz $A$ es invertible si y solo si puede reducirse 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: $A={\begin{bmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end{bmatrix}}.$

Para hallar la inversa de esta matriz, se toma la siguiente matriz aumentada con la matriz identidad y se reduce por filas a una matriz de 3 × 6: $[A|I]=\left[{\begin{array}{ccc|ccc}2&-1&0&1&0&0\\-1&2&-1&0&1&0\\0&-1&2&0&0&1\end{array}}\right].$

Al realizar operaciones de fila, se puede comprobar que la forma escalonada reducida de esta matriz aumentada es $\left[{\begin{array}{rrr|rrr}1&0&0&{\frac {3}{4}}&{\frac {1}{2}}&{\frac {1}{4}}\\0&1&0&{\frac {1}{2}}&1&{\frac {1}{2}}\\0&0&1&{\frac {1}{4}}&{\frac {1}{2}}&{\frac {3}{4}}\end{array}}\right]=:[I|B].$

Podemos considerar cada operación de fila como el producto por la izquierda de una matriz elemental . A la derecha, observamos que el producto de estas matrices elementales es $B$ (ya que $B = BI$ ). Mientras tanto, a la izquierda, vemos que al multiplicar por la izquierda el producto de estas matrices por $A$ se obtiene la matriz identidad. En otras palabras, $BA = I.$ Por lo tanto , $B = A -1$ , la inversa deseada. Este procedimiento para hallar 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 $A$ $de m \times n$ . De esta manera, por ejemplo, algunas matrices de 6 × 9 se pueden transformar en una matriz que tenga una forma escalonada por filas como $T={\begin{bmatrix}a&*&*&*&*&*&*&*&*\\0&0&b&*&*&*&*&*&*\\0&0&0&c&*&*&*&*&*\\0&0&0&0&0&0&d&*&*\\0&0&0&0&0&0&0&0&e\\0&0&0&0&0&0&0&0&0\end{bmatrix}},$ 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 generado 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$ pueden escribirse como combinaciones lineales de las columnas de la base.

Todo esto también se aplica al formato de filas escalonadas reducido, que es un formato de filas escalonadas 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 fila en la matriz hasta que esté en forma escalonada, y luego resolviendo para 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 campo finito . Si los coeficientes son enteros o números 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 por lo tanto tiene una complejidad temporal fuertemente polinómica .

La eliminación gaussiana y sus variantes pueden utilizarse en ordenadores para sistemas con miles de ecuaciones e incógnitas. Sin embargo, el coste se vuelve prohibitivo para sistemas con millones de ecuaciones. Estos sistemas de gran tamaño se suelen resolver 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} De forma independiente y casi simultánea, 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. $R_{i}$ debajo de la fila pivote $R_{k}$ un múltiplo de $R_{k}$ por $r_{i,k}/r_{k,k},$ dónde $r_{i,k}$ y $r_{k,k}$ son las entradas en la columna dinámica de $R_{i}$ y $R_{k},$ respectivamente.

La variante de Bareiss consiste, en cambio, en reemplazar $R_{i}$ con ${\textstyle {\frac {r_{k,k}R_{i}-r_{i,k}R_{k}}{r_{k-1,k-1}}}.}$ Esto produce una forma escalonada por filas que tiene las mismas entradas cero que con la eliminación gaussiana estándar.

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

En particular, si se comienza con entradas enteras, las divisiones que ocurren en el algoritmo son divisiones exactas que dan como resultado enteros. Por lo tanto, todas las entradas intermedias y finales son enteras. Además, la desigualdad de Hadamard proporciona una cota superior para los valores absolutos de las entradas intermedias y finales, y por lo tanto una complejidad de bits de ${\tilde {O}}(n^{5}),$ utilizando la notación O suave .

Además, como se conoce un límite superior en el tamaño de las entradas finales, se obtiene una complejidad. ${\tilde {O}}(n^{4})$ se puede obtener con computación modular seguida de resto chino o levantamiento de Hensel .

Como corolario, los siguientes problemas pueden resolverse en tiempo fuertemente polinomial con la misma complejidad de bits: ^{[ 11 ]}^{: 40}

Comprobar si m vectores racionales dados son linealmente independientes.
Cálculo del determinante de una matriz racional
Calcular la solución de un sistema de ecuaciones racionales Ax = b
Cálculo de la matriz inversa de una matriz racional no singular.
Cálculo del rango de una matriz racional

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, para reducir la matriz por filas sería necesario dividir por ese número. Esto significa que cualquier error existente para el número cercano a 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 se considera generalmente estable al usar pivoteo parcial , aunque existen ejemplos de matrices estables para las que es inestable. ^{[ 12 ]}^{[ 13 ]}

Generalizaciones

La eliminación gaussiana se puede realizar sobre cualquier campo , no solo 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 para las variables ya está implícita en la eliminación gaussiana, manifestándose como la decisión de trabajar de izquierda a derecha al seleccionar las posiciones de los pivotes.

Calcular el rango de un tensor de orden mayor que 2 es NP-difícil . ^{[ 14 ]} Por lo tanto, si $P \neq 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 arreglos de tensores de orden 2).

Pseudocódigo

Como se explicó anteriormente, la eliminación gaussiana transforma una matriz $A$ $de m \times n$ dada en una matriz en forma escalonada por filas .

En el siguiente pseudocódigo , A[i, j]denota la entrada de la matriz $A$ en la fila $i$ y la columna $j$ con índices que comienzan desde 1. La transformación se realiza in situ , lo que significa que la matriz original se pierde para ser reemplazada finalmente 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 k-ésimo pivote: */ 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] /* Rellena con ceros la parte inferior de la columna dinámica: */ 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 la fila y la columna del pivote */ h := h + 1 k := k + 1

Este algoritmo difiere ligeramente del descrito anteriormente, ya que elige un pivote con el mayor valor absoluto . Este pivoteo parcial puede ser necesario si, en la posición del pivote, la entrada de la matriz es cero. En cualquier caso, elegir el mayor valor absoluto posible del pivote mejora la estabilidad numérica del algoritmo cuando se utiliza coma flotante para representar los números. ^{[ 15 ]}

Una vez completado este procedimiento, la matriz estará en forma escalonada por filas y el sistema correspondiente podrá resolverse mediante sustitución hacia atrás.

Véase también

Fangcheng (matemáticas)
Proceso de Gram-Schmidt : otro proceso para transformar una matriz en una forma canónica.
Eliminación de Fourier-Motzkin : un algoritmo para eliminar variables de un sistema de desigualdades lineales, en lugar de ecuaciones.

Referencias

↑ "DOCUMENTA MATHEMATICA, Vol. Volumen extra: Historias de optimización (2012), 9-14" . www.emis.de. Consultado el 2 de diciembre de 2022 .
↑ Calinger 1999 , págs. 234–236
↑ 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.
1 2 Grcar 2011a , págs. 169–172
↑ Grcar 2011b , págs. 783–785
↑ Lauritzen , pág. 3
↑ Grcar 2011b , pág. 789
↑ Althoen, Steven C.; McLaughlin, Renate (1987), "Reducción de Gauss-Jordan: una breve historia", The American Mathematical Monthly , 94 (2), Mathematical Association of America: 130–142 , doi : 10.2307/2322413 , ISSN 0002-9890 , JSTOR 2322413
↑ Farebrother 1988 , pág. 12
↑ Fang, Xin Gui; Havas, George (1997). "Sobre la complejidad del peor caso de la eliminación gaussiana entera" . 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.
1 2 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, MR 1261419
^ Préstamo Golub y Van 1996 , §3.4.6
↑ John Urschel: "Estabilidad numérica en la eliminación gaussiana", junio/julio de 2025, Notice of AMS, pp. 605-613.
↑ Hillar, Christopher; Lim, Lek-Heng (2009-11-07). "La mayoría de los problemas tensoriales son NP-difíciles". arXiv : 0911.1393 [ cs.CC ].
↑ Kurgalin, Sergei; Borzunov, Sergei (2021). Álgebra y geometría con Python . Cham. doi : 10.1007/978-3-030-61541-3 . ISBN 978-3-030-61540-6.{{cite book}}: CS1 mantenimiento: falta el editor de ubicación ( enlace )

Obras citadas

Atkinson, Kendall A. (1989), Introducción al análisis numérico (2.ª ed.), Nueva York: John Wiley & Sons , ISBN 978-0471624899.
Bolch, Gunter; Greiner, Stefan; de Meer, Hermann; Trivedi, Kishor S. (2006), Redes de colas y cadenas de Markov: modelado y evaluación del rendimiento con aplicaciones en informática (2.ª ed.), Wiley-Interscience , ISBN 978-0-471-79156-0.
Calinger, Ronald (1999), Una historia contextual de las matemáticas , Prentice Hall , ISBN 978-0-02-318285-3.
Farebrother, RW (1988), Cálculos de mínimos cuadrados lineales , ESTADÍSTICA: Libros de texto y monografías, Marcel Dekker, ISBN 978-0-8247-7661-9.
Lauritzen, Niels, Convexidad para estudiantes de pregrado: De Fourier y Motzkin a Kuhn y Tucker.
Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations (3.ª ed.), Johns Hopkins, ISBN 978-0-8018-5414-9.
Grcar, Joseph F. (2011a), "Cómo la eliminación ordinaria se convirtió en eliminación gaussiana", Historia Mathematica , 38 (2): 163–218 , arXiv : 0907.2397 , doi : 10.1016/j.hm.2010.06.003 , S2CID 14259511
Grcar, Joseph F. (2011b), "Matemáticos de la eliminación gaussiana" ( PDF) , Notices of the American Mathematical Society , 58 (6): 782–792
Higham, Nicholas (2002), Precisión y estabilidad de los algoritmos numéricos (2.ª ed.), SIAM , ISBN 978-0-89871-521-7.
Katz, Victor J. (2004), Historia de las matemáticas, versión breve , Addison-Wesley , ISBN 978-0-321-16193-2.
Kaw, Autar; Kalu, Egwu (2010). "Métodos numéricos con aplicaciones: Capítulo 04.06 Eliminación gaussiana" (PDF) (1.ª ed.). Universidad del Sur de Florida. Archivado (PDF) del original el 7 de septiembre de 2012.
Lipson, Marc; Lipschutz, Seymour (2001), Schaum's outline of theory and problems of linear algebra , Nueva York: McGraw-Hill , pp. 69–80 , ISBN 978-0-07-136200-9
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Sección 2.2" , Numerical Recipes: The Art of Scientific Computing (3.ª ed.), Nueva York: Cambridge University Press, ISBN 978-0-521-88068-8Archivado del original el 19 de marzo de 2012 , consultado el 8 de agosto de 2011.

Enlaces externos

Herramienta didáctica interactiva

[1] "DOCUMENTA MATHEMATICA, Vol. Volumen extra: Historias de optimización (2012), 9-14" . www.emis.de. Consultado el 2 de diciembre de 2022 .

[2] Calinger 1999 , págs. 234–236

[princeton-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.

[harvnb|Grcar|2011a|pp=169–172-4] 1 2 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), Mathematical Association of America: 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 entera" . 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.

[:0-11] 1 2 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, MR 1261419

[12] Préstamo Golub y Van 1996 , §3.4.6

[13] John Urschel: "Estabilidad numérica en la eliminación gaussiana", junio/julio de 2025, Notice of AMS, pp. 605-613.

[14] Hillar, Christopher; Lim, Lek-Heng (2009-11-07). "La mayoría de los problemas tensoriales son NP-difíciles". arXiv : 0911.1393 [ cs.CC ].

[15] Kurgalin, Sergei; Borzunov, Sergei (2021). Álgebra y geometría con Python . Cham. doi : 10.1007/978-3-030-61541-3 . ISBN 978-3-030-61540-6.{{cite book}}: CS1 mantenimiento: falta el editor de ubicación ( enlace )

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ],

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]