Počítačové metody v teoretické fyzice - NTMF057(ZS 2023-24)
Aktuality:
(15. 12. 2023) 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.
Přednáška probíhá v Pa 9:00-11:15 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:
- 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
– Aitken-Neville ...........
....................demoL03.01_A-N.scheme.py
- A-N
schema – konvergence……………………...demoL03.02_convergence.py
- Problémy
vysokého stupně na rovnoměr. Sítí… ..demoL03.03_problems.py
- Chování
polynomu omega..................................... demoL03.04_omega.gnu
(script pro gnuplot - testováno ve verzi 4.7)
- 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)
- Derivace
různými diskretizačními formulemi .........demoL4.01_derivace.py
- Zobrazení
výsledků..............................................demoL4.01_derivace.gnu
(script pro gnuplot)
- Totéž,
ale novější verze s pyplot…………………demoL4.02_derivace.py
- 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)
- 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 "sweepy"..........................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.