Metoda de putere

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 8 aprilie 2021; verificările necesită 4 modificări .

Metoda puterii [1] , sau metoda iterațiilor de putere , este un algoritm iterativ pentru găsirea unei valori proprii cu valoarea absolută maximă și unul dintre vectorii proprii corespunzători pentru o matrice arbitrară.

Algoritmul este simplu și converge cu o rată de progresie geometrică dacă toate valorile proprii cu modulo maxim coincid, altfel nu există convergență. Pentru valorile proprii apropiate în valoare absolută, convergența se poate dovedi a fi lentă. Datorită faptului că algoritmul se rezumă la înmulțirea secvențială a unei matrice date cu un vector, dacă este implementat corect, funcționează bine pentru matrice rare și mari .

Algoritmul a fost propus în 1929 de Richard von Mises și Hilda Geiringer [2] .

Algoritm

La începutul algoritmului, se generează un vector aleator [3] . În continuare, calculele secvențiale sunt efectuate conform formulei iterative: $r_{0}$

r_{k+1}={\frac {Ar_{k}}{\|Ar_{k}\|}}

[patru]

Dacă vectorul original nu este ortogonal cu propriul său subspațiu cu cea mai mare valoare proprie modulo, atunci distanța de la elementele acestei secvențe la un astfel de subspațiu tinde spre zero [5] . Secvența de vectori nu converge întotdeauna, deoarece vectorul poate schimba semnul la fiecare pas sau se poate roti în cazul complex, dar acest lucru nu împiedică alegerea unuia dintre vectori ca valoare proprie atunci când se obține o valoare proprie suficient de precisă.

Urmare

\mu _{k}={\frac {r_{k}^{T}Ar_{k}}{r_{k}^{T}r_{k}}}={\frac {(r_{ k},Ar_{k})}{(r_{k},r_{k})}}

converge la valoarea proprie modulo maximă în condiția de mai sus. Dar amintiți-vă că nu toate matricele reale au valori proprii reale.

Pentru operatorii normali

Într-un caz particular, dar important al operatorilor normali, toți vectorii proprii matrici sunt reciproc ortogonali. În acest caz, metoda puterii vă permite să găsiți toate valorile proprii și vectorii matricei.

Fie un vector propriu normalizat cu valoarea proprie maximă modulo a matricei operatorului normal. Apoi matricea $r_{k)$ $A$

A_{1}=A-\lambda r_{k}r_{k}^{T)

păstrează toți vectorii proprii ai matricei , cu excepția vectorului și permite utilizarea metodei puterii pentru a căuta următorul vector propriu cu valoarea proprie maximă în valoare absolută. $A$ $r_{k)$

Dovada de convergență

Să ordonăm valorile proprii după valoare absolută necrescătoare și să presupunem că [6] . Atunci vectorul inițial poate fi reprezentat ca $\lambda _{1}>\lambda _{2}\geq ...\geq \lambda _{n)$

r_{0}=\sum _{i=1}^{n}v_{i}+w

unde sunt vectorii proprii, vectorul este setat la zero la prima înmulțire cu matrice și prin presupunere. $v_{i)$ $w$ $v_{1}\neq 0$

Luați în considerare rezultatul înmulțirilor de matrice cu vectorul inițial: $k$

$R_{k}=A^{k}(\sum _{i=1}^{n}v_{i}+w)=\sum _{i=1}^{n}{\lambda _ {i}^{k}v_{i}}={\lambda _{1}}^{k}(v_{1}+O(({\frac {\lambda _{2}}{\lambda _{ 1}}})^{k})$ .

Împărțind părțile stânga și dreaptă la , obținem $\|R_{k}\|$

r_{k}=\lambda _{1}{\frac {v_{1}}{\|\lambda _{1}v_{1}\|}}+O(({\frac {\lambda _{2}}{\lambda _{1}}}})^{k}).

Aplicații

Metoda este utilizată în primul rând pentru matrici rare. De exemplu, Google îl folosește pentru a calcula rangul paginilor de pe web [7] , iar Twitter îl folosește pentru a recomanda „pe cine să urmărească” [8] .

Note

↑ Rostislav. Problema lui Chastkov a valorilor puterii matricei. Metoda puterii (nedeterminată) (27 februarie 2015). Preluat la 28 aprilie 2022. Arhivat din original la 10 iulie 2022.
↑ Richard von Mises și H. Pollaczek-Geiringer, Praktische Verfahren der Gleichungsauflesung , ZAMM-Zeitschrift für Angewandte Mathematik und Mechanik 9, 152-164 (1929).
↑ În unele cazuri, este posibil să se utilizeze aproximarea vectorului propriu dominant existent.
↑ Împărțirea (normalizarea) în această formulă este necesară pentru a exclude repunerea la zero sau depășirea coordonatelor vectoriale, iar cu valori proprii aproximativ cunoscute, nu este necesar să o faceți la fiecare pas.
↑ În cazul în care valoarea proprie cu cea mai mare valoare absolută este un număr real pozitiv, șirul dat de vectori converge de asemenea către un vector propriu.
↑ Ipoteza este făcută pentru a reduce calculele. În cazul mai multor valori proprii care coincid cu modul maxim, demonstrația este similară.
↑ Ipsen, Ilse și Rebecca M. Wills . Al 7-lea Simpozion Internațional IMACS privind metodele iterative în calculul științific (5–8 mai 2005). Arhivat din original pe 21 septembrie 2018. Preluat la 10 iulie 2019.
↑ Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang și Reza Bosagh Zadeh WTF: The who-to-follow system at Twitter Arhivat 12 iulie 2019 la Wayback Machine , Proceedings of the 22nd international Conference on World Wide Web