Normat 51:3, 119–131 (2003) 119
Matematikk og informasjonssøking
på nettet
D. Laksov
Matematiska Institutionen, KTH
SE–100 44 Stockholm
laksov@math.kth.se
Innledning
1
Matematikken spiller en fundamental rolle for nesten alle funksjoner i datamaski-
ner, og for all elektronisk kommunikasjon. Vi skal illustrere dette ved å forklare
hvordan matematikken brukes i informasjonssøking på nettet. En av de forbausen-
de egenskapene med denne anvendelsen er at matematikken har størst betydning
når det gjelder å avgjøre hvilke nettsider som er «viktigst» blandt de nettsidene
som inneholder samme informasjon. Det vil si, matematikken er sentral nettopp i
den delen av søkeprosessen d er det virker som om smak og subjektiv bedømning
spiller en vesentlig rolle. Dette viser hvordan matematikken trenger gjennom pro-
blemer der det er mange uoversiktlige faktorer som gjensidig påvirker hverandre,
og hvordan den gir en klar og objektiv analyse av situasjonen.
Vi skal vise hvordan problemet med å rangordne nettsider blir løst ved enk-
le, velkjente og klassiske matematiske ligninger, takket være en genial idé og god
kjennskap til hvordan nettet fungerer. Ettersom ligningssystemene er så store, med
veldige mengder variable behøves det spesielle metoder for å løse dem effektivt.
Metoden for å løse disse ligningene bygger på res ultater fra begynne lsen av nitten-
hundretallet. Det er interessant at disse metodene bare gjelder under betingelser
som vi ikke kan vise er oppfylt for de ligninger vi vil behandle. I praksis funge-
rer imidlertid metodene utmerket. Dette viser at matematikken er til nytte selv
i tilfellene der alle de tekniske matematiske detaljene ikke har noen betydning.
Matematikken forteller i hvilken retning vi skal lete for å løse problemene som
oppstår.
1
En varm takk til Tommy Ekola (KTH) for all hjelp med denne artikkelen.
laksov.tex,v 1.6
120 D. Laksov Normat 3/2003
De viktigste delene av denne artikkelen bør være forståelige for lesere med vanlige
matematikkunnskaper fra gymnaset. I avsnitt 3 har vi tatt med noe mer krevende
matematiske resultater.
1. Informasjonssøking på nettet
1.1 Nettlesere. En av de viktigste anvendelsene av datamaskiner er å søke in-
formasjon på nettet. I dag har nesten alle tilgang til en nettleser, som Explorer,
Mozilla, Netscape, eller Opera, og med disse programmene får man tilgang til en
rekke ulike søkemotorer, som Alta Vista, Google, Lycos, eller Yahoo. Tatt i betrakt-
ning at det i dag finnes mer enn 3 milliarder
2
nettsider spredt over hele verden,
og mange av dem inneholder store mengder med dokumenter er det vanskelig å
fatte at det er mulig å lete gjennom disse enorme datamengdene, og på bare noen
sekunder komme opp med de viktigste nettsidene som inneholder informasjonen
vi søker. En oppmerksom bruker vil oppdage at det er betydelige forskjeller mel-
lom de ulike søkemotorene, både når det gjelder hastighet og den informasjonen
de finner. For å forstå forskjellen mellom programmene og hvordan det er mulig å
oppnå slike søkehastigheter er det nødvendig å kjenne til prinsippene og teoriene
bak programmene.
Som så ofte når det g je lder viktige tekniske anvendelser, og spesielt når det
gjelder verktøyene som hjelper oss å bruke nettet, så er det matematiske resultater
og formler som ligger til grunn for anvendelsene, og som forklarer hvordan en slik
effektivitet og presisjon er mulig. Det er også karakteristisk for slike anvendelser
at den matematikken som brukes er klassisk og ble funnet uten tanke på disse
anvendelsene.
Vi skal her forklare i hvilken del av søkingene etter informasjon som matema-
tikken spiller en avgjørende rolle, og vi skal gi et lite innblikk i den matematikken
som behøves.
1.2 Søkemotorer. En enkel modell for en søkemotor på nettet består av tre deler:
1. En robot. Den første ingrediensen er en robot som døgnet rundt søker opp nettsi-
der og laster ned dokumentene på nettsidden i en database. Den mest kjente søke-
motoren er google som kan søke opp og laste ned mer enn 2 milliarder nettsider i
løpet av en uke. Det vil si, den klarer 3300 nettsider per sekund.
Grunnen til at dette arb e idet er mulig er at hver maskin med nettsider har et
internettnummer som er forholdsvis lett å finne på nettet. Har man først funnet en
maskin er det lett å finne nettsidene på maskinen, og dermed også alle lenkene på
hver nettside. Ved hjelp av lenkene kan roboten også komme videre til nye nettsider.
2. Ordliste. Den andre ingrediensen er en ordliste, som inneholder de fleste viktige
ordene som forekommer på dokumentene på de nettsidene vi har lastet ned ved
hjelp av roboten. En slik liste kan inneholde mer enn 100 millioner ord, hvilket kan
sammenliknes med de par tusen ordene vi bruker i daglig skrift og tale. Til hvert
ord i ordlisten finnes en peker til de nettsidene der ordet forekommer. Hver gang vi
2
Alle oppgaver om tider og antall må taes med en klype salt. Nettet og datamaskinene end-
rer seg med en skremmende hastighet. Nye brukere kommer til, maskinene blir hurtigere, og
hukommelsene større.
laksov.tex,v 1.6
Normat 3/2003 D. Laksov 121
skriver inn ett, eller flere, ord vi vil søke på, leter søkemaskinen i ordlisten til den
finner alle ordene, og den vet da også hvilke nettsider ordene forekommer på. Med
de hurtigste søkemaskinene tar det mindre enn et sekund å finne ordkombinasjoner
med 5–6 ord.
Det tar selvsagt lang tid å sette opp en ordliste over ordene som forekommer
i en database med milliarder av dokumenter, men det er mindre krevende e nn å
finne og laste ned dokumentene i databasen.
3. Rangordning. Den tredje ingrediensen består i å rangordne nettsidene etter hvor
viktige de er. Hver gang vi søker på et, eller flere, ord, finnes ordet, eller ordene,
oftest på tusentalls nettsider. For at et søk skal være meningsfull er de t derfor helt
avgj ørende at de nettsidene som kommer først opp på skjermen er de som har
størst betydning for den som søker. Prøver vi for eksempel å finn e opplysninger om
Edvard Grieg vil vi ikke gjerne komme til tusenvis av nettsider som handler om
noe h elt annet, og der Grieg bare er nevnt i forbifarten. Vi vil komme direkte til de
store sentrale arkivene som inneholder viktig informasjon om Grieg og hans verk.
Det er lett å forstå at det er en vanskelig oppgave å rangordne alle nettsidene
på nettet. At en nettside er «viktigere» enn en annen virker å bero på en subjektiv
vurdering. Men subjektive bedømmelser av milliarder av nettsider, mange av dem
med store mengder dokumenter, er selvsagt umulig. Dessuten er nettsidene veldig
ulike. De spenner fra personlige n ettsider som innholder noen få linjer tekst til
store databaser med millioner av dokumenter. For å rangordne sidene må vi derfor
prøve å finne objektive kriterier for hva som er «viktig», og som bare avhenger
av den formelle strukturen av dokumentene, og ikke beror på deres innhold. Det
finnes en rekke forslag på hvordan man skal rangordne nettsider etter «viktighet»,
og leseren kan selv tenke gjennom hvilke løsninger som kan være interessante. Skal
man bruke antallet ganger et ord forekommer på en nettside, eller kanskje antallet
henvisninger til andre sider, eller kanskje antallet dokumenter på nettsiden? Den
store forskjellen mellom de ulike søkemaskinene ligger nettopp i hvordan de løser
denne oppgaven. De som klarer det best blir mes t benyttet kommersielt og får
derfor best råd til å kjøpe inn flere datamaskiner og mer minne, og dermed bli
markedsledende. I dag har de største søkemaskinene titusentalls datamaskiner som
arbeider parallellt med å søke og lagre d ata.
De fleste søkemaskinene bruker mange ulike kriterier for å rangordne nettsider,
som ordfrekvens, plassering av ordene i dokumentene, og avstanden mellom ord. Vi
skal i resten av denne artikkelen forklare en metode for å rangordne nettsider, eller
i det hele tatt store datamengder, som bare avhenger av lenkene på nettsidene.
Metoden kalles PageRank og ble foreslått av Sergey Brin og Larry Page [1] for
omkring 5 år siden, da de var studenter ved Stanford Un iversity. PageRank er
hjertet i den fenomenale søkemotoren google og bygger på enkle og fundamentale
matematiske idéer og resultater.
1.3 «Viktighet»/relevans. Vi har brukt adjektivet viktig om nettsider for en egen-
skap som brukes til å rangordne nettsidene. Ordet viktig er sterkt følelseladet.
Derfor vil vi påpeke at ordet i denne forbindelsen betyr at informasjonen på nett-
siden har stor betydning for det spesielle søket vi gjør, og ikke er noe forsøk til
en subjektiv e ller objektiv bedømning av nettsiden. Når vi sier at «en nettside er
viktig» betyr det at «nettsiden har stor relevans, eller betydning, for den aktuelle
søkningen».
laksov.tex,v 1.6
122 D. Laksov Normat 3/2003
2. PageRank
2.1 Lenker. Idéen bak PageRank er å bruke lenkene mellom nettsidene til å avgjøre
hvor viktige de er. En lenke fra en nettside a til en nettside b er en henvisning i
et dokument på nettsiden a som er slik at om man klikker på henvisningen så
kommer man til nettsiden b. Alle som har sett en nettside vet hvordan slike lenker
ser ut og har brukt dem til å komme fra en nettside til en ann en . Vi skal bruke litt
matematisk terminologi og si at a peker på b og skriver
a
b
c
om a, b og c er nettsider og a og c peker på b, mens nettsiden b peker på nettsiden
c.
2.2 Rangordning. Problemet er å gi hver nettside a en rang R
a
. Det vil si, vi vil
tilordne et tall R
a
til nettsiden a som forteller hvor viktig nettsiden er i forhold til
de andre nettsidene. Med andre ord, om nettsiden a er «viktigere» enn nettsiden
b så skal R
a
være større enn R
b
, og a skal derfor komme opp på skjermen før b
om begge nettsidene a og b inneholder ordene vi søker. Det er for å løse dette
problemet at vi behøver matematikk. For å forklare metoden begynner vi derfor
med litt matematisk notasjon:
For hver nettside a betegner vi dens rang med R
a
. Det er disse tallene
vi skal bestemme ved å finne ligninger som de tilfredsstiller. Vi betegner
med |F
a
| antallet lenker som finnes på nettsiden a. Videre betegner vi
med B
a
alle nettsidene som peker på a, det vil si alle nettsidene som
har et dokument som inneholder en lenke til a. En litt foreklet form for
ligningene som bestemmer tallene R
a
i PageRank er
(PR) R
a
=
X
b2B
a
R
b
|F
b
|
,
der er et tall som vi også må bestemme.
Det er et par ting vi bør merke oss med dette ligningssystemet før vi kan forstå
hvordan denne modellen for rangordning fungerer.
2.3 Bemerkning. Rangordningen R
a
er bestemt av de nettsidene som peker på
a og hvor mange lenker som finnes på disse nettsidene. Bidraget til R
a
blir stort
om mange sider med høy rangordning, og med få lenker, peker på den. Dette er
en rimelig modell ettersom en nettside bør være viktig om den har mange viktige
lenker til seg. Dessuten er disse lenkene mer verdt om de kommer fra nettsider med
få lenker, hvilket også er tiltalende.
En annen f ordel ved denne modellen er at antallet nettsider som peker på en
gitt side er vanskelig å manipulere for de som har kommersielle interesser og vil at
deres side skal ha høy rangordning for å synes først ved et søk. Vi kan selv velge
hvilke sider vi vil lenke til, men ikke hvilke sider som skal lenke til oss.
2.4 Bemerkning. Rangordningen avhenger ikke av hvilket ord vi søker. Om to ord
står på de samme nettsidene vil de samme nettsidene komme opp på skjermen, og
laksov.tex,v 1.6
Normat 3/2003 D. Laksov 123
i samme rekkefølge når vi søker på de to ordene. For eksempel, om navnene Scylla
og Carybdis forekommer på de samme nettsidene vil samme nettsider komme opp i
samme rekkefølge, om vi søker på ordet Scylla, som når vi søker på ordet Carybdis.
Meningen med et ord spiller heller ingen rolle. Søker vi på ordet blad, så kommer
de viktigste nettsidene som inneholde r dette ordet opp, uansett om blad på disse
nettsidene henviser til et blad på et tre, et ukeblad, eller arkene i en bok.
2.5 Bemerkning. Rangordningen til en side R
b
blir like fordelt mellom alle nett-
sidene den peker på, og bidrar til hver nettside med R
b
/|F
b
|, det vil si, termen
R
b
/|F
b
| forekommer i alle ligningen for R
a
der b peker på a, og den forekommer
bare i disse ligningene. Summerer vi over alle nettsidene H får vi derfor
X
a2H
R
a
=
X
a2H
X
b2B
a
R
b
|F
b
|
=
X
a2H
0
R
a
,
der H
0
er nettsidene som inneholder lenker. Vi ser at tallet måler kvoten mel-
lom summen av rangordningen til de sidene som inneholder lenker, og summen av
rangordningen til alle nettsidene. Ettersom det alltid finnes ne ttsider uten lenker
vil 0 <<1.
2.6 Bemerkning. Vi vet at nettsidene, i gjen nomsn itt, har 11 lenker. Det vil derfor
også være i gjennomsnitt 11 lenker som peker på en gitt nettside. Derfor vil hver
ligning PR stort se tt inneholde 12 ukjente med ikke null koeffisienter.
Vi gir nu noen eksempler som viser hvordan ligningene PR ser ut for enkle nett
bestående av 3 nettsider. Sammenliknet med det virkelig nettet med milliarder av
nettsider er dette ganske lite, men det gir en god ide om hvordan ligningene PR
ser ut.
2.7 Eksempel. (Redusible tilfellet)
a
b
c
gir ligningene
R
a
=
1
2
R
c
R
b
= R
a
+
1
2
R
c
R
c
= R
b
Legger vi sammen de venstre og høyre termene i disse tre ligningene får vi at
(R
a
+ R
b
+ R
c
)=R
a
+ R
b
+ R
c
,
som viser at enten er R
a
= R
b
= R
c
=0, som vi ikke vil ha, eller vi har at =1.
Med =1kan vi løse ligningssystemet og får at R
a
=
1
2
R
b
=
1
2
R
c
. Vi kan velge
R
a
vilkårlig til R
a
=1, og får rangordningen R
a
=1,R
b
=
1
2
,R
c
=
1
2
.
laksov.tex,v 1.6
124 D. Laksov Normat 3/2003
Små eksempler er selvsagt ikke realistiske. For eksempel fant vi at =1, som ikke
forekommer i praksis, som vi så i Bemerkning 2.5. Vi må tenke oss at eksempelet
er en del av et større nettverk.
2.8 Eksempel. (Loop)
a
b
c
gir ligningene
R
a
=0
R
b
= R
a
+ R
c
R
c
= R
b
Legger vi sammen termene til venstre og høyre i disse tre ligningen får vi at
(R
a
+ R
b
+ R
c
)=R
a
+ R
b
+ R
c
,
som viser at enten vil R
a
= R
b
= R
c
=0, som vi ikke vil ha, eller så er =1. Med
=1kan vi løse ligningene, og vi får R
a
=0og R
b
= R
c
. Vi kan velge R
b
vilkårlig
til R
b
=1, og får rangordningen R
a
=0,R
b
=1,R
c
=1. Som i forrige eksempel er
ikke dette eksempelet heller spesielt realistisk, og vi må tenke oss at dette også er
en de l av et større nettverk.
2.9 Eksempel. (Hengende nettsider)
a
b
c
gir ligningene
R
a
=
1
2
R
b
R
b
=
1
2
R
a
R
c
=
1
2
R
a
+
1
2
R
b
Legger vi sammen termene til venstre og høyre i disse tre ligningene får vi at
(R
a
+ R
b
+ R
c
)=R
a
+ R
b
.
For =0får vi R
a
= R
b
=0, og velger vi R
c
vilkårlig til 1 får vi rangordningen
R
a
=0, R
b
=0, R
c
=1. Når 6=0kan vi løse ligningene for R
a
og får R
a
=2R
b
=
laksov.tex,v 1.6
Normat 3/2003 D. Laksov 125
4
2
R
a
. Om vi vil ha R
a
6=0får vi at =
1
2
. Dette gir R
a
= R
b
,ogR
c
= R
a
+ R
b
.
Vi kan velge R
a
vilkårlig til R
a
=
1
2
og får rangordningen R
a
=
1
2
,R
b
=
1
2
,R
c
=1.
2.10 Bemerkning. I praksis vil man unngå hengende nettsider, det vil si nettsider
som ikke inneholder noen lenke r. Disse taes derfor bort under beregningene og
settes tilbake til slutt.
Vi vil også unngå looper, det vil si kjeder av nettsider der hver nettside peker
til den ne ste i kjeden, og der det finnes en nettside som ikke inngår i kjeden, men
som peker til en av medlemmene av kjeden. Det er for å håndtere slike looper at
man i praksis bruker en variant på ligningene PR.
2.11 Løsninger. Vi har ikke løst problemet med å rangordne sider bare fordi vi har
satt opp ligningssystemet PR. Vi må også finne en metode for å løse disse ligningene
i løpet av en rimelig tid. De tradisjonelle metodene som vi lærer på universitetene,
for eksempel Gauss–Jordan eliminasjon, er altfor langsomme og for vanskelige å
håndtere for ligningssystemer som inneholder så mange som 3 milliarder ligninger
i like mange ukjente, selv når de fleste koeffisientene er 0. Når koeffisientene er
positive eller null finnes det imidlertid andre metoder, som bruker iterasjon. Dette
viser seg å være veldig effektivt for ligningene PR. I praksis rekker det med omkring
50 iterasjoner f or å få en meget god rangordning for nettsidene. Vi skal i de neste
seksjonene gi en matematisk motivasjon til hvorfor det fungerer så bra å iterere
disse ligningen e.
3. Litt matematikk
I dette avsnittet skal vi uttrykke ligningene fra forrige avsnitt ved hjelp av matri-
ser og vektorer. Vi skal også indikere hvilke metoder man bruker for å løse disse
ligningene. Matematikken burde være forståelig for lesere med gode gymnaskunn-
skaper, og er lett forståelig for lesere med et første års kurs i lineær algebra på et
universitet, eller en høyskole.
3.1 Ligningene på matriseform. La A =(R
ab
) være matrisen med koeffisienter
R
ab
=1/|F
a
| om b peke r mot a og der R
ab
=0om b ikke peker mot a. La videre
v =(R
a
) være søylevektoren hvis a’te koordinat er lik R
a
. Da kan ligningene PR
skrives på matriseform:
Av = v.
Alle som har lest litt lineær algebra vil kjenne igjen d ette uttrykket. Vi sier at
er en egenverdi for matrisen A, og at v er en egenvektor for matrisen A tilhørende
egenverdien .
Vi påminner om at egenverdiene til en n ⇥ n-matrise A er røttene til n-te-
gradspolynomet det(tI
n
A) i den variable t, der I
n
er n ⇥ n identitetsmatrisen.
Polynomet det(tI
n
A) kalles det karakteristiske polynomet for A. For hver egen-
verdi til A har ligningen Av = v i vektoren v løsninger, og løsningene kalles
egenvektorer tilhørende egenverdien .
laksov.tex,v 1.6
126 D. Laksov Normat 3/2003
3.2 Eksempel. I Eksemp el 2.7 ovenfor vil matrisen være
A =
0
B
@
00
1
2
10
1
2
010
1
C
A
I Eksempel 2.8 er matrisen
A =
0
@
000
101
010
1
A
,
og i Eksempel 2.9 er matrisen
A =
0
B
@
0
1
2
0
1
2
00
1
2
1
2
0
1
C
A
.
Matrisen A har ikke-n egative koordinater R
ab
. Når den tilfredsstiller visse til-
leggsbetingelser, som vi skal beskrive nedenfor, finnes det en vakker klassisk teori
for egenverdier og egenvektorer. For å beskrive de resultatene vi skal bruke innfører
vi først litt terminologi.
3.3 Definisjon. En matrise A =(a
ij
) kalles ikke-negativ om a
ij
0 for alle i, j,og
den kalles positiv om a
ij
> 0 for alle i, j.
3.4 Definisjon. En n ⇥ n-matrise er redusibel om den er på blokkformen
0
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
@
⇤··· ⇤⇤⇤··· ⇤⇤⇤··· ⇤⇤⇤··· ⇤
.
.
.
.
.
.
⇤··· ⇤⇤⇤··· ⇤⇤⇤··· ⇤⇤⇤··· ⇤
⇤··· ⇤0 ⇤··· ⇤0 ⇤··· ⇤0 ⇤··· ⇤
⇤··· ⇤⇤⇤··· ⇤⇤⇤··· ⇤⇤⇤··· ⇤
.
.
.
.
.
.
⇤··· ⇤⇤⇤··· ⇤⇤⇤··· ⇤⇤⇤··· ⇤
⇤··· ⇤0 ⇤··· ⇤0 ⇤··· ⇤0 ⇤··· ⇤
⇤··· ⇤⇤⇤··· ⇤⇤⇤··· ⇤⇤⇤··· ⇤
.
.
.
.
.
.
⇤··· ⇤⇤⇤··· ⇤⇤⇤··· ⇤⇤⇤··· ⇤
⇤··· ⇤0 ⇤··· ⇤0 ⇤··· ⇤0 ⇤··· ⇤
⇤··· ⇤⇤⇤··· ⇤⇤⇤··· ⇤⇤⇤··· ⇤
.
.
.
.
.
.
⇤··· ⇤⇤⇤··· ⇤⇤⇤··· ⇤⇤⇤··· ⇤
1
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
A
,
det vil si, den inneholder en blokk av nuller, der 0’ene står i rekkene i
1
,...,i
p
og i søylene j
1
,...,j
q
, og der p + q = n med n lik størrelsen av matrisen og
laksov.tex,v 1.6
Normat 3/2003 D. Laksov 127
{i
1
,...,i
p
,j
1
,...,j
q
} = {1, 2,...,n}. Ekvivalent er den redusibel om vi ved sam-
tidig å endre rekkefølgen av rekke- og søylenummerene 1, 2,...,n kan overføre den
til formen
✓
B 0
CD
◆
der B er en p ⇥ p-matrise, D er en q ⇥ q -matrise, og 0-matrisen i øverste høyre
hjørne e r en p ⇥ q-matrise. En matrise som ikke er redusibel kaller vi irredusibel.
Vi skal nu skrive ne d resultatene om positive og ikke-negative matriser som
danner bakgrunnen for å løse ligninger ved iterasjon, og som vi har nevnt flere
ganger ovenfor:
3.5 Theorem. (Perron 1907) Om A er en positiv matrise har den en positiv egen-
verdi (A) som er en enkel rot i det karakteristiske polynomet, og som er ekte større
enn absoluttverdien for de andre egenverdiene. Til (A) svarer en egenvektor som
er positiv.
3.6 Theorem. (Frobenius 1908-1912) En irredusibel ikkenegativ matrise A har en
positiv egenverdi (A) som er en enkel rot i det karakteristiske polynomet, og som
er ekte større enn absoluttverdien for de andre egenverdiene. Til (A) svarer en
egenvektor som er positiv.
Disse viktige resultatene inngår oftest ikke i et første års kurs i lineær algebra.
Bevisene er vakre, men ganske flokete, og vi gir dem ikke her. (For bevis, se for
eksempel [2].) Vi skal heller ikke gi bevis for følgende to resultater som også ofte
er nyttige, men som har mye enklere bevis (se for eksempel [3]):
3.7 Lemma. Om A er en ikke-negativ irredusibel n ⇥ n-matrise så vil (I
n
+ A)
n1
være positiv, der I
n
er n ⇥ n-enhetsmatrisen.
3.8 Proposisjon. Om A er en ikke-negativ irredusibel matrise slik at a
ii
> 0 for
minst en i så har A en positiv egenverdi som er ekte større enn absoluttverdien til
de andre egenverdiene.
Vi vil nu vise hvorfor Pe rrons og Frobenius setninger er så viktige for å finne
egenverdier for matriser som er positive, eller ikke-negative og irredusible. Ettersom
bevisene er enkle og resultatene så nyttige tar vi med bevisene. Først påminner vi
om noen kjente begrep er fra teorien for matriser.
3.9 Definisjon. La A =(a
ij
) være en m ⇥ n-matrise. Vi kaller n ⇥ m-matrisen
t
A =(a
ji
) den transponerte matrisen til A, og matrisen A =(a
ij
) den konjugerte
matrisen til A, d er a
ij
er den kompleks konjugerte til a
ij
. Vi sier at en n⇥n-matrise
U er unitær om
t
UU = I
n
.
Vi uttrykker også at U er unitær ved å si at rekkene, eller ekvivalent søylene, i U
er ortonormale.
3.10 Schurs meto de. For hver n ⇥ n-matrise A =(a
ij
) kan vi finne e n unitær
matrise U slik at
t
UAU = B
er øvre triangulær, det vil si B =(b
ij
) og b
ij
=0når i>j. Dette viser vi lett ved
induksjon etter n som følger:
laksov.tex,v 1.6
128 D. Laksov Normat 3/2003
La
1
være en egenverdi for A og la u
1
være en egenverdi for
1
av lengde 1.
Ved den kjente Gram–Schmidts ortogonaliseringsprosess, som inngår i alle kurser
i lineær algebra, kan vi finne ortonormale vektorer u
1
,u
2
,...,u
n
.LaU
0
være den
unitære matrisen med søyler u
1
,u
2
,...,u
n
. Da vil
AU
0
=
0
B
@
1
u
11
c
12
··· c
1n
.
.
.
.
.
.
.
.
.
.
.
.
1
u
n1
c
n2
··· c
nn
1
C
A
,
for noen tall c
ij
, og der u
11
,u
21
,...,u
n1
er koeffisientene for u. Ettersom vektorene
u
1
,u
2
,...,u
n
er ortonormale får vi derfor at
t
U
0
AU
0
=
0
B
B
B
@
1
b
2
··· b
n
0
.
.
. A
1
0
1
C
C
C
A
,
for noen tall b
2
,...,b
n
, der A
1
er en (n 1) ⇥ (n 1)-matrise. Antar vi at Schurs
metode holder for (n 1) ⇥(n 1) matriser kan vi finne en unitær (n1) ⇥ (n 1)-
matrise U
1
slik at
t
U
1
A
1
U
1
= B
1
er en øvre triangulær (n 1) ⇥ (n 1) matrise.
Sett
U
0
1
=
0
B
B
B
@
10··· 0
0
.
.
. U
1
0
1
C
C
C
A
.
Da er U
0
1
en un itær n ⇥ n-matrise og
t
U
0
1
0
B
B
B
@
1
b
2
··· b
n
0
.
.
. A
1
0
1
C
C
C
A
U
0
1
=
0
B
B
B
@
1
d
2
··· d
n
0
.
.
.
t
U
1
A
1
U
1
0
1
C
C
C
A
=
0
B
B
B
@
1
d
2
··· d
n
0
.
.
. B
1
0
1
C
C
C
A
= B
er øvre diagonal. Om vi setter U = U
0
U
0
1
får vi derfor
t
UAU =
t
U
0
1
t
U
0
AU
0
U
0
1
= B
som vi ville vise.
3.11 Proposisjon. La A være en matrise og ⇢ et positivt tall som er større enn
absoluttverdien til egenverdiene til A. For hver vektor v vil da
lim
n!1
A
n
v
⇢
n
=0.
laksov.tex,v 1.6
Normat 3/2003 D. Laksov 129
Bevis. Ved Schurs metode finner vi en unitær matrise U slik at
t
UAU er øvre trian-
gulær. Da består diagonalen til
t
UAU av egenverdiene til A. La D være diagonalma-
trisen med koordinater d
ii
= "
i1
. Da vil matrisen D
1t
UAUD være øvre diagonal,
og alle koordinatene ovenfor diagonalen vil være et produkt med en positiv potens
av ". Det følger at om vi velger " liten så vil 0 = lim
n!1
(D
1t
UAUD)
n
w /⇢
n
for
hver vektor w. Men vi har at
lim
n!1
(D
1t
UAUD)
n
w
⇢
n
= lim
n!1
D
1t
UA
n
UDw
⇢
n
= D
1t
U
✓
lim
n!1
A
n
UDw
⇢
n
◆
.
Derfor vil lim
n!1
A
n
UD w/⇢
n
=0, og velger vi w = D
1t
Uv får vi at
lim
n!1
A
n
v
⇢
n
=0.
3.12 Iterasjon. La A være en matrise og u en ikke null vektor. Vi definerer en følge
av vektorer v
0
,v
1
,v
2
,... rekursivt ved
v
0
=
u
|u|
,v
1
=
Av
0
|Av
0
|
,v
2
=
Av
1
|Av
1
|
,...,
det vil si
v
n+1
=
Av
n
|Av
n
|
for n =0, 1, 2,....
Da vil
v
n
=
A
n
u
|A
n
u|
for n =0, 1, 2,....
Spesielt har alle vektorene v
n
lengde 1. Vi skal gi noen enkle betingelser for at
følgen v
0
,v
1
,v
2
,... konvergerer mot en vektor v som er en egenvektor for A.Det
der dette vi mener med å løse ligningen Av = v ved iterasjon.
3.13 Setning. La A være en matrise med en positiv egenverdi (A) som er en enkel
rot i det karakteristiske polynomet til A, og som er større en absoluttverdien av de
andre egenvektorene til A. For «nesten alle» vektorer u vil da følgen av vektorer
v
0
= u/|u|, v
1
= Au/|Au|, v
2
= A
2
u/|A
2
u|,... konvergere og
lim
n!1
v
n
= lim
n!1
A
n
u
|A
n
u|
= v,
der v er en egenvektor for A av lengde 1 som tilhører egenverdien (A).
Bevis. Ettersom (A) er en enkel rot i minimalpolynomet kan vi finne en basis
u
1
,u
2
,...,u
n
for vektorrommet slik at v
1
= u
1
/|u
1
| er en egenvektor for matrisen
A av lengde 1 tilsvarende egenverdien (A), og slik at A med hensyn til denne
basisen kan skrives på formen
A =
0
B
B
B
@
(A)0··· 0
0
.
.
. A
0
0
1
C
C
C
A
,
laksov.tex,v 1.6
130 D. Laksov Normat 3/2003
der A
0
er en (n 1) ⇥ (n 1)-matrise. Skriver vi u = a
1
u
1
+ a
2
u
2
+ ···+ a
n
u
n
og
setter u
0
= a
2
u
2
+ a
3
u
3
+ ···+ a
n
u
n
så får vi at
A
n
u =
✓
(A)
n
a
1
(A
0
)
n
u
0
◆
.
Bortsett fra egenverdien (A) har A og A
0
samme egenverdier. Det følger derfor av
Proposisjon 3.11 at
lim
n!1
(A
0
)
n
u
0
(A)
n
=0
og derfor at
lim
n!1
A
n
u
(A)
n
=
0
B
B
B
@
a
1
0
.
.
.
0
1
C
C
C
A
= a
1
u
1
.
Videre følger det at
lim
n!1
|A
n
u|
(A)
n
= |a
1
||u
1
| = |a
1
|.
Om |a
1
|6=0, det vil si, for alle vektorer som ikke ligger i vektorrommet utspent av
u
2
,u
3
,...,u
n
får vi
lim
n!1
A
n
u
|A
n
u|
= lim
n!1
✓
A
n
u
(A)
n
(A)
n
|A
n
u|
◆
= lim
n!1
✓
A
n
u
(A)
n
◆
lim
n!1
✓
(A)
n
|A
n
u|
◆
=
a
1
|a
1
|
u
1
= ±u
1
.
3.14 Bemerkning. Vi har med vilje brukt det litt upresise begrepet «nesten alle
vektorer» i Setningen. Som vi ser av beviset for Setningen kan vi mer presist si «for
alle vektorer som ikke ligger i et un derrom av dimensjon n 1».
4. Tilbake til PageRank
4.1 Matematikk og praksis. Vi har tidligere bemerket at matrisen A =(R
ab
)
er ganske sp esiell. I søylen b er det nøyaktig |F
b
| koordinater som ikke er null,
og alle ikke null koordinater er lik 1/|F
b
|. Videre har hver rekke omkring |F
b
|
ko ordinater som er forskjellig fra null. I praksis er |F
b
| omtrent lik 11, så «nesten
alle» koordinatene i A =(R
ab
) er like null. Derfor er det ganske lett å regne ut
vektorene v
n
= A
n
u/|A
n
u| for en vilkårlig vektor u. Bestemmer man kvotientene
A
n
u/|A
n
u| for n =1, 2,... så viser det seg at når n nærmer seg 50 så skiller
vektorene A
n
u/|A
n
u| og A
n+1
u/|A
n+1
u| seg veldig lite. Det er derfor rimelig å
bruke vektoren A
n
u/|A
n
u| for en n 50 som en rangvektor. Som vi merker av
den fabelaktige prestasjonsevnen til søkemaskinene som bruker PageRank fungerer
laksov.tex,v 1.6
Normat 3/2003 D. Laksov 131
dette aldeles utmerket i praksis. Tids mess ig tar det bare noen timer å utføre de 50
iterasjonene på en større datamaskin.
Matematikken vi skisset i forrige seksjon er relevant for å sannsynliggjøre at
følgen u/|u|, Au/|Au|,A
2
u/|A
2
u|,... konvergerer mot en egenvektor. For å bruke
Setning 3.13 er det imidlertid nødvendig at forutsetningen om at A =(R
ab
) har
en positiv egenverdi som er en enkel rot i det karakteristiske polynomet, og som er
større enn absoluttverdien av de andre egenverdiene. Om A var positiv ville dette
følge av Perrons Setning 3.5, men som vi har sett er A langt fra positiv. For å bruke
Frobenius Setning 3.6 må vi, blandt annet, vite at matrisen er irredusibel. Dette er
langt fra klart. At den er irredusibel betyr, litt upresist, at det ikke finnes grupper
av nettsider som bare henviser til hverandre. Det er blandt annet dette vi prøver å
unngå ved å modifisere ligningene PR, og ved å ta bort hengende nettsider. Om A
er irredusibel må vi, for å bruke Frobenius Setning, dessuten vite at den positive
egenverdien (A) er ekte større enn absoluttverdien for de andre ege nverdiene.
Dette holder, ved Proposisjon 3.8, om R
aa
er forskjellig fra 0 for noe a. Dette vet
vi ikke holder. Derimot vil dette bli tilfredsstilt om vi modifiserer ligningssystemet
ved å betrakte hver nett som lenket til seg selv. En slik modifikasjon gjør at vi
også kan bruke Lemma 3.7 som sier at (I
n
+ A)
n1
er positiv, og dermed Perrons
Setning. Dette er imidlertid upraktisk ettersom n er så stor.
Man kan spørre seg om disse resonnementene e r interssante eller nødvendige,
ettersom iterasjon fungerer i praksis. Svaret er at vi klarer oss uten resonnementene,
men at det er takket være matematikken, og resultatene vi har nevnt, at vi i det
hele tatt skulle komme på tanken å løse ligningene ved iterasjon. Dette er en annen
grunn til at matematikken er så fundamental. Den gjør det mulig å sette opp de
rette modellene, og de n antyder hvordan modellene skal analyseres.
Bibliografi
[1] Sergey Brin and Larry Page, The PageRank Citation Ranking: Bringing order to the
web, google search engine, http://google.stanford.edu
[2] F. R. Gantmacher Applications of the theory of matrices, Interscience publishers,
inc., London–New York 1959.
[3] Roger A. Horn & Charles R. Johnson, Matrix Analysis, Cambridge Univ. Press 1985.
laksov.tex,v 1.6
