Section outline

  • Úvodní informace

    Alle einklappen Alle aufklappen

  • Přednáška a cvičení 22.2.

    Téma hodiny: Úvodní informace, základní pojmy teorie citlivosti a stability

    • korektnost a citlivost úlohy
    • stabilita postupů (metod)
    • vliv FPA na výpočet
    • viz. též skripta str. 5 - 16

    Cvičení:

    • příklady úloh citlivých na změnu dat
    • příklady zvýšení stability jednoduchých metod
    • přečtěte si ve skriptech str. 7-10 - aritmetika s plovoucí řádovou čárkou

  • Přednáška a cvičení 29.2.

    Téma hodiny: Citlivost vlastních čísel - vzdálenosti spekter

    Cvičení MATLAB:

    • Experimenty s citlivostí vlastních čísel jednoduchých testovacích matic.
    • Vliv FPA na výpočet vlastních čísel.

  • Přednáška a cvičení 7.3.

    Téma hodiny: Odhad vzdálenosti spekter, Geršgorinova věta a její důsledky

    • Elsnerova věta a její varianty
    • Geršgorinova věta
    • odhad polohy vlastních čísel pomocí Geršgorinových kruhů a jejich zpřesnění
    • viz. též skripta str. 29 - 35, 41 - 43

    Cvičení:

    • příklady lokalizace vl. čísel matice a kořenů polynomu pomocí Geršgorinovi věty

  • Přednáška a cvičení 14.3.


    Téma hodiny: Citlivost jednoduchých vlastních čísel a vl. čísel diagonalizovatelných matic

    • pravé a levé vlastní vektory a jejich vlastnosti
    • věta o citlivosti jednoduchého vl. čísla
    • podmíněnost a diferencovatelnost jednoduchého vl. čísla
    • odhady vzdálenosti spekter pro diagonalizovatelné (a spec. normální) matice
    • viz. též skripta str. 43 - 50

    Cvičení MATLAB:

    • Pomocí přiložené funkce vykreslete Geršgorinovi kruhy pro vybrané testovací matice, studujte jejich vlastnosti.
    • Experimentujte s polohou Geršgorinových kruhů a Brauer-Cassiniho oválů na https://bwlewis.github.io/cassini/ a https://demonstrations.wolfram.com/GershgorinCircles/
    • Citlivost a podmíněnost vlastních čísel lze v MATLABu ilustrovat na perturbaci jednoduché nesymetrické 3x3 matice, jak je krok po kroku popsáno zde

             https://blogs.mathworks.com/cleve/2019/05/22/an-eigenvalue-sensitivity-example/#fab26436-14bf-43a8-8df3-00c9397c18fa

  • Přednáška a cvičení 21.3.

     Téma hodiny: Pseudospektrum a pole hodnot: definice, vlastnosti, výpočet

    Cvičení:

    • vlastnosti pseudospektra a pole hodnot
    • výpočet odchylky od normality

  • Přednáška a cvičení 28.3.

    Téma hodiny: Odhady chyb při výpočtu vlastních čísel

    • odhad zpětné chyby při výpočtu vl. čísel
    • odhad přímé chyby při výpočtu vl. čísel
    • vliv normality matice
    • viz. též skripta str. 66 - 68

    Cvičení MATLAB:

    1. Demos -> Dense matrices -> Random
    2. Demos -> Dense matrices -> Grcar
    3. Demos -> Dense matrices -> Frank
    4. Demos -> Dense matrices -> Davies
    5. File       -> New matrix       -> gallery('jordbloc',50,0)
    6. File       -> New matrix       -> wilkinson(50)
    • Naprogramujte v MATLABu algoritmus pro odhad pseudospektra matice vzorkovací metodou. Porovnejte výsledky Vašeho algoritmu s výsledky získanými v EIGTOOL.

  • Přednáška a cvičení 4.4.

    Téma hodiny: Citlivost řešení a odhady chyb pro soustavy lineárních algebraických rovnic

    • citlivost řešení soustav rovnic na perturbace modelu/pravé strany
    • odhad chyby při řešení soustav rovnic
    • viz. též skripta str. 61 - 65, 69-71

    Cvičení:

    • Matlab (řešení lin. soustavy citlivé na perturbace):
    • Vytvořte příkazem H = hilb(n) postupně Hilbertovi matice dimenze n= 1, ..., 20. Sledujte pomocí příkazu cond(), jak s parametrem n roste jejich číslo podmíněnosti (zkuste různé normy - F, 1, 2, inf, pro řídké matice lze podmíněnost odhadnou pomocí condest()).
    • Pro každou matici vytvořte pravou stranu b odpovídající přesnému řešení x složenému ze samých jedniček. Řešte soustavy rovnic Hx=b pomocí backslash operátoru a sledujte, jak s parametrem n roste relativní norma skutečné chyby řešení (tj. norma rozdílu mezi přesným a spočteným řešením dělená normou přesného řešení). Zároveň norma residua i odhad zpětné chyby zůstávají malé.
    • Opakujte experiment s dalšímy maticemi (A = randn(n), ... ).

  • Přednáška a cvičení 11.4.

    Téma hodiny: Mocninná metoda, podprostorové iterace

    • mocninná metoda - podmínky a rychlost konvergence
    • inverzní mocninná metoda
    • urychlení konvergence pomocí shiftů, Rayleighův podíl
    • zobecnění na podprostorové iterace - konvergence, implementace

    Cvičení MATLAB:

    • Stáhněte si přiloženou složku souborů pro MATLAB a prohlédněte si obsažené funkce.
    • V textovém dokumentu "shift_invert_experimenty" je připraven průvodce experimentováním s mocninnou metodou, inverzními iteracemi a volbou shiftů pro různé testovací matice.
    • Proveďte experimenty, sledujte chování metod.

  • Přednáška a cvičení 25.4.

    Téma hodiny: Úplný problém vl. čísel - simultánní iterace nad R^n

    • podprostorové iterace nad plnou bází R^n
    • vlastnosti metody, podmínky a rychlost konvergence
    • odvození základního QR algoritmu jako podprostorové iterace

    Cvičení MATLAB:

    • Naprogramujte základní verzi QR-algoritmu a spusťte ji na matici A=gallery(3). Sledujte chování prvků na pozici (3,2) a (3,3).
    • Uvažujte podobnostní transformaci matice A na horní Hessenbergův tvar H pomocí reflexí. Jaké jsou výpočetní náklady transformace? Jaké jsou výpočetní náklady QR algoritmu pro obecnou a horní Hessenbergovu matici?
    • Příkazem hess(A) převeďte A na horní Hessenbergův tvar H, spusťte QR-algoritmus na H. Porovnejte rychlost konvergence a chybu aproximace vl. čísel s/bez transformace A na H .

  • Přednáška a cvičení 2.5.

    Téma hodiny: Explicitní QR algoritmus - implementace,  urychlení konvergence

    • preprocesing transformací na horní Hessenbergův tvar
    • princip duality a urychlení konvergence pomocí shiftů
    • sekvenční redukce rozměru a deflace
    • specifika implementace pro reálné matice
    • Záznam: viz 2. polovina videa k předchozí přednášce

    Cvičení MATLAB:

    • Rozšiřte QR-algoritmus z předchozího cvičení o Reylighův shift a zastavovací kritérium.
    • Sledujte rychlost konvergence základního algoritmu, algoritmu s preprocesingem a algoritmu s shiftováním.
    • Rozšiřte QR-algoritmus o redukci dimenze a rekurzi.
    • Testujte na maticích s různým rozložením vl. čísel. Co se stane, pokud je A symetrická?

  • Přednáška a cvičení 9.5.

    Téma hodiny: Implicitní QR algoritmus (Francisův)

    • odvození implicitní varianty QR algoritmu
    • výhody - násobné shiftování, stabilita
    • důkaz ekvivalence implicitního a explicitního QR algoritmu

    Cvičení MATLAB:

    • S využitím přiložených funkcí createbulge a bulgechasing naprogramujte implicitní QR-algoritmus pro 1 shift.
    • Přidejte zastavovací kritérium a redukci dimenze.
    • Porovnejte konvergenci implicitního a explicitního QR-algoritmu (z minulé hodiny).
    • Testujte oba algoritmy na různých maticích.

  • Témata navíc

    Téma hodiny: Aproximace singulárního rozkladu

    • výpočet vlastních vektorů
    • QR algoritmus ve variantě pro SVD
    • bidiagonální preprocesing

    Cvičení MATLAB:

    • Stáhněte si funkci EIGSVDGUI, která vizualizuje výpočet vlastních (a singulárních) čísel implicitním QR algoritmem https://www.mathworks.com/matlabcentral/mlc-downloads/downloads/submissions/37976/versions/7/previews/eigsvdgui.m/index.html
    • Spusťte funkci příkazem run eigsvdgui a procházejte přednastavené experimenty (symetrická/obecná čtvercová/obdélníková matice).
    • Sledujte preprocesing na tridiagonální/Hessenbergův/bidiagonální tvar a konvergenci nežádoucích prvků matice k nule.
    • Zkonstruujte testovací matici A = [ 0 2 0 -1; 1 0 0 0; 0 1 0 0; 0 0 1 0]. Ukažte matematicky, že má dvě dvojnásobná reálná vlastní čísla. Odvoďte její Jordanův tvar.
    • Spusťte eigsvdgui(A) -> metoda vrací komplexní čísla -> důvod: matice má citlivá vlastní čísla, nelze je spolehlivě aproximovat.
    • Použijte eigtool (z předchozích cvičení) k studiu citlivosti přes pseudospektrum, podmíněnost A, podmíněnost vl. čísel a vektorů atd.
    • Zopakujte experiment s maticí gallery('frank', 32), randn(40), wilkinson(40).

  • Přednáška 16.5. zrušena

    Předtermín zkoušky 17.5. v 9:00, seminární místnost KNM