Tehomenetelmä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 8. huhtikuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 4 muokkausta .

Tehomenetelmä [1] tai tehoiteraatioiden menetelmä on iteratiivinen algoritmi, jolla löydetään ominaisarvo , jolla on maksimiabsoluuttinen arvo ja yksi vastaavista ominaisvektoreista mielivaltaiselle matriisille.

Algoritmi on yksinkertainen ja konvergoi geometrisen etenemisen nopeudella, jos kaikki ominaisarvot, joilla on suurin modulo, ovat samat, muuten konvergenssia ei ole. Absoluuttisesti lähellä olevilla ominaisarvoilla konvergenssi voi osoittautua hitaaksi. Koska algoritmi tiivistyy tietyn matriisin peräkkäiseen kertomiseen vektorilla, jos se toteutetaan oikein, se toimii hyvin suurille harvoille matriiseille .

Algoritmia ehdottivat vuonna 1929 Richard von Mises ja Hilda Geiringer [2] .

Algoritmi

Algoritmin alussa generoidaan satunnaisvektori [3] . Seuraavaksi suoritetaan peräkkäiset laskelmat iteratiivisen kaavan mukaan: $r_{0}$

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

[neljä]

Jos alkuperäinen vektori ei ole ortogonaalinen omaan aliavaruuteensa nähden, jolla on suurin modulo-ominaisarvo, niin etäisyys tämän sekvenssin elementeistä tällaiseen aliavaruuteen pyrkii olemaan nolla [5] . Vektorijono ei aina konvergoi, koska vektori voi vaihtaa etumerkkiä jokaisessa vaiheessa tai pyöriä kompleksisessa tapauksessa, mutta tämä ei estä valitsemasta yhtä vektoreista ominaisarvoksi, kun saadaan riittävän tarkka ominaisarvo.

Jakso

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

konvergoi modulo-ominaisarvon maksimiarvoon yllä olevassa ehdossa. Mutta muista, että kaikilla todellisilla matriiseilla ei ole todellisia ominaisarvoja.

Tavallisille käyttäjille

Erityisessä mutta tärkeässä normaalioperaattoreiden tapauksessa kaikki matriisin ominaisvektorit ovat keskenään ortogonaalisia. Tässä tapauksessa tehomenetelmän avulla voit löytää kaikki matriisin ominaisarvot ja vektorit.

Olkoon normalisoitu ominaisvektori, jolla on normaalioperaattorin matriisin suurin modulo-ominaisarvo . Sitten matriisi ${\displaystyle r_{k))$ $A$

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

säilyttää kaikki matriisin ominaisvektorit vektoria lukuun ottamatta ja sallii tehomenetelmän avulla etsiä seuraavan ominaisarvon, jonka ominaisarvo on suurin absoluuttisena arvona. $A$ ${\displaystyle r_{k))$

Konvergenssitodistus

Järjestetään ominaisarvot ei-nousevan itseisarvon mukaan ja oletetaan, että [6] . Sitten alkuvektori voidaan esittää muodossa ${\displaystyle \lambda _{1}>\lambda _{2}\geq ...\geq \lambda _{n))$

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

missä ovat ominaisvektorit, vektori asetetaan nollaan ensimmäisessä kertolaskussa matriisilla ja oletuksella. ${\displaystyle v_{i))$ $w$ $v_{1}\neq 0$

Harkitse matriisin kertolaskujen tulosta alkuvektorilla: $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})$ .

Jakamalla vasemman ja oikean puolen luvulla , saamme $\|R_{k}\|$

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

Sovellukset

Menetelmää käytetään ensisijaisesti harvoille matriiseille. Esimerkiksi Google käyttää sitä laskeakseen sivujen sijoituksia verkossa [7] ja Twitter suosittelee sitä "ketä seurata" [8] .

Muistiinpanot

↑ Rostislav. Chastkovin ongelma matriisin tehoarvoista. Tehomenetelmä (rajoittamaton) (27. helmikuuta 2015). Haettu 28. huhtikuuta 2022. Arkistoitu alkuperäisestä 10. heinäkuuta 2022.
↑ Richard von Mises ja H. Pollaczek-Geiringer, Praktische Verfahren der Gleichungsauflesung , ZAMM-Zeitschrift für Angewandte Mathematik und Mechanik 9, 152-164 (1929).
↑ Joissakin tapauksissa on mahdollista käyttää olemassa olevaa dominanttivektoriapproksimaatiota.
↑ Jako (normalisointi) tässä kaavassa on välttämätön vektorin koordinaattien nollaamisen tai ylivuodon poissulkemiseksi, ja likimäärin tunnetuilla ominaisarvoilla sitä ei tarvitse tehdä joka vaiheessa.
↑ Siinä tapauksessa, että suurimman itseisarvon omaava ominaisarvo on positiivinen reaaliluku, myös annettu vektoreiden sarja konvergoi johonkin ominaisvektoriin.
↑ Oletus on tehty laskelmien vähentämiseksi. Jos useat yhtenevät ominaisarvot, joilla on maksimimoduuli, todistus on samanlainen.
↑ Ipsen, Ilse ja Rebecca M. Wills . 7. IMACS International Symposium iterative Methods in Scientific Computing (5.–8. toukokuuta 2005). Arkistoitu alkuperäisestä 21. syyskuuta 2018. Haettu 10.7.2019.
↑ Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang ja Reza Bosagh Zadeh WTF: The who-to-follow -järjestelmä Twitterissä Arkistoitu 12. heinäkuuta 2019 Wayback Machinessa , Proceedings of the 22nd International Conference on World Wide web