Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Matematika I – 11a Afinní geometrie Jan Slovák Masarykova univerzita Fakulta informatiky 26. 11. 2012 Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Obsah přednášky 1 Afinní geometrie 2 Konvexní množiny 3 Standardní úlohy 4 Transformace souřadnic Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Plán přednášky 1 Afinní geometrie 2 Konvexní množiny 3 Standardní úlohy 4 Transformace souřadnic Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Vrátíme se teď k úlohám elementární geometrie z podobného pohledu, jako když jsme zkoumali polohy bodů v rovině. Zjistili jsme, že všechna řešení nehomogenních systémů rovnic sice netvoří vektorové podprostory, vždy ale vznikají tak, že k jednomu jedinému řešení přičteme celý vektorový prostor řešení příslušné homogenní soustavy. Naopak, rozdíl dvou řešení nehomogenní soustavy je vždy řešením homogenní. Obdobně se chovají lineární difereční rovnice. Ve skutečnosti je podstatné, že k „bodům“ prostoru přičítáme „vektory“. Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Definition (Afinní prostory) Standarní afinní prostor An je množina všech bodů v Rn spolu s operací, kterou k bodu A = (a1, . . . , an) ∈ An a vektoru v = (v1, . . . , vn) ∈ Rn přiřadíme bod A + v = (a1 + v1, . . . , an + vn) ∈ Rn. Tyto operace splňují následující tři vlastnosti: 1 A + 0 = A pro všechny body A ∈ P a nulový vektor 0 ∈ V 2 A + (v + w) = (A + v) + w pro všechny vektory v, w ∈ V , A ∈ P 3 pro každé dva body A, B ∈ P existuje právě jeden vektor v ∈ P takový, že A + v = B. Značíme jej B − A, někdy také AB. Vektorový prostor Rn nazýváme zaměření afinního prostoru An. Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Definition (Afinní prostory) Standarní afinní prostor An je množina všech bodů v Rn spolu s operací, kterou k bodu A = (a1, . . . , an) ∈ An a vektoru v = (v1, . . . , vn) ∈ Rn přiřadíme bod A + v = (a1 + v1, . . . , an + vn) ∈ Rn. Tyto operace splňují následující tři vlastnosti: 1 A + 0 = A pro všechny body A ∈ P a nulový vektor 0 ∈ V 2 A + (v + w) = (A + v) + w pro všechny vektory v, w ∈ V , A ∈ P 3 pro každé dva body A, B ∈ P existuje právě jeden vektor v ∈ P takový, že A + v = B. Značíme jej B − A, někdy také AB. Vektorový prostor Rn nazýváme zaměření afinního prostoru An. Formálních nebezpečí – stejný symbol „+“ pro dvě různé operace: přičtení vektoru ze zaměření k bodu v afinním prostoru, ale také sčítání vektorů v zaměření Rn. Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Z definice standardního afinního prostoru okamžitě plyne pro libovolné body A, B, C v afinním prostoru An A − A = 0 ∈ V B − A = −(A − B) (B − A) + (C − B) = (C − A). Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Volba jednoho pevného bodu A0 ∈ An nám určuje bijekci mezi V = Rn a An. Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Volba jednoho pevného bodu A0 ∈ An nám určuje bijekci mezi V = Rn a An. 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í geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Volba jednoho pevného bodu A0 ∈ An nám určuje bijekci mezi V = Rn a An. 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í geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Definition (Afinní podprostory) Neprázdná podmnožina Q ⊂ An afinního prostoru An se zaměřením V se nazývá afinní podprostor v An, 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í geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Definition (Afinní podprostory) Neprázdná podmnožina Q ⊂ An afinního prostoru An se zaměřením V se nazývá afinní podprostor v An, 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í geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Generování podprostorů Pro libovolnou množinu bodů M ⊂ A v afinním prostoru se zaměřením V definujeme vektorový podprostor Z(M) = {B − A; B, A ∈ M} ⊂ V . Zejména je V = Z(A) a každý afinní podprostor Q ⊂ A splňuje sám axiomy afinního prostoru se zaměřením Z(Q). Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Generování podprostorů Pro libovolnou množinu bodů M ⊂ A v afinním prostoru se zaměřením V definujeme vektorový podprostor Z(M) = {B − A; B, A ∈ M} ⊂ V . Zejména je V = Z(A) a každý afinní podprostor Q ⊂ A splňuje sám axiomy afinního prostoru se zaměřením Z(Q). Přímo z definic je zřejmé, že průnik libovolné množiny afinních podprostorů je buď opět afinní podprostor nebo prázdná množina. Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Generování podprostorů Pro libovolnou množinu bodů M ⊂ A v afinním prostoru se zaměřením V definujeme vektorový podprostor Z(M) = {B − A; B, A ∈ M} ⊂ V . Zejména je V = Z(A) a každý afinní podprostor Q ⊂ A splňuje sám axiomy afinního prostoru se zaměřením Z(Q). Přímo z definic je zřejmé, že průnik libovolné množiny afinních podprostorů je buď opět afinní podprostor nebo prázdná množina. Afinní podprostor M v A generovaný neprázdnou podmnožinou M ⊂ A je průnikem všech afinních podprostorů, které obsahují všechny body podmnožiny M. Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Přímo z definic plyne, že pro kterýkoliv bod A0 ∈ M je M = {A0 + v; v ∈ Z(M) ⊂ Z(A)}, tj. pro generování afinního podprostoru vezmeme vektorový podprostor Z(M) v zaměření generovaný všemi rozdíly bodů z M a ten pak přičteme k libovolnému z nich. Hovoříme také o afinním obalu množiny bodů M v A. Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Přímo z definic plyne, že pro kterýkoliv bod A0 ∈ M je M = {A0 + v; v ∈ Z(M) ⊂ Z(A)}, tj. pro generování afinního podprostoru vezmeme vektorový podprostor Z(M) v zaměření generovaný všemi rozdíly bodů z M a ten pak přičteme k libovolnému z nich. Hovoříme také o afinním obalu množiny bodů M v A. Naopak, kdykoliv zvolíme podprostor U v zaměření Z(A) a jeden pevný bod A ∈ A, pak podmnožina A + U vzniklá všemi možnými součty bodů A s vektory v U je afinní podprostor. Takový postup vede k pojmu parametrizace podprostorů: Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Přímo z definic plyne, že pro kterýkoliv bod A0 ∈ M je M = {A0 + v; v ∈ Z(M) ⊂ Z(A)}, tj. pro generování afinního podprostoru vezmeme vektorový podprostor Z(M) v zaměření generovaný všemi rozdíly bodů z M a ten pak přičteme k libovolnému z nich. Hovoříme také o afinním obalu množiny bodů M v A. Naopak, kdykoliv zvolíme podprostor U v zaměření Z(A) a jeden pevný bod A ∈ A, pak podmnožina A + U vzniklá všemi možnými součty bodů A s vektory v U je afinní podprostor. Takový postup vede k pojmu parametrizace podprostorů: Nechť Q = A + Z(Q) je afinní podprostor v An a (u1, . . . , uk) je báze Z(Q) ⊂ Rn. Pak vyjádření podprostoru Q = {A + t1u1 + · · · + tkuk; t1, . . . , tk ∈ R} nazýváme parametrický popis podprostoru Q. Jeho zadání systémem rovnic v daných souřadnicích je implicitní popis podprostoru Q. Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Example Příklady afinních prostorů (1) Jednorozměrný (standardní) afinní prostor je množina všech bodů reálné přímky A1. Její zaměření je jednorozměrný vektorový prostor R (a nosná množina také R). Afinní souřadnice dostaneme volbou počátku a měřítka (tj. báze ve vektorovém prostoru R). Všechny vlastní afinní podprostory jsou 0-rozměrné, jsou to právě všechny body reálné přímky R. (2) Dvourozměrný (standardní) afinní prostor je množina všech bodů prostoru A2 se zaměřením R2. (Nosnou množinou je R2.) Afinní souřadnice dostaneme volbou počátku a dvou nezávislých vektorů (směrů a měřítek). Vlastní afinní podprostory jsou pak všechny body a přímky v rovině (0-rozměrné a 1-rozměrné). Přímky přitom jednoznačně zadáme jejich jedním bodem a jedním generátorem zaměření (tzv. parametrický popis přímky). Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Example (3) Trojrozměrný (standardní) afinní prostor je množina všech bodů prostoru A3 se zaměřením R3. Afinní souřadnice dostaneme volbou počátku a tří nezávislých vektorů (směrů a měřítek). Vlastní afinní podprostory jsou pak všechny body, přímky a roviny (0-rozměrné, 1-rozměrné a 2-rozměrné). (4) Podprostor všech řešení jedné lineární rovnice a · x = b pro neznámý bod (x1, . . . , xn) ∈ An, známý nenulový vektor koeficientů (a1, . . . , an) a skalár b ∈ R je afinní podprostor dimenze n − 1 (říkáme také, že je kodimenze 1), tj. tzv. nadrovina v An. Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Theorem Nechť (A0; u) je afinní souřadný systém v n-rozměrném afinním prostoru A. Afinní podprostory dimenze k v A, vyjádřené v daných souřadnicích, jsou právě množiny řešení řešitelných systémů n − k lineárně nezávislých lineárních rovnic v n proměnných. Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Afinní kombinace bodů Nechť A0, . . . , Ak jsou body v afinním prostoru A. Jejich afinní obal {A0 . . . , Ak} můžeme zapsat jako {A0 + t1(A1 − A0) + · · · + tk(Ak − A0); t1, . . . , tk ∈ R} a v libovolných afinních souřadnicích (tj. Ai je vyjádřen sloupcem skalárů) můžeme tutéž množinu zapsat jako A0, . . . , Ak = {t0A0 + t1A1 + · · · + tkAk; ti ∈ R, k i=0 ti = 1}. Obecně výrazy t0A0 + t1A1 + · · · + tkAk s koeficienty splňujícícmi k i=0 ti = 1 rozumíme body A0 + k i=1 ti (Ai − A0) a nazýváme je afinní kombinace bodů. Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Body A0 . . . , Ak jsou v obecné poloze, jestliže generují k-rozměný podprostor. Z našich definic je vidět, že to nastane právě, když pro kterýkoliv z nich platí, že vektory vzniklé pomocí rozdílů tohoto pevného s ostatními jsou lineárně nezávislé. Všimněme si také, že zadání posloupnosti dim A bodů v obecné poloze je ekvivalentní zadání afinního repéru s středem v prvním z nich. Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Body A0 . . . , Ak jsou v obecné poloze, jestliže generují k-rozměný podprostor. Z našich definic je vidět, že to nastane právě, když pro kterýkoliv z nich platí, že vektory vzniklé pomocí rozdílů tohoto pevného s ostatními jsou lineárně nezávislé. Všimněme si také, že zadání posloupnosti dim A bodů v obecné poloze je ekvivalentní zadání afinního repéru s středem v prvním z nich. Afinní kombinace je obdobná konstrukce pro body afinního prostoru jako byla lineární kombinace pro vektorové prostory. Skutečně, afinní podprostor generovaný body A0 . . . , Ak je roven množině všech afinních kombinací svých generátorů. Můžeme však nyní dobře zobecnit i pojem „mezi dvěma body na přímce“. V dvojrozměrném případě tomu odopovídá vnitřek trojúhelníku. Obecně budeme postupovat takto: Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Nechť A0, . . . , Ak je k + 1 bodů afinního prostoru A v obecné poloze. k–rozměrný simplex ∆ = ∆(A0, . . . , Ak) generovaný těmito body je definován jako množina všech afinních kombinací bodů Ai s pouze nezápornými koeficienty, tzn. ∆ = {t0A0 + t1A1 + · · · + tkAk; ti ∈ [0, 1] ⊂ R, k i=0 ti = 1}. Jednorozměrný simplex je úsečka, dvourozměrný trojúhelník. Zadání podprostoru jako množiny afinních kombinací bodů v obecné poloze je ekvivalentní parametrickému popisu. Obdobně pracujeme s parametrickými popisy simplexů. Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Plán přednášky 1 Afinní geometrie 2 Konvexní množiny 3 Standardní úlohy 4 Transformace souřadnic Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic 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í geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Theorem Konvexní obal libovolné podmnožiny M ⊂ A je K(M) = {t1A1 + · · · + tsAs; s i=1 ti = 1, ti ≥ 0} Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic 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í geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Jiným příkladem jsou konvexní podmnožiny generované jedním bodem a konečně mnoha vektory: Nechť u1, . . . , uk, jsou libovolné vektory v zaměření Rn, A ∈ An je libovolný bod. Rovnoběžnostěn Pk(A; u1, . . . , uk) ⊂ An je množina Pk(A; u1, . . . , uk) = {A+c1u1+· · ·+ckuk; 0 ≤ ci ≤ 1, i = 1, . . . , k}. Jsou-li vektory u1, . . . , uk nezávislé, hovoříme o k-rozměrném rovnoběžnostěnu Pk(A; u1, . . . , uk) ⊂ An. Z definice je zřejmé, že rovnoběžnostěny jsou konvexní. Ve skutečnosti jde o konvexní obaly jejich vrcholů. Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Plán přednášky 1 Afinní geometrie 2 Konvexní množiny 3 Standardní úlohy 4 Transformace souřadnic Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic (1) K podprostoru zadanému implicitně nalézt parametrický popis a naopak: Nalezením partikulárního řešení nehomogenního systému a fundamentálního řešení zhomogenizovaného systému rovnic získáme (v souřadnicích, ve kterých byly rovnice zadány) právě hledaný parametrický popis. Naopak, zapíšeme-li parametrický popis v souřadnicích, můžeme volné parametry t1, . . . , tk vyeliminovat a získáme právě rovnice zadávající daný podprostor implicitně. (2) Nalézt podprostor generovaný několika podprostory Q1, . . . , Qs (obecně různých dimenzí, např. v R3 nalézt rovinu danou bodem a přímkou, třemi body apod.) a zadat jej implicitně či parametricky: Výsledný podprostor Q je vždy určen jedním pevně zvoleným bodem Ai v každém z nich a součtem všech zaměření. Např. Q = A1 + (Z({A1, . . . , Ak}) + Z(Q1) + · · · + Z(Qs)). Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic (3) Nalézt průnik podprostorů Q1, . . . , Qs: Pokud jsou zadány v implicitním tvaru, stačí sjednotit všechny rovnice do jednoho systému (a případně vynechat lineárně závislé). Pokud je vzniklý systém neřešitelný, je průnik prázdný. V opačném případě získáme implicitní popis afinního podprostoru, který je hledaným průnikem. Pokud máme dány parametrické tvary, můžeme také hledat přímo společné body jako řešení vhodných rovnic, podobně jako při hledání průniků vektorových podprostorů. Získáme tak přímo opět parametrický popis. Pokud je podprostorů více než dva, musíme průnik hledat postupně. Máme-li jeden prostor zadaný parametricky a ostatní implicitně, stačí dosadit parametrizované souřadnice a řešit výsledný systém rovnic. Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic (4) Nalezení příčky mimoběžek p, q v A3 procházející daným bodem nebo mající předem daný směr (tj. zaměření): Příčkou rozumíme přímku, která má neprázdný průnik s oběmi mimoběžkami. Výsledná příčka r tedy bude jednorozměrným afinním podprostorem. Pokud máme zadán jeho bod A ∈ r, pak afinní podprostor generovaný p a A je buď přímka (A ∈ p) nebo rovina (A /∈ p). V prvém případě máme nekonečně mnoho řešení, jedno pro každý bod z q, v druhém stačí najít průnik B roviny p ∪ A s q a r = {A, B} . Pokud je průnik prázdný, úloha nemá řešení, v případě že q ⊂ p ∪ A , máme opět nekonečně mnoho řešení, a pokud je průnik jednoprvkový, dostáváme právě jedno řešení. Máme-li místo bodu dán směr u ∈ Rn, tj. zaměření r, pak uvažujeme opět podprostor Q generovaný p a zaměřením Z(p) + u ⊂ Rn. Opět, pokud q ⊂ Q, máme nekonečně mnoho řešení, jinak uvážíme průnik Q s q a úlohu dokončíme stejně jako v předchozím případě. Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Plán přednášky 1 Afinní geometrie 2 Konvexní množiny 3 Standardní úlohy 4 Transformace souřadnic Afinní geometrie Konvexní množiny Standardní úlohy Transformace souřadnic Dvě libovolně zvolené afinní soustavy souřadnic (A0, u), (B0, v) se obecně liší posunutím počátku o vektor (B0 − A0) a jinou bazí zaměření. Transformační rovnice tedy vyčteme ze vztahu pro obecný bod X ∈ A X = B0 + x1v1 + · · · + xnvn = B0 + (A0 − B0) + x1u1 + · · · + xnun. Označme y = (y1, . . . , yn)T sloupec souřadnic vektoru (A0 − B0) v bázi v a M = (aij ) buď matice vyjadřující bázi u prostřednictvím báze v. Potom x1 = y1 + a11x1 + · · · + a1nxn ... xn = yn + an1x1 + · · · + annxn tj. maticově x = y + M · x.