Matematika III - 4. přednáška Funkce více proměnných: vázané extrémy, optimalizační metody Michal Bulant Masarykova univerzita Fakulta informatiky 9. 10. 2007 = A Inverzní a implicitní zobrazení • Věta o inverzním zobrazení » Implicitně zadaná zobrazení A Tečny a normály k implicitně zadaným plochám • Gradient funkce • Tečné a normálové prostory A Vázané extrémy • Metoda Lagrangeových multiplikátorů • Speciální optimalizační metody ooooooooooooc Doporuč. Martin Panák, Jan Slovák, Drsná matematika, e-text. ooooooooooooc Doporuč. • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Zuzana Došlá, Ondřej Došlý, Diferenciální počet funkcí více proměnných, MU Brno, 2006, 150 s. • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Zuzana Došlá, Ondřej Došlý, Diferenciální počet funkcí více proměnných, MU Brno, 2006, 150 s. • Zuzana Došlá, Roman Plch, Petr Sojka, Diferenciální počet funkcí více proměnných s programem Maple, MU Brno, 1999, 273 s. (příp. http://www.math.muni.cz/~plch/mapm). • Martin Panák, Jan Slovák, Drsná matematika, e-text. • Zuzana Došlá, Ondřej Došlý, Diferenciální počet funkcí více proměnných, MU Brno, 2006, 150 s. • Zuzana Došlá, Roman Plch, Petr Sojka, Diferenciální počet funkcí více proměnných s programem Maple, MU Brno, 1999, 273 s. (příp. http://www.math.muni.cz/~plch/mapm). » Předmětové záložky v IS MU Obsah p. určování limit, resp. důkaz neexistence ooooooooooooc □ s - = Obsah p. ooooooooooooc • určování limit, resp. důkaz neexistence • výpočty parciálních a směrových derivací ooooooooooooc Obsah p. • určování limit, resp. důkaz neexistence • výpočty parciálních a směrových derivací • použití diferenciálu - aproximace, tečná nadrovina • určování limit, resp. důkaz neexistence • výpočty parciálních a směrových derivací • použití diferenciálu - aproximace, tečná nadrovina • využití Taylorovy věty a Hessiánu pro aproximaci • určování limit, resp. důkaz neexistence • výpočty parciálních a směrových derivací • použití diferenciálu - aproximace, tečná nadrovina • využití Taylorovy věty a Hessiánu pro aproximaci • Jacobián zobrazení a jeho inverze (včetně důkazu existence) Obsah p. ooooooooooooc • určování limit, resp. důkaz neexistence • výpočty parciálních a směrových derivací • použití diferenciálu - aproximace, tečná nadrovina • využití Taylorovy věty a Hessiánu pro aproximaci • Jacobián zobrazení a jeho inverze (včetně důkazu existence) • určování lokálních a globálních extrémů (vázané extrémy až na příští písemce) Q Inverzní a implicitní zobrazení • Věta o inverzním zobrazení • Implicitně zadaná zobrazení Inverzní a implicitní zobrazeni •ooooooo Tečny a normály k i OOOOOOO Tiplicitne zadaným plochám Vazane extrémy ooooooooooooc Věta o inverzním zobrazení ■ ^^^| ^^^| ^B ^| ^H 1 ■ Věta Nechť F : En —» En je spojitě diferencovatelné zobrazení na nějakém okolí bodu x* e En a nechť je Jacobiho matice D1F(x*) invertibilní Pak na nějakém okolí bodu x* existuje inverzní zobrazení F_1 a jeho diferenciál v bodě F(x*) je inverzním zobrazením k D1F(x*), tzn. je zadán inverzní maticí k Jacobiho matici zobrazení F v bodě x*. Inverzní a implicitní zobrazeni •ooooooo Tečny a normály k i OOOOOOO Tiplicitne zadaným plochám Vazane extrémy ooooooooooooc Věta o inverzním zobrazení ■ ^^^| ^^^| ^B ^| ^H 1 ■ Věta Nechť F : En —» En je spojitě diferencovatelné zobrazení na nějakém okolí bodu x* e En a nechť je Jacobiho matice D1F(x*) invertibilní Pak na nějakém okolí bodu x* existuje inverzní zobrazení F_1 a jeho diferenciál v bodě F(x*) je inverzním zobrazením k D1F(x*), tzn. je zadán inverzní maticí k Jacobiho matici zobrazení F v bodě x*. Princip důkazu: Z pravidla pro derivování složené funkce vyplývá, že pokud diferencovatelná inverze existuje, pak musí být její Jacobiho matice inverzí k původní Jacobiho matici (srovnejte s případem 1 proměnné). Důkaz poměrně komplikovaným způsobem vyvozuje, že díky invertovatelnosti Jacobiho matice existuje diferencovatelná inverze. ooooooooooooc Věta o impli Pro jednoduchost vyložíme ideu v rovině E2: □ s - = ■€. -o<\(y Věta o impli ooooooooooooc Pro jednoduchost vyložíme ideu v rovině E^. Pro spojitě diferencovatelnou funkci F{x,y) : E2 —> K hledejme body [x,y], ve kterých platí F{x,y) = 0. Příkladem může být třeba obvyklá (implicitní) definice přímek a kružnic: F(x, y) = ax + by + c = 0 F{x,y) = {x-sf + {y-tf 0, r > 0. ooooooooooooc Věta o impli Pro jednoduchost vyložíme ideu v rovině E^. Pro spojitě diferencovatelnou funkci F{x,y) : E2 —> K hledejme body [x,y], ve kterých platí F{x,y) = 0. Příkladem může být třeba obvyklá (implicitní) definice přímek a kružnic: F(x, y) = ax + by + c = 0 F(x,y) = (x-s)2 + (y-t)2 0, r > 0. V prvním případě je (při b 7^ 0) předpisem zadaná funkce a y = f (x) c ~b pro všechna x. ooooooooooooc Věta o impli Pro jednoduchost vyložíme ideu v rovině E^. Pro spojitě diferencovatelnou funkci F{x,y) : E2 —> K hledejme body [x,y], ve kterých platí F(x,y) = 0. Příkladem může být třeba obvyklá (implicitní) definice přímek a kružnic: F(x, y) = ax + by + c = 0 F(x,y) = (x- s)2 + (y - ř)2 - r2 = 0, r > 0. V prvním případě je (při b 7^ 0) předpisem zadaná funkce y = f (x) c ~b pro všechna x. Ve druhém případě umíme pouze pro [a, b] splňující rovnici kružnice a b 7^ ř najít okolí bodu a, na kterém nastane jedna z možností: y = f (x) = t + \J (x — s)2 — r, y = f (x) = ŕ - V(*-s)2-r. = Body [s ± r, ŕ] také vyhovují rovnici kružnice, platí v nich ale Fy(s ± r, ŕ) = 0, což vystihuje polohu tečny ke kružnici v těchto bodech rovnoběžné s osou y. V těchto bodech neumíme najít okolí, na němž by kružnice byla popsána jako funkce y = f (x). Body [s ± r, ŕ] také vyhovují rovnici kružnice, platí v nich ale Fy(s ± r, ŕ) = 0, což vystihuje polohu tečny ke kružnici v těchto bodech rovnoběžné s osou y. V těchto bodech neumíme najít okolí, na němž by kružnice byla popsána jako funkce y = f (x). Navíc umíme spočítat i derivace: f'(x) 1 2(x - s) V(x-s)2-r^ y Body [s ± r, ŕ] také vyhovují rovnici kružnice, platí v nich ale Fy(s ± r, ŕ) = 0, což vystihuje polohu tečny ke kružnici v těchto bodech rovnoběžné s osou y. V těchto bodech neumíme najít okolí, na němž by kružnice byla popsána jako funkce y = f (x). Navíc umíme spočítat i derivace: f'(x) 1 2(x - s) V(x-s)2-r^ y Naopak, pokud budeme chtít najít závislost x = ŕ(y) takovou, aby F(f(y),y) = 0, pak v okolí bodů (s± r, ř) bez problémů uspějeme. Všimněme si, že v těchto bodech je parciální derivace Fx nenulová. Shrňme pozorování (pro pouhé dva příklady): Shrňme pozorování (pro pouhé dva příklady): Pro funkci F{x,y) a bod [a, b] e E2 takový, že F{a, b) = 0, umíme najít funkci y = f (x) splňující F{x, f (x)) = 0, pokud je Fy{a, b) ^ 0. V takovém případě umíme i vypočíst f'{x) = —Fx/Fy. Z následující věty plyne, že takto to platí vždy, navíc rozšířené i na libovolné počty proměnných. Shrňme pozorování (pro pouhé dva příklady): Pro funkci F(x,y) a bod [a, b] e E2 takový, že F(a, b) = 0, umíme najít funkci y = f (x) splňující F(x, f (x)) = 0, pokud je Fy(a, b) 7^ 0. V takovém případě umíme i vypočíst f'{x) = —Fx/Fy. Z následující věty plyne, že takto to platí vždy, navíc rozšířené i na libovolné počty proměnných. Poslední tvrzení o derivaci přitom je dobře zapamatovalné (i pochopitelné) z výrazu pro diferenciál: 0 = dF = Fxdx + Fy áy = (Fx + Fyf'{x)) áx. Věta (O implicitní funkci) Nechť F : En+i —»■ R je spojitě diferencovatelná funkce na otevřeném okolí bodu [x*,y*] e f„ x K, ve kterém je F(x*,y*) = 0 a §^(x*,y*) ^ 0. Porom existuje spojitá funkce f : En —> R definovaná na nějakém okolí U bodu x* G En taková, že F(x, f(x)) = 0 pro všechny x G U. Navíc má funkce f v okolí bodu x* parciální derivace splňující df_ dx; 00 fg(*,f(x)) f(x,f(x))" Příklad Určete lokální extrémy funkce z implicitně rovnicí F(x,y,z) f(x,y), která je určena xz — w2yz - x2 + y2 + z2 1. Teeny a normály k implicitne zadaným pi ooooooo Příklad Určete lokální extrémy funkce z = f (x, y), která je určena implicitně rovnicí F(x, y, z) = x2 + y2 + z2 — xz — V2yz = 1. Derivováním rovnosti podle x a y dostáváme: 2x + 2z • zx — z — x • zx — v 2yzx = 0 2y + 2z • Zy — x ■ Zy — V2z — v2yzy = 0, odkud vyjádříme z — 2x V2z — 2y 2z — x — v2y 2z — x — v2y Řešení (pokr.) Stacionární body musí splňovat: zx = 0, zy = 0, tj. z = 2x = \/2y, a tedy y = \/2x. Dosazením do původní rovnice dostáváme stacionární body [1, \/2,2] a [—1, — \/2, —2]. V těchto bodech je Fz^0 (je to zároveň jmenovatel všech zde vystupujících zlomků), proto je v jejich okolí implicitně určena jistá funkce z = f(x, y). Dalším derivováním implicitní rovnice vypočteme parciální derivace f 2. řádu: 2z — x — v2y *-xy 0, <-yy 2z — x — v2y Řešení (pokr.) Stacionární body musí splňovat: zx = 0, zy = 0, tj. z = 2x = y/2y, a tedy y = \/2x. Dosazením do původní rovnice dostáváme stacionární body [1, \/2,2] a [—1, — \/2, —2]. V těchto bodech je Fz^0 (je to zároveň jmenovatel všech zde vystupujících zlomků), proto je v jejich okolí implicitně určena jistá funkce z = f(x, y). Dalším derivováním implicitní rovnice vypočteme parciální derivace f 2. řádu: 2z — x — v2y *-xy 0, <-yy 2z — x — v2y Ve stacionárních bodech je Hf negativně, resp. pozitivně definitní, proto zde nastávají lokální maximum, resp. minimum funkce f. Nejobecnější případ, kdy definujeme implicitně zadané zobrazení, popisuje následující věta (v případě n=l kopíruje větu o implicitní funkci). Nejobecnější případ, kdy definujeme implicitně zadané zobrazení, popisuje následující věta (v případě n=l kopíruje větu o implicitní funkci). Věta (0 implicitním zobrazení) Nechť F : Em+n —► En je spojitě diferencovatelné zobrazení na otevřeném okolí bodu [x*,y*] G Em x En = Em+n, v němž platí F{x*,y*) = 0 a det D^F ^ 0. Potom existuje spojitě diferencovatelné zobrazení G : Em —>■ En definované na nějakém okolí U bodu x* G Em s obrazem G{U), který obsahuje bod y*, takové, že F(x, G(x)) = 0 pro všechny x G U. Navíc je Jacobiho matice D1 G zobrazení G na okolí bodu x* zadána součinem matic D'Gix) = -{D±F)-\x, G(x)) ■ DlF{x, G(x)). O Tečny a normály k implicitně zadaným plochám • Gradient funkce • Tečné a normálové prostory ooooooooooooc Gradient Definition Pro spojitě diferencovatelnou funkci f{x\,... ,xn) : En —>■ R se vektor df df df v dx\' ' dxn / nazývá gradient funkce f. V technické a fyzikální literatuře se často zapisuje také jako grád f. = Definition Pro spojitě diferencovatelnou fun ke f(xi,.. ■,*n) in- -►M se vektor "-( 'df ,<3V dfs " ' dxn, ) nazývá gradient funkce f. V technické a fyzikální literatuře se často za pisuje take jako grs df. Rovnost f{x\,... ,xn) = b s pevnou hodnotou b G M zadává podmnožinu M C En, která mívá vlastnosti (n — l)-rozměrné nad plochy. Definition Pro spojitě diferencovatelnou fun ke f(xi,.. ■,*n) in- -^M se vektor "-( 'df ,<3V dfs " ' dxn, ) nazývá gradient funkce f. V technické a fyzikální literatuře se často za pisuje take jako grs df. Rovnost f{x\,... ,xn) = b s pevnou hodnotou b G M zadává podmnožinu M C En, která mívá vlastnosti (n — l)-rozměrné nadplochy. Přesněji: pokud je vektor parciálních derivací nenulový, můžeme lokálně množinu M popsat jako graf spojitě diferencovatelné funkce v n — 1 proměnných. Definition Pro spojitě diferencovatelnou fun ke f(xi,.. ■,*n) in- -►M se vektor "-( 'df ,<3V dfs " ' dxn, ) nazývá gradient funkce f. V technické a fyzikální literatuře se často za pisuje take jako grs df. Rovnost f{x\,... ,xn) = b s pevnou hodnotou b G M zadává podmnožinu M C En, která mívá vlastnosti (n — l)-rozměrné nadplochy. Přesněji: pokud je vektor parciálních derivací nenulový, můžeme lokálně množinu M popsat jako graf spojitě diferencovatelné funkce v n — 1 proměnných. Hovoříme v této souvislosti také o úrovňových množinách Mt, (analogie vrstevnic v př. n = 2). Na derivacích křivek ležících v úrovňové množině Mh se bude diferenciál df vždy vyčíslovat nulově: f(c(r)) = b pro všechna ř, proto d dt ŕ(c(t))=dŕ(c'(í)) = 0. Na derivacích křivek ležících v úrovňové množině Mt, se bude diferenciál áf vždy vyčíslovat nulově: f{c{t)) = b pro všechna ř, proto d dt ŕ(c(t))=dŕ(c'(t)) = 0. Pro obecný vektor v = (y-y,..., v„) G En je velikost příslušné směrové derivace funkce f: dvf\ df -V1 + --- + df cos v? 11 df||||v| 9xi 9x„ kde (/? je odchylka vektoru v od gradientu funkce f. Dokázali jsme: = Na derivacích křivek ležících v úrovňové množině Mt, se bude diferenciál df vždy vyčíslovat nulově: f{c{t)) = b pro všechna ř, proto d dt f(c(t))=df(c'(t)) = 0. Pro obecný vektor v = (ví,..., vn) e En je velikost příslušné směrové derivace funkce f: dvf\ df -V1 + --- + df cos v? 11 df||||v| 9xi 9x„ kde (/? je odchylka vektoru v od gradientu funkce f. Dokázali jsme: Směr zadaný gradientem v bodě x = (xi,..., x„) je právě ten směr, ve kterém funkce f nejrychleji roste. Tečná rovina k neprázdné úrovňové množině Mt, v okolí jejího bodu s nenulovým gradientem d f je určena ortogonálním doplňkem ke gradientu. Násobkům gradientu v tomto případě říkáme normálový vektor nadplochy Mt,. Pro funkci f n proměnných a bod P = (a\,..., an) € Mt, v jehož okolí je Mt, grafem funkce (n — 1) proměnných je implicitní rovnice pro tečnou nadrovinu 0 = t—(P) ■ (xi - ai) + • • • + t—(P) ■ (x„ - an). (JX\ oxn □ s - = Example (Model osvětlení 3D objektu) Pro 2D povrch známe směr v dopadu světla, tj. máme množinu M zadanou implicitně rovnicí f(x,y,z) = 0 a vektor v. Intenzitu osvětlení bodu P G M pak definujme jako Iq cosy, kde tp je úhel mezi normálou zadanou gradientem a vektorem opačným ke směru světla. (Znaménko říká, kterou stranu plochy osvětlujeme, /o je tzv. svítivost.) Např. v = (1,1, —1) (tj. „šikmo dolů") a f(x, y, z) = x2 + y2 + z2 - 1. Pro bod P = (x, y, z) G M /(P) grád f • v grád f\\\\v -2x - 2y + 2z 2^3 /o- Dle očekávání je plnou intenzitou Iq osvětlen bod P = 4=(—1, —1,1) na povrchu koule. □ s oooooooo oooo«oo ooooooooooooc Tečné a normálové prostory Obecné dimenze: funkce F = (f\,... ,fn) : Em+n fi(x1,...,xm+n) = b,-, / = !,... -4£„a/i rovnic ,n. dle věty o implicitní funkci je „většinou" množina všech řešení (xi,... ,xm+n) grafem zobrazení G : Em —► En. Pro pevnou volbu b = (i>i,..., r)n) je samozřejmě množinou M všech řešení průnik nadploch M{b;, fj) příslušejících jednotlivým rovnicím f, = b,. Totéž platí pro tečné směry a normálové směry: ooooooooooooc Tečné a ostory Obecné dimenze: funkce F = (f\,..., fn) fi(x1,...,xm+n) = b,-, i Em+n -4f„an rovnic --l,...,n. dle věty o implicitní funkci je „většinou" množina všech řešení (xi,... ,xm+n) grafem zobrazení G : Em —► En. Pro pevnou volbu b = (£>i,..., bn) je samozřejmě množinou M všech řešení průnik nadploch M{b;, fj) příslušejících jednotlivým rovnicím f, = b,. Totéž platí pro tečné směry a normálové směry: Afinní podprostor v Em+n obsahující právě všechny tečny k M bodem P dán rovnicemi: 0 9xi (P) • (xi - ai) + df\ . . . . + T— (P) ' (^m+n - am+n) uxn 9xi (P) • (xi - ai) + dfn + fT~{P) ' (xm+n - am+n). Tento podprostor se nazýva tečný prostor k (implicitně zadané) ploše M v bodě P. Normálový prostor v bodě P je afinní podprostor generovaný bodem P a gradienty všech funkcí f\,..., fn v bodě P, tj. řádky Jacobiho matice D1F. Tento podprostor se nazýva tečný prostor k (implicitně zadané) ploše M v bodě P. Normálový prostor v bodě P je afinní podprostor generovaný bodem P a gradienty všech funkcí f\,..., fn v bodě P, tj. řádky Jacobiho matice D1F. Příklad * Spočtěme tečnu a normálový prostor Uvažujme rovnici 0 = f{x, y,z)=z- ke kuželosečce v £3- - V*2 + y2 kuželu s vrcholem v počátku a rovinu zadanou 0 = g(x,y,z) = z- 2x + y + l. Bod P = (1,0,1) patří jak kuželu, tak rovině a průn dvou ploch je křivka. i k M těchto ---------------------/ = Příklad (pokr.) Její tečnou v bodě P bude přímka zadaná rovnicemi Příklad (pokr.) Její tečnou v bodě P bude přímka zadaná rovnicemi 0 ,2x x=l,y=0 (x-1)-—==2y 2v*2+y2 2V*2 + y2 + l(z-l) = -x + z 0 = -2(x - 1) + y + (z - 1) = -2x + y + z + 1 ■y x=l,y=0 Příklad (pokr.) Její tečnou v bodě P bude přímka zadaná rovnicemi 0 ,2x (x-1) x=l,y=0 2V*2+y2 2y x=l,y=0 2Vx2 + y2 + l(z-l) = -x + z 0 = -2(x - 1) + y + (z - 1) = -2x + y + z + 1 zatímco rovina kolmá k naší křivce bodem P bude parametricky dána výrazem (1,0,1)+r(-l,0,l) + a(-2,l,l) s parametry r a a. ■y Q Vázané extrémy • Metoda Lagrangeových multiplikátorů • Speciální optimalizační metody □ a - = i -o o. o Již dříve jsme se zabývali úlohou nalézt absolutní extrém dané funkce na (uzavřené) množině, což vedlo na vyšetření lokálních extrémů funkce na hranici této množiny. Jinými slovy, na hledání extrémů funkce v bodech, které jsou vázány nějakou další podmínkou. Již dříve jsme se zabývali úlohou nalézt absolutní extrém dané funkce na (uzavřené) množině, což vedlo na vyšetření lokálních extrémů funkce na hranici této množiny. Jinými slovy, na hledání extrémů funkce v bodech, které jsou vázány nějakou další podmínkou. Ukážeme nejprve názorně graficky na případu funkcí dvou proměnných obecnou metodu. Příklad Určete lokální extrémy funkce f{x,y) = x2y na množině M dané implicitně rovnicí 5x + 2y = 14. Již dříve jsme se zabývali úlohou nalézt absolutní extrém dané funkce na (uzavřené) množině, což vedlo na vyšetření lokálních extrémů funkce na hranici této množiny. Jinými slovy, na hledání extrémů funkce v bodech, které jsou vázány nějakou další podmínkou. Ukážeme nejprve názorně graficky na případu funkcí dvou proměnných obecnou metodu. ' Příklad ' Určete lokální extrémy funkce f{x,y) -implicitně rovnicí 5x2 + 2y2 = 14. = x2y na množině M dané Řešení Viz worksheet v Maplu. 1 V předchozím příkladu jsme viděli, že normálový vektor (tj. gradient) funkce, k níž hledáme extrém, musí být ve vyšetřovaném bodě prvkem normálového prostoru k ploše (v témže bodě). Toto samozřejmě platí i obecně. V předchozím příkladu jsme viděli, že normálový vektor (tj. gradient) funkce, k níž hledáme extrém, musí být ve vyšetřovaném bodě prvkem normálového prostoru k ploše (v témže bodě). Toto samozřejmě platí i obecně. Pokud je M ve všech svých bodech grafem hladkého zobrazení, musí být každý extrém P G M stacionárním bodem, tj. pro každou křivku c(ř) C M procházející přes P = c(0) musí být h(c(t)) extrémem pro tuto funkci jedné proměnné. Proto musí platit ^Kc(ř))|t=o = dc,(Q)h(P) = d/i(P)(c'(0)) = 0. V předchozím příkladu jsme viděli, že normálový vektor (tj. gradient) funkce, k níž hledáme extrém, musí být ve vyšetřovaném bodě prvkem normálového prostoru k ploše (v témže bodě). Toto samozřejmě platí i obecně. Pokud je M ve všech svých bodech grafem hladkého zobrazení, musí být každý extrém P G M stacionárním bodem, tj. pro každou křivku c(ř) C M procházející přes P = c(0) musí být h(c(t)) extrémem pro tuto funkci jedné proměnné. Proto musí platit jth(c(t))lt=0 = dc,(Q)h(P) = d/i(P)(c'(0)) = 0. Tato vlastnost je ekvivalentní tvrzení, že gradient h leží v normálovém podprostoru (přesněji v jeho zaměření). Takové body P G M budeme nazývat stacionární body funkce h vzhledem k vazbám F. V praxi mívají optimalizační úlohy často m + n parametrů, které jsou vázány n podmínkami. V našem jazyce diferenciálního počtu tedy hledáme extrémy spojitě diferencovatelné funkce h na množině bodů M zadaných implicitně rovnicí F{x\,... ,xm+n) = 0 {F ■ Em+n —s- E„). Normálový prostor k naší množině M je generován řádky Jacobiho matice zobrazení F a stacionární body jsou proto ekvivalentně určeny následujícím tvrzením, kterému se říká metoda Lagrangeových multiplikátorů: V praxi mívají optimalizační úlohy často m + n parametrů, které jsou vázány n podmínkami. V našem jazyce diferenciálního počtu tedy hledáme extrémy spojitě diferencovatelné funkce h na množině bodů M zadaných implicitně rovnicí F(x\,... ,xm+n) = 0 {F ■ Em+n —s- E„). Normálový prostor k naší množině M je generován řádky Jacobiho matice zobrazení F a stacionární body jsou proto ekvivalentně určeny následujícím tvrzením, kterému se říká metoda Lagrangeových multiplikátorů: Nechť F = (fi,..., fn) : Em+n —>■ En je spojitě diferencovatelná v okolí bodu P, F (P) = 0 a M je zadána implicitně rovnicí F(xi,..., xm+n) = 0, přičemž hodnost matice DXF v bodě P je n. Pak P je stacionárním bodem spojitě diferencovatelné funkce h : Em+n —í- R právě, když existují reálné parametry Ai,..., A„ takové, že grád h = Xi grád f\-\--------h A„ grád fn. Všimněme si počtu neznámých a rovnic v tomto algoritmu: gradienty jsou vektory o m + n souřadnicích, tedy požadavek z věty dává m + n rovnic. Jako neznámé máme jednak souřadnice xi,... ,xm+n hledaných stacionárních bodů P, ale navíc také n parametrů A, v hledané lineární kombinaci. Zbývá však požadavek, že hledaný bod P patří implicitně zadané množině M, což představuje dalších n rovnic. Celkem tedy máme 2n + m rovnic pro 2n + m proměnných a proto lze očekávat, že řešením bude diskrétní množina bodů P (tj. každý z nich bude izolovaným bodem). ooo«o ooooooc Výklad o vázaných extrémech jsme začali tím, že pro nalezení absolutních extrémů funkce na kompaktní množině často potřebujeme vyšetření extrémů na množině bodů vázaných nějakou podmínkou. ooo«o ooooooc Výklad o vázaných extrémech jsme začali tím, že pro nalezení absolutních extrémů funkce na kompaktní množině často potřebujeme vyšetření extrémů na množině bodů vázaných nějakou podmínkou. Ilustrujme si to na příkladu: Příklad Maximalizujte f(x,y) = 2x + y za podmínky ^- + y2 < 1. Množina určená vazební podmínkou je uzavřená a ohraničená, proto zde nabývá jakákoliv spojitá funkce svých extrémů, a to buď ve stacionárních bodech nebo na hranici. Snadno se ale přesvědčíme (dr(x,y) = (2,1)), že uvnitř množiny extrémy nejsou. Proto maximalizujeme funkci f za podmínky ^- +y2 = 1. Množina určená vazební podmínkou je uzavřená a ohraničená, proto zde nabývá jakákoliv spojitá funkce svých extrémů, a to buď ve stacionárních bodech nebo na hranici. Snadno se ale přesvědčíme (dr(x,y) = (2,1)), že uvnitř množiny extrémy nejsou. Proto maximalizujeme funkci f za podmínky ^- + y2 = 1. Sestrojíme Lagrangeovu funkci L(x, y, A) = 2x + y - A(^- + y2 - 1). Pak dostáváme: 0 0 Lv = 2-= 1- + y2 A2 2Ay -1. Množina určená vazební podmínkou je uzavřená a ohraničená, proto zde nabývá jakákoliv spojitá funkce svých extrémů, a to buď ve stacionárních bodech nebo na hranici. Snadno se ale přesvědčíme (dr(x,y) = (2,1)), že uvnitř množiny extrémy nejsou. Proto maximalizujeme funkci f za podmínky ^- + y2 = 1. Sestrojíme Lagrangeovu funkci L(x, y, A) = 2x + y - A(^- + y2 - 1). Pak dostáváme: Odtud snadno x (resp. A = —^Y~ h v 0 = LX = 2- A? 0 = Ly = 1- 2Ay 0 _x2 4 + y2 -1. = 2A' d tedy A = 17 y 17 17' y = —j= pro minimum). ooooo«ooooooc ni meto Zmiňme se jen ve stručnosti o speciálních optimalizačních technikách, které se v dnešní praxi používají. Zájemce o bližší seznámení s nimi můžeme odkázat na další předměty MU, např. • Optimalizace - PřF: M0160 (jaro) • Optimalizace - PV027 (jaro) • Úlohy lineární a celočíselné optimalizace a jejich řešení -IA102 (jaro) • Lineární programování - PřF: M4110 (jaro) • Matematické programování - PřF: M5170 (podzim) • Celočíselné programování - PřF: M8150 (jaro) Již dříve jsme zmínili, že funkce nejrychleji roste ve směru gradientu (a nejrychleji klesá ve směru opačném) - proto je přirozené se při hledání maxima vydat z daného bodu ve směru gradientu (analogie chození do kopce nejprudším svahem). Otázka je, jak dlouho „jít" a jak často gradient počítat. Iterace: xn+1 = xn + 7„ grád f(xn), pro dostatečně malé 7„, aby f{xn+\) > f(xn). oooooo«oooooc Metoda Již dříve jsme zmínili, že funkce nejrychleji roste ve směru gradientu (a nejrychleji klesá ve směru opačném) - proto je přirozené se při hledání maxima vydat z daného bodu ve směru gradientu (analogie chození do kopce nejprudším svahem). Otázka je, jak dlouho „jít" a jak často gradient počítat. Iterace: xn+i = xn + 7„ grád f (x„), pro dostatečně malé 7„, aby f{xn+\) > f(xn). Problémy: • náročný opakovaný výpočet 7, • velký počet iterací v případě velmi různorodé křivosti v různých směrech; např Rosenbrockova banánová funkce f(x,y) = (l-x)2 + 100(y-x2)2. ooooooo«ooooc Newton« acni rru Newtonova metoda je dobře známý numerický postup pro nalezení kořenů dané reálné funkce f . Známe-li bod xo „rozumně" blízko kořene, zkonstruujeme v bodě [xo, f(xo)] tečnu ke grafu funkce f a za bod xi zvolíme průsečík tečny s osou x. Tento postup opakujeme. Snadno je vidět, že platí rekurentní vztah 0,... ,xn > 0. □ g - = ^ -00,0 ooooooooooo»c Simplexe Standardní úlohu řeší klasická Simplexová metoda (George Dantzig, 1947). ooooooooooo»c Simplexe Standardní úlohu řeší klasická Simplexová metoda (George Dantzig, 1947). Úvodní fáze spočívá v nalezení nějakého vrcholu na polytopu (zobecnění polyedru na více dimenzí), který je tvořen body vyhovujícími podmínkám. V dalších krocích postupuje po hranách do vrcholů s vyšší hodnotou účelové funkce. ooooooooooo»c Simplexe Standardní úlohu řeší klasická Simplexová metoda (George Dantzig, 1947). Úvodní fáze spočívá v nalezení nějakého vrcholu na polytopu (zobecnění polyedru na více dimenzí), který je tvořen body vyhovujícími podmínkám. V dalších krocích postupuje po hranách do vrcholů s vyšší hodnotou účelové funkce. Sice je ukázán příklad podmínek, kdy simplexová metoda projde nešikovně všech 2" vrcholů (jde o příklad zborcené n-rozměrné krychle), a tedy metoda je v nejhorším případě exponenciální, ale v praxi je obvykle pozoruhodně úspěšná (kolem roku 2000 bylo dokázáno, že očekávaný čas běhu na náhodném vstupu je polynomiální). ' Příklad * Maximalizujte f = = 2x — 3y + 4z za podmínek 4x - 3y + z < 3 x + y+ z < 10 2x + y - z < 10 x > 0,y > 0,z > 0. .