Matematik
Konvergens af Markov matrix
Hej. Jeg arbejder pt. med min SRO om Markov matricer og Google's PageRank algoritme. Jeg er nået til det punkt hvor page rank vektoren skal beregnes vha. af en iterativ metode, som er den dominerende egenvektor til egenværdien 1 for ligningen
Ax = λx <=> Ax = x.
Hvis vi nu siger at vores netværk består af 4 sider, så antages det at deres vigtighed er uniformt fordelt, dvs. mit start gæt lyder som
x0 = [0.25, 0.25, 0.25, 0.25]
Jeg kan nu bestemme hvilken dominant egenvektor ligningen konvergerer imod ved at lade k → ∞ i ligningen
lim_{ k→∞} Akx0 = x,
hvor x er den dominerende egenvektor (PageRank vektoren). Følgende kan let bestemmes i Maple vha. af nedenstående løkke
for k from 0 to 10 do
A^k.x_0
od;
Hvilket giver os PageRank vektoren. Mit spørgsmål er så: er der en måde, hvorpå man teoretisk kan vise, hvilken dominant egenvektor systemet vil konvergere imod?
Mvh. Jonas
Svar #1
01. februar 2013 af peter lind
Jeg kender ikke pagerank vektoren; men der kan siges noget generelt ud fra numerisk analyse.
Du har en matrix A med m egenvektorer med egenværdierne λ1, λ2•••λm
Hvis du starter med en vilkårlig x vil den kunne skrives som en linearkombination af egenvektorerne x1, x2, ....xm altså
x= a1x1+a2x2+ .... amxm
Der gælder så Ax = λ1*a1x1+ λ2*a2x2+•••λmamxm
Hvis du gentager dette k gange vil du få
Akx = λ1k*a1x1+ λ2k*a2x2+•••λmkamxm
Hvis for eks den første egenværdi er den største altså λ1 > λi vil (λ1/λi)k kunne blive vilkårlig stor og egenvektoren og egenværdien vil dominere.
Hvis den vektor du startede med ikke havde en komponent i retning efter den største egenvektor (a1=0) vil regneunøjagtigheder i praksis medfører at du alligevel ender med den dominerende egenvektor
Svar #2
01. februar 2013 af JonasMcc (Slettet)
Du skal have mange tak. Det var præcist, hvad jeg ledte efter - smukt!
Skriv et svar til: Konvergens af Markov matrix
Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk?
Klik her for at oprette en bruger.
