Přednáška NMAI072 LA3 v pondělí od 17:20 v S10

Navazující přednáška k LA1 a LA2, zaměřená na složitější výsledky a pokročilé aplikace lineární algebry. V sylabu jsem před časem navrhl následující témata: Perron-Frobeniova věta a aplikace pro stochastické procesy; singulární dekompozice a její aplikace; iterativní algoritmy pro řešení soustav a výpočet vlastních čísel; tenzory a jejich aplikace; Rayleigho kvocienty a metoda konečných prvků; číslo podmíněnosti a úvod do numerické lineární algebry. Tohle jsou však pouze rámcově možné okruhy, kolem kterých se na přednášce budeme motat, co všechno probereme se uvidí podle situace.

Zkouška bude z předmětu sestávat předběžně ze tří částí. První část jsou základní znalosti z probraných témat; bude stačit, když si to třeba jednou přečtete, hlavně o tom přemýšlejte. Druhá část bude jedno vámi vybrané téma, které si podrobněji nastudujete; člověk by se hlavně měl učit, co ho baví a zajímá. Pro třetí část si vyberete nějaký článeček či text z knihy ze seznamu, nastudujete a vysvětlíte mi to, co se tam píše; alespoň si na tom vyzkoušíte prezentovaní a ty myšlenky lépe pochopíte, když je musíte někomu vysvětlit. Cílem té zkoušky je, abyste si z ní něco odnesli, ne aby vám příprava sežrala spoustu času. Budu se tedy hlavně snažit zjistit, čemu rozumíte, a případně si osvětlíme to, čemu nerozumíte.

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

Všechny přednášky v jednom souboru: PDF a PDF s okrajem.

Témata ke zkoušce

Z následujících témat, kterým jsme se na přednášce věnovali, si vyberte jedno podle vašeho zájmu a nastudujte si ho podrobněji.

• Soustavy a diskretizace differenciálních rovnic.
• Vlastní čísla a jejich zavedení bez determinantů.
• Úvod do numeriky a číslo podmíněnosti matice.
• Ortogonální matice a QR dekompozice.
• SVD dekompozice a její aplikace.
• Mocninná metoda a QR metoda pro výpočet vlastních čísel obecných matic.
• Iterativní metody pro soustavy a vlastní čísla.

Články ke zkoušce

Z následujícího seznamu si můžete zarezervovat články/texty ke zkoušce. Pokud samozřejmě chcete povídat něco jiného, pošlete mi mail a můžeme se domluvit. Budu ho postupně rozšiřovat, až objevím další texty.

• A. Axler: Down with Determinants [link] - text, který jsem využil při třetí přednášce k vybudování teorie vlastních čísel bez determinantů. Dostudovat zbývající důkazy a podrobněji vlastnosti determinantů, které jsme z časových důvodů vynechali.
• J. Demmel: Applied Numerical Linear Algebra - moc hezky napsaná kniha, kterou jsem převážně využíval při přípravě přednášky. Pochopitelně jsme se u většiny témat dotkli jednotlivých témat pouze trochu, a v knize je o nich podstatně více. Jako možná témata se nabízí z kapitoly 2 odhad zaokrouhlovacích chyb při Gaussovce, bloková implementace eliminace nebo speciální druhy matic, z kapitoly 3 metoda nejmenších čtverců, z kapitoly 4 odhad zaokrouhlovacích chyb pro vlastní čísla, z kapitoly 5 a dál algoritmické metody. Pochopitelně ke zkoušce by stačilo přečíst a vysvětlit jenom menší část. Text lze například zapůjčit v knihovně nebo sehnat na ruském serveru Library Genesis.
• J. Shlens: A Tutorial on Principal Component Analysis [PDF] - tématu PCA jsme dotkli pouze zhruba, když jsme probírali SVD. Jedná se o klíčovou statistickou metodu s řadou aplikací, ve které hledáme podprostor malé dimenze obsahující principiální komponenty daných dat. Tento text je příjemný úvod do statistiky, problematiky PCA a jak souvisí s SVD.
• L. He, X. Liu, G. Strang: Laplacean Eigenvalues of Growing Trees [PDF] - článek zabývající se Laplaceovými matice speciálních stromů, kde se distribuce vlastních čísel blíží Cantorově schodové funkci. Zde je distribuce úplně jiná než pro vlastní čísla nekonečného k-nárního stromu. Článek může být trochu technický, ale spíše jde o pochopení myšlenky rekurzivního výpočtu.
• G. Strang, T. Nguyen: The Interplay of Ranks of Submatrices [PDF] - pokud je pásová matice invertovatelná, její inverze nemusí být pásová. Tento článek však ukazuje, že inverze má relativně jednoduchou strukturu, protože například pro tridiagonální matici je to funkce 3n-2 hodnot a ne n² hodnot. Článek ukazuje dva důkazy tohoto tvrzení a také možné aplikace na maticové násobení a soustavy diferenciálních rovnic.

