Iteración de energía

Algoritmo de valores propios

En matemáticas , la iteración de potencia (también conocida como método de potencia ) es un algoritmo de valores propios : 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 del algoritmo que consume más tiempo es la multiplicación de una matriz por un vector, por lo que es eficaz para una matriz dispersa muy grande con la implementación adecuada. La velocidad de convergencia es como (ver una sección posterior). En palabras, la convergencia es exponencial siendo la base 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 está representada por 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 ). ^{[ se necesita aclaración ]}

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_iterations :  int ):  # Lo ideal es elegir un vector aleatorio  # Para disminuir la posibilidad de que nuestro vector  # sea ortogonal al vector propio  b_k  =  np . aleatorio . rand ( A . forma [ 1 ]) para  _  dentro del  rango ( num_iterations ):  # calcular el producto matriz por vector Ab  b_k1  =  np . punto ( A ,  b_k ) # calcular la norma  b_k1_norm  =  np . nalg . norma ( b_k1 ) # volver a normalizar el vector  b_k  =  b_k1  /  b_k1_norm regresar  negropower_iteration ( np . matriz ([[ 0.5 ,  0.5 ],  [ 0.2 ,  0.8 ]]),  10 )

El vector converge a un vector propio asociado. Idealmente, se debería utilizar el cociente de Rayleigh para obtener el valor propio asociado. ${\displaystyle b_{k}}$

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 magnitud más grande, 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}}}={\frac {b_{k+1}^{\top }b_{k}}{b_{k}^{\top }b_{k}}}.}$

Análisis

Descompongamos 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 es la matriz donde se encuentra 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 deriva 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 de una forma que enfatice su relación 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}}}$

donde 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. 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 grande . ${\displaystyle \left(b_{k}\right)}$ ${\displaystyle \left(b_{k}\right)}$ ${\displaystyle b_{k}}$

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

Sean λ ₁ , λ ₂ , ..., λ _m los m valores propios (contados con multiplicidad) de A y sean v ₁ , v ₂ , ..., v _m los correspondientes vectores propios. Supongamos que ese 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 al azar (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 aproxima solo un valor propio de una matriz, sigue siendo útil para ciertos problemas computacionales . 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 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 costo por iteración; consulte, 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 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 la iteración de Arnoldi o la iteración de Lanczos . La iteración de gramos ^[4] es un método superlineal y determinista para calcular el par propio más grande. ${\displaystyle A^{-1}}$ ${\displaystyle b_{k}}$

Ver 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 a 8 de mayo de 2005). "Séptimo 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 a quién seguir en Twitter, Actas de la 22ª conferencia internacional en 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 gramos", Actas de la 40.ª Conferencia internacional sobre aprendizaje automático