Afinní prostory Konvexní množiny a lineární programování Afinní zobrazení Matematika I – 11b Analytická geometrie – afinní prostory Jan Slovák Masarykova univerzita Fakulta informatiky 28. 11. 2012 Afinní prostory Konvexní množiny a lineární programování Afinní zobrazení Obsah přednášky 1 Afinní prostory 2 Konvexní množiny a lineární programování 3 Afinní zobrazení Afinní prostory Konvexní množiny a lineární programování Afinní zobrazení Plán přednášky 1 Afinní prostory 2 Konvexní množiny a lineární programování 3 Afinní zobrazení Afinní prostory Konvexní množiny a lineární programování Afinní zobrazení Definition Afinním prostorem A se zaměřením V rozumíme množinu bodů P, spolu se zobrazením P × V → P, (A, v) → A + v, splňující vlastnosti (1)–(3). Pro libovolný pevně zvolený vektor v ∈ V je tak definována translace τv : A → A jako zúžené zobrazení τv : P P × {v} → P, A → A + v. Dimenzí afinního prostoru A rozumíme dimenzi jeho zaměření. Afinní prostory Konvexní množiny a lineární programování Afinní zobrazení Definition Afinním prostorem A se zaměřením V rozumíme množinu bodů P, spolu se zobrazením P × V → P, (A, v) → A + v, splňující vlastnosti (1)–(3). Pro libovolný pevně zvolený vektor v ∈ V je tak definována translace τv : A → A jako zúžené zobrazení τv : P P × {v} → P, A → A + v. Dimenzí afinního prostoru A rozumíme dimenzi jeho zaměření. Nadále nebudeme rozlišovat A a P v označení. Z axiomů okamžitě plyne pro libovolné body A, B, C v afinním prostoru A A − A = 0 ∈ V B − A = −(A − B) (B − A) + (C − B) = (C − A). Afinní prostory Konvexní množiny a lineární programování Afinní zobrazení Volba jednoho pevného bodu A0 ∈ A nám určuje bijekci mezi V a A. Afinní prostory Konvexní množiny a lineární programování Afinní zobrazení Volba jednoho pevného bodu A0 ∈ A nám určuje bijekci mezi V a A. Při volbě pevné báze u ve V tak dostáváme pro každý bod A ∈ A jednoznačné vyjádření A = A0 + x1u1 + · · · + xnun. Afinní souřadnice Hovoříme o afinní soustavě souřadnic (A0; u1, . . . , un) zadané počátkem afinní souřadné soustavy A0 a bazí zaměření u. Hovoříme také o afinním repéru (A0, u). Afinní prostory Konvexní množiny a lineární programování Afinní zobrazení Volba jednoho pevného bodu A0 ∈ A nám určuje bijekci mezi V a A. Při volbě pevné báze u ve V tak dostáváme pro každý bod A ∈ A jednoznačné vyjádření A = A0 + x1u1 + · · · + xnun. Afinní souřadnice Hovoříme o afinní soustavě souřadnic (A0; u1, . . . , un) zadané počátkem afinní souřadné soustavy A0 a bazí zaměření u. Hovoříme také o afinním repéru (A0, u). Afinní souřadnice bodu A v soustavě (A0, u) jsou souřadnicemi vektoru A − A0 v bázi u zaměření V . Afinní prostory Konvexní množiny a lineární programování Afinní zobrazení Volba jednoho pevného bodu A0 ∈ A nám určuje bijekci mezi V a A. Při volbě pevné báze u ve V tak dostáváme pro každý bod A ∈ A jednoznačné vyjádření A = A0 + x1u1 + · · · + xnun. Afinní souřadnice Hovoříme o afinní soustavě souřadnic (A0; u1, . . . , un) zadané počátkem afinní souřadné soustavy A0 a bazí zaměření u. Hovoříme také o afinním repéru (A0, u). Afinní souřadnice bodu A v soustavě (A0, u) jsou souřadnicemi vektoru A − A0 v bázi u zaměření V . Volba afinního souřadného systému ztotožňuje n-rozměrný afinní prostor A se standardním afinním prostorem An. Afinní prostory Konvexní množiny a lineární programování Afinní zobrazení Definition (Afinní podprostory) Neprázdná podmnožina Q ⊂ A afinního prostoru A se zaměřením V se nazývá afinní podprostor v A, je-li podmnožina W = {B − A; A, B ∈ Q} ⊂ V vektorovým podprostorem a pro libovolné A ∈ Q, v ∈ W je A + v ∈ Q. Afinní prostory Konvexní množiny a lineární programování Afinní zobrazení Definition (Afinní podprostory) Neprázdná podmnožina Q ⊂ A afinního prostoru A se zaměřením V se nazývá afinní podprostor v A, je-li podmnožina W = {B − A; A, B ∈ Q} ⊂ V vektorovým podprostorem a pro libovolné A ∈ Q, v ∈ W je A + v ∈ Q. Skutečně je rozumné mít obě podmínky v definici, protože je snadné najít příklady podmnožin, které budou splňovat první, ale nikoliv druhou. (Např. přímka v rovině s vyjmutým jedním bodem.) Afinní prostory Konvexní množiny a lineární programování Afinní zobrazení Plán přednášky 1 Afinní prostory 2 Konvexní množiny a lineární programování 3 Afinní zobrazení Afinní prostory Konvexní množiny a lineární programování Afinní zobrazení Podmnožina M afinního prostoru se nazývá konvexní, jestliže s každými svými dvěma body A, B obsahuje i celou úsečku ∆(A, B). Přímo z definice je vidět, že každá konvexní množina obsahuje s každými k + 1 body v obecné poloze i celý jimi definovaný simplex. Konvexními množinami jsou např. (1) prázdná podmnožina (2) afinní podprostory (3) úsečky, polopřímky p = {P + t · v; t ≥ 0}, obecněji k– rozměrné poloprostory α = {P + t1 · v1 + · · · + tk · vk; t1, . . . , tk ∈ R, tk ≥ 0}, úhly v dvojrozměrných podprostorech β = {P + t1 · v1 + t2 · v2; t1 ≥ 0, t2 ≥ 0}, atd. Přímo z definice také plyne, že průnik libovolného systému konvexních množin je opět konvexní. Průnik všech konvexních množin obsahujících danou množinu M nazýváme konvexní obal K(M) množiny M. Afinní prostory Konvexní množiny a lineární programování Afinní zobrazení Theorem Konvexní obal libovolné podmnožiny M ⊂ A je K(M) = {t1A1 + · · · + tsAs; s i=1 ti = 1, ti ≥ 0} Konvexní obaly konečných množin bodů se nazývají konvexní mnohostěny. Jsou-li definující body A0, . . . , Ak konvexního mnohostěnu v obecné poloze, dostáváme právě k-rozměrný simplex. V případě simplexu je vyjádření jeho bodů ve tvaru afinní kombinace definujících vrcholů jednoznačné. Afinní prostory Konvexní množiny a lineární programování Afinní zobrazení V problému lineárního programování je množina přípustných hodnot vždy konvexní. Lineární formy nabývají maxima či minima na konvexní množině vždy na hranici v některém z vrcholů z příslušného konvexního mnohočlenu. Afinní prostory Konvexní množiny a lineární programování Afinní zobrazení Plán přednášky 1 Afinní prostory 2 Konvexní množiny a lineární programování 3 Afinní zobrazení Afinní prostory Konvexní množiny a lineární programování Afinní zobrazení Zobrazení f : A → B je afinní, právě když existuje lineární zobrazení ϕ mezi zaměřeními takové, že f (x + v) = f (x) + ϕ(v) Afinní prostory Konvexní množiny a lineární programování Afinní zobrazení Zobrazení f : A → B je afinní, právě když existuje lineární zobrazení ϕ mezi zaměřeními takové, že f (x + v) = f (x) + ϕ(v) Zobrazení f je afinní, právě když zachovává afinní kombinace bodů. Afinní prostory Konvexní množiny a lineární programování Afinní zobrazení Afinní kombinace dvojice bodů můžeme také dobře vyjádřit pomocí tzv. poměru bodů na přímce. Jeli bod C afinní kombinací bodů A a B = C, C = rA + sB, pak řekneme že číslo λ = (C; A, B) = − s r je poměrem bodu C vzhledem k daným bodům A a B. Protože bod C můžeme vyjádřit jako C = A + s(B − A) = B + r(A − B), je poměr λ ve skutečnosti poměrem velikostí orientovaných vektorů C − A a C − B. Zejména je λ = −1 právě, když je C středem úsečky dané body A a B (tj. v naší afinní kombinaci bude r = s = 1 2 ). Afinní prostory Konvexní množiny a lineární programování Afinní zobrazení Naše charakterizace afinních zobrazení prostřednictvím afinních kombinací má velice srozumitelně znějící důsledek: Corollary Afinní zobrazení jsou právě ta zobrazení, která zachovávají poměry. Afinní prostory Konvexní množiny a lineární programování Afinní zobrazení Změny souřadnic Volbou afinních souřadnic (A0, u) na A a (B0, v) na B dostáváme souřadné vyjádření afinního zobrazení f : A → B. Přímo z definice je zřejmé, že stačí vyjádřit obraz f (A0) počátku souřadnic v A v souřadnicích na B, tj. vyjádřit vektor f (A0) − B0 v bázi v jako sloupec souřadnic y0 a vše ostatní je pak určeno násobením maticí zobrazení ϕ ve zvolených bazích a přičtením výsledku. Každé afinní zobrazení tedy v souřadnicích vypadá takto: x → y0 + Y · x, kde y0 je jako výše a Y je matice zobrazení ϕ. Afinní prostory Konvexní množiny a lineární programování Afinní zobrazení Transformace afinních souřadnic odpovídá, obdobně jako u lineárních zobrazení, vyjádření identického zobrazení ve zvolených afinních repérech. Změna souřadného vyjádření afinního zobrazení v důsledku změny bazí se snadno spočte pomocí násobení a sčítání matic a vektorů. Skutečně, při změně báze na definičním oboru daném posunutím w a maticí M, přičemž staré souřadnice pomocí nových jsou x = w + M · x , a změně na oboru hodnot s posunutím z a maticí N, přičemž nové souřadnice jsou pomocí starých y = z + N · y. Afinní prostory Konvexní množiny a lineární programování Afinní zobrazení dostáváme pro zobrazení dané v původních bazích vektorem posunutí y0 a maticí Y přímým výpočtem y = z + N · y = z + N · (y0 + Y · x) = (z + N · y0 + N · Y · w) + (N · Y · M) · x . Je tedy afinní zobrazení v nových bazích dáno vektorem posunutí z + N · y0 + N · Y · w a maticí N · Y · M.