Obecné informace
Matematika I – 1b
Skaláry, kombinatorické veličiny a diferenční rovnice
Jan Slovák
Masarykova univerzita
Fakulta informatiky
19. 9. 2012
Obecné informace
Obsah přednášky
1 Obecné informace
Obecné informace
Kde je dobré číst?
vlastní poznámky, předběžné texty nové učebnice „Matematika
drsně a svižně“, GOOGLE, atd.
Pavel Horák, Úvod do lineární algebry, MU Brno, skripta.
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/).
Riley, K.F., Hobson, M.P., Bence, S.J. Mathematical Methods
for Physics and Engineering, second edition, Cambridge
University Press, Cambridge 2004, ISBN 0 521 89067 5, xxiii
+ 1232 pp.
František Šik, Lineární algebra zaměřená na numerickou
analýzu, MU, 1998, 176 s. ISBN 80-210-1996-2.
Obecné informace
Vlastnosti sčítání
Vyjmenujme takto obvyklé vlastnosti, které sčítání a násobení čísel
má:
(a + b) + c = a + (b + c), pro všechny a, b, c (KG1)
a + b = b + a, pro všechny a, b (KG2)
existuje prvek 0 tak, že pro všechny a je a + 0 = a (KG3)
pro všechny a existuje (−a) tak, že a + (−a) = 0. (KG4)
Vlastnostem (KG1) – (KG4) říkáme vlastnosti komutativní grupy.
Celá čísla Z jsou dobrým příkladem komutativní grupy, přirozená
čísla nikoliv, protože nesplňují KG4 (a případně neobsahují nulu
pokud ji do N nezahrnujeme).
Obecné informace
Vlastnosti násobení
(a · b) · c = a · (b · c), pro všechny a, b, c (O1)
a · b = b · a, pro všechny a, b (O2)
existuje prvek 1 takový, že pro vechny a platí 1 · a = a (O3)
a · (b + c) = a · b + a · c, pro všechny a, b, c. (O4)
Poslední vlastnosti O4 se říká distributivita.
Množiny s operacemi +, · a vlastnostmi (KG1)–(KG4), (O1)–(O4)
se nazývají komutativní okruhy. Potřebujeme však zpravidla ještě
další běžnou vlastnost čísel:
pro každé a = 0 existuje a−1
tak, že platí, a · a−1
= 1. (P)
Kdy naše objekty splňují navíc i (P), hovoříme o poli (často také o
komutativním tělese).
Obecné informace
Někdy se ale setkáme se slabší dodatečnou vlastností ne je (P).
Např. okruh celých čísel Z nesplňuje (P), ale splňuje
a · b = 0 ⇒ buď a = 0 nebo b = 0. (OI)
Hovoříme o oboru integrity.
Prvky nějaké mnoiny s operacemi + a · splňujícími (ne nutně
vechny) výe uvedené vlastnosti (tj. komutativní okruh, obor
integrity, pole) budeme nazývat skaláry.
Příklady – okruhy zbytkových tříd!
Budeme pro ně vesměs užívat latinská písmena ze začátku abecedy.
Obecné informace
Permutace
Z množiny n předmětů vytváříme pořadí jejich prvků.
Pro volbu prvního prvku je n moností, dalí je volen z n − 1 moností
atd., a nám nakonec zbude jediný poslední prvek.
Proto je na dané konečné mnoině S s n prvky právě n! různých
pořadí. Hovoříme o permutacích prvků mnoiny S.
Jestliže si předem prvky v S očíslujeme, tj. ztotoníme si S s
mnoinou S = {1, . . . , n} n přirozených čísel, pak permutace
odpovídají moným pořadím čísel od jedné do n.
Dokázali jsme tak:
Počet různých pořadí na konečné množině s n prvky je dán funkcí
faktoriál:
f (n) = n!
Obecné informace
Kombinace
Pro počet kombinací k-tého stupně z n prvků platí (samozřejmě
je k ≤ n)
c(n, k) =
n
k
=
n(n − 1) . . . (n − k + 1)
k(k − 1) . . . 1
=
n!
(n − k)!k!
.
Číslům c(n, k) říkáme binomická čísla.
Pokud nám ale záleží i na pořadí vybrané k-tice prvků, hovoříme o
variaci k-tého stupně.
Pro počet variací platí
v(n, k) = n(n − 1) · · · (n − k + 1)
pro vechny 0 ≤ k ≤ n (a nula jinak).
Obecné informace
Jako ukázku, jak vypadá matematický důkaz si odvoďme několik
jednoduchých tvrzení o kombinačních číslech. Definujme n
k = 0,
kdykoliv je buď k < 0 nebo k > n.
Pro vechna přirozená čísla k a n platí
1
n
k = n
n−k
2
n+1
k+1 = n
k + n
k+1
3
n
k=0
n
k = 2n
4
n
k=0 k n
k = n2n−1.
Obecné informace
Pořadí n prvků, z nichž mezi některými nerozlišujeme, nazýváme
permutace s opakovaním. Nechť je mezi n danými prvky p1
prvků prvního druhu, p2 prvků druhého druhu, . . . , pk prvků k-tého
druhu, p1 + p2 + · · · + pk = n, potom počet pořadí těchto prvků s
opakováním budeme značit P(p1, . . . , pk). Zřejmě platí:
P(p1, . . . , pk) =
n!
p1! · · · pk!
.
Obecné informace
Volný výběr prvků z n moností, včetně pořadí, nazýváme variace
k-tého stupně s opakováním, jejich počet budeme značit
V (n, k). Předpokládáme„ že stále máme pro výběr stejně možností,
např. díky tomu, že vybrané prvky před dalším výběrem vracíme
nebo třeba házíme pořád stejnou kostkou. Zřejmě platí:
V (n, k) = nk
.
Obecné informace
Pokud nás výběr zajímá bez zohlednění pořadí, hovoříme o
kombinacích s opakováním a pro jejich počet píšeme C(n, k).
Theorem
Počet kombinací s opakováním k-té třídy z n prvků je pro vechny
0 ≤ k a 0 < n
C(n, k) =
n + k − 1
k
.
Obecné informace
V předchozích odstavcích jsme viděli formule, které zadávaly
hodnotu skalární funkce definované na přirozených číslech
(faktoriál) nebo dvojicích čísel (binomická čísla) pomocí
předcházejících hodnot. Tomu lze rozumět také tak, e místo
hodnoty naí funkce zadáváme její změnu při odpovídající změně
nezávislé proměnné. Např.
n + 1
k + 1
−
n
k + 1
=
n
k
říká, e rozdíl počtu moností, jak vybrat k + 1 prvků z n + 1
moností, je vyjádřitelný pomocí (moná ji známé) hodnoty.
Takto se skutečně velice často postupuje při matematické formulaci
modelů, které popisují reálné systémy v ekonomice, biologii apod.
My si tu povšimneme jen nejednodušších případů a budeme se k
této tématice postupně vracet.
Obecné informace
Obecnou diferenční rovnicí prvního řádu rozumíme výraz
f (n + 1) = F(n, f (n)),
kde F je známá skalární funkce závislá na dvojicích přirozených
čísel.
Je zřejmé, e takový vztah, spolu s volbou pro f (0), zadává
jednoznačně celou nekonečnou posloupnost hodnot
f (0), f (1), . . . , f (n), . . . . Jako příklad můe slouit definiční formule
pro faktoriál, tj.
n! = n · (n − 1)!
Vidíme, že skutečně vztah pro f (n + 1) závisí na n i na hodnotě
f (n).
Obecné informace
lineární diferenční rovnice
Po konstantní závislosti je nejjednoduí
f (n + 1) = a · f (n) + b,
kde a, b ∈ N. Takovou rovnici umíme snadno řešit. Je-li b = 0, pak
zjevně
f (n) = an
f (0).
Obecné informace
Obecně pro rovnice prvního řádu s proměnnými koeficienty platí
Theorem
Obecné řešení diferenční rovnice prvního řádu
f (n + 1) = an · f (n) + bn
s počáteční podmínkou f (0) = y0 je dáno vztahem
f (n) =
n−1
i=0
ai y0 +
n−1
r=0
n−1
i=r+1
ai br .
Vlastnosti prostoru řešení?
Obecné informace
Corollary
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) = an
y0 +
1 − an
1 − a
b.
Důkaz.
Dosazením konstantních hodnot za ai a bi do obecné formule
dostáváme první sčítanec okamitě.
Pro vyčíslení součtu součinů v druhém si je třeba vimnout, e se
jedná o výrazy (1 + a + · · · + an−1)b. Sečtením této geometrické
řady (připomeňme, e 1 − an = (1 − a)(1 + a + · · · + an−1))
dostaneme právě poadovaný výsledek.
Obecné informace
Obecně nazýváme diferenční rovnicí řádu k vztah
f (n + k) = F(n, f (n), . . . , f (n + k − 1)) = 0,
kde F je známá skalární funkce v k + 1 proměnných skalárních
veličinách. Celá poslounost hodnot je jednoznačně určena volbou
k-tice čísel f (0), . . . , f (k − 1).
Lineární diferenční rovnicí druhého řádu rozumíme
f (n + 2) = a · f (n + 1) + b · f (n) + c,
kde a, b, c jsou známé skalární koeficienty. Dobře známým
příkladem s c = 0 je např. Fibonacciho posloupnost čísel.
Obecné informace
Zkusme dosadit do rovnice podobné řeení jako u lineárních, tj.
f (n) = λn pro nějaké skalární λ. Dosazením dostáváme
λn+2
− aλn+1
− bλn
= λn
(λ2
− aλ − b) = 0
a odtud vidíme, e buď je λ = 0 nebo
λ1 =
1
2
(a + a2 + 4b), λ2 =
1
2
(a − a2 + 4b).
Protože součet dvou řešení rovnice
f (n + 2) − a · f (n + 1) − b · f (n) = 0 je opět řešením téže rovnice a
totéž platí pro konstatní násobky řešení, odvodili jsme obecné
řešení f (n) = C1λn
1 + C2λn
2 a pro jednoznačné vyřeení konkrétní
úlohy se zadanými počátečními hodnotami f (0) a f (1) nám zbývá
jen najít příslušné konstanty C1 a C2.