Cvičení NMAI057 LA1 pro pokročilé, v středu 17:20

První cvičení začne až druhý týden v semestru, tedy 10. října. Pokud se vám nehodí časový termín, a přesto byste rádi chodili, napište mi (spolu s důvodem) a uvidíme, co se dá dělat.

Jedná se o výběrové cvičení pro náročné studenty, kteří se chtějí dozvědět víc. Nebaví-li vás počítání na běžných cvičeních a rádi byste se dozvěděli více zajímavého? Potom je toto cvičení určeno právě pro vás! V průběhu semestru se podrobněji seznámíme s lineární algebrou, ukážeme si řadu zajímavých úloh a naučíme se přemýšlet v pojmech lineární algebry. Také občas zabrousíme do aplikací lineární algebry, například v analýze, numerice, teorii grafů a řadě dalších oblastí. Můžete si prohlédnout letáček a prezentaci z přednášky.

Pro získání zápočtu je nutné získat 100 bodů. Body je možné získávat za aktivitu (pokud například ukážete nějaký příklad u tabule nebo budete aktivně řešit) a za řešení domácích úkolu (to budou jak běžné početní příklady, tak i zajímavější problémy. Pokud vás baví přemýšlení, získání zápočtu by neměl být žádný problém. Pro získání zápočtu je nutné (alespoň) občas na cvičení přijít, ostatně jinak by chození na pokročilé cvičení postrádalo smysl.

Konzultační hodiny nevypisuji, ale lze si je domluvit po mailu. Ideální doba je například na konci cvičení.

Postupně vznikají skripta Povídání o lineární algebře, více informací ZDE.

Domácí úkoly

Úkoly jsou zadávány po sériích, odevzdávat je můžete kdykoliv (ale doporučuji spíše s předstihem).

• První série: PDF a PS.
• Druhá série: PDF a PS.

Co jsme dělali na cvičeních

• 10.10.2012 - proč jsou pro matematiky tolik zajímavé rovnice; jak funguje Gaussova eliminace; odčítací úprava a dosazovací úprava vygeneruje přesně stejné koeficienty, ale odčítání se jednodušeji provádí; soustava s maticí A, kde (A)_ij = min(i,j) a libovolnou pravou stranou; soustava s maticí, která má na diagonále číslo a, mimo diagonálu číslo b (sečtením všech řádek); jak vypadají pivoti tridiagonální matice, která má na diagonále 2 a vedle diagonály proužek -1; jak najít neznámý polynom stupně n, pokud známe n+1 bodů, kterými prochází; Gaussova eliminace potřebuje zhruba n³/3 kroků, a ani hodně nulových koeficientů výrazně nepomůže.
• 17.10.2012 - pivoti tridiagonální matice jsou zlomky (i+1)/i, což jsme dokázali indukcí; o vektorech, jejich operacích, co je to vektorový prostor a rozdíl mezi konkrétní a abstraktní definicí; důkaz, že sčítání vektorů je komutativní (hlavní je uvědomit si, že dva vektory jsou stejné, pokud se shodují ve všech složkách); řádková geometrická interpretace soustavy - řešení jednoho řádku je nadrovina a množina řešení je průnik nadrovin; vektorové podprostory jsou hezké podmnožiny vektorového prostoru uzavřené na sčítání; vždy obsahují nulu a jsou to například v R³ počátek, přímky procházející počátkem, roviny procházející počátkem a celý prostor; průnik podprostorů je podprostor a naopak lineární obal množiny M je nejmenší podprostor obsahující množinu M (a definuje se jako průnik všech podprostorů obsahujících M); pokud podprostory uspořádáme inkluzí, tvoří svaz, kde infimum je průnik a supremum je lineární obal; řešení soustavy Ax=0 tvoří vektorový podprostor, kterému se říká kernel A; afinní podprostory jsou vektorové podprostory posunuté o vektor z počátku: W+p; jako p můžeme zvolit libovolný vektor z afinního podprostoru, vektorový podprostor W je jednoznačně určen; pokud uvažujeme i prázdné afinní podprostory, potom množina všech řešení Ax=b tvoří afinní podprostor W+p, kde W je kernel A a p je libovolné řešení Ap=b. Můžete si toto přečíst v druhé kapitole Povídání o lineární algebře.
• 24.10.2012 - úvod do matic; matice jsou tabulky čísel m x n, které umíme sčítat a násobit; násobení funguje jako skládání geometrických zobrazení; soustavu lineárních rovnic lze zapsat v řeči matic jako Ax = b; násobení matic obecně nekomutuje a úloha, které matice komutují se vším (zbývá dokončit); jak funguje násobení diagonální maticí a maticí samých jedniček; výpočet Fibonacciho čísel pomocí násobení matic.
• 30.10.2012 - třídy horních trojúhelníkových matic, dolních trojúhelníkových matic a diagonálních matic jsou uzavřené na součty, součiny a inverze; inverze levé a pravé a kdy existují obecně i pro obdélníkové matice; inverze jako řešení soustavy AX=I_n, kde konstruujeme X po sloupeččích tak, že Ax_k = e_k; matice A má pravou inverzi právě tehdy, když soustava Ax=b má řešení pro každou pravou stranu b, což platí právě tehdy, když matice nemá v odstupňovaném tvaru nulový řádek; pokud má matice víc řádku než sloupců, nemá pravou inverzi; levá inverze A existuje právě tehdy, když existuje pravá inverze matice A^T; pouze čtvercová matice může mít inverzi z obou stran; pokud má matice inverzi z levé strany a inverzi z pravé strany, je inverze jednoznačně určená a je z obou stran stejná; fundamentální věta lineární algebry říká, že pokud má čtvercová matice inverzi z jedné strany, potom má také inverzi z pravé strany, důkaz pomocí LU dekompozice; LU dekompozice je rozklad PA=LU, kde P je permutační matice, L je dolní trojúhelníková a U je horní trojúhelníková; lze ji získat aplikováním Gaussovy eliminace, U je výsledný odstupňovaný tvar, P je prohození řádků na začátku a L je součin dolních trojúhelníkových matic elemtárních úprav (přesněji jejich inverzí); více informací v kapitole 3 Povídání o LA.
• 7.11.2012 - maličký úvod do differenciálních rovnic, že to jsou vlastně lineární rovnice nad prostorem funkcí, kde derivace je lineární operátor; numerická metoda konečné mřížky pro řešení differenciálních rovnic a pár ukázek, jak se používá; pouze zmíněny metody konečných differencí a konečných prvků, budeme se věnovat někdy později; výpočet inverzí pro pár konkrétních matic; Hilbertova matice n x n má velké hodnoty v inverzní matici (oproti hodnotám v matici samotné), protože řádky matice ukazují skoro stejným směrem, velice špatné pro výpočty; matice, co má na diagonále jedničky a nad diagonálou proužek s hodnotou a, kde a je parametr; antisymetrická matice (platí A^T = -A) s -1 pod diagonálou a +1 nad diagonálou má pro sudé velikosti antisymetrickou inverzi s "šachovnicovým vzorem" +1 a -1;
• 14.11.2012 - povídali jsme si o lineárních kombinacích, nezávislosti a bazích; jako motivace pro lineární kombinace je konkrétnější popis vektorových podprostorů - zjevně množina všech lineárních kombinací tvoří vektorový podprostor a naopak každý vektorový podprostor lze zapsat jako množinu lineárních kombinací (možná hodně velké množiny vektorů); rádi bychom minimalizovali počet vektorů v lineární kombinaci, tedy aby žádný nebyl nadbytečný, což vede na požadavek lineární nezavislosti; množina, jejíž lineární obal je celý vektorový prostor, se nazývá generátor; lineárně nezavíslí generátor se nazývá báze a zavadí systém souřadnic nad vektorovým prostorem; důkaz, že libovolné dvě báze jsou stejně velké, pomocí Steinitzovy věty o výměně - této velikosti se říká dimenze prostoru.
• 20.11.2012 - cvičil Dušan Knop; blokové a operace s nimi fungují podobně jako operace na normálních maticích; mocnění blokově diagonální matice jenom umocňuje bloky (nezávisle na ostatních blocích); jak vypadá inverze blokové matice 2x2.
• 28.11.2012 - cvičil Jarda Horáček; o zaokrouhlovacích chybách a počítání v počítačích; reálný příklad selhání protiraketové obrany v Saúdské Arábii (1991) způsobený floating-point aritmetikou; další příklad, Gaussova eliminace na systému 2x2; jaké chyby vznikají při počítáním a jak to řeší různé přístupy; definice intervalové aritmetiky a které vlastnosti tělesa pro ni platí a které naopak ne; co to znamená NP-těžkost; jak vypadá vizuálně řešení intervalové lineární soustavy a že najít "ideální" řešení je NP-těžké a co chceme tedy najít místo toho; jak řešit takovou lineární soustavu s intervalovými koeficienty; Gaussova eliminace v intervalově aritmetice, která moc dobře nefunguje; co to je předpodmínění a proč se to dělá aby to fungovalo líp; jak spočítat něco, co obaluje intervalovou inverzní matici k nějaké intervalové matici - intervalová G-J eliminace.
• 5.12.2012 - lineární algebra z pohledu algebraického jako studium vektorových prostorů a lineárních zobrazení mezi těmito prostory; lineární zobrazení jsou zobrazení hezkých vlastnosti, protože zachovávají strukturu vektorového prostoru, chovají se pěkně vůči vektorovým operacím; lineární obraz nuly je nula a lineární obraz lineární kombinace je lineární kombinace obrazů; proto pokud víme, jak vypadá obraz nějaké báze, víme o lineárním zobrazení úplně všechno; obraz každého vektoru lze zapsat pomocí souřadnic vůči bázi v cílovém prostoru; pokud zapíšeme souřadnice obrazů báze po sloupečcích, dostáváme hezkou číselnou reprezentaci lineárního zobrazení, která se nazývá matice; násobení matice krát vektor odpovídá aplikování lineárního zobrazení na tento vektor; pokud chceme pro vektor b v cílovém prostoru najít všechny jeho vzory x, musíme vyřešit soustavu Ax=b; násobení matic odpovídá skládání lineárních zobrazení; inverzní matice odpovídá inverznímu lineárnímu zobrazení (a to nemusí nutně existovat); čtvercové matice lze interpretovat jako lineární zobrazení na stejném prostoru a většinou se uvažuje vůči jedné konkrétní bázi; příklady lineárních zobrazení z geometrie (rotace, projekce na přímku), derivace a integrál na polynomech (i obecně) jsou lineární zobrazení a že derivace je levá inverze integrálu; proč je vůbec užitečné studovat jiné báze než bázi kanonickou: můžeme nalézt souřadné systémy i uvnitř podprostorů a hlavně můžeme nalézt pro dané lineární zobrazení co nejhezčí bázi, která zobrazení co nejvíc zjednoduší (to bude jedno z hlavních témat letního semestru, pro co se vybuduje teorie vlastních čísel).
• 12.12.2012 - hodnost (rank) matice / lineárního zobrazení se definuje jako dimenze image (sloupcového prostoru), množina všech obrazů (a taky všech b, pro které má soustava Ax=b řešení); hodnost matice udává, kolik informace je ztraceno, pokud aplikujeme na vektorový prostor dané lineární zobrazení, čím větší hodnost, tím méně informace je ztraceno; pro libovolnou matici platí, že hodnost A je mezi 0 a n, kde n je dimenze cílového prostoru; pro libovolný podprostor W má jeho obraz f(W) nejvýše takovou dimenzi jako W (lineárně závislé věci se po zobrazení nemohou stát lineárně nezávislé); čtvercová matice je regulární, pokud má plnou hodnost n, a to je právě tehdy, když je invertovatelná (už dřív jsme vlastně zmínili, že čtvercové matice mají jako image celý prostor); pro součin matic platí, že hodnost AB je menší či rovna minimu z hodností A a B; násobení regulární maticí zleva i zprava nemění hodnost, protože se dají změny invertovat (tedy kdyby hodnost klesla, musela by po vynásobení inverzí vzrůst, což není možné); aplikace v kombinatorice, v Lichoměstě jsou podmínky pro kluby, že každý klub má lichý počet členů a počet společných členů pro libovolné dva kluby je sudý, maximální počet klubů je n, kde n je počet obyvatel Lichoměsta; matice hodnosti jedna je rovna součinu dvou vektoru uv^T; matici hodnosti k lze zapsat jako součet k matic hodnosti jedna (vyplývá z odstupňovaného tvaru matice, který takto zapsat jde); čtyři fundamentální podprostory definované maticí jsou řádkový prostor a kernel (ve vzorovém prostoru) a image/sloupcový prostor a levý kernel pro matici transponovanou (v cílovém prostoru); platí, že dimenze řádkového prostoru a image je stejná (i když to jsou zcela jiné podprostory žijící v různých prostorech); součet dimenzí kernelu a řádkového prostoru je m, součet dimenzí image a levého kernelu je n; obrázek akce matice na vektory vzhledem k řádkovému prostoru a kernelu, kde je zobrazení mezi řádkovým prostorem a image je bijekce (jinak by měl řádkový prostor netriviální průnik s kernelem, což není pravda v případě tělesa reálných čísel; aplikace fundamentálních podprostorů v teorii grafů na matici incidence, podprostory mají grafovou interpretaci a například z nich vyplývá Eulerova věta pro rovinné grafy.
• 19.12.2012 - cvičení zrušeno, klidně si nahradíme někdy ve zkouškovém.
• 2.1.2013 - úvod do algebraické teorie grup. Jaké jsou axiomy grupy a jaké vlastnosti z nich vyplývají (jednoznačnost neutrálního prvku a inverzí, v rovnostech lze zprava i zleva krátit); levé a pravé translace jsou bijektivní zobrazení, které permutují grupu; motivace grupy ve studiu symetrií geometrických objektů, akce grupy na množině; příklady grup: Z_n (grupa celých čísel modulo n), S_n (symetrická grupa všech permutací), D_n (dihedrální grupa symetrii pravidelného n-úhelníka); jak vypadá grupa všech symetrií čtyřstěnu a jak velká je grupa všech symetrií krychle (bez ukázání její struktury); grupy automorfismů grafů a ukázka existence asymetrického grafu s triviální jednoprvkovou grupou symetrií; rozkladové třídy (cosety) grup jsou posunuté kopie dané podgrupy, a proč z toho vyplývá, že řád podgrupy dělí řád grupy; dvě možnosti, jak vyrobit z jedné grupy menší grupu: uvážit její podgrupu nebo velkou grupu vyfaktorizovat.
• 9.1.2013 - dokončení grup z minula a algebraická tělesa; zabývali jsme se faktorizacemi nad grupami (podle rozkladových tříd) nebo obecně algebrami (podle tříd ekivalence); myšlenka je vyrobit z každé třídy jeden prvek malého objektu, a pro zadefinování operací použijeme libovolné reprezentanty; pokud faktorizujeme grupu podle normální podgrupy, potom je výsledek dobře definovaný a výsledný faktorobjekt je grupa; ukázka, že Petersenův graf lze vyfaktorizovat podle podgrupy Z₅ na dvouvrcholový graf se třemi hranami (a naopak z něj lze Petersenův graf inverzním procesem vyrobit); definice tělesa a nějaké další důsledky, co vyplývají z axiomů (0*a = 0, 0 je rozdílná od 1, (-1)*a = (-a), další vlastnosti se přenesou z grup); distributivita je veledůležitá vlastnost, protože pouze ona spojuje sčítání a násobení, bez ní těleso zcela ztratí svoji strukturu; odbočka: snaha o řešení diophantických rovnic vedli v minulosti k objevení grup a faktorizací, ve snaze si problémy zjednodušit, dnes už víme, že diophantické rovnice jsou obecně algoritmicky neřešitelné; příklady těles Q, R, C, konečná tělesa Z_p pouze pro prvočíselný řád; zmíněna věta, že konečné těleso lze zkonstruovat právě pro řád mocnina prvočísla a takové těleso je pak jednoznačně určené (důkaz jedné půlky bude za domací ukol v LS); ukázka konstrukce tělesa GF(4) řádu čtyři.
• 14.1.2013 - bonusové cviko o vztahu lineární algebry a analýzy; konstrukce afinních zobrazení z lineárních zobrazení vnořením prostoru jako afinního podprostoru v prostoru vyšší dimenze; differenciální rovnice není nic jiného než soustava lineárních rovnic Ax=b, které dobře známe z lineární algebry, pouze nad prostorem funkcí nekonečné dimenze; z toho plyne, že množina všech řešení tvoří afinní podprostor, co je vlastně posunutý kernel jedním libovolným řešením; můžeme řesit s homogenní pravou stranou nula, nalézt kernel a pak si zkusit tipnout jedno správné řešení; alternativní vysvětlení, proč platí n - dim(Ker) = dim(Im), přes faktorizaci podle afinních podprostorů tvořených posunutím kernelu; zhruba naznačena Fourierova transformace a proč se tak často používá ve funkcionální analýze při řešení differenciálních rovnic; Fourierova motivace, kdy bylo známe, jak vyřešit daný typ rovnic se speciální pravou stranou, a Fourier přišel, jak libovolné řešení nasčítat z těchto speciálních řešení; stručný úvod do vlastních čísel, pro jejichž studium máme dvě motivace: chceme zjistit budoucnost lineárních systémů a chceme nalézt bázi, pro kterou bude zobrazení co nejjednodušší; maticová podobnost vyjadřuje, že dvě zobrazení jsou stejná, jenom je uvažujeme vůči různým bazím; pokud by počáteční stav systému byl vlastní vektor, je budoucnost systému hrozně jednoduchá; pokud máme bázi z vlastních vektorů, potom můžeme libovolný vektor napsat jako lineární kombinaci vlastních vektorů, proto známe vývoj systému pro každý vektor; to odpovídá tomu, že po přechodu k bázi vlastních vektorů dostaneme diagonální matici, která je velice jednoduchá.