¿Cómo encontrar valores propios "únicos" cuando se calculan numéricamente?

Question

Tengo una matriz dispersa grande, $L$, que representa el laplaciano de un grafo ponderado: $L = \text{diag}(\sum_{j=1}^{N} w_{ij})-W$, donde $W$ es la matriz de adyacencia ponderada con $w_{ij}$ dando el peso no negativo de la arista que conecta los vértices $i$ y $j$, con $w_{ii} = 0$ (es decir, sin bucles). $L$ es simétrica. Me gustaría conocer los valores propios "únicos" o "distintos" de $L$. Calculo sus valores propios y obtengo algo como:

$$832.8374\\ 831.8227\\ 829.1944\\ 829.0325\\ 827.0706\\ 825.2424\\ 821.0557\\ 819.1499\\ 818.5737\\ 816.9287\\ \dots$$

Sospecho que mientras numéricamente diferentes, varios de estos realmente corresponden a la misma raíz del polinomio característico, por ejemplo, $\lambda_i' = 829.1944$ y $\lambda_i'' = 829.0325$ probablemente son la misma raíz, $\lambda_i$, pero debido a artefactos numéricos parecen diferentes.

Al calcular los valores propios numéricamente, ¿cómo puedo determinar qué valores propios son realmente raíces distintas del polinomio característico (es decir, quiero conocer los valores propios únicos y su multiplicidad geométrica)?

Estoy calculando estos utilizando la función eigs de Matlab, que utiliza el algoritmo de Arnoldi.

Answer 1

Suponiendo que la iteración de Arnoldi parece haber convergido, entonces dadas dos eigenvalores, es posible determinar si son diferentes. Sin embargo, es imposible determinar si son iguales.

Dados los elementos de la matriz y el vector inicial y el número de iteraciones en su solucionador de eigenvalores, es posible determinar la cantidad máxima de error que se ha acumulado a partir de operaciones de punto flotante como función de la precisión de la máquina. Desafortunadamente, este análisis de error flotante puede ser bastante complicado dependiendo de cómo esté implementando su solucionador iterativo (sería mucho más sencillo, por ejemplo, analizar la iteración de potencia).

Al final del día, tendrá un límite superior en el error relativo posible, en cuyo caso si dos eigenvalores tienen una relación que excede ese valor, entonces se puede concluir que son diferentes. Si la relación de dos eigenvalores está por debajo de este umbral, entonces no se puede hacer ninguna conclusión, ya que es imposible determinar si los eigenvalores son iguales, o simplemente más cercanos de lo que la precisión finita de la computadora puede resolver.