Robustní numerické algoritmy

Garant předmětu:

Pavel Váchal

Přednášející:

Pavel Váchal

Cvičící:

Pavel Váchal

Předmět zajišťuje:

katedra fyzikální elektroniky

Anotace:

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.

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

Studijní materiály:

Povinná literatura:

[1] N.J. Higham: Accuracy and Stability in Numerical Algorithms

[2] J. O'Rourke: Computational Geometry in C

Doporučená literatura:

[3] W.H. Press et al.: Numerical Recipes. The Art of Scientific Computing

[4] P.J. Schneider, D.H. Eberly: Geometric Tools for Computer Graphics

[5] F.P. Preparata, M.I. Shamos: Computational Geometry. An Introduction

[6] M. de Berg et al.: Computational Geometry. Algorithms and Applications

[7] O. Hjelle, M. Daehlen: Triangulations and Applications

[8] J. Nocedal, S.J. Wright: Numerical Optimization

[10] 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)

Poznámka:

Rozvrh na zimní semestr 2023/2024:

Rozvrh není připraven

Rozvrh na letní semestr 2023/2024:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• Fyzikální elektronika - Počítačová fyzika (PS)