En álgebra lineal numérica , la iteración de Arnoldi es un algoritmo de valor propio y un ejemplo importante de un método iterativo . Arnoldi encuentra una aproximación a los autovalores y autovectores de matrices generales (posiblemente no hermitianas ) mediante la construcción de una base ortonormal del subespacio de Krylov , lo que lo hace particularmente útil cuando se trata de grandes matrices dispersas .
El método Arnoldi pertenece a una clase de algoritmos de álgebra lineal que dan un resultado parcial después de un pequeño número de iteraciones, en contraste con los llamados métodos directos que deben completarse para dar resultados útiles (ver, por ejemplo, Transformación de amo de casa ). El resultado parcial en este caso son los primeros vectores de la base que está construyendo el algoritmo.
Cuando se aplica a matrices hermitianas, se reduce al algoritmo de Lanczos . La iteración de Arnoldi fue inventada por WE Arnoldi en 1951. [1]
Subespacios de Krylov y la iteración de poder
Un método intuitivo para encontrar el valor propio más grande (en valor absoluto) de una matriz m × m dadaes el método de las potencias : comenzando con una inicial arbitraria vector b , calcular Ab , A 2 b , A 3 b , ... normalizar el resultado después de cada aplicación de la matriz A .
Esta secuencia converge al autovector correspondiente al autovalor con el mayor valor absoluto,. Sin embargo, muchos cálculos potencialmente útiles se desperdician utilizando solo el resultado final,. Esto sugiere que, en cambio, formamos la llamada matriz de Krylov :
Las columnas de esta matriz no son en general ortogonales , pero podemos extraer una base ortogonal , mediante un método como la ortogonalización de Gram-Schmidt . El conjunto de vectores resultante es, por tanto, una base ortogonal del subespacio de Krylov ,. Podemos esperar que los vectores de esta base abarquen buenas aproximaciones de los vectores propios correspondientes a la valores propios ms grandes, por la misma razn que se aproxima al vector propio dominante.
La iteración de Arnoldi
La iteración de Arnoldi utiliza el proceso de Gram-Schmidt modificado para producir una secuencia de vectores ortonormales, q 1 , q 2 , q 3 ,…, llamados vectores de Arnoldi , de manera que para cada n , los vectores q 1 ,…, q n abarcan el subespacio de Krylov. Explícitamente, el algoritmo es el siguiente:
- Comience con un vector arbitrario q 1 con norma 1.
- Repita para k = 2, 3,…
- para j de 1 a k - 1
El j -loop proyecta el componente de en las direcciones de . Esto asegura la ortogonalidad de todos los vectores generados.
El algoritmo se rompe cuando q k es el vector cero. Esto sucede cuando el polinomio mínimo de A es de grado k . En la mayoría de las aplicaciones de la iteración de Arnoldi, incluido el algoritmo de valor propio a continuación y GMRES , el algoritmo ha convergido en este punto.
Cada paso del k- bucle toma un producto de matriz-vector y aproximadamente 4 mk operaciones de punto flotante.
En el lenguaje de programación python:
importar numpy como npdef arnoldi_iteration ( A , b , n : int ): "" "Calcula una base del subespacio (n + 1) -Krylov de A: el espacio generado por {b, Ab, ..., A ^ nb}. Argumentos A: matriz m × m b: vector inicial (longitud m) n: dimensión del subespacio de Krylov, debe ser> = 1 Devuelve Q: matriz mx (n + 1), las columnas son una base ortonormal del subespacio de Krylov. h: (n + 1) xn matriz, A sobre la base Q. Es el Hessenberg superior. """ M = A . La forma [ 0 ] h = np . Ceros (( n + 1 , n )) Q = np . Ceros (( m , n + 1 )) q = b / np . Linalg . Norma ( b ) # Normaliza el vector de entrada Q [:, 0 ] = q # Úselo como el primer vector de Krylov para k en gama ( n ): v = A . dot ( q ) # Genere un nuevo vector candidato para j en el rango ( k + 1 ): # Reste las proyecciones en los vectores anteriores h [ j , k ] = np . punto ( Q [:, j ] . conj (), v ) v = v - h [ j , k ] * Q [:, j ] h [ k + 1 , k ] = np . linalg . norma ( v ) eps = 1e-12 # Si v es más corto que este umbral, es el vector cero si h [ k + 1 , k ] > eps : # Agregue el vector producido a la lista, a menos que q = v / h [ k + 1 , k ] # se produce el vector cero. Q [:, k + 1 ] = q else : # Si eso sucede, deje de iterar. devuelve Q , h vuelve Q , h
Propiedades de la iteración de Arnoldi
Sea Q n la matriz m -por- n formada por los primeros n vectores Arnoldi q 1 , q 2 ,…, q n , y sea H n la matriz ( Hessenberg superior ) formada por los números h j , k calculados por el algoritmo:
El método de ortogonalización debe elegirse específicamente de modo que los componentes inferiores de Arnoldi / Krylov se eliminen de los vectores superiores de Krylov. Comopueden expresarse en términos de q 1 ,…, q i + 1 por construcción, son ortogonales a q i + 2 ,…, q n ,
Entonces tenemos
La matriz H n puede verse como A en el subespaciocon los vectores de Arnoldi como base ortogonal; A se proyecta ortogonalmente sobre. La matriz H n se pueden caracterizar por la siguiente condición de optimalidad. El polinomio característico de H n minimiza || p ( A ) q 1 || 2 entre todos los polinomios monicos de grado n . Este problema de optimización tiene una solución única si y solo si la iteración de Arnoldi no se rompe.
La relación entre las matrices Q en iteraciones posteriores viene dada por
dónde
es una matriz ( n +1) -por- n formada agregando una fila adicional a H n .
Encontrar valores propios con la iteración de Arnoldi
La idea de la iteración de Arnoldi como un algoritmo de valor propio es calcular los valores propios en el subespacio de Krylov. Los valores propios de H n se denominan valores propios de Ritz . Dado que H n es una matriz de Hessenberg de tamaño modesto, sus valores propios se pueden calcular de manera eficiente, por ejemplo, con el algoritmo QR , o algo relacionado, con el algoritmo de Francis. También se puede considerar que el propio algoritmo de Francis está relacionado con las iteraciones de poder, que operan en el subespacio anidado de Krylov. De hecho, la forma más básica del algoritmo de Francis parece ser para elegir b sea igual a Ae 1 , y que se extiende n a la dimensión completa de A . Las versiones mejoradas incluyen uno o más cambios, y se pueden aplicar mayores potencias de A en un solo paso. [1]
Este es un ejemplo del método Rayleigh-Ritz .
Se observa con frecuencia en la práctica que algunos de los valores propios Ritz convergen a valores propios de A . Dado que H n es n- por- n , tiene como máximo n valores propios, y no todos los valores propios de A pueden aproximarse. Típicamente, los valores propios Ritz convergen a los mayores autovalores de A . Para obtener los valores propios más pequeños de A , se debe usar la inversa (operación) de A en su lugar. Esto se puede relacionar con la caracterización de H n como la matriz cuyo polinomio característico minimiza || p ( A ) q 1 || de la siguiente manera. Una buena manera de conseguir p ( Un pequeño) es elegir el polinomio p tal que p ( x ) es pequeño cada vez que x es un valor propio de A . Por lo tanto, los ceros de p (y por lo tanto los valores propios Ritz) estarán cerca de los valores propios de A .
Sin embargo, los detalles aún no se comprenden completamente. Esto contrasta con el caso en el que A es simétrico . En esa situación, la iteración de Arnoldi se convierte en la iteración de Lanczos , para lo cual la teoría es más completa.
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/9/9b/Arnoldi_Iteration.gif)
Método Arnoldi reiniciado implícitamente (IRAM)
Debido a la consideración práctica del almacenamiento, las implementaciones comunes de los métodos Arnoldi generalmente se reinician después de algunas iteraciones. Una innovación importante en el reinicio se debió a Lehoucq y Sorensen, quienes propusieron el método Arnoldi reiniciado implícitamente. [2] También implementaron el algoritmo en un paquete de software disponible gratuitamente llamado ARPACK . [3] Esto ha provocado una serie de otras variaciones, incluido el método Lanczos reiniciado implícitamente. [4] [5] [6] También influyó en cómo se analizan otros métodos reiniciados. [7] Los resultados teóricos han demostrado que la convergencia mejora con un aumento en la dimensión n del subespacio de Krylov . Sin embargo, no se conoce un valor a priori de n que conduciría a una convergencia óptima. Recientemente se ha propuesto una estrategia de conmutación dinámica [8] que fluctúa la dimensión n antes de cada reinicio y, por lo tanto, conduce a una aceleración en la tasa de convergencia.
Ver también
El método de residuo mínimo generalizado (GMRES) es un método para resolver Ax = b basado en la iteración de Arnoldi.
Referencias
- ^ WE Arnoldi, "El principio de iteraciones minimizadas en la solución del problema de valores propios de la matriz", Quarterly of Applied Mathematics , volumen 9, páginas 17-29, 1951
- ^ RB Lehoucq y DC Sorensen (1996). "Técnicas de deflación para una iteración de Arnoldi reiniciada implícitamente". SIAM . doi : 10.1137 / S0895479895281484 . hdl : 1911/101832 .
- ^ RB Lehoucq; DC Sorensen y C. Yang (1998). "Guía de usuarios de ARPACK: solución de problemas de valores propios a gran escala con métodos Arnoldi reiniciados implícitamente" . SIAM. Archivado desde el original el 26 de junio de 2007 . Consultado el 30 de junio de 2007 .
- ^ D. Calvetti ; L. Reichel y DC Sorensen (1994). "Un método de Lanczos reiniciado implícitamente para grandes problemas de valores propios simétricos" . ETNA.
- ^ E. Kokiopoulou; C. Bekas y E. Gallopoulos (2003). "Un método de bidiagonalización de Lanczos reiniciado implícitamente para calcular los tríos singulares más pequeños" (PDF) . SIAM.
- ^ Zhongxiao Jia (2002). "El método armónico refinado de Arnoldi y un algoritmo refinado reiniciado implícitamente para calcular pares propios interiores de matrices grandes". Apl. Numer. Matemáticas . doi : 10.1016 / S0168-9274 (01) 00132-5 .
- ^ Andreas Stathopoulos y Yousef Saad y Kesheng Wu (1998). "Reinicio dinámico grueso de Davidson y los métodos Arnoldi reiniciados implícitamente". SIAM . doi : 10.1137 / S1064827596304162 .
- ^ K.Dookhitram, R. Boojhawon y M. Bhuruth (2009). "Un nuevo método para acelerar los algoritmos de Arnoldi para problemas propios a gran escala". Matemáticas. Computación. Simulat . doi : 10.1016 / j.matcom.2009.07.009 .
- WE Arnoldi, "El principio de iteraciones minimizadas en la solución del problema de valores propios de la matriz", Quarterly of Applied Mathematics , volumen 9, páginas 17-29, 1951.
- Yousef Saad , Métodos numéricos para grandes problemas de valores propios , Manchester University Press, 1992. ISBN 0-7190-3386-1 .
- Lloyd N. Trefethen y David Bau, III, Álgebra lineal numérica , Sociedad de Matemáticas Industriales y Aplicadas, 1997. ISBN 0-89871-361-7 .
- Jaschke, Leonhard: Métodos de Arnoldi preacondicionados para sistemas de ecuaciones no lineales . (2004). ISBN 2-84976-001-3
- Implementación: Matlab viene con ARPACK incorporado. Tanto las matrices almacenadas como las implícitas se pueden analizar mediante la función eigs () .