Iteración de potencia

Algoritmo de valores propios

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 mayor valor propio (en valor absoluto) de , y un vector distinto de cero , que es un vector propio correspondiente de , es decir, . El algoritmo también se conoce como iteración de Von Mises . ^[1] ${\displaystyle A}$ ${\displaystyle \lambda }$ ${\displaystyle A}$ ${\displaystyle v}$ ${\displaystyle \lambda }$ ${\displaystyle Av=\lambda v}$

La iteración de potencia es un algoritmo muy simple, pero puede converger lentamente. La operación que consume más tiempo del algoritmo es la multiplicación de una matriz por un vector, por lo que es eficaz para una matriz dispersa muy grande con una implementación adecuada. La velocidad de convergencia es similar a (consulte una sección posterior). En palabras, la convergencia es exponencial y la base es la brecha espectral . ${\displaystyle A}$ ${\displaystyle (\lambda _{1}/\lambda _{2})^{k}}$

El método

Animación que visualiza el algoritmo de iteración de potencia en una matriz de 2x2. La matriz se representa mediante sus dos vectores propios. El error se calcula como ${\displaystyle ||{\text{approximation}}-{\text{largest eigenvector}}||}$

El algoritmo de iteración de potencia comienza con un vector , que puede ser una aproximación al vector propio dominante o un vector aleatorio. El método se describe mediante la relación de recurrencia ${\displaystyle b_{0}}$

${\displaystyle b_{k+1}={\frac {Ab_{k}}{\|Ab_{k}\|}}}$

Entonces, en cada iteración, el vector se multiplica por la matriz y se normaliza. ${\displaystyle b_{k}}$ ${\displaystyle A}$

Si suponemos que 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 vector propio asociado con el valor propio dominante, entonces una subsecuencia converge a un vector propio asociado con el valor propio dominante. ${\displaystyle A}$ ${\displaystyle b_{0}}$ ${\displaystyle \left(b_{k}\right)}$

Sin los dos supuestos anteriores, la secuencia no necesariamente converge. En esta secuencia, ${\displaystyle \left(b_{k}\right)}$

${\displaystyle b_{k}=e^{i\phi _{k}}v_{1}+r_{k}}$,

donde 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 definida por ${\displaystyle v_{1}}$ ${\displaystyle \|r_{k}\|\rightarrow 0}$ ${\displaystyle e^{i\phi _{k}}}$ ${\displaystyle \left(b_{k}\right)}$ ${\displaystyle e^{i\phi _{k}}=1}$ ${\displaystyle \left(\mu _{k}\right)}$

${\displaystyle \mu _{k}={\frac {b_{k}^{*}Ab_{k}}{b_{k}^{*}b_{k}}}}$

converge al valor propio dominante (con cociente de Rayleigh ). ^{[ aclaración necesaria ]}

Esto se puede calcular con el siguiente algoritmo (mostrado en Python con NumPy):

#!/usr/bin/env python3importar  numpy  como  npdef  power_iteration ( A ,  num_iterations :  int ):  # Idealmente elija un vector aleatorio  # Para disminuir la probabilidad de que nuestro vector  # Sea ortogonal al vector propio  b_k  =  np . random . rand ( A . shape [ 1 ]) para  _  en  rango ( num_iterations ):  # calcula el producto matriz-vector Ab  b_k1  =  np . dot ( A ,  b_k ) # Calcular la norma  b_k1_norm  =  np . linalg . norm ( b_k1 ) # volver a normalizar el vector  b_k  =  b_k1  /  b_k1_norm devolver  b_kpotencia_iteración ( np . matriz ([[ 0.5 ,  0.5 ],  [ 0.2 ,  0.8 ]]),  10 )

El vector converge a un vector propio asociado. Lo ideal sería utilizar el cociente de Rayleigh para obtener el valor propio asociado. ${\displaystyle b_{k}}$

Este algoritmo se utiliza para calcular el Google PageRank .

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.

${\displaystyle \rho (A)=\max \left\{|\lambda _{1}|,\dotsc ,|\lambda _{n}|\right\}={\frac {b_{k}^{\top }Ab_{k}}{b_{k}^{\top }b_{k}}}.}$

Análisis

Sea descompuesto en su forma canónica de Jordan : , donde la primera columna de es un vector propio de correspondiente al valor propio dominante . Dado que genéricamente , el valor propio dominante de es único, el primer bloque de Jordan de es la matriz donde es el valor propio más grande de A en magnitud. El vector inicial se puede escribir como una combinación lineal de las columnas de V : ${\displaystyle A}$ ${\displaystyle A=VJV^{-1}}$ ${\displaystyle V}$ ${\displaystyle A}$ ${\displaystyle \lambda _{1}}$ ${\displaystyle A}$ ${\displaystyle J}$ ${\displaystyle 1\times 1}$ ${\displaystyle [\lambda _{1}],}$ ${\displaystyle \lambda _{1}}$ ${\displaystyle b_{0}}$

