¿Por qué tiene problemas de estabilidad numérica?

Question

Lo siguiente es parte de un papel Estoy leyendo.

Antecedentes : $D$ es la matriz de grados de un grafo. $A$ es la matriz de adyacencia de ese grafo.

$D$ es una matriz diagonal donde $D(i,i)$ es la suma de los elementos del $i$ a fila en $A$ y $A$ es una matriz no negativa dispersa.

No entiendo por qué la matriz $I_N+D^{-1/2}A{-1/2}$ tiene problemas de estabilidad cuando se aplica repetidamente a un vector $x$ y por qué simplemente cambiarlo por un equivalente $\tilde D^{-1/2} \tilde A \tilde D^{-1/2}$ ayuda. El documento afirma que el problema numérico se debe a que la primera matriz tiene un valor propio en $[0,2]$ pero el valor propio sigue estando en $[0,2]$ después de la transformación.

No estoy en esta área pero conozco el concepto de estabilidad numérica y número condicional. Se agradece cualquier ayuda.

Answer 1

No es tan importante que los valores propios en ambos casos sigan perteneciendo a un mismo segmento [0,2]. Lo que sí importa: la relación de condiciones que es la relación entre los valores propios máximos y mínimos. La transformación sugerida en el documento, aparentemente, fue probada por los autores y se encontró que era beneficiosa en términos de reducción de la relación de condiciones de manera significativa. Como ejemplo: supongamos que en el primer caso los valores propios máximo y mínimo son iguales a 1,9999999 y 0,00000001 respectivamente, pero después de la transformación los valores máximo y mínimo son 1,9 y 0,1 . En el primer caso, la relación de condiciones es tan grande que incluso la multiplicación matriz por vector realizada en doble precisión (16 dígitos decimales) no tendrá dígitos significativos correctos. En el segundo caso, sin embargo, la matriz estaría muy bien condicionada, y la multiplicación matriz por vector dará un resultado numéricamente excelente.