Počítačové metody v teoretické fyzice - TMF057(ZS 2019-20)

Aktuality:

(8.1.2020) Aktualizoval jsem syllabus podle letošní přednášky. Témata zobrazená šedě jsem nestihl, nebo nezkouším. V SISu jsou vypsány zkouškové termíny.

(20.11.2019) Doplnil jsem seznam obsazených úloh. Seznam úloh budu ještě rozšiřovat, pokud byste měli zájem o některou již obsazenou úlohu nebo nějaké konkrétní téma, ozvěte se a něco vymyslíme. Také jsem vypsal předtermín na pátek 20.12. – prosím odevzdejte předem zápočtovou úlohu, ať se na ni mohu před zkouškou podívat.

(19.11.2019) Vytvořil jsem předběžnou verzi seznamu zápočtových úloh pro tento semester – až na vyjímky ze starých úloh. Průběžně zkusím doplnit ještě pár úloh, ale pokud chcete na nějaké úloze začít pracovat napište mi e-mail, kterou úlohu řešíte a já vytvořím seznam obsazených úloh.

(1.10.2019) Přednáška probíhá 9:00-11:20 v přednáškové místnosti UČJF v 8.patře. Letos přednáší Martin Čížek , stránky Karla Houfka najdete zde.

Syllabus contains most of the examples in Python (some using NumPy libraries) which you could see in the lecture. The LIST OF PROBLEMS FOR CREDITS will appear in due time. You should select one of the problems and solve it in suitable programming language (C, C++, C#, Fortran, Pascal, Python) using floating point arithmetic. You will present your solution at the exam including your understanding of the theory related to the subject of the selected problem. The exam will consist of this presentation and one additional theoretical question.

Czech syllabus English version is available here.

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řevedení 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.
• Metody typu Runge-Kutta. Základní princip metody, lokální diskretizační chyba. Výhody a nevýhody ve srovnání s LIMUFO.

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.