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:
- Zaokrouhlovací chyba (triviální příklad) ......................
demoL01.01_wrong_loop.py
- Sčítání odpředu = sčítání odzadu?
..............................
demoL01.02_suma.py
- Zaokrouhlovací chyba při odčítání...............................
demoL01.03_cancelation.py
- Kvadratická rovnice (minimalizace zaokr. chyby).........
demoL01.04_quadratic.py
- 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:
-
cos(cos(cos(...cos(1.0)...)))..................................demoL02.01_coscos.py
- Babylonská metoda výpočtu odmocniny................demoL02.02_Babylon.py
- Aitken na cos
cos.................................................demoL02.03_Aitken.py
- Aiten-Steffensen na cos
cos..................................demoL02.04_AitkenSteffensen.py
- Newtonův fraktál = odpověď na
otázku: "Ke kterému kořenu rovnice z3-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)
- Interpolace na rovnoměrné síti...............................demoL03.01_regular.py
- Chování polynomu omega.....................................demoL03.02_omega.gnu
(script pro gnuplot - testováno
ve verzi 4.7)
- 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)
- Derivace různými diskretizačními formulemi .........demoL4.01_derivace.py
- 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)
- Výpočet řešení počáteční úlohy explicitními formulemi
...........demoL5.01_LIMUFO.py
- Zobrazení řešení pro různé metody
....................................... reseni.gnu
(script pro gnuplot, ukaze data z predchoziho *.py)
- Testování rychlosti konvergence pro zmenšující se
krok..........demoL5.02_global.py
- Zobrazení rychlosti konvergence
...........................................
konverg.gnu
- Jako 1,2 ale implicitni.............................................................demoL6.01_implicit.py,
reseni.gnu
- 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í):
- Nalezení vlastních fcí kvantového oscilátoru
..................DemoL8.01_QR_LHO.py
- Zpetná stabilita QR
faktorizace.....................................DemoL8.02_zpet_stabil.py
- 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)
- Gauss bez pivotace......................DemoL9.01_LU_nestab.py
- Gauss s pivotaci...........................DemoL9.02_LU_pivot.py
- 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)
- Pouziti diagonalizace z numpy..........................DemoL10.01_eigval.py
- Jacobiho metoda se "speepy"..........................DemoL10.02_Jacobi.py
- 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.