Semesstrální práce z předmětu
MM Diferrenční rov vnice
Jmééno a příjmen ní:
J Forejt Jan
Osobní číslo:
A A07026
Stud dijní skupinaa:
1. ročník, kom mb. studium
Oboor:
M Matematika
E-m mail:
f
[email protected] r.cz
Datum m odevzdání: 7.2.2008
Obsah: 1. The Tower of Hanoi …………………………………………… 2 2. Lineární diferenční rovnice ………………………..………..… 4 3. Problémy s počáteční podmínkou …………………………..… 4 4.Řešení diferenčních rovnic …………..………………………… 5 5. Řešení prvního řádu lineárních rovnic ………………………... 6 6. Literatura ……………………………………………………… 11
1
T Towerr of Hanoi 1. The ...v jedné tiibetské oblaasti, v kláštteře uprostřřed strmýchh hor, prý eexistuje náb boženská s sekta, kteráá ví, kdy buude konec světa. Mnichové této sekty se zaabývají pro oblémem p přesouvání 64 zlatých disků navleečených na tři t tyče. Cílem je přesuunout všechn ny disky z první tyčee na třetí s tím, že mohhou používat druhou tyyč jako pom mocnou. Vžždy však m mohou přessouvat pouzze jeden diskk a nikdy neesmíme um místit větší diisk na menšší. P Před mnohaa sty lety začali z mnišii s přesouvááním disků.. Až se jim m podaří úko ol splnit, n nastane konnec světa. O Otázkou je,, jestli je tatto legenda pravdivá, p a přenesení jednoho j dissku trvá kněěžím 1 s, j dlouho budou jak b kněžží disky převvádět a kdy nastane konec světa. K řešení toohoto probllému nejprrve určíme počet požaadovaných pohybů k přesunu j jednoho, d dvou či tří disků. Z tohoto řešeení budemee moci oddvodit praviidlo pro p přenesení liibovolného počtu diskůů. (P1=1) 1 disk (n=1) J Jeden disk lzze přenést z jedné jehlyy na druhou u v jednom pohybu. p 2 disky (n=2) (P2=3) D disky lzze přenést z jedné jehlyy na druhou Dva u ve třech poovolených ppohybech. 3 disky (n=3) (P3=7) T disky lzee přenést z jedné Tři j jehly na druhou v sedmi povvolených poohybech.
2
Nyní známe, jak přenést jeden, dva nebo tři disky z jedné jehly na druhou. Není již těžké odvodit strategii pro přenos libovolného počtu disků. Krok
Popis akce
Počet kroků
1
Přenesení všech disků kromě největšího disku z 1. jehly na 2.
Pn-1
2
Přenesení zbývajícího disku z 1. jehly na 3.
1
3
Přenesení disků z 2. jehly na 3.
Pn-1
Počet pohybů celkem
Pn = 2*Pn-1 + 1
Tabulka ukazuje danou strategii a dle ní lze spočítat požadovaný počet přesunů pro libovolný počet disků. Naším úkolem bylo zjistit, jak dlouho potrvá přesun 64 disků. Výpočet provedeme přesně podle dané strategie: - nejdříve vypočteme počet přenosů pro jeden disk - z něj lze vypočítat počet přenosů pro dva disky - atd., až spočteme hledaný počet pro 64 disků P64 = 18 446 744 073 709 551 615 [s] > 500 * 109 [let]
3
2. Lineární diferenční rovnice Hanojské věže a její řešení je příkladem diferenční rovnice. Diferenční (rekursivní) rovnice jsou takové rovnice, kde hledáme vzorec pro n-tý člen posloupnosti čísel splňující jistý daný vztah. Pokud se v dané rovnici vyskytuje pouze lineární kombinace členů hledané posloupnosti, hovoříme o lineární diferenční rovnici. yn = -a1yn-1 - a2yn-2 - … - akyn-k + bn Pokud se zpětně podíváme na diferenční rovnici z Hanojských věží (yn = 2yn-1 + 1), tak v případě nezadání tzv. počáteční podmínky (počet nutných přesunů pro nejmenší počet disků), řešením dané rovnice by byla každá posloupnost tvaru: yn = d*2n – 1, d ≠ 0 Dosazením dostaneme: d*2n – 1 = 2*(d*2n-1 – 1) + 1 = 2*d*2n-1 – 2 + 1 = d*2n – 1 Aby bylo její řešení určeno jednoznačně (existovala pouze jediná posloupnost splňující danou rovnici), je nutno ještě zadat tzv. počáteční podmínky, tj. hodnoty prvních k členů dané posloupnosti. Příklady známých lineárních diferenčních rovnic: Fibonacciho rovnice: Fn = Fn-1 + Fn-2 Tower of Hanoi: Pn = 2*Pn-1 + 1
3. Problémy s počáteční podmínkou Pokud máme dánu diferenční rovnici a její první eventuálně i druhý člen, a úkolem je najít posloupnost čísel dané diferenční rovnice, jedná se o tzv. problém s počáteční hodnotou (initial-value problem). Pro objasnění uvedu několik příkladů: Příklad 1.: Nalezněte prvních šest členů posloupnosti s počáteční podmínkou. y0 = 1 yn = 3yn-1 + 5 Řešení: Známe hodnotu y0 (= 1) a použitím zadané diferenční rovnice spočteme požadovaný počet členů posloupnosti: y0 = 1 y1 = 3y0 + 5 = 3*1 + 5 = 8 y2 = 3y1 + 5 = 3*8 + 5 = 29 4
y3 = 3y2 + 5 = 3*29 + 5 = 92 y4 = 3y3 + 5 = 3*92 + 5 = 281 y5 = 3y4 + 5 = 3*281 + 5 = 848 Příklad 2.: Nalezněte prvních šest členů posloupnosti s počáteční podmínkou. y0 = 1 yn – yn-1 = 2n, n ≥ 1 Řešení: Tato diferenční rovnice není zadána ve tvaru, aby člen s nejvyšším indexem byl na levé straně rovnice sám. Tyto rovnice se řeší pro člen s nejvyšším indexem jako funkce členů s nižšími indexy. Tudíž je nutno danou rovnici upravit: yn = yn-1 + 2n, n ≥ 1 Nyní již můžeme spočítat prvních šest členů dané posloupnosti: y0 = 1 y1 = 1 + 2*1 = 3 y2 = 3 + 2*2 = 7 y3 = 7 + 2*3 = 13 y4 = 13 + 2*4 = 21 y5 = 21 + 2*5 = 31 Příklad 3.: Nalezněte prvních pět členů posloupnosti s počáteční podmínkou. y0 = 5 y1 = 0 yn = (yn-1)2 - yn-2 , n ≥ 1 Řešení: Tato diferenční rovnice potřebuje pro své řešení první dva členy dané posloupnosti (počáteční podmínky). Jejich hodnota je známa a není proto problém najít řešení: y0 = 5 y1 = 0 y2 = 02 – 5 = – 5 y3 = (– 5)2 – 0 = 25 y4 = 252 – (– 5) = 630
4. Řešení diferenčních rovnic Předcházející příklady ukazují fakt, že stačí ovládat základní kroky aritmetiky abychom dokázali najít prvních několik členů řešení úlohy s počáteční podmínkou. Nicméně jak už bylo prezentováno na problému Hanojských věží, bylo by určitě časově a výpočetně ideálnější najít algebraický výraz pro n-tý člen yn posloupnosti. Nazvali bychom ho řešením problému s počáteční podmínkou. Výhoda tohoto výrazu leží ve skutečnosti, že můžeme nalézt hodnotu nějakého členu posloupnosti jednoduše bez nutnosti vyčíslit předchozí členy posloupnosti. 5
Jako příklad si můžeme vzít Hanojské věže: yn = 2yn-1 + 1 y0 = 1 je řešením problému s počáteční hodnotou yn = 2n – 1 2n – 1 = 2*(2n-1 – 1) + 1 = 2*2n-1 – 2 + 1 = 2n – 1 Mějme dánu diferenční rovnici: yn = ayn-1 + b ,kde a, b jsou reálná čísla. Takovouto rovnici nazveme diferenční rovnicí prvního řádu (first-order linear). Je možné najít n-tý člen yn z posloupnosti, který uspokojí tuto rovnici pro první člen y0, touto metodou: postupným rozepisováním dané diferenční rovnice nejdříve pro n=1 a dále pro n=2,3,…, a nahrazením členů s vyššími indexy členy s indexy nižšími, dostaneme vztah pro výpočet člena yn pomocí člena y0 (počáteční podmínka). Dostaneme: y1 = ay0 + b y2 = ay1 + b = a(ay0 + b) + b = a2y0 + ab + b y3 = ay2 + b = a(a2y0 + ab + b) + b = a3y0 + a2b + ab + b . . yn = ayn-1 + b = any0 + an-1b + an-2b + … + a2b + ab + b Použitím formule na součet konečné geometrické řady: b + ab + a2b + … + an-1 = b[(1-an)/(1-a)], a ≠ 1 Takže řešením je: yn = any0 + b[(1-an)/(1-a)] = any0 + b/(1-a) – ban/(1-a) = b/(1-a) + [y0 - b/(1-a)]an
5. Řešení prvního řádu lineárních rovnic Z uvedeného vzorce vyplývá, že problém s počáteční podmínkou: yn = ayn-1 + b, dáno y0 , n ≥ 1 má řešení: yn = r + (y0 – r)an , n ≥ 0 , kde r = b/(1-a), a ≠ 1 6
Pokud je a = 1, diferenční rovnice má řešení yn = y0 + nb Příklad 4.: Nalezněte řešení problému s počáteční podmínkou. y0 = 0 yn = 0,8yn-1 + 1 , n ≥ 1 Řešení: y0 = 0 yn = ayn-1 + b , n ≥ 1 , kde a = 0,8 b=1 r = b/(1-a) = 1/(1-0,8) = 5 , pak yn = r + (y0 - r)an = 5 + (0 – 5)0,8n = 5 – 5*0,8n , n ≥ 0 Příklad 5.: Pastevec má populaci 30 horských koz. Jeho stádo se zvětšuje ročně o 12%. Na takto zadané úloze můžeme zkoumat 2 problémy: Jak velká bude populace koz za n let? Za kolik let dosáhne jeho stádo počtu 150 ks? Jak velká bude populace koz za n let? Řešení: yn - yn-1 = 0,12yn-1 y0 = 30, yn = 1,12yn-1 , n ≥ 1 , problém s počáteční podmínkou yn = ayn-1 + b , kde a = 1,12 b=0 r = b/(1-a) = 0 Dostaneme řešení yn = r + (y0 – r)an = 0 + (30 – 0)1,12n = 30*1,12n , n≥0
7
Prvních pár členů je uvedeno v tabulce:
Za kolik let dosáhne jeho stádo počtu 150 ks? Řešení: stanovíme 30*1,12n = 150 , kde potřebujeme určit n 1,12n = 5 , zlogaritmováním dostaneme: n log 1,12 = log 5 log 1,12 ≈ 0,049218 log 5 ≈ 0,69897 , dosazením 0,049218n ≈ 0,69897 n ≈ 14,2 Stádo dosáhne stavu 150ti kusů za přibližně 14 let.
8
180 160 140 120 100 80 60 40 20 0 0
2
4
6
8
10
12
14
16
Tabulka růstu počtu horských koz v závislosti na čase
Příklad 6.: Třeboňští rybáři mají ve svém rybníce 100.000 ks třeboňských kaprů. Kapři se ročně rozrostou o 25% a je povolen výlov 30.000 ks kaprů určených na vánoční stůl. Za kolik let bude celé hejno ryb vyloveno? Řešení: yn - yn-1 = 0,25yn-1 – 30000, n ≥ 1, y0 = 100000 yn = 1,25yn-1 – 30000 , což je lineární rovnice prvního řádu (yn = ayn-1 + b), kde a = 1,25 b = -30000 r = b/(1-a) = (-30000)/(1 - 1,25) = 120000 Za kolik let bude celé hejno ryb vyloveno? (yn = 0) Dostaneme řešení yn = r + (y0 – r)an , n≥0 0 = 120000 + (100000 – 120000)1,25n 0 = 120000 – 20000*1,25n 20000*1,25n = 120000 0,2*1,25n = 1,2 1,25n = 6 , zlogaritmováním dostaneme n log 1,25 = log 6 log 1,25 ≈ 0,09691 log 6 ≈ 0,778151 9
, dosazením m 0,099691n ≈ 0,7778151 n ≈ 8,029 Rybník budde bez kaprrů za 9 let.
10
6. Literatura Kopeček, I.; Kučera, J.: Programátorské poklesky, Mladá fronta, 1989 Chval, Z.: The Tower of Hanoi: Diferenční rovnice, ZČU, 2005 Bartsch, H.-J.: Matematické vzorce, Mladá fronta, 1996 www.wikipedia.org
11
