Počítačové metody v teoretické fyzice - TMF057(ZS 2015-16)

Aktualiky: (25. ledna 2016) Do sylabu jsem doplnil literaturu. V SISu jsem vypsal termíny zkoušek, pokud někomu nevyhovuje žádný, napište mi e-mail. Ke zkoušce si přineste jednu vypracovanou zápočtovou úlohu, kterou společně projdeme. Dále dostanete dvě teoretické otázky, jednu k tématům ze zápočtové úlohy, druhou z dalších přednesených témat.

 (15. ledna 2016) Zde je zadání zápočtových úloh (každý si vyberte jednu) a doplnil jsem sylabus a demostrační scripty v pythonu.

LEKCE 1 - Zaokrouhlovací chyby a numerická stabilita. (viz [1], pro hlubší zájemce též [4,5,7])

• Reprezentace reálných čísel v pohyblivé řádové čárce a zaokrouhlovací chyba.
• Strojové epsilon, skládání chyb při základních aritmetických operacích. Problémy s odčítáním podobných čísel.
• Numerická stabilita a podmíněnost úlohy.

Demonstrace:

1. Zaokrouhlovací chyba (triviální příklad) ...................... demoL01.01_wrong_loop.py
2. Sčítání odpředu = sčítání odzadu? .............................. demoL01.02_suma.py
3. Zaokrouhlovací chyba při odčítání............................... demoL01.03_cancelation.py
4. Kvadratická rovnice (minimalizace zaokr. chyby)......... demoL01.04_quadratic.py
5. Proč nekonverguje absolutně konvergentní řada?......... demoL01.05_Taylor_exp.py

Cvičení: Určení čísla pi Archimedovou metodou. (pokus1-nestabilní, pokus2-funkční, pokus3-urychlení konvergence)

LEKCE 2 - Iterace a řešení nelineárních rovnic. (viz [1], pro hlubší zájemce též [5,7,8])

• Věta o pevném bodě kontrahujícího zobrazení a konvergence iterací.
• Odhad chyby, řád konvergence a její urychlování.
• Aitkenův a Aitkenův-Steffensenův algoritmus.
• Iterační řešení nelineárních rovnic. Newtonova metoda.

Demonstrace:

1. cos(cos(cos(...cos(1.0)...)))..................................demoL02.01_coscos.py
2. Babylonská metoda výpočtu odmocniny................demoL02.02_Babylon.py
3. Aitken na cos cos.................................................demoL02.03_Aitken.py
4. Aiten-Steffensen na cos cos..................................demoL02.04_AitkenSteffensen.py
5. Newtonův fraktál = odpověď na otázku: "Ke kterému kořenu rovnice z³-1=0 dokonverguje Newtonův algoritmus spuštěný z daného místa komplexní roviny?" dává obrázek https://en.wikipedia.org/wiki/Newton_fractal

LEKCE 3 - Interpolace a interpolační polynomy. (viz [1], pro hlubší zájemce [2,8])

• Existence a jednoznačnost polynovmiální iterpolace.
• Lagrangeova interpolace, Aitkenovo-Nevillovo Schema.
• Chybový vzorec a jeho chování na rovnoměrné a Čebyševově síti.
• Hermiteova interpolace, chybový vzorec a souvislost s Taylorovou řadou.

Demonstrace: (používají metod knihovny Turtle graphics z Pythonu pro zobrazení dat)

1. Interpolace na rovnoměrné síti...............................demoL03.01_regular.py
2. Chování polynomu omega.....................................demoL03.02_omega.gnu (script pro gnuplot - testováno ve verzi 4.7)
3. Interpolace na Čebyševově síti..............................demoL03.03_chebychev.py

LEKCE 4 - Interpolace na rovnoměrné síti, diferenční rovnice. (viz [1], pro hlubší zájemce [5])

• Operátory zpětné a dopředné diference. Funkce operátorů.
• Newtonova interpolační formule.
• Odvození vzorců pro derivaci interpolačních polynovů.
• Numerické integrování a Eulerova-Maclaurinova sumační formule.
• Lineární diferenční rovnice a jejich řešení. Explicitní formule pro Fibonacciho posloupnost.

