Si $ A $ es un $ n \times n $ y supongamos que queremos resolver $ Ax = b $ utilizando la eliminación gaussiana. La complejidad del tiempo de ejecución de la eliminación gaussiana es $ O(n^3), $ pero ¿cuál es el número aproximado de iteraciones necesarias para realizar el algoritmo?
Respuestas
¿Demasiados anuncios?
Nikolai Prokoschenko
Puntos
2507
Depende de lo que se llame una iteración. Wikipedia dice
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, requiere $\frac{n(n+1)}{2}$ divisiones, $\frac{2n^3 + 3n^2 − 5n}{6}$ multiplicaciones, y $\frac{2n^3 + 3n^2 − 5n}{6}$ sustracciones, para un total de aproximadamente $\frac{2n^3}{3}$ operaciones.
Jared
Puntos
3856
Efectivamente depende de lo que consideres una iteración porque una iteración puede ser 1) reducir el resto de la submatriz, 2) reducir la siguiente fila, o 3) reducir el elemento actual de la matriz.
Si una "iteración" es reducir una sola fila, entonces hay $(n-1) + (n - 2) + (n - 3)... \approx O(n^2)$ iteraciones. Si una iteración está reduciendo una sub-matriz entonces hay $n - 1 \approx O(n)$ .
