Matematika I - 13. přednáška Lineární procesy, diferenční rovnice, Markovovy procesy Michal Bulant Masarykova univerzita Fakulta informatiky 13. 5. 2009 □ S Obsah přednášky Lineární procesy • Iterované procesy 9 Markovovy procesy □ s • Martin Panák, Jan Slovák - Drsná matematika, e-text. • Roman Hilscher - MB101, e-text. • Slidy z přednášek a democvičeni • Martin Panák, Jan Slovák - Drsná matematika, e-text. • Roman Hilscher - MB101, e-text. • Slidy z přednášek a democvičení • Pavel Horák, Úvod do lineární algebry, MU Brno, skripta (http://www.math.muni.cz/~horak) • Luboš Motl, Miloš Zahradník, Pěstujeme lineární algebru, 3. vydání, Univerzita Karlova v Praze, Karolinum, 348 stran (elektronické vydání také na http://www.kolej.mff.cuni.cz/~lmotm275/skripta/). Plán přednášky Lineární procesy • Iterované procesy 9 Markovovy procesy □ s Lineární procesy Jednoduché lineární procesy jsou dány lineárními zobrazeními ip : V —> W na vektorových prostorech. Pokud nám totiž vektor v G V představuje stav nějakého námi sledovaného jevu (třeba počty občanů tříděných dle nejvyšší dosažené kvalifikace, stav zásob jednotlivých dílů a výrobků atd.), pak 0. Evidentně bude proto existovat právě jedno kladné A, pro které bude q(X) = 1 a tedy p(A) = 0. Jinými slovy, pro každou Leslieho matici existuje právě jedno kladné vlastní číslo. Leslieho model růstu (3) Pro konkrétní koeficienty (např. když všechny f; jsou také mezi nulou a jedničkou) můžeme dojít k závěru, že absolutní hodnoty ostatních vlastních čísel jsou ostře menší než jedna, zatímco dominantní vlastní číslo může být vetší než jedna. V takovém případě při iteraci kroků našeho procesu dojde při libovolné počáteční hodnotě xo k postupnému přiblížení rozložení populace do věkových skupin k poměrům komponent vlastního vektoru příslušného k dominantnímu vlastnímu číslu. Leslieho model růstu (3) Pro konkrétní koeficienty (např. když všechny f; jsou také mezi nulou a jedničkou) můžeme dojít k závěru, že absolutní hodnoty ostatních vlastních čísel jsou ostře menší než jedna, zatímco dominantní vlastní číslo může být vetší než jedna. V takovém případě při iteraci kroků našeho procesu dojde při libovolné počáteční hodnotě xo k postupnému přiblížení rozložení populace do věkových skupin k poměrům komponent vlastního vektoru příslušného k dominantnímu vlastnímu číslu. Například pro matici A = vyjdou vlastní hodnoty přibližně 1.03, 0, -0.5, -0,27 + 0.74/, -0.27 ^^.74? 0 0.2 0.8 0.6 °\ 0.95 0 0 0 0 0 0.8 0 0 0 0 0 0.7 0 0 0 0 0 0.6 0/ eslieho model růstu (4) Vlastním vektorem příslušným dominantnímu vlastnímu číslu 1.03 je přibližně x = (30 27 21 14 8). Zvolili jsme rovnou jediný vlastní vektor se součtem složek rovným stu, zadává nám proto přímo výsledné procentní rozložení populace. □ s - Příklad Uvažujme Leslieho model růstu pro populaci krys, které máme rozděleny do tří věkových skupin: do jednoho roku, od jednoho do dvou let a od dvou let do tří. Předpokládáme, že se žádná krysa nedožívá více než tří let. Průměrná porodnost v jednotlivých věkových skupinách připadajících na jednu krysu je následující: v 1.skupině je to nula a ve druhé i třetí 2 krysy. Krysy, které se dožijí jednoho roku umírají až po druhém roce života (úmrtnost ve druhé skupině je nulová). Určete úmrtnost v první skupině víte-li, že daná populace krys stagnuje (počet jedinců v ní se nemění). □ s Příklad Uvažujme Leslieho model růstu pro populaci krys, které máme rozděleny do tří věkových skupin: do jednoho roku, od jednoho do dvou let a od dvou let do tří. Předpokládáme, že se žádná krysa nedožívá více než tří let. Průměrná porodnost v jednotlivých věkových skupinách připadajících na jednu krysu je následující: v 1.skupině je to nula a ve druhé i třetí 2 krysy. Krysy, které se dožijí jednoho roku umírají až po druhém roce života (úmrtnost ve druhé skupině je nulová). Určete úmrtnost v první skupině víte-li, že daná populace krys stagnuje (počet jedinců v ní se nemění). M a r kovový procesy a řetězce Velice častý a zajímavý případ lineárních procesů je popis systému, který se může nacházet v m různých stavech s různou pravděpodobností. V jistém okamžiku je ve stavu s pravděpodobností a; pro stav / a k přechodu z možného stavu / do stavu j dojde s pravděpodobností ty. Můžeme tedy proces zapsat takto: V čase n je systém popsán pravděpodobnostním vektorem xn = (ai,..., am). To znamená, že všechny komponenty vektoru x jsou reálná nezáporná čísla a jejich součet je roven jedné. Komponenty udávají rozdělení pravděpodobnosti jednotlivých možností stavů systému. Rozdělení pravděpodobností pro čas n + 1 bude dáno vynásobením pravděpodobnostní maticí přechodu T = (ty), tj. xn+i = T xn. Protože předpokládáme, že vektor x zachycuje všechny možné stavy, budou všechny sloupce matice T tvořeny také pravděpodobnostními vektory. Takovému procesu říkáme Markovův proces. Všimněme si, že každý pravděpodobnostní vektor x je opět zobrazen na vektor se součtem souřadnic jedna: E tu* = EGC ŕíH = Ex; = L ij J i J □ s Protože předpokládáme, že vektor x zachycuje všechny možné stavy, budou všechny sloupce matice T tvořeny také pravděpodobnostními vektory. Takovému procesu říkáme Markovův proces. Všimněme si, že každý pravděpodobnostní vektor x je opět zobrazen na vektor se součtem souřadnic jedna: E tu* = EGC ŕíH = Ex; = L ij j i j Protože je součet řádků matice T vždy roven vektoru (1,..., 1), bude jednička zaručeně vlastním číslem matice T a k ní musí existovat vlastní vektor xo. Abychom mohli podrobněji pochopit chování Markovových procesů, uvedeme si docela snadno pochopitelné obecné tvrzení o maticích, tzv. Perronovu-Frobeniovu větu. □ s Věta (Perron-Frobenius) Nechi A je reálná čtvercová matice dimenze m s kladnými prvky Pak platí O existuje reálné vlastní číslo Xm matice A takové, že pro všchna ostatní vlastní čísla X platí \X\ < Xm (dominantní vl.č.J, O vlastní číslo Xm má algebraickou násobnost jedna, Q vlastní podprostor odpovídající Xm obsahuje vektor se všemi souřadnicemi kladnými Q platí odhad min,- V- a-ý < Xm < max,- V- a/,-. □ s Lineárni proces oooooooo» Veta (Perron-Frobenius) Nechi A je reálna čtvercová matice dimenze m s kladnými prvky Pak platí O existuje reálné vlastní číslo Xm matice A takové, že pro všchna ostatní vlastní čísla X platí \X\ < Xm (dominantní vi. č.), O vlastní číslo Xm má algebraickou násobnost jedna, Q vlastnípodprostor odpovídající Xm obsahuje vektor se všemi souřadnicemi kladnými Q platí odhad min,- V- a-ý < Xm < max,- V- a/,-. Důsledkem této věty pro Markovovy procesy s maticí, která nemá žádné nulové prvky (nebo jejíž některá mocnina má tuto vlastnost), je • existence vlastního vektoru Xoo pro vlastní číslo 1, který je pravděpodobnostní • přibližování hodnoty iterací Tkxo k vektoru x^ pro jakýkoliv pravděpodobnostní vektor x0. Příklady Markovových procesů a viz lecturel3/iterovane_procesy.pdf (applet http://cauchy.math.colostate.edu/Applets/ PredatorPrey/predatorprey.htm) □ s Příklady Markovových procesů a viz lecturel3/iterovane_procesy.pdf (applet http://cauchy.math.colostate.edu/Applets/ PredatorPrey/predatorprey.htm) • viz lecturel3/google-PageRank.pdf (resp. lecturel3/SlideGooglePageRank.pdf) □ s a viz lecturel3/iterovane_procesy.pdf (applet http://cauchy.math.colostate.edu/Applets/ PredatorPrey/predatorprey.htm) • viz lecturel3/google-PageRank.pdf (resp. lecturel3/SlideGooglePageRank.pdf) • Mlsný hazardér (viz prednasky_MB101_podzim2008.pdf) Lineární diferenční rovnice • Viz roughmath.pdf, kapitola 1, např. Fibonacciho posloupnost • Viz roughmath.pdf, kapitola 3, odst. 1.2. (př. 3.8). □ s