Effektmetod

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 8 april 2021; kontroller kräver 4 redigeringar .

Effektmetoden [1] , eller metoden för potensiterationer , är en iterativ algoritm för att hitta ett egenvärde med det maximala absoluta värdet och en av de motsvarande egenvektorerna för en godtycklig matris.

Algoritmen är enkel och konvergerar med en hastighet av en geometrisk progression om alla egenvärden med maximal modulo sammanfaller, annars finns det ingen konvergens. För egenvärden nära i absolut värde kan konvergensen visa sig vara långsam. På grund av det faktum att algoritmen kokar ner till sekventiell multiplikation av en given matris med en vektor, om den implementeras korrekt, fungerar den bra för stora glesa matriser .

Algoritmen föreslogs 1929 av Richard von Mises och Hilda Geiringer [2] .

Algoritm

I början av algoritmen genereras en slumpmässig vektor [3] . Därefter utförs sekventiella beräkningar enligt den iterativa formeln: $r_{0}$

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

[fyra]

Om den ursprungliga vektorn inte är ortogonal mot sitt eget delrum med det största moduloegenvärdet, tenderar avståndet från elementen i denna sekvens till ett sådant delrum till noll [5] . Sekvensen av vektorer konvergerar inte alltid, eftersom vektorn kan byta tecken vid varje steg eller rotera i det komplexa fallet, men detta hindrar inte att man väljer en av vektorerna som ett egenvärde när ett tillräckligt exakt egenvärde erhålls.

Efterföljd

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

konvergerar till det maximala modulo-egenvärdet under ovanstående villkor. Men kom ihåg att inte alla reella matriser har reella egenvärden.

För normala operatörer

I ett speciellt men viktigt fall med normala operatorer är alla matrisegenvektorer ömsesidigt ortogonala. I det här fallet låter kraftmetoden dig hitta alla matrisens egenvärden och vektorer.

Låta vara en normaliserad egenvektor med det maximala modulo-egenvärdet för matrisen för normaloperatorn. Sedan matrisen ${\displaystyle r_{k))$ $A$

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

bevarar alla egenvektorer i matrisen , förutom vektorn , och tillåter användning av potensmetoden för att söka efter nästa egenvektor med det maximala egenvärdet i absolut värde. $A$ ${\displaystyle r_{k))$

Konvergensbevis

Låt oss ordna egenvärdena efter icke-ökande absolutvärde och anta att [6] . Då kan den initiala vektorn representeras som ${\displaystyle \lambda _{1}>\lambda _{2}\geq ...\geq \lambda _{n))$

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

var är egenvektorerna, vektorn sätts till noll vid den första multiplikationen med matrisen och genom antagande. ${\displaystyle v_{i))$ $w$ $v_{1}\neq 0$

Betrakta resultatet av matrismultiplikationer med den initiala vektorn: $k$

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

Dela vänster och höger sida med , vi får $\|R_{k}\|$

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

Applikationer

Metoden används främst för glesa matriser. Till exempel använder Google det för att beräkna sidrankningar på webben [7] och Twitter använder det för att rekommendera "vem man ska följa" [8] .

Anteckningar

↑ Rostislav. Chastkovs problem med matrisens effektvärden. Effektmetod (obestämd) (27 februari 2015). Hämtad 28 april 2022. Arkiverad från originalet 10 juli 2022.
↑ Richard von Mises och H. Pollaczek-Geiringer, Praktische Verfahren der Gleichungsauflesung , ZAMM-Zeitschrift für Angewandte Mathematik und Mechanik 9, 152-164 (1929).
↑ I vissa fall är det möjligt att använda den existerande dominanta egenvektorapproximationen.
↑ Division (normalisering) i denna formel är nödvändig för att utesluta nollställning eller översvämning av vektorkoordinaterna, och med ungefär kända egenvärden är det inte nödvändigt att göra det vid varje steg.
↑ I det fall när egenvärdet med det största absolutvärdet är ett positivt reellt tal, konvergerar den givna vektorsekvensen också till någon egenvektor.
↑ Antagandet görs för att reducera beräkningar. I fallet med flera sammanfallande egenvärden med maximal modul är beviset liknande.
↑ Ipsen, Ilse och Rebecca M. Wills . 7:e IMACS International Symposium on Iterative Methods in Scientific Computing (5–8 maj 2005). Arkiverad från originalet den 21 september 2018. Hämtad 10 juli 2019.
↑ Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang och Reza Bosagh Zadeh WTF: The who-to-follow-systemet på Twitter Arkiverad 12 juli 2019 på Wayback Machine , Proceedings of the 22nd international conference on World Wide webb