Teljesítmény módszer

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. április 8-án felülvizsgált verziótól ; az ellenőrzések 4 szerkesztést igényelnek .

A hatványmódszer [1] , vagy a hatványiterációk módszere egy iteratív algoritmus a maximális abszolút értékű sajátérték és a megfelelő sajátvektorok egyikének megtalálására tetszőleges mátrixhoz.

Az algoritmus egyszerű, és egy geometriai progresszió sebességével konvergál, ha minden sajátérték egybeesik a maximális modulóval, különben nincs konvergencia. Abszolút értékben közeli sajátértékeknél a konvergencia lassúnak bizonyulhat. Tekintettel arra, hogy az algoritmus egy adott mátrix vektorral való szekvenciális szorzására vezet le, helyesen végrehajtva jól működik nagy ritka mátrixok esetén .

Az algoritmust 1929-ben Richard von Mises és Hilda Geiringer javasolta [2] .

Algoritmus

Az algoritmus elején egy véletlen vektort generál [3] . Ezután szekvenciális számításokat hajtanak végre az iteratív képlet szerint: $r_{0}$

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

[négy]

Ha az eredeti vektor nem merőleges a legnagyobb modulo-sajátértékkel rendelkező saját alterére, akkor ennek a sorozatnak az elemeitől az ilyen altérhez való távolság nullára hajlik [5] . A vektorok sorozata nem mindig konvergál, mivel a vektor minden lépésben előjelet válthat, vagy összetett esetben elfordulhat, de ez nem akadályozza meg, hogy kellően pontos sajátérték elérése esetén valamelyik vektort sajátértékként válasszuk.

Utóbbi

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

a fenti feltétel mellett konvergál a maximális modulo sajátértékhez. De ne feledje, hogy nem minden valós mátrixnak van valós sajátértéke.

Normál operátoroknak

A normál operátorok egy különleges, de fontos esetben az összes mátrix sajátvektora egymásra merőleges. Ebben az esetben a teljesítménymódszer lehetővé teszi a mátrix összes sajátértékének és vektorának megtalálását.

Legyen egy normalizált sajátvektor a normál operátor mátrixának maximális modulo sajátértékével. Aztán a mátrix ${\displaystyle r_{k))$ $A$

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

megőrzi a mátrix összes sajátvektorát , kivéve a vektort , és lehetővé teszi a hatványmódszer használatával, hogy megkeressük a következő sajátvektort a maximális sajátértékkel abszolút értékben. $A$ ${\displaystyle r_{k))$

Konvergenciabizonyítás

Tegyük sorba a sajátértékeket nem növekvő abszolút érték szerint, és tegyük fel, hogy [6] . Ekkor a kezdeti vektort így lehet ábrázolni ${\displaystyle \lambda _{1}>\lambda _{2}\geq ...\geq \lambda _{n))$

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

ahol a sajátvektorok vannak, a vektort nullára állítjuk az első szorzáskor a mátrixszal és feltételezéssel. ${\displaystyle v_{i))$ $w$ $v_{1}\neq 0$

Tekintsük a mátrixszorzás eredményét a kezdeti vektorral: $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})$ .

A bal és a jobb oldalt elosztva -vel , azt kapjuk $\|R_{k}\|$

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

Alkalmazások

A módszert elsősorban ritka mátrixokra alkalmazzák. Például a Google ezt használja az oldalak rangsorolásának kiszámítására a weben [7] , a Twitter pedig arra, hogy „kit kövessünk” [8] ajánlására .

Jegyzetek

↑ Rosztiszlav. Chastkov problémája a mátrix teljesítményértékeivel kapcsolatban. Hatalommódszer (határozatlan) (2015. február 27.). Letöltve: 2022. április 28. Az eredetiből archiválva : 2022. július 10.
↑ Richard von Mises és H. Pollaczek-Geiringer, Praktische Verfahren der Gleichungsauflesung , ZAMM-Zeitschrift für Angewandte Mathematik und Mechanik 9, 152-164 (1929).
↑ Bizonyos esetekben lehetőség van a meglévő domináns sajátvektor-közelítés használatára.
↑ Ebben a képletben az osztás (normalizálás) szükséges a vektorkoordináták nullázásának vagy túlcsordulásának kizárásához, és megközelítőleg ismert sajátértékek esetén nem szükséges ezt minden lépésben megtenni.
↑ Abban az esetben, ha a legnagyobb abszolút értékű sajátérték pozitív valós szám, akkor az adott vektorsorozat is konvergál valamilyen sajátvektorhoz.
↑ A feltételezés a számítások csökkentését szolgálja. Több egybeeső maximális modulusú sajátérték esetén a bizonyítás hasonló.
↑ Ipsen, Ilse és Rebecca M. Wills . 7. IMACS Nemzetközi Szimpózium az iteratív módszerekről a tudományos számítástechnikában (2005. május 5–8.). Archiválva az eredetiből 2018. szeptember 21-én. Letöltve: 2019. július 10.
↑ Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang és Reza Bosagh Zadeh WTF: The who-to-follow rendszer a Twitteren Archiválva 2019. július 12-én a Wayback Machine - nél web