${\displaystyle b_{0}=c_{1}v_{1}+c_{2}v_{2}+\cdots +c_{n}v_{n}.}$

Por supuesto, tiene un componente distinto de cero en la dirección del valor propio dominante, por lo que . ${\displaystyle b_{0}}$ ${\displaystyle c_{1}\neq 0}$

La relación de recurrencia computacionalmente útil para se puede reescribir como: ${\displaystyle b_{k+1}}$

${\displaystyle b_{k+1}={\frac {Ab_{k}}{\|Ab_{k}\|}}={\frac {A^{k+1}b_{0}}{\|A^{k+1}b_{0}\|}},}$

donde la expresión: es más susceptible al siguiente análisis. ${\displaystyle {\frac {A^{k+1}b_{0}}{\|A^{k+1}b_{0}\|}}}$

${\displaystyle {\begin{aligned}b_{k}&={\frac {A^{k}b_{0}}{\|A^{k}b_{0}\|}}\\&={\frac {\left(VJV^{-1}\right)^{k}b_{0}}{\|\left(VJV^{-1}\right)^{k}b_{0}\|}}\\&={\frac {VJ^{k}V^{-1}b_{0}}{\|VJ^{k}V^{-1}b_{0}\|}}\\&={\frac {VJ^{k}V^{-1}\left(c_{1}v_{1}+c_{2}v_{2}+\cdots +c_{n}v_{n}\right)}{\|VJ^{k}V^{-1}\left(c_{1}v_{1}+c_{2}v_{2}+\cdots +c_{n}v_{n}\right)\|}}\\&={\frac {VJ^{k}\left(c_{1}e_{1}+c_{2}e_{2}+\cdots +c_{n}e_{n}\right)}{\|VJ^{k}\left(c_{1}e_{1}+c_{2}e_{2}+\cdots +c_{n}e_{n}\right)\|}}\\&=\left({\frac {\lambda _{1}}{|\lambda _{1}|}}\right)^{k}{\frac {c_{1}}{|c_{1}|}}{\frac {v_{1}+{\frac {1}{c_{1}}}V\left({\frac {1}{\lambda _{1}}}J\right)^{k}\left(c_{2}e_{2}+\cdots +c_{n}e_{n}\right)}{\left\|v_{1}+{\frac {1}{c_{1}}}V\left({\frac {1}{\lambda _{1}}}J\right)^{k}\left(c_{2}e_{2}+\cdots +c_{n}e_{n}\right)\right\|}}\end{aligned}}}$

La expresión anterior se simplifica como ${\displaystyle k\to \infty }$

${\displaystyle \left({\frac {1}{\lambda _{1}}}J\right)^{k}={\begin{bmatrix}[1]&&&&\\&\left({\frac {1}{\lambda _{1}}}J_{2}\right)^{k}&&&\\&&\ddots &\\&&&\left({\frac {1}{\lambda _{1}}}J_{m}\right)^{k}\\\end{bmatrix}}\rightarrow {\begin{bmatrix}1&&&&\\&0&&&\\&&\ddots &\\&&&0\\\end{bmatrix}}\quad {\text{as}}\quad k\to \infty .}$

El límite se deduce del hecho de que el valor propio de es menor que 1 en magnitud, por lo que ${\displaystyle {\frac {1}{\lambda _{1}}}J_{i}}$

${\displaystyle \left({\frac {1}{\lambda _{1}}}J_{i}\right)^{k}\to 0\quad {\text{as}}\quad k\to \infty .}$

Resulta que:

${\displaystyle {\frac {1}{c_{1}}}V\left({\frac {1}{\lambda _{1}}}J\right)^{k}\left(c_{2}e_{2}+\cdots +c_{n}e_{n}\right)\to 0\quad {\text{as}}\quad k\to \infty }$

Usando este hecho, se puede escribir en una forma que enfatiza su relación con cuando k es grande: ${\displaystyle b_{k}}$ ${\displaystyle v_{1}}$

${\displaystyle {\begin{aligned}b_{k}&=\left({\frac {\lambda _{1}}{|\lambda _{1}|}}\right)^{k}{\frac {c_{1}}{|c_{1}|}}{\frac {v_{1}+{\frac {1}{c_{1}}}V\left({\frac {1}{\lambda _{1}}}J\right)^{k}\left(c_{2}e_{2}+\cdots +c_{n}e_{n}\right)}{\left\|v_{1}+{\frac {1}{c_{1}}}V\left({\frac {1}{\lambda _{1}}}J\right)^{k}\left(c_{2}e_{2}+\cdots +c_{n}e_{n}\right)\right\|}}\\[6pt]&=e^{i\phi _{k}}{\frac {c_{1}}{|c_{1}|}}{\frac {v_{1}}{\|v_{1}\|}}+r_{k}\end{aligned}}}$

Dónde y como ${\displaystyle e^{i\phi _{k}}=\left(\lambda _{1}/|\lambda _{1}|\right)^{k}}$ ${\displaystyle \|r_{k}\|\to 0}$ ${\displaystyle k\to \infty }$

