Perronin ja Frobeniuksen lause
Tekijät
Päivämäärä
2023Tekijänoikeudet
© The Author(s)
Tässä tutkielmassa perehdytään matriisiteoriaan. Tarkastelu keskittyy neliömatriiseihin, niiden ominaisarvoihin ja niitä vastaaviin ominaisvektoreihin. Tarkastelu rajataan kahteen osaan, joista toiseen esitetään käytännönsovellus, jossa tarkastellaan Googlen hakukoneen toiminnan matemaattista taustaa.
Vaadittavien lineaarialgebran esitietojen jälkeen tarkastellaan positiivisia neliömatriiseja. Ensin esitellään aputuloksia liittyen positiivisiin matriiseihin, sekä niiden itseisarvoltaan suurimpaan ominaisarvoon eli spektraalisäteeseen ja tätä ominaisarvoa vastaavaan ominaisvektoriin. Näiden aputulosten tarkastelun jälkeen esitellään Perronin lause ja sille esitetään todistus. Perronin lause toteaa, että positiivisella neliömatriisilla on itseisarvoltaan suurin ominaisarvo, joka on aidosti suurempi kuin mikään muu matriisin ominaisarvojen itseisarvoista. Lisäksi lause toteaa, että tämän itseisarvoltaan suurimman ominaisarvon algebrallinen kertaluku on 1 ja sitä vastaava ominaisvektori on positiivinen.
Perronin lauseen todistuksen jälkeen perehdytään verkkoteoriaan, jonka avulla havainnollistetaan graafisesti tutkielman sovellusta. Verkkoteoriaan liittyvien määritelmien ja tulosten esittämisen jälkeen tarkastellaan differenssiyhtälöitä. Differenssiyhtälöissä ajan hetki $t$ liitetään ajanhetkeen $t+1$ lineaarisesti siten, että $Av_t=v_{t+1}$, missä neliömatriisia $A$ kutsutaan siirtymämatriisiksi.
Differenssiyhtälöissä keskitytään Markovin ketjuihin, jotka ovat todennäköisyyksiä kuvaavia differenssiyhtälöitä. Tällaisten differenssiyhtälöiden siirtymämatriisit ovat stokastisia matriiseja, jotka ovat ei-negatiivisia matriiseja ja niiden jokainen sarake summautuu luvuksi yksi. Stokastisten matriisien lisäksi Markovin ketjuissa esiintyvät vektorit $v_i$ ovat todennäköisyysvektoreita eli ei-negatiivisia vektoreita, joiden alkiot summautuvat luvuksi yksi.
Markovin ketjujen teoria toimii teoriapohjana Googlen Pagerank-algorit-mille, jossa sovelletaan Perronin lausetta. Määritellään Google-matriisi, joka on positiivinen stokastinen matriisi. Perronin lause takaa, että tämän matriisin spektraalisäde on luku 1 ja sen virittää positiivinen ominaisvektori, jota kutsutaan tasapainotilavektoriksi. Pagerank-algoritmissa tarkastellaan Markovin ketjua, jonka määrää Google-matriisi $G$ ja tasapainotilavektori $w$. Tällöin Markovin ketjun $Gv_t=v_{t+1}$ avulla saadaan internetin nettisivujen tärkeysjärjestys eli järjestys, jossa hakutulokset tulevat näkyviin hakukoneessa. Tämän tärkeysjärjestyksen kertoo Markovin ketjun vektori $v_{t+1}$.
Tutkielman lopuksi tarkastellaan Perronin lauseen yleistystä eli Perronin ja Frobeniuksen lausetta. Tämä lause antaa vastaavat tulokset kuin Perronin lause, koskien ei-negatiivisia redusoitumattomia matriiseja.
Tarkoituksena on esitellä Perronin ja Frobeniuksen lauseen yleinen versio. Tämän jälkeen esitellään ja todistetaan kyseisen lauseen erikoistapaus, jossa tarkastellaan ei-negatiivisia redusoitumattomia neliömatriiseja, joiden jokin positiivinen kokonaislukupotenssi on positiivinen neliömatriisi. Tämä erikoistapaus toteaa vastaavat tulokset, kuin yleinen Perronin ja Frobeniuksen lause.
...
Asiasanat
Metadata
Näytä kaikki kuvailutiedotKokoelmat
- Pro gradu -tutkielmat [29747]
Lisenssi
Samankaltainen aineisto
Näytetään aineistoja, joilla on samankaltainen nimeke tai asiasanat.
-
Googlen PageRankin matematiikka
Hirvelä, Juulia (2023)Tämän tutkielman tarkoituksena on esitellä matematiikkaa, johon Googlen hakutulosten järjestämiseen käyttämä PageRank-algoritmi perustuu. Tutkielmassa hyödynnetään lineaarialgebran, graafien ja Markovin ketjujen teorian ... -
Matriisihajotelmia
Koskimäki, Saaga (2023)Tämän tutkielman tarkoituksena on tarkastella matriisin kolmea erilaista hajotelmaa. Matriisihajotelmien avulla matriisi voidaan esittää hyödyllisessä muodossa muita tuloksia varten. Tutkielmassa perehdytään matriisin ... -
Kompleksiset vektoriavaruudet
Särkijärvi, Tuomas (2020)Tässä matematiikan pro gradu -tutkielmassa perehdytään kompleksisiin vektoriavaruuksiin ja sivutaan myös niiden sovelluskohteita. Tutkielman tavoitteena on esitellä riittävät tiedot, jotta lukija voi muodostaa eheän ... -
Matriisin Hessenbergin muoto
Holopainen, Niko (2013) -
Matriisin singulaariarvohajotelma
Kirsilä, Jaakko (2021)Tämän tutkielman tarkoituksena on esitellä ja todistaa matriisin singulaariarvohajotelma, jonka mukaan jokainen m x n matriisi A voidaan esittää muodosssa A=USV^T, missä matriisit U ja V ovat ortogonaalisia ja S on ...
Ellei toisin mainittu, julkisesti saatavilla olevia JYX-metatietoja (poislukien tiivistelmät) saa vapaasti uudelleenkäyttää CC0-lisenssillä.