Autovalor prueba más rápido que $O\left(n^3\right)$?

Question

Dado un real $n\times n$ matriz $A$, uno puede encontrar los autovalores de a $O\left(n^3\right)$ utilizando decir, el $QR$ algoritmo.

Ahora, lo que si suponemos un autovalor $\lambda_0$, y queremos saber si se trata realmente de un autovalor de la matriz $A$? Intuitivamente, esto debería ser significativamente más rápido que en realidad encontrar todos los autovalores. Podemos, por supuesto, comprobar si $\lambda_0$ es en realidad un autovalor mediante el cálculo de $\det(A-\lambda_0 I)$, pero al calcular el determinante también es $O\left(n^3\right)$.

Así:

• Hay más de lo $O\left(n^3\right)$ método de evaluación de la "eigenvaluedness" de un determinado número de $\lambda_0$, sin resolver para el resto de la $\lambda_i$'s? Se puede demostrar que no existe?

• Ayuda si $A$ es ortogonal, simétrica o tiene otros especiales (no triangular) formulario?

Recompensa de actualización:

Recompensa va a quienquiera que muestra cualquiera de los siguientes:

1. Un método de comprobación de una posible autovalor en menos de $O(n^3)$.
2. Una prueba o suficientemente convincente heurística argumento de que no existe un método.

Answer 1

El primer algoritmo calcular el determinante más rápido que en el $O(n^{3})$ tiempo (su algoritmo trabajó en $O(n^{\ln 7/\ln 2})$) fue determinado por Volker Strassen en este clásico de papel. Por lo tanto, $O(n^{\ln 7/\ln 2})$ el tiempo suficiente para comprobar si un número dado es un autovalor o no. De hecho, el problema de calcular el determinante ha asintóticamente la misma complejidad que el problema de la multiplicación de dos $n\times n$ matrices, para que $O(n^{2+\varepsilon})$ compleixty es conjetura. Algunos datos y referencias sobre este están contenidas en el enlace proporcionado por xavierm02 en su comentario.

Answer 2

Por supuesto, el algoritmo de Strassen calcula el determinante de a $O(n^{2.807})$ ; por otra parte es el único algoritmo que, en la práctica, hace el trabajo más rápido que en el $O(n^3)$ - al $n\geq 2048$ - (para fijar ideas) (a continuación, vamos a $\omega=2.807$ si $n\geq 2048$, de lo contrario $\omega=3$.). Sin embargo, esa no es realmente la cuestión aquí. De hecho, el cálculo de $spectrum(A)$ y el cálculo de $\det(A)$ (o de la plaza de la $A^2$) están todos en $O(n^{\omega})$, bajo la condición de que buscamos una aproximación de los valores verdaderos. Por lo que la pregunta sería:

Consideramos el siguiente problema : Supongamos $A\in M_n(\mathbb{C}),\lambda_0\in \mathbb{C},r\in \mathbb{N}$ ; ¿existe un autovalor $\lambda$ $A$ s.t. $|\lambda-\lambda_0|<10^{-r}$ ? Su complejidad es $\sim kn^{\omega}$. ¿Cuál es el valor de $k$ ?

Consideremos el siguiente experimento (Arce): $A\in M_{10}(\mathbb{Z})$ es elegido al azar ($a_{i,j}\in[-99,99])$. $A$ admite un autovalor $\lambda\approx -166-15i$ $\lambda_0$ está construido con la primera $15$ dígitos significativos de $Re(\lambda)$$Im(\lambda)$. Si $r=12$, entonces la respuesta a nuestro problema, es que SÍ. Desafortunadamente $\det(A-\lambda_0 I))\approx 1.7\times 10^7-3.7\times10^7i$. Por último, no basta para calcular el anterior determinante. También se debe considerar la derivada en $\lambda_0$ de la función de $\phi:t\rightarrow \det(A-tI)$.

EDIT: Más precisamente, $\phi(\lambda_0)\approx(\lambda_0-\lambda)\phi'(\lambda_0)$ y, en consecuencia, $|\lambda-\lambda_0|\approx\rho=\dfrac{|\det(A-\lambda_0I)|}{|trace(adj(A-\lambda_0I))|}=\dfrac{1}{|trace((A-\lambda_0I)^{-1})|}$ (si $\lambda_0\not=\lambda$). De la instancia anterior, nos encontramos con $|\lambda-\lambda_0|\approx 6\times 10^{-13}$. La complejidad del cálculo de $\rho$ , $LU$ método, es $\sim n^3$ (que es $k=1$). Tenga en cuenta que la complejidad de una descomposición QR es $\sim\dfrac{4}{3}n^3$.

Answer 3

No es necesario calcular el determinante, sólo para confirmar si es cero.

Como tal, es suficiente para intentar una inversión de matrices para $\mathbf{A}-\lambda\mathbf{I}$... si esto falla, entonces el determinante es cero, y por lo tanto hemos confirmado $\lambda$ a ser un autovalor.

Se puede demostrar que, a través de un divide y vencerás enfoque, la inversión de matrices tiene la misma complejidad que la multiplicación de la matriz. Y porque Williams algoritmo existe con $O(n^{2.3727})$, esto también es posible, la complejidad para la confirmación de un autovalor (hasta una cierta precisión numérica, por supuesto).