Co jsme probírali

• 7.10.2013 - úvodní přednáška, zaměřená na opakování LA1. Lineární zobrazení jako základní pojem lineární algebry, a matice jako reprezentace lineárního zobrazení vůči bázím. Tedy matice není pouze tabulka čísel, ale popisuje nějaký proces. Fundamentální podprostory definované matici a obrázek zobrazující akci lineární transformace vůči ním. S tím související problémy najití pseudoinverze a co nejmenší úpravy pravé strany, aby soustava měla řešení (metoda nejmenších čtverců). Zápisky: PDF (chybí úplný konec, přihodím na začátek příště).
• 14.10.2013 - Laplacova matice grafu jako diskretizace Laplaceova operátoru, motivace pro studium vlastních čísel a vlastních vektorů jako nejkrásnějších bází pro dané lineární zobrazení; aplikace vlastních čísel pro náhodné procházky a Markovské řetězce. Zápisky: PDF.
• 21.10.2013 - vybudování vlastních čísel a vlastních vektorů bez determinantů, podle textu Down with Determinants; Gershgorinova věta o discích; různé rozklady pomocí vlastních čísel. Zápisky: PDF.
• 28.10.2013 - svátek, přednáška se nekonala.
• 4.11.2013 - dva světa lineární algebry: ten přesný a ten numerický se zaokrouhlováním; úvod do světa numeriky; schéma typického problému z reálného světa až po jeho numerické řešení; Wilkinsonův iterativní refinement a vztah residua jako chyby ve zkoušce a chyby samotné; číslo podmíněnosti matice a jeho odvození; maticové normy a geometrie matic; převrácená hodnota čísla podmíněnosti je vzdálenost od variety singulárních matic. Zápisky: PDF.
• 11.11.2013 - dokončení důkazu, že vzdálenost od nejbližší singulární matice je převrácená hodnota čísla podmíněnosti; přehled slavných dekompozic lineární algebry; proč jsou ortogonální matice tak skvělé; QR dekompozice vybudovaná přes Gram-Schmidtovu ortogonalizaci a proč to není dobrý nápad; numericky se spíše QR počítá jinak, pomocí Householderových reflexí nebo Givensových rotací. Zápisky: PDF.
• 18.11.2013 - přednášel Milan Hladík; verifikace pro lineární a nelineární soustavy rovnic - nalezeni boxu kolem numericky přibližně spočítaného řešení, který zaručeně obsahuje právě jediné řešení. Přitom jsme si připomenuli: Brouwerova věta o pevném bodě, základní výsledky Perron-Frobeniovy teorie nezáporných matic.
• 25.11.2013 - singulární dekompozice matice (SVD); motivace pomocí numerického ranku a zobecnění spektrálního rozkladu; dva důkazy existence SVD; základní vlastnosti a aplikace SVD. Zápisky: PDF.
• 2.12.2013 - úvod do toho, jak se počítají vlastní čísla pro matici, u které nemáme žádné specifické vlastnosti; mocninná metoda, inverzní mocninná metoda, ortogonální metoda a QR metoda, která všechno toto propojuje dohromady. Trochu podrobnější zápisky, než co se odpředneslo: PDF.
• 9.12.2013 - přednáška zrušena kvůli nemoci.
• 16.12.2013 - přednáška Zdeňka Strakoše o iterativních algoritmech; obecný náhled do problematiky iterativních algoritmů; algoritmy Arnoldiho a Lanczose na výpočet ortogonální báze Krylovova podprostoru; odvození metody konjugovaných gradientů přes ortogonalitu rezidua na Krylovovský podprostor. Zápisky: PDF.
• 6.1.2014 - video o výpočtu SVD rozkladu: youtube.com; přednáška o tom, jak lze využít specifických vlastností symetrických matic pro rychlejší výpočet vlastních čísel; metoda rozděl a panuj a metoda bisekce. Zápisky: PDF.