Power iteration

Inom matematik är potens iteration (även känd som potensmetoden ) en egenvärdesalgoritm : givet en diagonaliserbar matris $A$ kommer algoritmen att producera ett tal ${\displaystyle \lambda } ,$ som är det största (i absoluta tal) värde) egenvärde för $A$ , och en vektor som inte är noll $v$ , som är en motsvarande egenvektor för ${\displaystyle \lambda } ,$ det vill säga $Av=\ lambda v$ . Algoritmen är också känd som Von Mises-iterationen .

Power iteration är en mycket enkel algoritm, men den kan konvergera långsamt. Den mest tidskrävande operationen av algoritmen är multiplikationen av matris $A$ med en vektor, så den är effektiv för en mycket stor gles matris med lämplig implementering.

Metoden

Animation som visualiserar kraftiterationsalgoritmen på en 2x2-matris. Matrisen avbildas av sina två egenvektorer. Felet beräknas som $||{\text{approximation}}-{\text{största egenvektorn}}||$

Power iterationsalgoritmen börjar med en vektor $b_{0}$ , som kan vara en approximation till den dominerande egenvektorn eller en slumpmässig vektor. Metoden beskrivs av återfallsrelationen

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

multipliceras vektorn ${\displaystyle b_{k}} med matrisen$$A$ och normaliseras.

Om vi ​​antar att $A$ har ett egenvärde som är strikt större i magnitud än dess andra egenvärden och startvektorn $b_{0}$ har en komponent som inte är noll i riktning mot en egenvektor som är associerad med det dominanta egenvärdet , då konvergerar en undersekvens $\left(b_{k}\right)$ till en egenvektor som är associerad med det dominanta egenvärdet.

konvergerar inte sekvensen ${\displaystyle \left(b_{k}\right)} nödvändigtvis.$ I denna sekvens,

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

där $v_{1}$ är en egenvektor associerad med det dominanta egenvärdet, och $\|r_{k}\|\högerpil 0$ . Närvaron av termen $e^{i\phi _{k}}$ antyder att $\left(b_{k}\right)$ inte konvergerar om inte $e^{i\phi _{k}}=1$ . Under de två antaganden som anges ovan definieras sekvensen ${\displaystyle \left(\mu _{k}\right)} av$

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

konvergerar till det dominanta egenvärdet (med Rayleigh-kvoten ) .

Man kan beräkna detta med följande algoritm (visas i Python med NumPy):

   

   
    
    
    
      

       
        
           

        
          

        
            

     

     #!/usr/bin/env python3  importera  numpy  som  np  def  power_iteration  (  A  ,  num_iterations  :  int  ):  # Välj helst en slumpmässig vektor  # För att minska chansen att vår vektor  # är ortogonal mot egenvektorn  b_k  =  np  .  slumpmässigt  .  rand  (  A.  form  [  1  ])  för  _  i  intervallet  (  antal_iterationer  ):  # beräkna matris-för-vektor-produkten  Ab  b_k1  =  np  .  dot  (  A  ,  b_k  )  # beräkna normen  b_k1_norm  =  np  .  linalg  .  norm  (  b_k1  )  # åternormalisera vektorn  b_k  =  b_k1  /  b_k1_norm  return  b_k  power_iteration  (  np  .  array  ([[  0.5  ,  0.5  ],  [  0.2  ,  0.8  ]]),  10  ) 

Vektorn $b_{k}$ till en associerad egenvektor. Helst bör man använda Rayleigh-kvoten för att få det associerade egenvärdet.

Denna algoritm används för att beräkna Google PageRank .

Metoden kan också användas för att beräkna spektralradien ( egenvärdet med den största magnituden, för en kvadratisk matris) genom att beräkna Rayleigh-kvoten

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

Analys

Låt $A$ brytas upp i sin Jordan-kanoniska form : $A=VJV^{-1}$ , där den första kolumnen i $V$ är en egenvektor för $A$ som motsvarar det dominanta egenvärdet $\lambda _{1}$ . Eftersom det dominerande egenvärdet för ${\displaystyle A} är unikt$ är det första Jordan-blocket i $J$$1\times 1$ matrisen $[\lambda _{1}],$ där $\lambda _{1}$ är det största egenvärdet för A i magnitud. Startvektorn $b_{0}$ kan skrivas som en linjär kombination av kolumnerna i V :

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

