Vectores y valores propios en los métodos iterativos

Question

He estudiado muchos métodos iterativos, como el de Jacobi, el de punto fijo, el de Newton y el de gradiente conjugado.

Actualmente, estoy estudiando el método CG, pero no es la primera vez que los vectores propios (y los valores propios) de la matriz habitual implicada son importantes para determinar cómo se comporta el método iterativo, como cuál es la convergencia del método.

En concreto, estaba leyendo el libro "A first course in numerical methods" (de Greif, Ascher) y en un punto determinado (pp. 186-7) hay:

Si los valores propios de A se encuentran en unos pocos clústeres estrechos, entonces el CG requiere sólo unas pocas iteraciones para converger. Sin embargo, la convergencia es más lenta si los valores propios están muy repartidos.

lo que me hace preguntarme por qué, si los valores propios de $A$ se encuentran en unos pocos grupos estrechos el CG converge rápidamente?

No es la primera vez que veo observaciones similares en las que los valores y vectores propios de la matriz implicada en el método iterativo determinan de alguna manera el comportamiento o rendimiento del método iterativo.

Mis preguntas, aparte del caso concreto anterior, son:

1. ¿Cuáles son las relaciones entre los vectores propios y los valores propios de las matrices que intervienen en un método iterativo y el comportamiento del método iterativo (si se puede generalizar)?

2. ¿Cuáles son los comportamientos generales de los métodos iterativos que podemos predecir dados los vectores propios o los valores propios?

Si esto no se puede generalizar, o bien podría hacer preguntas específicas, o bien podría como enumerar algunos ejemplos en los que los vectores propios y los valores propios influyen en diferentes métodos iterativos. Por supuesto, una lista exhaustiva estaría bien para todos.

Nota: Sé lo que son los vectores propios y los valores propios, aunque cuando pienso en ellos no consigo entender por qué son útiles. Se podría argumentar que son útiles como en el ejemplo anterior, pero no puedo ver la relación muy bien y claramente.

Answer 1

El método iterativo puede dividirse en dos grandes grupos:

• Métodos estacionarios que utilizan una idea de iteración de punto fijo
• Los métodos de Krylov que son métodos de proyección. ( en esta pregunta le interesan estos )

Ver esto Respuesta de @Christian_Clason para más detalles.

¿Cuáles son las relaciones entre los vectores propios y los valores propios de las matrices que intervienen en un método iterativo y el comportamiento del método iterativo (si se puede generalizar)?

¿Cuáles son los comportamientos generales de los métodos iterativos que podemos predecir dados los vectores propios o los valores propios?

Para el GC la relación con los valores propios viene dada por la estimación del error que implica el número de condición $k= \lambda_{max} / \lambda_{min}$ : $$ || x_\star - x_m||_A \leq 2 \left[ \frac{\sqrt{k} - 1}{\sqrt{k} + 1} \right]^m || x_\star - x_0||_A $$ Vea la página 187 de su libro, o [1] página 215 ecuación (6.128) aquí puede encontrar también la prueba.

Nota:

• el uso del número de condición para la estimación se puede considerar una "característica" de los métodos de Krylov.
• para diferentes algoritmos se puede encontrar la estimación oportuna, ver [1]

Considerando el caso:

Si los valores propios de A se encuentran en unos pocos grupos estrechos

entonces también $\lambda_{max}, \lambda_{min}$ están cerca y tienes una mejor $k$ , el caso perfecto es cuando $k=1$ . En el caso realista es cuando $k$ lo más cerca posible a 1. Mejor es $k$ menos iteraciones necesita para la convergencia.

Nota: Este es el alcance de la técnica de precondicionamiento, sustituir el sistema lineal original por un equivalente cuyas propiedades espectrales son mejores (ver pag 187-88 de su libro, o dedicar capítulos de [1]). Es decir, que los valores propios de la matriz de precondicionamiento $P^{-1}A$ están en un grupo a 1.

---

[1] Saad, Yousef. Iterative methods for sparse linear systems. Siam, 2003.