UNIVERZA V LJUBLJANI
FAKULTETA ZA MATEMATIKO IN FIZIKO Finan£na matematika 1. stopnja
Tinkara itko
Potence pozitivnih matrik
Delo diplomskega seminarja Mentor: izr. prof. dr. David Dolºan
Ljubljana, 2021
Kazalo
1. Uvod 4
2. Matrike in njihove lastnosti 4
2.1. Lastne vrednosti in lastni vektorji 4
2.2. Zgled ra£unanja potenc matrik 5
3. Nilpotentne matrike 6
4. Jordanova kanoni£na forma 7
4.1. Funkcije matrik 8
4.2. Matrike s spektralnim radijem manj²im od 1 10
5. Stohasti£ne matrike 11
6. Perron-Frobeniusov izrek 13
6.1. Perron-Frobeniusov izrek (²ibka oblika) 13
6.2. Perron-Frobeniusov izrek (krepka oblika) 14
7. Perronov izrek 17
8. Uporaba Perron-Frobeniusovega izreka 19
8.1. Populacijski model 19
8.2. Model Leontijeva 20
8.3. Googlove matrike 21
9. Zaklju£ek 23
Slovar strokovnih izrazov 24
Literatura 24
Potence pozitivnih matrik Povzetek
Diplomska naloga se osredoto£a na potence pozitivnih matrik. Te so tesno pove- zane z lastnimi vrednostmi in lastnimi vektorji matrik, zato delo razloºi postopek za njihovo ra£unanje in lastnosti matrik v povezavi z njimi. Na podlagi Jordanove ka- noni£ne forme je v delu razloºen preprostej²i postopek za ra£unanje potenc in hkrati tudi drugih funkcij matrik. Razloºene so tudi lastnosti potenc stohasti£nih oziroma verjetnostnih matrik. Osrednja izreka dela sta Perron-Frobeniusov in Perronov iz- rek. Prvi razloºi lastnosti pozitivnih matrik, ki jih nato drugi uporabi pri ra£unanju limit zaporedja potenc pozitivnih matrik. Vse preu£eno je na koncu uporabljeno na primerih iz realnega ºivljenja, kjer lahko vidimo uporabnost potenc pozitivnih matrik in razlog zakaj smo to temo sploh preu£evali.
Powers of positive matrices Abstract
The thesis focuses on powers of positive matrices. They are closely related to ei- genvalues and eigenvectors of said matrices. For this reason the thesis explains the procedure for calculating eigenpairs and their characteristics. On the basis of Jordan normal form the thesis explains a simpler way of calculating powers of matrices and also other matrix functions. It also explains the characteristics of powers of stocha- stic or probability matrices. The centre theorems of this thesis are Perron-Frobenius and Perron theorem. The rst focuses on characteristics of positive matrices, which then the second uses to compute limits of sequences of powers of positive matrices.
Everything we learn is then used in examples from real life, where we can see the usefulness of powers of positive matrices and the reason we started studying them in the rst place.
Math. Subj. Class. (2010): 15A15, 15A16, 15A18, 15B51
Klju£ne besede: lastna vrednost, lastni vektor, pozitivna matrika, nenegativna matrika, Perron-Frobeniusov izrek, Perronov izrek, potence matrik, Jordanova ka- noni£na forma, stohasti£ne matrike
Keywords: eigenvalue, eigenvector, positive matrix, nonnegative matrix, Perron- Frobenius theorem, Perron theorem, powers of matrices, Jordan normal form, sto- chastic matrices
1. Uvod
Pri preu£evanju potenc pozitivnih matrik se stalno opiramo na osnove lastnosti matrik, zato sem v prvem razdelku predstavila le-te. Nadaljevala sem z zgledom obna²anja potenc matrik, ko pove£ujemo stopnje potence in s tem prikazala kaj bodo glavne lastnosti, ki jih bomo spremljali. Ker je obna²anje potenc pozitivnih matrik razli£no za razne skupine pozitivnih matrik sem se najprej omejila na nilpotentne matrike, nato sem prek Jordanove kanoni£ne forme obravnavala pozitivne matrike s spektralnim radijem manj²im od ena in na koncu ²e stohasti£ne matrike. Prek Jordanove kanoni£ne forme sem na²la tudi preprostej²i postopek za ra£unanje potenc pozitivnih matrik. Nato sem iskala skupne lastnosti pozitivnih matrik, ki bi nam postopek ra£unanja potenc ²e olaj²ale, te sta kot prva dokazala nem²ka matematika Oskar Perron (7 May 1880 22 February 1975) in Ferdinand Georg Frobenius (26 October 1849 3 August 1917). Njune ugotovitve sem opisala v poglavjih o Perron- Frobeinusovem, ter Perronovem izreku. Ko sem spoznala vse pomembne lastnosti pozitivnih matrik, pa sem se osredoto£ila na njihovo uporabo, kar sem opisala v razdelku Uporaba Perron-Frobeniusovega izreka.
2. Matrike in njihove lastnosti
Matrika je pravokotna tabela realnih ali kompleksnih ²tevil. Je matemati£ni objekt, ki se veliko uporablja tudi v drugih vejah znanosti. Matrike opi²emo prek
²tevila njihovih vrstic in stolpcev, mnoºico vseh realnih matrik z m vrsticami in n stolpci ozna£imo z Rm×n, mnoºico kompleksnih matrik istih razseºnosti pa s Cm×n. V diplomski nalogi bom ve£inoma govorila o realnih matrikah, veliko lastnosti pa lahko posplo²imo tudi na kompleksne matrike. Najprej si poglejmo nekaj pomemb- nih lastnosti matrik, ki jih bom uporabljala skozi celotno nalogo.
Mnoºenje matrik je kompleksen in £asovno zahteven postopek ºe za niºje stopnje potenc matrik niºjih dimenzij, saj produkt dveh matrik deniramo kot:
Denicija 2.1. Naj bosta A ∈ Rm×n in B ∈ Rn×p. e z aij ozna£imo (i, j)-ti element matrike A, zbij pa (i, j)-ti element matrike B, potem je produkt:
A·B =
Pn
k=1a1kbk1 Pn
k=1a1kbk2 . . . Pn
k=1a1kbkp Pn
k=1a2kbk1 Pn
k=1a2kbk2 . . . Pn
k=1a2kbkp
... ... ... ...
Pn
k=1amkbk1 Pn
k=1amkbk2 . . . Pn
k=1amkbkp
.
Ta produkt je m×p- razseºnostna realna matrika.
Zato prek drugih lastnosti matrik i²£emo rezultate, ki bi nam zmanj²ali komple- ksnost in £asovno zahtevnost tega postopka.
2.1. Lastne vrednosti in lastni vektorji. Do nadaljnjega privzamemo, da je A∈Rn×n.
Denicija 2.2. Realno ²tevilno λ je lastna vrednost matrike A, £e obstaja tak neni£eln vektor x, da velja Ax = λx. Vektor x v tem primeru imenujemo desni lastni vektor pripadajo£ lastni vrednosti λ. Podobno deniramo tudi levi lastni vektor pripadajo£ lastni vrednosti λ, ki je tak neni£eln vektor y za katerega velja yA =λy.
Lastne vrednosti matrik ra£unamo prek karakteristi£nih polinomov matrik.
Denicija 2.3. Karakteristi£ni polinom matrike A v spremenljivkiλdeniramo kot pA(λ) = det(A−λI). Ni£le tega polinoma pa so lastne vrednosti matrike A.
Denicija 2.4. Naj boλlastna vrednost matrikeAinpA(λ)karakteristi£ni polinom matrike A. Potem:
• ve£kratnostλ kot ni£lepA(λ)imenujemo algebrai£na ve£kratnost lastne vre- dnosti λ,
• dimenzijo lastnega podprostoraker(A−λI)imenujemo geometri£na ve£kra- tnost lastne vrednostiλ.
Geometri£na in algebrai£na ve£kratnost lastne vrednosti matrike sta naravni ²tevili, hkrati pa velja, da je algebrai£na ve£kratnost posamezne lastne vrednosti vedno manj²a ali enaka njeni geometri£ni ve£kratnosti.
Ve£krat bom uporabila tudi pojem spektralnega radija.
Denicija 2.5. Spektralni radij matrike A ozna£imo z ρ(A) in ga deniramo kot po absolutni vrednosti najve£jo lastno vrednost matrike A.
V nadaljevanju se bom omejila na nenegativne in pozitivne matrike.
Denicija 2.6. Vektor x =
x1
...
xn
∈ Rn je nenegativen, £e je xi > 0 za vsak i = 1, . . . n in je pozitiven, £e jexi > 0 za vsak i = 1, . . . n . Matrika A ∈ Rm×n je nenegativna, £e je vsak njen element aij >0in je pozitivna, £e je vsak njen element aij >0.
Naj bo A pozitivna kvadratna matrika. Poglejmo si nekaj njenih lastnosti, ki jih lahko preverimo na preprost na£in:
• A ima vsaj eno lastno vrednost razli£no od 0 in ima s tem pozitiven spektralni radij,
• ρ(A) =r ⇐⇒ ρ(A/r) = 1,
• A∈Rm×n, A >0, x∈Rn, x>0in je x neni£eln vektor⇒Ax >0.
2.2. Zgled ra£unanja potenc matrik. Na tem mestu si poglejmo preprost zgled ra£unanja potenc matrik, da bomo intuitivno videli, kak²no je obna²anje matrik pri niºjih potencah in nato tudi pri nekoliko vi²jih.
Zgled 2.7. Naj bo
B = 6 4
1 3
. V tem primeru je:
B2 =
40 36 9 13
, B3 =
276 268 67 75
, B4 =
1924 1908 477 493
.
Pri niºjih potencah ²e ne opazimo nobenega vzorca. Opazimo le, da ²tevila zelo hitro rastejo. e pa spremljamo vi²je potence te matrike, lahko opazimo, da ²tevila eksponentno rastejo z osnovo 7. Tako, dobimo idejo, da bi iz n-te potence matrike B izpostavili 7n. Poglejmo spet zgornje potence matrik, tokrat pomnoºene z 1/72, 1/73 in1/74.
1 72B2 =
0,8163 0,7347 0,1837 0,2653
, 1 73B3 =
0,8047 0,7813 0,1953 0,2187
, 1
74B4 =
0,8013 0,7913 0,1987 0,2053
.
Tukaj vidimo, da je spreminjanje elementov matrike z vi²anjem potenc vedno manj²e. Zdi se nam, da bi lahko, ko n po²ljemo v neskon£no, dobili konvergenco zaporedja potenc. e pogledamo ²e 20. potenco izraza, to ustreza na²im predvide- vanjem. Dobimo:
1
720B20=
0,800 0,800 0,200 0,200
.
Iz tega sklepamo, da bi bila lahko na²a limitna matrika oblike:
0,800 0,800 0,200 0,200
.
V nadaljevanje bomo videli, da to drºi, pojavi pa se nam vpra²anje, kako bi pri²li do te limitne matrike in zakaj je rast ²tevil ravno eksponentna z osnovo 7.
Izkaºe se, da je 7 lastna vrednost matrike. e izra£unamo njej pripadajo£i desni in levi lastni vektor, dobimo:
x= 4
1
, y =1
5 1 5
.
e lastna vektorja zmnoºimo v vrstnem redu y · x dobimo 1, £e pa vrsti red mnoºenja zamenjamo, dobimo ravno limitno matriko:
x·y= 4
1
·1
5 1 5
=
0,800 0,800 0,200 0,200
V tem zgledu smo imeli pozitivno kvadratno matriko, ki je imela pozitivno lastno vrednost in pozitivna pripadajo£a lastna vektorja, kar so pomembne lastnosti, da bo v limiti zaporedje potenc matrike res konvergiralo.
3. Nilpotentne matrike
Prva skupina matrik, ki ima v limiti, ko stopnjo potence po²ljemo v neskon£no preprost rezultat so nilpotentne matrike.
Denicija 3.1. Matrika A∈Rm×m je nilpotentna, £e
∃k ∈N:Ak = 0m×m. Najmanj²i tak k imenujemo red nilpotentnosti matrike A.
Za nilpotentno matriko A∈Rm×m torej velja:
n→∞lim An = 0m×m.
Nilpotentne matrike preprosto prepoznamo, ko ra£unamo lastne vrednosti matrik, saj nam izrek pove, da je matrika nilpotentna natanko tedaj, ko ima vse lastne vrednosti enake 0.
4. Jordanova kanoni£na forma
Obna²anje potenc matrik je preprostej²e tudi za kvadratne matrike s spektralnim radijem manj²im od 1. Rezultat izpeljemo prek Jordanove kanoni£ne forme matrike, ki nam da tudi nekoliko preprostej²i postopek ra£unanja potenc matrik.
Naj bo A∈Rn×n.
Denicija 4.1. Matriko A se da diagonalizirati, £e obstaja taka obrnljiva matrika P ustrezne razseºnosti, da je
D=P−1·A·P
diagonalna matrika. Matriki P pravimo prehodna matrika, saj je prehodna matrika med bazo, ki jo tvorijo lastni vektorji matrike A in standardno bazo zaRn.
Diagonalna matrika iz zgornje denicije ima na diagonali lastne vrednosti matrike A. Ko i²£emo lastne vrednosti matrike A lahko pridemo do dveh zaklju£kov:
• vse lastne vrednosti imajo algebrai£no ve£kratnost 1,
• obstajajo lastne vrednosti matrike, ki imajo algebrai£no ve£kratnost strogo ve£jo od 1.
V posebnem primeru, ko je A simetri£na matrika, nam izrek pove, da so vsi njeni lastni vektorji neodvisni. Prav tako so lastni vektorji matrike A neodvisni, ko ima n razli£nih lastnih vrednosti. V obeh teh primerih se torej A da diagonalizirati.
e pa smo pri²li do drugega zaklju£ka, torej obstaja lastna vrednost z algebrai£no ve£kratnostjo strogo ve£jo od 1 se nam spet lahko zgodita dve situaciji. Lahko imaA
²e vednonneodvisnih lastnih vektorjev, v tem primeru seAda diagonalizirati, £e pa so lastni vektorji matrike A med seboj linearno odvisni, se A ne da diagonalizirati.
V tem primeru pa velja ena£ba
J(A) = P−1 ·A·P,
kjer je J(A) Jordanova kanoni£na forma matrike A. Jordanova kanoni£na forma je blo£no diagonalna matrika, torej je oblike
J =
J1
J2 ...
Jm
.
Matrike Ji imenujemo Jordanove kletke in so oblike:
Ji =
λ 1
... ...
... 1 λ
.
Vsaka Jordanova kletka ima na diagonali lastne vrednosti matrike A, na prvi naddiagonali pa ima enke. Razseºnosti posameznih Jordanovih kletk in ²tevilo kletk, ki pripadajo posamezni lastni vrednosti so odvisne od algebrai£ne in geometri£ne ve£kratnosti lastnih vrednosti.
Poglejmo si preprost primer ra£unanja Jordanove kanoni£ne forme matrike.
Zgled 4.2. Imamo matriko:
A=
3 −1 0 0 0
0 2 −1 0 0
−1 1 1 0 0
2 2 −4 −2 −1
3 −4 2 1 0
.
Pri dolo£anju Jordanove kanoni£ne forme matrike moramo najprej poiskati lastne vrednosti matrike, ter njihove algebrai£ne ve£kratnosti, kar dobimo prek karakteri- sti£nega polinoma.
pA(λ) = det(A−λI) =
3−λ −1 0 0 0
0 2−λ −1 0 0
−1 1 1−λ 0 0
2 2 −4 −2−λ −1
3 −4 2 1 0−λ
=
=−λ5+ 4λ4−λ3−10λ2+ 4λ+ 8 =
=−(λ+ 1)2(λ−2)3 Lastne vrednosti matrike A so torej:
• λ1 =−1, njena algebrai£na ve£kratnost je 2 in
• λ2 = 2, njena algebrai£na ve£kratnost je 3.
Iz zgornjega vemo, da je Jordanova kanoni£na forma matrike A oblike:
J(A) =
−1 ? 0 0 0
0 −1 0 0 0
0 0 2 ? 0 0 0 0 2 ? 0 0 0 0 2
,
saj nam lastne vrednosti dajo elemente na diagonali, njihove algebrai£ne ve£kra- tnosti pa ²tevilo ponovitev vsake. Zanimajo nas ²e elementi na mestih, kjer so vpra-
²aji. tevilo kletk posamezne lastne vrednosti nam da ²tevilo njenih pripadajo£ih neodvisnih lastnih vektorjev. e jih izra£unamo, dobimo za vsako lastno vrednost en neodvisen vektor, kar pomeni, da vsaki lastni vrednosti pripada ena Jordanova kletka. Jordanova kanoni£na forma matrike A je torej:
J(A) =
−1 1 0 0 0
0 −1 0 0 0
0 0 2 1 0 0 0 0 2 1 0 0 0 0 2
.
4.1. Funkcije matrik. Prek Jordanove kanoni£ne forme dobimo naslednji rezultat o ra£unanju funkcij matrik.
Denicija 4.3. Naj bo A n×n realna (ali kompleksna) matrika in f realna (ali kompleksna) funkcija, ki je neskon£nokrat odvedljiva v okolicah lastnih vrednosti matrike A.
e je A=P ·J(A)·P−1, potem deniramo
f(A) = P ·f(J(A))·P−1.
Iz zgornjega sledi, da lahko namesto potenc matrike A ra£unamo le potence njene Jordanove kanoni£ne forme, ki jo nato pomnoºimo ²e s prehodno matriko z leve in inverzom prehodne matrike z desne. Naprej se pri ra£unanju potenc Jordanove kanoni£ne forme matrike lahko omejimo na ra£unanje potenc posamezne Jordanove kletke, saj velja:
Jn=
J1n
J2n ...
Jmn
.
Naj bo Ji Jordanova kletka razseºnosti d×d:
Ji =
λ 1
... ...
... 1 λ
.
To lahko zapi²emo tudi kot vsoto identitete pomnoºene z λ in matrike N, kjer smo z N ozna£ili matriko, ki ima enke na prvi naddiagonali, na ostalih mestih pa ima same ni£le. Potenco matrike Ji lahko tako zapi²emo kot Jin = (λ·I +N)n, kar s pomo£jo binomskega izreka zapi²emo z vsoto:
Jin= (λ·I+N)n =
n
X
k=0
n k
·λn−kNk. Sedaj nas zanimajo ²e potence matrike N. Opazimo, da je
N2 =
0 0 1 0 0 1
... ... ...
0 0 1 0 0 0
.
Z indukcijo lahko dokaºemo, da je i - ta potenca matrike N matrika z enkami na i-ti naddiagonali in ni£lami na ostalih mestih. Ko ta rezultat uporabimo v zgornji vsoti dobimo:
Jin=
λn n1
λn−1 n2
λn−2 · · · nd λn−d λn n1
λn−1 · · · d−1n
λn−d+1
... ... · · · ...
λn n1
λn−1 n2 λn−2 λn n1
λn−1 λn
.
Iz te formule ugotovimo, da so Jordanove kletke, ki pripadajo lastni vrednosti 0 nilpotentne matrike. To potrdi tudi obstoj vsaj ene neni£elne lastne vrednosti kva- dratne pozitivne matrike, saj bi bila v nasprotnem primeru ta matrika nilpotentna.
4.2. Matrike s spektralnim radijem manj²im od 1. Omejimo se sedaj na ma- trike s spektralnim radijem manj²im od 1. Predpostavimo, da jeJiJordanova kletka velikostid×d. Zanima nas posamezen elementn-te potence te kletke. Vsak element je produkt binomskega koecienta in potence lastne vrednosti, ki je po absolutni vrednosti manj²a od 1. Binomski koecient navzgor ocenimo z:
n k
6 nk
k!.
Vsak element matrike Jin ima torej vrednost med 0 in nk!·λk·λkn. Zanima nas obna-
²anje teh elementov v limiti, ko n po²ljemo proti neskon£no. V ulomku imamo v imenovalcu elemente neodvisne od n. Zanima nas le obna²anje ²tevca. Izraznk·λk lahko zapi²emo tudi kot (1/λ)nkk. Tako dobimo v imenovalcu ulomek 1λ, ki je ve£ji od 1, v ²tevcu pa polinom. Izraz v imenovalcu nara²£a hitreje kot izraz v ²tevcu, zato je:
n→∞lim
nk·λn k!·λk = 0.
Ker to velja za vsak element vsake Jordanove kletke matrike s spektralnim radijem manj²im od 1 smo tako dokazali naslednjo lemo.
Lema 4.4. e je M kvadratna m×m (ne nujno realna oziroma pozitivna) matrika s spektralnim radijem manj²im od 1, potem velja:
n→∞lim Mn = 0m×m.
Poglejmo primer matrike, na kateri bomo videli veljavnost zgornje leme.
Zgled 4.5. Imamo matriko
M =
0,3 0,1 0,61 0,7 0,4 0,1 0,6 0,01 0,27
.
Izra£unamo najprej njen spektralni radij prek lastnih vrednosti te matrike. Do- bimo karakteristi£ni polinom:
pM(λ) = −λ3+ 0,97λ2+ 0.,128λ−0,12293.
Ni£le tega polinoma nam dajo lastne vrednosti matrike: λ1 = 0,971508, λ2 =
−0,356473in λ3 = 0,354965. Spektralni radij sedaj dobimo tako, da izmed lastnih vrednosti izberemo tisto, ki je najve£ja po absolutni vrednosti, to je torej λ1 = 0,971508, ki je res manj²a od 1. Izpolnjene so vse predpostavke leme 4.3, torej pri£akujemo, da bo zaporedje potenc matrike M konvergiralo proti ni£elni matriki, ko stopnjo potence po²ljemo v neskon£no. Poglejmo najprej nekaj niºjih potenc te matrike:
M2 =
0,526 0,0761 0,3577 0,55 0,231 0,494 0,349 0,0667 0,4399
, M3 =
0,4257 0,0866 0,425 0,6231 0,1523 0,492 0,4153 0,066 0,3383
,
M4 =
0,4434 0,0815 0,3831 0,5888 0,1282 0,5282 0,3738 0,0713 0,3513
.
Tu opazimo, da se elementi ne spreminjajo prav veliko in po ve£ini padajo. Ker padajo precej po£asi poglejmo nekoliko vi²je potence, potenca stopnje 50 nam da rezultat:
M50 =
0,1151 0,0219 0,1032 0,1586 0,0302 0,1422 0,1007 0,01920 0,0903
, stopnje 100 pa:
M100 =
0,0271 0,0052 0,0243 0,0374 0,0071 0,0335 0,0237 0,0045 0,0212
.
Vidimo, da vsi elementi res padajo proti 0. e bi ºeleli dobiti ni£elno matriko, bi morali stopnjo potence sicer ²e precej pove£ati, vendar pa po lemi 4.4 vemo, da bomo ob veljavnosti predpostavk, v limiti, ko stopnjo potence po²ljemo v neskon£no, zagotovo dobili ni£elno matriko.
5. Stohasti£ne matrike
Naslednja skupina matrik z zanimivimi lastnostmi so stohasti£ne matrike.
Denicija 5.1. Matrika S ∈ Rn×n je stohasti£na, £e je 0 6 mij 6 1 za vsak i, j = 1, . . . n in jePn
j=1mij = 1 za vsak i= 1, . . . , n.
Stohasti£ne matrike imenujemo tudi verjetnostne, saj lahko elemente posamezne vrstice interpretiramo kot verjetnosti. Druga denicija stohasti£nih matrik pa je prek lastne vrednosti in pripadajo£ega lastnega vektorja in sicer, je matrika stoha- sti£na natanko tedaj, ko velja S ·1 = 1, kjer je 1 =
1...
1
. To pomeni, da imajo stohasti£ne matrike lastno vrednost 1 in njej pripadajo£ lastni vektor je 1.
Za potence stohasti£nih matrik velja naslednji izrek.
Izrek 5.2. Naj bo S pozitivna stohasti£na matrika. Potem obstaja limita
limn→∞Sn =T. Za matriko T velja ²e, da je stohasti£na in ima vse vrstice enake.
Dokaz. Naj bo S pozitivna stohasti£na matrika. Najprej z indukcijo dokaºemo, da je 1 lastna vrednost matrikeSnza∀n ∈N. Predpostavimo, da ena£ba velja zan−1, torej da je Sn−1·1= 1·1 (indukcijska predpostavka).
• Najprej preverimo, da ena£ba drºi zan= 1: S·1 = 1·1 velja, ker ima matrika lastno vrednost 1 s pripadajo£im lastnim vektorjem 1 (baza indukcije).
• Predpostavili smo, da trditev velja za n−1, dokazujemo ²e, da velja za n: Sn·1 =S·Sn−1·1 =S·1·1 =S·1 = 1·1, kjer smo na drugem koraku uporabili indukcijsko predpostavko, na £etrtem pa bazo indukcije.
Dokazali smo, da ena£ba velja za ∀n ∈ N. Torej je 1 tudi lastna vrednost matrike Sn in njej pripadajo£ lastni vektor je 1. Iz tega sledi, da je Sn stohasti£na matrika za vsak n.
Dokazujemo ²e obstoj limite in enakost vseh vrstic v limitni matriki. Naj bo p poljuben nenegativen vektor iz Rn, £igar vsota komponent je enaka 1. Ozna£imo :
• s - najmanj²i element matrike S
• Mi - najve£ji element vektorja Sip za vsaki>0
• mi - najmanj²i element vektorja Sip za vsaki>0
Produkt Sp predstavlja uteºeno povpre£je elementov vektorja p, M0 predstavlja najve£ji, m0 pa najmanj²i element vektorja p. Uteºeno povpre£je ima najve£jo vrednost, £e najve£jemu elementu vektorja p, torej M0, dodelimo najve£jo moºno uteº. Ta je v na²em primeru 1. Takrat bodo imeli ostali elementi vektorja dodeljeno uteº 0 in bo rezultat uteºenega povpre£ja ravno M0. Tako dobimo rezultat, da je najve£ji element uteºenega povpre£ja vektorja p vedno manj²i ali enak najve£jemu elementu tega vektorja, z zgornjimi oznakami torej M0 >M1. Podobno ugotovimo tudi za najmanj²e elemente, kjer najmanj²i moºen rezultat dobimo tako, da m0
dodelimo najve£jo moºno uteº, v tem primeru bo rezultat ravno m0, v vseh ostalih primerih pa bo rezultat ve£ji, torej m0 6 m1. Na enak na£in pokaºemo, da velja tudi:
M0 >M1 >· · ·>Mn >· · ·>0 in
m0 6m1 6· · ·6mn 6· · ·61.
Iz tega sledi, da obstajata limiti limn→∞Mn inlimn→∞mn.
e smo z s ozna£ili najmanj²i element matrike S, vemo da so vsi njeni elementi hkrati tudi manj²i od 1−s. To razberemo iz lastnosti, da jeS stohasti£na matrika.
Spet bomo najve£je uteºeno povpre£je dobili, £e elementu M0 pripi²emo najve£jo moºno uteº, torej 1− s, najmanj²emu pa najmanj²o moºno, torej s. Zato velja M1 6sm0+(1−s)M0. S podobnim premislekom dobimo tudim1 >sM0+(1−s)m0.
e zdruºimo te dve neenakosti dobimo:
M1−m1 6(1−2s)(M0−m0).
Z indukcijo pa lahko dokaºemo tudi, da velja:
Mn−mn6(1−2s)n(M0−m0).
Matrika Sje razseºnosti vsaj 2×2, njen najmanj²i elementsje zato vedno manj²i od 12, saj bi v nasprotnem primeru imeli vsoto posamezne vrstice ve£jo od 1. Ker je 0< s 6 12 je 06 1−2s <1 in po izreku o sendvi£u tako dobimo limn→∞(Mn− mn) = 0. Iz tega sledi, da obstaja limita limn→∞Snpin da so vsi elementi limitnega vektorja enaki. Ker dokazujemo, da obstaja limita limn→∞Sn, za vektor p lahko izberemo vektor ei, ki ima nai-ti komponenti 1, na ostalih mestih pa ni£le. Za vsak itorej obstaja limitalimn→∞Snei in ta limitni vektor predstavljai-ti stolpec limitne matrike, ki jo i²£emo. Tako smo dokazali, da obstaja limita limn→∞Sn in so vse vrstice te limitne matrike enake.
V izreku je matrika S pozitivna stohasti£na matrika, torej elementi matrike ne smejo biti ni£le. Preprost primer, ki nam pokaºe, da v primeru nenegativne stoha- sti£ne matrike izrek ne velja nujno, je matrika
S = 0 1
1 0
.
Potence te matrike so oblike Sn =
1 0 0 1
ali
0 1 1 0
, torej limita v tem primeru ne obstaja.
Ker bom stohasti£ne matrike uporabljala tudi v poglavju o uporabi
Perron-Frobeniusovaga izreka, si na tem mestu poglejmo zgled, ki nakazuje veljav- nost izreka 5.2.
Zgled 5.3. Imamo pozitivno stohasti£no matriko S:
S =
0,32 0,46 0,22 0,81 0,09 0,1 0,64 0,11 0,25
.
Podobno kot v prej²njih zgledih tudi tukaj najprej izra£unamo nekaj potenc niºjih stopenj te matrike. Dobimo:
S2 =
0,6158 0,2128 0,1714 0,3961 0,3917 0,2122 0,4539 0,3318 0,2143
, S3 =
0,4791 0,3213 0,1996 0,5798 0,2408 0,1794 0,5516 0,2622 0,1866
,
S4 =
0,5413 0,2713 0,1874 0,4954 0,3081 0,1965 0,5082 0,2977 0,1941
.
Pri niºjih potencah vzorec ²e ni opazen. Na primer element na mestu(1,1)najprej naraste, nato pade in nato spet naraste. Poglejmo ²e 20. potenco te matrike.
Dobimo:
S20 =
0.521797 0.286891 0.191312 0.521796 0.286891 0.191312 0.521797 0.286891 0.191312
.
Tukaj pa smo ºe dobili rezultat kot ga narekuje izrek 5.2. Dobili smo stohasti£no matriko, £e se²tejemo elemente po vrsticah res dobimo 1, hkrati pa so vse vrstice te matrike enake. e preverimo ²e 40. potenco matrike S, dobimo enako matriko.
Torej se ob vi²anju potence matrike ne spreminjajo ve£.
6. Perron-Frobeniusov izrek
Za ra£unanje potenc pozitivnih matrik potrebujemo ²e nekaj lastnosti pozitivnih matrik, ki nam jih da Perron-Frobeniusov izrek.
6.1. Perron-Frobeniusov izrek (²ibka oblika).
Izrek 6.1. (Perron-Frobeniusov izrek (²ibka oblika)) Naj bo A∈ Rn×n nenegativna matrika s spektralnim radijem ρ. Potem je ρ lastna vrednost matrike A in njen pripadajo£ lastni vektor je nenegativen.
V ²ibki obliki Perron-Frobeniusovega izreka imamo nenegativne matrike in lastne vektorje. Za pozitivne matrike pa velja tudi krepka oblika tega izreka.
6.2. Perron-Frobeniusov izrek (krepka oblika).
Izrek 6.2. (Perron-Frobeniusov izrek (krepka oblika)) Naj bo A ∈ Rn×n pozitivna matrika s spektralnim radijem ρ. Potem velja:
(1) ρ je lastna vrednost matrike A in ima pozitiven pripadajo£ lastni vektor, (2) ρ >|λ| za vsako lastno vrednost λ, razli£no od ρ, matrike A in
(3) ρ ima algebrai£no in geometri£no ve£kratnost enako 1.
Izrek pri zgornjih predpostavkah velja le za pozitivne matrike. e bi ºeleli, da velja tudi za nenegativne matrike, bi morali dodati ²e predpostavko ireducibilnosti oziroma nerazcepnosti.
Denicija 6.3. A ∈ Rn×n je reducibilna (razcepna), £e jo lahko s kon£no mnogo hkratnimi menjavami vrstic in stolpcev preoblikujemo v matriko oblike:
A=
B C 0 D
,
kjer sta B in D kvadratni matriki. Sicer, je matrika ireducibilna (nerazcepna).
Kljub tej predpostavki pa ne bo veljala 2. to£ka izreka. Za nenegativne nerazcepne matrike ima lahko ve£ lastnih vrednosti absolutno vrednost enako spektralnemu radiju.
V dokazu Perron-Frobeniusovega izreka bom uporabila ²e vektorske norme.
Denicija 6.4. Vektorska norma je preslikava ||.|| : Cn → R, za katero velja (za vsaka x, y iz Cn inα ∈C):
(1) ||x|| ≥0, ||x||= 0 ⇐⇒ x= 0, (2) ||α·x||=|α| · ||x|| in
(3) ||x+y|| ≤ ||x||+||y|| (trikotni²ka neenakost).
Dokaz. (izreka 6.2)
(1) Iz lastnosti pozitivnih matrik vemo, da za matrikoAveljaρ >0in obstajaλ, za katerega velja|λ|>0in|λ|=ρ. Hkrati vemo, da se lahko pri dokazovanju omejimo na pozitivne matrike s spektralnim radijem 1, ker lahko A vedno delimo z njenim spektralnim radijem in tako dobimo matriko s spektralnim radijem 1.
Naj bo torej (λ, x) lastni par matrike A, hkrati naj velja, da je |λ| = 1. Radi bi dokazali, da je par(|λ|,|x|)prav tako par lastne vrednosti in lastnega vektorja. Tako bomo dobili pozitivno lastno vrednost in pozitiven pripadajo£
lastni vektor.
Velja:
|x|=|λ| · |x|=|λ·x|=|A·x| ≤ |A| · |x|=A· |x|.
Torej |x| ≤ A|x|. Radi bi dokazali, da v tej neenakosti velja ena£aj. Nee- nakost preoblikujemo v:
A|x| − |x| ≥0.
Privzemimo, da jeA|x| − |x| ≥0 inA|x| − |x| 6= 0.
Celotno neena£bo lahko pomnoºimo zA z leve in dobimo:
A(A|x| − |x|)≥0.
Da bo dokaz bolj pregleden ozna£imo z =A|x| in neena£bo prepi²emo v:
Az−z ≥0.
Tu spet uporabimo lastnosti pozitivnih matrik, ker imamo A > 0 in po predpostavki velja A|x| − |x| ≥0 inA|x| − |x| 6= 0 sledi, da je Az−z > 0. Dobili smo torej ena£bo, kjer dokazujemo strogo neenakost. Iz te neena£be sledi, da obstaja >0, tak da velja Az >(1 +)z, oziroma:
A
(1 +)z > z.
Spet poenostavimo zapis tako, da ozna£imo A/(1 + ) = B in dobimo neena£boBz > z.
To zadnjo neena£bo sedaj pomnoºimo z B z leve, neenakost se, podobno kot na prej²njem koraku, ohrani. Dobimo B2z > Bz, kar je strogo ve£je od z. To iterativno ponavljamo in dobimo neenakost:
Bkz >· · ·> B2z > Bz > z.
Spektralni radij matrikeB je ρ
A 1 +
= ρ(A)
1 + = 1
1 + <1.
Iz leme 4.4 sedaj vemo, da v limiti velja:
k→∞lim Bk = 0.
S tem v limiti dobimo neenakost0> z. Pri²li smo do protislovja in s tem smo dokazali, da je A|x| = |x| oziroma, da je A|x| = |λ| · |x|. Tako je (|λ|,|x|) torej par lastne vrednosti in lastnega vektorja, kjer je |λ| = ρ. O£itno je
|x| ≥0in spet lahko sklepamo, da je A|x|>0. Ker velja A|x|=ρ· |x|torej velja da je |x| pozitiven. S tem smo dokazali 1. to£ko izreka.
(2) Dokazali smo ºe, da je ρ=|λ| spektralni radij matrikeA, torej jeρ≥ |µ|za vsako lastno vrednostµmatrikeA. Dokazujemo ²e da v neena£bi velja stroga neenakost oziroma, da je jeλedina lastna vrednost, ki je enaka spektralnemu radiju.
Spet brez ²kode za splo²nost predpostavimo, da je ρ= 1. Iz dokaza prve to£ke vemo, da je A|x|=|x|>0, torej za vsako komponentok velja:
0<|xk|= (A|x|)k =
n
X
j=1
akj|xj|.
Po drugi strani velja:
|xk|=|λ| · |xk|=|λ·xk|=|(Ax)k|=
n
X
j=1
akj·xj . Skupaj dobimo:
n
X
j=1
akj ·xj
=
n
X
j=1
akj|xj|=
n
X
j=1
|akj ·xj|.
Absolutno vrednost komponent produkta matrike z vektorjem, kot jo imamo napisano zgoraj lahko razumemo tudi kot vektorsko normo, saj ustre- za vsem lastnostim od 1 do 3 iz denicije vektorskih norm. Uporabimo lahko
trikotni²ko neenakost: za neni£elne vektorjez1, . . . , znizCnvelja||P
jzj||= P
j||zj|| ⇐⇒ so vsi vektorji z1, . . . , zn linearno odvisni oziroma, se vse da izraziti kot ve£kratnike enega. Torej obstajajo ²tevila αj >0, tak²na da je zj =αj·z1 za vsakj = 1, . . . , n.V na²em primeru torej enakost velja natanko tedaj, ko lahko akj ·xj zapi²emo kot αj ·(ak1 ·x1). Ekvivalentno lahko to zapi²emo kot xj =bjx1, kjer jebj =αj·aak1
kj >0. Za lastno vrednost|µ|= 1, lahko lastni vektor x zapi²emo kot produkt prve komponente vektorja x1
in vektorja p =
b1
...
bn
, ki je pozitiven in velja b1 = 1. Torej, £e zdruºimo, dobimo:
µ·x=Ax⇒µ·x1·p=A·x1·p.
Ker je x1 skalar lahko celotno ena£bo delimo z njim in dobimo:
µ·p=Ap=|Ap|=|µ·p|=|µ| ·p=p λ·p=|µ| ·p
⇒µ= 1.
Dobili smo torej, da je µ vedno pozitivno ²tevilo, torej edina lastna vre- dnost, ki leºi na spektralnem radiju matrike.
(3) Dokazati moramo le ²e zadnjo lastnost, torej da imaρ algebrai£no in geome- tri£no ve£kratnost enako 1. Najprej dokaºemo geometri£no ve£kratnost, saj si bomo s to lastnostjo pomagali pri dokazu algebrai£ne ve£kratnosti.
e vedno vzamemo lastni par (ρ, x). Geometri£na ve£kratnost enaka 1 pomeni, da so vsi lastni vektorji, ki pripadajoρlinearno odvisni. Dokazujemo s protislovjem, torej recimo, da obstaja lastni vektor y, ki pripada ρ in je linearno neodvisen od x. Zato velja, da je tudi vsaka linearna kombinacija vektorjev x in y lastni vektor matrike A, pripadajo£ ρ. Ker je x pozitiven, obstaja∈R, tak da jey0 =x+ynenegativen vektor z vsaj enim elementom enakim 0. Kljub temu pay0ni ni£eln vektor, saj staxinylinearno neodvisna.
ey0 zmnoºimo zAz leve dobimoAy0, ki je pozitiven vektor in tako pridemo do protislovja, saj bi moral produkt biti skalarni ve£kratnik vektorja y0, ki ima vsaj en ni£eln element. Geometri£na ve£kratnost ρ je torej 1.
Sedaj uporabimo ²e lastnost, da je algebrai£na ve£kratnost posamezne lastne vrednosti vedno manj²a ali enaka njeni geometri£ni ve£kratnosti in tako dobimo, da je tudi algebrai£na ve£kratnost lastne vrednostiρ enaka 1.
Dokazali smo celoten Perron-Frobeniusov izrek. Lastno vrednost ρ omenjeno v izreku imenujemo tudi Perron-Frobeniusova lastna vrednost, njen pripadajo£i lastni vektor pa Perron-Frobeniusov lastni vektor.
Zgled 6.5. Lastnosti pozitivnih matrik, ki jih opisuje Perron-Frobeniusov izrek sedaj poglejmo na zgledu. Naj bo
A=
3 4 5 3 4 3 4 2 2
.
Poi²£emo najprej lastne vrednosti matrike, z ra£unanjem ni£el karakteristi£nega polinoma matrike.
pA(λ) =−λ3+ 9λ2+ 12λ−20 =
= (λ−10)(λ+ 2)(λ−1)
Lastne vrednosti matrike A so torej λ1 = 10, λ2 = −2 in λ3 = 1. Spektralni radij te matrike je tako ρ(A) = 10, kar je pozitivna lastna vrednost matrike in njena algebrai£na ve£kratnost je 1. Hkrati velja, da je ρ(A) > |λ2| in ρ(A) > |λ3|. Vrednost λ1 = ρ(A) = 10 je torej Perron-Frobeniusova lastna vrednost. Poi²£emo
²e njen pripadajo£ lastni vektor D. Velja:
AD=λ1D.
Kar preoblikujemo v(A−10·I)D= 0.Dobili smo matri£no ena£bo, ki jo re²imo z Gaussovo eliminacijo in re²itev dobimo pozitiven lastni vektor:
D=
7 6 5
,
ki je Perron-Frobeniusov lastni vektor. Algebrai£no ve£kratnosti λ1 smo dobili kot stopnjo ni£le v karakteristi£nem polinomu. Preverimo ²e, da je geometri£na ve£- kratnost te lastne vrednosti prav tako 1. To bi v splo²nem preverili z ra£unanjem ranga matrikeA−λ1I. V na²em primeru, ker imamo 3 razli£ne lastne vrednosti, pa vemo da je geometri£na ve£kratnost vsake enaka 1. Tako vidimo, da res drºi celoten Perron-Frobeniusov izrek.
7. Perronov izrek
Do sedaj smo pri lastnostih govorili ve£inoma o desnih lastnih vektorjih, vse pa lahko simetri£no prepi²emo tudi za leve lastne vektorje.
Izrek 7.1. (Perronov izrek)
Naj bo A ∈ Rm×m pozitivna matrika in naj bosta D in L pozitivni desni in levi lastni vektor, pripadajo£a Perron-Frobeniusovi lastni vrednosti λin naj velja L·D= 1. Potem velja:
n→∞lim 1
λnAn =D·L.
Obstoj pozitivnih lastnih vektorjev v tem izreku, nam da Perron-Frobeniusov izrek.
Dokaz. Naj bodo torej matrika A, vektorja L in D, ter λ denirani kot v izreku.
Torej:
A=
a11 . . . a1m ... ... ...
am1 . . . amm
, L=
w1 . . . wm
in D=
v1
...
vm
.
Sedaj vpeljemo diagonalni matriki V in njen inverz V−1, ki izhajata iz vektorja D:
V =
v1
...
vm
in V−1 =
1/v1
...
1/vm
,
ter pozitivno matriko S, prek formule:
S = 1
λV−1AV.
e S pomnoºimo z vektorjem 1=
1...
1
, dobimo:
S·1 = 1
λV−1AV ·1= 1
λV−1AD= 1
λV−1·λD=V−1D=1.
Iz £esar lahko ugotovimo, da je vsota vsake vrstice matrike S enaka 1, torej je S stohasti£na matrika. Po izreku o stohasti£nih matrikah (5.2) vemo, da obstaja matrika T, da velja:
n→∞lim Sn = lim
n→∞
1
λV−1AV n
=T.
T je torej oblike (spet po izreku o stohasti£nih matrikah):
T =
t1 t2 . . . tm t1 t2 . . . tm
... ... ... ...
t1 t2 . . . tm
.
Ena£bo limn→∞ 1
λV−1AVn
=T lahko ekvivalentno zapi²emo kot limn→∞ 1
λ
n
·An =V T V−1, kjer smo celotno ena£bo najprej pomnoºili z V z leve in nato ²e z V−1 z desne.
V naslednjem koraku limitno ena£bo pomnoºimo z vektorjem Lz leve.
L·/ lim
n→∞
1 λ
n
·An=V T V−1
n→∞lim 1
λ n
·L·An=LV T V−1
Za vsako potenco n je vektor L levi lastni vektor matrike An pripadajo£ lastni vrednosti λn zato dobimo:
n→∞lim 1
λ n
·Lλn =LV T V−1
L=LV T V−1
Zanimajo nas ²e vrednosti produktaLV T V−1. Najprej zmnoºimo LV in dobimo vektor:
LV =
w1v1 . . . wmvm .
Ko ta vektor zmnoºimo ²e s T pa dobimo vektor, katerega i-ti element je:
ti
m
X
j=1
wjvj =ti, ker je vsota Pm
j=1wjvj enaka ravno produktu LD, kar smo ºe na za£etku predpo- stavili, da je enako 1.
Ko na koncu to zmnoºimo ²e z V−1, dobimo vektor z i-tim elementom ti/vi. e zdruºimo oba rezultata torej dobimo n ena£b obliketi/vi =wi, iz £esar sledi:
ti =wivi,
kar je ravno i-ta komponenta produkta DL.
Zgled 7.2. Nadaljujemo s prej²njim zgledom in poi²£emo ²e limitno matriko. Naj- prej potrebujemo ²e levi lastni vektor, ki ga dobimo prek matri£ne ena£beLA=λ1L. To ena£bo preoblikujemo v obliko (A−10I)TLT = 0 in jo re²imo. Dobimo:
L=
1 1 1 .
Po predpostavkah Perronovega izreka, mora veljati LD= 1, zato vektorja normi- ramo. Izra£unamo:
L·D=
1 1 1
7 6 5
= 18.
Enega od vektorjev delimo z 18, tako bomo dobili produkt LD res enak 1. Recimo, da z 18 delimo vektor D in nato vektorja zmnoºimo ²e v obratnem vrstnem redu:
D·L=
7/18 6/18 5/18
1 1 1
=
7/18 7/18 7/18 1/3 1/3 1/3 5/18 5/18 5/18
. Perronov izrek nam pove, da je to ravno limitna matrika, torej velja:
n→∞lim 1 10n
3 4 5 3 4 3 4 2 2
n
=
7/18 7/18 7/18 1/3 1/3 1/3 5/18 5/18 5/18
. 8. Uporaba Perron-Frobeniusovega izreka
Ko poznamo rezultate potenc pozitivnih matrik, se vpra²amo zakaj so ti sploh pomembni. V realnem ºivljenju je veliko podatkov, ki jih ocenjujemo, modeliramo, spremljamo, itd. nenegativnih, lahko pa tudi pozitivnih, na primer £as, smrtnost, rodnost, proizvodnja . . . .
Druga pomembna lastnost, zakaj se ukvarjamo z lastnostmi in potencami pozitiv- nih matrik, pa je, da ko dolo£ene podatke modeliramo, velikokrat opazimo linearen model, ki se skozi £as iterativno spreminja po formulixk+1 =Axk, kjer jexk stanje v prej²njem obdobju. Ra£unamo torej na videz preprost produkt matrike in vektorja, a pri velikih koli£inah podatkov so ti postopki lahko zelo zamudni. Prav tako lahko zgornjo formulo prepi²emo v xk =Akx0, kjer je x0 za£etno stanje. V tem primeru pa vidimo tudi potenco matrike, kar je ºe samo po sebi zamuden proces.
8.1. Populacijski model. Imamo populacijo, ki jo razdelimo vn skupin, glede na njihova leta. Podatke zapi²emo v vektor x, ki ga indeksiramo z j, ki predstavlja
£asovno obdobje v katerem se nahajamo. V i-ti vrstici vektorja xj je torej zapisana koli£ina ljudi, ki je ob £asu j spadala vi-to starostno skupino. V matriki A imamo zbrane podatke o tem kolik²en del starostne skupine bo v naslednjem obdobju spa- dal v naslednjo starostno skupino, v prvi vrstici pa so zbrane pri£akovane koli£ine otrok, ki jih bo imela dolo£ena starostna skupina kot celota. S tem modelom lahko spremljamo spreminjanje starosti populacije, na primer v neki drºavi.
xj+11
...
xj+1n
=
a11 a12 . . . a1n
a21 0 . . . 0 ... ... ...
0 an,n−1 0
xj1
...
xjn
Zanima nas ali obstaja moºnost, da populacija izumre, ne glede na prvotno koli-
£ino prebivalstva. Re²itev nam da lema 4.4, iz katere sledi, da £e imamo v popula- cijskem modelu matriko A s spektralnim manj²im od 1 pri£akujemo izumrtje vseh starostnih skupin od nekega £asovnega obdobja dalje, ne glede na prvotno stanje populacije.
8.2. Model Leontijeva. Model Leontijeva oziroma Leontijev input/output model je imenovan po ruskem ekonomistu Wassilyjevu Leontiefu. S tak²nim modelom ra£unamo na primer BDP posamezne drºave, saj je potrebno pri ra£unanju upo²te- vati, da sektorji ne ustvarjajo le kon£nih produktov, ampak tudi produkte, ki jih potrebujejo drugi sektorji za proizvodnjo kon£nih produktov.
Poglejmo si to na preprostem primeru. Predstavljamo si poenostavljeno gospodar- stvo z le tremi sektorji kmetijstvo, industrija in storitvene dejavnosti, ter zunanjim uporabnikom (npr. gospodinjstva). Vsakemu sektorju pripi²emo xi koli£ino svoje dobrine, ki jo proizvede za i = 1,2,3. V prvi vrstici tabele imamo deleºe proizvo- dnje kmetijstva (x1), ki jo potro²i posamezen sektor: 30% potro²i kmetijstvo samo, 20% porabi industrija in s tem proizvede x2 proizvodov, 30% porabijo storitvene dejavnosti za proizvod x3 enot proizvodov in preostale 4 enote porabi potro²nik.
Podobno v ostalih vrsticah vidimo porazdelitev koli£in x2 in x3. kmetijstvo industrija storitvene
dejavnosti zunanji
uporabniki SKUPAJ
kmetijstvo 0,3 x1 0,2 x1 0,3 x1 4 x1
industrija 0,4 x2 0,3 x2 0,2 x2 5 x2
storitvene
dejavnost 0,2 x3 0,1 x3 0,5 x3 12 x3
Osnovna predpostavka Leontijevega input/output modela je, da ko en od sektorjev pove£a svojo proizvodnjo, bo s tem potreboval ve£ surovin in se bo tako morala pove£ati proizvodnja ostalih sektorjev.
Posplo²imo ta model na n proizvajalcev, kjer vsak proizvaja natanko eno do- brino. Koli£ino dobrine, ki jo proizvedei-ti proizvajalec ozna£imo z xi in te koli£ine zapi²emo v vektor x. Predpostavimo, da vsak sektor proizvaja pozitivno koli£ino izdelkov in hkrati, da se vse dobrine uporabijo za proizvodnjo vseh ostalih dobrin, nekaj dobrin pa gre tudi zunanjim uporabnikom. Ozna£imo zxij deleºi-te dobrine, ki jo potrebuje j-ti proizvajalec in te koli£ine zapi²emo v matrikoX. V vektord pa zapi²emo koli£ine dobrin, ki jo potrebuje zunanji uporabnik. Tu torej velja X ≥0, d ≥ 0 in x > 0. Predpostavimo ²e, da je proizvodnja enaka povpra²evanju, torej mora za ∀i= 1, . . . , n veljati:
xi1+xi2+· · ·+xin+di =xi.
I²£emo optimalen vektorx, ki bo zado²£al vsem ena£bam. Ker smo predpostavili, da velja x >0, lahko deniramo:
aij =xij/xj,
ki nam pove, koliko enot dobrineirabimo za proizvodnjo ene enote dobrinej. Ko to formulo vstavimo v zgornje ena£be dobimo:
ai1x1+ai2x2+· · ·+ainxn+di =xi.
e ²e elemente aij zapi²emo v matriko A, lahko ta sistem ena£b zapi²emo v matri£ni obliki kot:
Ax+d=x ali
(I−A)x=d.
Matriki A pravimo matrika Leontijeva ali vhodno-izhodna matrika, vektorju x vektor proizvodnje, vektorju d pa vektor povpra²evanja.
Model Leontijeva delimo na 2 obliki:
(1) Odprti model Leontijeva: (I−A)x=din (2) Zaprti model Leontijeva: (I−A)x= 0.
Na Perron-Frobeniusovi teoriji sloni le zaprti model Leontijeva, zato obravnavamo njegove rezultate.
8.2.1. Zaprti model Leontijeva. V tej obliki predpostavimo, da je vektor povpra²e- vanja ni£eln. Tako imamo homogen sistem ena£b:
(I −A)x= 0.
Predpostavimo ²e:
(1) A je nenegativna kvadratna matrika.
(2) V vsakem stolpcu matrikeA je vsaj en element neni£eln.
(3) aii<1 za vsaki.
(4) Vsota elementov v vsakem stolpcu matrike A je 1.
Predpostavka (2) je smiselna, kar bi sicer obstajal proizvod, za katerega ne po- trebujemo nobene dobrine. V predpostavki (3) predpostavimo, da vsak proizvajalec proizvede ve£ svojih dobrin, kot jih potrebuje zase. Predpostavka (4) pa nam pove, da se celotna proizvodnja dobrine iporabi znotraj vseh panog.
V zaprtem modelu vedno obstaja re²itev, in sicer je to trivialna re²itev x = 0, vendar pa ta ni smiselna. Zanima nas, kdaj to ni edina re²itev sistema. Iz zgornjih predpostavk vidimo, da jeAT stohasti£na matrika. Le-te imajo eno lastno vrednost vedno enako 1, ki je hkrati tudi spektralni radij teh matrik. Ker imataAinAT enake lastne vrednosti imamo tako nenegativno matriko s spektralnim radijem 1. Zgornji sistem lahko prepi²emo v ena£bo oblikeAx =x. Vektor, ki ga i²£emo je torej lastni vektor matrike A pripadajo£ lastni vrednosti 1. Vidimo, da imamo izpolnjene vse predpostavke ²ibke oblike Perron-Frobeniusovega izreka in obstajala bo nenegativna re²itev matri£ne ena£be. e boA ²e ireducibilna, bodo izpolnjene vse predpostavke krepke oblike Perron-Frobeniusovega izreka in obstajala bo pozitivna re²itev ena£be.
8.3. Googlove matrike. Rezultate Perrona in Frobeniusa v svojem algoritmu upo- rablja tudi brskalnik Google prek t.i. Googlovih matrik. Ozna£imo jih z G in so generirane prek ve£ spremenljivk. Najprej je generirana matrika A. V tej matriki vrstice in stolpce predstavljajo posamezne spletne strani (A je torej kvadratna), njeni elementi pa predstavljajo povezave med posameznimi spletnimi stranmi. e torej iz j-te spletne strani lahko direktno pridemo doi-te je(i, j)-ti element matrike A 1, sicer pa 0. Iz te matrike je nato generirana matrika S, tako, da posamezen
element delimo z vsoto stolpca v katerem leºi. e je vsota stolpca enaka 0 pa vse elemente v tem stolpcu nadomestimo z n1, kjer jen razseºnost matrikeA.
Vsota vsakega stolpca tako denirane matrikeSje 1, take matrike imenujemo tudi leve stohasti£ne matrike. Te imajo prav tako kot stohasti£ne matrike lastno vrednost 1, ki je hkrati tudi njihov spektralni radij. Za razliko od stohasti£nih matrik, pa lastni vektor 1 ni lastni vektor pripadajo£ lastni vrednosti 1.
Na koncu deniramo ²e α, ki je realno ²tevilo z vrednostmi v intervalu (0,1). Z α dolo£imo verjetnost, da posameznik iz i-te spletne strani sledi povezavi na j-to spletno stran, z(1−α)pa verjetnost, da posameznik naklju£no pristane na dolo£eni spletni strani. e ²e z B ozna£imo matriko z vsemi elementi enakimi 1, lahko Googlovo matriko deniramo kot:
G=αS+ 1−α n B.
Googlova matrika je tako pozitivna leva stohasti£na matrika in zanjo velja krepka oblika Perron-Frobeniusovega izreka. Ta nam pove, da lastni vrednost 1 pripada pozitiven lastni vektor. e ta lastni vektor normiramo, torej vsak element delimo z vsoto celotnega vektorja, dobimo vektor, katerega vsota komponent je enaka 1, kar lahko razumemo tudi kot verjetnosti. Tako dobljen vektor za Googlove matrike imenujemo PageRank vektor. Njegovai-ta komponenta predstavlja verjetnost, da se bo posameznik nahajal na i-ti spletni strani. PageRank je algoritem, ki ga Google uporablja za razvr²£anje spletnih strani v vrstni red med zadetki iskanja. Prek PageRank vektorja torej Google dolo£i kako pomembna je posamezna spletna stran in kako visoko na seznam zadetkov iskanja jo bo uvrstil.
Za laºjo predstavo Googlovih matrik si poglejmo preprost zgled.
Zgled 8.1. Predstavljajmo si preprosto omreºje 5 spletnih strani (A, B, C, D in E), ki vsebujejo medsebojne povezave prikazane v naslednjem grafu:
Te povezave najprej predstavimo z matriko A:
A=
0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 1 0 0 0 1 0 0 0
.
Posamezni element matrike sedaj delimo z vsoto stolpca v katerem leºi, stolpec ki vsebuje same ni£le pa zamenjamo z elementi 1/5 in dobimo:
S =
0 1/4 0 1/5 0 0 0 0 1/5 1/2 0 1/4 0 1/5 1/2 1 1/4 1 1/5 0 0 1/4 0 1/5 0
.
Google navadno za α uporabi vrednost 0,85; zato to vrednost uporabimo tudi v tem zgledu in dobimo Googlovo matriko.
G=αS+ 1−α n B =
= 0,85
0 1/4 0 1/5 0 0 0 0 1/5 1/2 0 1/4 0 1/5 1/2 1 1/4 1 1/5 0 0 1/4 0 1/5 0
+1−0,85 5
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
=
=
0,03 0,2425 0,03 0,2 0,03 0,03 0,03 0,03 0,2 0,455 0,03 0,2425 0,03 0,2 0,455 0,88 0,2425 0,88 0,2 0,03 0,03 0,2425 0,03 0,2 0,03
Poi²£emo ²e PageRank vektor po podobnem postopku, kot smo to naredili ºe v zgledu 6.5. Dobimo:
x=
1 1,1753
1,425 3,0613
1
.
Ko se²tejemo vse komponente vektorja dobimo 7,6616 in ko vektor normaliziramo dobimo PageRank vektor:
x=
0,1305 0,1534 0,1860 0,3996 0,1305
.
PageRank vektor nam torej pove, da je najve£ja verjetnost, da posameznik pri- stane na spletni strani D, ki bi jo v zadetkih iskanja tako Google uvrstil najvi²je.
9. Zaklju£ek
Matrike so zelo vsestranski matemati£ni objekt. Kljub temu, da sem se v diplom- skem delu omejila le na pozitivne in nenegativne matrike pa to ni veliko omejilo podro£ja njihove uporabe. V celotnem diplomskem delu vidimo, kako pomembne so lastnosti pozitivnih in nenegativnih matrik, ki sta jih kot prva dokazala Oskar Per- ron in Georg Frobenius. Na podlagi njunih ugotovitev so se razvili razli£ni modeli, ki olaj²ajo ra£unanje in modeliranje na razli£nih podro£jih znanosti.
Slovar strokovnih izrazov eigenvalue lastna vrednost
eigenvector lastni vektor
Jordan normal form Jordanova kanoni£na forma matrix (pl. matrices) matrika (matrike)
power potenca
spectral radius spektralni radij
stochastic matrix stohasti£na matrika
Literatura
[1] C. Bernhart, Powers of Positive Matrices, Mathematics Magazine 2018, strani 218-227.
[2] P. Glaister, Diagonalization and Jordan normal form motivation through Maple , Internati- onal Journal of Mathematical Education in Science and Technology 2009 strani 705712.
[3] A. R. Horn in C. R. Johnson, Matrix Analysis, Cambridge University Press, 2012.
[4] T. Ko²ir, Lastne vrednosti in lastni vektorji, [ogled 8. 9. 2021], dostopno na https://www.
fmf.uni-lj.si/~kosir/poucevanje/skripta/lastne.pdf.
[5] T. Ko²ir, Matrike, [ogled 8. 9. 2021], dostopno na https://www.fmf.uni-lj.si/~kosir/
poucevanje/skripta/matrike.pdf.
[6] B. Lavri£, Algebra 1 - kratek povzetek rezultatov in denicij, [ogled 8. 9. 2021], dostopno na https://www.fmf.uni-lj.si/~lavric/algebra1-pregled.pdf.
[7] C. R. MacCluer, The Many Proofs and Applications of Peron's Theorem, SIAM Rev. 2006 strani 487498.
[8] C.D. Meyer, Matrix Analysis and Applied Linear Algebra, [ogled 9. 9. 2021], dosto- pno na https://books.google.si/books?hl=en&lr=&id=HoNgdpJWnWMC&oi=fnd&pg=
PR2&dq=matrix+analysis+and+applied+linear+algebra+meyer&ots=HaGwPby4MR&sig=
rZW4wZH4ccSCdDaHm0zQk2nnVLw&redir_esc=y#v=onepage&q&f=false.
[9] P. Moravec, Dodatna poglavja iz linearne algebre za 1. letnik nan£ne matematike na FMF, verzija 13. 9. 2017, [ogled 8. 9. 2021], dostopno na https://www.fmf.uni-lj.si/~moravec/
Papers/finmat_alg1.pdf.
[10] B. Plestenjak, Linerani sistemi, [ogled 8. 9. 2021], dostopno na https://www.fmf.uni-lj.
si/~plestenjak/Vaje/NmFin/Predavanja/NMFIN_1_2008_PP_06_LinearniSistemi.pdf.
[11] T. ten Raa, Input-Output Economics: Theory and Applications, [ogled 9. 9. 2021], dostopno na https://books.google.si/books?id=nu0FAvNiFhYC&printsec=frontcover&dq=input+
output+mo-del&hl=en&sa=X&ved=2ahUKEwj23IynkLjwAhVOmIsKHaESC70Q6AEwB3oECAcQAg#
v=onepage&q&f=false.
[12] Google Matrix, v:Scholarpedia, [ogled 9. 9. 2021], dostopno na http://www.scholarpedia.
org/article/Google_matrix.
[13] Google Matrix, v: Wikipedia: The Free Encyclopedia, [ogled 5. 9. 2021], dostopno na https:
//en.wikipedia.org/wiki/Google_matrix.
[14] PageRank, v: Wikipedia: The Free Encyclopedia, [ogled 5. 9. 2021], dostopno na https:
//en.wikipedia.org/wiki/PageRank.
[15] Perron-Frobenius theorem, v: Wikipedia: The Free Encyclopedia, [ogled 9. 9. 2021], dostopno na https://en.wikipedia.org/wiki/Perron%E2%80%93Frobenius_theorem.
[16] Stochastic Matrices, v:Interactive Linear Algebra, [ogled 9. 9. 2021], dostopno na https:
//textbooks.math.gatech.edu/ila/stochastic-matrices.html.
[17] Stochastic matrix, v: Wikipedia: The Free Encyclopedia, [ogled 5. 9. 2021], dostopno na https://en.wikipedia.org/wiki/Stochastic_matrix.
[18] What Is a Totally Nonnegative Matrix?, v:Nick Higham, [ogled 9. 9. 2021], dostopno na https:
//nhigham.com/category/what-is/.
