Kurs slouží k získání základních dovedností a citu pro implementaci přesných a stabilních algoritmů, spolehlivě fungujících ve skutečných numerických výpočtech. Výklad je doprovázen praktickými cvičeními a ukázkou aplikace v konkrétních simulačních kódech s možností zapojení studentů do aktuálně řešených výzkumných projektů. Základy teorie výpočtů s konečnou přesností, typy chyb, jejich hromadění a interakce, stabilita výpočtu a zpřesňování výsledků. Vhodné techniky pro sčítání, práci s polynomy a maticemi. Algoritmy počítačové geometrie: průsečíky a průniky přímek, úseček a polygonů, triangulace a dělení polygonů, Voronoiovy diagramy, Delaunayova triangulace, dělení roviny (arrangement), hledání konvexního obalu, případně plánování pohybu robota. Lineární a nelineární numerická optimalizace bez vazeb a s vazbami.
Robustní numerické algoritmy
Požadavky:
Povinné:
- Není požadováno předchozí absolvování žádného konkrétního předmětu
Doporučené:
- Znalost alespoň jednoho vhodného programovacího jazyka (C, Fortran, Pascal, Matlab apod.)
- Znalost základů lineární algebry v rozsahu prvního semestru
Osnova přednášek:
1. Výpočty s konečnou přesností - typy a hromadění / interakce chyb, zpřesňování výsledků, stabilita, mýty a pověry, návrh stabilního algoritmu, reprezentace čísel v počítači
2. Základní operace a techniky - analýza chyb, sumace, polynomy, matice, stabilita lineárních systémů
3. Průsečíky a průniky přímek, úseček a polygonů - algoritmy, komplikace; aplikace: výpočetní sítě (remap), raytracing
4.-5. Triangulace a dělení polygonů - teorie a algoritmy triangulace, výpočet plochy, dělení na konvexní polygony; aplikace: generování sítí
5. Voronoiovy diagramy, Delaunayova triangulace, dělení roviny (arrangement) - definice, vlastnosti, algoritmy; aplikace: adaptace sítě
6. Konvexní obal ve 2D a 3D - naivní algoritmy, Quickhull, rozděl a panuj,...
7. Numerická optimalizace - (jednoduché 1D metody (linesearch), výběr směru ve více dimenzích, konjugované gradienty, simplexová metoda, kvadratické programování s vazbami; aplikace: optimalizace kvality sítě
Osnova cvičení:
- Studenti budou na počítači implementovat metody a problémy probírané na přednášce a naučí se tak sami odhalovat a překonávat konkrétní nástrahy
- Průběžně jsou zařazeny ukázky aplikací ve vybraných skutečných simulačních kódech vyvíjených na KFE a ve spolupráci s dalšími institucemi
- Případně budou prezentovány a konzultovány numerické výpočty jež jsou součástí právě řešených kvalifikačních prací (BP, DP) studentů předmětu
- Možnost zapojení studentů do aktuálních výzkumných projektů
Cíle studia:
Znalosti:
- vybrané klasické algoritmy numerické matematiky, s nimi spojené obtíže a nástrahy a možnosti jejich řešení
Schopnosti:
- základní dovednosti a cit pro implementaci přesných a stabilních algoritmů, spolehlivě fungujících ve skutečných numerických výpočtech
- komplexní řešení daného numerického problému, od návrhu kvalitní metody až po skutečnou implementaci
Povinná literatura:
- N.J. Higham: Accuracy and Stability in Numerical Algorithms
- J. O'Rourke: Computational Geometry in C
Doporučená literatura:
- W.H. Press et al.: Numerical Recipes. The Art of Scientific Computing
- P.J. Schneider, D.H. Eberly: Geometric Tools for Computer Graphics
- F.P. Preparata, M.I. Shamos: Computational Geometry. An Introduction
- M. de Berg et al.: Computational Geometry. Algorithms and Applications
- O. Hjelle, M. Daehlen: Triangulations and Applications
- J. Nocedal, S.J. Wright: Numerical Optimization
- www.geometrictools.com
Studijní pomůcky:
- Počítačová učebna s OS UNIX/Linux a vhodnými programovacími jazyky (C, Fortran, Matlab, příp. Pascal)
