Finanční Matematika - 11. přednáška Perronova věta, systém bonus malus Martin Panák 3. května 2016 Perronova-Frobeniova věta Theorem Jestliže je A primitivní matice se spektrálním poloměrem A G IR, pak je X jednoduchým kořenem charakteristického polynomu matice A, který je ostře větší než absolutní hodnota kteréhokoliv jiného vlastního čísla matice A. K vlastnímu číslu X navíc existuje vlastní vektor x s výhradně kladnými prvky x\. V důkazu se budeme opírat o intuici elementární geometrie. Částečně budeme použité koncepty upřesňovat už v analytické geometrii ve čtvrté kapitole, některé analytické aspekty budeme studovat podrobněji v kapitolách páté a později, přesné důkazy některých analytických kroků v této učebnici nepodáme vůbec. Snad budou následující úvahy nejen osvětlovat dokazovaný teorém, ale budou také samy o sobě motivací pro naše další studium geometrie i matematické analýzy. Uvažme libovolný mnohostěn P obsahující počátek 0 e IR". Jestliže nějaká iterace lineárního zobrazení^ : Kn —Kn zobrazuje P do jeho vnitřku, pak je spektrální poloměr zobrazení íp ostře menší než jedna. Uvažme libovolný mnohostěn P obsahující počátek 0 £ Jestliže nějaká iterace lineárního zobrazení^ : Kn —Kn zobrazuje P do jeho vnitřku, pak je spektrální poloměr zobrazení íp ostře menší než jedna. Uvažme matici A zobrazení íp ve standardní bázi. Protože vlastní čísla Ak jsou k-té mocniny vlastních čísel matice A, můžeme rovnou bez újmy na obecnosti předpokládat, že samotné zobrazení íp již zobrazuje P do vnitřku P. Zjevně tedy nemůže mít íp Žádnou vlastní hodnotu s absolutní hodnotou větší nezjedná. Důkaz dále povedeme sporem. Předpokládejme, že existuje vlastní hodnota A s |A| = 1. Máme tedy dvě možnosti. Buď je A^ = 1 pro vhodné k nebo takové k neexistuje. Obrazem P je uzavřená množina (to znamená, že pokud se body v obrazu budou hromadit k nějakému bodu y v IRn, bude y opět v obrazu) a hranici P tento obraz vůbec neprotíná. Nemůže tedy mít íp pevný bod na hranici P ani nemůže existovat žádný bod na hranici, ke kterému by se mohly libovolně blížit body v obrazu. Obrazem P je uzavřená množina (to znamená, že pokud se body v obrazu budou hromadit k nějakému bodu y v IRn, bude y opět v obrazu) a hranici P tento obraz vůbec neprotíná. Nemůže tedy mít íp pevný bod na hranici P ani nemůže existovat žádný bod na hranici, ke kterému by se mohly libovolně blížit body v obrazu. První argument vylučuje, že by nějaká mocnina A byla jedničkou, protože to by takový pevný bod na hranici P jistě existoval. Ve zbývajícím případě jistě existuje dvourozměrný podprostor W C ]Rn, na nějž se íp zužuje coby rotace o iracionální argument a jistě existuje bod y v průniku W s hranicí P. Pak by ale byl bod y libovolně přesně přiblížen body z množiny ipn(y) při průchodu přes všechny iterace, a tedy by musel sám být také v obrazu. Obrazem P je uzavřená množina (to znamená, že pokud se body v obrazu budou hromadit k nějakému bodu y v IRn, bude y opět v obrazu) a hranici P tento obraz vůbec neprotíná. Nemůže tedy mít íp pevný bod na hranici P ani nemůže existovat žádný bod na hranici, ke kterému by se mohly libovolně blížit body v obrazu. První argument vylučuje, že by nějaká mocnina A byla jedničkou, protože to by takový pevný bod na hranici P jistě existoval. Ve zbývajícím případě jistě existuje dvourozměrný podprostor W C ]Rn, na nějž se íp zužuje coby rotace o iracionální argument a jistě existuje bod y v průniku W s hranicí P. Pak by ale byl bod y libovolně přesně přiblížen body z množiny ipn(y) při průchodu přes všechny iterace, a tedy by musel sám být také v obrazu. Došli jsme tedy ke sporu a lemma je ověřeno. Nyní se dáme do důkazu Perronovy věty. Naším prvním krokem bude ověření existence vlastního vektoru, který má všechny prvky kladné. Uvažme za tím účelem tzv. standardní simplex S = {x = (xi,... ,x„) x = 1, x/ > 0, / = 1,..., n}. Nyní se dáme do důkazu Perronovy věty. Naším prvním krokem bude ověření existence vlastního vektoru, který má všechny prvky kladné. Uvažme za tím účelem tzv. standardní simplex S = {x = (xi,...,xn)J"; |x| = 1,x; > 0, / = 1,..., n}. Protože všechny prvky v matici A jsou nezáporné, obraz A • x bud mít samé nezáporné souřadnice stejně jako x a alespoň jedna z nich bude vždy nenulová. Nyní se dáme do důkazu Perronovy věty. Naším prvním krokem bude ověření existence vlastního vektoru, který má všechny prvky kladné. Uvažme za tím účelem tzv. standardní simplex S = {x = (xi,...,xn)J"; |x| = 1,x; > 0, / = 1,..., n}. Protože všechny prvky v matici A jsou nezáporné, obraz A • x bude mít samé nezáporné souřadnice stejně jako x a alespoň jedna z nich bude vždy nenulová. Zobrazení x i—>> \A • x|_1(/4 • x) proto zobrazuje S do sebe, Toto zobrazení S —> S splňuje všechny předpoklady tzv. Brouwerovy věty o pevném bodě a proto existuje vektor y G S takový, že je tímto zobrazením zobrazen sám na sebe. Nyní se dáme do důkazu Perronovy věty. Naším prvním krokem bude ověření existence vlastního vektoru, který má všechny prvky kladné. Uvažme za tím účelem tzv. standardní simplex S = {x = (xi,... ,x„) T X = 1, x/ > 0, / = 1,..., n}. Protože všechny prvky v matici A jsou nezáporné, obraz A • x bude mít samé nezáporné souřadnice stejně jako x a alespoň jedna z nich bude vždy nenulová. Zobrazení x i—>> \A • x|_1(/4 • x) proto zobrazuje S do sebe, Toto zobrazení S —> S splňuje všechny předpoklady tzv. Brouwerovy věty o pevném bodě a proto existuje vektor y £ S takový, že je tímto zobrazením zobrazen sám na sebe. To ale znamená, že A- y = A y, A = A • y a našli jsme vlastní vektor, který leží v S Protože ale má nějaká mocnina A podle našeho předpokladu samé kladné prvky a samozřejmě je také Ak • y = \ky, všechny souřadnice vektoru y jsou ostře kladné (tj. leží ve vnitřku S) a A > 0. Protože ale má nějaká mocnina A podle našeho předpokladu samé kladné prvky a samozřejmě je také Ak • y = \ky, všechny souřadnice vektoru y jsou ostře kladné (tj. leží ve vnitřku S) a A > 0. Abychom dokázali zbytek věty, budeme uvažovat zobrazení zadané maticí A ve výhodnější bázi a navíc ho vynásobíme konstantou A-1 B = A"1^-1 'A - V), kde V je diagonální matice se souřadnicemi y; právě nalezeného vlastního vektoru y na diagonále. Evidentně je B také primitivní matice a navíc je vektor z — (1,..., 1)T jejím vlastním vektorem s vlastní hodnotou 1, protože zjevně Y • z = y. Protože ale má nějaká mocnina A podle našeho předpokladu samé kladné prvky a samozřejmě je také Ak • y = \ky, všechny souřadnice vektoru y jsou ostře kladné (tj. leží ve vnitřku S) a A > 0. Abychom dokázali zbytek věty, budeme uvažovat zobrazení zadané maticí A ve výhodnější bázi a navíc ho vynásobíme konstantou A-1 B = A"1^-1 'A - V), kde V je diagonální matice se souřadnicemi y; právě nalezeného vlastního vektoru y na diagonále. Evidentně je B také primitivní matice a navíc je vektor z — (1,..., 1)T jejím vlastním vektorem s vlastní hodnotou 1, protože zjevně Y • z = y. Jestliže nyní dokážeme, že ji — 1 je jednoduchým kořenem charakteristického polynomu matice B a všechny ostatní kořeny mají absolutní hodnotu ostře menší nezjedná, bude Perronova věta dokázána. K tomu se nám teď bude hodit dříve dokázané pomocné lemma. Uvažujme matici B jako matici lineárního zobrazení, které zobrazuje řádkové vektory u = (í7i, ..., un) i—y u ■ B — v . tj. pomoci násobení zprava. Díky tomu, že je z = (1,..., 1)T vlastním vektorem matice B, je součet souřadnic řádkového vektoru v roven n n Uibu = Uí = x> K tomu se nám teď bude hodit dříve dokázané pomocné lemma. Uvažujme matici B jako matici lineárního zobrazení, které zobrazuje řádkové vektory U = (i7i, . . . , Un) h->> u • B — v , tj. pomoci násobení zprava. Díky tomu, že je z = (1,..., 1)T vlastním vektorem matice 6, je součet souřadnic řádkového vektoru v roven n n uibij = ^2ui = l, ij=l 1=1 kdykoliv je u G S. Proto toto zobrazení zobrazuje simplex S na sebe a má také jistě v S vlastní (řádkový) vektor w s vlastní hodnotou jedna (pevný bod, opět dle Brouwerovy věty). Protože nějaká mocnina Bk obsahuje samé ostře pozitivní prvky, je nutně obraz simplexu S v k—té iteraci zobrazení daného B uvnitř S. To už jsme blízko použití našeho lemmatu, které jsme si pro důkaz připravili. Budeme i nadále pracovat s řádkovými vektory a označme si P posunutí simplexu S do počátku pomocí vlastního vektoru w, který jsme právě našli, tj. P = — w + S. Evidentně je P mnohostěn obsahující počátek a vektorový pod prostor V C IRn generovaný P je invariantní vůči působení matice B pomocí násobení řádkových vektorů zprava. Zúžení našeho zobrazení na P tedy splňuje předpoklady pomocného lemmatu, a proto nutně musí být všechny jeho vlastní hodnoty v absolutní hodnotě menší nezjedná. Budeme i nadále pracovat s řádkovými vektory a označme si P posunutí simplexu S do počátku pomocí vlastního vektoru w, který jsme právě našli, tj. P = — w + S. Evidentně je P mnohostěn obsahující počátek a vektorový pod prostor V C IRn generovaný P je invariantní vůči působení matice B pomocí násobení řádkových vektorů zprava. Zúžení našeho zobrazení na P tedy splňuje předpoklady pomocného lemmatu, a proto nutně musí být všechny jeho vlastní hodnoty v absolutní hodnotě menší nezjedná. Ještě se musíme vypořádat se skutečností, že právě uvažované zobrazení je dáno násobením řádkových vektorů zprava maticí B (zatímco nás původně zajímalo chování zobrazení, zadaného maticí B pomocí násobení sloupcových vektorů zleva). To je ale ekvivalentní násobení transponovaných sloupcových vektorů transponovanou maticí B obvyklým způsobem zleva. Dokázali jsem tedy vlastně potřebné tvrzení o vlastních číslech pro matici transponovanou k naší matici B. Transponování ale vlastní čísla nemění. Budeme i nadále pracovat s řádkovými vektory a označme si P posunutí simplexu S do počátku pomocí vlastního vektoru w, který jsme právě našli, tj. P = — w + S. Evidentně je P mnohostěn obsahující počátek a vektorový pod prostor V C IRn generovaný P je invariantní vůči působení matice B pomocí násobení řádkových vektorů zprava. Zúžení našeho zobrazení na P tedy splňuje předpoklady pomocného lemmatu, a proto nutně musí být všechny jeho vlastní hodnoty v absolutní hodnotě menší nezjedná. Ještě se musíme vypořádat se skutečností, že právě uvažované zobrazení je dáno násobením řádkových vektorů zprava maticí B (zatímco nás původně zajímalo chování zobrazení, zadaného maticí B pomocí násobení sloupcových vektorů zleva). To je ale ekvivalentní násobení transponovaných sloupcových vektorů transponovanou maticí B obvyklým způsobem zleva. Dokázali jsem tedy vlastně potřebné tvrzení o vlastních číslech pro matici transponovanou k naší matici B. Transponování ale vlastní čísla nemění. Dimenze prostoru V je přitom n — 1, takže důkaz věty je ukončen. Následující velice užitečné tvrzení má při znalosti Perronovy věty až překvapivě jednoduchý důkaz a ukazuje, jak silná je vlastnost primitívnosti matice zobrazení. Corollary Jestliže A = (a,y) je primitivní matice axGK" její vlastní vektor se všemi souřadnicemi nezápornými a vlastní hodnotou A, pak A > 0 je spektrální poloměr A. Navíc platí n n minj6{l,.,n} a'J - A - maX/€{l,...,n} J2 3iJ- ;=i i=i Uvažme vlastní vektor x z dokazovaného tvrzení. Protože je A primitivní, můžeme zvolit pevně k tak, aby Ak už měla samé pozitivní prvky, a pak je samozřejmě i Ak • x = A^x vektor se samými ostře kladnými souřadnicemi. Nutně proto je A > 0. Uvažme vlastní vektor x z dokazovaného tvrzení. Protože je A primitivní, můžeme zvolit pevně k tak, aby Ak už měla samé pozitivní prvky, a pak je samozřejmě i Ak • x = A^x vektor se samými ostře kladnými souřadnicemi. Nutně proto je A > 0. Z Perronovy věty víme, že spektrální poloměr ji]e vlastním číslem a zvolme takový vlastní vektor y k /i, že rozdíl x — y má samé kladné souřadnice. Potom nutně pro všechny mocniny n 0 < An • (x - y) = A"x - /i"y, ale zároveň platí A < ji. Odtud již vyplývá A = ji. Zbývá odhad spektrálního poloměru pomocí minima a maxima součtů jednotlivých sloupců matice. Označme je bmjn a bmax, zvolme za x vektor se součtem souřadnic jedna a počítejme: Zbývá odhad spektrálního poloměru pomocí minima a maxima součtů jednotlivých sloupců matice. Označme je bmjn a br zvolme za x vektor se součtem souřadnic jedna a počítejme: 'maxi n n Y a ab + bc + 2ac + b2/2 . \cj \ c2 + bc + b2/A J Podotkněme, že za definiční obor (a pochopitelně i obor hodnot) T vlastně bereme pouze vektory b , kde a, b, c £ [0,1], a + b + c = 1. Chtěli bychom zadat operaci T pomocí násobení vektoru (a, b, c) jistou konstantní maticí. To však očividně není možné (zobrazení T není lineární). Nejedná se tedy o Markovův proces a nelze zjednodušit určování, co se stane po velmi dlouhé době, jako v předešlých případech. Můžeme ale vypočítat, co se stane, když aplikujeme zobrazení T dvakrát po sobě. Ve druhém kroku dostáváme / a2 + ab+b2/A \ /t£\ T : i ab + bc + 2ac + b2/2 \ ^ r| , V c2 + bc + b2/A J \tiJ kde 2 u í 2 u b2 a1 + ab + — j + í az + ab + — + - í a6+ 6c + 2ac + y j a2 + ab + ^ Tab + 6c + 2ac + y\ + ab + 6c + 2ac + + ab + be + 2ac + 2 t t A c2 + 6c + — I + .2\2 + 2 ^az + ab + —J (^c + 6c + — J + - (^a6 + 6c + 2ac + —j , : ^c2 + 6c + f^J + ^a6 + 6c + 2ac + y ^ ^c2 + 6c + ^ + + - í a6+ 6c + 2ac + y j . Lze ukázat (využitím a + b + c = 1), že 1 9 k2 9 k2 t£ = a + ab -\--, Í2 = ab + be + 2ac + — t% = c2 + bc + tj a2 + ab+ i>2/4 T : I ab+ bc + 2ac + b2/2 c2 + bc + i>2/4 a2 + ab+ i>2/4 i-)- I a/? + be + 2ac + b2/2 c2 + bc + i>2/4 Získali jsme tak překvapivý výsledek, že dalším aplikováním transformace T se vektor obdržený v prvním kroku nezmění. To znamená, že výskyt uvažovaných dvojic alel je po libovolně dlouhé době totožný jako v první generaci potomstva. Pro velkou populaci jsme tak dokázali, že evoluční vývoj by se realizoval během jediné generace, kdyby nedocházelo k mutacím nebo k selekci. Necht jsou dány dvě urny, které obsahují dohromady n bílých a n černých koulí. V pravidelných časových intervalech je z obou uren vylosována jedna koule a přemístěna do druhé urny, přičemž počet koulí v obou urnách je na začátku (a tedy po celou dobu) právě n. Zadejte tento Markovův proces pravděpodobnostní maticí přechodu T. Tento příklad se používá ve fyzice jako model prolínání dvou nestlačitelných kapalin (již v roce 1769 ho zavedl D. Bernoulli) nebo analogicky jako model difúze plynů. Stavy 0,1,..., n budou odpovídat kupř. počtu bílých koulí v jedné pevně zvolené urně. Tento údaj totiž současně zadává, kolik černých koulí je ve zvolené urně (všechny ostatní koule jsou pak ve druhé z uren). Pokud v jistém kroku dojde ke změně stavu j £ {1,..., n} na j — 1, znamená to, že ze zvolené urny byla vytažena bílá koule a z druhé černá. To se stane s pravděpodobností ■2 lmJ_ = J_ n n n2 Přechodu ze stavu j £ {0,..., n — 1} do j + 1 odpovídá vytažení černé koule ze zvolené urny a bílé z té druhé s pravděpodobností n-j n-j = (n-j)2 n n n2 Soustava zůstane ve stavu j G {1,..., n — 1}, jestliže z obou uren byly vytaženy koule stejné barvy, což má pravděpodobnost ■a ■ ■ ■ r\ ■ í 41 " -i ^ 1 >OQ,0 i /I t-i _ i irt _ i i ) i l irt _ i l Při užití tohoto modelu ve fyzice nás samozřejmě zajímá složení uren po uplynutí určité doby (po daném počtu výměn v závislosti na předešlém složení uren). Bude-li počáteční stav např. 0, můžeme pomocí mocnin matice T sledovat, s jakou pravděpodobností přibývají ve zvolené urně bílé koule. Také lze potvrdit očekávaný výsledek, že počáteční rozdělení koulí bude ovlivňovat jejich rozdělení po delší době zanedbatelným způsobem. Při užití tohoto modelu ve fyzice nás samozřejmě zajímá složení uren po uplynutí určité doby (po daném počtu výměn v závislosti na předešlém složení uren). Bude-li počáteční stav např. 0, můžeme pomocí mocnin matice T sledovat, s jakou pravděpodobností přibývají ve zvolené urně bílé koule. Také lze potvrdit očekávaný výsledek, že počáteční rozdělení koulí bude ovlivňovat jejich rozdělení po delší době zanedbatelným způsobem. Kdybychom jednotlivé koule očíslovali, místo výběru po jedné kouli z uren vylosovali nějaké z čísel 1, 2,..., 2n a kouli, jejíž číslo bylo vytaženo, přemístili do druhé urny, obdrželi bychom Markovův proces se stavy 0,1,..., 2n (počet koulí ve zvolené urně), kdy se tak už nerozlišuje barva koulí. Tento Markovův řetězec je rovněž ve fyzice důležitý. (P. a T. Ehrenfestovi jej zavedli v roce 1907.) Používá se jako model výměny tepla mezi dvěma izolovanými tělesy (teplota je reprezentována počtem koulí, tělesa urnami).