ÚvodTento dokument obsahuje poznámky k předmětu Vybrané matematické metody (BI-VMM),který je přednášen na FIT ČVUT v letním semestru akademického roku 2020/2021. Před-mět tématicky navazuje a čerpá zejména z předmětů Základy matematické analýzy (BI-ZMA) a Lineární algebra (BI-LIN), přednášených pro studenty prvního ročníku.
Zabýváme se zde zejména Fourierovými řadami, diskrétní Fourierovou transformací,teorií funkcí více proměnných, obecnou optimalizační úlohou a obyčejnými diferenciálnímirovnicemi. Dle zájmu studentů občas zařazujeme i přednášku o Lineárním programování(speciální případ optimalizační úlohy) na úkor některého z dříve uvedených témat. S funk-cemi více proměnných se studenti setkají i v povinném magisterském předmětu Matema-tika pro informatiku (MI-MPI). Tvůrci tohoto textu jsou ale toho názoru, že i bakalářštístudenti (zejména oborů Znalostního inženýrství) by s touto látkou měli přijít do stykupodstatně dříve, než až během magisterského studia.
Cílů tohoto předmětu je několik. V některých partiích přednášky se snažíme studentůmrozšířit rozhled v matematických tématech. V jiných, zejména aplikačních partiích, se sna-žíme nejen „klouzat po povrchu“ a naopak jít v rámci možností do hloubky. Tomu odpovídái rozsah tohoto textu, který v každé kapitole obsahuje podrobný výklad, poté poznámky spřípadnými ukazateli na další literaturu pro zájemce o další studium a v neposlední řaděpříklady k procvičování dané látky.
Tento text je psán méně formálním způsobem, než na jaký jste zvyklí z povinnýchpředmětů. Nové pojmy a koncepty jsou zaváděny (definovány) průběžně v textu. Čtenářna ně je upozorněn tučným fontem.
1 Prolog: Komplexní číslaIt is not knowledge, but the act of learning, not possession but the act of gettingthere, which grants the greatest enjoyment1. Carl Friedrich Gauss
V předmětu BI-ZMA jsme pracovali s reálnými číselnými posloupnostmi,
(an)∞n=0, an ∈ R pro každé n ∈ N,
reálnými číselnými řadami,∞∑k=0
ak, ak ∈ R pro každé k ∈ N,
a reálnými funkcemi jedné reálné proměnné f : A ⊂ R → R u kterých jsme studovalivlastnosti jako konvergence, spojitost a diferencovatelnost.
Všechny důležité pojmy jako např. omezenost posloupností a funkcí, konvergence řada posloupností, limita funkce, spojitost funkce, derivace funkce stojí na pojmu absolutníhodnoty reálného čísla, resp. okolí. V této první rozcvičkové kapitole si ukážeme, jak pojemokolí rozšířit i na komplexní čísla a tím pádem i jak zavést tyto pojmy i pro komplexníposloupnostmi a funkce komplexní proměnné.
1.1 Vlastnosti množiny komplexních číselZačněme připomenutím vlastností tělesa komplexních čísel, které v tomto předmětu budehrát významnou roli. Je-li z ∈ C komplexní číslo tvaru2
z = a+ bi, a, b ∈ R,
kde i je imaginární jednotka splňující i2 = −1, pak o a mluvíme jako o reálné části čísla za o b jako o imaginární části čísla z. Tato reálná čísla pak značíme symboly3
<z ··= a, =z ··= b.
Komplexní čísla si proto můžeme představovat jako body v komplexní rovině v níž mámepravoúhlý souřadný systém, kde počátku odpovídá číslo 0 = 0 + 0i, na vodorovnou osuvynášíme reálnou část komplexního čísla a na svislou osu imaginární část komplexníhočísla (tzv. komplexní či Gaussova rovina, viz také Obrázek 1).
1Wahrlich es ist nicht das Wissen, sondern das Lernen, nicht das Besitzen sondern das Erwerben, nichtdas Da-Seyn, sondern das Hinkommen, was den grössten Genuss gewährt.
2Je dobré si uvědomit, že symbol + v tomto zápisu nehraje roli algebraické operace. Je to vlastně jenoddělovač, který říká co je reálná část a imaginární část komplexního čísla. Jinak řečeno, jde o jiný zápisuspořádané dvojice (a, b) ∈ R2.
3Symbol ··= označuje definitorickou rovnost. Symbol na levé straně od ··= je definován výrazem na pravéstraně. Povšimněte si, že < a = lze chápat jako zobrazení < : C→ R a = : C→ R.
Dvě komplexní čísla z1 = a1 + b1i a z2 = a2 + b2i, a1, a2, b1, b2 ∈ R, se rovnají, píšemez1 = z2, právě když se rovnají jejich reálné a imaginární části. Komplexní čísla sčítáme anásobíme podle předpisu
Sčítání se provádí tzv. po složkách a násobení formálně odpovídá roznásobení závorek avyužití vztahu i2 = −1. Množina C s takto zavedenými binárními operacemi tvoří těleso(Cvičení 1.1). Znak pro násobení, tečku, ve většině případů explicitně nepíšeme.
Číslo komplexně sdružené k číslu z = a+ bi ∈ C, a, b ∈ R, definujeme předpisem
z ··= a− bi.
Geometricky tato operace představuje zrcadlení vůči reálné ose v Gaussově rovině, vizObrázek 1. Není těžké si rozmyslet4 (Cvičení 1.2), že pro z, w ∈ C platí
zw = z w, z + w = z + w a z = z. (2)
Povšimněte si, že komplexní číslo z je reálné, právě když z = z.Podobně jako v případě reálných čísel máme k dispozici absolutní hodnotu komplexního
čísla. Konkrétně pro komplexní číslo
z = a+ bi, a, b ∈ R,
klademe5
|z| ··=√a2 + b2
a toto reálné nezáporné číslo nazýváme absolutní hodnotou komplexního čísla z.Absolutní hodnotu komplexního čísla si představujeme jako délku úsečky spojující bod od-povídající číslu 0 a bod odpovídající číslu z v Gaussově (komplexní) rovině. Pro představuviz Obrázek 1.
Zmiňme několik užitečných vlastností absolutní hodnoty komplexního čísla. Zřejměplatí, že |z|2 = zz a |z| = |z| pro každé komplexní číslo z ∈ C. Skutečně, je-li z = a + bi,a, b ∈ R, pak
Dále pro libovolná komplexní čísla z, w ∈ C je |zw| = |z| · |w|. Ano, podle výše uvedenéhototiž platí
|zw|2 = zw zw = zz ww = |z|2 |w|2 .
Po odmocnění dostáváme požadovaný vztah mezi absolutními hodnotami.4Synonymum pro lehký důkaz.5Mohlo by se zdát, že symbol |z| má nyní dva významy – každé reálné číslo je i komplexní číslo. Oba
významy ale v tomto případě splývají: |a+ 0i| =√a2 + 02 =
√a2 = |a|.
5
<
=
a
bz
|z| =√a2 + b2 <
=
−b
a
bz
z
Obrázek 1: Vlevo: absolutní hodnota komplexního čísla z = a + bi, a, b ∈ R, v Gaussově(komplexní) rovině. Vpravo: komplexně sdružené číslo z k číslu z = a+ bi, a, b ∈ R.
1.1.1 Trojúhelníková nerovnost
Absolutní hodnota komplexního čísla splňuje trojúhelníkovou nerovnost. Pro komplexníčísla z, w ∈ C platí
|z + w| ≤ |z|+ |w| .
Proč se této nerovnosti říká „trojúhelníková“ je zřejmé z Obrázku 2.
Důkaz trojúhelníkové nerovnosti. Pro kvadrát absolutní hodnoty platí
Po těchto úvodních odstavcích s povídáním o komplexních číslech se vraťme k pojmu okolí.Připomeňme, že pro a ∈ R a ε > 0 jsme v BI-ZMA definovali okolí bodu a o poloměru εpředpisem
Ha(ε) ··= (a− ε, a+ ε) = x ∈ R | |x− a| < ε ⊂ R.
O bodu a mluvíme také jako o středu okolí Ha(ε). Dále jsme definovali okolí bodu +∞,resp. −∞, jako množinu H+∞(K) = (K,+∞), resp. H−∞(K) = (−∞, K), pro zadanéreálné K ∈ R.
Obrázek 2: Grafická ilustrace trojúhelníkové nerovnosti |z + w| ≤ |z|+ |w| pro komplexníčísla z, w ∈ C.
<
=
z
ε
Hz(ε)<
=
R
H∞(R)
Obrázek 3: Vlevo: okolí bodu z ∈ C s poloměrem ε > 0. Vpravo: okolí ∞ s parametrem R,vyznačená oblast pokrývá celou rovinu vyjma bílého kruhu (včetně „hraniční“ kružnice).
Jsouce vybaveni pojmem absolutní hodnoty komplexního čísla, můžeme definovat okolíbodu z ∈ C s poloměrem ε > 0 prakticky stejným předpisem jako v předchozím odstavci,
Hz(ε) ··= w ∈ C | |w − z| < ε ⊂ C.
Množina Hz(ε) geometricky představuje kruh (disk) v komplexní rovině se středem v boděz a poloměrem ε. Hranice kruhu do této množiny nepatří. Vidíme, že názvosloví spojené spojmem okolí (střed, poloměr) má vlastně v komplexní rovině výstižnější význam než nareálné ose, viz Obrázek 3.
Podobně jako jsme k množině R přidali dva prvky +∞ a −∞, přidáváme k C prvek∞. Tuto rozšířenou množinu opět značíme C ··= C ∪ ∞. Okolí ∞ v komplexní roviněpak je dáno
H∞(R) ··= z ∈ C | |z| > R ⊂ C,
kde R > 0 je kladný parametr. Geometricky tedy H∞(R) představuje vnějšek kruhu o
7
poloměru R a středu v bodě 0. Poznamenejme, že ačkoliv platí R ⊂ C inkluze R ⊂ C užpravdivá není. Upozorňujeme čtenáře aby se zamyslel nad rozdílem mezi symboly ∞, +∞a −∞. Nyní je tedy nutné skutečně ukončit občasné lajdácké psaní∞ místo +∞. Jedinouvýjimkou z tohoto pravidla je použití symbolu ∞ v notaci limit posloupností a řad.
1.2 Limita komplexních posloupnostíNyní můžeme zavést pojem limity pro komplexní číselné posloupnosti (prakticky překopí-rováním definice pro reálné číselné posloupnosti). Řekneme, že posloupnost komplexníchčísel (zn)∞n=0 má limitu w ∈ C, právě když pro každé okolí Hw bodu w existuje n0 ∈ Ntakové, že pokud n > n0 pak zn ∈ Hw. Pokud w je limitou posloupnosti (zn)∞n=0, pak tutoskutečnost symbolicky zapisujeme následujícími ekvivalentními způsoby
limn→∞
zn = w nebo zn → w .
Pokud limita posloupnosti (zn)∞n=0 existuje a její hodnota w není ∞, tj. w ∈ C, pak o tétoposloupnosti mluvíme jako o konvergentní posloupnosti.
Není těžké si rozmyslet, že tento pojem limity má spoustu vlastností shodných s limitouzavedenou pro reálné posloupnosti v BI-ZMA. Speciálně například každá posloupnost mánejvýše jednu limitu6, dále každá posloupnost vybraná z posloupnosti mající limitu mástejnou limitu jako původní posloupnost. Stále také platí vhodně upravená věta o limitěsoučtu, součinu a podílu posloupností. Viz také Cvičení 1.9.
Některé koncepty se do komplexního oboru ovšem nepřenáší. Na rozdíl od reálných po-sloupností nemáme pojem monotónní posloupnosti. Mezi komplexními čísly není zavedenožádné standardní uspořádání. Podobně v komplexním oboru nemáme „jednostranná“ okolíbodů.
Veledůležitou vlastností pojmu konvergence komplexních posloupností je platnost známéBolzanovy–Cauchyovy podmínky (úplnost tělesa komplexních čísel):Věta 1.1 (Bolzano–Cauchy): Komplexní posloupnost (zn)∞n=0 konverguje, právě když prokaždé ε > 0 existuje n0 ∈ N takové, že pokud n,m > n0 pak |zn − zm| < ε.
Důkaz. Nejprve dokažme jednodušší implikaci zleva doprava. Předpokládejme, že zn → w.Pro ε > 0 máme k dispozici n0 = n0(ε/2) takové, že je-li n > n0 pak zn ∈ Hw(ε/2). Prolibovolná n,m > n0 tedy platí
|zn − zm| = |zn − w + w − zm| ≤ |zn − w|+ |w − zm| <ε
2 + ε
2 = ε .
Naopak, předpokládejme, že platí tvrzení na pravé straně ekvivalence. Uvažme reálnéposloupnosti (<zn)∞n=0 a (=zn)∞n=0. Dle předpokladu pro ε > 0 existuje n0 ∈ N takové, žepokud n,m > n0 pak7
Posloupnosti (<zn)∞n=0 a (=zn)∞n=0 proto splňují Bolzano–Cauchyovu podmínku konver-gence (viz BI-ZMA) pro reálné posloupnosti a proto existují konečné reálné limity
a ··= limn→∞
<zn ∈ R a b ··= limn→∞
=zn ∈ R .
Označme w ··= a+ bi. Potom s využitím trojúhelníkové nerovnosti dostáváme
|zn − w| =∣∣∣<zn − a+ i(=zn − b)
∣∣∣ ≤ |<zn − a|+ |=zn − b| → 0
a proto zn → w.
Všimněte si, že důkaz stojí na Bolzanově–Cauchyově podmínce pro reálné posloupnosti(tedy úplnosti reálných čísel).
1.3 Limita a spojitost funkcePosuňme se nyní od posloupností k funkcím. V této sekci se lehce odchýlíme od způsobu,jakým je limita funkce zavedena v úvodním kurzu BI-ZMA a zavedeme limitu o něcoobecněji.
Nejprve ještě zaveďme dva užitečné pojmy. Hromadným bodem množiny M ⊂ Cnazýváme bod w ∈ C takový, že každé okolí Hw bodu w obsahuje alespoň jeden bodmnožiny M různý od w. Hromadný bod množiny M očividně nemusí být prvkem množinyM .
Uvažme nyní funkci f : M → C definovanou na (neprázdné) množině M ⊂ C ahromadný bod w ∈ C množiny M = Df . Bod u ∈ C nazveme limitou funkce f v boděw, právě když pro každé okolí Hu bodu u existuje okolí Hw bodu w takové, že kdykolivz ∈ (Hw r w) ∩M pak platí f(z) ∈ Hu. Tuto situaci symbolicky zapisujeme následovně
limz→w
f(z) = u nebo limwf = u.
Je-li dále N ⊂M množina mající w také jako hromadný bod, pak klademe
limz→wz∈N
f(z) ··= limz→w
(f∣∣∣M∩N
)(z)
a mluvíme o limitě funkce f vzhledem k množině N . Viz také Cvičení 1.11.I pojem limity funkce zavedený tímto způsobem má podobné vlastnosti jako v BI-ZMA.
Speciálně například platí
limw
(f + g) = limwf + lim
wg,
limw
(f · g) = limwf · lim
wg,
limw
f
g= limw f
limw g,
za předpokladu, že bod w je hromadným bodem množiny Df ∩Dg, limity limw f a limw gexistují a výrazy na pravých stranách rovností mají dobrý smysl.
Spojitost funkce f v bodě w ∈ Df zavádíme pak jednoduše požadavkem
limz→w
f(z) = f(w).
Pod spojitou funkcí pak máme na mysli funkci spojitou v každém bodě svého definičníhooboru.
1.4 Derivace funkceZ předešlého textu můžete mít pocit, že v komplexním oboru vše funguje tak jak jsmezvyklí a že až na pár drobných detailů bude vše jako při starém. Tento pocit se významnězlomí jakmile se začneme zabývat derivací komplexní funkce komplexní proměnné.
Uvažme funkci f : M → C definovanou na množině M = Df ⊂ C a bod w takový,že existuje Hw okolí bodu w splňující Hw ⊂ M . Takovýto bod je zcela jistě hromadnýmbodem množiny M . Existuje-li konečná8 limita
limz→w
f(z)− f(w)z − w
,
pak ji nazýváme derivací funkce f v bodě w a značíme ji f ′(w).Nyní by opět bylo možné odvodit známá pravidla pro derivování součtu, součinu a
podíly funkcí. Existence derivace komplexní funkce komplexní proměnné ovšem klade velmistriktní omezení na funkci samotnou. Ilustrujme toto tvrzení na jednom jednoduchémpříkladu.
Uvažme funkci f : M → C mající derivaci f ′(w) ∈ C v hromadném bodě w = a +bi otevřené množiny M ⊂ C. Dále předpokládejme, že funkce f nabývá pouze reálnýchhodnot, tj. f(M) ⊂ R. Potom současně platí
f ′(w) = limh→ah∈R
f(h+ bi)− f(w)h− a
∈ R,
f ′(w) = −i limh→bh∈R
f(a+ hi)− f(w)h− b
∈ iR.
A nutně proto f ′(w) = 0. Takováto funkce je proto konstantní na množině M !Předchozí odstavec můžeme přeformulovat úderněji takto: komplexních funkcí s re-
álným oborem hodnot existuje jistě celá řada, ovšem mezi všemi těmito funkcemi jsoudiferencovatelné pouze ty konstantní!
Ba co víc. Lze ukázat, že má-li komplexní funkce komplexní proměnné konečnou deri-vaci, pak má i derivace všech vyšších řádů! V teorii komplexní funkce komplexní proměnnése mluví o tzv. holomorfních funkcích. Případného zvídavého čtenáře odkazujeme na lite-raturu zmíněnou v Sekci 1.7.
8Tj. ∈ C.
10
<
=
r
ϕ
a
bz
Obrázek 4: Polární tvar komplexního čísla z = a+ bi = reiϕ.
1.5 Polární tvar komplexního číslaAbychom uvedli příští kapitolku připomeňme, že ze středoškolské matematiky jistě znátetzv. polární tvar komplexního čísla z ∈ C,
z = r eiϕ ··= r(cosϕ+ i sinϕ), r ≥ 0, ϕ ∈ R. (3)
V podstatě nejde o nic jiného, než o přechod od kartézských (reálná a imaginární osa)souřadnic v komplexní rovině k polárním souřadnicím (vhodně měřený úhel a vzdálenostod počátku). Ilustraci tohoto konceptu lze shlédnout v Obrázku 4. Hodnota ϕ není dánajednoznačně, ale až na celočíselné násobky 2π. Abychom zajistili jednoznačnost musímeomezit možné hodnoty ϕ. Standardně se požaduje ϕ ∈ (−π, π〉. Přesněji, platí-li pro z 6= 0rovnost z = reiϕ, kde ϕ ∈ (−π, π〉 pak o ϕ mluvíme jako o argumentu čísla z a značímeho arg z = ϕ.
Volíme-li v rovnici (3) speciálně r = 1 a ϕ = π dostáváme jednu z nejkrásnějšíchmatematických rovnic9
eiπ + 1 = 0 . (4)Jedná se pouze o formální zápis, nebo mu lze dát hlubší význam? Má symbol eiπ zavedenýv rovnici (3) skutečně něco společného s exponenciální funkcí známou z BI-ZMA? Na tytoa další otázky odpovíme v další kapitole.
1.6 Exponenciální funkceThis is the most important function in mathematics. Walter Rudin
Uvažme komplexní číslo z ∈ C a posloupnost (sn)∞n=0 (ve skutečnosti tedy posloupnostčástečných součtů jisté komplexní číselné řady) komplexních čísel
sn ··=n∑k=0
zk
k! , n = 0, 1, 2, . . .
9Skutečně! Tato rovnost vyhrává matematické soutěže krásy.
Pro libovolná přirozená n,m splňující n > m platí rovnost
sn − sm =n∑
k=m+1
zk
k!
a díky (několikrát použité) trojúhelníkové nerovnosti pak i nerovnost
|sn − sm| ≤n∑
k=m+1
|z|k
k! .
Reálná číselná řada∞∑k=0
|z|k
k!
je ale podle d’Alembertova kritéria10 (absolutně) konvergentní. Podle Bolzanovy–Cauchyovypodmínky pro reálné číselné řady můžeme proto pro libovolné ε > 0 najít přirozené n0 tak,že pro každé n,m > n0, n > m, je
n∑k=m+1
|z|k
k! < ε .
Tím pak ale pro tato n a m platí i nerovnost
|sn − sm| ≤n∑
k=m+1
|z|k
k! < ε .
Podle Bolzanova–Cauchyova kritéria (Věta 1.1) pro komplexní posloupnosti je tedy kon-vergentní i komplexní posloupnost (sn)∞n=1. Označme její limitu očekávaným symbolem
∞∑k=0
zk
k!··= lim
n→∞sn = lim
n→∞
n∑k=0
zk
k! .
V předchozím odstavci jsme zjistili, že komplexní řada∞∑k=0
zk
k!
konverguje pro libovolné z ∈ C. Její součet je jednoznačně určené komplexní číslo. Tímtozpůsobem definujeme zobrazení exp : C→ C,
exp(z) ··=∞∑k=0
zk
k! , z ∈ C.
10Uvažme reálnou číselnou posloupnost s členy an > 0, n ∈ N∗. Nechť existuje limita limn→∞an+1an
,označme její limitu q. Je-li q < 1, pak reálná číselná řada
∑∞n=0 an konverguje. Pokud q > 1, pak zmíněná
číselná řada diverguje.
12
Jedná se o rozšíření exponenciální funkce na všechna komplexní čísla. Speciálně tedy platí,že exp(1) je Eulerovo číslo, či pro reálné x je exp(x) = ex známá reálná exponenciála. Zdefinice také ihned plyne vztah exp(0) = 1.
Exponenciální funkce stále splňuje veledůležitý vztah
exp(z + w) = exp(z) exp(w) , z, w ∈ C . (5)
Skutečně, pro součin dvou absolutně konvergentních číselných řad obecně platí11
∞∑k=0
ak ·∞∑`=0
b` =∞∑n=0
n∑m=0
ambn−m .
Speciálně v našem případě proto máme
exp(z) exp(w) =∞∑k=0
zk
k! ·∞∑`=0
w`
`! =∞∑n=0
n∑m=0
zm
m!wn−m
(n−m)! =
=∞∑n=0
1n!
n∑m=0
(n
m
)zmwn−m =
∞∑n=0
(z + w)nn! = exp(z + w).
V předposlední rovnosti jsme použili binomickou větu.Z rovnosti (5) plyne řada důležitých vlastností komplexní exponenciály. Například pro
každé komplexní číslo z ∈ C platí
1 = exp(0) = exp(z − z) = exp(z) exp(−z),
a proto číslo exp(z) nikdy není nulové a
exp(−z) = 1exp(z) , z ∈ C.
Z předmětu BI-ZMAvíme, že trigonometrické funkce sin a cos lze rozvinout do Taylo-rových řad s nekonečným poloměrem konvergence. Přesněji víme, že platí rovnosti
pro zadané reálné x (ix je tedy čistě imaginární, nebo nulové). Povšimněme si, že
ik =
1, k = 4`, ` ∈ Z,i, k = 4`+ 1, ` ∈ Z,−1, k = 4`+ 2, ` ∈ Z,−i, k = 4`+ 3, ` ∈ Z.
Přeuspořádáme-li tedy sčítání v (6), což si můžeme dovolit vzhledem k absolutní konver-genci příslušné řady, tak dostáváme
exp(ix) =∞∑k=0
(−1)k(2k)! x
2k + i∞∑k=0
(−1)k(2k + 1)!x
2k+1 = cosx+ i sin x , x ∈ R. (7)
Celkem uzavíráme, že pro reálné x ∈ R leží exp(ix) = cos x+ i sin x na jednotkové kružniciv komplexní rovině se středem v bodě 0. Parametr x představuje úhel měřený (v radiánech)od kladného směru reálné osy proti směru hodinových ručiček. Navíc z rovnosti (7) ihnedplynou rovnosti
exp(iπ
2
)= cos π2 + i sin π2 = i,
exp(iπ) = cos π + i sin π = −1.
Druhá z těchto rovnic po jednoduché úpravě je přesně rovnice (4).Na závěr ještě poznamenejme, že pro x ∈ R z rovnic
exp(ix) = cos x+ i sin x,exp(−ix) = cos x− i sin x,
můžeme vyjádřit známé trigonometrické funkce sinus a kosinus pomocí exponenciály
cosx = 12(
exp(ix) + exp(−ix)),
sin x = 12i(
exp(ix)− exp(−ix)).
Funkce sin a cos můžeme pomocí nich (nebo rovnou pomocí příslušných Taylorových roz-vojů) rozšířit na celou komplexní rovinu.
Na závěr této kapitoly poznamenejme, že komplexní exponenciála exp : C→ C již neníprostá funkce. Skutečně, z rovnice (7) například ihned vidíme, že exp(0) = exp(2πi) = 1.Není proto možné mluvit o inverzní funkci k funkci exp. Zavést komplexní logaritmus, log,je tedy složitější úloha, které se věnujeme v Cvičení 1.18, 1.19 a 1.20.
1.7 Poznámky a odkazyPřípadné zájemce o podrobný výklad komplexní analýzy, kterou jsme zde sotva nakousli,čtenáře odkazujeme na několik kvalitních učebnic uvedených v seznamu literatury, kon-krétně [4], [1] a [11].
14
1.8 CvičeníCvičení 1.1: Dokažte, že množina C s operacemi zavedenými v (1) tvoří těleso.
Řešení. Pro důkaz toho, že (C, +, ·) tvoří těleso, jsou potřeba dva pojmy z lineární algebry,konkrétně těleso a grupa.
Začneme ověřením, zda je (C,+) abelovská grupa. V následujících výpočtech uvažmev = a+ bi a u = c+ di a postupně ověřme požadované vlastnosti:
• komutativita
v + u = a+ bi+ c+ di = (a+ c) + it(b+ d) == (c+ a) + i(d+ b) = c+ di+ a+ bi = v + u,
• asociativita
(u+ v) + w = (a+ bi+ c+ di) + e+ fi = a+ c+ i(b+ d) + e+ fi == a+ c+ e+ i(b+ d+ f) = a+ bi+ (c+ e+ i(d+ f)) == u+ (v + w),
• neutrálním prvkem této grupy je 0 = 0 + 0i, skutečně, pro každé u ∈ C platí
u+ 0 = (a+ bi) + 0 = 0 + (a+ bi) = a+ bi,
• pro každé číslo tvaru u = a+ bi existuje opačný prvek ve tvaru v = −a− bi
u+ v = (a+ bi) + (−a− bi) = a− a+ i(b− b) = 0 + 0 = 0.
Nyní zjistíme, zda (C \ 0, ·) je grupa. Se stejným značením jako výše platí
z + w = a+ bi+ c+ di = a+ c+ i(b+ d) = a+ c− i(b+ d)z + w = a+ bi+ c+ di = a− bi+ c− di = a+ c− i(b+ d)
• výraz z = z ověříme opakovanou aplikací definice komplexně sdruženého čísla
z = a+ bi = a− bi = a+ bi = z
Cvičení 1.3: Dokažte, že pro každé u ∈ C platí
|<u| ≤ |u| a |=u| ≤ |u|.
Řešení. Pro komplexní číslo u = a+ bi s absolutní hodnotou |u| =√a2 + b2 platí
<u = a a =u = b.
Čísla a2 i b2 jsou jistě nezáporná, proto
|u| =√a2 + b2 ≥
√a2 = |a|
Tím se dostáváme k požadovanému výrazu.
|<u| = |a| ≤ |u|
Obdobně i důkaz druhé nerovnosti:
|u| =√a2 + b2 ≥
√b2 = |b| ⇒ |=u| = |b| ≤ |u|.
Cvičení 1.4: Vypočtěte reálnou a imaginární část komplexního čísla 11−i a komplexního
čísla 1z, kde z je nenulové komplexní číslo.
Řešení. Mějme nenulové z = a+ bi, pak 1z
= 1a+bi , a dále postupujeme následně
1a+ bi
= 1a+ bi
· a− bia− bi
= a− bi(a+ bi)(a− bi) = a− bi
a2 − b2i2=
= a− bia2 + b2 = a
a2 + b2 −b
a2 + b2 i.
Tímto způsobem jsme vyjádřili 1z
= c + di, kde c, d ∈ R, a můžeme tedy triviálně určit <a =,
<1z
= a
a2 + b2 ,
=1z
= −ba2 + b2 .
Odpověď na první otázku tedy je
< 11− i = 1
2 ,
=1z
= 12 .
17
Cvičení 1.5: Převeďte komplexní čísla 1 + i√
2, −3, 4i a −1− i do polárního tvaru.
Řešení. Mějme z = a+ bi. Pro převedení do tvaru z = r(cosϕ+ i sinϕ) nejprve spočteme
r = |z| =√a2 + b2
a poté ϕ. Podmínka
a+ bi = r(cosϕ+ i sinϕ),a
r+ b
ri = cosϕ+ i sinϕ,
je ekvivalentní podmínkám
⇒ a
r= cosϕ a b
r= sinϕ
a tedy, pokud cosϕ 6= 0,tanϕ = sinϕ
cosϕ = b/r
a/r= b
a.
Nyní je potřeba rozlišit situace podle znaménka a a využít π-periodicity funkce tan. Řeše-ním poslední rovnice je
ϕ =
arctan(b/a), když a > 0,arctan(b/a) + π, když a < 0.
Pro a = 0 nebo b = 0 můžeme ϕ triviálně dodefinovat následujícím vztahem
ϕ =
0, když a > 0, b = 0,π/2, když a = 0, b > 0,π když a < 0, b = 0,3π/2, když a = 0, b < 0.
Případ a = b = 0 polárně vyjadřovat nemá smysl.Polární tvar zadaných čísel už zbývá jen dopočítat podle odvozených vzorců:
1 + i√
2 '√
3(cos 0.9553 + i sin 0.9553),−3 = 3(cos π + i sin π),4i = 4(cosπ/2 + i sin π/2),
−1− i =√
2(cosπ/4 + i sin π/4).
Cvičení 1.6: Nalezněte všechna komplexní řešení rovnice zn = 1 pro n ∈ N∗. Tato řešenígraficky znázorněte v komplexní rovině.
18
Cvičení 1.7: Ukažte, že množina všech reálných matic tvaru(α β−β α
)(8)
vybavená standardním sčítáním a násobením matic je izomorfní12 tělesu komplexních čísel,C.
Řešení. Označme M množinu všech matic tvaru (8) a dále uvažme
A =(α β−β α
)a B =
(γ δ−δ γ
)
dvě libovolné matice z M . Definujeme zobrazení ϕ : M → C jako
ϕ(A) = α + iβ.
Toto zobrazejní je zřejmě injektivní, protože komplexní čísla α + iβ a γ + iδ se rovnajíprávě když α = γ a β = δ a tedy se musí rovnat i jim odpovídajíci matice z M . Rovněž jetriviálně surjektivní, s inverzním zobrazením
čili a2 + b2 =√α2 + β2. Přičtením této rovnice k dříve odvozenému vztahu a2 − b2 = α
dostáváme postupně
a2 + b2 + a2 − b2 =√α2 + β2 + α
⇒ 2a2 =√α2 + β2 + α
⇒ a = ±√√
α2 + β2 + α
2 .
Obdobně můžeme získat b,
a2 + b2 − (a2 − b2) =√α2 + β2 − α
⇒ 2b2 =√α2 + β2 − α
⇒ b = ±√√
α2 + β2 − α2 .
Ze vztahu β = 2abmůžeme triviálně určit, že pokud β ≥ 0, pak ab ≥ 0 a tedy i sgn a = sgn ba opačně, tj. pokud je β záporná, pak jsou znaménka a a b různá.
Na závěr tedy (horní a dolní znaménka si odpovídají, tj. na začátku zmíněné y1 je třebařešení s horními znaménky a y2 s dolními):
a = ±√√
α2 + β2 + α
2 ,
b =
±√√
α2+β2−α2 když β ≥ 0,
∓√√
α2+β2−α2 když β < 0.
Cvičení 1.9: Uvažme komplexní posloupnost (zn)∞n=0 a w ∈ C. Dokažte následující ekvi-valenci,
limn→∞
zn = w ⇔ limn→∞
|zn − w| = 0 .
Cvičení 1.10: Nalezněte všechny hromadné body následujících množin.
A = 1, B = n | n ∈ N, C = x | x ∈ R, D = 1nein
∣∣∣∣n ∈ N.
20
Cvičení 1.11: Uvažme funkci f mající limitu u v bodě w (který je tím pádem hromadnýmbodem množiny Df ). Dokažte následující tvrzení13: je-li N ⊂ Df mající w jako hromadnýbod, pak je limita funkce f vzhledem k množině N rovna také u.Cvičení 1.12: Dokažte spojitost následujících funkcí
• komplexní polynom komplexní proměnné,
• absolutní hodnota komplexního čísla,
• reálná a imaginární část komplexního čísla,
• komplexní sdružení.
Cvičení 1.13: Rozhodněte o konvergenci řady∞∑k=0
zk
v závislosti na komplexním z ∈ C. Graficky znázorněte obor konvergence jakožto množinuv komplexní rovině.Cvičení 1.14: Uvažme funkci f(x) = arctg x, x ∈ R. Její graf jistě všichni známe a víme,že je definovaná na celé reálné ose. Dále víme, že její Taylorova řada v bodě 0 je
∞∑k=0
(−1)k2k + 1x
2k+1.
Tato reálná číselná řada má poloměr konvergence 1, což může být z grafu funkce arctgpřekvapivé – nevidíme žádný očividný důvod jako tomu je třeba u Taylorových řad funkcíln(x+ 1) nebo 1
1−x (např. v nule).Tento fakt je ale očividný, pokud se na tuto mocninou řadu díváme jako na komplexní
číselnou řadu, tj.∞∑k=0
(−1)k2k + 1z
2k+1, z ∈ C.
V kterých bodech komplexní roviny má tato řada zásadní problém, který zapříčiňuje uve-dené omezení poloměru konvergence?Cvičení 1.15: S pomocí známého vztahu ez+w = ezew, platného pro všechna komplexníz a w, odvoďte součtové vzorce pro reálné funkce sinus a kosinus, tedy
sin(x+ y) = sin x cos y + cosx sin y,cos(x+ y) = cos x cos y − sin x sin y,
kde x, y ∈ R.13V podstatě jde o zobecnění věty o limitě vybrané posloupnosti, případně jedné implikace Heineho věty.
21
Cvičení 1.16: Vyřešte kvadratickou rovnici
z2 + (α + iβ)z + γ + iδ = 0,
kde z je komplexní proměnná a α, β, γ, δ jsou reálné parametry.Cvičení 1.17: Pro z ∈ C definujeme Riemannovu ζ-funkci předpisem
ζ(z) =∞∑k=1
1kz.
Dokažte, že tato řada konverguje pro <z > 1 a Riemannova ζ-funkce je tímto způsobemzadána na množině z ∈ C | <z > 1.
Řešení. Nechť z = a+ bi pro nějaké a, b ∈ R, pak:
ζ(a+ bi) =∞∑k=1
1ka+bi .
Vyšetříme absolutní konvergenci této řady, tj. řady∞∑k=1
∣∣∣∣ 1ka+bi
∣∣∣∣ =∞∑k=1
1|ka||kbi|
=∞∑k=1
1|ka||1ebi ln(k)|
=∞∑k=1
1ka
Dokážeme, že pro a > 1 řada ∑∞k=11ka
konverguje a to přímo z definice. Vypočtemesoučet posloupnosti částečných součtů řady pro nějaké k = 2n − 1 a sdružíme při tomkladné členy řady do následujícího tvaru:
S2n−1 = 1 +( 1
2a + 13a)
+( 1
4a + 15a + 1
6a + 17a)
+ · · ·+( 1
2(n−1)a + · · ·+ 1(2n − 1)a
).
Pro členy v k-té závorce platí nerovnost:
1(2k +m)a ≤
12ka ,
kde m = 0, 1, 2, . . . , 2k − 1. Jelikož každá taková závorka má 2k sčítanců dostáváme:
S2n−1 < 1 + 22a + 22
22a + · · ·+ 2n−1
2(n−1)a <∞∑n=1
12(n−1)(a−1) = 1
1− 12a−1
= 2a−1
2a−1 − 1
Posloupnost částečných součtu je omezena shora. Navíc její členy jsou kladné. To znamená,že existuje limita limn→∞ Sn = S. Jelikož S2n−1 je podposloupnost monotonní posloupnostiSn je i tato limita konečná. Alternativně by šlo využít integrálního kritéria.
Dokázali jsme, že pro a > 1 řada ∑∞k=11ka
konverguje, to znamená, že i řada ∑∞k=11
ka+bi
konverguje (absolutně).
V následujících třech cvičeních se vrátíme k problému logaritmu jakožto komplexnífunkci komplexní proměnné.
22
Cvičení 1.18: Buď w nenulové komplexní číslo, pak existuje spočetně mnoho komplexníchčísel z splňující rovnost exp(z) = w. Jinak řečeno, obor hodnot exp je množina C r 0.Explicitně nalezněte všechna tato řešení.Cvičení 1.19: Pomocí Cvičení 1.18 ukažte, že pro každé nenulové komplexní číslo wexistuje právě jedno řešení rovnice exp(z) = w splňující arg z ∈ (−π, π〉. Toto z značímelogw, definičním oborem takovéto funkce je množina Cr 0.Cvičení 1.20: Vypočtěte
log(−3), log(e+ i), log(i).
Na rozdíl do reálných funkcí reálné proměnné není tak snadné komplexní funkce kom-plexní proměnné graficky znázornit. Následující tři cvičení ukazují dva známé a používanézpůsoby jak komplexní funkce vizualizovat. Následující cvičení popisují tři metody použi-telné k znázorňování komplexních funkcí komplexní proměnné.Cvičení 1.21 (Barevné kódování): Mějme funkci f : C → C. Bodu z ∈ C je funkcí fpřiřazeno komplexní číslo f(z), které má polární tvar
f(z) = reiϕ, (9)
kde r ≥ 0 a ϕ ∈ (−π, π]. Bod z bereme jako bod v komplexní rovině a přiřadíme mu barvuv závislosti na r a ϕ z rovnice (9). Nejčastěji se volí barevný odstín v závislosti na ϕ asytost barvy v závislosti na r.Cvičení 1.22 (Metoda obrazů): Mějme funkci f : C → C. Zvolme vhodné podmnožinyMi ⊂ C, i = 1, 2, . . . , n, (například vhodnou část souřadnicové mřížky, nebo kružnice sestředem v bodě 0 a různých poloměrech). Do roviny vynesme a vhodně označme obrazyf(Mi).Cvičení 1.23 (Křivky konstantní absolutní hodnoty a fáze): Pro funkci f : C → Cmůžeme znázornit křivky v C, kde je |f(z)| konstantní, případně kde je arg f(z) konstantní.
23
2 Fourierovy řadyProfound study of nature is the most fertile source of mathematical discoveries.
Joseph Fourier
V této části textu si stručně představíme důležité matematické objekty nesoucí jménopo francouzském matematikovi a fyzikovi Josephovi Fourierovi (1768 – 1830). Text tétokapitoly bude místy neformální a rozhodně ho nelze považovat za ucelený výklad tétolátky. Cílem je zde zejména poskytnout čtenáři jisté povědomí o těchto důležitých tématecha připravit půdu pro příští kapitolu. Fourierovy řady i Diskrétní Fourierova transformace(DFT), probíraná v příští kapitole, spolu totiž úzce souvisí. DFT lze z jistého úhlu pohleduchápat jako diskrétní analog Fourierových řad.
2.1 ÚvodNebude-li v této kapitole řečeno jinak, pak pod pojmem funkce rozumíme vždy reálnoufunkci jedné reálné proměnné.
V předmětu BI-ZMA jsme se zabývali možností vyjádření některých elementárníchfunkcí ve tvaru tzv. mocninných řad. Například jsme zjistili, a v předchozí kapitole znovuověřili, že v reálném oboru platí rovnosti
ex =∞∑k=0
xk
k! ,
sin x =∞∑k=0
(−1)k(2k + 1)!x
2k+1.
Výrazy na pravých stranách těchto rovností představují mocninné řady, tedy řady jejichžčleny jsou konstantní násobky mocnin xk, k ∈ N. Co kdybychom místo těchto monomůchtěli použít trigonometrické funkce sinus a kosinus?
Ve svém článku z roku 1822 vyjádřil Fourier hypotézu, že každou periodickou „funkci“f s periodou 2T lze vyjádřit ve tvaru tzv. trigonometrické řady. Přesněji, pro takovoufunkci postuloval následující rovnost
f(x) = a0
2 +∞∑k=1
(ak cos kπx
T+ bk sin kπx
T
), x ∈ R, (10)
kde reálné číselné koeficienty a0, a1, a2, . . . a b1, b2, . . . lze napočítat pomocí vztahů
S takto napočítanými číselnými posloupnostmi (an)∞n=0 a (bn)∞n=1 (mají-li uvedené integrálysmysl) se řada na pravé straně rovnosti (10) nazývá Fourierovou řadou funkce f naintervalu (−T, T ). Rovnice (11) a (12) bývají označovány jako Eulerovy vzorce.
Bohužel, pouze periodičnost funkce f nestačí k tomu, aby platila rovnost (10). Z perio-dicity funkcí sinus a kosinus ale logicky vyplývá, že i funkce f , pro kterou má platit rozvoj(10) na celém R, musí být periodická. S problémem jak popsat třídu funkcí, pro kteréby platila rovnost (10) se kromě Fouriera zabývali největší matematici 19. století, např.F. W. Bessel, U. Dini, G. L. Dirichlet, R. O. Lipschitz, B. Riemann a další. Toto snaženíve výsledku vedlo k rozšíření samotného pojmu „funkce“ a k vybudování Lebesgueova in-tegrálu. Podrobný výklad těchto partií matematiky by vydal na samostatný předmět a zdese jimi nebudeme zabývat. Případné zájemce opět odkazujeme např. na [11]. Výklad nanásledujících řádkách je tímto faktem samozřejmě poznamenán. Pokusíme se vypíchnoutalespoň základní výsledky a myšlenky, i ve zjednodušené formě.
2.2 Konvergence Fourierových řadPostupné kroky téměř jedno století trvající práce nakonec vedly k vybudování celé teorietrigonometrických řad. Tato problematika ovšem není ani dnes uzavřená a existují otázkytýkající se Fourierových řad, které zůstávají stále nezodpovězené.
My si zde nejprve uvedeme jeden výsledek tohoto snažení, který dává alespoň částečnouodpověď na to, jaké funkce lze rozvíjet ve Fourierovu řadu, resp. jak je to s tzv. bodovoukonvergencí Fourierovy řady. Důkaz tohoto tvrzení je samozřejmě daleko nad rámcemtohoto kurzu, a proto ho neuvedeme.Věta 2.1: Buď f funkce, která má po částech spojitou derivaci na intervalu 〈−T, T 〉. Po-tom Fourierova řada funkce f na intervalu (−T, T ) konverguje na celé množině R. OznačmeF její součtovou funkci, tzn.
F (x) ··=a0
2 +∞∑k=1
(ak cos kπx
T+ bk sin kπx
T
), ∀x ∈ R ,
kde posloupnosti (an)∞n=0 a (bn)∞n=1 jsou určeny vztahy (11) a (12). Potom platí:
(i) F je periodická funkce s periodou 2T .
(ii) F (x) = f(x+) + f(x−)2 pro každé x ∈ (−T, T ).
(iii) F (T ) = F (−T ) = f(−T+) + f(T−)2 .
kde f(x±) ··= limy→x±
f(y).
Důkaz. Neuvádíme.
Tvrzení této věty je vhodné podrobněji okomentovat.
Poznámka 2.2: Připomeňme, že funkce je po částech spojitá na uzavřeném a ome-zeném intervalu, má-li v tomto intervalu nejvýše konečně mnoho bodů nespojitostia v těchto bodech existují konečné jednostranné limity (tzv. odstranitelná nespojitost,nebo nespojitost 1. druhu).Poznámka 2.3: Podle Věty 2.1 platí rovnost (10), tzn. F (x) = f(x), ve všech bodechspojitosti f . V bodech nespojitosti je pravá strana rovnice (10), tzn. F (x), rovna průměrujednostranných limitních hodnot funkce f v odpovídajícím bodě.Poznámka 2.4: V mnoha situacích hledáme Fourierův rozvoj funkce f ∈ C1(〈−T, T 〉),tj. funkce která má spojitou první derivaci na celém intervalu 〈−T, T 〉 (v bodech ±T jef ′ spojitá z příslušné strany). Rovnost (10) potom platí pro všechna x ∈ (−T, T ). Pronázornou ukázku viz Obrázek 5.Poznámka 2.5: Všimněte si, že ve speciálním případě, kdy T = π, se formule (10), (11)a (12) mírně zjednoduší:
f(x) = a0
2 +∞∑k=1
(ak cos kx+ bk sin kx) , x ∈ R
a
ak = 1π
∫ π
−πf(x) cos kx dx , k ∈ N , (13)
bk = 1π
∫ π
−πf(x) sin kx dx , k ∈ N∗ . (14)
Poznámka 2.6: Všimněte si, že je-li funkce f lichá je ak = 0 pro ∀k ∈ N. Je-li naopakfunkce f sudá je bk = 0 pro ∀k ∈ N∗. (Cvičení 2.1)
Ukažme si nyní alespoň částečně, že z rovnosti (10) skutečně vyplývají Eulerovy vzorceve tvaru (11) a (12) pro koeficienty an a bn. Vynásobením obou stran rovnice (10) funkcísin nπx
T, kde n ∈ N∗, a zintegrováním od −T do T dostaneme∫ T
−Tf(x) sin nπx
Tdx = a0
2
∫ T
−Tsin nπx
Tdx +
+∫ T
−T
( ∞∑k=1
ak cos kπxT
sin nπxT
+ bk sin kπxT
sin nπxT
)dx .
Na pravé straně nyní provedeme záměnu sumy a integrálu. Pro tento krok nemáme ospra-vedlnění, ale za uvedených předpokladů je možné ho provést. Máme tedy∫ T
−Tf(x) sin nπx
Tdx = a0
2
∫ T
−Tsin nπx
Tdx +
+∞∑k=1
ak
∫ T
−Tcos kπx
Tsin nπx
Tdx+ bk
∫ T
−Tsin kπx
Tsin nπx
Tdx .
Protože pro ∀k, n ∈ N∗ je ∫ π
−πsin kx cosnx dx = 0
26
a ∫ π
−πsin kx sinnx dx =
∫ π
−πcos kx cosnx dx = πδk,n ,
(Cvičení 2.3, ověřte!) můžeme po jednoduché substituci spočítat integrály na pravé straněupravovaného výrazu a dojdeme tak k rovnosti∫ T
−Tf(x) sin nπx
Tdx = bnT.
Dostáváme tak formulku (12). Podobnou úvahu lze učinit i v případě koeficientů an a od-vodit tak (11).
Uvažujme ještě chvíli speciální případ, kdy f ∈ C1(〈−T, T 〉). Podle Věty 2.1 platírovnost (10) pro ∀x ∈ (−T, T ). Řada napravo rovnosti (10) konverguje ale pro ∀x ∈ R aprotože je to 2T -periodická funkce, musí se její hodnota pro nějaké x ∈ ((2`−1)T, (2`+1)T ),kde ` ∈ Z, rovnat hodnotě f(y), kde
y = x− 2`T ∈ (−T, T ).
Nahradíme-li tedy levou stranu v rovnici (10) periodickým prodloužení funkce f na R \(2Z + 1)T ,
f ∗(x) ··= f(x−
⌊x+ T
2T
⌋2T), ∀x /∈ (2Z + 1)T,
dostaneme identitu
f ∗(x) = a0
2 +∞∑k=1
(ak cos kπx
T+ bk sin kπx
T
)
s an a bn určenými Eulerovými vzorci (11) a (12), která platí ∀x /∈ (2Z + 1)T . V bodechx ∈ (2Z + 1)T potom opět podle věty 2.1 platí rovnost
f(−T+) + f(T−)2 = a0
2 +∞∑k=1
(ak cos kπx
T+ bk sin kπx
T
).
Příklad 2.7: Prozkoumejme výše uvedená tvrzení na konkrétním příkladu jednoduchéfunkce f(x) = x. Najdeme její Fourierovu řadu na intervalu (−π, π). Volíme tedy T = π.
Vypočtěme Fourierovy koeficienty f . Dosazením do rovnic (13) a (14) spočítáme pomocíintegrace per partes
a0 = 1π
∫ π
−πx dx = 0 ,
ak = 1π
∫ π
−πx cos kx dx = 1
π
([x
ksin kx
]π−π−∫ π
−π
1k
sin kx dx)
= 0 ,
bk = 1π
∫ π
−πx sin kx dx = 1
π
([−xk
cos kx]π−π
+∫ π
−π
1k
cos kx dx)
=
= 2(−1)k+1
k, k ∈ N∗ .
27
Dostáváme tak Fourierův rozvoj (2.5) funkce f(x) = x na (−π, π), který je tvaru
x =∞∑k=1
2(−1)k+1
ksin kx (15)
a tato rovnost platí pro všechna x ∈ (−π, π). Několik jejích částečných součtů s nízkýmpočtem sčítanců je znázorněno na obrázku 5. Skutečně tedy získáváme pocit, že postupnýmpřidáváním členů řady dostáváme lepší a lepší aproximaci funkce f .
x
yn = 1
x
yn = 2
x
yn = 3
x
yn = 4
Obrázek 5: Částečné součty Fourierovy řady (15) na (−π, π) periodického prodlouženífunkce f(x) = x, n označuje počet sčítanců v částečném součtu.
Věta 2.1 se zabývá tzv. bodovou konvergencí, tj. konvergencí odpovídající číselné řadypro pevně zvolený bod x ∈ R. Další kvalitativní vlastnosti konvergence posloupnosti funkcílze vyjádřit pomocí následujícího užitečného pojmu. O posloupnosti funkcí (fn)∞n=0 řek-neme, že stejnoměrně konverguje k funkci f na množině M , právě když pro každéε > 0 existuje n0 ∈ N takové, že pro všechna n > n0 a x ∈ M platí |fn(x) − f(x)| < ε.
28
O Fourierově řadě řekneme, že stejnoměrně konverguje na množině M , právě kdyžposloupnost jejích částečných součtů je stejnoměrně konvergentní na množině M .
Ekvivalentně bychom uvedenou podmínku mohli kompaktně vyjádřit takto: posloup-nost (fn)∞n=0 konverguje stejnoměrně k funkci f na množině M , právě když
limn→∞
supM|fn − f | = 0.
Pokud naše posloupnost stejnoměrně konverguje k funkci f na množině M , tak jistě v kaž-dém bodě x ∈M číselná posloupnost fn(x) konverguje k číslu f(x), tj.
limn→∞
fn(x) = f(x), x ∈M.
Opak ale není pravdou. Bodová konvergence v každém bodě množiny M zřejmě nestačík tomu, aby šlo o stejnoměrnou konvergenci.
Dále zdůrazňujeme, že stejnoměrná konvergence posloupnosti funkcí je pojem relativnívzhledem k dané množině. Tj. slovní spojení „posloupnost funkcí je stejnoměrně konver-gentní“ nemá smysl bez uvedení o jaké množině se mluví. K osvětlení tohoto konceptu atěchto poznámek dobře poslouží následující elementární příklad.Příklad 2.8: Ne/stejnoměrnost konvergence posloupnosti funkcí lze pěkně demonstrovatna jednoduchém příkladu posloupnosti fn(x) = xn. Níže porovnáme bodovou konvergencia stejnoměrnou konvergenci této posloupnosti na vhodně zvolených množinách.
Uvažme nejprve množinu M = (0, 1). Pro každé x z M je bodovou limitou nulováfunkce, tj.
f(x) = limn→∞
xn = 0 .Na druhou stranu ale
supx∈M|xn − 0| = sup
x∈Mxn = 1
pro každé n ∈ N. Tudížlimn→∞
supx∈M|xn − 0| = 1 6= 0
a proto posloupnost funkcí (xn)∞n=0 nekonverguje stejnoměrně na M = (0, 1).Jakmile se ovšem „odrazíme“ od 1, tak již vše bude v pořádku. Uvažme pro názornost
například M = (0, 1/2). Zde pak platí
limn→∞
supx∈M|xn − 0| = lim
n→∞
(12
)n= 0
a posloupnost funkcí (xn)∞n=0 konverguje stejnoměrně k 0 na množině M = (0, 1/2). Proilustraci uvádíme Obrázek 6.
Vraťme se zpět k hlavnímu tématu této kapitoly, Fourierovým řadám. Nyní mámevšechny pojmy nutné k zformulování následující věty.Věta 2.9: Je-li f 2T -periodická funkce se spojitou první derivací na intervalu 〈−T, T 〉,pak její Fourierova řada na intervalu (−T, T ) konverguje stejnoměrně na celém R.
Důkaz. Vynecháváme.
K této problematice se ještě jednou vrátíme v podkapitole 2.3.
29
x
y = xn
1
1
1/2
Obrázek 6: Ilustrace k Příkladu 2.8, graf funkcí xn pro n = 2, 4, 6, 8, 10 na intervalu 〈0, 1〉.
2.3 Gibbsův efektUvažme funkci
f(x) = sgn (x) =
−1, x < 0,0, x = 0,1, x > 0.
a její Fourierovu řadu na intervalu (−π, π). Jedná se o lichou funkci a pro její Fourierovykoeficienty platí ak = 0, k ∈ N, a
bk = 1π
∫ π
−πf(x) sin kx dx = 2
π
∫ π
0sin kx dx = −2
kπ
[cos kx
]π0
= 2kπ
(1− (−1)k
), k ∈ N∗.
Speciálně tedy pro ` ∈ N∗ platí
b2`−1 = 4(2`− 1)π a b2` = 0.
Pro součtovou funkci naší Fourierovy řady proto platí
s2n−1(x) = s2n(x) = 4π
n∑`=1
sin(2`− 1)x2`− 1 . (16)
Z dřívějšího výkladu plyne, že tato řada konverguje stejnoměrně například na intervalu〈δ, π−δ〉 pro 0 < δ < π
2 . V násobcích π má součtová funkce ale neodstranitelnou nespojitost1. druhu („konečný skok“). Z Obrázku 7 je patrné, že blízko u těchto skoků částečnésoučty divoce oscilují, přičemž maximální „amplituda“ těchto oscilací na první pohledpříliš neubývá. Tento jev se nazývá Gibbsův efekt.
Pojďme podrobněji prozkoumat co se děje s částečným součtem řady (16) pro malékladné x a velké n. K tomu použijeme úpravu
sin kxk
=∫ x
0cos kt dt, k ∈ N∗ .
30
a tedy
s2n(x) = 4π
∫ x
0
n∑`=1
cos(2`− 1)t dt .
Dále, využitím vyjádření kosinu pomocí komplexní exponenciály a vzorce pro součet prv-ních několika členů geometrické posloupnosti, dostáváme
n∑`=1
cos(2`− 1)t = 12
n∑`=1
(ei(2`−1)t + e−i(2`−1)t
)=
= 12e
it1− e2int
1− e2it + 12e−it1− e−2int
1− e−2it =
= i
41− e2int
sin t − i
41− e−2int
sin t =
= sin 2nt2 sin t .
a tedy
s2n(x) = 2π
∫ x
0
sin 2ntsin t dt = 2
π
∫ 2nx
0
sin ss
ds︸ ︷︷ ︸G(2nx)··=
+ 2π
∫ x
0
( 1sin t −
1t
)sin 2nt dt︸ ︷︷ ︸
F (x)··=
. (17)
Nejprve prozkoumejme funkci F . Existuje konstanta C > 0 splňující
|F (x)| ≤ Cx2, x ∈ R.
Pro derivaci funkce G(x) platí
G′(x) = 2π
sin xx
, x > 0.
Tato derivace je nulová v násobcích π a maximum funkce G proto je
G(π) = 2π
∫ π
0
sin tt
dt ≈ 1.17898.
Uvážíme-li tedy pravé okolí bodu 0, např. (0, ε), tak vhodnou volnou ε můžeme členF (x) v (17) učinit libovolně malý. Poté lze zvolit dostatečně velké n takové, že první členv (17), tj. G(2nx) nabude hodnoty G(π) pro nějaké x ∈ (0, ε). Hodnota G(π) je známajako Wilbrahamova–Gibbsova konstanta.
2.4 Komplexní vyjádřeníPodívejme se ještě na ekvivalentní formulaci trigonometrické řady (10) pomocí komplexníexponenciály. Tu lze vyjádřit takto:
∞∑k=−∞
ckeikπxT , (18)
31
kde ck ∈ C. Tento způsob zápisu je také bližší výrazům s kterými se budeme potýkatpři studiu diskrétní Fourierovy transformace. Všimněte si, že součet (18) je „dvojitě neko-nečný“. Mezi koeficienty ak, bk a ck lze najít jednoduchý vztah. Vzhledem k rovnosti
∑k∈Z
ckeikπxT = c0 +
∞∑k=1
(cke
ikπxT + c−ke
− ikπxT
)=
= c0 +∞∑k=1
((ck + c−k) cos kπx
T+ i(ck − c−k) sin kπx
T
)
platí následující vztahy mezi koeficienty
a0 = 2c0 , ak = ck + c−k , bk = i(ck − c−k) , k ∈ N∗
a naopakc0 = a0
2 , ck = ak − ibk2 , c−k = ak + ibk
2 , k ∈ N∗ . (19)
Je tedy otázkou vkusu, zda použijeme rozvoj pomocí ak, bk, či ck. Typicky platí, že svýrazem (18) se snadněji pracuje. Na druhou stranu se někdy chceme vyhnout výrazům skomplexními čísly a v takových situacích použijeme spíše rozvoj (10).
Z předchozího odstavce také snadno nahlédneme, že koeficienty ck můžeme přímo vy-počítat pomocí vztahu
ck = 12T
∫ T
−Tf(x)e− ikπxT dx , k ∈ Z . (20)
Případně bychom tuto formuli mohli odvodit stejným způsobem jako dříve (nyní vynáso-bením vhodnou exponenciálou).
2.5 Parsevalova rovnostNa tomto místě ještě uveďme jeden důležitý vztah, tzv. Parsevalovu rovnost.Věta 2.10: Nechť je funkce f Riemannovsky integrabilní na intervalu (−T, T ) a nechťintegrál
∫ T−T f
2(x)dx existuje a je konečný. Potom platí:∞∑
k=−∞|ck|2 = 1
2T
∫ T
−Tf 2(x) dx . (21)
Důkaz. Vynecháváme.
Poznámka 2.11: Předpoklady Věty 2.10 jsou restriktivní. Rovnost (21) platí totiž prokaždou funkci f , která je měřitelná a kvadraticky integrabilní na (−T, T ) v Lebesgueověsmyslu. Tato skutečnost se obvykle vyjadřuje takto: f ∈ L2((−T, T ), dx). Zde se dotýkámeteorie Lebesgueova integrálu a funkcionální analýzy, což jsou opět matematické disciplínyjdoucí nad rámec našeho kurzu. Podotkněme pouze, že funkcionální přístup k trigono-metrickým řadám této problematice „sedí“. Téměř k dokonalosti ho přivedl francouzskýmatematik H. Lebesgue (1875 – 1941).
Podobně jako jsme z rozvoje (10) odvodili Eulerovy vzorce (11) a (12), můžeme i zdealespoň nekorektním způsobem dojít k Parsevalově rovnosti (21). Předpokládejme, že profunkci f platí rozvoj
f(x) =∑k∈Z
ckeikπxT , ∀x ∈ (−T, T ).
Dosazením za f(x) do pravé strany rovnice (21) a prohozením (dvojité) sumy a integrálu(neospravedlněný krok!) dostaneme
12T
∫ T
−Tf 2(x) dx = 1
2T∑`,k∈Z
c`ck
∫ T
−Tei(`+k)πx
T dx
Protože pro libovolné n ∈ Z je∫ T
−TeinπxT dx =
∫ T
−Tcos nπx
Tdx+ i
∫ T
−Tsin nπx
Tdx = 2Tδn,0,
docházíme k rovnosti1
2T
∫ T
−Tf 2(x) dx =
∑k∈Z
ckc−k
Protože uvažujeme funkci f s reálnými hodnotami, vyplývá ze vztahu (20) rovnost ck = c−kpro ∀k ∈ Z a tudíž ckc−k = |ck|2.
Dále uveďme ještě Parsevalovu rovnost zapsanou pomocí koeficientů ak a bk. Sumu nalevé straně rovnice (21) lze zapsat jako
|c0|2 + 2∞∑k=1
ckc−k.
Dosazením vztahů (19) dostaneme Parsevalovu rovnost (21) ve tvaru
a20
2 +∞∑k=1
(a2k + b2
k
)= 1T
∫ T
−Tf 2(x) dx . (22)
V aplikacích, které uvedeme níže, lze Parsevalovu rovnost interpretovat např. jako vy-jádření zachování celkové energie v původním a transformovaném signálu. Parsevalova rov-nost představuje ale také silný nástroj pro sčítání řad.Příklad 2.12: Vraťme se ještě k Příkladu 2.7. Pro periodické prodloužení funkce f(x) = x,x ∈ (−π, π) jsme dostali Fourierovy koeficienty
ak = 0 , bk = 2(−1)k+1
k.
Protoc0 = 0 , ck = − i2
2(−1)k+1
k, c−k = i
22(−1)k+1
k, k ∈ N∗ .
33
Parsevalova rovnost (21) potom dává
∑k 6=0
1k2 = 2
∞∑k=1
1k2 = 1
2π
∫ π
−πx2 dx = 1
2π
[x3
3
]π−π
= π2
3 .
Celkem dostáváme známou formulku∞∑k=1
1k2 = π2
6 .
Ke stejnému závěru dojdeme, použijeme-li Parsevalovu rovnost ve tvaru (22). (Zkuste sito!)
2.6 Poznámky a odkazyZájemce o podrobné studium problematiky Fourierových řad odkazujeme na klasickoumonografii [13].
2.7 CvičeníCvičení 2.1: Následující dvě tvrzení se často hodí při počítání Fourierových koeficientů.
• Je-li f spojitá sudá funkce, tj. f(−x) = f(x) pro každé x ∈ R, pak pro koeficienty bkjejí Fourierovy funkce na intervalu (−T, T ) platí bk = 0, k ∈ N∗.
• Je-li f spojitá lichá funkce, tj. f(−x) = −f(x) pro každé x ∈ R, pak pro koeficientyak její Fourierovy funkce na intervalu (−T, T ) platí ak = 0, k ∈ N.
Dokažte.
Řešení. Pro důkaz nejdříve potřebujeme ukázat následující tvrzení: Mějme sudou funkcif : X → R a lichou funkci g : X → R, kde X ⊂ R splňující ∀x ∈ X: −x ∈ X. Pakf · g : X → R je lichá funkce. Důkaz: Pro x ∈ X platí
• Pro první případ: číselné koeficienty bk máme v (12) definováné vztahem
bk = 1T
∫ T
−Tf(x) sin kπx
Tdx, k ∈ N∗.
Funkce sin je lichá funkce a funkce f je z zádání sudá funkce. Proto z faktů zmíněnýchvýše dostáváme:
bk = 1T· 0 = 0.
• Obdobně pro duhý případ: číselné koeficienty ak máme v (11) definováné vztahem
ak = 1T
∫ T
−Tf(x) cos kπx
Tdx, k ∈ N.
Funkce cos je sudá funkce a funkce f je z zádání lichá funkce, tedy
ak = 1T· 0 = 0.
Cvičení 2.2: Toto cvičení ukazuje jak „hladkost“ funkce souvisí s chováním jejích Fou-rierových koeficientů. Mějme 2T -periodickou funkci f mající spojitou ntou derivaci, potomexistují konstanty Ca, Cb, Cc závisející pouze na f a T splňující
|ak| ≤Cakn, |bk| ≤
Cbkn
a |ck| ≤Cc|k|n
.
Cvičení 2.3: Ukažte, že pro každé k, n ∈ N platí∫ π
−πsin kx cosnx dx = 0 , (23)∫ π
−πsin kx sinnx dx =
∫ π
−πcos kx cosnx dx = πδk,n . (24)
U následujících příkladů doporučujeme použít svůj oblíbený počítačový algebraickýsystém a prozkoumat grafy zadaných funkcí a částečné součty zadaných Fourierových řad.Cvičení 2.4: Nalezněte Fourierovu řadu funkce f(x) = 1− x2 na intervalu (−1, 1).Cvičení 2.5: Nalezněte Fourierovu řadu funkce
f(x) =
0, x ≤ 0,x, x > 0.
na intervalu (−π, π).Cvičení 2.6: Nalezněte Fourierovu řadu funkce f(x) = sgn x na intervalu (−π, π). Spomocí nalezeného rozvoje určete součet číselné řady
∞∑n=0
(−1)n2n+ 1 .
Dále si všimněte, k jaké hodnotě konverguje vámi spočtená Fourierova řada pro x = 0,tento fakt lze brát jako další důvod pro definici sgn (0) = 0.
35
Cvičení 2.7: Nalezněte Fourierovu řadu funkce f(x) = x(x − π)(x + π) na intervalu(−π, π). S pomocí nalezeného rozvoje určete součet číselné řady
∞∑k=0
(−1)k(2k + 1)3 .
Cvičení 2.8: Nalezněte Fourierovu řadu funkce f(x) = |x| na intervalu (−π, π) a pomocíParsevalovy rovnosti určete součet číselné řady
∞∑n=1
1n4 .
Cvičení 2.9: Nalezněte Fourierovu řadu funkce f(x) = sin(αx), resp. f(x) = cos(αx) naintervalu (−π, π), kde α /∈ Z.Cvičení 2.10: Nalezněte Fourierovu řadu funkce f(x) = x2 na intervalu (−π, π) a pomocíParsevalovy rovnosti určete součet číselné řady
∞∑n=1
(−1)n+1
n2 .
Cvičení 2.11: Nalezněte Fourierovu řadu funkce f(x) = sinh x na intervalu (−π, π).Cvičení 2.12: Nalezněte Fourierovu řadu funkce f(x) = eαx na intervalu (−T, T ), kdeα ∈ R a T > 0.Cvičení 2.13: Nalezněte Fourierovu řadu funkce
f(x) =
1, pro |x| ≤ α,
0, pro α < |x| < π,
na intervalu (−π, π), kde α ∈ (0, π). Pomocí Parsevalovy rovnosti vypočtěte součty řad∞∑n=1
sin2(nα)n2 a
∞∑n=1
cos2(nα)n2 .
36
x
yn = 1
x
yn = 7
x
yn = 13
x
yn = 19
Obrázek 7: Částečné součty Fourierovy řady (16) funkce signum na intervalu (−π, π), nopět označuje počet sčítanců v částečném součtu.
37
t
x
t0 t1 t2 t3 t4 t5 t6 t7 t8 t9
∆
Obrázek 8: Vzorkování signálu x(t) s vzorkovací frekvencí f = 1/∆.
3 Diskrétní Fourierova transformace (DFT)V této kapitole se budeme podrobně věnovat diskrétní Fourierově transformaci (DFT).Ukážeme si jednu z jejích možných interpretací jako nástroje pro spektrální analýzu signálua prozkoumáme její základní vlastnosti. Podrobný, čtenáři přístupný, přehled vlastnostíDFT a jejích aplikací ve zpracování audiosignálu lze nalézt například v [12].
3.1 ÚvodPředstavme si, že v N po sobě jdoucích časových okamžicích tn = ∆ ·n, n = 0, 1, . . . , N−1,vzájemně od sebe vzdálených o ∆ > 0 sekund, naměříme hodnoty jistého signálu x(tn). Proilustraci uvádíme Obrázek 8. Může jít o záznam zvuku, teploty, zemětřesení, kurz bitcoinuvůči dolaru atp. Diskrétní Fourierovou transformací tohoto záznamu pak rozumíme14
x(ωk) = 1√N
N−1∑n=0
x(tn)e−iωktn , k = 0, 1, . . . , N − 1 .
Komplexní číslo x(ωk) je „spektrum“ odpovídající úhlové frekvenci ωk = kΩ (měřena vradiánech za sekundu) a Ω = 2π
N∆ je základní úhlová frekvence. Dále ještě poznamenejme,že f = 1
∆ představuje vzorkovací frekvenci (sampling rate). Velikost (v absolutní hodnotě)x(ωk) udává, jak významně do signálu přispívá harmonická oscilace s úhlovou frekvencí ωk.
Z výše uvedeného je patrné, že budeme pracovat v komplexním vektorovém prostoruCN . Z praktických důvodů budeme v sekcích věnovaných DFT indexovat složky vektorů zCN od nuly, tzn.
x = (x0, x1, . . . , xN−1) ∈ CN .
Nyní můžeme přistoupit k obvyklé definici.14K tomuto vzorci lze dospět například diskretizací Eulerova vzorce pro koeficient ck v komplexním
vyjádření Fourierovy řady. Tedy přechodem od spojité funkce k diskrétnímu signálu při němž se integrálnahradí konečným součtem.
38
Definice 3.1: Diskrétní Fourierova transformace vektoru x = (x0, x1, . . . , xN−1) ∈CN je opět vektor x ∈ CN , jehož složky jsou definovány předpisem
xk ··=1√N
N−1∑n=0
xne−2πikn/N , k = 0, 1, . . . , N − 1. (25)
Na prostoru CN je tímto způsobem definováno zobrazení F : CN → CN , které každémuvektoru x ∈ CN přiřadí opět vektor x ∈ CN ,
Fx := x.
Tomuto F přirozeně říkáme diskrétní Fourierova transformace.Vlastnostmi tohoto zobrazení se budeme zabývat. Nejprve si ale připomeneme něko-
lik základních poznatků z lineární algebry týkající se vektorových prostorů se skalárnímsoučinem. DFT odpovídá volbě velice speciálního lineárního zobrazení definovaného naprostoru se skalárním součinem, jde o tzv. unitární operátor. O těchto operátorech si taképovíme víc v následující podsekci. Všechny fundamentální vlastnosti DFT potom vyplynouz obecných vlastností unitárních operátorů jako speciální případ.
3.2 Hilbertův prostor konečné dimenzeMathematical science is in my opinion an indivisible whole, an organism whosevitality is conditioned upon the connection of its parts. David Hilbert
V této kapitole shrneme některé pojmy z lineární algebry. Začněme skalárním součinem.Buď V vektorový (někdy též lineární) prostor nad tělesem komplexních čísel C. Zobrazení
〈·, ·〉 : V × V → C
splňující podmínky
i) pro každé x, y, z ∈ V a α ∈ C platí
〈x+ αy, z〉 = 〈x, z〉+ α〈y, z〉 ,
ii) pro každé x, y ∈ V platí 〈x, y〉 = 〈y, x〉,
iii) pro každé x ∈ V je 〈x, x〉 ≥ 0 a rovnost platí právě tehdy, když x = 0,
nazýváme skalárním součinem na prostoru V . O vektorovém prostoru V konečné di-menze vybaveném skalárním součinem mluvíme jako o Hilbertově prostoru15.
15Předpoklad konečnosti dimenze uvažovaného vektorového prostoru je podstatný. Vektorový prostor seskalárním součinem se nazývá pre-Hilbertův prostor. Hilbertův prostor je pre-Hilbertův prostor, kterýje úplný. Ukazuje se ovšem, že každý pre-Hilbertův prostor konečné dimenze je úplný a tedy i Hilbertův.Protože se zde prostory nekonečné dimenze nebudeme zabývat, je naše označení konzistentní se zbytkemsvěta.
Podmínka i) říká, že skalární součin je lineární ve svém prvním argumentu. Kombinacípodmínek i) a ii) zjišťujeme, že je antilineární ve své druhé složce. Přesněji, pro každéx, y, z ∈ V a α ∈ C platí
Na skalární součin je navázáno několik další pojmů, tím nejznámějším je ortogona-lita (kolmost) vektorů. Pokud pro vektory x, y ∈ V platí rovnost 〈x, y〉 = 0, pak o nichmluvíme jako o vzájemně kolmých (ortogonálních)16 vektorech. Symbolicky tento faktzapisujeme: x ⊥ y. Z kontextu musí být vždy jasné jaký skalární součin na prostoru Vuvažujeme.Lemma 3.2: Jsou-li nenulové vektory x1, . . . , xn ∈ V vzájemně kolmé, pak tvoří lineárněnezávislý soubor.
Důkaz. Skutečně, předpokládejme že máme nulovou lineární kombinaci daného souboruvektorů, tj. máme čísla α1, . . . , αn ∈ C taková, že
n∑k=1
αkxk = 0 .
Uvážíme-li postupně ` = 1, 2, . . . , n, pak díky vlastnostem skalárního součinu a předpo-kladu vzájemné kolmosti vektorů x1, . . . , xn platí rovnost⟨
n∑k=1
αkxk, x`
⟩=
n∑k=1
αk〈xk, x`〉 = α` 〈x`, x`〉︸ ︷︷ ︸6=0
.
Na druhou stranu ale i triviálně platí⟨n∑k=1
αkxk, x`
⟩= 〈0, x`〉 = 0.
Shrnujeme, že α` = 0 pro každé ` = 1, 2, . . . , n. Jediná nulová lineární kombinace vektorůx1, . . . , xn je právě triviální lineární kombinace. Tento soubor vektorů je proto lineárněnezávislý.
Máme-li vektorový prostor V se skalárním součinem 〈·, ·〉, pak klademe
‖x‖ ··=√〈x, x〉 . (26)
Zobrazení ‖ · ‖ : V → R nazýváme norma indukovaná skalárním součinem 〈·, ·〉 naprostoru V (viz také Definici 5.1). Norma je zobecněním Euklidovské délky vektoru v R3.Vektorovým prostorům s normou se budeme ještě podrobněji věnovat později v semestru. Vtento okamžik nám postačí pouze několik základních informací. Mezi skalárním součinema jím indukovanou normou platí následující důležitá nerovnost.
16Tento pojem samozřejmě závisí na volbě skalárního součinu! Jisté dva vektory mohou být kolmévzhledem k jednomu, ale ne vzhledem k jinému skalárnímu součinu.
40
Věta 3.3 (Schwarzova nerovnost): Pro normu ‖·‖ na vektorovém prostoru V indukovanouskalárním součinem 〈·, ·〉 platí pro každé x, y ∈ V nerovnost
|〈x, y〉| ≤ ‖x‖ ‖y‖ .
Důkaz. Uvažme x, y ∈ V a α ∈ C. Je-li x nebo y rovno nule, pak nerovnost triviálně platí.Předpokládejme dále, že obě x i y jsou nenulová. Z vlastností skalárního součinu plynenerovnost
Potom po dosazení do odvozené nerovnosti dostáváme
0 ≤ ‖x‖2 + |〈x, y〉|2 −1‖y‖2
a po elementární úpravě|〈x, y〉|2 ≤ ‖x‖2‖y‖2 .
Jakožto důsledek Schwarzovy nerovnosti si ukážeme trojúhelníkovou nerovnost pronormu indukovanou skalárním součinem.Věta 3.4 (Trojúhelníková nerovnost): Pro normu ‖ · ‖ na vektorovém prostoru V induko-vanou skalárním součinem 〈·, ·〉 platí pro každé x, y ∈ V nerovnost
Tvrzení ihned dostáváme prostým odmocněním. Ve výpočtu jsme použili vlastnosti skalár-ního součinu, nerovnost <z ≤ |z| platnou pro libovolné z ∈ C a Schwarzovu nerovnost.
Poznámka 3.5: Uveďme ještě jednu důležitou vlastnost normy indukované skalárnímsoučinem. Pro každý vektor x ∈ V a číslo λ ∈ C platí
‖λx‖ =√〈λx, λx〉 =
√|λ|2〈x, x〉 = |λ| ‖x‖.
Toto pozorování nám říká, jak se norma indukovaná skalárním součinem chová vůči šká-lování vektorů. Zanedlouho uvidíme, že tuto vlastnost použijeme při axiomatizaci pojmu„normy“ ne nutně indukované skalárním součinem.
Každý vektorový prostor má bázi. V Hilbertových prostorech, tedy v našem případěvektorových prostorech konečné dimenze se skalárním součinem, hrají důležitou roli jistétypy bází, které si teď popíšeme.
Bázi B = (b1, b2, . . . , bn) prostoru V se skalárním součinem 〈·, ·〉 nazýváme ortonor-mální, právě když pro každé `, k ∈ 1, 2, . . . , n platí
〈bk, b`〉 = δk,`.
Jinak řečeno, vektory z ortonormální báze B jsou vzájemně kolmé a navíc mají všechnyjednotkovou normu. Skutečně, 〈bk, bk〉 = ‖bk‖2 = 1, čili ‖bk‖ = 1.
Souřadnice vektoru vzhledem k ortonormální bázi lze velmi snadno17 napočítat. Z před-mětu BI-LIN víme, že každý vektor x ∈ V lze jednoznačně vyjádřit ve tvaru
x =n∑k=1
αkbk , (27)
kde αk ∈ C, k = 1, 2, . . . , n, jsou souřadnice vektoru x vzhledem k bázi B. Všimněte siovšem, že díky ortonormalitě báze B a vlastnostem skalárního součinu pro toto x platí
〈x, b`〉 =⟨
n∑k=1
αkbk, b`
⟩=
n∑k=1
αk 〈bk, b`〉︸ ︷︷ ︸δk,`
= α` ,
pro každé ` = 1, 2, . . . , n. Rozvoj (27) tedy můžeme zapsat ve tvaru
x =n∑k=1〈x, bk〉bk , (28)
a mluvíme o něm jako o Fourierově rozvoji vektoru x do ortonormální báze B. Příslušnéčíselné koeficienty nazýváme Fourierovými koeficienty vektoru x. Vektor 〈x, bk〉bk od-povídá ortogonální projekci vektoru x na jednorozměrný podprostor 〈bk〉 ≡ αbk | α ∈C, viz obrázek 9.
Mezi Fourierovými koeficienty vektoru x a jeho normou platí tzv. Parsevalova rovnost.Věta 3.6 (Parsevalova rovnost): Je-li B = (b1, . . . , bn) ortonormální báze prostoru Vvybaveného skalárním součinem 〈·, ·〉, pak pro každý vektor x ∈ V platí Parsevalovarovnost:
‖x‖2 =n∑k=1
∣∣∣〈x, bk〉∣∣∣2 , (29)
kde ‖ · ‖ je norma indukovaná skalárním součinem 〈·, ·〉.17Nemusíme se zabývat GEM!
Obrázek 9: Ilustrace k Fourierově rozvoji (27). Vektory 〈x, bi〉bi představují projekci vektorux do směru, který odpovídá vektoru bi, i = 1, 2.
Důkaz. Tvrzení stačí ověřit přímým výpočtem. Využijeme-li Fourierova rozvoje (28) a vlast-ností skalárního součinu, ihned dostáváme
‖x‖2 = 〈x, x〉 =⟨
n∑k=1〈x, bk〉bk,
n∑`=1〈x, b`〉b`
⟩=
n∑k=1
n∑`=1〈x, bk〉〈x, b`〉 〈bk, b`〉︸ ︷︷ ︸
δk,`
=
=n∑k=1
∣∣∣〈x, bk〉∣∣∣2 .Nyní si ukážeme dva příklady vektorových prostorů vybavených skalárním součinem.
Příklad 3.7: Připomeňme, že na prostoru Cn lze zavést (Euklidovský, standardní) skalárnísoučin:
〈x, y〉 ··=n∑k=1
xkyk .
Jako domácí cvičení ověřte splnění všech požadavků z definice skalárního součinu. Přísluš-nou indukovanou normou je18
‖x‖2 =√√√√ n∑k=1|xk|2 .
18Spodní index souvisí s druhou mocninou a odmocninou vyskytující se v tomto výrazu. Na Cn lzeobecně zavést normy pro každé p ≥ 1 předpisem
‖x‖p = p
√√√√ n∑k=1|xk|p .
Pouze ‖x‖2 je ale indukována (uvedeným) skalárním součinem.
43
Všimněte si, že Schwarzova nerovnost rozepsaná do sum nám dává značně netriviální tvr-zení ∣∣∣∣∣
n∑k=1
xkyk
∣∣∣∣∣ ≤√√√√ n∑k=1|xk|2 ·
√√√√ n∑k=1|yk|2 ,
platné pro libovolný vektor x ∈ Cn. Analogicky, pokud rozepíšeme trojúhelníkovou nerov-nost, pak dostáváme nerovnost√√√√ n∑
k=1|xk + yk|2 ≤
√√√√ n∑k=1|xk|2 +
√√√√ n∑k=1|yk|2 ,
platnou pro libovolné x, y ∈ Cn.Příklad 3.8: Prostor C(J) všech spojitých reálných funkcí na uzavřeném intervalu J lzevybavit skalárním součinem
〈f, g〉 ··=∫Jf(x)g(x) dx . (30)
Toto je příklad lineárního prostoru nad R nekonečné dimenze se skalárním součinem.Připomeňme, že C(J) skutečně tvoří vektorový prostor nad tělesem reálných čísel.
Algebraické operace jsou definovány standardně bodově. Z BI-ZMA také víme, že součindvou spojitých funkcí je opět spojitá funkce a součet dvou spojitých funkcí je spojitá funkce.Dále víme, že pro funkce spojité na uzavřeném intervalu J existuje jejich Riemannůvintegrál. Výraz na pravé straně rovnice (30) je tedy dobře definovaný pro libovolné dvaprvky f, g ∈ C(J).
Pojďme ověřit, že (30) skutečně zadává skalární součin. Nejprve prozkoumejme linearituv prvním argumentu,
〈αf + g, h〉 =∫J
(αf(x) + g(x)
)h(x) dx = α
∫Jf(x)h(x) dx+
∫Jg(x)h(x) dx =
= α〈f, h〉+ 〈g, h〉 , f, g ∈ C(J) , α ∈ R .
Druhý požadavek v definici skalárního součinu se v prostoru nad tělesem reálných číselredukuje na symetrii. Ta v našem případě plyne z komutativity násobení reálných čísel,
〈f, g〉 =∫Jf(x)g(x) dx =
∫Jg(x)f(x) dx = 〈g, f〉 , g, f ∈ C(J) .
Konečně pojďme ověřit třetí požadavek. Pro libovolné f ∈ C(J) platí (vzpomeňte navětu o nerovnosti mezi integrály formulovanou v BI-ZMA)
〈f, f〉 =∫Jf(x)2 dx ≥
∫J
0 dx = 0 .
Nyní musíme ověřit, že rovnost nastává skutečně pouze pro nulovou funkci. To ukážemesporem. Předpokládejme, že existuje nenulová funkce f ∈ C(J), pro niž platí
Protože je funkce f nenulová, musí existovat bod x0 takový, že f(x0)2 = c > 0. Ze spojitostifunkce f 2 ale také plyne, že pro ε = c/2 > 0 existuje δ > 0 takové, že 3c/2 > f(x)2 > c/2pro každé x ∈M ··= (x0 − δ, x0 + δ) ∩ J . Odtud dostáváme odhad
〈f, f〉 =∫Jf(x)2 dx ≥
∫Mf(x)2 dx ≥
∫M
c
2 dx ≥
≥ δ · c2 > 0 .
To je ovšem spor.Všimněte si, že výpočet koeficientů Fourierových řad zmíněných v předchozí části textu
není nic jiného než počítání jistých skalárních součinů.
3.3 Unitární matice a operátoryPro naše potřeby v další části této kapitoly bude docela stačit, vyšetříme-li základní vlast-nosti unitárních operátorů definovaných na speciálním Hilbertově prostoru komplexníchn-tic Cn vybaveným skalárním součinem
〈x, y〉 ··=n∑k=1
xkyk.
Celou teorii lze vyložit v obecném Hilbertově prostoru (téměř ve stejné podobě).Buď A ∈ Cn,n. Matici A∗ ∈ Cn,n s prvky definovanými vztahem
A∗i,j ··= Aj,i ,
pro ∀i, j ∈ n, nazýváme maticí (hermitovsky) sdruženou k matici A. Matici A∗ tedyzískáme tak, že transponujeme matici A a komplexně sdružíme („opruhujeme“) její prvky.
Následující vlastnosti sdružených matic ověřte jako cvičení (Cvičení 3.3): A,B ∈ Cn,n,x, y ∈ Cn, α ∈ C,
1. (A + αB)∗ = A∗ + αB∗,
2. (AB)∗ = B∗A∗,
3. (A∗)∗ = A, E∗ = E, kde E označuje jednotkovou matici,
4. 〈x,Ay〉 = 〈A∗x, y〉.
Pomocí hermitovského sdružení definujeme speciální třídu matic.Definice 3.9: Matici U ∈ Cn,n nazveme unitární, právě když platí U∗U = E.
Z vlastností sdružení a definice unitární matice ihned vyplývá, že unitární matice za-chovávají hodnotu skalárního součinu dvou vektorů. Přesněji, pro libovolná x, y ∈ Cn aunitární matici U ∈ Cn,n platí
〈Ux,Uy〉 = 〈U∗Ux, y〉 = 〈x, y〉. (31)
45
Poznámka 3.10: Připomeňme jedno tvrzení dokazované v předmětu BI-LIN: PokudA,B ∈ Cn,n splňují AB = E (resp. BA = E), je matice A regulární a B = A−1. Zdefinice unitární matice U proto vyplývá, že U je regulární a U−1 = U∗.
Další důležitou vlastnost, resp. charakterizaci, unitárních matic nám odhaluje následu-jící věta. Vidíme, že unitární matice vlastně hrají podobnou roli jako ortogonální matice vRn,n.Věta 3.11: Matice U ∈ Cn,n je unitární právě tehdy, když sloupce U tvoří ortonormálníbázi Cn.
Důkaz. Označme U•,i ∈ Cn i-tý sloupec matice U. Potom pro i, j ∈ n máme
〈U•,i,U•,j〉 =n∑k=1
Uk,iUk,j =n∑k=1
(U∗)j,kUk,i = (U∗U)j,i.
Tedy rovnost U∗U = E platí právě tehdy, když pro ∀i, j ∈ n je 〈U•,i,U•,j〉 = δi,j. Odtuduž plyne ekvivalence z tvrzení věty.
Na závěr této části textu obraťme naší pozornost k lineárním zobrazením, která, jakvíme, úzce souvisejí s maticemi. Definujeme unitární zobrazení a ukážeme jeho vlastnosti.Definice 3.12: Lineární zobrazení U : Cn → Cn, jehož matice U ≡ EU ve standardní báziE prostoru Cn je unitární, nazýváme unitární operátor.Věta 3.13: Buď U : Cn → Cn unitární operátor, potom U je izomorfismus na Cn aE(U−1) = U∗.
Důkaz. Z lineární algebry víme, že lineární zobrazení A : Cn → Cn je izomorfismus, právěkdyž je jeho matice XAY (v libovolných bázích X a Y) regulární. Navíc pro inverzní zob-razení A−1 platí
Y(A−1
)X=(XAY
)−1.
Unitární operátor U : Cn → Cn je proto izomorfismus, neboť unitární matice U ≡ EU jeregulární a
E(U−1) =(EU)−1
= U−1 = U∗.
3.4 DFT jako unitární operátor na CN
Na tomto místě dokážeme19 ty nejzákladnější vlastnosti DFT. Připomeňme, že nyní opětindexujeme složky vektorů z CN od nuly.
Úmluva: Nebudeme rozlišovat mezi lineárním zobrazením A : CN → CN a jeho maticíve standardní bázi EA a pro oba objekty použijeme stejné písmeno A (podobně jako provektor souřadnic (v)E stručně píšeme jen v).
Začněme tou nejzákladnější vlastností. DFT je lineární zobrazení zadané pomocí jistématice bohaté na komplexní exponenciálu.
19V podstatě jen použijeme výsledky předchozí kapitoly 3.3.
Důkaz. Nejprve dokažme linearitu. Buďte x, y ∈ CN a α ∈ C. Potom
(F (x+ αy))k = 1√N
N−1∑n=0
e−2πikn/N (x+ αy)n︸ ︷︷ ︸xn+αyn
= 1√N
N−1∑n=0
e−2πikn/Nxn + α1√N
N−1∑n=0
e−2πikn/Nyn = (Fx)k + α(Fy)k
pro ∀k ∈ 0, 1, . . . , N − 1. Dále pro j, k ∈ 0, 1, . . . , N − 1 máme
Fk,j = (F ej)k = 1√N
N−1∑n=0
δjne−2πikn/N = 1√
Ne−2πijk/N .
Matice, která zadává DFT, v předchozí větě je ale dokonce unitární. To má pro DFTzávažné důsledky shrnuté v následující větě.Věta 3.15: DFT F : CN → CN je izomorfismus na CN . Pro inverzi F platí F−1 = F ∗,nebo-li
(F−1x)k = 1√N
N−1∑k=0
xke2πink/N , x ∈ CN .
Důkaz. Stačí ověřit, že matice F uvedená ve větě 3.14 je unitární, tedy že platí F ∗F = E.Tvrzení potom vyplývá z Věty 3.13.
Skutečně, pro j, k ∈ 0, 1, . . . , N − 1 máme20
(F ∗F )j,k = 1N
N−1∑n=0
e2πijn/Ne−2πikn/N = 1N
N−1∑n=0
(e2πi(j−k)/N
)n=
1−e2πi(j−k)
N(1−e2πi(j−k)/N ) , j 6= k,
1, j = k.
Nyní si stačí uvědomit, že pro libovolné m ∈ Z je e2πim = cos(2πm) + i sin(2πm) = 1.Proto je pro j 6= k
1− e2πi(j−k)
N(1− e2πi(j−k)/N) = 0
a my celkem dostáváme (F ∗F )j,k = δjk.20V posledním kroku jsme použili známý vzorec pro součet prvních několika členů geometrické posloup-
nosti s kvocientem e2πi(j−k)/N a prvním členem 1.
47
Poznámka 3.16: Podívejme se ještě na jednu interpretaci DFT. Označme fj j-tý sloupecmatice F ∗, tedy (fj)k ≡ F ∗
k,j = 1√Ne2πijk/N . Protože je F ∗ unitární, je soubor F =
(f0, f1, . . . , fN−1) ortonormální báze CN . Pro k-tou souřadnici vektoru Fx (ve standardníbázi) máme
(Fx)k = 〈Fx, ek〉 = 〈x,F ∗ek〉 = 〈x, fk〉,
neboli Fx = (x)F . Vidíme tedy, že složky DFT vektoru x jsou souřadnice vektoru x vespeciálně volené bázi F !
V teorii signálu se zavádí mnoho různých charakteristik vzorku x ∈ CN . Jedním z nichje jeho energie, která není nic jiného než norma x, tedy
‖x‖2 =
√√√√N−1∑n=0|xn|2 .
Veledůležitou vlastností DFT je, že zachovává celkovou energii. Přesněji platí následujícívěta.Věta 3.17 (Plancherelova a Parsevalova rovnost): Pro libovolné x, y ∈ CN platí Plan-cherelova rovnost
〈x, y〉 = 〈x, y〉
a speciálně Parsevalova rovnost
‖x‖2 = ‖x‖2 .
Důkaz. Stačí dosadit za unitární matici U do rovnosti (31) matici DFT F . Proč se druhérovnosti říká Parsevalova je patrné z předchozí Poznámky.
Na závěr této části zformulujeme jednoduché tvrzení popisující, jak se DFT vektorux ∈ CN chová vzhledem ke komplexnímu sdružení.Lemma 3.18: Pro každé k = 0, 1, 2, . . . , N − 1 platí
(Fx)k = (Fx)N−k ,
kde pro k = 0 na pravé straně klademe (Fx)N := (Fx)0. Speciálně proto pro reálný vektorx ∈ RN platí
(Fx)k = (Fx)N−k .
Důkaz. Skutečně, tvrzení lze přímo ověřit následujícím výpočtem
(Fx)k = 1√N
N−1∑n=0
xne−2πink/N = 1√N
N−1∑n=0
xne2πink/N =
= 1√N
N−1∑n=0
xne−2πin(N−k)/N = (Fx)N−k .
48
3.5 DFT a konvoluceK zjednodušení následujícího výkladu je výhodné periodicky prodloužit vektory z na-šeho prostoru CN . Jinak řečeno, ztotožníme vektorový prostor CN s vektorovým prostoremoboustranně nekonečných komplexních posloupností (xk)∞k=−∞ periodických s periodou N ,
xk+mN = xk , ∀m ∈ Z .
Tedy index v xk lze chápat jako modulo N , tj. xk = xk mod N .Rozšíříme si definici DFT i na vektory z periodicky prodlouženého prostoru CN . Uvi-
díme, že vektor Fx lze opět chápat jako periodickou posloupnost s periodou N a tedyprvek (nově chápaného) prostoru CN . Buď k ∈ Z a označme ` zbytek k po dělení N . Tzn.,že ` ∈ 0, . . . , N − 1 a k = `+mN pro nějaké m ∈ Z. Rozšíříme-li definici DFT použitímstejného vzorečku (25), dostaneme
xk = 1√N
N−1∑n=0
xne−2πink/N = 1√
N
N−1∑n=0
xne−2πin(`+mN)/N =
= 1√N
N−1∑n=0
xne−2πin`/N e−2πinm︸ ︷︷ ︸
=1
= x` .
Tedy skutečněx`+mN = x` .
Této vlastnosti se často říká periodicita DFT.Chápeme-li vektor x jako oboustranně nekonečnou komplexní posloupnost periodickou
s periodou N , můžeme k výpočtu DFT vektoru x sčítat přes libovolnou periodu délky N .Přesněji
xk = 1√N
N−1∑n=0
xne−2πink/N = 1√
N
`+N−1∑n=`
xne−2πink/N (32)
pro libovolné ` ∈ Z. Tento pohled je konzistentní s naším zjištěním, že xk je periodické vk s periodou N . Navíc analogický trik jsme uplatňovali i v kontextu funkcí a Fourierovýchřad.
Pro dva vektory x, y ∈ CN definujeme jejich konvoluci (propletení) jako nový vektorx ∗ y ∈ CN se složkami
(x ∗ y)k ··=N−1∑n=0
xnyk−n , k ∈ Z . (33)
Nejprve ověřme, že vektor x ∗ y lze skutečně chápat jako prvek CN , tj. jeho periodicitu speriodou N ve spodním indexu:
(x ∗ y)k+N =N−1∑n=0
xn yk+N−n︸ ︷︷ ︸=yk−n
= (x ∗ y)k , k ∈ Z .
49
Lemma 3.19: Konvoluce je binární operace ∗ : CN ×CN → CN , která je lineární v obousvých argumentech, platí
(x+ αy) ∗ z = x ∗ z + αy ∗ z a x ∗ (y + αz) = x ∗ y + αx ∗ z,
pro každé x, y, z ∈ CN a α ∈ C. Konvoluce je komutativní operace. Pro libovolné x, y ∈ CN
platíx ∗ y = y ∗ x .
Důkaz. Nejprve dokažme komutativitu. Stačí provést záměnu sčítacího indexu:
(x ∗ y)k =N−1∑n=0
xnyk−n =k∑
m=k−N+1xk−mym =
N−1∑m=0
ymxk−m = (y ∗ x)k ,
kde jsme od sčítacího indexu n ∈ 0, 1, . . . , N − 1 přešli k novému sčítacímu indexum = k − n ∈ k, k − 1, . . . , k − N + 1, tedy n = k −m. Nakonec jsme vhodně posunulisčítací obor, neboť posloupnost v sumě je opět periodická s periodou N .
Dále stačí dokázat linearitu třeba v prvním argumentu (v druhém už plyne z komuta-tivity). Pro libovolná x, y, z ∈ CN a α ∈ C platí(
(x+ αy) ∗ z)k
=N−1∑n=0
(x+ αy)nzk−n =N−1∑n=0
xnzk−n + αN−1∑n=0
ynzk−n = x ∗ z + αy ∗ z .
Věta 3.20: Fourierova transformace převádí konvoluci na součin. Pro libovolné x, y ∈ CN
platí:F (x ∗ y) =
√N(x · y) .
Pozor, zde tečka není skalární součin, ale obyčejný součin po složkách,
(x · y)k ··= xkyk ,
jehož výsledkem je vektor. Tečku je zde nutné chápat jako vektorovou binární operaci navektorech, · : CN × CN → CN .
Důkaz. Tvrzení ověříme přímým výpočtem. Pro k = 0, 1, . . . , N − 1 platí
(F (x ∗ y))k = 1√N
N−1∑n=0
(x ∗ y)ne−2πink/N = 1√N
N−1∑n=0
(N−1∑`=0
x`yn−`
)e−2πink/N =
= 1√N
N−1∑`=0
x`
(N−1∑n=0
yn−`e−2πi(n−`)k/N
)︸ ︷︷ ︸
=√Nyk
e−2πi`k/N = ykN−1∑`=0
x`e−2πi`k/N
︸ ︷︷ ︸√Nxk
=
=√Nxkyk .
Díky předchozí větě proto platí, že pro výpočet konvoluce můžeme použít veledůležitývzorec
x ∗ y =√NF−1(x · y) .
Jak uvidíme níže, DFT můžeme efektivně počítat pomocí FFT. Díky tomu lze pak efektivněpočítat i konvoluci!
50
3.6 Poznámky a odkazyLátka probraná v první části této kapitoly (tedy částí 3.1, 3.2 a 3.3) představují poměrněstandardní úvod do základní geometrie pre-Hilbertových prostorů (tj. bez zkoumání úpl-nosti) a lze je nalézt ve většině textů pojednávajících o Lineární algebře.
Druhá část kapitoly týkající se DFT lze chápat jako aplikaci výše abstraktní látky uve-dené v předchozím odstavci. Dopodrobna tato látka nebývá v základních kurzech Lineárníalgebry probírána. Na DFT lze ale často narazit v samostatných předmětech zabývajícíchse jejími inženýrskými aplikacemi ve zprazování a analýze signálu.
3.7 CvičeníCvičení 3.1: Dokažte zobecněnou Pythagorovu větu: je-li V vektorový prostor vybavenýskalárním součinem 〈·, ·〉 a x, y dva kolmé vektory (vzhledem k uvedenému skalárnímusoučinu), pak platí pro indukovanou normu platí
‖x‖2 + ‖y‖2 = ‖x+ y‖2.
Často je potřeba umět přecházet od „obyčejné“ báze k ortonormální bázi. Jeden zmožných přístupů jak toho lze docílit ukazuje následující cvičení.Cvičení 3.2 (Gramm–Schmidtův ortonormalizační proces): Uvažme vektorový prostor Vse skalárním součinem 〈·, ·〉 a lineárně nezávislý soubor vektorů (x1, . . . , xk). Ukažte, žeexistuje ortonormální soubor (y1, . . . , yk) mající stejný lineární obal jako původní soubor.Nápověda: Postupujte induktivně. Vektor y1 bude jistě pouze normalizovaný vektor x1.Vektor y2 hledejte jako lineární kombinaci vektorů x1 a x2 kolmou na y1, atd.
Řešení. Nejdřív poznamenejme, že pro libovolný nenulový x ∈ V platí∥∥∥∥∥ x
‖x‖
∥∥∥∥∥ =
√√√√⟨ x
‖x‖,x
‖x‖
⟩=√
1‖x‖2 〈x, x〉 =
√√√√〈x, x〉〈x, x〉
= 1.
To znamená, že v zadání zmíněné normalizace se dá dosáhnout pouhým vydělením vektorujeho normou. Tím pádem máme-li ortogonální soubor (z1, . . . , zk), mající stejný lineárníobal jako (x1, . . . , xk), pak hledaným ortonormálním souborem je soubor (y1, . . . , yk) =( z1‖z1‖ , . . . ,
zk‖zk‖
). Ukážeme, že takový (z1, . . . , zk) existuje.Položme z1 = x1 a další zn (tj. n = 2, 3, . . . , k) získáme induktivně jako lineární kom-
binaci vektorů x1, . . . , xn kolmou na z1, . . . , zn−1. Tedy musí platit
∃αi, . . . , αn ∈ C : zn =n∑i=1
αixi
a zároveň〈zn, z1〉 = · · · = 〈zn, zn−1〉 = 0,
51
což vede na homogenní soustavu rovnicn∑i=1
αi〈xi, zj〉 = 0
∣∣∣∣∣∣ j ∈ 1, . . . , n− 1
,nebot’
〈zn, zj〉 =⟨
n∑i=1
αixi, zj
⟩=
n∑i=1
αi〈xi, zj〉.
V každém indukčním kroku taková soustava v maticovém tvaru má n proměnných amá plnou hodnost rovnou n − 1, a tudíž podle Frobeniovy věty má i netriviální řešení.Z toho plyne, že nenulové vektory z1, . . . , zk existují. Každý z těchto vektoru je line-ární kombinací vektorů x1 . . . , xn, což implikuje 〈z1, . . . , zk〉 ⊂⊂ 〈x1, . . . , xk〉. Na druhoustranu je (z1, . . . , zk) ortogonální soubor nenulových vektorů a podle lemmatu dokázanéhona začátku kapitoly je i lineárně nezavislý a generuje tedy prostor stejné dimenze jako(x1, . . . , xk). To je samozřejmě možné pouze v případě, že (z1, . . . , zk) generuje právě celý〈x1, . . . , xk〉21. Tím je dokázáno, že hledaný soubor (z1, . . . , zk) existuje.
Cvičení 3.3: Dokažte vlastnosti hermitovského sdružení matice. Pro A,B ∈ Cn,n a α ∈ Cplatí rovnosti
(A + αB)∗ = A∗ + αB∗, (AB)∗ = B∗A∗,(A∗)∗ = A, 〈x,Ay〉 = 〈A∗x, y〉, x, y ∈ Cn,
a uvažujeme standardní skalární součin.Následující dvě cvičení ukazují zajímavou paralelu mezi operacemi hermitovského sdru-
žení matic a komplexním sdržením komplexních čísel.Cvičení 3.4: Ukažte, že všechna vlastní čísla zadané unitární matice U ∈ Cn,n leží najednotkové kružnici v C. Podrobněji, je-li λ vlastní číslo unitární matice U, pak |λ| =1. Poznámka: Toto pozorování lze chápat jako vysvětlení volby jména „unitární“ (českybychom asi řekli jednotková, ale to už znamená něco jiného) matice. Nápověda: Využijterovnost (31) a vhodný vektor.
Řešení. Je-li λ vlastní číslo unitární matice U, pak k němu existuje přislušný vlastní vektorx 6= 0. Podle rovnosti (31) a definice vlastního čísla platí
Cvičení 3.5: Další zajímavou a důležitou třídou matic jsou tzv. hermitovské matice.Zvídavý čtenář by se s nimi mohl setkat například v teorii Kvantového počítání. MaticiA ∈ Cn nazýváme hermitovskou, právě když A∗ = A.
Dokažte, že spektrum každé hermitovské matice je podmnožinou reálné osy (tj. každévlastní číslo hermitovské matice je reálné). Nápověda: Využijte výsledky Cvičení 3.3.
Řešení. Nechť λ je libovolné vlastní číslo matice A. Dle definice tedy platí
∃x ∈ Cn,n, x 6= θ : Ax = λx.
Jelikož A = A∗, pro stejný vektor x platí i vztah
A∗x = λx.
Nyní využijeme skalárního součinu.
〈Ax, x〉 = 〈λx, x〉 = λ〈x, x〉.
Díky čtvrtému vztahu Cvičení 3.3 platí i
〈Ax, x〉 = 〈x,A∗x〉 = 〈x, λx〉 = λ〈x, x〉.
Zjistili jsme, že λ〈x, x〉 = λ〈x, x〉, a díky nenulovosti x tedy platí i λ = λ. Aby tato rovnostplatila, λ musí být reálné číslo.
Cvičení 3.6: Dokažte následující vlastnosti diskrétní Fourierovy transformace,
i. obrácení času (time reversal): (Fx)−k = (F−1x)k,
ii. posun času (time shift): (FTk0x)k = e−2πikk0/N(Fx)k, kde (Tk0x)k = xk−k0 .
pro každé x ∈ CN
Řešení. Pro důkaz vlastnosti time reversal využijeme definici DFT a Větu 3.15.
(Fx)−k def.= 1√N
N−1∑n=0
xne−2πi(−k)n/N = 1√
N
N−1∑n=0
xne2πikn/N 3.15= (F−1x)k.
Nyní dokážeme vlastnost time shift. K tomu kromě definic budeme potřebovat rovnost (32),
(FTk0x)k def.= 1√N
N−1∑n=0
(Tk0x)ne−2πikn/N = 1√N
N−1∑n=0
xn−k0e−2πikn/N
= 1√N
N−1−k0∑n=−k0
xne−2πik(n+k0)/N = 1√
N
N−1−k0∑n=−k0
xne−2πikn/Ne−2πikk0/N
= e−2πikk0/N · 1√N
N−1−k0∑n=−k0
xne−2πikn/N (32)= e−2πikk0/N(Fx)k.
53
Cvičení 3.7: Nalezněte kandidáty na vlastní čísla diskrétní Fourierovy transformace ja-kožto linárního operátoru na CN , N ∈ N, N ≥ 4. Nápověda: Nelze nalézt nějaké n ∈ N∗pro které je F n identita? Co to pak znamená pro případná vlastní čísla?
Řešení. Podívejme se, jak bude vypadat matice F 2. Z důvodu přehlednosti a v souladu spředchozím výkladem budeme řádky i sloupce matice F číslovat od 0 do N − 1.
F 2m,n =
N−1∑k=0
Fmk ·Fkn =
=N−1∑k=0
1√Ne−mk2πi/N · 1√
Ne−kn2πi/N =
= 1N
N−1∑k=0
e−k2πi(m+n)/N ,
kde číslo m+ n je z množiny 0, 1, . . . , 2N − 2.Pokud m = n = 0, pak
F 20,0 = 1
N
N−1∑k=0
e−k2πi(0)/N = 1N
N−1∑k=0
e0 = 1.
Pokud m+ n = N , pak
F 2m,n = 1
N
N−1∑k=0
e−k2πi(N)/N = 1N
N−1∑k=0
e−k2πi = 1N
N−1∑k=0
1 = 1.
Jinak si uvědomme, že čísla e−k2πi(m+n)/N jsou v komplexní rovině body na jednotkovékružnici se středem v bodě 0 a výraz F 2
m,n představuje jejich průměrnou hodnotu. Tytobody rovnoměrně rozdělují úhel (m + n) · 2π na N segmentů o úhlu (m+n)·2π
N. Můžeme na
ně nahlížet jako na vrcholy nějakého pravidelného mnohoůhelníku (nebo úsečky, pokudm + n = N/2), vepsaného do jednotkové kružnice. Průměrná hodnota těchto čísel pakodpovídá těžišti tohoto mnohoúhelníku, které se rovná středu jeho opsané kružnice, vtomto případe 0. (Alternativně by šlo opět sečíst odpovídající sumu a využít vzorec prosoučet geometrické posloupnosti.)
Celkově tedy:
F 2m,n =
1, pokud (m+ n) ≡ 0 mod N,
0, jinak.Tato matice má první řádek a sloupec shodný s jednotkovou maticí a zbytek má tvarhorizontálně překlopené jednotkové matice. Její aplikací na vektor x ∈ CN , dostanemevektor, který zachovává svojí první složku a ostatní složky má v obráceném pořadí, tedy
F 2 ·
x0x1x2...
xN−1
=
x0xN−1xN−2...x1
.
54
Druhá mocnina matice F 2 je pak triviálně rovna jednotkové matici a tedy F 4 = E. Pokudx je vlastní vektor operátoru F a λ jemu odpovídající vlastní číslo, z definice vlastníhočísla je Fx = λx a opakovaným aplikováním F dostaneme F 4x = λ4x. Protože zobrazeníF 4 je identita, musí platit λ4x = x a nutně λ4 = 1 pro všechny vlastní čísla λ operátoruF . Vyřešením této rovnice dostáváme 4 možné hodnoty vlastních čísel matice F :
λ ∈ 1,−1, i,−i.
Poznámka: Lze ukázat, že tato uvedená množina skutečně tvoří spektrum DFT. Argumen-tace je však nad rámec tohoto kurzu. V současnosti se znají i násobnosti těchto vlastníchhodnot v závislosti na N . Otázka vlastních vektorů není doposud zcela uspokojivě vyře-šena.
ii. x = (1,−1, 1,−1, . . . , 1,−1) ∈ CN pro sudé N ,
iii. x = (0, . . . , 1, . . . , 0) ∈ CN , kde 1 je právě v jté složce a ostatní jsou nulové.
Řešení. i. Dosadíme do Definice 3.1 (všechny xn jsou rovny 1). k-tý prvek výslednéhovektoru je pak
xk = 1√N
N−1∑n=0
e−2πikn/N
Povšimněme si, že suma v tomto výrazu se dá sečíst pomocí vzorečku pro částečnésoučty geometrické posloupnosti. První člen a1 je roven 1 (kvůli n = 0 v exponentu) akvocient je q = e−2πik/N . Vzoreček
sN = a1qN − 1q − 1
lze použít v případě že q 6= 1. Pokud q = 1 pak je součet prostě N · a1. Náš kvocientje triviálně roven 1 pouze pro k = 0. Jinak by mohl být roven jedné pouze pokud byexponent nad e byl celočíselným (nenulovým) násobkem 2πi, to se ale stát nemůže,protože index k běží od 0 do N − 1 a nikdy se tedy nezkrátí se jmenovatelem N . Prok = 0 tedy máme
x0 = 1√N·N · a1
a po zjednodušeníx0 =
√N.
Pro k 6= 0 (a tedy q 6= 1) použijeme výše uvedený vzoreček a dostáváme
xk = 1√N· (e−2πik/N)N − 1
e−2πik/N − 1 = 1√N· e−2πik − 1e−2πik/N − 1 = 1√
N· 1− 1e−2πik/N − 1 = 0.
55
Výsledný vektor má tedy podobu
x = (√N, 0, 0, . . . , 0) ∈ CN .
ii. Po dosazení zadaných hodnot vektoru do definice 3.1 dostáváme výraz
xk = 1√N
N−1∑n=0
(−1)ne−2πikn/N = 1√N
N−1∑n=0
(−(e−2πik/N))n.
Suma ve výrazu opět odpovídá částečnému součtu geometrické posloupnosti s prvnímčlenem rovným 1. Kvocient má hodnotu q = −(e−2πik/N). Vyřešíme nejprve situaci,kdy q = 1:
q = 1⇔ e−2πik/N = −1⇔ −2πikN
= (2l + 1)πi, l ∈ Z
(e je umocněno na lichý násobek πi). Získaný výraz upravíme
k = −(2l + 1)πiN2πi = −(2l + 1)N2
a zjistili jsme, že aby byl kvocient roven 1, musí k být lichý násobek N/2 – to je ale vdaném rozsahu hodnot možné pouze pokud k = N/2. Tím pádem
xN/2 = N√N.
Pro ostatní členy výsledného vektoru (k 6= N/2) můžeme opět použít již zmíněnývzoreček a dostáváme
xk = 1√N
(−(e−2πik/N))N − 1−(e−2πik/N)− 1 .
Zdálo by se, že tento výraz se od prvního příkladu liší pouze znaménkem kvocientu. Včitateli je ale kvocient umocněn na sudou mocninu a tím pádem dostáváme v čitateliúplně stejný výraz jako v prvním příkladu. Celý výraz je tedy roven 0. Výsledný vektorje pak
x =(0, 0, . . . , N√
N, . . . , 0, 0
)∈ CN ,
kde právě na pozici N2 je výraz N√N
a ostatní jsou nulové.
iii. Vzhledem k tomu, že xn = 0 pro všechny n 6= j zbude nám ze sumy v definici vždypouze jediný sčítanec – ten kde n = j. Dostáváme tedy výraz
Cvičení 3.9: Explicitně vypočtěte konvoluci následujících dvojic vektorů z CN .
i. x = y = (1, 1, . . . , 1),
ii. x = (δ1,k)N−1k=0 , y = (δN−1,k)N−1
k=0 ,
iii. x = (1, 0, . . . , 0), y = (1, 1, . . . , 1).
Řešení. i. Nacházíme se na periodicky prodlouženém prostoru CN . Po dosazení do Defi-nice 33 tedy dostáváme výraz
(x ∗ y)k =N−1∑n=0
1 · 1 = N
a výsledný vektor má podobu
x ∗ y = (N,N, . . . , N) ∈ CN .
ii. Vzhledem k tomu, že xn je rovno 0 pro n 6= 1 a x1 = 1 zůstane nám pro každý členvýsledného vektoru pouze
(x ∗ y)k = yk−1.
Tento výraz je ale roven 0 pro všechny k kromě k = 0 + lN, l ∈ Z (pro které je roven1). Výsledný vektor má tedy podobu
x ∗ y = (1, 0, . . . , 0, 0) ∈ CN .
iii. xn je rovno 0 pro n 6= 0 a x0 = 1. Opět nám tedy zůtává pouze jeden sčítanec prokaždý člen vektoru a to
(x ∗ y)k = yk.
yk je ale vždy rovno 1 a výsledný vektor je tím pádem
x ∗ y = (1, 1, . . . , 1, 1) ∈ CN .
4 Rychlá Fourierova transformace (FFT)The best thing about being a statistician is that you get to play in everyone’sbackyard. John Tukey
Nyní se zabývejme otázkou, jak zrychlit výpočet DFT. Složitost naivního způsobu výpočtuDFT, viz např. vzorec (25), je O(N2), kde N je délka vstupu. V následujícím odstavci sipředstavíme speciální případ metody výpočtu DFT se složitostíO(N logN) proN mocninudvou pocházející z článku Cooleyho a Tukeyho [5] z roku 1965. Základní myšlenka algoritmuje metoda “rozděl a panuj”, která se v souvislosti s DFT objevila už v článku Danielsona aLanczose z roku 1942 [6]. O DFT počítané metodou s lepší složitostí než O(N2) se mluvíjako o rychlé Fourierově transformaci (FFT).
57
4.1 Cooleyho-Tukeyho algoritmusPro účely této části textu označme
wN ··= e−2πi/N , N ∈ N .
Všimněte si, že wN je řešení komplexní rovnice zN = 1 s nejmenším kladným argumentem22,z toho důvodu se wN také často nazývá primitivní kořen jedničky. Platí pro něj wNN = 1.
DFT vektoru x ∈ CN definovanou rovnicí (25) pak lze zapsat zkráceně ve tvaru
xk = 1√N
N−1∑n=0
xnwnkN .
Pro účely tohoto odstavce vypusťme multiplikativní faktor 1√N
v předpisu pro DFT.Pozor, je pak nutné vhodně upravit i vztahy pro inverzi, nebo Parsevalovu rovnost. Položmetedy
(Fx)k =N−1∑n=0
xnwnkN , x ∈ CN . (34)
Tato volba je častá a setkáte se s ní v řadě implementací. Na vlastnostech DFT praktickynic nemění, jen je třeba některé vzorce modifikovat právě o faktor
√N . Například platí
(F−1x
)k
= 1N
N−1∑n=0
xnw−nkN , x ∈ CN .
V následujícím textu budeme o F i o F mluvit jako diskrétní Fourierově transformaci.Předpokládejme, že N je sudé. Potom lze součet v (34) rozdělit na součet přes liché a
22Argument nenulového komplexního čísla z je úhel v (−π, π], který svírá vektor spojující 0 a z s kladnýmsměrem reálné osy.
58
Stručně řečeno, pro sudé N zobrazení E (resp. O) z vektoru x ∈ CN extrahuje pouzesložky se sudým (resp. lichým) indexem. Výše odvozený vztah (35) pro DFT pak můžemezkráceně zapsat ve tvaru
(Fx)k = (FEx)k + wkN(FOx)k , k = 0, 1, 2, . . . , N − 1 . (36)
Podstatné v předchozím vztahu je, že DFT na pravé straně se již provádějí na vektorechpoloviční délky, než s kterou jsme začali. Tento proces se v kontextu zpracování signálunazývá decimace v čase. Zdůrazněme také, že ačkoliv vektor FOx má poloviční délku nežx, chápeme ho opět jako oboustranně nekonečný a (FOx)k má dobrý smysl dokonce provšechna k ∈ Z.
Předpokládejme, že prvotní N je mocninou dvou, N = 2K , K ∈ N. Provedeme-lioperaci (36) rekurentně K−1 krát, pak skončíme s nutností výpočtu DFT vektorů délky2, což je velmi snadné. Pro zadané N je těchto dělení (decimací) potřeba provést přibližnělogN . V každé fázi je nutno provést přibližně N operací. Celková složitost výpočtu jetedy O(N logN). Tento rekurentní výpočet DFT se nazývá rychlá Fourierova transformace(FFT) a jde o speciální případ Cooley-Tukeyho algoritmu pro N mocninu dvou. Existujívarianty tohoto algoritmu aplikovatelné i na jiná složená čísla N , než jen mocninu dvou.
Zcela stejným způsobem jako v předchozím textu bychom odvodili podobný vztah proinverzní DFT, přesněji
(F−1x)k =(F−1Ex
)k
+ wNk(F−1Ox
)k, k = 0, 1, 2, . . . , N − 1 . (37)
Inverzní DFT lze tedy také počítat tímto způsobem.K přednášce od DFT, resp. FFT, je jako doplněk připraven IPython (nově Jupyter)
notebook s ukázkami použití FFT v jazyce Julia. Navíc je zde porovnáváme různé metodyvýpočtu DFT (naivní dle definice, rekurentní implementace výše popsaného algoritmu aimplementace z knihovny FFTW). Tabulka 1 ilustruje propastné rozdíly v časové délcevýpočtu DFT v závislosti na délce vstupu.
4.2 Frekvenční spektrum audiosignálu (spektrogram)Připomeňme jeden z možných významů Fourierovy transformace. Vzorec pro inverzní Fou-rierovu transformaci signálu x ∈ CN s vzorkovací frekvencí f = 1/∆ a celkovou délkouT = N∆ dle věty 3.15 zní
xk = 1√N
N−1∑n=0
xne2πikn/N .
Původní signál je zde tedy vyjádřen jako superpozice (lineární kombinace) harmonic-kých oscilací s frekvencemi fn = n/T (resp. úhlovými frekvencemi ωn = 2πn/T ), n =0, 1, . . . , N − 1. Koeficienty xn pak udávají, jakou mírou harmonická oscilace s frekvencífn přispívá do celkového signálu x. Touto mírou může být například kvadrát absolutníhodnoty n-té složky Fourierovy transformace, tj. velikost
Tabulka 1: Porovnání časové délky (v sekundách) výpočtu DFT pomocí naivní imple-mentace (25), FFT pomocí rekurze (36) a FFT z knihovny FFTW. Implementace bylaprovedena v jazyce Julia, výpočet na stroji s procesorem Intel Core i3-3227U 1.90GHz. Noznačuje délku vstupního vektoru.
Nyní si ukážeme, jak výše popsané informace využít k analýze frekvenčního spektrazvukového záznamu. Předpokládejme, že máme k dispozici záznam x ∈ RN se vzorkovacífrekvencí f = 1
∆ (typicky např. f = 44 100 Hz). Abychom získali informaci o harmonickýchsložkách zvuku v jistém okamžiku, rozdělíme si záznam na (nejlépe překrývající se) úseky oNw vzorcích. Tyto krátké úseky se často nazývají okna (window). Volba délky tohoto oknazávisí na konkrétní aplikaci, například při analýze záznamu řeči se používá délka okolo25 ms.
Nechť y ∈ RNw je jedno z oken. Před aplikací FFT je vhodné tento záznam přenásobittzv. okénkovou funkcí (window function). Častou volbou je Hannova funkce
Její graf je vynesen na obrázku 10. Tato úprava má za následek potlačení některých ne-žádoucích efektů způsobených diskretizací signálu, dojde k potlačení signálu na okrajíchokna. V praxi lze narazit i na jiné volby „okénkových“ funkcí. FFT poté aplikujeme nasoučin (po složkách) y ·H.
Z Fourierovy transformace y ·H pak vyčteme frekvence obsažené v signálu v oka-mžiku odpovídajícímu vybranému oknu y. Složky
(y ·H
)n
pak odpovídají frekvencímfn = n/(∆Nw).
Než začneme spektrogramy vykreslovat, je dobré si připomenout Lemma 3.18. Protožechápeme nyní prvky prostoru CN jako periodicky prodloužené, můžeme znění Lemmatupřeformulovat takto: pro x ∈ RN platí
(Fx)k = (Fx)−k . (39)
Důsledkem tohoto pozorování je, že z Fourierovy transformace daného okna vyčteme
frekvence do maximálně (Nw/2)/(∆Nw) = 1/(2∆). Tedy do poloviny vzorkovací frekvence.Všimněte si ale, že čím je delší délka okna, tím máme jemnější frekvenční rozlišení.
Na obrázku 11 je zobrazen spektrogram harmonické sinusové oscilace s frekvencí 329.63 Hzvzorkované s frekvencí f = 44 100 Hz. Na vodorovné ose je vynesen čas a na svislé frek-vence. Bod v grafu pak v odstínech šedi zobrazuje kvadrát absolutní hodnoty Fourierovakoeficientu transformace příslušného okénka a frekvence.
Na obrázku 12 uvádíme zajímavější příklad analýzy záznamu zvuku houslí. Dále naobrázku 13 může prozkoumat spektrogram zvuk šesti prázdných kytarových strun. Všechnyuvedené obrázky a způsob jejich výpočtu lze prozkoumat ve zmíněném IPython notebooku.
61
Spektrogram
0
100
200
300
400
Frekven
ce [
Hz]
0 0.5 1 1.5 2 2.5 3Čas [s]
Obrázek 11: Očekávané frekvenční spektrum harmonické oscilace. Záznam představuje sig-nál tvaru funkce sin s frekvencí 329.63 Hz dlouhý jednu sekund a vzorkovaný s frekvencí44 100 Hz.
62
violin.wav
−0.2
−0.1
0
0.1
0.2
Am
plit
uda
0 1 2 3Čas [s]
Spektrogram: violin.wav
0
1000
2000
3000
4000
5000
Frekven
ce [
Hz]
0 0.5 1 1.5 2 2.5 3 3.5Čas [s]
Obrázek 12: Frekvenční spektrum tónu houslí. Použitý WAV je vzorkovaný s frekvencí44 100 Hz, na každý vzorek připadá 16 bitů. Hráč rozeznívá jeden tón na struně. Všimnětesi, že vyjma základní frekvence se ve spektru objevují i její vyšší násobky.
63
Kytara, prázdné struny
0
500
1000
1500
2000
Frekven
ce [
Hz]
0 1 2 3 4 5 6Čas [s]
Obrázek 13: Spektrum postupně zahraných prázdných strun na kytaře.
64
4.3 Aplikace konvoluce: Gaussovské vyhlazováníPředstavuje-li x ∈ CN vstupní signál, pak pod konvolučním filtrem máme na mysli trans-formaci
K : x 7→ K ∗ x , K : CN → CN ,
kde K ∈ CN je pevně zvolené tzv. konvoluční jádro (kernel). Různé volby jádra dávajírůzné filtry, schopné plnit různé úkoly. Ukážeme si volbu jádra vhodného pro vyhlazo-vání/rozmazávání a jádro vhodné pro detekci hran. Poznamenejme, že konvoluční filtrprakticky implementujeme pomocí rychlé Fourierovy transformace (jinak by byl velmi po-malý)
Kx =√NF−1(K · x) ,
kde tečka označuje násobení po složkách.Kdybychom zkoumali spojitý signál, pak bychom pro každé kladné σ > 0 volili jádro
hσ(x) = 1√2πσ
e−x2/(2σ2) . (40)
Grafy této funkce pro různé volby parametru σ jsou vyneseny na obrázku 14. Koeficientyjsou zvoleny tak, že pro každou hodnotu σ > 0 je plocha pod grafem funkce hσ rovnajedné, tedy ∫ ∞
−∞hσ(x) dx = 1 . (41)
Pomocí Gaussiánu (40) definujeme Gaussovo jádro. Je-li x ∈ CN vstupní signál a N jesudé, pak klademe
Nezapomeňte, že v indexy chápeme modulo N . Konstanta cσ je volena tak, aby (diskrétníanalogie (41))
N−1∑k=0
Kσ,k = 1 .
Pokud bychom aplikovali tento filtr s tímto Gaussovskýcm jádrem na vstupní signál,získali bychom vyhlazenou verzi signálu na výstupu. Volba σ pak kontroluje citlivost filtru.Čím menší je σ, tím citlivější je filtr.
Ukažme si jedno možné a zajímavé použití konvolučního filtru v grafice. Každý zdigi-talizovaný obrázek lze chápat jako matici pixelů, jejíž prvky označují barvu příslušnéhopixelu (ta může být udána třemi čísly (RGB), nebo třeba jedním číslem popisujícím odstínšedi, jak je tomu v našem příkladě). Pro zvolené σ pak můžeme aplikovat výše zmíněnýkonvoluční filtr na řádky a poté na sloupce matice. Tím získáme Gaussovsky rozmazanouverzi vstupního obrázku. Všimněte si, že tuto operaci lze i snadno paralelizovat a tedy ještědále významně urychlit. Ukázka takovéhoto rozmazávání je na obrázku 15.
65
x
hσ
Obrázek 14: Graf funkce (40) pro hodnoty σ rovné 2 (zelená), 1 (červená), 1/2 (černá), 1/4(hnědá) a 1/10 (modrá).
66
Obrázek 15: Gaussovské rozmazávání Johanna Carla Friedricha Gausse (levý horní), apli-kace konvolučního filtru po řádcích (pravý horní), po sloupcích (levý dolní) a v obousměrech (pravý dolní).
67
4.3.1 Rychlé násobení polynomů
Označme si p polynom s komplexními koeficienty tvaru
p(x) =N−1∑j=0
ajxj.
Všiměte si, že hodnoty polynomu p v bodech jednotkové kružnice
ωkN = e−2πik/N
lze vyjádřit pomocí DFT jako
p(ωkN) = (Fa)k, ∀k ∈ 0, 1, . . . , N − 1,
kde a = (a0, a1, . . . , aN−1) ∈ CN je vektor koeficientů polynomu a.Na tomto pozorování je založený algoritmus pro rychlé násobení dvou polynomů
p(x) =N−1∑j=0
ajxj a q(x) =
N−1∑j=0
bjxj.
Horní meze v sumách výše lze volit obě stejné bez újmy na obecnosti, jinak bychom dopl-nili přislušný počet nulových koeficientů k jednomu z polynomů. Cílem bude rychle najítkoeficienty polynomu, který je součinem
p(x) · q(x) =2N−2∑j=0
cjxj,
kdecj =
∑0≤r,s≤N−1r+s=j
arbs.
Krok 1: Pomocí DFT vypočítáme hodnoty p a q v bodech ωk2N pro k = 0, 1, . . . , 2N − 1:
p(ωk2N) = (Fa)k, k ∈ 0, 1, . . . , 2N − 1,
kde nyní je a = (a0, a1, . . . , aN−1, 0, . . . , 0) ∈ C2N vektor koeficientů polynomu p doplěnýo N nul, aby měl odpovídající délku. Podobně najdeme stejné hodnoty pro polynom q.Složitost tohoto kroku je při použití FFT rovna O(N logN).Krok 2: Vynásobíme komplexní čísla
Tedy číslo ck je rovno hodnotě součinu p · q v bodě ωk2N . V tomto kroku provádíme 2Nnásobení, a proto je složitost řádově O(N).
68
Krok 3: Pomocí inverzní DFT spočítáme hledané koeficienty součinu p · q:
ck = (F−1c)k, k ∈ 0, 1, . . . , 2N − 2,
kde c = (c0, c1, . . . , c2N−1) ∈ C2N je vektor hodnot nalezených v předchozím kroku.Využijeme-li FFT, je složitost opět O(N logN). A tedy i celková složitost tohoto algo-ritmu pro násobení polynomů je O(N logN).
Na závěr poznamenejme, že tento algoritmus lze poměrně snadno upravit k násobenívelkých čísel (v bázi o libovolném základu).
4.4 Poznámky a odkazy
4.5 Cvičení
69
5 Funkce více proměnnýchThe calculus was the first achievement of modern mathematics and it is dif-ficult to overestimate its importance. I think it defines more unequivocally thananything else the inception of modern mathematics; and the system of mathe-matical analysis, which is its logical development, still constitutes the greatesttechnical advance in exact thinking. John von Neumann
V aplikacích je typicky potřeba popisovat a zkoumat modely závisející na více parametrech.Proto je nevyhnutelně nutné používat funkce více proměnných. Základním vlastnostemtěchto funkcí se budeme věnovat v první části této kapitoly (sekce 5.1 a 5.2). Podrobnějise budeme zabývat funkcemi definovanými na normovaných vektorových prostorech, kdemáme k dispozici i důležitý pojem konvergence. Obecnějším rámcem by bylo studium tzv.topologických nebo metrických prostorů, kterým se zde ale podrobně věnovat nebudeme.
Druhá část této kapitoly (sekce 5.3) se věnuje hledání extrémů funkcí více proměnnýcha dále studiu obecné úlohy nelineárního programování. V průběhu výkladu si ukážemekonkrétní praktické ukázky.
5.1 Základní pojmy z teorie funkcí více proměnnýchGood mathematicians see analogies. Great mathematicians see analogies be-tween analogies. Stefan Banach
Na začátku tohoto kurzu jsme zavedli konvergenci na množině komplexních čísel. Při tomjsme využili existence absolutní hodnoty komplexního čísla. Ukazuje se, že naprosto analo-gický přístup lze použít i v libovolném vektorovém prostoru, který je vybaven tzv. normou.Definice 5.1: Normovaným vektorovým prostorem nazýváme vektorový prostor Vnad tělesem reálných čísel R (nebo komplexních čísel C) vybavený normou, tedy zobrazením‖ · ‖ : V → R splňujícím podmínky:
i) Pro každé x ∈ V je ‖x‖ ≥ 0. Rovnost ‖x‖ = 0 nastává právě když x = 0.
ii) Pro každé α ∈ R (nebo C) a x ∈ V platí
‖αx‖ = |α| ‖x‖ .
iii) Pro každé x, y ∈ V platí trojúhelníková nerovnost
‖x+ y‖ ≤ ‖x‖+ ‖y‖ .
Norma vektoru představuje zobecnění Euklidovské délky vektoru z R3. Na množinureálných (resp. komplexních) čísel se lze dívat jako na jednorozměrný prostor R nad R(resp. C nad C) vybavený normou – absolutní hodnotou. Norma indukovaná skalárnímsoučinem na vektorovém prostoru V , vizte rovnici (26), je skutečně normou, tj. splňujevýše uvedené axiomy normy. Ne každá norma je však indukována skalárním součinem.
Příklad 5.2: Ukažme si několik příkladů normovaných prostorů.
a) Na vektorovém prostoru V = Rn (resp. Cn) je předpisem
‖x‖p ··= p
√√√√ n∑k=1|xk|p ,
kde p ≥ 1 a x = (x1, . . . , xn) ∈ Rn (resp. Cn), definována norma. Není triviální dokázat23
trojúhelníkovou nerovnost, která v tomto případě má tvar
p
√√√√ n∑k=1|xk + yk|p ≤ p
√√√√ n∑k=1|xk|p + p
√√√√ n∑k=1|yk|p
a nazývá se Minkowskiho nerovností. Pouze pokud p = 2 je tato norma indukovánaskalárním součinem, uhodnete jakým?
b) Na vektorovém prostoru V = Rn (resp. Cn) je předpisem
‖x‖∞ ··= maxk=1,...,n
|xk|
definována norma. V tomto případě je snadné rozmyslet si i platnost trojúhelníkovénerovnosti (plyne ze známé trojúhelníkové nerovnosti pro absolutní hodnotu reálného,resp. komplexního, čísla).
c) Na vektorovém prostoru V = C(J) spojitých funkcí na uzavřeném intervalu J je před-pisem
‖f‖p ··= p
√∫J|f(x)|p dx , f ∈ C(J) ,
definována norma. Trojúhelníková nerovnost je opět netriviální. Nazývá se Minkowskihonerovností v integrálním tvaru.
Pro dva vektory x a y lze výraz ‖x− y‖ také chápat jako vzdálenost bodů x a y veV . Je-li (V, ‖ · ‖) prostor s normou, pak pro ε > 0 a x ∈ V definujeme množinu
Hx(ε) ··=y ∈ V
∣∣∣ ‖x− y‖ < ε
a nazýváme ji okolím bodu x o poloměru ε. Jde tedy o množinu všech vektorů, jejichžvzdálenost od vektoru x ∈ V je menší než ε. Ukázky různých typů okolí bodů v rovině jsouuvedeny na obrázku 16. Ve vektorových prostorech konečné dimenze je „jedno“ s jakounormou pracujeme. Platí totiž následující tvrzení.
23Pro p = 2 jsme důkaz provedli v předchozí kapitole, tato norma je totiž indukována skalárním součinem.
71
x1
x2
‖x‖1 < 1
x1
x2
‖x‖2 < 1
x1
x2
‖x‖4 < 1
x1
x2
‖x‖∞ < 1
Obrázek 16: Různá okolí bodu (0, 0) v rovině R2.
Věta 5.3: Libovolné dvě normy na vektorovém prostoru konečné dimenze jsou si ekviva-lentní. Přesněji, je-li V vektorový prostor a ‖ · ‖1, ‖ · ‖2 dvě24 normy na V , pak existují dvěkladné konstanty c1, c2 splňující
‖x‖1 ≤ c1‖x‖2 , ‖x‖2 ≤ c2‖x‖1 ,
pro každé x ∈ V .
Důkaz. Vynecháváme.
Geometricky předchozí věta znamená, že každé okolí bodu x ∈ V definované pomocínormy ‖ · ‖1 lze vnořit25 do jistého okolí definovaného pomocí normy ‖ · ‖2 a naopak. Zdů-razněme, že předpoklad konečné dimenze V je podstatný, v prostorech nekonečné dimenzepředchozí věta neplatí. Jedním z jejích důsledků je nezávislost pojmů konvergence a limityna konkrétní volbě normy ve V konečné dimenze.Definice 5.4: Buď (zn)∞n=0 posloupnost v normovaném vektorovém prostoru (V, ‖ · ‖). Oposloupnosti (zn)∞n=0 řekneme, že konverguje k vektoru z ∈ V , právě když pro každéokolí Hz(ε) bodu z existuje n0 ∈ N takové, že zn ∈ Hz(ε) kdykoliv n > n0. Tento fakt opětsymbolicky zapisujeme lim
n→∞zn = z.
24Spodní indexy nyní používáme k odlišení těchto dvou norem. Nejedná se konkrétní normy zavedené vpříkladu 5.2.
25Ve smyslu množinové inkluze.
72
Definici lze přeformulovat i bez použití pojmu okolí. Posloupnost vektorů (zn)∞n=0 z Vkonverguje k z ∈ V , právě když pro každé ε > 0 existuje n0 ∈ N takové, že pro každépřirozené n > n0 platí ‖zn − z‖ < ε. Z tohoto pozorování ihned dostáváme následujícíekvivalenci
limn→∞
zn = z v (V, ‖ · ‖) ⇔ limn→∞
‖zn − z‖ = 0 .
Definice 5.5: Buďte (V, ‖·‖) normovaný vektorový prostor aM ⊂ V . Bod a ∈ V nazvemehromadným bodem množiny M , právě když pro každé okolí Ha bodu a platí (Ha ra) ∩M 6= ∅.
Jinak řečeno, bod a ∈ V je hromadným bodem množiny M ⊂ V , právě když v každémokolí bodu a leží aspoň jeden bod množinyM různý od a. Není těžké si rozmyslet jak tentopojem souvisí s konvergencí:Věta 5.6: Buďte (V, ‖ · ‖) normovaný vektorový prostor a M ⊂ V . Bod a ∈ V je hromad-ným bodem množiny M , právě když existuje posloupnost (zn)∞n=1, zn ∈M r a, splňujícílimn→∞
zn = a.
Důkaz. Přenecháváme čtenáři jako domácí cvičení (Cvičení 5.2).
Zcela analogicky můžeme zavést pojem limity i pro zobrazení přiřazující vektorům vek-tory.Definice 5.7: Buďte (V, ‖ · ‖1) a (W, ‖ · ‖2) dva vektorové normované prostory. O funkcif : Df ⊂ V → W řekneme, že v bodě a ∈ V má limitu rovnou c ∈ W , právě když a jehromadným bodem Df a pro každé okolí Hc bodu c existuje okolí Ha bodu a splňující
x ∈ (Ha r a) ∩Df ⇒ f(x) ∈ Hc .
Tento fakt zapisujeme symbolicky
limx→a
f(x) = c .
Pro libovolné dva různé body x, y ∈ V , x 6= y, z normovaného prostoru (V, ‖·‖) existujíjejich disjunktní okolí (Cvičení 5.4). Díky tomu je pojem limity funkce a posloupnostijednoznačný. Tj. posloupnost i funkce v daném bodě nemůže mít dvě různé limity. Limitasamozřejmě stále nemusí existovat.Poznámka 5.8: Pro pojem limity platí řada tvrzení známých z BI-ZMA. Pokud jsou dvěposloupnosti konvergentní, pak jejich součet konverguje k součtu limit. Mají-li dvě funkcef : Df ⊂ V → W a g : Dg ⊂ V → W limity limx→a f(x) = c a limx→a g(x) = d, a bod aje hromadným bodem průniku Df ∩Dg, pak součet funkcí f a g má limitu rovnou součtulimit c+d. Je-li W = R (nebo C), pak lze podobné tvrzení zformulovat i pro součin funkcí.
Podrobněji se těmto tvrzením věnovat nebudeme. Bude-li potřeba upozorníme na ně adokážeme je během dalšího výkladu.
Uveďme dále důležitý důsledek ekvivalence norem z Věty 5.3.
Poznámka 5.9: Uvažme zobrazení f : V → W normovaných prostorů (V, ‖ · ‖1) a (W, ‖ ·‖2), oba nad reálným tělesem. Předpokládejme, že V i W jsou konečné dimenze. Existujíproto jejich báze, označme je B1 = (a1, . . . , am) ⊂ V a B2 = (b1, . . . , bn) ⊂ W . Této volběbází odpovídá souřadnicová reprezentace zobrazení f definovaná předpisem
f := L2 f L−11 : Rm → Rn,
kde L1 : V → Rm a L2 : W → Rn přiřazují vektorům jejich souřadnice v bázích B1, resp.B2.
Rozdíl mezi f a f je jemný. Zobrazení f přiřazuje vektorům vektory. Naproti tomu fpřiřazuje odpovídajícím způsobem souřadnicím vektorů souřadnice f -obrazů těchto vek-torů. Musí být ale jasné, s jakými bázemi se pracuje. Tato situace je známá z Lineárníalgebry kde se rozlišuje mezi lineárním zobrazením a maticí lineárního zobrazení vzhle-dem k bázím. My jsme tento pojem jen zobecnili i na nelineární zobrazení. Není obtížnéuvědomit si následující ekvivalenci:
limx→a
f(x) = c ⇐⇒ limy→a
f(y) = c,
kde a ∈ V , c ∈ W a a = L1a, c = L2c (důkaz proveďte v Cvičení 5.3).Díky výše uvedené ekvivalenci se můžeme omezit na zobrazení mezi prostory Rm a Rn.
Uvažme proto nyní funkci f : Rm → Rn, která má v jistém bodě a ∈ Rm limitu s hodnotouc ∈ Rn. Pro každé x ∈ Rm můžeme f zapsat ve tvaru
f(x) =
f1(x)...
fn(x)
a dále
c =
c1...cn
.Využijeme-li ekvivalence norem v Rn, a zvolíme-li za normu maximovou normu
‖y‖∞ = maxj=1,...,n
|yj|, y = (y1, . . . , yn)T ∈ Rn,
pak tvrzenílimx→a
f(x) = c
je ekvivalentní (tzv. konvergenci po složkách)
limx→a
fj(x) = cj pro každé j ∈ n.
Všimněte si, že fj : Rm → R pro každé j ∈ n. Připomeňme, že používáme značení n :=1, 2, . . . , n.
74
Na závěr ještě uveďme jednu fundamentální vlastnost omezených posloupností v normo-vaných prostorech konečné dimenze, jejíž speciální případ pro číselné posloupnosti (V = R)znáte z BI-ZMA. Přirozeně posloupnost bodů (zn)∞n=1 z normovaného prostoru (V, ‖ · ‖)nazveme omezenou, pokud existuje K > 0 takové, že ‖zn‖ < K pro všechna n ∈ N.Věta 5.10 (Bolzano–Weierstrass): Každá omezená posloupnost z normovaného prostorukonečné dimenze obsahuje konvergentní podposloupnost.
Důkaz. Vynecháme.
Nyní si uvedeme jeden důležitý a zajímavý příklad zobrazení typu uvažovaného v tétokapitole.Příklad 5.11 (Maticová exponenciála): Uvažme vektorový prostor V všech komplexníchmatic typu n× n vybavený normou
‖A‖2 =√√√√ n∑j,k=1|Ajk|2 , A ∈ V. (42)
Čtenáři by mělo být zřejmé, že se jedná skutečně o normu.Na rozdíl od obyčejných vektorových prostorů jsme v tomto V = Cn,n schopni vektory
– matice – i násobit. Jak se vůči maticovému násobení chová naše norma? Platí nerovnost26
‖A ·B‖2 ≤ ‖A‖2 ‖B‖2 , A,B ∈ V.
Skutečně, pro maticové prvky součinu dle Schwarzovy nerovnosti platí
|(A ·B)jk| =∣∣∣〈Aj•,B•k〉
∣∣∣ ≤ ‖Aj•‖2 ‖B•k‖2 = ‖Aj•‖2 ‖B•k‖2
a proto
‖A ·B‖2 =√√√√ n∑j,k=1|(A ·B)j,k|2 ≤
√√√√ n∑j,k=1‖Aj•‖2
2 ‖B•k‖22 =
=√√√√ n∑j=1‖Aj•‖2
2 ·
√√√√ n∑k=1‖B•k‖2
2 = ‖A‖2 ‖B‖2 .
Nyní definujme zobrazení exp : V → V , které matici A ∈ V přiřadí matici
exp(A) ··=∞∑j=0
1j!A
j = limN→∞
N∑j=0
1j!A
j .
Tato limita má dobrý význam jako limita v normovaném vektorovém prostoru (Cn,n, ‖·‖2).Takto zavedené zobrazení je dobře definované. Čtenář se o tom může přesvědčit zopaková-ním kroků použitých v první kapitole, kde jsme se zabývali komplexní exponenciálou. Jen
26Dvojice (V, ‖ · ‖) tak ve skutečnosti tvoří Banachovu algebru.
roli absolutní hodnoty zde bude hrát norma ‖ · ‖2. Drobným rozdílem je, že pro komplexníčísla platí rovnost
|zj| = |z|j , z ∈ C , j ∈ N0 ,
ale pro naší normu máme obecně pouze nerovnost
‖Aj‖2 ≤ ‖A‖j2 , A ∈ V , j ∈ N .
Na výpočet to nebude mít vliv. Dále je relativně snadné si rozmyslet, že uvažovaný nor-movaný vektorový prostor je úplný (viz cvičení 5.6).
Jaké vlastnosti má naše maticová exponenciála? Z definice je zřejmé, že
exp(0) = E .
Co lze říci o exponenciále součtu? Rovnost
exp(A + B) = exp(A) · exp(B)
platí pouze pro matice, které navzájem komutují, tj. pouze pokud
A ·B−B ·A = 0 .
Pokud se podíváte na důkaz této formule pro komplexní exponenciálu zjistíte, že v jednomkruciálním okamžiku jsme použili binomickou větu. Ta pro nekomutující matice ale neplatí,obecně víme pouze
(A + B)2 = A2 + A ·B + B ·A + B2 .
Pouze pokud A a B komutují můžeme psát
(A + B)2 = A2 + 2 A ·B + B2 .
Pro komutující matice dále platí
A · exp(B) = exp(B) ·A .
Z výše uvedeného je dále patrné, že pro libovolnou matici A ∈ V je exp(A) regulárnía matice k ní inverzní je exp(−A).
K maticové exponenciále se ještě běheme semestru vrátíme. Budeme totiž s její pomocíkonstruovat řešení obyčejných lineárních diferenciálních rovnic s konstantními koeficienty(Kapitola 6)Poznámka 5.12 (Metrické prostory): Pro pojmy jako okolí, konvergence a vzdálenostnebylo nijak podstatné, že pracujeme s vektorovým prostorem. Pojem vzdálenosti lze tedyabstrahovat dále, čímž získáme tzv. metrické prostory.
Je-li M libovolná neprázdná množina a d : M ×M → R zobrazení splňující podmínky
a) d(x, y) ≥ 0 pro každé x, y ∈M a navíc d(x, y) = 0 právě když x = y,
76
b) d(x, y) = d(y, x) pro každé x, y ∈M ,
c) d(x, y) ≤ d(x, z) + d(z, y) pro každé x, y, z ∈M ,
potom d nazývámemetrikou na množiněM a o dvojici (M,d) mluvíme jako ometrickémprostoru.
Čtenáři by nyní mělo být zřejmé, jak zavést okolí bodu v metrickém prostoru a vybudo-vat na něm pojmy konvergence a limity. Metrickými prostory se v tomto kurzu podrobnějizabývat nebudeme, pro pojem derivace je podstatné, že prvky našich prostorů můžemesčítat a násobit číslem, což v obecném metrickém prostoru nemůžeme.
Mělo by být zřejmé, že v normovaném vektorovém prostoru (V, ‖ · ‖) je metrikoud(x, y) = ‖x− y‖, x, y ∈ V .
5.2 Derivace funkcí více proměnnýchDůležitým analytickým nástrojem je derivace funkce. V této části si ukážeme, jak tentopojem zavést i pro funkce více proměnných. Nejprve se ale dohodněme na drobném zjed-nodušení notace a výkladu.Poznámka 5.13 (Úmluva): Pro zjednodušení výkladu budeme pracovat ve vektorovémprostoru Rn se standardní bází En = (e1, . . . , en). Symbol ‖ · ‖ bude označovat libovolnounormu na Rn. Toto opatření není velké omezení, odpovídá pouze volbě konkrétní báze vprostoru V . Viz poznámky z předchozí kapitoly.Definice 5.14: Buď f : Rn → R a a ∈ Df . Pokud existuje limita27
limh→0
f(a+ hei)− f(a)h
, (43)
pak její hodnotu nazýváme parciální derivací funkce f podle i-té proměnné v boděa. Její hodnotu označujeme jedním z následujících tradičních symbolů
∂f
∂xi(a) , ∂xif(a) , fxi(a) .
Předpis (43) je prakticky shodný se známou definicí z BI-ZMA. Pokud máme funkcizadanou explicitně pomocí vzorce, lze použít všechny známé vlastnosti o derivování funkcíjedné proměnné.
Geometrická interpretace parciální derivace je pak nasnadě. Parciální derivace funkce fpodle i-té proměnné v bodě a udává míru změny funkčních hodnot v tomto bodě ve směrui-té souřadné osy (ve směru udaném vektorem ei).
Pro zadanou funkci f : Rn → R lze zkoumat množinu všech a ∈ Df , pro něž existujeparciální derivace podle i-té proměnné. Tímto způsobem získáváme novou funkci, parciálníderivaci funkce f podle i-té proměnné, kterou značíme ∂xif . Tato funkce je opět typu
∂xif : Rn → R, její definiční obor je podmnožinou definičního oboru původní funkce.Můžeme proto zkoušet vytvořit druhou derivaci podle zvolené proměnné. Zkráceně píšeme
∂2xixj
f ··= ∂xi(∂xjf), i, j ∈ n.
Podobně můžeme konstruovat parciální derivace vyšších řádů.Příklad 5.15: Pomocí definice nalezněme parciální derivaci funkce f(x, y) = x2 + xy + 1podle druhé proměnné v bodě a = (1, 0). Dosazením do definice dostáváme
∂yf(1, 0) = limh→0
f(1, h)− f(1, 0)h
= limh→0
1 + h+ 1− 1− 0− 1h
= 1 .
Mohli jsme ale také nejprve vypočítat parciální derivaci této funkce podle druhé proměnné,tedy
∂yf(x, y) = x
a poté ji vyhodnotit v bodě (1, 0),
∂yf(1, 0) = 1 .
Nyní zavedeme pojem derivace funkce více proměnných. Někdy se též pro tento objektpoužívá název „totální“ derivace.Definice 5.16: Derivací funkce f : Rn → Rm v bodě a ∈ Df nazýváme lineárnízobrazení Df(a) : Rn → Rm splňující
limx→a
‖f(x)− f(a)−Df(a)(x− a)‖‖x− a‖
= 0 . (44)
Existuje-li Df(a), pak funkci f nazýváme diferencovatelnou v bodě a.Rozeberme si tuto definici podrobněji a pokusme se zjistit jak vypadá matice28 Df(a) ∈
Rm,n. Předpokládejme, že f : Rn → Rm je diferencovatelná v bodě a a označme si složkynaší funkce
f(x) =
f1(x)f2(x)...
fm(x)
.
Z rovnice (44) plyne konvergence v každé složce, tedy
limx→a
∣∣∣∣fj(x)− fj(a)−(Df(a)(x− a)
)j
∣∣∣∣‖x− a‖
= 0 , j ∈ m .
28Zdůrazňuji, že již pracujeme se standardní bázi a ve značení nerozlišujeme mezi lineárním zobrazeníma jeho maticí ve standardní bázi.
78
Nyní použijeme zobecnění Heineho věty. Zvolíme konkrétní způsob jak se blížit s x k bodua. Konkrétně ve směru i-té souřadné osy, x = a+ hei, h→ 0. Potom
limh→0
∣∣∣∣fj(a+ hei)− fj(a)−(Df(a)hei
)j
∣∣∣∣‖hei‖
= 1‖ei‖
limh→0
∣∣∣∣∣fj(a+ hei)− fj(a)h
−(Df(a)
)ji
∣∣∣∣∣ ,kde i ∈ n a j ∈ m jsou libovolné. Uzavíráme tedy, že(
Df(a))ji
= ∂xifj(a) , i ∈ n a j ∈ m .
Případně zapsáno v maticovém tvaru, matice derivace funkce f v bodě a ve standardníbázi má tvar
Poznámka 5.17: Ukázali jsme tedy, že pro funkci f : Rn → Rm diferencovatelnou v boděa existují parciální derivace funkcí složek f1, . . . , fm podle všech proměnných v bodě a amaticeDf(a) obsahuje tyto derivace ve svých složkách. Upozorňujeme, že opačná implikaceneplatí, tj., existence parciálních derivací funkcí f1, . . . , fm podle všech proměnných v boděa nezaručuje diferencovatelnost f v bodě a. Platí ale např. tvrzení: Existují-li parciálníderivace funkcí f1, . . . , fm podle všech proměnných na nějakém okolí bodu a a jsou spojitév bodě a, potom je f diferencovatelná v bodě a. Důkaz tohoto tvrzení vynecháme.
Uvažme speciálně reálnou funkci n reálných proměnných f : Rn → R, její derivací jematice z R1,n tvaru
Df =(∂x1f, ∂x2f, . . . , ∂xnf
).
Z historických důvodů se tento řádkový vektor také často značí symbolem ∇ (nabla),∇f := Df , a mluví se o něm jako o gradientu funkce f : Rn → R. Z definice (44) plyne,že lineární funkce T : Rn → R definovaná předpisem
T (x) = f(a) +Df(a)(x− a) ,
představuje nejlepší lineární aproximaci funkce f v bodě a. Její graf pak představuje tečnounadrovinu ke grafu funkce f v bodě a. Rozepíšeme-li tento fakt podrobněji, pak rovnicítečné nadroviny grafu funkce f v bodě a (resp. (a, f(a))) má tvar
Normálovým vektorem této nadroviny je proto vektor(∂x1f(a), ∂x2f(a), . . . , ∂xnf(a),−1
).
79
Derivace funkce f : Rn → R je funkce Df : Rn → Rn. Podle definice 5.16 můžemetedy Df znovu derivovat (je-li diferencovatelná) a dostáváme tak druhou derivaci funkcef , která je lineárním zobrazením Rn → Rn s maticí
D2f(a) =
∂2x1x1f(a) ∂2
x2x1f(a) · · · ∂2xnx1f(a)
∂2x1x2f(a) ∂2
x2x2f(a) · · · ∂2xnx2f(a)
... ... . . . ...∂2x1xnf(a) ∂2
x2xnf(a) · · · ∂2xnxnf(a)
.
Tato matice se často nazývá Hessova matice funkce f v bodě a a značí se symbolem∇2f(a).Poznámka 5.18: V tomto bodě je vhodné doplnit výklad následující poznámkou. Aby-chom se dostali k Hessově matici, derivovali jsme dvakrát speciální, totiž skalární funkcif : Rn → R (s hodnotami v R). Definice derivace vyššího řádu pro obecnou vektorovoufunkci f : Rn → Rm také existuje, my se jí tu ale úmyslně vyhýbáme. Podle definice 5.16 jeDf(a) lineární zobrazení z Rn do Rm, tedy element lineárního prostoru L(Rn,Rm), kterýje izomorfní s prostorem matic Rm,n. Pokud bychom se pokusili obdobně aplikovali definici5.16 na Df : Rn → L(Rn,Rm) dostali bychom objekt
D2f(a) ∈ L(Rn,L(Rn,Rm)).
Elementy lineárního prostoru L(Rn,L(Rn,Rm)) již nelze realizovat maticemi, nýbrž tak-zvanými tenzory (jejich elementy by měly v tomto případě tři indexy místo dvou). Podobně
D3f(a) ∈ L(Rn,L(Rn,L(Rn,Rm))).
Tenzorová algebra není součástí běžných kurzů lineární algebry a to je důvod, proč úplnoudefinici derivace vyšších řádů neuvádíme a s jedinou výjimkou týkající se Hessovy maticeji ani v našem výkladu nebudeme potřebovat.Věta 5.19 (Derivace složené funkce): Buďte f : Rn → Rm a g : Rm → Rk. Nechť f jediferencovatelná v bodě a ∈ Df a g diferencovatelná v bodě f(a) ∈ Dg. Potom pro derivacisložené funkce g f v bodě a platí
D(g f)(a) = Dg(f(a)) ·Df(a) , (45)
kde tečka označuje maticové násobení.
Důkaz. Vynecháváme.
Ukažme si na jednoduchém příkladě, co se skrývá pod kompaktní formulkou (45). Jakopříklad, který navíc později využijeme, uvažme funkce f : R→ Rn a g : Rn → R. Složenáfunkce g f je proto obyčejná reálná funkce jedné reálné proměnné. Označme si nezávisleproměnné a složky funkcí následovně
Z očividných důvodů se vzorci (45) (rozepsanému po složkách, v libovolném případě funkcí)říká řetězové pravidlo (chain rule).Příklad 5.20 (Maticová exponenciála, pokračování): Vraťme se k maticové exponenciálezavedené v Příkladu 5.11.
Uvažme matici A ∈ Rn,n a zobrazení Φ : R→ Rn,n definované předpisem
Φ(t) := exp(tA), t ∈ R .
Tento výraz skutečně má smysl pro každé t ∈ R.Lze dokázat platnost rovnosti
Φ′(t) ≡ DΦ(t) = A exp(tA) = exp(tA)A .
Je-li navíc x0 ∈ Rn a x(t) := Φ(t)x0 pak
x′(t) = Φ′(t)x0 = A exp(tA)x0 = Ax(t) , t ∈ R ,x(0) = x0 .
Jinak řečeno, pomocí maticové exponenciály lze konstruovat řešení lineárních soustavobyčejných diferenciálních rovnic ve tvaru
x′ = Ax , x(0) = x0 ∈ Rn ,
kde A ∈ Rn,n a x : R→ Rn je hledaná vektorová funkce. Diferenciální rovnice tohoto typuse nazývají evoluční.
81
5.3 Extrémy funkcí více proměnnýchK výkladu postupu hledání extrémů funkce f : Rn → R použijeme zobecnění pojmuTaylorův polynom pro funkce více proměnných. Buď a ∈ Df a předpokládejme, že najistém okolí Ha tohoto bodu má uvažovaná funkce f všechny parciální derivace až dotřetího řádu spojité29. Stručně tuto skutečnost označujeme f ∈ C3(Ha) (a obecněji pakf ∈ CN(Ha)). Uvažme x ∈ Ha. Množina Ha je konvexní a bod a a x lze proto spojitúsečkou
〈0, 1〉 3 t 7→ a+ t(x− a) ∈ Rn ,
která celá leží v Ha. Položme g(t) ··= f(a + t(x − a)). Tímto způsobem získáváme funkcijedné proměnné g : 〈0, 1〉 → R se spojitou derivací až do třetího řádu. Můžeme ji tedyaproximovat pomocí Taylorova polynomu stupně 2 se středem v 0:
g(t) = g(0) + g′(0)t+ 12g′′(0)t2 +R3(a; t), (46)
kde R3(a; t) označuje zbytek, který lze vyjádřit ve tvaru
R3(a; t) = 16g′′′(ξ)t3
a číslo ξ ∈ (0, 1).Aplikujeme-li větu 5.19 spočítáme postupně
g′(0) =n∑i=1
∂xif(a) (xi − ai) = ∇f(a) · (x− a),
g′′(0) =n∑i=1
n∑j=1
∂2xixj
f(a) (xi − ai)(xj − aj) = (x− a)T∇2f(a)(x− a),
g′′′(ξ) =n∑i=1
n∑j=1
n∑k=1
∂3xixjxk
f (a+ ξ(x− a)) (xi − ai)(xj − aj)(xk − ak).
Nyní dosadíme-li do (46) t = 1, g(1) = f(x) a použijeme-li spočítané derivace g, dostaneme
f(x) = f(a) +∇f(a) · (x− a) + 12(x− a)T∇2f(a)(x− a) +R3(a;x), (47)
kdeR3(a;x) = 1
6
n∑i=1
n∑j=1
n∑k=1
∂3xixjxk
f(a+ ξ(x− a))(xi − ai)(xj − aj)(xk − ak)
a ξ ∈ (0, 1). Vzorec platí pro každé x ∈ Ha. Získali jsme tak druhý Taylorův polynomfunkce f : Rn → R se středem v bodě a,
f(a) +∇f(a) · (x− a) + 12(x− a)T∇2f(a)(x− a) .
29Funkci f : Rn → Rm nazýváme spojitou v bodě a ∈ Df , právě když limx→a f(x) = f(a).
82
Tento polynom představuje kvadratickou aproximaci funkce f v bodě a. Lineární člen udává„sklon“ grafu a kvadratický člen pak jeho „vypouklost“.
Uvedený postup lze jednoduše zobecnit a dostaneme tak obecnýN -tý Taylorův polynomfunkce f : Rn → R se středem v bodě a. Tvrzení zformulujeme v následující větě. Důkazpřenecháváme čtenáři.Věta 5.21: Buď N ∈ N0 a f ∈ CN+1(Ha), kde Ha je nějaké okolí bodu a ∈ Rn. Potompro libovolné x ∈ Ha platí
a ξ ∈ (0, 1).Bod a+ ξ(x−a) objevující se ve vzorci pro zbytek RN+1(a;x) leží na úsečce mezi body
a a x. Srovnejte to se speciálním případem pro n = 1, který znáte z BI-ZMA.Vztah (47) použijeme k odvození postupu pro hledání extrémů funkcí více proměnných.
Nejprve se podíváme podrobněji na kvadratický člen.
5.3.1 Kvadratické formy: stručný souhrn
V tomto textu jen velmi stručně shrneme základní informace o tzv. kvadratických formách.Tématicky tato látka spadá do lineární algebry, ale v kurzu BI-LIN se neobjeví.
Buď A ∈ Rn,n reálná symetrická n × n matice. Pod symetrií máme na mysli platnostpodmínky AT = A, kde AT značí matici transponovanou. Kvadratickou formou příslušnoumatici A je pak zobrazení qA : Rn → R definované předpisem
qA(x) = xTAx , x ∈ Rn .
Zavádíme následující terminologii. Matici A a taktéž příslušnou kvadratickou formu qA
nazýváme
i) pozitivně definitní, právě když qA(x) > 0 pro každé nenulové x ∈ Rn,
ii) negativně definitní, právě když qA(x) < 0 pro každé nenulové x ∈ Rn,
iii) pozitivně semidefinitní, právě když qA(x) ≥ 0 pro každé x ∈ Rn,
iv) negativně semidefinitní, právě když qA(x) ≤ 0 pro každé x ∈ Rn,
v) indefinitní, právě když existují x, y ∈ Rn splňující qA(x) < 0 a qA(y) > 0.
Pojem definitnosti lze chápat jako zobecnění znaménka na matice (reálná čísla, lze chá-pat jako matice z R1,1). Pozor, definice definitnosti se v různých textech mohou lišit. Podlenaší definice je každá pozitivně (negativně) definitní matice také pozitivně (negativně) se-midefinitní. Jediná matice, která je současně pozitivně i negativně semidefinitní, je nulovámatice.
Grafy kvadratických forem pro n = 2 s různými typy definitností jsou zobrazeny naObrázku č. 17. K rozhodování o různých typech definitnosti lze použít několik kritérií:
• Definice a úprava na čtverce.
• Sylvestrovo kritérium (pouze pro pozitivní a negativní definitnost!).
• Spektrum matice A.
84
−4−2 0
24 −4
−20
24
0
20
40
x y
z=x
2+y
2
−4−2 0
24 −4
−20
24
−50
0
x y
z=−
2x2−y
2
−4−2 0
24 −4
−20
24
0
100
200
x y
z=x
2−
4xy
+4y
2
−4−2 0
24 −4
−20
24
−20
0
x y
z=−y
2
−4−2 0
24 −4
−20
24
−20
0
20
x y
z=x
2−y
2
Obrázek 17: Ukázka grafů několika kvadratických forem. Jejich typ je postupně PD, ND,PSD, NSD a ID.
85
Na závěr této části ještě uveďme několik pojmů a tvrzení, které je zobecněním věty zBI-ZMA: „Funkce spojitá na omezeném a uzavřeném intervalu nabývá na tomto intervalusvého minima i maxima“. Jelikož toto tvrzení nebudeme dokazovat, zformulujeme ho pouzejako poznámku. Nicméně tato věta má velmi důležitý teoretický význam.Poznámka 5.22: Nejprve musíme zobecnit pojmy „uzavřenost“ a „omezenost“ množinyz Rn. Množinu M ⊂ Rn nazveme otevřenou, právě když (∀x ∈ M)(∃Hx ⊂ M). Nebolimnožina M je otevřená, pokud každý bod množiny M leží v M i s nějakým svým okolím.Množinu M ⊂ Rn nazveme uzavřenou, právě když její doplněk MC = Rn \M je množinaotevřená. Konečně množinu M ⊂ Rn nazveme omezenou, právě když (∃K > 0)(∀x ∈M)(‖x‖ < K).
Funkce f : Rn → R, která je spojitá na omezené a uzavřené množině M (tzn. spojitá vkaždém bodě M), nabývá na M svého maxima i minima. Tzn., že existují xmin, xmax ∈Mtakové, že
f(xmin) = minx∈M
f(x) a f(xmax) = maxx∈M
f(x).
Speciálně tedy každá funkce, která je spojitá na uzavřené a omezené množině, je na tétomnožině omezená.Lemma 5.23: Buď q : Rn → R pozitivně (negativně) definitní kvadratická forma. Potomexistuje α > 0 takové, že pro všechna x ∈ Rn platí:
q(x) ≥ α‖x‖2 (q(x) ≤ −α‖x‖2).
Důkaz. Uvažujme případ pozitivně definitní formy q. Kvadratická forma q je spojitá funkcena celém Rn. Uvažujme jednotkovou sféru S = x ∈ Rn | ‖x‖ = 1. Množina S je zřejměomezená a je také uzavřená. Proto funkce q nabývá na S svého minima, které musí býtkladné, neboť q má na S pouze kladné hodnoty. Označíme-li tuto minimální hodnotu α > 0,potom máme
α = minx∈S
q(x).
Neboli(∀x ∈ Rn, ‖x‖ = 1)(q(x) ≥ α).
Tvrzení věty zřejmě platí pro x = 0. Je-li nyní x 6= 0 libovolné, máme
q(x) = ‖x‖2q
(x
‖x‖
)≥ α‖x‖2.
Modifikaci pro případ negativně definitní formy přenecháme čtenáři.
5.3.2 Vyšetřování extrémů funkcí více proměnných
Na úvod poznamenejme, že definice (ostrých) lokálních maxim a minim funkce f : Rn → Rje prakticky shodná s definicí pro funkci jedné proměnné uvedené v BI-ZMA. Stačí pouzeuvažovat okolí bodů a ∈ Rn.
Definice 5.24: Buď f : Rn → R definovaná na nějakém okolí bodu a ∈ Rn. Řekneme, že fmá v bodě a lokální maximum, resp. minimum, jestliže (∃Ha ⊂ Rn)(∀x ∈ Ha)(f(x) ≤f(a)), resp. (∃Ha ⊂ Rn)(∀x ∈ Ha)(f(x) ≥ f(a)). Platí-li v těchto definicích ostré nerovnostipro x 6= a, mluvíme o ostrém lokálním maximu, resp. minimu. Lokální maxima a minimanazýváme souhrnně lokální extrémy.Věta 5.25 (nutná podmínka extrému): Nechť má funkce f : Rn → R v bodě a ∈ Rn par-ciální derivaci podle i-té proměnné. Má-li f v bodě a lokální extrém, potom ∂xif(a) = 0.Speciálně, má-li funkce f s lokálním extrémem v a parciální derivace podle všech proměn-ných, potom je ∇f(a) = 0.Poznámka 5.26: Bod a ∈ Rn takový, že ∇f(a) = 0, se nazývá stacionární bod funkcef .
Důkaz. Tvrzení věty vyplývá z analogické věty pro funkce jedné proměnné. Skutečně, po-ložíme-li
g(xi) := f(a1, . . . , ai−1, xi, ai+1, . . . , an),je g reálná funkce jedné proměnné, která je v bodě ai diferencovatelná. Pro derivaci g platí
g′(ai) = ∂xif(a).
A protože g má lokální extrém v bodě ai, musí g′(ai) = 0.
Dospěli jsme k následujícímu ponaučení: Má-li f v bodě a lokální extrém, potom buďa je stacionárním bodem f , nebo alespoň jedna z derivací ∂xif(a) neexistuje.
K nalezení extrému budou klíčové postačující podmínky, které zformulujeme v násle-dující větě.Věta 5.27 (postačující podmínka extrému): Nechť a ∈ Rn je stacionární bod funkcef : Rn → R a nechť existuje okolí Ha bodu a takové, že f ∈ C3(Ha). Je-li matice ∇2f(a)
i) pozitivně (negativně) definitní, pak má f v bodě a ostré lokální minimum (maximum).
ii) indefinitní, pak f nemá v bodě a lokální extrém.
Poznámka 5.28: Ihned poznamenejme, že podmínky z věty nejsou vyčerpávající. Je-litotiž matice ∇2f(a) pozitivně nebo negativně semidefinitní, pak v bodě a může, ale nemusímít funkce f lokální extrém (viz ilustrativní příklady níže). V tomto případě tedy nelzepoužitím diferenciálního počtu rozhodnout, zda v a je či není extrém.
Důkaz. Buď ε > 0 takové, že
Ha(ε) := x ∈ Rn | ‖x− a‖ ≤ ε ⊂ Ha.
Množina Ha(ε) je uzavřená a omezená. Podle předpokladu je f ∈ C3(Ha(ε)), a protovšechny třetí parciální derivace f jsou omezené na Ha(ε). Tzn., že existuje K > 0 takové,že pro každé i, j, k ∈ n je
maxx∈Ha(ε)
|∂3xixjxk
f(x)| ≤ K.
87
Pro ‖h‖ < ε podle Taylorova vzorce (47) platí
f(a+ h)− f(a) = ∇f(a) · h+ 12h
T∇2f(a)h+R3(a;h). (48)
První sčítanec na pravé straně je nula, neboť a je stacionární bod f , a tedy ∇f(a) = 0.Pro zbytek R3 máme
|R3(a;h)| ≤ 16
n∑i=1
n∑j=1
n∑k=1|∂3xixjxk
f(a+ ξh)hihjhk|.
Protože číslo ξ ∈ (0, 1), je a+ ξh ∈ Ha(ε), a proto můžeme dále odhadovat
|R3(a;h)| ≤ K
6
(n∑`=1|h`|
)3
= K
6 ‖h‖31 ≤
Kc
6 ‖h‖3.
V poslední nerovnosti jsem využili faktu, že všechny normy na Rn jsou ekvivalentní, tedy∃c > 0 takové, že ‖h‖1 ≤ c‖h‖.
i) Buď ∇2f(a) např. pozitivně definitní matice. Podle Lemma 5.23 existuje α > 0takové, že
hT∇2f(a)h ≥ α‖h‖2.
Aplikujeme-li všechny uvedené skutečnosti na výraz na pravé straně vzorce (48), dostanemeodhad
f(a+ h)− f(a) ≥ α
2 ‖h‖2 − Kc
6 ‖h‖3 = 1
2‖h‖2(α− Kc
3 ‖h‖),
který platí pro všechna h, pro která ‖h‖ < ε. Nyní je klíčové si uvědomit, že výraz vkulatých závorkách bude pro dostatečně malé h (v normě) kladný. Skutečně, vezmeme-linějaké δ < 3α/Kc tak, že také δ < ε, bude pro každé h ∈ Ha(δ)
α− Kc
3 ‖h‖ > 0.
Celkem tedy máme, že pro každé h ∈ H0(δ) různé od 0 je f(a + h) − f(a) > 0. Bod a jeproto ostré lokální minimum funkce f .
Tvrzení pro ∇2f(a) negativně definitní matici, lze dokázat aplikací již dokázané částina funkci −f . Detaily přenecháme čtenáři.
ii) Nechť ∇2f(a) je indefinitní matice. Označme h+, h− ∈ Rn vektory takové, že
hT+∇2f(a)h+ > 0 a hT−∇2f(a)h− < 0.
Ukážeme, že v libovolně malém okolí a lze vždy nalézt jak body, v nichž je hodnota f většínež f(a), tak body, v nichž je hodnota f menší než f(a). Vezměme λ > 0 dost malé a v(48) položme h = λh+. Dostaneme stejně jako výše
f(a+ λh+)− f(a) ≥ λ2
2 hT+∇2f(a)h+ −
Kc
6 λ3‖h+‖3 = λ2
2
hT+∇2f(a)h+︸ ︷︷ ︸>0
−Kc3 λ‖h+‖3
.88
Je zřejmé, že výraz v kulaté závorce je pro všechna dostatečně malá λ kladný, a protof(a) < f(a+ λh+).
Analogicky se využije zápornosti hT−∇2f(a)h−, k tomu aby se ukázalo, že f(a) > f(a+λh−) pro všechna dostatečně malá λ.
Poznámka 5.29: Poznamenejme, že tvrzení věty platí za slabšího předpokladu existencederivace druhého řádu funkce f v bodě a, viz např. Věta 216 v [8].
Shrňme obecný postup hledání lokálních extrémů funkcí f : Rn → R definovanýchna otevřené množině Df . Postup je analogický postupu při hledání extrémů funkcí jednéproměnné. Jeho kroky jsou následující:
i) Nalezni body podezřelé z extrému, tj. stacionární body f , nebo body, kde alespoňjedna parciální derivace f neexistuje.
ii) Ve stacionárním bodě a zkoumej definitnost Hessovy matice ∇2f(a). Ta může (alenemusí!) rozhodnout o existenci lokálního extrému v tomto bodě. Nastane jeden znásledujících případů. Pokud je Hessova matice ∇2f(a)
a) pozitivně definitní, pak má f v a ostré lokální minimum,b) negativně definitní, pak má f v a ostré lokální maximum,c) pozitivně nebo negativně semidefinitní, pak pomocí ní nelze o extrému rozhod-
nout30,d) indefinitní, pak f v bodě a extrém nemá31.
Ukažme si na konkrétním příkladu, že semidefinitnost Hessovy matice neimplikuje anineostrý lokální extrém. Příkladem budiž funkce
f(x, y) = x2 + y3 .
Její graf je na obrázku 18, očividně v bodě (0, 0) nemá extrém. To je samozřejmě explicitněvidět i z jejího předpisu. Pro derivaci (gradient) této funkce platí
∇f(x, y) =(2x, 3y2
).
Jediným stacionárním bodem je proto bod (0, 0). Hessovou maticí v bodě (0, 0) je matice
∇2f(0, 0) =(
2 00 6y
)∣∣∣∣∣(x,y)=(0,0)
=(
2 00 0
).
Kvadratickou formou této matice je
(x, y)∇2f(0, 0)(xy
)= 2x2 ,
30Naopak ale například platí, že pokud má funkce f v bodě a lokální minimum a je dvakrát diferenco-vatelná, pak je Hessova matice funkce f v bodě a pozitivně semidefinitní.
31Bodu a se v tomto případě někdy říká sedlový bod funkce f .
89
která je očividně pozitivně semidefinitní.Na druhou stranu například funkce
g(x, y) = x4 + y4
má v počátku ostré globální minimum. Její gradient je
∇g(x, y) =(4x3, 4y3
),
a proto bod (0, 0) je jediným stacionárním bodem g. Avšak Hessova matice ∇2g(0, 0) jematice nulová, která je pozitivně (i negativně) semidefinitní.
−50
5 −20
2
0
50
x y
z=x
2+y
3
Obrázek 18: Graf funkce f(x, y) = x2 + y3. V bodě (0, 0) tato funkce nemá lokální extrém,i když její Hessova matice v tomto bodě je pozitivně semidefinitní.
Vyšetřování průběhu funkcí více proměnných je tedy velmi analogické známé situaci profunkce jedné proměnné. Na závěr této sekce ještě ukážeme, že naopak některé představyzažité z výšetřování průběhů funkcí jedné proměnné mohou vést k nesprávným závěrům vpřípadě funkcí více proměnných. Např., má-li všude definovaná a diferencovatelná funkcef : R→ R jediný stacionární bod, ve kterém má lokální extrém, pak je tento bod extrémglobální. Analogické tvrzení pro funkce více proměnných neplatí. Jako protipříklad uveďmefunkci
f(x, y) = x2 + y2(1− x)3.
Bod (0, 0) je jediný stacionární bod f a v tomto bodě má f lokální minimum s hodnotouf(0, 0) = 0. Avšak bod (0, 0) není globální minimum f , neboť např. f(2, 3) = −5; vizObrázek č. 19.
5.4 Příklad: Metoda nejmenších čtvercůPředpokládejme, že máme k dispozici sadu dat (xi, yi)ni=1 a chceme nalézt lineární kom-binaci daných funkcí f1, f2, . . . , fm, tj. funkci
f =m∑i=1
cifi ,
tak, aby funkční hodnoty funkce f v bodech xi co nejlépe odpovídaly hodnotám yi prokaždé i ∈ n. Úkolem je určit neznámé koeficienty lineární kombinace: c1, c2, . . . , cm. Před-pokládejme, že m ≤ n. To není na závadu, neboť typicky je množství dat n mnohem většínež počet funkcí m.
Funkce fi mohou být např. voleny tak, že fi(x) = xi. V tomto případě prokládáme datapolynomiální křivkou. Funkce f1, f2, . . . , fm nelze volit úplně libovolně, jedna podmínkasvazující funkce f1, f2, . . . , fm a data x1, x2, . . . , xn nám vypadne z výpočtu dále.
Metoda nejmenších čtverců spočívá v myšlence minimalizovat kvadrát celkové chybymezi yi a f(xi). Přesněji, hledáme konstanty c1, c2, . . . , cm tak, aby hodnota
F (c) ··=n∑i=1
(yi − f(xi)
)2=
n∑i=1
(yi − (Ac)i
)2= ‖y −Ac‖2
2
byla co nejmenší. Zde jsme označili
(Ac)i =m∑j=1
fj(xi)cj .
Matice A ∈ Rn,m je dána hodnotami jednotlivých funkcí f1, f2, . . . , fm v bodech x1, x2 . . . , xn:
Metodu nejmenší čtverců tedy můžeme shrnout taktominimalizuj ‖y −Ac‖2
2 ,
vůči c = (c1, c2, . . . , cm) ∈ Rm ,
kde y = (y1, y2, . . . , yn) ∈ Rn a Aij = fj(xi) jsou dány .(50)
Aplikujme analytický postup pro hledání extrémů funkcí více proměnných. Předpoklá-dejme navíc, že matice A definovaná vztahem (49) má plnou hodnost, tzn. h(A) = m(předpokládáme m ≤ n). Nejprve hledejme gradient funkce F . Pro parciální derivaci platí
(∂cjF )(c) = −2n∑i=1
(yi − (Ac)i
)Aij = −2
n∑i=1
(AT )jiyi + 2n∑i=1
(AT )ji(Ac)i =
= −2(ATy)j + 2(ATAc)j .
92
Pro gradient proto platí(∇cF )(c)T = −2ATy + 2ATAc , (51)
kde spodní index u symbolu ∇c nám připomíná, vůči kterým proměnným derivujeme.Hledáme bod c, kde ∇cF (c) = 0. Protože A má dle předpokladu plnou hodnost, je maticeATA ∈ Rm,m regulární (rozmyslete si – Cvičení 5.1). Z rovnosti (51) potom dostávámeřešení
c = (ATA)−1ATy . (52)
Hessovou maticí funkce F je shodou okolností právě matice ATA (až na multiplikativníčíselný faktor). Skutečně, pro prvek Hessovy matice funkce F platí
∂2cicjF (c) = 2(ATA)ji .
Matice ATA je pozitivně definitní, neboť pro x ∈ Rm je
xTATAx = (Ax)T (Ax) = ‖Ax‖2 ≥ 0
a rovnost nastává pouze pro x = 0, protože je ATA regulární.Shrnutí: Úloha nejmenších čtverců (50) s maticí (49), která má plnou hodnost, má
řešení určené rovností (52).Cvičení 5.1: Buď A ∈ Rn,m, m ≤ n a h(A) = m. Dokažte, že matice ATA ∈ Rm,m jeregulární.
-2 -1 0 1 2
-2
-1
0
1
2
x
y
Obrázek 20: Ukázka metody nejmenších čtverců.
93
5.5 Numerické hledání extrémů: spádová metoda*If I have seen further it is by standing on the shoulders of giants. Isaac Newton
V této sekci si ukážeme obecný postup při numerickém hledání lokálních minim funkcí f : Rn → Rbez omezujících podmínek na proměnné xi, i = 1, 2, . . . , n. Řešíme tedy úlohu
minimalizuj f(x) , (53)
kde f : Rn → R a x probíhá všechny možné hodnoty x ∈ Df . Dále požadujeme, aby f byladvakrát spojitě diferencovatelná32.
Řešení hledáme iterativně. V tomto odstavci shrneme obecný postup tzv. spádových metod.V každé iteraci se snažíme snížit hodnotu minimalizované funkce f . Nechť je dáno x(1) ∈ Df .Sestavíme posloupnost x(k), k = 1, 2, . . ., podle rekurentního předpisu
x(k+1) = x(k) + t(k)∆x(k) ,
kde ∆x(k) je vhodně zvolený vektor (směr poklesu) a t(k) délka tzv. kroku. Následující členvždy musí být zvolen tak, aby f(x(k+1)) < f(x(k)), samozřejmě vyjma případu, kdy x(k) je jižoptimální. Běh typické spádové metody lze tedy popsat následovně (odpustíme si horní indexy,budeme mluvit o jednom kroku):
Nechť je dáno x ∈ Df .
1. Urči směr ∆x.
2. Zvol velikost kroku t > 0.
3. Napočti x+ t∆x a ulož ho do x.
Předchozí kroky opakuj dokud není splněno kritérium pro zastavení smyčky. Praktické kritériumpro zastavení může být například dostatečná blízkost nule normy gradientu.
Konkrétní volbě směru ∆x se budeme věnovat podrobněji níže. V tento okamžik pouzeuveďme, že pro malá t přibližně platí
f(x+ t∆x) ≈ f(x) + t∇f(x) ·∆x. (54)
Pokud chceme v kroku funkční hodnotu zmenšit, musíme krok ∆x vždy volit tak, aby
∇f(x) ·∆x < 0.
Také ve zbytku popisu algoritmu předpokládáme, že v každém kroku ∇f(x) 6= 0. Pokud bygradient byl nulový, pak běh algoritmu již skončil.
Nyní se podívejme podrobněji na hledání velikosti kroku t. Nechť máme bod x a již jsmezvolili směr ∆x. Ideálně bychom chtěli t > 0 zvolit tak, aby v tomto bodě bylo nabyto minimumfunkce jedné proměnné s > 0,
s 7→ f(x+ s∆x)
Jednou z možností je tedy nalézt minimum této funkce analyticky. Pokud je funkce f konvexní,tak takový bod existuje nejvýše jeden. Další možností je na tento jednorozměrný problém nasadit
32Tj. všechny její parciální derivace až do druhého řádu včetně jsou spojité na Df .
94
t
f(x+ t∆x)
Obrázek 21: Zpětné krokování. Na obrázku je znázorněn řez funkce nad přímkou x+t∆x (černě),tečna f(x) + t∇f(x) ·∆x (modře) a přípustná mez poklesu f(x) + αt∇f(x) ·∆x (červeně).
známé numerické metody z BI-ZMA (např. půlení intervalu či Newtonova metoda aplikovaná naderivaci). V praxi se ovšem často používá tzv. zpětné krokování (backtracking).
Algoritmus zpětného krokování je následující: jsou dány f , směr ∆x, bod x ∈ Df a parametryα ∈ (0, 1/2), β ∈ (0, 1). Polož t := 1. Dokud f(x + t∆x) > f(x) + αt∇f(x) ·∆x změň t na βt.Vrať t. Pro ilustraci uvádíme obrázek 21.
Parametr α kontroluje, jaký pokles jsme ochotni akceptovat. Parametr β pak udává, jak rychlezmenšujeme prvotní t (proto zpětné krokování). Poznamenejme ještě, že algoritmus zpětnéhokrokování jistě úspěšně skončí, jak je vidět z rovnice (54).
Nyní si rozeberme možné způsoby volby směru. Předpokládejme, že jsme v bodě x a vydámese malým krokem směrem v. Potom lineární aproximace změny funkční hodnoty je
f(x+ v) ≈ f(x) +∇f(x) · v .
Jak již bylo řečeno, směry ve kterých dojde k poklesu funkční hodnoty splňují ∇f(x) · v < 0.Tuto veličinu můžeme udělat libovolně hodně zápornou, pokud nenaklademe nějaká omezení nav. Musíme tuto úlohu proto zpřesnit. Zvolme normu ‖ · ‖ na Rn. Směr nejprudšího poklesu je pakdán řešením úlohy
∆x = argmin ∇f(x) · v | ‖v‖ ≤ 1 .
Pro reálnou symetrickou pozitivně definitní matici P ∈ Rn,n můžeme definovat normu
‖v‖P ··=√vTP v , v ∈ Rn .
Směr největšího poklesu vzhledem k této normě je pak dán
∆x = −P−1∇f(x)T .
Důkaz pro případ P = E. Uvažme tedy obecně úlohu minimalizovat funkci
Vzpomeňme si, že ze Schwarzovy nerovnosti plyne nerovnost |g(v)| ≤ ‖c‖‖v‖, což za uvedenépodmínky na vektory v implikuje |g(v)| ≤ ‖c‖. Této meze ale snadno dosáhneme volbami
v+ = c
‖c‖a v− = − c
‖c‖.
Důkaz pro obecný případ. Uvažme funkci g(v) = cT v, v ∈ Dg = Rn, pro zadaný vektor c ∈ Rn.Hledáme řešení úlohy
minimalizuj g(v) = cT v ,
za podmínky vTP v = 1 ,v ∈ Rn .
kde P je (reálná) symetrická pozitivně definitní matice.Za těchto předpokladů víme, že P má všechna vlastní čísla kladná a je diagonalizovatelná, tj.
P = Udiag (λ1, . . . , λn)UT ,
kde λi > 0, i ∈ n, jsou vlastní čísla matice P a matice U je (reálná) a ortogonální (tj. UT = U−1,resp. UUT = E).
Definujme matici P 1/2 předpisem
P 1/2 := Udiag (λ1/21 , . . . , λ1/2
n )UT .
Tato matice splňuje P 1/2P 1/2 = P , je (reálná) symetrická.Naší minimalizační úlohu proto můžeme přepsat do následujícího tvaru,
minimalizuj g(v) =((P 1/2)−1c
)TP 1/2v ,
za podmínky (P 1/2v)T (P 1/2v) = 1 ,v ∈ Rn .
Pokud provedeme změnu souřadnic u := P 1/2v, tak dostaneme minimalizační úlohu tvaruminimalizuj g(u) =
((P 1/2)−1c
)Tu ,
za podmínky uTu = 1 .y ∈ Rn .
O té z předchozího případu víme, že nabývá maxima a minima v
u+ = (P 1/2)−1c
‖(P 1/2)−1c‖a u− = − (P 1/2)−1c
‖(P 1/2)−1c‖.
V původních proměnných pak v
v+ = P−1c
‖(P 1/2)−1c‖a v− = − P−1c
‖(P 1/2)−1c‖.
96
Zvolíme-li za normu Euklidovskou normu ‖ · ‖2, pak dostaneme tzv. gradientovou metodu.Vzhledem k Euklidovské normě tedy platí, že směr největšího poklesu funkce f v bodě x jeskutečně −∇f(x).Příklad 5.30 (Gradientová metoda): Očividnou volbou pro volbu směru kroku při minimalizacije krok ve směru záporně vzatého gradientu,
∆x(k) ··= −∇f(x(k)) .
Je tato volba ale nejlepší možná? Ukazuje se, že pokud máme dostatek informací o funkci f ,můžeme dosáhnout lepších výsledků s pomocí Newtonovy metody.Příklad 5.31 (Newtonova metoda): Newtonova metoda volí směr poklesu jako
∆x = −(∇2f(x)
)−1(∇f(x))T .
V každém bodě tedy hledá směr nejmenšího poklesu vzhledem k normě ‖ · ‖P , kde P je Hessiánfunkce f v bodě x.
5.6 Vícerozměrná optimalizaceTeorie optimalizace je velmi obsáhlý obor s přesahem do mnoha dalších matematických inematematických odvětví. Začněme nejprve formulací obecné úlohy nelineárního pro-gramování (NLP):
minimalizuj f(x) ,za podmínek gj(x) ≤ 0, j ∈ m,
hk(x) = 0, k ∈ p.(55)
Vektor x = (x1, . . . , xn) se zde nazývá vektorem optimalizačních proměnných, funkcef : Rn → R je objektivní nebo účelová funkce. Funkce gj : Rn → R, j ∈ m, udávajínerovnostní podmínky a funkce hk : Rn → R, k ∈ p, rovnostní podmínky. Pro jednoduchostbudeme předpokládat, že jsou všechny funkce f , gj, j ∈ m, hk, k ∈ p definovány nacelém Rn. Později přidáme další předpoklady.Poznámka 5.32: Počet nerovnostních a rovnostních podmínek udávají čísla m ∈ N0 ap ∈ N0. Pokud je m = 0 nebo p = 0, symbol 0 chápeme jako prázdnou množinu. V případě,že např. m = 0, úloha (55) má pouze rovnostní podmínky a v takovém případě mluvíme otzv. vázaných extrémech f . Naopak, je-li p = 0 a navíc požadujeme xi ≥ 0, i ∈ n, označujese úloha (55) jako symetrická úloha NLP. Další speciální instance úlohy (55) jsou úlohytzv. lineárního nebo kvadratického programování.
Označme
M ··= x ∈ Rn | (∀j ∈ m)(gj(x) ≤ 0) ∧ (∀k ∈ p)(hk(x) = 0) (56)
tzv. množinu přípustných řešení úlohy (55). Řešit úlohu (55) znamená najít optimálníhodnotu
p∗ = inff(x) | x ∈M.
97
Toto infimum může obecně nabývat i hodnoty p∗ = +∞ (o problému pak říkáme, že jenesplnitelný33) a p∗ = −∞ (problém je zdola neomezený). Optimální hodnota danéhoproblému je dána jednoznačně, na rozdíl od optimálních bodů, což jsou body x∗ ∈ Msplňující
f(x∗) = p∗.
Optimální bod úlohy (55) nemusí existovat.Příklad 5.33: Ilustrujme výše zavedené pojmy na velmi jednoduchém příkladě. Uvažmeproblém minimalizace funkce f(x) = 1 + sin2(x) s nerovnostními podmínkami g1(x) =x− π ≤ 0 a g2(x) = −π − x ≤ 0. Rovnostní podmínky pro jednoduchost neuvažujeme.
Množinou přípustných bodů jeM = 〈−π, π〉. Dále očividně (z vlastností funkce sinus)je optimální hodnotou číslo p∗ = 1 a za optimální body lze volit x∗ z množiny −π, 0, π.Tato situace je znázorněna na Obrázku 22.
x
y = f(x)
−π π
1
M
Obrázek 22: Optimální hodnotou je 1 a optimálními body jsou −π, 0 a π.
Ještě než se pustíme do teoretického výkladu, uvedeme několik konkrétních problémů,které lze zformulovat jakožto obecné úlohy NLP. Upozorňujeme, že tento seznam nenížádným způsobem vyčerpávající. Pouze chceme čtenáři demonstrovat šíři problémů, kteroutyto úlohy popisují.Příklad 5.34 (Nejmenší čtverce, znovu): Problém nejmenších čtverců, který jsme již po-psali dříve, je optimalizační úlohou bez omezení. Cílem je minimalizovat funkci
f(x) = ‖Ax− b‖22 =
k∑i=1
((Ax)i − bi
)2,
kde A ∈ Rk,n, b ∈ Rk jsou zadaná matice, resp. vektor, a x ∈ Rn je optimalizační proměnná.O krok obecnější úlohou je úloha vážených nejmenších čtverců. Každému měření (viz
původní motivace), dejme tomu itému, je přiřazena navíc ještě váha wi > 0. Cílem pak jeminimalizovat funkci
f(x) =k∑i=1
((Ax)i − bi
)2wi.
33Tento případ odpovídá situaci kdyM = ∅
98
Příklad 5.35 (Lineární programování – dietologický problém): Zdravá strava musí ob-sahovat alespoň m různých živin v množství b1, . . . , bm (např. v jednotkách hmotnosti zajednotku času). Takovouto stravu lze sestavit z x1, . . . , xn (opět hmota za čas) různýchjídel. Jednotka j-tého jídla obsahuje aij živiny i a stojí cj (jednotek peněz), i = 1, . . . ,m aj = 1, . . . , n.
Úkol je nalézt co nejlevnější dietu (jídelníček) splňující podmínku na zdravost. Úlohatedy zní34
minimalizuj cTx,
za podmínek Ax ≥ b,
x ≥ 0.
Příklad 5.36 (Lineární separace dat): Uvažme dvě množiny bodů
V = v1, . . . , vK ⊂ Rn, W = w1, . . . , wL ⊂ Rn.
Nalezněte nadrovinuaTx+ b = 0, a ∈ Rn, b ∈ R,
oddělující V a W , tj.
aTvi + b ≥ 0, i = 1, . . . , K, (57)aTwi + b ≤ 0, i = 1, . . . , L. (58)
Samozřejmě není zajištěno, že takováto nadplocha existuje. Pokud existuje, snažme senalézt takovou, která odděluje skupiny V a W s co největší mezerou.
Normálový vektor, a ∈ Rn, je dán jednoznačně až na konstantní číselný násobek(škálování). Využijme této nejednoznačnosti a požadujme, aby separační nadrovina byla„uprostřed“ mezery. To znamená, že pro jistá konkrétní i0 ∈ K a j0 ∈ L platí
aTvi0 + b = 1 > 0 a aTwj0 + b = −1 < 0 .
Tato vi0 a wj0 leží na hranici oddělovací mezery, často se nazývají podpůrné vektory (supportvectors, odtud často používaný název support vector machine v kontextu strojového učení).
Ze situace popsané v předchozím odstavci plyne, že šířka separační mezery je 2/‖a‖2.Skutečně, uvážíme-li například vektor vi0 + ta, pak z podmínky
aT (vi0 + ta) + b = −1
plyne t ‖a‖22 + 1 = −1 a tedy t = −2/‖a‖2
2. Proto
dist(vi0 , vi0 + ta) = ‖ta‖2 = 2‖a‖2
.
34V zápise používáme standardní vektorové nerovnosti. Pro dva vektory a, b ∈ Rn platí a ≥ b, právěkdyž platí ai ≥ bi pro každé i = 1, . . . , n. Podobně i pro další typy nerovností.
99
Protože vi0 a wj0 leží na hranici separační mezery, jsou nejblíže separační nadrovině,musí i pro všechna i ∈ K a j ∈ K platit
aTvi + b ≥ 1 ,aTwj + b ≤ −1 .
Šířku mezery chceme maximalizovat, proto za objektivní funkci bereme
f(a, b) = 12‖a‖
22 , (a, b) ∈ Rn × R .
a naším cílem je její hodnotu minimalizovat. Tím je tato optimalizační úloha zcela po-psána.Příklad 5.37 (Sudoku): Tento příklad slouží jako drobná poznámka ukazující jaké dalšítypy optimalizačních úloh může čtenář potkat a že se občas nemusí jednat o optimalizačníproblémy v pravém slova smyslu.
Definiční obory funkcí v (55) mohou být dále omezeny například na celá čísla (integerprogramming) nebo dokonce pouze hodnoty 0 a 1 (binary programming). Dále je vhodnési uvědomit, že nemusí být na první pohled jasné, jestli množina M přípustných řešení(viz (56)) je neprázdná. Případný algoritmus řešící naší optimalizační úlohu lze tedy použíti na hledání nějakého přípustného řešení (tj. prakticky bez objektivní funkce). Oba tytojevy si ukážeme na případu známého hlavolamu Sudoku, viz také následující Příklad 5.38.
Pravidla hlavolamu Sudoku jsou jistě všem dobře známá. Poznamenejme pouze, že domřížky 9× 9 políček, rozdělených na 9 čtverců v mřížce 3× 3 musíme vyplnit cifry 1, . . . , 9tak, aby v každém řádku, sloupci a čtverci byly právě všechny cifry 1, . . . , 9.
Stav Sudoku mřížky popíšeme pomocí tenzoru
xijk ∈ 0, 1, i, j, k ∈ 9 .
Jinak řečeno, xijk říká, zda v i-tém řádku a j-tém sloupci tabulky je cifra k.Nyní musíme sestavit podmínky na správnost řešení.
i) V každém políčku je právě jedna cifra,
∀i, j ∈ 9 :9∑
k=1xijk = 1 .
ii) V každém řádku jsou všechny cifry,
∀i, k ∈ 9 :9∑j=1
xijk = 1 .
iii) V každém sloupci jsou všechny cifry,
∀j, k ∈ 9 :9∑i=1
xijk = 1 .
100
iv) V každém čtverci jsou všechny cifry,
∀I, J ∈ 1, 4, 7, k ∈ 9 :I+2∑i=I
J+2∑j=J
xi,j,k = 1 .
v) Předepsané zadání, je dána množina indexů I0 ⊂ 9× 9 pro které jsou xijk, (i, j) ∈ I0předepsány.
Příklad 5.38 (Grafové problémy): Optimalizační metody lze, mimo jiné, aplikovat nacelou řadu zajímavých grafových problémů. V těchto poznámkách se jim věnovat nebudeme.Pouze čtenáře odkážeme na přehlednou stránku s příklady od Nathanna Cohena.
Formulace obecné úlohy NLP vyžaduje hledání globálních extrémů, což je přirozenýpožadavek z praxe. Obecně tento problém ovšem bez dalších předpokladů (například kon-vexnosti) nelze plně vyřešit. My zde budeme chtít opět využít možností diferenciálníhopočtu funkcí více proměnných. Tento aparát dává ovšem pouze lokální odpovědi.Definice 5.39 (Lokální extrém vzhledem k množině): Řekneme, že funkce f : Rn → R máv bodě x∗ ∈ M ⊂ Df ostré lokální minimum vzhledem k množině M právě tehdy,když existuje okolí Hx∗ bodu x∗ takové, že
(∀x ∈ (Hx∗ ∩M) \ x∗) (f(x∗) < f(x)) .
Analogicky lze zformulovat definici ostrého lokální maxima vzhledem k množině, resp.neostré varianty extrémů.
V případě úlohy (55) mluvíme o x∗, který je (ne)ostrým lokálním minimem objektivnífunkce f vzhledem k množině přípustných řešeníM, jako o bodu (ne)ostrého lokálníhominima úlohy (55) nebo stručně jako o lokálním řešení úlohy (55). Uvědomte si, želokální řešení obecné úlohy NLP nemusí být jejím optimálním bodem.
K přechodu od lokálních odpovědí ke kýženým globálním lze využít např. konvexnosti(přesný význam této věty vyjasníme později). Nicméně žádný univerzální a přitom snadnopoužitelný postup k nalezení řešení úlohy (55) neexistuje. Vždy je nutné zohlednit specifikakonkrétního problému. Velká třída úloh NLP spadá např. do třídy takzvaných konvexníchproblémů, pro které existují efektivní algoritmy hledající jejich řešení. Více k tomuto tématučtenář najde např. v knize [2]. Další speciální úlohy zahrnují tzv. lineární a kvadraticképrogramování, kde existují velmi efektivní algoritmy založené na propracované matematickéteorii [10].
Naším cílem bude odvodit postačující podmínky pro nalezení lokálního řešení obecnéúlohy NLP podobných těm z Věty 5.27. Takových podmínek existuje celá řada pro různésituace a s různými předpoklady; viz např. článek [9]. My se zde omezíme na odvozeníjediné věty s postačujícími podmínkami pro nalezení lokálního řešení obecné úlohy NLP,které jsou dostatečně obecné a při tom poměrně snadno aplikovatelné.
Pro formulaci postačujících podmínek budeme potřebovat zavést tzv. Lagraneovu funkci.Tato funkce je také důležitým prostředkem v tzv. teorii duality, kterou ovšem v našem vý-kladu úplně vypustíme. Čtenář se zájmem o tuto problematiku může nahlédnout např. doknihy [2].
Definice 5.40 (Lagrangeova funkce): Funkci L : M × (R+0 )m × Rp → R definovanou
vztahemL(x;λ, µ) := f(x) +
m∑j=1
λjgj(x) +p∑
k=1µkhk(x)
nazýváme Lagrangeova funkce pro úlohu (55). Připomeňme, že R+0 = 〈0,+∞). Koefici-
entyλ = (λ1, . . . , λm) a µ = (µ1, . . . , µp)
nazýváme Lagrangeovy multiplikátory.Poznámka 5.41: Jelikož budeme chtít používat diferenciální počet, bude často nutnépředpokládat existenci otevřené nadmnožiny M ⊃M, na níž budou všechny funkce f , gj,j ∈ m, hk, k ∈ p diferencovatelné. V takovém případě rozšiřujeme definiční obor funkce Lna M × (R+
0 )m × Rp.Dále bude nutné rozlišit indexy, pro které nerovnostní podmínky úlohy (55) platí jako
rovnosti.Definice 5.42 (Množina aktivních omezení): Pro bod x ∈ M definujeme množinu ak-tivních omezení
B(x) := j ∈ m | gj(x) = 0.
Nyní je již vše připravené a můžeme zformulovat postačující podmínku pro nalezenílokálního řešení obecné úlohy NLP. Podmínky z druhého bodu věty níže jsou spojovány sejmény Karush, Kuhn a Tucker (40. a 50. léta 20. století).Věta 5.43 (Postačující podmínka existence ostrého lokálního minima): Nechť funkce f ,gj, j ∈ m a hk, k ∈ p mají spojité všechny druhé parciální derivace na nějaké otevřenénadmnožině M ⊃M. Pokud trojice (x∗, λ∗, µ∗) ∈M× (R+
0 )m × Rp splňuje podmínky:
(i) (optimalita) ∇xL(x∗;λ∗, µ∗) = 0,
(ii) (KKT) pro každé j ∈ m platí λ∗jgj(x∗) = 0,
(iii) (podmínka 2. řádu) pro každý vektor 0 6= z ∈ Rn splňující
∇gj(x∗) · z = 0, pro ∀j ∈ B(x∗), pro která λ∗j 6= 0,∇hk(x∗) · z = 0, pro ∀k ∈ p,
platízT∇2
xL(x∗;λ∗, µ∗)z > 0,
potom je x∗ bodem ostrého lokálního minima úlohy (55).Poznámka 5.44: Všimněte si, že předpoklad (x∗, λ∗, µ∗) ∈ M × (R+
aλ∗j ≥ 0, ∀j ∈ m, (spolu s KKT tzv. komplementarita).
Dále indexy x ve výrazech ∇xL(x∗;λ∗, µ∗) a ∇2xL(x∗;λ∗, µ∗) naznačují, že parciálně deri-
vujeme jen v proměnných x1, . . . , xn, tzn., že
∇xL(x∗;λ∗, µ∗) = ∇f(x∗) +m∑j=1
λ∗j∇gj(x∗) +p∑
k=1µ∗k∇hk(x∗) ∈ Rn
a podobně
∇2xL(x∗;λ∗, µ∗) = ∇2f(x∗) +
m∑j=1
λ∗j∇2gj(x∗) +p∑
k=1µ∗k∇2hk(x∗) ∈ Rn,n.
Důkaz. Větu dokážeme sporem: Nechť x∗ ∈ M není bodem ostrého lokálního minimaúlohy (55). Potom v libovolně malém okolí x∗ vždy najdeme bod zM různý od x∗, v němžmá f funkční hodnotu menší nebo rovnou f(x∗). Tzn., že můžeme najít posloupnost bodůxn ∈M takovou, že pro každé n ∈ N je xn 6= x∗, dále limn→∞ xn = x∗ a
f(xn) ≤ f(x∗), ∀n ∈ N.
Podle Bolzanovy–Weierstrassovy věty 5.10 existuje podposloupnost (xn`)∞`=1 posloupnosti(xn)∞n=1 taková, že
lim`→∞
xn` − x∗
‖xn` − x∗‖= η ∈ Rn.
Všimněte si, že η 6= 0, neboť ‖η‖ = 1.Podle předpokladů věty mají všechny funkce f gj, j ∈ m, hk, k ∈ p spojité parciální
derivace, a proto podle věty 5.21 existují vektory θ(f)` , θ(gj)
Vynásobíme-li tuto rovnost skalárně vektorem η a využijeme-li (59) a (61), dostaneme
0 ≥ ηT∇f(x∗) = −m∑j=1
λ∗jηT∇gj(x∗)
Z předpokladu (ii) vyplývá, že λ∗j = 0 pro každé j /∈ B(x∗). Poslední nerovnosti proto lzeupravit,
0 ≥ −∑
j∈B(x∗)λ∗jη
T∇gj(x∗),
odkud díky nerovnostem (60) a λ∗j ≥ 0, j ∈ m, docházíme k závěru, že
λ∗jηT∇gj(x∗) = 0, ∀j ∈ B(x∗).
Tedy pro ∀j ∈ B(x∗), pro která je λ∗j 6= 0, platí
ηT∇gj(x∗) = 0.
Podle předpokladu (iii) vyplývá z poslední rovnosti a z (61), že
ηT∇2xL(x∗;λ∗, µ∗)η > 0. (62)
Nyní znovu aplikujeme předchozí závěry, podle kterých máme
0 ≥ f(xn`)− f(x∗)
= L(xn` ;λ∗, µ∗)− L(x∗;λ∗, µ∗) +m∑j=1
λ∗j (gj(x∗)− gj(xn`)) +p∑
k=1µ∗k (hk(x∗)− hk(xn`))
= L(xn` ;λ∗, µ∗)− L(x∗;λ∗, µ∗)−m∑j=1
λ∗jgj(xn`) ≥ L(xn` ;λ∗, µ∗)− L(x∗;λ∗, µ∗).
Využijeme-li toho, že L má spojité druhé parciální derivace podle x1, . . . , xn, pak víme zvěty 5.21, že existuje vektor θ(L)
` na spojnici bodů xn` a x∗ takový, že
0 ≥ L(xn` ;λ∗, µ∗)− L(x∗;λ∗, µ∗)
= (xn` − x∗)T∇xL(x∗;λ∗, µ∗) + 12(xn` − x∗)T∇2
xL(θ(L)` ;λ∗, µ∗)(xn` − x∗).
Podle předpokladu (i) je první člen nula. Vydělíme-li poslední výraz členem 12‖(xn`−x
∗)‖2
a pošleme `→∞, dostaneme
0 ≥ ηT∇2xL(x∗;λ∗, µ∗)η,
což je spor s (62).
104
Příklad 5.45 (Jedna nerovnostní vazba): Nalezněme lokální ostrá minima funkce f(x, y) =x3 + y2 vzhledem k nerovnostní podmínce g(x, y) = x2 + y2 − 1 ≤ 0.
Projděme si podrobně celé řešení této úlohy. Lagrangeova funkce má v tomto případětvar L(x, y;λ) = x3 + y2 + λ(x2 + y2 − 1). Řešíme proto soustavu rovnic a nerovnic
V prvním případě je naše jediná vazba aktivní, tj. platí rovnost g(x1, y1) = 0. Pro gradient∇g a Hessovu matici ∇2
(x,y)L v tomto bodě platí
∇g(x1, y1) = (−2, 0) a ∇2(x,y)L(x1, y1;λ1) =
(−3 00 5
).
Konečně vektor z = (z1, z2)T ∈ R2 splňuje podmínku
∇g(x1, y1)z = (−2, 0)z = −2z1 = 0,
právě když z1 = 0. Pro všechny takovéto nenulové vektory z = (0, z2)T proto platí
(0, z2)(−3 00 5
)(0z2
)= 5z2
2 > 0.
Díky Větě 5.43 můžeme nyní učinit závěr, že bod (−1, 0) je bodem ostrého lokálního minimafunkce f vzhledem k dané vazbě.
V druhém případě (tedy (x2, y2) = (0, 0) a λ2 = 0) není vazba aktivní. Dále pro Hessovumatici ∇2
(x,y)L(x2, y2;λ2) platí
∇2(x,y)L(x2, y2;λ2) =
(0 00 2
).
Nyní ale neplatí podmínka druhého řádu ve Větě 5.43. Z toho ovšem neplyne, že v bodě(0, 0) není ostré lokální minimum. V tomto případě se ovšem stačí jednoduše podívat nakřivku γ(t) = (t, 0), která pro všechna t ∈ (−1, 1) patří doM a prochází kritickým bodem(0, 0) = γ(0). Funkce f v bodech této křivky splňuje f(γ(t)) = t3, a v nule mění znaménko.Není splněna podmínka v definici extrému.
Grafickou ilustraci k této úloze naleznete na Obrázku č. 23.
105
−1−0.5
00.5
1
−1−0.5
00.5
1−1
0
1
xy
z=f
(x,y
)
Obrázek 23: Ilustrace k Příkladu č. 5.45.
Příklad 5.46 (Jedna rovnostní vazba): Nalezněme lokální ostrá minima funkce f(x, y, z) =x3 + y2 + z vzhledem k rovnostní podmínce h(x, y, z) = x2 + y2 − z = 0.
Lagrangeova funkce je v tomto případě
L(x, y, z;µ) = x3 + y2 + z + µ(x2 + y2 − z).
Řešení soustavy
∇L(x, y, z;µ) = 0, h(x, y, z) = 0,
pro čtyři neznámé x, y, z a µ, existují dvě
(x1, y1, z1, µ1) =(−2
3 , 0,49 , 1
),
(x2, y2, z2, µ2) = (0, 0, 0, 1) .
Postupně pojďme oba prozkoumat.Pro Hessovu matici a gradient vazby v prvním bodě ihned dostáváme
∇2(x,y,z)L(x1, y1, z1;µ1) =
−2 0 00 4 00 0 0
∇h(x1, y1, z1) =
(−4
3 , 0,−1).
Pro každý nenulový vektor u = (3u1, u2,−4u1)T platí
uT∇2(x,y,z)L(x1, y1, z1;µ1)u = −18u2
1 + 4u22.
Tato kvadratická forma je indefinitní a v tomto bodě proto extrém není. To lze vidět ipřímo z definici, podíváme-li se na hodnoty funkce f podél křivek
γ1(t) =(−2
3 + 3t, 0, 49 − 4t+ 9t2
)a γ2(t) =
(−2
3 , t,49 + t2
),
106
pro t na okolí bodu 0.Pro Hessovu matici a gradient vazby v druhém bodě pak dostáváme
∇2(x,y,z)L(x2, y2, z2;µ2) =
2 0 00 4 00 0 0
∇h(x2, y2, z2) = (0, 0,−1) .
Pro každý nenulový vektor u = (u1, u2, 0)T platí
uT∇2(x,y,z)L(x2, y2, z2;µ2)u = 2u2
1 + 4u22 > 0.
V tomto bodě má proto naše funkce ostré lokální minimum vzhledem k zadané vazbě.
5.7 Konvexní úloha nelineárního programováníPřipomeňme, že množinuM ⊂ Rn nazýváme konvexní, právě když pro každé dva její bodyleží jejich spojnice také v množině M . To znamená, že pro každé x, y ∈ M a θ ∈ 〈0, 1〉 jeθx+ (1− θ)y ∈M .Definice 5.47: Funkci f : Rn → R nazýváme konvexní, právě když Df je konvexnímnožina a pro každé x, y ∈ Df a θ ∈ (0, 1) platí
f(θx+ (1− θ)y) ≤ θf(x) + (1− θ)f(y) .
Nahradíme-li nerovnost výše ostrou nerovností, nazýváme f ryze konvexní. Funkce f jekonkávní, resp. ryze konkávní, právě když je −f konvexní, resp. ryze konvexní.
Geometrická ilustrace konvexnosti funkce je na obrázku (24). Podstatnou výhodoutěchto definic oproti těm používaným v BI-ZMA je, že nevyžadují diferencovatelnost uva-žované funkce. Např. funkce |x| je podle této definice konvexní na celém R.
f
x y
Obrázek 24: Konvexní funkce jedné reálné proměnné.
Důležitou vlastností konvexních funkcí je, že jejich lokální minima jsou automatickyglobální.
107
Lemma 5.48: Nechť f : Rn → R je konvexní. Potom každé lokální minimum funkce f(vzhledem k Df ) je globální minimum funkce f (vzhledem k Df ).
Důkaz. Sporem: nechť x∗ ∈ Df je lokální minimum f a současně není globální. Tzn., žeexistuje y ∈ Df takové, že f(y) < f(x∗). Z konvexnosti f musí pro každé θ ∈ (0, 1) být
Tzn., že v libovolně malém okolí x∗ (vezmi θ blízko 1) existuje bod, v němž má f menšíhodnotu než f(x∗). To je spor s tím, že x∗ je lokální minimum f .
Lemma 5.49: Má-li ryze konvexní funkce f : Rn → R lokální minimum v bodě x∗, je x∗její jediné globální minimum.
Důkaz. Proveďte jako cvičení.
Ještě se naposledy vraťme k obecné úloze NLP (55). Je jasné z příslušných definic,že každé řešení úlohy (55) je i její lokální řešení. Opačná implikace neplatí. Pokud alenavíc přidáme předpoklad konvexnosti (viz větu níž), lze implikaci už obrátit a v takovémpřípadě můžeme využít postačujících podmínek z věty 5.43. Nutno dodat, že předpokladkonvexnosti je poměrně omezující podmínka navíc.Věta 5.50 (lokální NLP + konvexita ⇒ NLP): Nechť množina přípustných řešeníM jekonvexní a f : Rn → R je konvexní objektivní funkce definovaná na M. Je-li x∗ ∈ Mlokální minimum f vzhledem kM, potom x∗ je řešením úlohy (55).
Důkaz. Vyplývá okamžitě z Lemma 5.48.
5.8 Poznámky a odkazyZájemce o podrobné studium problematiky Fourierových řad odkazujeme na klasickoumonografii [13].
5.9 CvičeníCvičení 5.2: Dokončete důkaz Věty 5.6.Cvičení 5.3: Dokažte tvrzení uvedené v Poznámce 5.9.Cvičení 5.4: Dokažte, že pro dva body a, b ∈ V v normovaném vektorovém prostoru(V, ‖ · ‖) existují disjunktní okolí bodu a a b.Cvičení 5.5: Vedle hromadných bodů množiny se zavádí další pojmy (tzv. topologické,závislé pouze na pojmu okolí). Uvažme normovaný vektorový prostor (V, ‖ · ‖) a množinuM ⊂ V .
a) Prvek a ∈M nazýváme izolovaným bodem množiny M , právě když existuje okolí Ha
bodu a splňující Ha ∩M = a.
108
b) Prvek a ∈ M nazveme vnitřním bodem množiny M , právě když existuje okolí Ha
bodu a splňující Ha ∩M = Ha. Množinu všech vnitřních bodů množiny M značíme36
symbolemM. Pokud je množinaM tvořena pouze vnitřními body, tj. pokudM = M,nazýváme ji otevřenou.
c) Uzávěr množinyM , značíme37 M , je tvořen všemi body a ∈ V , pro které je Ha∩M 6= ∅pro každé okolí Ha bodu a. Pokud platí M = M , pak M nazýváme uzavřenou.
d) Hranicí množiny M nazýváme množinu ∂M ··= M rM.
Poznamenejme, že prázdnou množinu chápeme jako uzavřenou i otevřenou zároveň. Jakádalší podmnožina množiny V má tuto vlastnost?
Dokažte následující tvrzení:
i) Průnik dvou otevřených množin je otevřená množina.
ii) Sjednocení libovolného systému otevřených množin je otevřená množina.
iii) Je-li M ⊂ V otevřená množina, pak její doplněk V rM je uzavřená množina.
iv) M je největší38 otevřená množina obsažená v M , tj.
M =⋃A⊂MA=A
A .
v) M je nejmenší39 uzavřená množina obsahující M , tj.
M =⋂M⊂AA=A
A .
vi) Bod a ∈ V je hraničním bodem množiny M (tj. a ∈ ∂M), právě když každé okolíbodu a obsahuje nějaký prvek množiny M a současně nějaký prvek nepatřící do M .
vii) Bod a ∈ V patří do uzávěru množiny M (tj. a ∈ M), právě když existuje vektorováposloupnost (xn)∞n=0 taková, že xn ∈M pro každé n ∈ N a lim
n→∞xn = a.
V následujících řešeních budeme okolím myslet otevřenou kouli Nε(x) = y ∈ V |‖y − x‖ < ε. Nebude-li třeba specifikovat poloměr ε, směle budeme psát jen N(x).
Řešení 5.5 i). Nechť U, V jsou otevřené množiny. Máme ukázat, že U∩V obsahuje všechnysvé body i se svými okolími. Nechť tedy x ∈ U ∩ V . Protože U, V jsou otevřené, x jejejich vnitřním bodem, existuje okolí Nε1(x) ⊂ U a taky okolí Nε2(x) ⊂ V . Položmeε = minε1, ε2, pak Nε(x) je okolí x obsažené v U ∩ V .
36Alternativně intM .37Alternativně clM .38Ve smyslu inkluze.39Ve smyslu inkluze.
109
Řešení 5.5 ii). Nechť Aii∈I je systém otevřených množin. Ukážeme, že pro každý bodx ∈ ⋃i∈I Ai existuje okolí N(x) takové, že N(x) ⊂ ⋃
i∈I Ai. Nechť x ∈⋃i∈I Ai, z definice
sjednocení to znamená, že existuje index i ∈ I takový, že x ∈ Ai. Ai je ale otevřená, tedyexistuje okolí Nε(x) ⊂ Ai ⊂
⋃i∈I Ai.
Řešení 5.5 iii). Nechť M je otevřená množina. Ukážeme, že doplněk M c je uzavřená mno-žina. To z definice znamená, že je rovna svému uzávěru, tj. M c = M c. Inkluze ⊂ je zřejmá.Nechť naopak x ∈ M c a pro spor nechť x /∈ M c, tzn. x ∈ M , M je otevřená, nechť tedyNε(x) ⊂M je okolí x. To je ale spor, protože existence takového okolí není možná. Každéokolí bodu bodu x má mít neprázdný průnik s M c protože x je v uzávěru M c tj. x ∈ M c.Tedy x ∈M c.
Řešení 5.5 iv). Předně, M je otevřená z definice, to že M ⊂ M také plyne z definice.Ukážeme, že pro každou otevřenou M ′ pro kterou platí M ′ ⊂M a M ⊂M ′ je M ′ ⊂M.M ′ je otevřená, tedy pro každé x ∈M ′ existuje okolí N(x) ⊂M ′ ⊂M , tedy x ∈M, tedyM ′ ⊂M.
Řešení 5.5 v). Předně, M je uzavřená z definice, to že M ⊂ M také plyne z definice.Ukážeme, že pro každou uzavřenou M ′ pro kterou platí M ⊂ M ′ a M ′ ⊂ M je M ⊂ M ′.Nechť x ∈ M a pro spor nechť x /∈ M ′, tzn. x ∈ M ′c, ale M ′c je otevřená, protože je todoplněk uzavřené množiny. Přitom ale M ′c ⊂ M c. To znamená, že x je obsažený v M c
společně s nějakým svým okolím. Ale to je spor, protože x je v uzávěru M , tj. x ∈ M akaždé jeho okolí má mít neprázdný průnik s M . Nutně tedy x ∈M ′.
Řešení 5.5 vi). Bod a je hraničním bodem právě když a ∈ M a zároveň x /∈ M. To jeprávě když každé okolí bodu a má neprázdný průnik s M a zároveň právě když neexistujeokolí a obsažené pouze v M – tedy každé okolí bodu a má neprázdný průnik s M c.
Řešení 5.5 vii). Nechť (xn)n∈N je posloupnost prvků v M konvergující k a. Tzn. pro každéokolí N(a) a pro dost velké n ∈ N je xn ∈ N(a), tj. N(a) ∩M 6= ∅ tedy a ∈M .
Na druhou stranu, nechť a ∈ M . Uvažujme systém okolí Na = N1/n(a) | n ∈ N.Každé okolí v Na má neprázdný průnik s M , protože a je v uzávěru M . Za každé n ∈ Nvybereme z množinyM∩N1/n(a) prvek xn. Sestrojíme takto posloupnost (xn)n∈N. Ukažme,že konverguje k a. Nechť ε > 0 je dané. Jistě existuje n0 ∈ N takové, že 1
n0< ε. Potom
pro každé n > n0 je pravda, že ‖xn − a‖ < ε, protože xn jsou volené tak, že ‖xn − a‖ < 1n.
Dostáváme:‖xn − a‖ <
1n<
1n0
< ε
tedy lim xn = a.
Cvičení 5.6: Dokažte, že vektorový prostor V = Cn,n vybavený normou (42) je úplný.Tj. každá Cauchyovská posloupnost je v něm konvergentní.Cvičení 5.7: Vypočtěte exponenciály následujících matic:
a) A =(
0 −xx 0
)∈ C2,2, kde x ∈ R.
110
b) A = diag (a1, . . . , an) ∈ Cn,n, tedy diagonální matice s prvky a1, . . . , an na diagonále40.
Cvičení 5.8: Vypočtěte parciální derivace funkce f(x, y, z) = (x + y)2exyz podle všechjejích proměnných.
Řešení. Připomeňme si potřebné vzorce pro práce s derivacemi
(ex)′ = ex , (xn)′ = nxn−1.
A ještě pravidlo pro derivaci součinu,
(f · g)′ = f ′g + fg′,
Použijme tato pravidla a vypočteme derivace funkce f podle všech proměnných
Řešení. a) Víme, že derivací funkce typu f : Rn → R je gradient funkce f , tedy
Df = ∇f = (∂xf, ∂yf).
Vypočteme parciální derivace
∂xf(x, y) = 2x+ 3y a ∂yf(x, y) = 3x+ 2y.
A poté dostávámeDf(x, y) = (2x+ 3y, 3x+ 2y).
b) Z definice 5.16 víme, že derivací funkce f : Rn → Rm v bodě a je matice Df(a) s prvkydefinovanými následujícím způsobem
Df(a))ij = ∂xifj(a), i ∈ n a j ∈ m.40Tento příklad naznačuje, jak lze maticovou exponenciálu počítat pomocí diagonalizace, z definice
snadno nahlédneme, že platí-li A = U D U−1, kde U je unitární a D je diagonální, pak exp(A) =U exp(D) U−1.
111
V našem případě f je zobrazení f : R2 → R2 a tedy Df ∈ R2,2 a
Df =(∂x(xy) ∂y(xy)∂x(x+ y) ∂y(x+ y)
).
Stačí vypočíst jednotlivé parciální derivace
∂x(xy) = y,
∂x(x+ y) = 1,∂y(xy) = x,
∂y(x+ y) = 1.
Nakonec dostanemeDf(x, y) =
(y x1 1
).
Cvičení 5.10: Uvažte funkci
f(x, y) =
xy(x2−y2)x2+y2 (x, y) 6= 0
0 (x, y) = 0
Ukažte, že tato funkce nemá záměnné smíšené parciální derivace v bodě (0, 0). Tedy ne-rovnost ∂2
xyf(0, 0) 6= ∂2yxf(0, 0).
Cvičení 5.11: Rozhodněte o definitnosti kvadratické formy q : R3 → R, je-li
a) q(x) = x21 + 3x2
2 + 4x23 − 2x1x2 + 2x1x3 − 2x2x3;
b) q(x) = x21 − 2x2
2 + 4x1x2;
c) q(x) = 5x21 + x2
2 + x23 + 4x1x2 − 2x1x3 − 2x2x3;
d) q(x) = x1x2 + x1x3 + x2x3;
Cvičení 5.12: V závislosti na parametrech a, b, c ∈ R vyšetřete definitnost matice
A =(a bb c
).
Řešení. Rozbor definitnosti matice A zahájíme odhalením podmínek pro pozitivní a ne-gativní definitnost, které postupně relaxujeme.
• Matice A je pozitivně definitní, právě tehdy když paramery splňují a > 0, c > 0 a|b| <
√ac.
112
Podle Sylvestrova kritéria je matice A pozitivně definitní, právě když platí následujícídvě nerovnosti
0 < det(a)
= a,
0 < det(a bb c
)= ac− b2.
Tedy jednoduchými úpravami získáme ekvivalentní podmínky:a > 0, c > 0, |b| <
√ac.
• Matice A je negativně definitní, právě tehdy když paramery splňují a < 0, c < 0 a|b| <
√ac. Argument pro toto tvrzení lze opět založit na Sylvestrově kritériu, nebo
můžeme konstatovat, že matice A je negativně definitní, právě když je −A pozitivnědefinitní a použít předchozí bod.
• Matice A je pozitivně, resp. negativně semidefinitní, právě tehdy když paramery spl-ňují a ≥ 0, c ≥ 0 a | b |≤
√ac, resp. a ≤ 0, c ≤ 0 a | b |≤
√ac.
Víme, že pro reálnou symetrickou matici A a její příslušnou kvadratickou formuqA(x) = xTAx, x ∈ Rn dle definice platí:
i) A je pozitivně semidefinitní, právě když qA(x) ≥ 0 pro každé x ∈ Rn,ii) A je negativně semidefinitní, právě když qA(x) ≤ 0 pro každé x ∈ Rn.
Pozitivní semidefinitnost matice A je tedy ekvivalentní platnosti nerovnosti
0 ≤ xTAx = (x0, x1)(a bb c
)(x0x1
)=
= ax20 + 2bx0x1 + cx2
1
pro každé x = (x0, x1)T ∈ R2. Nyní tento požadavek rozebereme podle ne/nulovostiparametru a.Pokud a = 0, pak máme nerovnost
2bx0x1 + cx21 ≥ 0.
která pro všechny možné x0, x1 platí pouze, pokud b = 0 a c ≥ 0.Pokud a 6= 0, pak kvadratickou formu a nerovnost upravíme na
a
(x0 + x1
b
a
)2
+(c− b2
a
)x2
1 ≥ 0.
Opět abychom pokryli všechny možné vektory musí zřejmě platit a > 0 a tedy i
c− b2
a≥ 0, což je pak ekvivalentní s c ≥ 0 a |b| ≤
√ac.
Pro vyšetření negativní semidefinitnosti můžeme opět vyjít přímo z definice (jen zdeobrátit znaménko), nebo využít předchozí bod podobně jako definitnosti dříve.
113
• Pokud a = c = 0 a b 6= 0, pak je matice A indefinitní. Kvadratická forma protakovou matici má tvar qA(x) = 2bx0x1, kde x = (x0, x1)T ∈ R2. Zajisté dokážemenajít vektory x, y ∈ R2 pro které bude qA(x) > 0 a qA(y) < 0.
• Pokud má matice A na diagonále dva prvky s různým znaménkem (jeden kladný adruhý záporný), pak je indefinitní. Mějme Ai,i > 0 a Aj,j < 0 pro nějaká i, j ∈1, 2. Pak pro vektory ze standardní báze R2 dostaneme hodnoty kvadratické formys opačnými znaménky tedy z definice je matice A indefinitní.
Cvičení 5.13: Nalezněte všechny extrémy funkce
f(x, y) = xy ln(x2 + y2
).
Cvičení 5.14: Nalezněte extrémy a sedlové body následujících funkcí více proměnných:
a) f(x, y) = x2 + (y − 1)2,
b) f(x, y) = x2y3(6− x− y),
c) f(x, y) = x4 + y4 − x2 − 2xy − y2,
d) f(x, y) = 2x4 + y4 − x2 − 2y2,
e) f(x, y) = ex2−y(5− 2x+ y),
f) f(x, y) = x− 2y + ln√x2 + y2 + 3 arctan y
x,
Cvičení 5.15: Nalezněte extrémy a sedlové body následujících funkcí více proměnných:
a) f(x, y, z) = x3 + y2 + z2 + 12xy + 2z,
b) f(x, y, z) = xy2z3(1− x− 2y − 3z),(nudíte-li se, pak vezměte obecněji:
f(x1, x2, . . . , xn) = x1x22 . . . x
nn(1− x1 − 2x2 − . . .− nxn)
pro x1, x2, . . . xn > 0.)
c) f(x, y, z) = 1x
+ x2
y+ y2
z+ z2 (x, y, z > 0),
Cvičení 5.16: Dané kladné číslo a rozložte na součin n kladných součinitelů tak, abysoučet jejich inverzních hodnot byl minimální.Cvičení 5.17: Dané kladné číslo a rozložte na součet n kladných čísel tak, aby součetjejich druhých mocnin byl minimální.Cvičení 5.18: Dané kladné číslo a rozložte na součin n kladných součinitelů tak, abysoučet jejich daných kladných mocnin byl minimální.Cvičení 5.19: Při jakých rozměrech bude mít otevřená nádoba tvaru kvádru danéhoobjemu V minimální povrch?
114
Cvičení 5.20: Do polokoule o poloměru R > 0 vepište kvádr maximálního objemu.Cvičení 5.21: Do elipsoidu
x2
a2 + y2
b2 + z2
c2 = 1
vepište kvádr maximálního objemu.Cvičení 5.22: Při jakých rozměrech bude mít otevřená válcová vana s půlkruhovým prů-řezem, jejíž povrch je S > 0, maximální objem?
Řešení. Označme poloměr průřezu za r ∈ R+ a délku za l ∈ R+. Pak objem vany lzespočítat podle vztahu πr2l
2 a S vyjádřit jako 2πr2+2πrl2 = πr2+πrl, což vede na optimalizační
úlohu minimalizuj f(r, l) = −πr2l2 ,
za podmínky h1(r, l) = πr2 + πrl − S = 0.(63)
Lagrangeova funkce je v tomto případě
L(r, l;µ) = −πr2l
2 + µ(πr2 + πrl − S).
Řešení soustavy
∇L(r, l;µ) = 0, h1(r, l) = 0,
pro tři neznámé r, l, µ, existují dvě:
(r1, l1, µ1) =(α, 2α, α2
),
(r2, l2, µ2) =(−α,−2α,−α2
),
kde α =√
S3π . Pojd’me prozkoumat první řešení. Pro Hessovu matici a gradient vazby v
bodě (r1, l1, µ1) dostáváme
∇2(r1,l1)L(r1, l1, µ1) = −πα
(1 1
212 0
),
∇h1(r1, l1) = πα (4, 1) .
Pro každý nenulový vektor z = (z1,−4z1)T platí
zT∇2(r1,l1)L(r1, l1, µ1)z = 3παz2
1 .
Tato kvadratická forma je pozitivně definitní, a proto v bodě (r1, l1) má cílová funkceostré lokální minimum. V druhém bodě pak evidentně má funkce ostré lokální maximum.Celkově uzavíráme, že vana bude mít největší objem při poloměru rovnému
√S3π a délce o
dvakrát větší než poloměr.
115
Cvičení 5.23: Raketa se skládá z rotačního válce zakončeného rotačním kuželem. Víte,že její povrch je S > 0 a byla navržena tak, aby mohla nést co nejvíce materiálu, tj., abyjejí objem byl maximální možný. Jaké jsou rozměry rakety?Cvičení 5.24: Vypočtěte vzdálenost mezi parabolou y = x2 a přímkou x− y = 2.
Důkaz. Vzdálenost mezi body v rovině můžeme zadefinovat jako d(X, Y ) = (X1 − Y1)2 +(X2 − Y2)2, kde X, Y ∈ R2. Buďte p1(s) = (s, s2) a p2(t) = (t, t − 2), kde s, t ∈ R, body,které leží na zadané parabole, resp. přímce.
Teď můžeme najít stacionární body funkce F (s, t). Vypočteme parciální derivace funkceF ,
∂F
∂s= 4s3 + 10s− 2t− 4st,
∂F
∂t= 4t− 2s2 − 2s− 4.
Pro gradient pak dostáváme
∇F =(4s3 + 10s− 2t− 4st, 4t− 2s2 − 2s− 4
).
Po vyřešení soustavy rovnic4s3 + 10s− 2t− 4st = 04t− 2s2 − 2s− 4 = 0
s reálnými neznámými s a t dostaneme právě jedno řešení s = 12 a t = 11
8 .Nyní vypočteme Hessovu matici, tedy
∇2F =(
∂F∂s2
∂F∂s∂t
∂F∂t∂s
∂F∂t2
)=(
12s2 + 10− 4t, −4s− 2−4s− 2, 4
).
V našem stacionárním bodě platí
∇2F(1
2 ,118
)=(
152 −4−4 4
),
což je pozitivně definitni matice podle Sylvestrova kritéria, tedy jde o lokální minimum.Vzdálenost mezi zadanými křivkami teď můžeme jednoduše spočítat dosasením s = 1
2a t = 11
8 do F (s, t), z čeho vyplyne odpověď 7√
28 .
Cvičení 5.25: Odvoďte vzorec pro výpočet vzdálenosti bodu (x0, y0, z0) od roviny ax +by + cz + d = 0 v R3.
116
Cvičení 5.26: Do úseče eliptického paraboloidu z = c(x2 + y2), z = c > 0, vepište kvádrmaximálního objemu.
Řešení. Objem kvádru, vepsáného do úseče eliptického paraboloidu z = c(x2 + y2), z =c > 0, v souladu se souřadnými osami (strany délky 2x, 2y a c − z) se dá vyjádřit jakof(x, y, z) = 4xy(c− z). Úloha se pak mění na úlohu nalezení extrému funkce f(x, y, z) zapodmínky h(x, y, z) = c(x2 + y2)− z = 0.
Tato kvadratická forma je negativně definitní a v tomto bodě proto má naše funkce skutečnélokální maximum.
Rozměry hledaného kvádru proto jsou 2× 2× c2 a jeho objeme je roven 2c.
117
Cvičení 5.27: Buďte f a g dvě konvexní funkce a Df ⊂ Dg konvexní množina. Potomfunkce h definovaná předpisem
h(x) := maxf(x), g(x)
je konvexní.
Řešení. Konvexnost funkce h(x) je dle definice ekvivalentní podmínkám:
(i) Dh je konvexní množina.
(ii) Pro každé a, b ∈ Dh a θ ∈ (0, 1) platí
h(θa+ (1− θ)b) ≤ θh(a) + (1− θ)h(b)
Postupně dokažeme oba body:
(i) Jelikož Df ⊂ Dg a h(x) := max f(x), g(x) platí, že Dh = Df . Df je konvexnífunkce, jejíž definiční obor je z definice konvexní množina, tím pádem i Dh je konvexnímnožina.
(ii) Z definice funkce h(x) pro každé c ∈ Dh platí jedna ze dvou rovností: bud’ h(c) = f(c)anebo h(c) = g(c). Necht’ pro nějaká a, b ∈ Dh a θ ∈ (0, 1) platí h(θa + (1 − θ)b) =f(θa+ (1− θ)b). Pak je dokazovaná nerovnost h(θa+ (1− θ)b) ≤ θh(a) + (1− θ)h(b)ekvivalentní nerovnosti
f(θa+ (1− θ)b) ≤ θh(a) + (1− θ)h(b)
Jelikož pro každé c ∈ Df platí f(c) ≤ max f(c), g(c) (tedy f(c) ≤ h(c)), a θ a 1− θjsou kladná je pro každý součet θh(a) + (1− θ)h(b), kde a, b ∈ Df a θ ∈ (0, 1) platnýodhad
θf(a) + (1− θ)f(b) ≤ θh(a) + (1− θ)h(b)Využitím tohoto odhadu a konvexnosti f(x) dostáváme nerovnost
To znamená, že pro hodnoty a, b ∈ Dh a θ ∈ (0, 1), splňující h(θa + (1 − θ)b) =f(θa+ (1− θ)b) platí
h(θa+ (1− θ)b) ≤ θh(a) + (1− θ)h(b)
Stejným postupem se dá dokazat, že h(θa+ (1− θ)b) ≤ θh(a) + (1− θ)h(b) platí i propřípad, když pro nějaká a, b ∈ Dh a θ ∈ (0, 1) platí h(θa+(1−θ)b) = g(θa+(1−θ)b).Z toho plyne, že nerovnost h(θa+ (1− θ)b) ≤ θh(a) + (1− θ)h(b) je platná pro každéa, b ∈ Dh a θ ∈ (0, 1). Tím pádem je bod (ii) zcela dokázaný.
118
Cvičení 5.28: Buďte A a B konvexní podmnožiny vektorového prostoru V . Dokažte nebovyvraťte tvrzení
a) Sjednocení množin A a B je konvexní.
b) Průnik množin A a B je konvexní.
Řešení. a) To neplatí. Bud’ například A = a, B = b jednoprvkové41 a platí A 6= B.Předpokládejme, že A∪B je konvexní. Tzn., pro všechna x, y ∈ A∪B a všechna θ ∈ 〈0, 1〉platí θx+(1−θ)y ∈ A∪B. Pro nějaké θ′ ∈ (0, 1) speciálně platí i θ′a+(1−θ′)b ∈ A∪B,anebo θ′a+(1−θ′)b = a∨θ′a+(1−θ′)b = b. Po úpravě rovnic dostaváme a = b∨a = b,čili A = B, což je spor.
b) To platí, dokážeme to sporem. Předpokládejme, že A ∩B není konvexní. Tzn., existujíx′, y′ ∈ A ∩ B a θ′ ∈ 〈0, 1〉 takové, že θ′x′ + (1− θ′)y′ /∈ A ∩ B. Na druhou stranu A jekonvexní a tedy pro všechna x, y ∈ A a všechna θ ∈ 〈0, 1〉 platí θx + (1 − θ)y ∈ A. Zdefinice průniku dvou množin x′, y′ ∈ A, a proto platí θ′x′ + (1 − θ′)y′ ∈ A, stejně takplatí i θ′x′ + (1− θ′)y′ ∈ B, z čehož nutně plyne θ′x′ + (1− θ′)y′ ∈ A ∩B, což je spor.
Cvičení 5.29: Uvažme dvě konvexní funkce f a g definované na konvexní množině D ⊂ Rn
a dvě kladné konstanty a, b > 0. Potom af + bg je konvexní.Cvičení 5.30: Afinní funkce, tedy funkce tvaru f(x) = aTx+c, a ∈ Rn, c ∈ R, s Df ⊂ Rn
konvexní množinou, je konvexní.Cvičení 5.31: Dokažte Lemma 5.49.
41Každá jednoprvková M ⊂ V je konvexní, nebot’ pro jediný prvek m ∈ M a libovolné θ ∈ 〈0, 1〉 platíθm+ (1− θ)m = m ∈M
119
6 Obyčejné diferenciální rovniceV této části textu se dotkneme základů teorie obyčejných diferenciálních rovnic (ODR).Na úvod nejprve zdůrazněme v čem se ODR liší od úloh s kterými se čtenář jistě již setkalběhem svého studia.
Řešíme-li například kvadratickou rovnici
x2 + 2x− 3 = 0
tak řešením této úlohy je číslo. V tomto konkrétním případě jsou řešení dvě: číslo 1 a číslo−3.
Podobně v Lineární algebře jsme řešili soustavy lineárních rovnic, které se ovšem dalyzapsat v kompaktním tvaru
Ax = b,
kde A je matice s m řádky a n sloupci, a b je vektor s m složkami. Řešením této úlohyje vektor x s n složkami. Pro jednoduchost uvažujme, že počítáme nad reálným tělesem.Je-li množina všech řešení takovéto soustavy lineárních rovnic neprázdná, pak tvoří lineárnívarietu v prostoru Rn.
V předchozích dvou příkladech (a čtenářovi se jistě vybaví i další podobné situace) jsouřešeními čísla, vektory – statické objekty. Naopak, řešeními obyčejných diferenciálních rov-nic budou (dostatečně diferencovatelné) funkce. Odtud by měla být ihned patrná důležitosttohoto pojmu. Pomocí ODR můžeme modelovat celou řadu zajímavých dynamických jevůa procesů které se mění v čase (nezávisle proměnná je často čas). Pomocí ODR můžemepředpovídat budoucnost.
Nejprve začněme formální definicí, která na první čtení může vypadat komplikovaně,ale opak je pravdou.Definice 6.1: Buďte n,m ∈ N a
F : R× Rn × Rn × · · · × Rn︸ ︷︷ ︸(n+1)krát
→ Rm
spojitá funkce netriviálně závisející na své (n + 2). proměnné. Soustavou obyčejnýchdiferenciálních rovnic nazýváme rovnici tvaru42
F(t, y, y′, . . . , y(n)
)= 0 (64)
pro neznámou funkci y : R → Rn s nezávislou proměnnou t. Řešením rovnice (64) paknazýváme libovolnou funkci y : J → Rn definovanou na otevřeném intervalu J splňující43
F(t, y(t), y′(t), . . . , y(n)(t)
)= 0 pro každé t ∈ J. (65)
42Někdy slovíčko „soustava“ vynecháváme. Ve vektorové notaci jde o jednu rovnici.43Implicitně se tedy předpokládá, že y má na intervalu J všechny derivace až až do řádu n včetně.
120
Například mějme jednu diferenciální rovnici
y′′ + y = 0 (66)
pro jednu neznámou funkci y. Ve značení uvedeném v předcházející definici máme
F (t, y, y′, y′′) = y′′ + y.
Funkce F v tomto případě nezávisí na t a y′.Všimněme si, že derivací vyšších řádů se můžeme zbavit zavedením nových proměnných.
Skutečně, bavíme-li se například o (66), můžeme zavést novou funkci z := y′ a získat takdvě rovnice
z′ + y = 0, y′ = z, (67)
pro dvě neznámé funkce y a z. Tyto dvě formulace ((66) a (67)) jsou očividně ekvivalentní.Díky tomuto pozorování je možné se v úvahách omezit pouze na diferenciální rovniceobsahující pouze první derivace neznámých funkcí.
My se v tomto textu budeme zabývat diferenciálními rovnicemi v následujícím speciální,ale stále dostatečně obecném, tvaru.Definice 6.2: Soustavu obyčejných diferenciálních rovnic, kterou lze vyjádřit ve tvaru
y′ = f(t, y), (68)
kde y : R→ Rn, t ∈ R a f : R×Rn → Rn, nazýváme soustavou obyčejných diferenci-álních rovnic n-tého řádu ve standardním tvaru. Pokud hledáme řešení rovnice (68)splňující y(t0) = y0 pro zadané t0 ∈ R a y0 ∈ Rn, pak o této úloze mluvíme jako opočáteční (Cauchyho) úloze.
Nyní zmiňme veledůležitou větu zajišťující existenci a jednoznačnost řešení počátečníúlohy.Věta 6.3 (Picard–Lindelöf): Nechť f : R × Rn → Rn je spojitá a stejnoměrně Lipschit-zovská na oblasti Ω ⊂ Rn vzhledem k t ∈ J = (a, b), tj. existuje konstanta L > 0 taková,že pro všechna x, y ∈ Ω a všechna t ∈ J platí
‖f(t, x)− f(t, y)‖ ≤ L ‖x− y‖.
Potom pro každé t0 ∈ J a y0 ∈ Ω existuje právě jedno řešení Cauchyho úlohy
y′ = f(t, y), y(t0) = y0
definované na jistém intervalu (t0 − ε, t0 + ε) ⊂ J , kde ε > 0.
Důkaz. Vynecháváme. Viz například [3].
121
Příklad 6.4: Vyřešte y′ = y1/3 s počáteční podmínkou y(0) = 0.Povšimněte si, že vydělením rovnice pravou stranou (problém potenciálního dělení nulou
zatím ponechme stranou) lze tuto rovnici přepsat do tvaru
y′
y1/3 = 1.
Integrací obou stran vůči t pak dostáváme
t =∫ t
01 ds =
∫ t
0
1y1/3(s)y
′(s) ds =[32y
2/3(s)]t
0= 3
2y2/3(t)− 3
2y2/3(0) = 3
2y2/3(t).
Jinak řečeno, dostáváme předpis
y1(t) :=(2t
3
)3/2.
Snadno se přesvědčíme (přímo z definice), že tato funkce splňuje uvedenou diferenciálnírovnici i počáteční podmínku.
Na druhou stranu, řešením naší rovnice je ale triviálně i funkce y2(t) = 0, která ji takévyhovuje a splňuje uvedenou počáteční podmínku!
Vidíme, že tato diferenciální rovnice má dvě různá řešení splňující y(0) = 0.Příklad 6.5: Vyřešme rovnici y′′+y = 0 uvedenou na začátku této kapitoly (rovnice (66)).
Jedná se o homogenní lineární diferenciální rovnici s konstantními koeficienty (to jsouobecně rovnice tvaru cny(n) +cn−1y
(n−1) + · · · c1y′+c0y = 0). Jednou z metod jak nalézt její
řešení je pokusit se ho hledat ve tvaru y(t) = eλt, kde λ je jistá, zatím neurčená, konstanta.Po dosazení tohoto předpisu do naší rovnice získáme rovnici
λ2eλt + eλt = 0.
Aby námi zvolená funkce byla řešením, musí nutně platit λ2 + 1 = 0, čili λ = ±i. Díkylinearitě je řešením i C±e±it a tedy i libovolná funkce tvaru
y(t) = C+eit + C−e
−it.
Vzpomeneme-li si na vztah mezi exponenciální a trigonometrickými funkcemi můžeme tentoodstavec uzavřít pozorováním, že libovolná funkce
y(t) = A sin t+B cos t,
kde A a B jsou konstanty (nezávislé na t), je řešením rovnice y′′+ y = 0. O tomto faktu sesamozřejmě můžeme přesvědčit i prostým dosazením tohoto předpisu do uvažované rovnice.
Předchozí příklad lze řešit i jiným způsobem. Zbavíme-li se vyšší derivace zavedenímnové funkce z = y′ (jak bylo uvedeno na začátku této sekce), tak lze rovnici zapsat ve tvaru
y′ = z, z′ = −y.
122
V maticovém zápisu (y′
z′
)=(
0 1−1 0
)(yz
).
Pro ODE tohoto typu může být užitečná následující věta.Věta 6.6: Homogenní soustava obyčejných lineárních diferenciálních rovnic n-tého řádu skonstantními koeficienty, tj. soustava
y′ = Ay,
kde A ∈ Rn,n, a počáteční podmínkou y(t0) = y0 ∈ Rn má řešení
y(t) = exp((t− t0)A
)y0.
Nejprve dokažme pomocné tvrzení.Lemma 6.7: Libovolná ‖·‖ norma na vektorovém prostoru Rn je spojitá funkce. Násobenín × n maticí A je taktéž spojitá funkce. Přesněji, je-li (zk)∞k=1 posloupnost vektorů z Rn
konvergující k z ∈ Rn, potom platí
limk→∞‖zk‖ = ‖z‖ a lim
k→∞Azk = Az.
Důkaz. Nejprve si rozmysleme platnost následující nerovnosti∣∣∣‖u‖ − ‖v‖∣∣∣ ≤ ‖u− v‖, u, v ∈ Rn.
Tato nerovnost plyne z trojúhelníkové nerovnosti. Na jednu stranu pro libovolné u, v ∈ Rn
máme‖u‖ = ‖u− v + v‖ ≤ ‖u− v‖+ ‖v‖,
čili ‖u‖ − ‖v‖ ≤ ‖u − v‖. Prohozením u a v dostaneme ‖v‖ − ‖u‖ ≤ ‖v − u‖ = ‖u − v‖a proto dohromady máme −‖u − v‖ ≤ ‖u‖ − ‖v‖ ≤ ‖u − v‖, což jsme tvrdili na začátkutohoto odstavce.
První tvrzení lemmatu pak ihned plyne z odhadu∣∣∣‖zk‖ − ‖z‖∣∣∣ ≤ ‖zk − z‖ → 0
když k →∞.V případě druhého tvrzení máme díky linearitě maticového násobení
‖Azk − Az‖ = ‖A(zk − z)‖ ≤ ‖A‖ ‖zk − z‖.
Zde pod normou matice máme na mysli (jde skutečně o normu, tento fakt ale není potřeba)
‖A‖ := sup‖Au‖‖u‖
∣∣∣∣∣u ∈ Rn, u 6= 0.
123
Důkaz věty 6.6. Počáteční podmínka je očividně splněna, protože exp(0) = id.Bez újmy na obecnosti uvažme t0 = 0. Potom máme dokázat, že (využíváme spojitost)
y′(t) = lims→t
1s− t
(exp(sA)y0 − exp(tA)y0
)= exp(tA) lim
s→t
1s− t
(exp((s− t)A)y0 − y0
)=
= exp(tA) limh→0
exp(hA)y0 − y0
h= exp(tA)Ay0 = A exp(tA)y0 = Ay(t).
Ve výpočtu je nutné si rozmyslet platnost druhé rovnosti na druhém řádku. Buď N přiro-zené číslo větší než 2 a h 6= 0. Potom po přímočarém odečítání dostaneme
1h
(N∑k=0
hk
k!Aky0 − y0
)− Ay0 =
N∑k=2
hk−1
k! Aky0.
Tudíž pro normu tohoto výrazu pro všechna nenulová h z jistého okolí 0 máme∥∥∥∥∥1h
(N∑k=0
hk
k!Aky0 − y0
)− Ay0
∥∥∥∥∥ ≤N∑k=2
|hk−1|k! ‖A‖
k‖y0‖ ≤
≤ |h|‖y0‖∞∑k=2
|h|k−2
2k−1 ‖A‖k = |h| ·
‖y0‖ · ‖A‖2
21− |h|‖A‖/2 .
Díky spojitosti normy lze provést nyní limitu N → ∞ (pravá strana navíc na N vůbecnezávisí) a dostáváme odhad
∥∥∥∥1h
(exp(hA)y0 − y0)− Ay0
∥∥∥∥ ≤ |h| · ‖y0‖ · ‖A‖2
21− |h|‖A‖/2
platný pro všechna výše zmíněná h. Konečně provedením limity h→ 0 dostáváme
limh→0
∥∥∥∥1h
(exp(hA)y0 − y0)− Ay0
∥∥∥∥ = 0
odkud již ihned plyne dokazované tvrzení, tj. že
limh→0
1h
(exp(hA)y0 − y0) = Ay0.
6.1 Integrální křivky, pevné body a stabilitaV této části textu budeme pro jednoduchost uvažovat úlohu (73) v případě kdy pravástrana nezávisí na čase t (tzv. autonomní případ). Zabýváme se tedy řešením úlohy
y′ = f(y), y(t0) = y0 ∈ Rn. (69)
Zde funkce f je vektorová funkce typu Rn → Rn. Můžeme si ji představovat jako tzv.vektorové pole. Každému bodu x ∈ Rn tato funkce přiřazuje vektor f(x) ∈ Rn.
124
Řešení y : J → Rn, kde t0 ∈ J , úlohy (69) si lze představovat jako křivku v prostoru Rn.Tato křivka navíc má tu vlastnost, že v každém bodě této křivky, řekněme v y(t), je jejítečný vektor přesně f(y(t)). Tj. tečný vektor je v každém okamžiku předepsán vektorovýmpolem f . O řešeních úlohy (69) se proto často také mluví jako o tzv. integrálních křivkáchvektorového pole f .
Platí-li předpoklady věty (6.3), pak se integrální křivky nikde neprotínají (jinak by bylaporušena jednoznačnost).Příklad 6.8: Ukažme si tento pohled na konkrétním příkladě,
f(y) =(y10
), y = (y1, y2)T ∈ R2.
Rozepsána po složkách má tato soustava tvar
y′1 = y1, y′2 = 0.
Její řešení je tedyy1(t) = C1e
t, y2(t) = C2,
kde C1 a C2 jsou konstanty závisející na počátečních podmínkách. Je-li zadáno y(0) =(y10, y20)T ∈ R2, pak příslušným řešením je zřejmě
y(t) =(ety10y20
).
V prostoru R2, kde si přirozeně zavedeme kartézské souřadnice (y1, y2) pak integrálníkřivky představují rovnoběžky s osou y1.
Při pohledu na (69) se ihned nabízí zjistit, zda-li v některých bodech y0 ∈ Rn nenastávárovnost f(y0) = 0. V tom případě bychom totiž ihned měli řešení
y(t) = y0.
Jinak řečeno, nachází-li se systém v bodě y0, tak se z něj už nikdy nedostane. Integrálníkřivka „degeneruje“ na bod. Z očividných důvodů se takovéto body nazývají pevné bodyvektorového pole f (případně stacionární body, rovnovážná konfigurace, aj.).
Dále se můžeme zamyslet co se děje na okolí jistého pevného bodu y0. Co když systémlehce vychýlíme z rovnováhy? Vrátí se zpět do pevného bodu, uteče pryč, nebo bude kolempevného bodu kroužit? Jinak řečeno, nyní se pokusíme nastínit řešení otázky stabilitypevného bodu.Definice 6.9: Pevný bod y∗ ∈ Rn vektorového pole f , tj. f(y∗) = 0, nazýváme (asympto-ticky) stabilní, pravé když existuje okolí By∗ bodu y∗ takové, že pro libovolné řešení úlohy
y′ = f(y), y(0) ∈ By∗ ,
platí limt→+∞ y(t) = y∗.
125
Mějme nyní pevný bod y∗ ∈ Rn vektorového pole f , tj. nechť f(y∗) = 0. VyužijmeTaylorovu větu pro funkci f na okolí bodu y∗,
f(y) = f(y∗) +Df(y∗)(y − y∗) + o(‖y − y∗‖2
)= Df(y∗)(y − y∗) + o
(‖y − y∗‖2
).
Je-li y „blízko“ pevnému bodu y∗, pak na jeho vývoj bude mít podstatný vliv lineární člena kvadratický můžeme zanedbat. Jinak řečeno, položíme z = y−y∗ (tj. posuneme souřadnýsystém do bodu y∗, navíc pak z′ = y′) a zkoumáme chování řešení úlohy
z′ = Df(y∗)z, z(0) = z0
zejména na pro z0 ∈ H0 ⊂ Rn. Tuto rovnici ale umíme řešit pomocí maticové exponenciály!Řešením je
z(t) = exp(tDf(y∗)
)z0. (70)
Otázkou se nyní stává, zda-li lze na základě vlastností matice Df(y∗) odvodit kvalitativnívlastnosti řešení z(t). Ukažme si tento postup na následujícím příkladu.Příklad 6.10: Zkoumejte pevné body a chování řešení blízko těchto bodů pro obyčejnoudiferenciální rovnici
y′ = f(y) =(
13(y1 − y2)(1− y1 − y2)
y1(2− y2)
), y = (y1, y2)T . (71)
Z rovnice f(y) = 0 pro pevný bod nutně plyne, že y1 = 0 nebo y2 = 2. Pokud y1 = 0,pak −1
3y2(1−y2) = 0, tj. buď y2 = 0 nebo y2 = 1. Tato větev výpočtu nám dává dva pevnébody, označme si je A = (0, 0) a B = (0, 1). Je-li naopak y2 = 2, pak 1
3(y1−2)(−1−y1) = 0,čili y1 = 2 nebo y1 = −1. Dostáváme tak další dva pevné body C = (2, 2) a D = (−1, 2).
Pro první derivaci dostáváme
Df(y) =(
13(1− y1 − y2)− 1
3(y1 − y2) −13(1− y1 − y2)− 1
3(y1 − y2)2− y2 −y1
).
Tudíž matice linearizací v bodech A = (0, 0), B = (0, 1), C = (2, 2), D = (−1, 2) jsou dány(dosazení)
Df(A) =(
13 −
13
2 0
), Df(B) =
(13
13
1 0
),
Df(C) =(−1 10 −2
), Df(D) =
(1 10 1
).
Vypočtěme nyní řešení (70) v těchto čtyřech případech.
A: Vlastní čísla matice Df(A) jsou λ± = 16
(1± i
√23), každé z nich má násobnost
jedna. Matice B je proto diagonalizovatelná, platí
Df(B) = U
(λ+ 00 λ−
)U−1,
126
kde matice U má ve sloupcích vlastní vektory k vlastnímu číslu λ+ a λ− (v tomtopořadí). Pro maticovou exponenciálu, resp. linearizované řešení, proto platí
exp(tDf(B))z0 = U
(eλ+t 0
0 eλ−t
)U−1z0.
Vzhledem k tomu, že <λ+ > 0 i <λ− > 0 vidíme, že s rostoucím časem se řešenívzdaluje od bodu A. Imaginární složky vlastních čísel do řešení přispějí jako sinus akosinus a mají za následek rotaci viditelné na obrázku 25.
B: Vlastní čísla matice Df(B) jsou λ± = 16
(1±√
13), každé z nich má násobnost jedna.
Matice B je proto diagonalizovatelná, platí
Df(B) = U
(λ+ 00 λ−
)U−1,
kde matice U má ve sloupcích vlastní vektory k vlastnímu číslu λ+ a λ− (v tomtopořadí). Pro maticovou exponenciálu, resp. linearizované řešení, proto platí
exp(tDf(B))z0 = U
(eλ+t 0
0 eλ−t
)U−1z0.
Vzhledem k tomu, že λ+ > 0 a λ− < 0 vidíme, že v jednom směru se řešení blíží kbodu B a v jiném směru se od něho vzdalují. Viz obrázek 25.
C: Nyní má matice Df(C) jedno vlastní číslo λ+ = −2 a druhé λ− = −1. Jedná se tedyo stabilní pevný bod.
D: V tomto případě není maticeDf(D) diagonalizovatelná. Má totiž jenom jedno vlastníčíslo λ = 1 s algebraickou násobností 2 a geometrickou násobností 1. Maticovouexponenciálu ovšem dokážeme vypočíst přímo z definice, dostáváme
exp(tDf(D))z0 =(eλt teλt
0 eλt
)U−1z0.
Řešení se proto s rostoucím časem od bodu D vzdalují a tento není stabilním pevnýmbodem.
127
x
-0.5 0.0 0.5
1.0
1.5
0.0
0.5
Color
-0.5
0.0
0.5
y
x
-0.5 0.0 0.5
0.6
0.8
0.0
0.4
0.2
Color
-0.5
0.0
0.5
y
x
-0.5 0.0 0.5
1.0
1.5
0.0
0.5
Color
-0.5
0.0
0.5
y
x
-0.5 0.0 0.5
1.0
1.5
0.0
0.5
Color
-0.5
0.0
0.5
y
Obrázek 25: Vektorové pole (71) na okolí bodu A, B, C a D (popořadě).
Výše popsanou intuici přesně vystihují následující dvě věty (zájemce o důkaz a podrob-nější rozbor odkazujeme na [3, Kapitola 13]).Věta 6.11: Mějme systém obyčejných diferenciálních rovnic
y′ = Ay + f(t, y), (72)
kde A je reálná matice jejíž všechna vlastní čísla mají záporné reálné části a f je spojitáfunkce splňující
f(t, y) = o(‖y‖), když ‖y‖ → 0
stejnoměrně pro t ≥ 0. Potom řešení y(t) = 0 je asymptoticky stabilní.Podobně máme i výsledek v opačném směru.
Věta 6.12: Má-li alespoň jedno vlastní číslo matice A z rovnice (72) kladnou reálnou částa f splňuje podmínky uvedené ve Větě 6.11, potom řešení y(t) = 0 není asymptotickystabilní.
128
6.2 Přibližné numerické metodyVelmi obsáhlým a podrobným přehled přibližných numerických metod pro řešení obyčej-ných diferenciálních rovnic lze nalézt například v [7]. V této sekci se omezíme na ukázkuněkolika základních metod určených pro řešení Cauchyho úlohy
y′ = f(t, y), y(t0) = y0 ∈ Rn. (73)
Tato kapitola je dále doplněna Jupyter notebookem odes.ipynb s mnoha ukázkami a de-monstracemi.
6.2.1 Eulerova metoda
Jednou z nejjednodušších metod je patrně Eulerova metoda. Její myšlenka je následující:máme zadánu počáteční hodnotu y0 = y(t0), pokusme se proto nalézt aproximaci skuteč-ného řešení v čase t0 + h, kde h > 0 je předem zvolená konstanta. Chceme tedy přibližněvypočítat y(t0 + h). Je-li h „malé,“ pak pro derivaci funkce y′ v čase t0 „přibližně“ platí
y′(t0) = lims→0
y(t0 + s)− y(t0)s
≈ y(t0 + h)− y(t0)h
.
Na druhou stranu z rovnice (73) máme pro skutečené řešení rovnost
y′(t0) = f(t0, y(t0)).
Porovnáním tak dostáváme
y(t0 + h) ≈ y(t0) + hf(t0, y(t0)).
Nyní můžeme celou úvahu znovu opakovat a získat tak aproximaci řešení v čase t0 + 2h av dalších časových okamžicích.
Eulerova metoda pro úlohu (73) tedy spočívá ve volbě konstanty h > 0 a následujícíjednoduché rekurenci
yk+1 = yk + hf(tk, yk), k = 0, 1, 2, . . . , (74)
kde tk = t0 +kh, k = 0, 1, 2, . . . Počáteční hodnota y0 je předepsána a y1, y2, . . . představují(doufáme!) aproximace skutečného řešení v časech t1, t2, . . .
Zamysleme se nyní nad otázkou přesnosti Eulerovy metody. Označme y(t) řešení Cau-chyho úlohy (73) a (yk)∞k=0 přibližné „řešení“ zkonstruované pomocí rekurence (74). Chybuv prvním kroku můžeme odhadnout pomocí Taylorovy věty (máme-li dostatečně hladkéřešení)
y(t0 + h)− y1 = y(t0) + y′(t0)h+ o(h2)− (y0 + hf(t0, y0)) = O(h2),protože y′(t0) = f(t0, y0). Lokální chyba (chyba v jednom kroku) se chová kvadratickyvzhledem k velikosti kroku h. Prakticky zajímavější je odhadnout chybu na (například)intervalu délky 1. Je-li h délka jednoho kroku, pak abychom pomocí Eulerovy metody z
129
y(t0) vypočetli y(t0 + 1), pak musíme provést cca 1/h kroků. V každém kroku ale udělámechybu řádově O(h2). Globální chyba (chyba na intervalu) Eulerovy metody proto jeO(h1). Jedná se o tzv. metodu prvního řádu.
Pozorování v předchozím odstavci by nás mělo před Eulerovou metodou varovat. Jehopraktickým důsledkem je, že chceme-li docílit globální chyby dejme tomu 10−6 na jednot-kovém časovém intervalu, pak musíme provést řádově 106 kroků!
6.2.2 Implicit midpoint rule
Pokusme se nyní znovu „zaútočit“ na úlohu (73). Budeme používat stejné značení jako vpředchozím textu. Pro skutečné řešení dle Newtonovy formule v prvním kroku platí
y(t0 + h) = y(t0) +∫ t0+h
t0y′(s) ds = y0 +
∫ t0+h
t0f(s, y(s)) ds.
Pro „malé“ h > 0 se zdá jako dobrý nápad44 odhadnout integrál na pravé straně pomocíobsahu obdélníku se stranami h a f(t0 + h/2, y(t0 + h/2)) (výšku obdélníku volíme nazákladě funkční hodnoty integrandu v polovině integračního intervalu – proto midpoint),tedy konkrétně
y(t0 + h) ≈ y0 + hf(t0 + h/2, y(t0 + h/2)).
Konečně, nahraďme neznámou hodnotu y(t0 + h/2) hodnotou získanou pomocí průměru zy0 a y1, tj. y(t0 + h/2) ≈ (y0 + y1)/2. Dostáváme tak přibližné vyjádření
y(t0 + h) ≈ y0 + hf(t0 + h/2, (y0 + y1)/2).
Po drobném přeznačení získáváme metodu (jeden její krok):
k1 = f
(t0 + h
2 , y0 + h
2k1
),
y1 = y0 + hk1,
Abychom mohli jeden krok provést je nutné z první rovnice určit k1. Tato rovnice je im-plicitní vzhledem ke k1. K určení k1 je většinou nutné se uchýlit k numerickým metodám(je jasné, že bez podrobnější znalosti funkce f obecně k1 nevypočteme – nevyjádříme ex-plicitně).
6.2.3 Runge–Kutta metoda (RK4)
Na myšlenkách uvedených v předchozím textu je založena celá rodina metod (explicit-ních i implicitních) nazývaných Runge-Kuttovy metody. V tomto textu se jimi podrobněnebudeme zabývat. Zvídavý čtenář nalezne množství informací v [7].
44Odhadnout limitu pomocí konečného podílu v Eulerově metodě byl také dobrý nápad.
130
Pro úplnost a porovnání s předchozími metodami zde alespoň uvedeme nejpoužívaněj-šího zástupce uvedené rodiny, explicitní Runge–Kuttovu metodu 4. řádu („RK4“). Jedenjejí krok pro úlohu (73) zní
7 Lineární programováníIndustrial production, the flow of resources in the economy, the exertion of mi-litary effort in a war, the management of finances—all require the coordinationof interrelated activities. What these complex undertakings share in common isthe task of constructing a statement of actions to be performed, their timingand quantity (called a program or schedule), that, if implemented, would movethe system from a given initial status as much as possible towards some definedgoal. George Dantzig
Výklad o Lineárním programování probíhá podle skript [10].
Reference[1] Ahlfors, Lars V.: Complex Analysis. McGraw-Hill, 1979.
[2] Boyd, Stephen a Lieven Vandenberghe: Convex Optimization. Cambridge UniversityPress, 2009.
[3] Coddington, Earl a Norman Levinson: Theory of Ordinary Differential Equations.McGraw-Hill, 1955.
[4] Conway, John B.: Functions of One Complex Variable. Springer, 1978.
[5] Cooley, James W. a John W. Tukey: An algorithm for the machine calculation ofcomplex Fourier series. Math. Comput., 19:297–301, 1965.
[6] Danielson, G. C. a C. Lanczos: Some improvements in practical Fourier analysis andtheir application to X-ray scattering from liquids. J. Franklin Inst., 233:365–380, 435–452, 1942.
[7] Heirer, Ernest, Syvert Norset a G. Wanner: Solving Ordinary Differential Equations.Springer, 2008.
[8] Jarník, Vojtěch: Diferenciální počet II. Academia, 1956.
[9] Peterson, David W.: A Review on Constraint Qualifications in Finite-dimensionalspaces. SIAM Review, 15:639–654, 1973.
[10] Rohn, Jiří: Lineární programování (stručný učební text). Technická zpráva 845, Insti-tute of Computer Science, Academy of Sciences of the Czech Republic, Prague, 2001.http://uivtx.cs.cas.cz/~rohn/publist/skripta.pdf.
[11] Rudin, Walter: Analýza v reálném a komplexním oboru. Academia, 2003.
[12] Smith III, Julius O.: Mathematics of the Discrete Fourier Transform (DFT), withAudio Applications. W3K Publishing, second edition edice, 2007. https://ccrma.stanford.edu/~jos/mdft/.
