Analyza maticovych vypoctu 2
Osnova sekce
-
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
-
Téma hodiny: Citlivost vlastních čísel - vzdálenosti spekter
- vlastní čísla jako spojitá funkce prvků matice
- definice vzdálenosti spekter matice a matice perturbované
- viz. též skripta str. 25 - 29
- důkaz Roucheho věty pro zájemce (nezkouší se): https://proofwiki.org/wiki/Rouch%C3%A9%27s_Theorem
Cvičení MATLAB:
- Experimenty s citlivostí vlastních čísel jednoduchých testovacích matic.
- Vliv FPA na výpočet vlastních čísel.
-
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
-
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
-
Téma hodiny: Pseudospektrum a pole hodnot: definice, vlastnosti, výpočet
- odchylka matice od normality
- definice pseudospektra a pole hodnot
- jejich vlastnosti a techniky aproximace
- viz. též skripta str. 36, 51 - 60 a web https://www.cs.ox.ac.uk/pseudospectra/index.html
- důkaz, že pole hodnot je konvexní množina viz https://math.unm.edu/~vageli/courses/Ma504/Field_of_Values.pdf
Cvičení:
- vlastnosti pseudospektra a pole hodnot
- výpočet odchylky od normality
-
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:
- Podívejte se na příklady pseudospekter na https://www.cs.ox.ac.uk/pseudospectra/examples.html
- Stáhněte si software EigTool pro MATLAB na http://www.cs.ox.ac.uk/pseudospectra/eigtool/
- Studujte s jeho pomocí vlastní čísla, jejich podmíněnost a citlivost; pseudospektra; pole hodnot; podmíněnosti matic
- Demos -> Dense matrices -> Random
- Demos -> Dense matrices -> Grcar
- Demos -> Dense matrices -> Frank
- Demos -> Dense matrices -> Davies
- File -> New matrix -> gallery('jordbloc',50,0)
- 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.
-
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 dimenzen= 1, ..., 20.
Sledujte pomocí příkazucond()
, jak s parametremn
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 rovnicHx=b
pomocí backslash operátoru a sledujte, jak s parametremn
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)
, ... ).
-
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.
-
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 .
-
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á?
-
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é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ředtermín zkoušky 17.5. v 9:00, seminární místnost KNM