Enligt antagandet har $b_{0}$ en komponent som inte är noll i riktning mot det dominanta egenvärdet, så $c_{1}\neq 0$ .

Den beräkningsmässigt användbara upprepningsrelationen för $b_{k+1}$ kan skrivas om som:

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

där uttrycket: ${\frac {A^{k+1}b_{0}}{\|A^{k+1}b_{0}\ |}}$ är mer mottaglig för följande analys.

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

Uttrycket ovan förenklas som $k\to \infty$

$\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 .$

Gränsen följer av det faktum att egenvärdet för ${\frac {1}{\lambda _{1}}}J_{i}$ är mindre än 1 i storleken, så

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

Det följer att:

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

Med detta faktum kan $b_{k}$ skrivas i en form som understryker dess relation till $v_{1}$ när k är stor:

${\begin{aligned}b_{k}&=\left({\frac {\lambda _{1}}{|\lambda _{1}|}}\ höger)^{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\höger)^{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är $e^{i\phi _{k}}=\left(\lambda _{1}/|\lambda _{1}|\ höger)^{k}$ och $\|r_{k}\|\to 0$ som $k\to \infty$

Sekvensen $\left(b_{k}\right)$ är avgränsad, så den innehåller en konvergent undersekvens. Observera att egenvektorn som motsvarar det dominanta egenvärdet endast är unik upp till en skalär, så även om sekvensen ( $\displaystyle \left(b_{k}\right)}$ kanske inte konvergerar, $b_{ k}$ är nästan en egenvektor till A för stor k .

Alternativt, om A är diagonaliserbar , ger följande bevis samma resultat

Låt λ ₁ , λ ₂ , ..., λ _m vara m egenvärdena (räknade med multiplicitet) för A och låt v ₁ , v ₂ , ..., v _m vara motsvarande egenvektorer. Antag att $\lambda _{1}$ är det dominanta egenvärdet, så att $|\lambda _{1}|>|\lambda _{j}|$ för $j>1$ .

Den initiala vektorn $b_{0}$ kan skrivas:

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

Om $b_{0}$ väljs slumpmässigt (med enhetlig sannolikhet), då c ₁ ≠ 0 med sannolikhet 1 . Nu,

${\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{ för }}j>1\end{aligned}}$

Å andra sidan:

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

Därför konvergerar $b_{k}$ till (en multipel av) egenvektorn $v_{1}$ . Konvergensen är geometrisk , med förhållande

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

där $\lambda _{2}$ anger det andra dominanta egenvärdet. Således konvergerar metoden långsamt om det finns ett egenvärde nära det dominerande egenvärdet i storlek.

Ansökningar

Även om power iterationsmetoden endast approximerar ett egenvärde av en matris, förblir den användbar för vissa beräkningsproblem . Till exempel Google den för att beräkna PageRank för dokument i deras sökmotor, och Twitter använder den för att visa användarnas rekommendationer om vilka de ska följa. Power iteration-metoden är särskilt lämplig för glesa matriser , såsom webbmatrisen, eller som den matrisfria metoden som inte kräver att koefficientmatrisen $A$ explicit lagras, utan istället kan komma åt en funktionsutvärderande matrisvektor produkter $Ax$ . För icke-symmetriska matriser som är välkonditionerade kan power iterationsmetoden överträffa mer komplex Arnoldi iteration . För symmetriska matriser används effektiterationsmetoden sällan, eftersom dess konvergenshastighet lätt kan ökas utan att offra den lilla kostnaden per iteration; se t.ex. Lanczos iteration och LOBPCG .

Några av de mer avancerade egenvärdesalgoritmerna kan förstås som variationer av effektiterationen. Till exempel tillämpar den inversa iterationsmetoden potensiteration på matrisen $A^{-1}$ . Andra algoritmer tittar på hela delutrymmet som genereras av vektorerna $b_{k}$ . Detta underrum är känt som Krylov-underrummet . Det kan beräknas med Arnoldi iteration eller Lanczos iteration .

Se även

• Rayleigh kvot iteration
• Omvänd iteration