Iteración de potencia

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

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 matrices.${\displaystyle A}$mediante un vector, por lo que resulta eficaz para una matriz dispersa muy grande con la implementación adecuada. La velocidad de convergencia es como${\displaystyle (\lambda _{2}/\lambda _{1})^{k}}$dónde${\displaystyle k}$es el número de iteraciones, y${\displaystyle \lambda _{1}}$y ${\displaystyle \lambda _{2}}$son, respectivamente, el autovalor de mayor valor absoluto y un autovalor de segundo mayor valor absoluto (véase una sección posterior ). En otras palabras, la convergencia es exponencial con base en la brecha espectral .

El algoritmo de iteración de potencia comienza con un vector${\displaystyle b_{0}}$, 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_{k+1}={\frac {Ab_{k}}{\lVert Ab_{k}\rVert }}}$

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

Si asumimos${\displaystyle A}$tiene un valor propio que es estrictamente mayor en magnitud que sus otros valores propios, es decir,

${\displaystyle \left\vert \lambda _{1}\right\vert >\left\vert \lambda _{2}\right\vert \geq \ldots \geq \left\vert \lambda _{n}\right\vert \geq 0}$

y el vector inicial${\displaystyle b_{0}}$tiene un componente distinto de cero en la dirección de un vector propio asociado con el valor propio dominante, entonces una subsecuencia${\displaystyle \left(b_{k}\right)}$converge a un vector propio asociado con el valor propio dominante.

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

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

dónde${\displaystyle v_{1}}$es un vector propio asociado con el valor propio dominante, y${\displaystyle \|r_{k}\|\rightarrow 0}$. La presencia del término${\displaystyle e^{i\phi _ {k}}}$implica que${\displaystyle \left(b_{k}\right)}$no converge a menos que${\displaystyle e^{i\phi _ {k}}=1}$Bajo las dos suposiciones enumeradas anteriormente, la secuencia${\displaystyle \left(\mu _{k}\right)}$definido por

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

converge al valor propio dominante (con cociente de Rayleigh ).

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

import numpy as npfrom numpy import typing as nptdef random_vector ( dimensión : int ) -> npt . NDArray [ np . float64 ]:rng = np.random.default_rng ( )​​​devolver rng.random ( dimensión )​​def método_de_potencia (R : npt . NDArray [ np . flotador64 ],num_iteraciones : int ,) -> tnp . NDArray [ np . flotador64 ]:Si A.forma [ 0 ] ! = A.forma [ 1 ] :​​generar ValueError ( "A debe ser una matriz cuadrada." )# Elija un vector inicial aleatorio para reducir la probabilidad# que sea ortogonal al vector propio dominante.b_k = vector_aleatorio ( A . forma [ 1 ])# Normalizar el vector inicial.b_k /= np . linalg . norm ( b_k )para _ en rango ( num_iteraciones ):# Multiplicar por la matriz.b_k1 = A @ b_k# Calcula la longitud del nuevo vector.b_k1_norm = np . linalg . norm ( b_k1 )# Detenerse si el nuevo vector está dentro de la precisión de la máquina de 0.Si np.isclose ( b_k1_norm , 0.0 ) :​generar ValueError ( "El método Power produjo el vector cero." )# Normaliza el vector para la siguiente iteración.b_k = b_k1 / b_k1_norm# Devuelve el vector propio dominante aproximado.devolver b_k

El vector${\displaystyle b_{k}}$converge a un vector propio asociado. Idealmente, se debería usar 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.

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

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

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

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

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

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

donde la expresión:${\displaystyle {\frac {A^{k+1}b_{0}}{\|A^{k+1}b_{0}\|}}}$se presta mejor al siguiente análisis:

${\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}\|}}\quad {\text{(since}}\,A\,{\text{is diagonalizable)}}\\&={\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${\displaystyle {\frac {1}{\lambda _{1}}}J_{i}}$es menor que 1 en magnitud, por lo tanto

${\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 }$

Utilizando este hecho,${\displaystyle b_{k}}$puede escribirse de una forma que enfatice su relación con${\displaystyle v_{1}}$cuando${\displaystyle k}$es grande:

${\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${\displaystyle e^{i\phi _{k}}=\left(\lambda _{1}/|\lambda _{1}|\right)^{k}}$y${\displaystyle \|r_{k}\|\to 0}$como${\displaystyle k\to \infty }$

La secuencia${\displaystyle \left(b_{k}\right)}$está acotada, por lo que contiene una subsecuencia convergente. Nótese que el vector propio correspondiente al valor propio dominante es único salvo por un escalar, por lo que, aunque la secuencia${\displaystyle \left(b_{k}\right)}$puede que no converja, ${\displaystyle b_{k}}$es casi un vector propio de${\displaystyle A}$para grandes${\displaystyle k}$.

Alternativamente, si${\displaystyle A}$Si es diagonalizable , entonces la siguiente demostración produce el mismo resultado:

Dejar${\displaystyle \lambda _{1},\lambda _{2},\ldots ,\lambda _{m}}$ser el${\displaystyle m}$valores propios (contados con multiplicidad) de${\displaystyle A}$en orden descendente de valor absoluto (se permiten igualdades), es decir${\displaystyle |\lambda _{1}|\geq |\lambda _{2}|\ldots \geq |\lambda _{m}|}$y dejar${\displaystyle v_{1},v_{2},\ldots ,v_{m}}$sean los vectores propios correspondientes. Supongamos que${\displaystyle \lambda _{1}}$es el valor propio dominante, de modo que${\displaystyle |\lambda _{1}|>|\lambda _{j}|}$a pesar de${\displaystyle j>1}$.

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

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

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

${\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,${\displaystyle b_{k}}$converge a (un múltiplo de) el vector propio${\displaystyle v_{1}}$La convergencia es geométrica , con razón

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

Por lo tanto, el método converge lentamente si existe un valor propio de magnitud cercana al valor propio dominante.

Aunque el método de iteración de potencias solo aproxima 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 sobre a quién seguir ^{[ 3 ]} . El método de iteración de potencias es especialmente adecuado para matrices dispersas , como la matriz web, o como método sin matriz que no requiere almacenar la matriz de coeficientes.${\displaystyle A}$explícitamente, pero en su lugar puede acceder a una función que evalúa productos matriz-vector${\displaystyle Ax}$Para matrices no simétricas bien condicionadas , el método de iteración de potencias puede superar a la iteración de Arnoldi, más compleja . Para matrices simétricas, el método de iteración de potencias se usa raramente, ya que su velocidad de convergencia se puede aumentar fácilmente sin sacrificar el pequeño costo por iteración; véase, por ejemplo, la iteración de Lanczos y LOBPCG .

Algunos de los algoritmos de autovalores 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.${\displaystyle A^{-1}}$Otros algoritmos analizan todo el subespacio generado por los vectores.${\displaystyle b_{k}}$Este subespacio se conoce como subespacio de Krylov . Se puede calcular 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.

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