¿cuál es la complejidad computacional de la descomposición de valores propios de una matriz unitaria? ¿es O(n^3) una respuesta correcta?
Respuestas
¿Demasiados anuncios?
Skizz
Puntos
30682
En la práctica, $O(n^3)$ .
En teoría, tiene la misma complejidad de la multiplicación de matrices y más o menos todos los "en la práctica $O(n^3)$ "es decir, problemas de álgebra lineal, $O(n^\omega)$ para algunos $2<\omega<2.376$ . Para esta última afirmación, véase Demmel, Dimitriu, Holtz, "Fast linear algebra is stable".
EDIT: esto es en el modelo habitual de álgebra lineal numérica donde las operaciones básicas (+,-,*,/) se realizan aproximadamente en aritmética de máquina IEEE y coste $O(1)$ cada uno. Si tenemos en cuenta la precisión múltiple y las complejidades variables en función de la longitud en bits de los números, la cosa cambia por completo.
Gopherkhan
Puntos
2269
Eche un vistazo al siguiente enlace (y sus referencias) para conocer la complejidad de varios algoritmos para operaciones matemáticas comunes:
Complejidad computacional de las operaciones matemáticas.
En particular, la complejidad de la descomposición de los valores propios de una matriz unitaria es, como ya se ha dicho, la complejidad de la multiplicación de matrices, que es la siguiente $O(n^{2.376})$ utilizando el algoritmo de Coppersmith y Winograd.
Martin Streicher
Puntos
476
Creo que las otras respuestas son erróneas. Busco periódicamente este problema y creo que está abierto. Resumiré mi opinión:
-
Los problemas de valores propios simétricos están "resueltos". Wilkinson pudo demostrar que la iteración QR, con su propia estrategia especial de desplazamiento, converge cúbicamente. Véase este por ejemplo.
-
El problema de los valores propios no simétricos sigue abierto. El capítulo sobre ese tema en Golub y Van Loan dice tiene una discusión sobre cómo el cambio de Wilkinson falla en algunas matrices no simétricas. También mencionan que el desplazamiento ad-hoc de Wilkinson no debe tomarse "demasiado en serio" y que en realidad sólo da a la iteración QR un nuevo comienzo y una oportunidad para una mejor convergencia.
Hasta donde yo sé, nadie conoce la complejidad computacional del problema aproximado de los valores propios.
Edita: Me corrijo . Gracias Suvrit.
Amarald
Puntos
200
2 votos
Tengo algunas dudas sobre la pertinencia de las respuestas que se dan a continuación. No se pueden calcular los valores propios de una matriz unitaria general en tiempo finito. Porque, estos cálculos se podrían utilizar para resolver cada ecuación polinómica con raíces reales (el eje real se transforma racionalmente en el círculo unitario).
1 votos
Añade "...hasta una aproximación necesaria" para resolver esta cuestión. Por lo demás, tienes razón, no se pueden calcular en ningún tiempo finito con el conjunto habitual de operaciones.