Lineární procesy ooooooooooooooo Lineární diferenční rovnice ooooooooooo Matematika I - 12. přednáška Lineární procesy, diferenční rovnice, Markovovy procesy Michal Bulant Masarykova univerzita Fakulta informatiky 14. 5. 2012 Lineární procesy ooooooooooooooo Obsah přednášky Lineární diferenční rovnice ooooooooooo Ql Lineární procesy • Iterované procesy • M a r kovový procesy Q Lineární diferenční rovnice • Martin Panák, Jan Slovák - Drsná matematika, e-text. • Roman Hilscher - MB101, e-text. • Slidy z přednášek a democvičení • 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árni 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/). Lineární procesy Lineární diferenční rovnice ooooooooooooooo ooooooooooo Plán přednášky Qi Lineární procesy • Iterované procesy • M a r kovový procesy Q Lineární diferenční rovnice 4 D ► 4 S ► 4 = * 4 š ► Jednoduché lineární procesy jsou dány lineárními zobrazeními tp : 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 (f(v) může představovat výsledek provedené operace (výsledek vzdělávací činnosti školské soustavy nebo výroba a prodej za určité časové období apod.). Pokud chceme dosáhnout předem daného výsledku b G W takového jednorázového procesu, řešíme problém ip{x) = b pro neznámý vektor x. V pevně zvolených souřadnicích pak máme matici A zobrazení ip a souřadné vyjádření vektoru b. Jak jsme si ukázali už dříve, řešení příslušné homogenní úlohy A-x = 0 je vektorovým pod prostorem. Představme si, že zkoumáme nějaký systém jednotlivců (pěstovaná zvířata, hmyz, buněčné kultury apod) rozdělený do m skupin (třeba podle stáří, fází vývoje hmyzu apod.). Stav xn je tedy dán vektorem (ai,..., am) závisejícím na okamžiku r^, ve kterém systém pozorujeme. Lineární model vývoje takového systému je dán maticí A dimenze n, která zadává změnu vektoru xn na Xn+l = A ■ Xn při přírůstku času z ŕ> na r>+i. Představme si, že zkoumáme nějaký systém jednotlivců (pěstovaná zvířata, hmyz, buněčné kultury apod) rozdělený do m skupin (třeba podle stáří, fází vývoje hmyzu apod.). Stav xn je tedy dán vektorem (ai,..., am) závisejícím na okamžiku tn, ve kterém systém pozorujeme. Lineární model vývoje takového systému je dán maticí A dimenze n, která zadává změnu vektoru xn na Xn+l = A ■ Xn při přírůstku času z ŕ> na r>+i. V praktických modelech se často setkáváme se situací, kdy je vývoj systému v jednom časovém období dán lineárním procesem, zajímáme se ale o chování systému po mnoha iteracích. Často přitom samotný lineární proces zůstává pořád stejný, z pohledu našeho matematického modelu tedy nejde o nic jiného než opakované násobení stavového vektoru stále stejnou maticí. Dobrým příkladem lineárních procesů je tzv. Leslieho model růstu. V takových modelech vystupuje matice popisující vývoj populace rozdělené na několik věkových skupin (h h h U h\ ti 0 0 o o 0 t2 0 0 0 0 0 r3 0 0 \0 0 0 t4 0/ kde f, označuje relativní plodnost příslušné věkové skupiny (ve sledovaném časovém skoku vznikne z N jedinců v /-té skupině f,N jedinců nových, tj. ve skupině první), zatímco (1 — 77) je relativní úmrtnost /-té skupiny během jednoho období. Všechny koeficienty jsou tedy kladná reálná čísla a r jsou mezi nulou a jedničkou. Přímým výpočtem (třeba využitím Laplaceova rozvoje) nyní spočteme charakteristický polynom p(A) = det(i4 - XE) = -A5 + aA4 + bX3 + cX2dX + e s vesměs nezápornými koeficienty a, b, c, d, e, např. e = t1t2t3t4/í5. Je tedy p(A) = -A5(l - g(A)) kde q(X) = (j + -j^ + ■ ■ ■ + je ostře klesající a nezáporná funkce pro A > 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. Lineární procesy Lineární diferenční rovnice oooo»oooooooooo ooooooooooo Pro konkrétní praktické koeficienty (např. když všechny f, jsou také mezi nulou a jedničkou) typicky dochází k situaci, kdy absolutní hodnoty ostatních vlastních čísel jsou ostře menší než jedna, zatímco dominantní vlastní číslo bývá větší než jedna. V takovém případě při iteraci kroků (kdy vlastně umocňujeme matici A) 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. 4Ľ3k4l3*4 = k4 = * -š -O^O Lineární procesy Lineární diferenční rovnice oooo»oooooooooo ooooooooooo Pro konkrétní praktické koeficienty (např. když všechny f, jsou také mezi nulou a jedničkou) typicky dochází k situaci, kdy absolutní hodnoty ostatních vlastních čísel jsou ostře menší než jedna, zatímco dominantní vlastní číslo bývá větší než jedna. V takovém případě při iteraci kroků (kdy vlastně umocňujeme matici A) 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. Je-li totiž obecný vektor x = a\ • x\ + ... + am ... xm lineární kombinací vlastních vektorů xi,... ,xm, příslušných vlastním hodnotám Ai,..., Am, pak po k iteracích dostaneme Ak ■ x = aiA^xi + ... amA^,xm, takže za předpokladu, že |A/| < 1 pro všechna / > 2, budou všechny komponenty ve vlastních podprostorech velmi rychle mizet, kromě kompomenty aiA^xi. Rozložení populace do věkových skupin se tak budou rychle blížit poměrům složek vlastního vektoru příslušného k dominantnímuq/lasti»iímLrčíslu Ai.i o«.o Příklad Například pro matici (0 0.2 0.8 0.6 o\ 0.95 0 0 0 0 0 0.8 0 0 0 0 0 0.7 0 0 V o 0 0 0.6 vyjdou vlastní hodnoty přibližně 1.03, 0, -0.5, -0,27 + 0.74/, -0.27 - 0.74/ s velikostmi 1.03,0,0.5,0.78,0.78. 00.0 Příklad Například pro matici (0 0.2 0.8 0.6 o\ 0.95 0 0 0 0 0 0.8 0 0 0 0 0 0.7 0 0 V o 0 0 0.6 vyjdou vlastní hodnoty přibližně 1.03, 0, -0.5, -0,27 + 0.74/, -0.27 - 0.74/ s velikostmi 1.03,0,0.5,0.78,0.78. Vlastním vektorem příslušným dominantnímu vlastnímu číslu 1.03 je přibližně x = (30 27 21 14 8). Prí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í). Prí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í). Řešení Matice 0 2 2 a 0 0 0 1 0 Lineární procesy ooooooo»ooooooo Lineární diferenční r ooooooooooo 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í fy/. 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 = (fy/), tj. Xn+l = T -Xn. Lineární procesy 00000000*000000 Lineární diferenční rovnice ooooooooooo 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 ť* = e(e = e*/ = l ij J i J Lineární procesy 00000000*000000 Lineární diferenční rovnice ooooooooooo 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 ť* = e(e = e*/ = l ij J i j Protože je součet řádků matice T vždy roven vektoru (1,..., 1), je zřejmě matice T — E singulární a jednička proto bude zaručeně vlastním číslem matice T. Abychom mohli podrobněji pochopit chování M a r kovových procesů, uvedeme si docela snadno pochopitelné obecné tvrzení o maticích, tzv. Perronovu-Frobeniovu větu. Lineární procesy OOOOOOOOO0OOOOO Lineární diferenční rovnice ooooooooooo Věta (Perron-Frobenius) Necht A je reálná čtvercová matice dimenze m s kladnými prvky. Pak platí Q existuje reálné vlastní číslo Xm matice A takové, že pro všechna ostatní vlastní čísla X platí \X\ < Am (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 O platí odhad miny J2i aij < < maxy J2i aij- Lineární procesy oooooooooo«oooo Lineární diferenční rovnice ooooooooooo 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 • vlastní číslo 1 je dominantní • existence vlastního vektoru Xoo pro vlastní číslo 1, který je pravděpodobnostní • přibližování hodnoty iterací TkXQ k vektoru x^ pro jakýkoliv pravděpodobnostní vektor xq. Lineárni' procesy Lineární diferenční rovnice ooooooooooo»ooo ooooooooooo Příklady Markovových procesu • viz lecturel3/iterovane_procesy.pdf (applet http://cauchy.math.colostate.edu/Applets/ PredatorPrey/predatorprey.htm) • viz lecturel3/iterovane_procesy.pdf (applet http://cauchy.math.colostate.edu/Applets/ PredatorPrey/predatorprey.htm) • viz lecture 13/google-PageRank.pdf (resp. lecturel3/SlideGooglePageRank.pdf) • viz lecturel3/iterovane_procesy.pdf (applet http://cauchy.math.colostate.edu/Applets/ PredatorPrey/predatorprey.htm) • viz lecture 13/google-PageRank.pdf (resp. lecturel3/SlideGooglePageRank.pdf) • 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. • 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) Hazardní hráč sází na to, která strana mince padne. Na začátku hry má tři kremrole. Na každý hod vsadí jednu kremroli a když jeho tip vyjde, tak k ní získá jednu navíc. Pokud ne, tak kremroli prohrává. Hra končí, pokud všechny kremrole prohraje, nebo jich získá pět. Jaká je pravděpodobnost, že hra skončí do čtvrté sázky? Lineární procesy oooooooooooo»oo Lineární diferenční rovnice ooooooooooo Před 7-tým kolem (sázkou) můžeme popsat stav, ve kterém se hráč nachází, náhodným vektorem Xj = (PoO'),PiO'),P2(y'),P3(y'),P4(y'),P5(y'))T, kde p, je pravděpodobnost, že hráč má právě / kremrolí. Pokud má hráč před _/-tou sázkou / kremrolí (/' = 1, 2, 3,4), tak po sázce má s poloviční pravděpodobností / — 1 kremrolí a s poloviční pravděpodobností / + 1 kremrolí. Pokud dosáhne pěti kremrolí nebo pokud všechny prohraje, již se počet kremrolí nemění. Lineární procesy oooooooooooo»oo Lineární diferenční rovnice ooooooooooo Před 7-tým kolem (sázkou) můžeme popsat stav, ve kterém se hráč nachází, náhodným vektorem Xj = (PoO'),PiO'),P2(y'),P3(y'),P4(y'),P5(y'))T, kde p, je pravděpodobnost, že hráč má právě / kremrolí. Pokud má hráč před _/-tou sázkou / kremrolí (/' = 1, 2, 3,4), tak po sázce má s poloviční pravděpodobností / — 1 kremrolí a s poloviční pravděpodobností / + 1 kremrolí. Pokud dosáhne pěti kremrolí nebo pokud všechny prohraje, již se počet kremrolí nemění. Vektor X/+i proto získáme z vektoru Xj vynásobením maticí \ 0 0 0 0\ 0^000 ±0^00 0 \ 0 \ 0 " 0 0^00 o o o I 1/ o o o o Vo Lineární procesy Lineární diferenční rovnice ooooooooooooo»o ooooooooooo Na začátku máme Xo = (0, 0, 0,1, 0, O)7", tedy vektor X4 = AaXq = (|, 0, 0, |), popisuje situaci po čtyřech sázkách. Pravděpodobnost, že hra skončí do čtvrté sázky (včetně) - tj. pravděpodobnost, že bude hráč mít nula nebo pět kremrolí- je rovna součtu první a poslední hodnoty ve vektoru X4, tj. 1 1 3 _ 1 8 ~r 8 2" 4Ľ3k4l3*4 = k4 = * -š -OOO Lineární procesy 00000000000000» Lineární diferenční rovnice ooooooooooo Všimněme si ještě, že matice A popisující vývoj pravděpodobnostního vektoru X je pravděpodobnostní, tedy má součet prvků v každém sloupci 1. Nemá ale vlastnost vyžadovanou v Perronově-Frobeniově větě a snadným výpočtem zjistíte (nebo přímo uvidíte bez počítání), že existují dva lineárně nezávislé vlastní vektory příslušné k vlastnímu číslu A = 1 - případ, kdy hráči nezůstane žádná kremrole, tj. x = (1, O, O, O, O, O)7", nebo případ kdy získá 5 kremrolí a hra tím pádem končí a všechny mu už zůstávají, tj. x = (O, O, O, O, 0,1)T. Všechna ostatní vlastní čísla (přibližně 0.8, 0.3, —0.8, —0.3) jsou v absolutní hodnotě menší než jedna. Proto komponenty v příslušných vlastních podprostorech při iteraci procesu s libovolnou počáteční hodnotou vymizí a proces se blíží k limitní hodnotě pravděpodobnostího vektoru tvaru Xqo := (a, O, O, O, 0,1 — a)7", kde hodnota a závisí na počtu kremrolí, se kterými hráč začíná. V našem případě je to a = 0.4. (Kdyby začal se 4 kremrolemi, bylo by to a = 0.2 atd.) Lineární procesy ooooooooooooooo Plán přednášky Lineární diferenční rovnice ooooooooooo Q Lineární procesy • Iterované procesy • M a r kovový procesy Q Lineární diferenční rovnice Obecnou diferenční rovnicí prvního řádu rozumíme výraz f(n + l) = F(n,f(n)), kde F je známá skalární funkce závislá na dvojicích přirozených čísel. Známe-li počáteční hodnotu ^(0), můžeme spočítat f(l) = F(0, f(0)), poté f (2) = F(l, f(l)) atd. Tímto postupným způsobem můžeme tedy nakonec spočítat hodnotu f(n) pro libovolné n G N. Všimněme si, že tato úvaha je podobná konstrukci přirozených čísel z prázdné množiny nebo principu matematické indukce. Definice Obecnou diferenční rovnicí prvního řádu rozumíme výraz f(n + l) = F(n,f(n)), kde F je známá skalární funkce závislá na dvojicích přirozených čísel. Známe-li počáteční hodnotu ^(0), můžeme spočítat f(l) = F(0, f(0)), poté f (2) = F(l, f(l)) atd. Tímto postupným způsobem můžeme tedy nakonec spočítat hodnotu f(n) pro libovolné n G N. Všimněme si, že tato úvaha je podobná konstrukci přirozených čísel z prázdné množiny nebo principu matematické indukce. Jako příklad může sloužit definiční formule pro faktoriál, tj- (n + 1)! = {n + l)-n\ Vidíme, že skutečně vztah pro f(n + 1) závisí na n i na hodnotě f(n). 00.0 Definice Dalším obzvlášť jednoduchým příkladem je f(n) = C pro nějaký pevný skalár C a všechna n a tzv. lineární diferenční rovnice f(n + 1) = a ■ f(n) + b, kde a / 0, a b jsou známé skaláry. 4Ľ3k4l3*4 = k4 = * -š -O^O Definice Dalším obzvlášť jednoduchým příkladem je f(n) = C pro nějaký pevný skalár C a všechna n a tzv. lineární diferenční rovnice f(n + 1) = a ■ f(n) + b, kde a / 0, a b jsou známé skaláry. Takovou diferenční rovnici umíme snadno řešit, je-li b = 0. Pak se totiž jedná o dobře známou rekurentní definici geometrické posloupnosti a platí f(l) = af(0), f(2) = af(l) = a2f(0) atd. Máme tedy pro všechna n f (n) = anf(0). To je např. vztah pro tzv. Malthusiánský model populačního růstu, který vychází z představy, že za zvolený časový interval vzroste populace s konstantní úměrou a vůči předchozýnu gtavu, > < s > 5 Lineární procesy Lineární diferenční rovnice ooooooooooooooo oo»oooooooo Dokážeme si obecný výsledek pro rovnice prvního řádu, které se podobají lineárním, ale připouští proměnné koeficienty a a b, f{n + l) = an-f{n) + bn. Lineární procesy Lineární diferenční rovnice ooooooooooooooo oo»oooooooo Dokážeme si obecný výsledek pro rovnice prvního řádu, které se podobají lineárním, ale připouští proměnné koeficienty a a b, f{n + l) = an-f{n) + bn. Tvrzení Obecné řešení diferenční rovnice prvního řádu s počáteční podmínkou f(0) = yo je dáno vztahem (n-l \ n-2 / n-1 \ ri3' p+e n a,-u,+/)„_!. /=0 / j=Q \i=j+l ) Lineární procesy ooooooooooooooo Lineární diferenční rovnice oo»oooooooo Dokážeme si obecný výsledek pro rovnice prvního řádu, které se podobají lineárním, ale připouští proměnné koeficienty a a b, f(n + l) = an-f(n) + bn. Tvrzení Obecné řešení diferenční rovnice prvního řádu s počáteční podmínkou f(0) = yo je dáno vztahem 'n-\ n-2 / n-1 j=Q \i=j+l J=0 Důsledek Obecné řešení lineární diferenční rovnice prvního řádu s konstantními koeficienty a ^ 1, b a počáteční podmínkou f(0) = y0 je f{n) = anyQ + I^Z>. 1 — a Nyní si ukážeme obecnou teorii pro lineární rovnice s konstantními koeficienty, která poskytuje nejen velmi praktické nástroje, aleje také pěknou ilustrací pro koncepty vektorových podprostorů a lineárních zobrazení. Definice Homogenní lineární diferenční rovnice řádu k je dána výrazem a0xn + 3ix„_i H-----h akxn_k = 0, a0 ^ 0 ak^0, kde koeficienty a, jsou skaláry, které mohou případně i záviset na n. Lineární procesy ooooooooooooooo Lineární diferenční rovnice oooo»oooooo Říkáme také, že taková rovnost zadává homogenní lineární rekurenci řádu k a často zapisujeme hledanou posloupnost jako funkci xn = f(n) = -^f(n - 1) - ... - ^f(n - k). Řešením této rovnice nazýváme posloupnost skalárů x,-, pro všechna / G N, případně / G Z, které vyhovují rovnici s libovolným pevným n. Lineární procesy Lineární diferenční rovnice ooooooooooooooo oooo»oooooo Říkáme také, že taková rovnost zadává homogenní lineární rekurenci řádu k a často zapisujeme hledanou posloupnost jako funkci xn = f(n) = -^f(n - 1) - ... - ^f(n - k). Řešením této rovnice nazýváme posloupnost skalárů x,-, pro všechna / G N, případně / G Z, které vyhovují rovnici s libovolným pevným n. Prostor všech nekonečných posloupností x; je vektorový prostor, kde sčítání i násobení skaláry je dáno po složkách. Přímo z definice je zjevné, že součet dvou řešení homogenní lineární rovnice nebo skalární násobek řešení je opět řešení. Stejně jako u homogenních systémů lineárních tedy vidíme, že množina všech řešení je vektorový pod prostor. Lineární procesy ooooooooooooooo Lineární diferenční rovnice 00000*00000 Počáteční podmínka na hodnoty řešení je dána jako /c-rozměrný vektor v Kk. Součtu počátečních podmínek odpovídá součet příslušných řešení a obdobně se skalárními násobky. Dále si všimněme, že dosazením nul a jedniček do zadávaných počástečních k hodnot snadno získáme k lineárně nezávislých řešení naší rovnice. Jakkoliv jsou tedy zkoumané vektory nekonečné posloupnosti skalárů, samotný prostor všech řešení je konečněrozměrný, předem víme, že jeho dimenze bude rovna řádu rovnice k, a umíme snadno určit bázi všech těchto řešení. Opět hovoříme o fundamentálním systému řešení a všechna ostatní řešení jsou právě jejich lineární kombinace. Lineární procesy Lineární diferenční rovnice ooooooooooooooo oooooo»oooo Řešení homogenních rekurencís konstantními koeficienty V praktických modelech velice často vystupují rovnice, kde jsou koeficienty konstantní. V tomto případě se daří uhodnout vhodnou formu řešení a skutečně se nám podaří najít k lineárně nezávislých možností. Tím budeme mít problém vyřešený, protože všechny ostatní budou jejich lineární kombinací. Lineární procesy Lineární diferenční rovnice ooooooooooooooo oooooo»oooo Řešení homogenních rekurencís konstantními koeficienty V praktických modelech velice často vystupují rovnice, kde jsou koeficienty konstantní. V tomto případě se daří uhodnout vhodnou formu řešení a skutečně se nám podaří najít k lineárně nezávislých možností. Tím budeme mít problém vyřešený, protože všechny ostatní budou jejich lineární kombinací. Pro jednoduchost začneme rovnicemi druhého řádu. Takové potkáváme obzvlášť často v praktických problémech, kde se vyskytují vztahy závisející na dvou předchozích hodnotách. Lineární diferenční rovnicí druhého řádu s konstantními koeficienty (resp. lineární rekurencí druhého řádu s konstantními koeficienty) tedy rozumíme předpis f(n + 2) = a-f(n + l) + b-f(n) + c, kde a, b, c jsou známé skalární koeficienty. -š -00.0 Lineární procesy ooooooooooooooo Lineární diferenční rovnice ooooooo^ooo Např. v populačních modelech můžeme zohlednit, že jedinci v populaci dospívají a pořádně se rozmnožují až o dvě období později (tj. přispívají k hodnotě f(n + 2) násobkem b ■ f (n) s kladným b > 1), zatímco nedospělí jedinci vysílí a zničí část dospělé populace (tj. koeficient a pak bude záporný). Navíc si je třeba někdo pěstuje a průběžně si ujídá konstantní počet c < 0 v každém jednotlivém období. Speciálním takovým příkladem s c = 0 je např. Fibonacciho posloupnost čísel yo,yi,..., kde yn+2 = yn+i + yn- Lineární procesy ooooooooooooooo Lineární diferenční rovnice oooooooo»oo Zkusme nyní stejně jako v případě rovnic 1. řádu dosadit volbu xn = A" pro nějaký (zatím neznámý) skalár A do obecné homogenní rovnice z definice. Dostáváme pro každé n podmínku \n-k(aQ\k + a1\k-1--- + ak) = 0 což znamená, že bud' A = 0 nebo je A kořenem tzv. charakteristického polynomu v závorce. Charakteristický polynom ale už není závislý na n. Lineární procesy Lineární diferenční rovnice ooooooooooooooo oooooooo»oo Zkusme nyní stejně jako v případě rovnic 1. řádu dosadit volbu xn = A" pro nějaký (zatím neznámý) skalár A do obecné homogenní rovnice z definice. Dostáváme pro každé n podmínku \n-k(aQ\k + a1\k-1--- + ak) = 0 což znamená, že bud' A = 0 nebo je A kořenem tzv. charakteristického polynomu v závorce. Charakteristický polynom ale už není závislý na n. Předpokládejme, že má charakteristický polynom k různých kořenů Ai,..., Xk- Každý z kořenů nám dává jedno možné řešení Xn = (A/)". Abychom byli uspokojeni, potřebujeme k lineárně nezávislých řešení, což vede na výpočet Vandermondova determinantu. Nalezli jsme tedy fundamentální systém řešení homogenní diferenční rovnice v případě, že všechny kořeny jejího charakteristického polynomu jsou po dvou různé. Lineární procesy Lineární diferenční rovnice ooooooooooooooo oooooooo»oo Zkusme nyní stejně jako v případě rovnic 1. řádu dosadit volbu xn = A" pro nějaký (zatím neznámý) skalár A do obecné homogenní rovnice z definice. Dostáváme pro každé n podmínku \n-k(aQ\k + a1\k-1--- + ak) = 0 což znamená, že bud' A = 0 nebo je A kořenem tzv. charakteristického polynomu v závorce. Charakteristický polynom ale už není závislý na n. Předpokládejme, že má charakteristický polynom k různých kořenů Ai,..., \k- Každý z kořenů nám dává jedno možné řešení Xn = (A/)". Abychom byli uspokojeni, potřebujeme k lineárně nezávislých řešení, což vede na výpočet Vandermondova determinantu. Nalezli jsme tedy fundamentální systém řešení homogenní diferenční rovnice v případě, že všechny kořeny jejího charakteristického polynomu jsou po dvou různé. V případě násobných kořenů dále vstupují do hry řešení tvaru //A". Lineární procesy ooooooooooooooo Lineární diferenční rovnice oooooooooso Věta Každá homogenní lineární diferenční rovnice řádu k nad libovolným číselným oborem K obsaženým v komplexních číslech K má za množinu všech řešení k-rozměrný vektorový prostor generovaný posloupnostmi xn = neXn, kde X jsou (komplexní) kořeny charakteristického polynomu a mocniny i probíhají všechna přirozená čísla od nuly až do násobnosti příslušného kořenu X. Lineární procesy ooooooooooooooo Lineární diferenční rovnice oooooooooso Věta Každá homogenní lineární diferenční rovnice řádu k nad libovolným číselným oborem K obsaženým v komplexních číslech K má za množinu všech řešení k-rozměrný vektorový prostor generovaný posloupnostmi xn = neXn, kde X jsou (komplexní) kořeny charakteristického polynomu a mocniny i probíhají všechna přirozená čísla od nuly až do násobnosti příslušného kořenu X. Stejně jako u systémů lineárních rovnic můžeme dostat všechna řešení nehomogenních lineárních diferenčních rovnic ao{n)xn + 3i(rt)x„_i H-----h ak(n)xn-k = b(n), kde koeficienty a, a b jsou skaláry, které mohou záviset na n, a ao(n) A ak(n) ^ 0. Postupujeme tak, že najdeme jedno řešení a přičteme celý vektorový prostor dimenze k řešení odpovídajících systémů homogenních. Skutečně takto dostáváme řešení a protože je rozdíl dvou řešení nehomogenní rovnice zjevně řešením homogenní, dostáváme takto řešení všechna. Lineární procesy ooooooooooooooo Lineární diferenční rovnice 0000000000» ' Příklad ^ Řešte rekurenci: 1 yn+2 = yn+i + ^yn s počátečními podmínkami yo = 2,yi = 0. Lineární procesy ooooooooooooooo Lineární diferenční rovnice 0000000000» ' Příklad ^ Řešte rekurenci: 1 yn+2 = yn+i + ^yn s počátečními podmínkami yo = 2,yi = 0. Řešení Obecné řešení je tvaru y„ = CiA" + C^X^, kde Ai, A2 jsou kořeny charakteristického polynomu x2 — x — \. Lineární procesy ooooooooooooooo Lineární diferenční rovnice 0000000000» ' Příklad ^ Řešte rekurenci: 1 yn+2 = yn+i + ^yn s počátečními podmínkami yo = 2,yi = 0. Řešení Obecné řešení je tvaru y„ = CiA" + C^X^, kde Ai, A2 jsou kořeny charakteristického polynomu x2 — x — \. Máme tedy Ai,2 = ^(1 ± VŠ) a z počátečních podmínek yo = C1 + C2 = 2, resp. Yl = §G(1 + VŠ) + |C2(1 - VŠ) Lineární procesy Lineární diferenční rovnice ooooooooooooooo 0000000000» ' Příklad ^ Řešte rekurenci: 1 yn+2 = yn+i + ^yn s počátečními podmínkami yo = 2,yi = 0. Řešení Obecné řešení je tvaru y„ = CiA" + C^X^, kde Ai, A2 jsou kořeny charakteristického polynomu x2 — x — \. Máme tedy Ai,2 = ^(1 ± VŠ) a z počátečních podmínek yo = C1 + C2 = 2, resp. Yl = §G(1 + VŠ) + |C2(1 - VŠ) Dostáváme jediné řešení f(n) = (1 - ^V3)^(l + VŠ)" + (1 + ^V3)^(l - VŠ)".