LEKCE 5 - Numerická derivace derivace a integrace. (viz [1], pro hlubší zájemce [2,5,8])

• Analýza chování zaokrohlovací a diskretizační chyby pro různé aproximace derivace funkce.
• Integrace pomocí Newtonových-Cotesových formulí.
• Použití Richardsonovy extrapolace a Rombergova integrace.
• Gaussova kvadratura a ortogonální polynomy.
• Diskuse různých přístupů k interaci, singularity integrandu, nevlastní integrály. Více dimenzí.

Cvičení: Numerické derivování, diskretizační a zaokrouhlovací chyba (výpis numerické derivace pro různé hodnoty h do souboru a zobrazení chyby výsledků pomocí gnuplotu).

Demonstrace: (Numerická derivace, diskretizační x zaokrouhlovací chyba)

1. Derivace různými diskretizačními formulemi .........demoL4.01_derivace.py
2. Zobrazení výsledků..............................................demoL4.01_derivace.gnu (script pro gnuplot)

LEKCE 6 - Numerická integrace diferenciálních rovnic. (viz [1], pro hlubší zájemce [2,3])

• Formulace počáteční úlohy pro ODR. Převení rovnice vyššího řádu na soustavu rovnic prvního řádu.
• Příklady odvození jednoduchých diferenčních schémat.
• Formulace obecné lineární multikrokové formule (LIMUFO). Řád přesnosti a konzistence metody.
• Souvislost s aproximací funkce logaritmus, odvození metod pomocí Padého aproximace. Metody AB, BA a BD
• Charakteristické polynomy a stabilita metody. Stabilita Adamsových metod a zpětné diference.
• Dahlquistovy věty o konvergenci a bariéry stability, absolutní stability, oblasti stability.

Demonstrace: (Numerické řešení diferenciálních rovnic)

1. Výpočet řešení počáteční úlohy explicitními formulemi ...........demoL5.01_LIMUFO.py
2. Zobrazení řešení pro různé metody ....................................... reseni.gnu (script pro gnuplot, ukaze data z predchoziho *.py)
3. Testování rychlosti konvergence pro zmenšující se krok..........demoL5.02_global.py
4. Zobrazení rychlosti konvergence ........................................... konverg.gnu
5. Jako 1,2 ale implicitni.............................................................demoL6.01_implicit.py,    reseni.gnu
6. Jako 3,4 ale implicitni ............................................................demoL6.02_stiff.py,         kstif.gnu

LEKCE 7 - Numerická lineární algebra - faktorizace matic. (viz [2,4])

• O numerické algebře obecně: pojem faktorizace matice, charakterizace algoritmu pomocí asymptotické složitosti (FLOPs)
• Gram-Schmidtova ortogonalizace a QR-faktorizace. Stabilita, Hausholderova metoda, složitost algoritmu.
• SVD-faktorizace. Existence singulárního rozkladu a jeho použití.
• Řešení soustavy rovnic ve smyslu nejmeších čtverců. Normální rovnice a pseudoinverze, řešení pomocí faktorizací.
• Norma vektoru a matice. Příklady norem a jejich výpočet. Základní nerovnosti.
• Stabilita a zpětná stabilita. Zpětná stabilita QR faktorizace.

Demonstrace: (Faktorizace matice a její použití):

1. Nalezení vlastních fcí kvantového oscilátoru ..................DemoL8.01_QR_LHO.py
2. Zpetná stabilita QR faktorizace.....................................DemoL8.02_zpet_stabil.py
3. Hodnost matice pomocí QR.........................................DemoL8.03_Hello.py

LEKCE 8 - Numerická lineární algebra - Gaussova eliminace. (viz [2,4])

