Počítačové metody v teoretické fyzice - NTMF057(ZS 2021-22)

Aktuality:

(5. 1. 2021) Založil jsem termíny zkoušek do SISu a aktualizoval sylabus. Také odkazy na demonstrační programy v pythonu by měly být již všechny funkční. Zkouška bude probíhat tak, že vám zadám dvě otázky z teorie, jednu tématicky k vybrané zápočtové úloze, druhou něco dalšího z probraných témat (sylabus) a nechám vám čas na přípravu. Součástí ústní zkoušky bude předvedení zápočtového programu a jeho výsledků. Pokud chcete, můžete mi jej poslat předem a tak se vyhneme případným nejasnostem a zdržení v udělení zápočtu. (Případné nedostatky v odevzdaných úlohách žádám odstranit a výsledek zápočtu a zkoušky zapíšu až po jejich odevzdání).

(6. 12. 2021) Zveřejnil jsem první verzi zadání zápočtových úloh. Možná ještě nějaké přidám, ale tyto tam zůstanou. Prosím vyberte si nějakou a samostatně vypracujte. U zkoušky budu chtít slyšet teorii k úloze (plus vyberu ještě jednu teoretikou otázku) a v případě potřeby budu chtít, abyste uměli do řešení interaktivně něco dodělat/upravit. V sylabu jsou u probraných témat už aktuální verze příkladů v PYTHONU.

(23.11.2021) Aktualizuji stránku, zatím ještě není hotové, ale brzy dodělám. Zatím jsem v sylabu vyznačil šedě témata, která jsme ještě neprobrali. Pro ty co nemohli přijít na nějakou přednášku doporučuji moje poznámky ze seznamu literatury a videozáznamy loňské přednášky od Karla Houfka (link je v SISu). Chybí přidat aktualizované příklady v pythonu. Zatím jsou tam staré verze s drobnymi doplňky v lekcích 1 a 2. Ostatní brzy doplním. Odkaz na starou stránku je zde.

Přednáška probíhá v Po 9:50-12:05 v přednáškové místnosti UTF v 10.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 soon. 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.

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 – Aitken-Neville ........... ....................demoL03.01_A-N.scheme.py
2. A-N schema – konvergence……………………...demoL03.02_convergence.py
3. Problémy vysokého stupně na rovnoměr. Sítí… ..demoL03.03_problems.py
4. Chování polynomu omega..................................... demoL03.04_omega.gnu (script pro gnuplot - testováno ve verzi 4.7)
5. Interpolace na Čebyševově síti..............................demoL03.05_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)
3. Totéž, ale novější verze s pyplot…………………demoL4.02_derivace.py
4. Integrace lichobeznikovym pravidlem………… demoL4.03_trapezoid.py

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 nové

1. Konstrukce a obrázek řešení rovnice DemoL5.01_LIMUFO_new.py

2. Konstrukce celého řešení najednou DemoL5.02_global_new.py

3. Konvergence v koncovém bodě – analýza chyb DemoL5.03_convergence.py

4. Konstrukce řešení pro implicitní metody DemoL5.04_implicit.py

5. Analýza chyb a příklad problému se silným tlumením DemoL5.05_conv_stiff.py

Demonstrace staré: (s výpisem do souboru a vykreslením gnuplotem)

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 "sweepy"..........................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.