¿Por qué el método de Lanczos sólo sirve para resolver los valores propios extremos?

Question

Es un folclore que el método de Lanczos es bueno para buscar los pocos valores propios más pequeños o más grandes, pero no es útil para buscar los que están en el medio del espectro. En realidad, esto parece una regla general para muchos algoritmos similares, como el método de Davidson.

¿Hay alguna razón general para esta limitación general?

Answer 1

En general, los métodos de subespacios de Krylov, como el método de Lanczos, producen una aproximación del "espacio dominante" de una matriz, es decir, se aproximan los vectores propios más grandes o más pequeños. La ventaja de este método es que el cálculo de un pequeño número de vectores propios (comparado con el tamaño de la matriz) es mucho más barato que el cálculo de una factorización de la matriz. Para muchas aplicaciones, el cálculo de los valores propios más grandes o más pequeños es suficiente.

No es posible aproximar directamente el centro del espectro mediante el método de Lanczos. Si se quiere aproximar la parte central del espectro con el método de Lanczos, habría que aproximar un "espacio dominante", que contiene aproximaciones para todos los vectores propios desde el más grande/pequeño hasta los de la parte central, es decir, más de $n/2$ para un $n \times n$ matriz. Esto ya no es eficiente y podría conducir a inestabilidades numéricas.

Si puede estimar un valor cercano al valor propio medio, puede utilizar la iteración inversa para calcular los valores propios más cercanos a un valor prescrito. De lo contrario, tendrá que calcular al menos la mitad de los valores propios, lo que puede resultar muy caro.

En este último caso, podría ser mejor calcular directamente todos los valores propios utilizando un algoritmo adecuado (véase https://en.wikipedia.org/wiki/List_of_numerical_analysis_topics#Eigenvalue_algorithms ). Estos eigensolvers directos suelen implicar el cálculo de una forma tridiagonal o una descomposición de Schur, a partir de la cual se obtienen los valores propios (véase también https://en.wikipedia.org/wiki/Eigenvalue_algorithm ).

---

Para entender mejor por qué la mayoría de los algoritmos calculan el mayor o el menor valor propio, puede ser bueno empezar por ver el método de la potencia. Al calcular $A^kx$ para $k\to \infty$ se obtiene una aproximación del mayor valor propio. En los métodos de Krylov se proyecta la matriz en el subespacio de Krylov $\{ x, Ax, A^2x, A^3x, A^4x, \dots\}$ . Por construcción, este subespacio tiende a contener aproximadamente los vectores propios más grandes.

Para obtener el valor propio más pequeño se calcula $A^{-k}x$ que está relacionado con el subespacio de Krylov $\{ x, A^{-1}x,A^{-2}x,\dots\}$ .

No se puede construir directamente un subespacio de Krylov para los valores propios medios.