• Podmíněnost úlohy. Číslo podmíněnosti matice a jeho význam pro různé úlohy.
• Řešení soustavy rovnic a jeho souvislost s Gaussovou eliminací. LU rozklad.
• Stabilita LU rozkladu Gaussovou eliminací, pivotace.
• Použití LU rozkladu na řešení soustav, nalezení inverze, determinantu matice.
• Složitost Gaussovy eliminace. Tridiagonální a pásové matice. Symetrické matice (Choleského rozklad)
• Řešení soustav rovnic se špatně podmíněnou maticí. Použití SVD.

Demonstrace: (Gaussova eliminace a LU rozklad)

1. Gauss bez pivotace......................DemoL9.01_LU_nestab.py
2. Gauss s pivotaci...........................DemoL9.02_LU_pivot.py
3. LU rozklad z knihovny scipy.........DemoL9.03_LU_linalg.py

LEKCE 9 - Numerická lineární algebra - diagonalizace matic. (viz [2,4,5])

• Pojem diagonalizace. Vlastní čísla a jejich multiplicita. Levé a pravé vlastní vektory. Charakteristický polynom.
• Diagonalizace reálné symetrické matice Jacobiho metodou. Konvergence a asymptotická složitost metody.
• Přehled dalších metod. Převedení do tridiagonálního (Hessenbergova) tvaru.
• Princip QR algoritmu. Hledání kořenů charakteristického polynomu tridiagonální matice.

Demonstrace: (Diagonalizace Jacobiho metodou)

1. Pouziti diagonalizace z numpy..........................DemoL10.01_eigval.py
2. Jacobiho metoda se "speepy"..........................DemoL10.02_Jacobi.py
3. Jacobiho metoda s vyhledáním max. prvku......DemoL10.03_Jacobi_max.py

LEKCE 10 - Diskrétní Fourierova transformace (odpřednesl jsem zrychleně - nezkouším, základní informace viz [2,3])

• FT, semiDFT a DFT, Nyquistova frekvence.
• Algoritmust rychlé Fourierovy transformace (FFT) a jeho složitost.
• Použití Fourierovy transformace na řešení problémů.

DOPORUČENÁ LITERATURA:

Opírám se především o [1] a [4]. Jako vhodný doplněk pro praktickou implementaci algoritmů lze vždy doporučit [2]. Ostatní uvedené knihy jsou vhodným doplňkem k různým tématům, viz zelené poznámky.

• [1] (stále neúplné) moje poznámky k přednášce.- základní odkaz pro první část přednášky.
• [2] Press, Teukolsky, Vetterling, Flannery: Numerical Recipes in Fortran (or in C), k dipozici online. Starší verze zdarma. Tištěná verze by měla být v knihovně. - základní odkaz pro většinu témat k přednášce.
• [3] L. N. Trefethen: Finite difference and spectral methods for ODE and PDE. Nedopsaná kniha přístupná online. Pěkný pedagogický výklad LIMUFO.
• [4] L.N. Trefethen, D. Bau III: Numerical Linear Algebra. SIAM 1997. Pěkný pedagogický výklad numerické lineární algebry.
• [5] Isaacson, Keller: Analysis of Numerical Methods. Důkladnější matematická analýza pro většinu témat z přednášky.
• [6] Koonin: Computational Physics. Řešené příklady s fyzikální tématikou.
• [7] Henrici: Essentials of Numerical Analysis with Pocket Calculator Demonstrations. Základy numerické matematiky s pěknými příklady.
• [8] Segethová: Základy numerické matematiky. Skriptum MFF UK, výběr základních algoritmů a jejich analýza včetně důkazů.

Poznámka k Pythonu: Výše uvedené příklady v Pythonu používají knihovny numpy a matplotlib. Python lze stáhnout zdarma. Jedna z možností je:

1 jít na https://www.continuum.io/downloads stáhnout anacondu dle vlastniho výběru
2 nainstalovat
3 spustit Anaconda Launcher
4 spustit Spyder - IDE (obsahuje i interaktivní konzoli) nebo spustit Ipython-qtconsole - interaktivni python .

Informace z loňských stránek Karla Houfka naleznete naleznete zde.