¿Cuál es la eficiencia computacional de la eliminación gaussiana?

Answer 1

De la página de Wikipedia sobre la eliminación gaussiana (con ediciones leves):

El número de operaciones aritméticas requeridas 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 al realizar operaciones de fila en la matriz hasta que esté en forma escalonada, y luego resolver para cada incógnita en orden inverso, requiere [matemáticas] \ frac {n (n + 1) } {2} [/ matemáticas] divisiones, [matemáticas] \ frac {2n ^ 3 + 3n ^ 2–5n} {6} [/ matemáticas] multiplicaciones, y [matemáticas] \ frac {2n ^ 3 + 3n ^ 2– 5n} {6} [/ math] sustracciones, [8], para un total de aproximadamente [math] \ frac {2n ^ 3} {3} [/ math] operaciones. Por lo tanto, tiene una complejidad aritmética de O ([matemáticas] n ^ 3 [/ matemáticas]); ver la gran notación O. Esta complejidad aritmética 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 coma flotante o cuando pertenecen a un campo finito. Si los coeficientes son números enteros o números racionales exactamente representados, las entradas intermedias pueden crecer exponencialmente grandes, por lo que la complejidad de bits es exponencial. [9]

Sin embargo, existe una variante de eliminación gaussiana, llamada algoritmo de Bareiss, que evita este crecimiento exponencial de las entradas intermedias y, con la misma complejidad aritmética de O ([matemática] n ^ 3 [/ matemática]), tiene un poco de complejidad de O ([matemáticas] n ^ 5 [/ matemáticas]).

Este algoritmo se puede usar en una computadora para sistemas con miles de ecuaciones e incógnitas. Sin embargo, el costo se vuelve prohibitivo para sistemas con millones de ecuaciones. Estos grandes sistemas generalmente se resuelven utilizando métodos iterativos. Existen métodos específicos para sistemas cuyos coeficientes siguen un patrón regular (ver sistema de ecuaciones lineales).

Para poner una matriz n por n en forma escalonada reducida por operaciones de fila, se necesitan operaciones aritméticas [matemáticas] n ^ 3 [/ matemáticas]; que es aproximadamente un 50% más de pasos de cálculo. [10]

Answer 2

Imaginaría mucho en comparación con cualquiera de los métodos de iteración donde cada iteración se acerca más a la respuesta exacta. En ingeniería estructural, si el número de incógnitas es bajo, el método de distribución de momentos era popular antes que las computadoras. Pero la eliminación gaussiana es perfecta para las computadoras. Requiere mucha programación para hacerlo usted mismo. O puede usar varios programas estructurales de software ya escritos. rrr

Answer 3

Su pregunta es imprecisa porque no especifica la aritmética utilizada. Si trabaja en doble precisión, el costo es el mismo para todas las operaciones. Si se trabaja en aritmética racional de precisión arbitraria, el costo varía con la complejidad de los números.

Y las técnicas de eliminación gaussianas son muy caras para las fracciones involucradas.

Answer 4

Echa un vistazo a Álgebra lineal numérica de Trefethen y Bau. Es publicado por SIAM. Tienen una serie de bonitas ilustraciones sobre mosaico. Véanse, por ejemplo, las páginas 151–152. En el siguiente capítulo, tratan la eliminación gaussiana con un giro parcial.