O złożoności zadań numerycznych matematyki ciągłej

Analiza numeryczna jest dziedziną matematyki, a także informatyki, która zajmuje się konstrukcją, teoretyczną analizą i implementacją algorytmów dla zadań numerycznych matematyki ciągłej. Obejmuje z jednej strony zaawansowane matematycznie badania, a z drugiej kwestie związane z wpływem hardware’u i software’u na konkretne implementacje algorytmów.

W tym wystąpieniu skoncentrujemy się na badaniu złożoności zadań numerycznych. Ponieważ dokładne rozwiązania są nieosiągalne, istotną rolę w analizie pełni informacja o zadaniu. Najpierw zaprezentujemy podstawowe pojęcia związane z teorią złożoności zadań ciągłych. Następnie pokażemy na dwóch przykładach jak taka analiza może być przeprowadzona. Pierwszy z nich dotyczy całkowania funkcji jednej zmiennej na podstawie informacji o jej wartościach w skończonej liczbie punktów. Drugi problem to aproksymacja w normie $L^p$ funkcji wielu zmiennych, gdzie informacja o wartościach funkcji jest dodatkowo zaburzona zmieniającym się szumem gaussowskim.

Aby dołączyć do spotkania prosimy o skorzystanie z linku meet.google.com/xui-qqpw-fze na kilka minut przed 14:30. Osoby posiadające konto google z adresem UW prosimy o wcześniejsze zalogowanie.

Numerical analysis is the area of mathematics and also computer science whose main tasks are creation, theoretical analysis, and implementations of algorithms for solving numerically problems of continuous mathematics. It ranges from highly theoretical mathematical studies to issues related to influence of computer hardware and software on concrete implementations of specific algorithms.

In this talk, we concentrate on complexity of numerical problems. Since exact solutions are not available, information about the problem plays a crucial role in the analysis. We first present a general framework of information-based complexity theory. Then we give two examples illustrating how such analysis can be done. The first problem is the univariate integration from information about finitely many values of the integrand. The second problem is $L^p$-approximation of multivariate functions where information about their values is additionally corrupted by varying Gaussian noise.

In order to join the meeting please follow the link meet.google.com/xui-qqpw-fze a few minutes before 2:30 p.m. If you have a google account with a UW address, please log-in first.