Cvičení NMAI058 LA2 pro pokročilé, v pondělí 17:20

Cvičení vedu spolu s Dušanem Knopem a Tomášem Vyškočilem. Pokud se vám nehodí časový termín a přesto byste rádi chodili, napište nám (spolu s důvodem) a uvidíme, co se dá dělat. První cvičení začne až třetí týden v semestru, tedy 5. března.

Jedná se o výběrové cvičení pro talentované studenty. 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 také občas zabrousíme do aplikací lineární algebry, například v analýze, numerice, teorii grafů a řadě dalších oblastí.

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. Samozřejmě docházka není nutná, ale můžeme ji jenom doporučit (jinak přijdete o spoustu zajímavých věcí a chození na pokročilé cvičení postrádá smysl).

Konzultační hodiny nevypisujeme, 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.

POZOR! - bonusové cviko bude ve středu 13.6 v posluchárně S11 od 15:40, délka podle chuti. Na programu bude víc o kvadratických formách a pozitivně definitních matic.

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

• 5.3.2012 - cvičil Dušan Knop; opakování zimního semestru (tělesa, vektorové prostory, lineární zobrazení); lineární zobrazení derivace a integrálu na prostoru polynomů; pokud pro čtvercové matice platí ABCD=I, potom také BCDA = CDAB = DABC = I; speciální soustavy se speciálními pravými stranami; rovnoběžné affinní podprostory definují vektorový prostor.
• 12.3.2012 - algebraický přístup k lineární algebře - studium homomorfismů mezi vektorovými prostory; lineární zobrazení je jednoznačně určené obrazem báze, jednotlivé obrazy zapíšeme do tabulky po sloupečcích a dostaneme maticový zápis; násobení matice krát vektor zobrazuje vektor, soustava lineárních rovnic odpovídá hledání vzorů b, násobení matic odpovídá skládání zobrazení, inverzní matice odpovídá inverznímu lineárnímu zobrazení, detaily naleznete v prezentaci Procházka světem vektorových prostorů; které čtvercové matice X komutují se vším, tedy XA = AX pro každou matici A; LU dekompozice matice PA = LU, souvislost s Gaussovou eliminací, jednoznačnost dekompozice, jako aplikace Choleského dekompozice, později uvidíme více použití; uzavřenost trojúhelníkových matic na součiny a inverze.
• 19.3.2012 - definice skalárního součinu a normy (obecná i standardní); obecné skalární součiny odpovídají symetrickým pozitivně definitním maticím; jak ze skalárního součinu odvodit normu a že to jde i naopak, pokud norma splňuje rovnoběžníkový princip (bez důkazu, bude jako úkol); na co se hodí nestandardní skalární součin v numerické metodě konjugovaných gradientů na řešení Ax=b pro SPD matici A; dva vektory jsou ortogonální (kolmé), když jejich skalární součin je nulový; nechť vektory v₁ až v_k jsou nenulové a navzájem ortogonální, potom jsou lineárně nezávislé.
• 26.3.2012 - ortogonalita (kolmost) vektorů a její vlastnosti; dva vektory jsou ortogonální právě pokud jejich skalární součin je nula - geometrický důkaz pomocí Pythagorovy věty; kolmost podprostorů a ortogonální doplněk; ortogonální doplněk doplňku je původní prostor (zatím důkaz nedokončen); fundamentální podprostory matice (řádkový, sloupcový, kernel, kernel transpozice) jsou po dvojicích ortogonální doplňky; obrázek akce matice s projekcemi, matice zobrazuje řádkový prostor bijektivně na sloupcový (a proto mají stejný rank), navíc bijekce umožňuje zavést pseudoinverzi matice A⁺; fundamentální podprostory matice incidence grafu, jejich kombinatorický význam a proč implikují Eulerovu větu (n + f = m + 2 pro každý souvislý rovinný graf).
• 2.4.2012 - proč jsou ortogonální vektory výhodné a jak je vyrobit; matice ortogonálních projekcí; projekce na přímku je určená skalárním součinem; Cauchy-Schwarzova věta a její důkaz (neboť délka projekce je nezáporná); projekce na podprostor pomocí normální rovnice A^TAx = A^Tb; matice P je ortogonální projekce, právě když splňuje P² = P (to platí pro každou projekci) a P^T = P (dává ortogonalitu); metoda nejmenších čtverců aneb hledáme nejbližší pravou stranu k b, pro kterou ma rovnice Ax=b řešení; Gram-Schmidtova ortogonalizace a QR rozklad; naznačen vypočet vlastních čísel pomocí QR metody; PDFko s důkaz Cauchy-Schwarze a příkladem na Gram-Schmidta ZDE.
• 10.4.2012 - bonusová megahodina o Fourierově řadě a transformaci; aplikace v diferenciálních rovnicích a dalších oblastech; proč jsou ortogonální/ortonormální báze složené z vlastních vektorů ideální pro vyřešení soustavy Ax=b; diferenciální rovnice jako soustava lineárních rovnic v Hilbertových prostorech nekonečné dimenze a problémy spojené (konvergence, uniformní konvergence, spojitost, diferencovatelnost); numerické metody na řešení diferenciálních rovnic v kostce: metoda konečných diferencí, metoda konečné mřížky a metoda konečných prvků; Fourierova řada umožňuje vyjádřit periodické funkce vůči ortogonální bázi ze sinu a cosinu; tato báze odpovídá jiné bázi exponenciálních funkcí e^izx pro všechna z celá, tyto vektory jsou navíc vlastní vektory pro lineární operátor derivace, tedy diferenciální rovnice je snadné vyřešit, viz výše; jak nalézt snadno koeficienty Fourierovy řady pomocí ortogonálních projekcí; další dvě varianty Fourierových transformací (to je převod na koeficienty Fourierovské báze): spojitá verze a diskrétní verze; diskrétní verzi lze aplikovat v čase O(n log n), což má řadu aplikací: zpracovávání signálů, násobení velkých čísel a polynomů, ...; pár historických poznámek o Eulerovi a komplexních číslech; Baselský problém (podle Švýcarského města Basel) sečíst řadu 1/n² = pi²/6 pomocí Fourierova rozkladu funkce f(x) = x na (-pi,pi) a nekonečně dimenzionální Pythagorovy věty.
• 16.4.2012 - determinanty: vlastnosti a výpočet; čtyři různé definice determinantu (formule, vlastnosti jako multilineární alternující forma - bude úkol, změna objemů lineárním zobrazením, pomocí rekurzivní formule na rozvoj); determinanty jednodušších matic nxn; vlastnosti determinantů; aplikace determinantu v analýze při substituci ve vícerozměrném integrálu (jenom ukázka na příkladě, kdy chceme integrovat kruh).
• 23.4.2012 - vypočty determinantu pomocí rozvoje, rekuretní formule; adjungovaná matice funguje jako inverze (skoro); odvození Cramerova pravidla z adjungované matice; k čemu se hodí Cramerovo pravidlo - víme, že řešení je jenom polynomiálně velké vůči koeficientům matice, což je užitečné v teorii složitosti.
• 30.4.2012 - diskrétní a spojité lineární systémy (systémy určené diferenčními/diferenciálními lineárními rovnicemi); odvození rovnice pro vlastní čísla; vlastní čísla maticových mocnin a inverzní matice; vlastní čísla A+lambda*I jsou posunutá o k; vlastní vektory k vlastnímu číslu nula odpovídají kernelu matice, existují právě když matice má netriviální kernel, a tedy je singulární; tedy pomocí A-lambda*I můžeme testovat snadno, jestli je lambda vlastní číslo a tento test se provádí determinantem; z determinantu plyne, že každá matice má n vlastních čísel; naznačili jsme si, jak se dokáže, že každý polynom nenulového stupně má komplexní kořen; proč je tak užitečné mít bázi složenou z vlastních vektorů; jak odvodit formulku pro Fibonacciho čísla z matice lineárního systému; stabilita lineárního systému závisí na spektrálním radiusu (pokud je víc jak jedna, je systém nestabilní; pokud je méně, je stabilní; pokud je přesně jedna, je systém neutrálně stabilní); pokud máme vlastní vektory příslušející k po dvou různým vlastním číslům, jsou tyto vlastní vektory lineárně nezávislé.
• 7.5.2012 - protože dorazila disjunktní skupina studentů, dělali jsme přibližně to samé jako na hodině 30.4.
• 14.5.2012 - pokračování vlastních čísel; proč z charakteristického polynomu plyne, že součet vlastních čísel je stopa matice a součin vlastních čísel je determinant; podobnost matic aneb stejné lineární zobrazení vůči různé bázi; nejjednodušší forma matice - diagonální, pokud existuje báze z vlastních vektorů, z čehož dostáváme spektrální dekompozici matice; podobnost zachovává vlastní čísla a pouze transformuje vlastní vektory přechodem od jedné báze k druhé; hermitovská transpozice jako obdoba klasické transpozice, jenom pro jiný skalární součin; hermitovské (symetrické) matice mají všechna vlastní čísla reálná a mají ortogonální vlastní vektory; pro hermitovské matice je spektrální dekompozice SDS^-1 tvořená unitárními maticemi (obdoba matic ortogonálních nad C) a proto můžeme místo inverze použít hermitovskou transpozici UDU^*.
• 15.5.2012 - bonusová megahodina, která trvala skoro čtyři hodiny, děkuji dvěma odvážlivcům; Schurova dekompozice pomocí unitární matice A=UTU^*, tedy pro libovolné zobrazení existuje ortogonální báze, ve které je zobrazení trojúhelníkové (důkaz indukcí podle velikosti, s využitím vždy jednoho vlastního vektoru); pokud je A=A^*, potom T=T^* a speciálně Schurova dekompozice je diagonalizace; pokud matici S diagonalizuje A, potom jsou sloupce S tvořené vlastními vektory A; tedy hermitovské matice mají tři následující užitečné vlastnosti: 1) všechna vlastní čísla jsou reálná, 2) mají n lineárně nezávislých vlastních vektorů a 3) existuje ortonormální báze z vlastních vektorů; důkaz Gershgorinovy věty o kruzích, že všechna vlastní čísla leží v komplexní rovině ve sjednocení n kruhů, kde i-tý kruh má střed v a_i,i a poloměr součet absolutních hodnot a_i,j pro j rozdílné od i; pomocí Gershgorinovy věty víme, že všechna vlastní čísla matice sousednosti grafu leží v intervalu [-Delta,Delta] a Laplaceovy matice grafu leží v intervalu [0,2Delta], kde Delta značí maximální stupeň vrcholu; aplikace vlastních čísel na náhodné procházky v grafu, graf je tím lepší expandér, čím větší je rozdíl druhého a prvního největšího čísla (bráno v absolutní hodnotě); zmíněna věta o proplétání vlastních čísel pro hermitovské/symetrické matice; kvadratická forma x^TAx odpovídá kvadratickému polynomu v proměnných x₁ až x_n; kvadratická forma je v nule rovna nule a je pozitivně definitní, pokud je mimo nulu kladná; pět ekvivalentních definic pozitivní semidefinitnosti spolu s důkazem jejich ekvivalence; povídání o hledání extrémů hladkých/dostatečně diferencovatelných funkcí a souvislostí s Taylorovým polynomem (jak pro funkce jedné, tak pro funkce více proměnných); test na lokální minima pomocí kvadratické formy tvořené druhými derivacemi (tečná rovina musí být vodorovná, jinak není extrém, tečný paraboloid musí být pozitivně/negativně definitní, abychom dostali lokální minimum/maximum, indefinitnost znamená sedlový bod - není lokální extrém, v případě semidefinitnosti nevíme a musíme testovat derivace vyšších řádů.