En matemáticas , la iteración de potencia (también conocida como método de potencia ) es un algoritmo de valor propio : dada una matriz diagonalizable , el algoritmo producirá un número , que es el valor propio más grande (en valor absoluto) dey un vector distinto de cero , que es un vector propio correspondiente de, es decir, . El algoritmo también se conoce como la iteración de Von Mises . [1]
La iteración de potencia es un algoritmo muy simple, pero puede converger lentamente. La operación del algoritmo que consume más tiempo es la multiplicación de matricespor un vector, por lo que es eficaz para una matriz dispersa muy grande con una implementación adecuada.
El método
El algoritmo de iteración de potencia comienza con un vector , que puede ser una aproximación al autovector dominante o un vector aleatorio. El método se describe mediante la relación de recurrencia
Entonces, en cada iteración, el vector se multiplica por la matriz y normalizado.
Si asumimos tiene un valor propio que es estrictamente mayor en magnitud que sus otros valores propios y el vector inicial tiene un componente distinto de cero en la dirección de un autovector asociado con el autovalor dominante, luego una subsecuencia converge a un vector propio asociado con el valor propio dominante.
Sin los dos supuestos anteriores, la secuencia no necesariamente converge. En esta secuencia,
- ,
dónde es un vector propio asociado con el valor propio dominante, y . La presencia del término implica que no converge a menos que . Bajo los dos supuestos enumerados anteriormente, la secuencia definido por
converge al valor propio dominante (con cociente de Rayleigh ). [ aclaración necesaria ]
Se puede calcular esto con el siguiente algoritmo (que se muestra en Python con NumPy):
#! / usr / bin / env python3importar numpy como npdef power_iteration ( A , num_simulations : int ): # Lo ideal es elegir un vector aleatorio # Para disminuir la probabilidad de que nuestro vector # sea ortogonal al autovector b_k = np . al azar . rand ( A . forma [ 1 ]) para _ en rango ( núm_simulaciones ): # calcular el producto matriz por vector Ab b_k1 = np . punto ( A , b_k ) # calcular la norma b_k1_norm = np . linalg . norma ( b_k1 ) # re normalizar el vector b_k = b_k1 / b_k1_norm volver b_kpower_iteration ( np . array ([[ 0.5 , 0.5 ], [ 0.2 , 0.8 ]]), 10 )
El vector a un vector propio asociado. Idealmente, se debería utilizar el cociente de Rayleigh para obtener el valor propio asociado.
Este algoritmo se utiliza para calcular el PageRank de Google .
El método también se puede utilizar para calcular el radio espectral (el valor propio con la mayor magnitud, para una matriz cuadrada) calculando el cociente de Rayleigh
Análisis
Dejar descomponerse en su forma canónica de Jordan :, donde la primera columna de es un vector propio de correspondiente al autovalor dominante . Dado que el autovalor dominante de es único, el primer bloque de Jordania es el matriz dónde es el valor propio más grande de A en magnitud. El vector inicialse puede escribir como una combinación lineal de las columnas de V :
Por suposición, tiene un componente distinto de cero en la dirección del autovalor dominante, por lo que .
La relación de recurrencia computacionalmente útil para se puede reescribir como:
donde la expresión: es más susceptible al siguiente análisis.
La expresión anterior se simplifica como
El límite se deriva del hecho de que el valor propio de es menor que 1 en magnitud, por lo que
Resulta que:
Usando este hecho, puede escribirse en una forma que enfatice su relación con cuando k es grande:
dónde y como
La secuencia está acotado, por lo que contiene una subsecuencia convergente. Tenga en cuenta que el vector propio correspondiente al valor propio dominante solo es único hasta un escalar, por lo que aunque la secuencia puede no converger, es casi un vector propio de A para k grandes .
Alternativamente, si A es diagonalizable , entonces la siguiente demostración arroja el mismo resultado
Sean λ 1 , λ 2 , ..., λ m los m autovalores (contados con multiplicidad) de A y sean v 1 , v 2 , ..., v m los autovectores correspondientes. Suponer que es el autovalor dominante, de modo que por .
El vector inicial puede ser escrito:
Si se elige al azar (con probabilidad uniforme), luego c 1 ≠ 0 con probabilidad 1 . Ahora,
Por otro lado:
Por lo tanto, converge a (un múltiplo de) el vector propio . La convergencia es geométrica , con razón
dónde denota el segundo valor propio dominante. Por lo tanto, el método converge lentamente si hay un valor propio cercano en magnitud al valor propio dominante.
Aplicaciones
Aunque el método de iteración de potencia se aproxima solo a un valor propio de una matriz, sigue siendo útil para ciertos problemas de cálculo . Por ejemplo, Google lo usa para calcular el PageRank de documentos en su motor de búsqueda, [2] y Twitter lo usa para mostrar a los usuarios recomendaciones sobre a quién seguir. [3] El método de iteración de potencia es especialmente adecuado para matrices dispersas , como la matriz web, o como el método sin matriz que no requiere almacenar la matriz de coeficientes. explícitamente, pero en su lugar puede acceder a una función que evalúa productos de matriz-vector . Para matrices no simétricas que están bien acondicionadas, el método de iteración de potencia puede superar a la iteración de Arnoldi más compleja . Para matrices simétricas, el método de iteración de potencia rara vez se usa, ya que su velocidad de convergencia se puede aumentar fácilmente sin sacrificar el pequeño costo por iteración; ver, por ejemplo, la iteración de Lanczos y LOBPCG .
Algunos de los algoritmos de valores propios más avanzados pueden entenderse como variaciones de la iteración de potencia. Por ejemplo, el método de iteración inversa aplica iteración de potencia a la matriz. Otros algoritmos analizan todo el subespacio generado por los vectores.. Este subespacio se conoce como subespacio de Krylov . Puede calcularse mediante iteración de Arnoldi o iteración de Lanczos .
Ver también
Referencias
- ^ Richard von Mises y H. Pollaczek-Geiringer, Praktische Verfahren der Gleichungsauflösung , ZAMM - Zeitschrift für Angewandte Mathematik und Mechanik 9, 152-164 (1929).
- ^ Ipsen, Ilse y Rebecca M. Wills (5-8 de mayo de 2005). "VII Simposio Internacional IMACS sobre métodos iterativos en informática científica" (PDF) . Fields Institute, Toronto, Canadá.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang y Reza Bosagh Zadeh WTF: El sistema a seguir en Twitter , Actas de la 22a conferencia internacional en World Wide Web