Cvičení NMAI058 LA2 pro pokročilé, v úterý 17:20 v S11

Cvičení vedu spolu s Petrem Zemanem. 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 ze zimního semestru.

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é příklady, tak i zajímavější problémy, tady je ukázka z minulého semestru). 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

• 18.2.2014 - opakovaní zimní lingebry; zavedení standardní normy a standardního skalárního součinu; souvislost s klasickou geometrií (úhly, délky); ortogonalita a ortogonální doplňky; fundamentální podprostory jsou ortogonální doplňky; ortogonální vektory jsou lineárně nezávislé; kolmá projekce na přímku je určena skalárním součinem; Cauchy-Schwartzova věta se dokazuje tak, že délka rozdílu vektoru a jeho kolmé projekce je nezáporná.
• 25.2.2014 - kolmá projekce na obecný podprostor; odvození přes normální rovnici a souvislost s metodou nejmenších čtverců; matice kolmé projekce splňuje dvě podmínky: P² = P a P^T = P; matice pseudoinverze jako nejlepší možné inverze singulární matice; Gram-Schmidtův ortogonalizační proces a kolmá projekce na podprostor určený ortogonální bází se provádí po složkách; QR rozklad matice jako maticový zápis Gram-Schmidtovy ortogonalizace.
• 4.3.2014 - více o maticovém zápisu Gram-Schmidta; ortogonální matice obecně a proč jsou zajímavé; QR rozklad pomocí Givensových rotací; obecný skalární součin jako standardním vůči jiné bázi; skalární součin indukuje normu, ale norma neindukuje skalární součin, tedy norem je podstatně víc; geometrické znázornění norem, kde ty přes skalární součin jsou elipsoidy a obecné normy jsou pouze symetrické a konvexní.
• 11.3.2014 - definice determinantu formulkou; odvození základních vlastností determinantu - prohození řádku mění znaménko, přičtení řádku nemění determinant, vynásobení řádku vynásobí determinant; determinant trojúhelníkové matice je součin prvků na diagonále a obecně lze determinant tedy spočítat eliminací; determinant transponované matice je stejný, a tedy všechny vlastnosti platí i pro sloupce; matice má nenulový determinant právě když je regulární; bloková diagonální matice má determinant roven součinu determinantů diagonálních bloků; součin matic má determinant roven součinu determinantů a důkaz přes úpravu blokové matice 2nx2n; alternativní zavedení determinantu jako multilineární alternující formy, důkaz jako úloha 9.
• 18.3.2014 - geometrická interpretace determinantu jako změna objemu při lineární transformaci; ukázka toho, že jednotlivé vlastnosti determinantu dávají smysl pro objemy; aplikace objemů při substituci ve vícerozměrném integrálu (na příkladu); Laplaceův řádkový a sloupcový rozvoj determinantu; Adjungované matice a jejich vztah s inverzní maticí; Cramerovo pravidlo, jeho geometrická interpretace a odvození (lze udělat z adjungované matice, neboť to je inverze); aplikace Cramerova pravidla na LP na důkaz, že problém leží v NP.
• 25.3.2014 - úvod do vlastních čísel, motivace přes systémy lineárních diferenciálních rovnic na konkrétním příkladu spojitých toků; odvození výpočtu vlastních čísel přes determinant, jako kořenů charakteristického polynomu; základní maticové operace a jejich vliv na vlastní čísla; přičtení na diagonálu posouvá vlastní čísla; geometrické příklady a jejich vlastní vektory a čísla.
• 1.4.2014 - opakování předchozí hodiny; vektory patřící k různým vlastním číslům jsou lineárně nezávislé; Gershgorinova věta a její zobecnění na komponenty disků; vlastní čísla speciálních matic: úplný bipartitní graf, matice samých jedniček, úplný graf.
• 8.4.2014 - numerické problémy při řešení soustav lineárních rovnic a rozdíl mezi přímými a iteračními metodami; Wilkinsonův iterativní refinment jako algoritmus na řešení soustav ve vysoké přesnosti, kdy se většina výpočtů provádí v nízké přesnosti; aproximační iterativní refinment, kdy se řeší uvnitř aproximativní soustava a příklady pro covarianční matice; souvislost s klasickými stacionárními/štěpícími metodami; analýza konvergence těchto metod: 1) když konvergují, konvergují ke správnému řešení, 2) konvergence a její rychlost závisí na vlastních vektorech a vlastních číslech matice S^-1T; problém mocnění vektorů maticí a jeho analýza; pokud mám bázi z vlastních vektorů, tak typicky zaleží pouze na největším vlastním čísle, což se nazývá spektrální radius matice; každá striktně diagonálně dominantní matice je regulární podle Gershgorinovy věty; důkaz, že Jacobiho metoda konverguje pro striktně diagonálně dominantní matice.
• 15.4.2014 - základní třídy matic a kolik nám o nich prozradí znalost vlastních čísel: symetrické (či Hermitovské), normální a nenormální; pro symetrickou matici jsou všechna vlastní čísla reálná, tedy chovají se jednoduše geometricky; matice je normální, pokud komutuje se svojí transpozicí; normální matice (a tedy i symetrické) jsou přesně ty, které mají spektrální rozklad, což je ortogonální báze z vlastních vektorů; tedy znalost vlastních čísel poví o matici prakticky všechno (až na pootočení os vlastních vektorů); naproti tomu nenormální matice nemusí ani mít bázi z vlastních vektorů, a i když mají, mohou mít velice malé úhly; tedy nenormální matice se mohou chovat velice složitě a vlastní čísla o nich nedávají dostatečnou informaci, existují jiné metody (pseudospektrum, numerický rozsah); Schurův rozklad existuje vždycky a lze ho efektivně spočítat; pro normální matice je Schurův rozklad roven spektrálnímu rozkladu.
• 22.4.2014 - Jordanova normální forma existuje pro libovolnou matici a převádí ji do skoro diagonální podoby; oproti Schurovu rozkladu je nespojitá v koeficientech matice, a tedy nelze numericky určit; důkaz indukcí přes zkoumání obrazu a jádra singulární matice; Fourierova řada/transformace přes analýznický klasický pohled a přes pohled algebraický jako způsob na řešení Ax=b ze znalosti vlastních vektorů; funkce sinus a cosinus tvoří ortogonální bázi z vlastních vektorů operátoru derivace; Fourierova původní motivace pro řešení diferenciálních rovnic a ukázka na modelu pružiny s působením vnější síly; řešení Basilejského problému, že součet 1/n² je roven pi²/6, pomocí Fourierovy řady jednoduché funkce a nekonečně dimenzionální Pythagorovy věty.
• 29.4.2014 - motivace pro kvadratické formy a pozitivní definitnost matic, přes hledání extrémů funkcí více proměnných; aproximujeme funkci lokálně pomocí Taylorova polynomu a řešíme chování kvadratických členů určených druhými parciálními derivacemi; pět ekvivalentních definic pozitivní definitnosti a různé důkazy vztahů mezi nimi; věta o proplétání vlastních čísel pro podmatice symetrických matic (důkaz příště); Choleského rozklad a různé pohledy na něj; motivace pro Choleského rozklad z numerické lineární algebry, jeho výhody oproti obecné LU dekompozici.
• 6.5.2014 - geometrické interpretace symetrických matic; pozitivně semidefinitní matice geometricky tvoří nekonečný kužel, definitní by tvořili to samé bez hranice; množina řešení x^TAx = 1 tvoří pro pozitivně definitní matici elipsoid, jehož osy jsou vlastní vektory a délky v osách jsou převrácené hodnoty odmocnin z vlastních čísel; jak vypadají stejné kvadratické formy uvažované vůči různým bázím, aneb obdoba podobnosti mezi A a X^TAX; Sylvestrova věta o setrvačnosti, která říká, že pro libovolnou kvadratickou formu existuje báze, která ji diagonalizuje a na diagonále se objevují pouze +1, -1 a 0; stejná kvadratická forma vůči různým bázím má stejná znaménka vlastních čísel, i když hodnoty se mohou lišit (topologický důkaz); diskuze o varietě singulárních matic; algoritmus bisekce na výpočet vlastních čísel symetrických matic, inverzní mocninná metoda ve zkratce, ortogonální redukce do Hessenbergova tvaru (tridiagonální pro symetrické matice), který nemění vlastní čísla.