Perronin ja Frobeniuksen lause
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.
...
Keywords
Metadata
Show full item recordCollections
- Pro gradu -tutkielmat [29685]
License
Related items
Showing items with similar title or keywords.
-
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 ... -
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 ... -
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 ... -
Matriisin Hessenbergin muoto
Holopainen, Niko (2013) -
Itsetarkistuvat STACK-tehtävät kurssille Lineaarinen algebra ja geometria 1
Räihä, Sauli (2019)Tässä pro gradu -tutkielmassa esitellään Jyväskylän yliopiston matematiikan ja tilastotieteen laitoksella luennoitavalle kurssille Lineaarinen algebra ja geometria 1 luotu STACK-tehtäväkokoelma ja työprosessin eri vaiheita. ...