La secuencia está acotada, por lo que contiene una subsecuencia convergente. Nótese 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 valores grandes de k . ${\displaystyle \left(b_{k}\right)}$ ${\displaystyle \left(b_{k}\right)}$ ${\displaystyle b_{k}}$

Alternativamente, si A es diagonalizable , entonces la siguiente prueba arroja el mismo resultado

Sean λ ₁ , λ ₂ , ..., λ _m los m valores propios (contados con multiplicidad) de A y sean v ₁ , v ₂ , ..., v _m los vectores propios correspondientes. Supóngase que es el valor propio dominante, de modo que para . ${\displaystyle \lambda _{1}}$ ${\displaystyle |\lambda _{1}|>|\lambda _{j}|}$ ${\displaystyle j>1}$

El vector inicial se puede escribir: ${\displaystyle b_{0}}$

${\displaystyle b_{0}=c_{1}v_{1}+c_{2}v_{2}+\cdots +c_{m}v_{m}.}$

Si se elige aleatoriamente (con probabilidad uniforme), entonces c ₁ ≠ 0 con probabilidad 1. Ahora, ${\displaystyle b_{0}}$

${\displaystyle {\begin{aligned}A^{k}b_{0}&=c_{1}A^{k}v_{1}+c_{2}A^{k}v_{2}+\cdots +c_{m}A^{k}v_{m}\\&=c_{1}\lambda _{1}^{k}v_{1}+c_{2}\lambda _{2}^{k}v_{2}+\cdots +c_{m}\lambda _{m}^{k}v_{m}\\&=c_{1}\lambda _{1}^{k}\left(v_{1}+{\frac {c_{2}}{c_{1}}}\left({\frac {\lambda _{2}}{\lambda _{1}}}\right)^{k}v_{2}+\cdots +{\frac {c_{m}}{c_{1}}}\left({\frac {\lambda _{m}}{\lambda _{1}}}\right)^{k}v_{m}\right)\\&\to c_{1}\lambda _{1}^{k}v_{1}&&\left|{\frac {\lambda _{j}}{\lambda _{1}}}\right|<1{\text{ for }}j>1\end{aligned}}}$

Por otro lado:

${\displaystyle b_{k}={\frac {A^{k}b_{0}}{\|A^{k}b_{0}\|}}.}$

Por lo tanto, converge a (un múltiplo de) el vector propio . La convergencia es geométrica , con razón ${\displaystyle b_{k}}$ ${\displaystyle v_{1}}$

${\displaystyle \left|{\frac {\lambda _{2}}{\lambda _{1}}}\right|,}$

donde 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. ${\displaystyle \lambda _{2}}$

Aplicaciones

Aunque el método de iteración de potencia se aproxima sólo a un valor propio de una matriz, sigue siendo útil para ciertos problemas computacionales . Por ejemplo, Google lo utiliza para calcular el PageRank de los documentos en su motor de búsqueda, ^[2] y Twitter lo utiliza para mostrar a los usuarios recomendaciones de 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, sino que puede acceder a una función que evalúa productos matriz-vector . Para matrices no simétricas que están bien condicionadas , 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 utiliza, ya que su velocidad de convergencia se puede aumentar fácilmente sin sacrificar el pequeño coste por iteración; véase, por ejemplo, la iteración de Lanczos y LOBPCG . ${\displaystyle A}$ ${\displaystyle Ax}$

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 la iteración de potencia a la matriz . Otros algoritmos observan todo el subespacio generado por los vectores . Este subespacio se conoce como el subespacio de Krylov . Puede calcularse mediante la iteración de Arnoldi o la iteración de Lanczos . La iteración de Gram ^[4] es un método superlineal y determinista para calcular el par propio más grande. ${\displaystyle A^{-1}}$ ${\displaystyle b_{k}}$

Véase también

• Iteración del cociente de Rayleigh
• Iteración inversa

Referencias

1. Richard von Mises y H. Pollaczek-Geiringer, Praktische Verfahren der Gleichungsauflösung , ZAMM - Zeitschrift für Angewandte Mathematik und Mechanik 9, 152-164 (1929).
2. Ipsen, Ilse y Rebecca M. Wills (5–8 de mayo de 2005). "7º Simposio internacional IMACS sobre métodos iterativos en computación científica" (PDF) . Instituto Fields, Toronto, Canadá.{{cite news}}: CS1 maint: multiple names: authors list (link)
3. Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang y Reza Bosagh Zadeh WTF: El sistema de a quién seguir en Twitter, Actas de la 22.ª conferencia internacional sobre la World Wide Web
4. Delattre, B.; Barthélemy, Q.; Araujo, A.; Allauzen, A. (2023), "Límite eficiente de la constante de Lipschitz para capas convolucionales mediante iteración de Gram", Actas de la 40.ª Conferencia internacional sobre aprendizaje automático