Lineární modely -1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice prvního řádu
Ondřej Klíma 21. 2. 2013
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Osnova přednášky
• Skaláry a číselné obory (komplexní čísla)
• Kombinatorika
a Diferenční rovnice prvního řádu
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Čísla
Objevovala se čísla vyjadřující počet, vzdálenost, délku, váhu, ...a také potřeba s nimi pracovat: sčítat, násobit,...
• N = {0,1,2,3,... }, operace: +, •
• Z = {..., -2, -1,0,1,2,...}, operace: +, •, -
• Q = {£ | p e Z, qe N- {0}}, operace: +, •, -,: (částečně)
• R - reálná čísla (obsah kruhu, úhlopříčka čtverce),
-„operace" navíc: příští semestr; částečné odmocňování
• C - operace navíc: odmocňování
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Vlastnosti sčítání
Množina vybavená operací + má často tyto vlastnosti:
• pro všechna a, b, c platí (a + b) + c = a + (b + c)
• pro všechna a, £> platí a + b = b + a
• existuje prvek 0 tak, že pro všechna a je a + 0 = a
• pro všechna a existuje (-a) tak, že a + (-a) = 0
Hovoříme o komutativních grupách.
Kontrolní otázka: Co množiny z předchozí strany?
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Vlastnosti násobení
Zjednodušeně (tj. nesprávně) zapsáno
(a • b) ■ c = a - (b - c)
a - b = ba,
1 • a = a
a-a~1 = 1 (pro a 7^0)
a • (b + c) = a - b + a - c,
Hovoříme o poli (často také o komutativním tělese).
Prvky nějaké množiny s operacemi + a • splňujícími (ne nutně všechny) předchozí vlastnosti budeme nazývat skaláry.
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Skalární funkce
Nezkoumáme pouze skaláry, ale také závislosti mezi nimi:
y = m,
kde „závislá" veličina y je dána pomocí „nezávislé" veličiny x.
• daň ze mzdy ... f(x) = 0.15 • x
• plocha kruhu ... f(x) = ir ■ x2
• faktoriál ... f(0) = 1, f(n + 1) = {n + 1) • f(n)
• méně explicitní... f(x) je nejmenší prvočíslo větší než 10X
Ideální stav: f je dáno vzorcem pomocí známých operací.
Často má f neformální popis a přechod k explicitnímu popisu je právě úkolem.
Je-li hodnotou skalár, hovoříme o skalární funkci.
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Skalární funkce - poznámky
Hodnoty skalární funkce mohou být také dány pouze přibližně nebo s jistou pravděpodobností.
• měření ve fyzice (váha objektu x)
• součet na x kostkách
Formálně je funkce tzv. zobrazení z množiny X do množiny pro libovolný prvek x e X je jednoznačně dán prvek f(x) e
Další příklady zobrazení, které nejsou skalární funkce:
• Y = {true, falše} ... výroková logika
• X je množina studentů zapsaných v předmětu MB101, f je přiřazení hodnocení, tj. Y = {A, B, C, D, E, F, -}
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Komplexní čísla a jejich vlastnosti
Komplexní rovina.
C = {a + ib, a, b e R} Absolutní hodnota = vzdálenost od počátku
|z|2 = zž = (a+ib)(a - i b) Goniometrický tvar
z = |z| (cos0 + / sin <j))
Moivreova věta
zn = \z\n (cos(/70) + / sin(/70))
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Základní kombinatorické postupy
Základní kombinatorické principy
• princip součtu (rozdílu)
• princip součinu (podílu)
• princip bijekce (kódování)
• princip inkluze a exkluze
• rekurentní metody
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Příklad - reprezentace třídy
Příklad
Ze třídy 30 žáků máme vybrat 2 reprezentanty na školní soutěž, přičemž nám nezáleží na jejich pořadí.
Zadání jinak: ze 30 čísel 1,..., 30 máme vybrat 2 čísla. Řešení: rozdělme podle menšího čísla (princip součtu).
Kolik je možností, kdy menší reprezentant je 1 ? 29 Kolik je možností, kdy menší reprezentant je 2? 28
Kolik je možností, kdy menší reprezentant je 29? 1 Celkem: 29 + 28 + 27 +••• +1 = 3^5 = 15-29.
Jiné řešení: Dejme tomu, že nám na jejich pořadí bude záležet. Pak jich je 30 • 29 (princip součinu). Teď jsme každou možnost započítali dvakrát, tzn. 2 • x = 30 • 29. Odtud odpověď ^3. Pozor výsledek musí být přirozené číslo.
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Příklad - fotbalová liga
Příklad (Liga - celkové pořadí)
Kolik je možných pořadí fotbalové ligy (16 družstev). Řešení - princip součinu 16-15-14.....2-1 =16!
Příklad (Liga - pohárové pozice)
Kolik je možných pořadí na prvních čtyřech místech. Řešení - princip součinu 16 • 15 • 14 • 13 =
Příklad (Liga - pohárové pozice - varianta)
Stejná úloha, jen nám nezáleží na pořadí na prvních 4 místech, ale pouze na tom, která mužstva tam jsou.
Řešení - předchozí     Protože nám nezáleží na pořadí, každá možnost je počítána vícekrát. Kolikrát? 4!. Tedy ^r?r■
Kontrolní otázka: Kolika způsoby může liga dopadnout, pokud nás zajímá pořadí na prvních 4 místech a dále, která čtyři mužstva sestupují.
1. přednáška       Skaláry, Kombinatorika a Diferenční rovnice
Kombinační (binomická) čísla
Příklad (Sportka)
Kolika způsoby lze z množiny {1,..., 49} vybrat 6 čísel, přičemž nám nezáleží na jejich pořadí.
i
49! 43I-6!
Příklad (Počet podmnožin)
Je dána množina M o n prvcích a číslo k. Kolik existuje /c-prvkových podmnožin množiny M?
n\
(n-k)\k\
Pro toto číslo se vyplatí symbol: (nk) = ^n_nky.k, ■
Tzv. kombinační číslo, nebo také binomický koeficient.
Pozn.: Předpokládáme 0 < k < n. Jinak má smysl položit rovno 0.
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Binomická věta
Věta	
Pro libovolná a, b e ... platí	
{a + bf =	
	k=0 w
{a + b)n = {a + b)-{a + b)-{a + b)---{a + b)
Koeficient u mocniny 3řbn~k je roven právě počtu možností, jak vybrat /c-tici závorek, kde bereme a.
Proto se hovoří o binomických číslech/ koeficientech. Kombinační číslo se použivá, protože se hovoří o kombinacích. Permutace, variace, kombinace - pojďme udělat pořádek.
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Permutace
Definice
Permutace/pořadí je uspořádaná n-Wce (všech) prvků dané /i-prvkové množiny.
Věta
Počet všech permutací konečné množiny s n prvky je dán funkcí faktoriál:
f{n) = n\ Příklad: Liga - celkové pořadí
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Variace
Definice
Variace je uspořádaná /c-tice prvků z dané /i-prvkové množiny. Hovoříme o variaci k-tého stupně třídy n.
Počet variací k-tého stupně třídy n je n(n - 1) • • • (n - k + 1) kde 0 < k < n (a nula jinak).
n\
(n-k)\
Příklad: Liga - pohárové pozice; Reprezentace třídy
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Kombinace
Definice
Kombinace je neuspořádaná /c-tice prvků z dané /i-prvkové množiny.
Jinými slovy: kombinace je /c-prvková podmnožina. Hovoříme o kombinaci k-tého stupně třídy n.
Věta
Počet kombinací k-tého stupně třídy n je (£) pro všechna 0 < k < n (a nula jinak).
Příklad: Liga - pohárové pozice - varianta; Sportka
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Permutace, variace a kombinace s opakovaním
V předchozích příkladech byla daná množina prvků z které jsme vybírali. Tj. každý prvek má jeden exemplář.
V následujícím se podíváme na úlohy kde prvky mohou být vybrány opakovaně (máme dostatek exemplářů každého prvku). Např:
Příklad (Přesmyčky)
Kolik je možné sestavit slov z písmen slova ANANAS?
Příklad (Počet /c-ciferných čísel)
Kolik je 5-ciferných čísel, které neobsahují cifru 0?
Příklad (Nákup ovoce)
V obchodě chceme nakoupit 10 kusů ovoce ze sortimentu ananas, banán, jablko a pomeranč. Kolik možností takového nákupu máme?
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Permutace s opakováním
Věta
Nechť je mezi n danými prvky p-| prvků prvního druhu, p2 prvků druhého druhu,Pk prvkůk-tého druhu,
Pí + P2 H-----\-Pk = n. Potom počet všech pořadí těchto prvků
je
n\
_Pí! _
Hovoříme o permutacích s opakovaním. Příklad: Přesmyčky
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Variace s opakováním
Variace s opakováním je uspořádaná /c-tice prvků z dané /i-prvkové množiny, přičemž každý prvek množiny se může v této /c-tici vyskytovat v libovolném počtu kopií.
Věta
Počet variací s opakováním k-tého stupně třídy n je nk.
Pozn.: Všimněme si, že nyní není potřeba k < n
Příklad: Počet /c-ciferných čísel
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Kombinace s opakováním
Definice
Kombinace s opakováním je neuspořádaná /c-tice prvků z dané /i-prvkové množiny, přičemž každý prvek množiny se může v této /c-tici vyskytovat v libovolném počtu kopií.
Počet kombinací s opakováním k-tého stupně třídy n je
_m-
Pozn.: Důkaz není přímočarý, opírá se o princip bijekce/kódování.
Příklad: Nákup ovoce
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Základní kombinatorické principy
Základní kombinatorické principy
• princip součtu (rozdílu)
• princip součinu (podílu)
• princip bijekce (kódování)
• princip inkluze a exkluze [ Příště ]
• rekurentní metody
Kontrolní mechanismy a otázky
• počítám každý případ právě jednou?
• dávám celočíselnou odpověď?
• dává odpověď smysl pro malé hodnoty?
• umím výsledek spočítat více způsoby?
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Rekurentní metody
5
Příklad (Schody)
Kolika způsoby lze vyjít 10 schodů, pokud mohu dělat kroky po 1, 2 nebo 3 schodech.
Řešme obecně pro n schodů. Označme počet p(n). Platí: p(1) = 1, p(2) = 2, p(3) =4 (1 + 1 + 1; 1 + 2; 2 + 1; 3)
Pozn.: Má smysl uvažovat i p(0) = 1.
Rozdělíme podle prvního kroku: a 1 schod ... zbývá n - 1 schodů, tj. p(n - 1) způsobů
• 2 schody ... zbývá n-2 schodů, tj. p(n - 2) způsobů
• 3 schody ... zbývá n - 3 schodů, tj. p(n - 3) způsobů Celkem
p(n) = p(n - 1) + p(n - 2) + p(n - 3). Tj. p(4) = p(3) + p(2) + p(1) = 7, p(5) = 13, ..., p(10) = 274.
Jedná se o příklad diferenční rovnice.
Skaláry, Kombinatorika a Diferenční rovnice
Diferenční rovnice
Definice
Diferenční rovnice řádu k je formule
f [n + k) = F(n, f (n), f (n + 1),..., f (n + k - 1)),
kde F je funkce v k + 1 promněnných.
Poslopunost f(0),...,f(k- 1) nazýváme počáteční podmínky.
Funkce F a počáteční podmínky jednoznačně určují posloupnost
(f(n))nefi = (f(n))Zo-
Příklad (Diferenční rovnice prvního řádu)
ř(n+1) = f(n)-(n+1),   f(0) = 1 . Zde F(x, y) = y ■ x + y. Rovnice zadává funkci /"(/i) = n\
Skaláry, Kombinatorika a Diferenční rovnice
Lineární diferenční rovnice
Definice
Diferenční rovnice se nazývá lineární, jestliže existují skaláry(konstanty) a0, a-i,..., ak, b takové, že F(x0, Xt ,..., xk) = a0x0 + a-|X-| + • • • + akxk + b.
Příklad (Lineární diferenční rovnice třetího řádu)
Fromule z příkladu Schody
p(n+3) = p(n)+p(n+1)+p(n+2),   p(0) =p(1) = 1,p(2) = 2
je lineární diferenční rovnice třetího řádu.
Zde dokonce a0 = b = 0.    (a! = a2 = a3 = 1)
Dost často, představuje promněnná /i časový údaj/parametr. Potom a0 = 0, znamená, že f(n) "je nezávislé na čase", tj. závisí pouze na předchozích hodnotách f(n - 1), f(n - 2), atd.
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Lineární diferenční rovnice prvního řádu
Lineární diferenční rovnice prvního řádu (nezávislá na čase):
f(n + 1) = a • f(n) + b, a,beZ. Pro b = 0 dostáváme snadno f(n) = an ■ f(0).
Příklad (Malthusiánský model populačního růstu)
Populace roste s konstatní úměrou vzhledem k předchozímu stavu. (Např. "populace králíků se za půl roku zdvojnásobí.")
Pro b ^ 0 reálnější (např. úmrtnost v populaci). Vrátíme se k tomuto modelu později.
Příklad (Úročení — půjčky, spoření)
Výše nesplaceného dluhu je v každém měsíci úročena, tj. násobíme konstantou a (např. a = 1,01 při měsíčním úroku 1%, tj. 12% p.a.) a snížena o výši splátky b.
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Úročení - příklad
Příklad
Půjčíme částku C, při měsíčním úroku u a měsíční splátce S. Jaká je výše dluhu po n měsících?
Předpokládáme, že banka účtuje na konci měsíce, přičemž my v poslední den měsíce současně uhradíme měsíční splátku. Tj. banka připíše úrok z nesplaceného dluhu a sníží vzniklou částku o naši měsíční splátku. Výši dluhu na konci /i-tého měsíce označme dn. Předně d0 = C. Dále
d^ =(1 +u)-d0-S.
Obecně
c/fl+i = (1 + u) ■ dn - S,   a = 1 +u, b = -S.
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Úročení - příklad - pokračování
		dn+^ = (1 +u)-d„-S, d0	= C
d^	= d0	• (1 + u) - S	
d2	= d,	• (1 + u) - S = do ■ (1 + u)2 -	- S • (1 + u) - S
d3	= d0	•(1 +ív)3-S-(1 +ív)2-S-	(1 + u) — S
dn	= d0	•(1 +ív)n-S-[(1 +uf-" ■■■	• + (1 +
Pozn.: Vime a"~1 + a"~2 H-----h a + 1 = ^-1.
rf„ = c.(i+U)"-s.'1+»»"-1
1. přednáška       Skaláry, Kombinatorika a Diferenční rovnice
Úročení - výše splátky
Příklad
Půjčíme si částku C, při měsíčním úroku u. Jaká má být měsíční splátka pokud chceme dluh splatit po n měsících?
dn = C-(1 +u)n-S-Chceme dn = 0. Pak
(1 + u)n - 1
S=C-
(1 +u)n-u
(i +u)n- r
Příklad
Půjčíme si částku C = 160.000, při ročním úroku 13,9%
Pozn.: Měsíční úrok 13.9/12, tzn. u = 0,011583. Přesnější výpočet ^1.139 - 1.
na dobu n = 72 měsíců? S = 3.288
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Úročení - výše splátky - realita
Příklad
Půjčíme si částku C = 160.000, při ročním úroku 13.9%
na dobu n = 72 měsíců?_S = 3.288
Předchozí příklad vznikl na motivy reálné nabídky jedné banky: Půjčka 160 tis., úrok 13,9% p.a., 72 měsíců, splátka 3.549. Proč?
• Poplatek 1.000 za uzavření, vlastně C = 161.000.
• Poplatek 150 měsíčně za vedení dluhu, (spousta práce)
• Stejně nevychází, asi jiný model úročení (po dnech, spojité) nebo odložená první splátka, nebo další skryté poplatky? Čert ví.
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Úročení - výše úroku
Příklad
Půjčíme si částku C = 160.000 na n = 72 měsíců při měsíční splátce S = 3.549. Jaký je skutečný úrok?
S=C
(1 +u)n u
(1 +u)n- 1
Chceme vypočítat u. Nevyjádříme explicitně, ale numericky lze
určit.
je rostoucí funkce v promněnné u.
Pozn.: f(u) =
u = 0,01407, tj. roční cca 16,9%.
Proto se uvádí RPSN, což je zhruba hodnota o niž jsme se pokoušeli (přesnější).
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Lineární diferenční rovnice prvního řádu
Příklady:
• Zjistit výši splátek půjčky.
• Zjistit délku splácení při dané měsíční splátce.
• Zjistit výši "reálného" úroku.
• Spoření.
• Složitější zadání: stavební spoření (příspěvek státu, daň, poplatky).
Při přesných analýzách je třeba brát do úvahy inflaci, daně, změny úrokových sazeb, atd.
Další příklady na lineární diferenční rovnice - viz skripta, (kombinatorika - rekurentní metody)
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Skorolineární diferenční rovnice prvního řádu
Předchozí odvození pro lineární rovnice prvního řádu lze zobecnit na rovnice, kde F(x,y) je lineární vzhledem k y, tj. tvaru F(x, y) = a(x) ■ y + b(x). Tzn. na rovnice s tzv. promněnnými koeficienty:
f(n + 1) = an ■ f{n) + b„.
Pro tuto rovnici platí
/n-1    \ n-1 / n-1 \
Pozn.: Uvádíme spíše pro zajímavost.
Jednoduchý příklad: faktoriál. Zde bn = 0 pro všechna n.
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice
Shrnutí, požadavky
• Komplexní čísla: násobení, dělení, umocňování. (K čemuž je potřeba absolutní hodnota, algebraický a goniometrický tvar.)
• Kombinatorika: elementární příklady na princip součtu a součinu; permutace, variace a kombinace s opakováním i bez; rekurentní metody.
• Lineární diferenční rce: jednoduché příklady na úročení.
1. přednáška
Skaláry, Kombinatorika a Diferenční rovnice