Численные методы (8 семестр)
Лекции:
Григорий Рубцов
Семинары: Александр Иванов, Михаил Кузнецов
Семинары: Александр Иванов, Михаил Кузнецов
Рассматриваются алгоритмы и подходы к численному решению задач, возникающих в физике частиц и космологии.
План курса
- Введение
- численные методы и их применение в физике
- доступные инструменты: языки, среды, математические библиотеки
- возможности современных вычислительных машин
- представление чисел с плавающей точкой; ошибки округления
- алгоритмы: сложность, точность, устойчивость
- Методы решения задач линейной алгебры
- решение систем линейных уравнений, нахождение обратной матрицы
- метод Гаусса-Жордана; UL-разложение; сингулярное разложение
- трехдиагональные матрицы; метод прогонки, его связь с UL-разложением
- ленточные метрицы
- Интерполяция и приближение
- интерполяциия полиномами; интерполяция сплайнами
- приближение методом наименьших квадратов; метод наибольшего правдоподобия
- Методы оптимизации
- симплекс-метод
- метод сопряженных градиентов
- Численное дифференцирование
- точность вычисления производной
- частные производные; лаплассиан
- понятие разностной схемы
- Генерация случайных чисел
- методы генерации случайных чисел
- тестирование генератора
- хэш-функции и их применения
- генерация случайной величины с заданным распределением
- Статистический анализ данных
- проверка гипотез; уровень достоверности
- критерий Колмогорова-Смирнова; критерий Смирнова-Крамера-фон Мизеса
- проверка неточно сформулированной гипотезы, штрафные множители
- Быстрое преобразование Фурье (FFT)
- одномерное и многомерное FFT
- вычисление корреляционных функций, спектральный анализ данных
- фильтры
- Обработка больших объемов данных
- форматы хранения больших объемов данных: бинарные форматы, реляционные и нереляционные базы данных
- построение индексов; хэш-индексы, древесные индексы
- алгоритмы потоковой обработки данных
- Алгоритмы параллельных вычислений
- аппаратные среды: суперкомпьютер с общей памятью, кластер, грид, облако
- программные средства: MPI, openmp, LHC-grid, собственный протокол
- степень параллелизма алгоритмов различного типа
- распределенное хранение данных
- Численное интегрирование
- элементарные методы (трапеций, Симпсона, Ньютона-Котеса)
- экстраполяция Ричардсона
- несобственные интегралы; интегрирование быстро осциллирующих функций
- квадратуры Гаусса; метод Монте-Карло
- методы многомерного интегрирования
- Дифференциальные уравнения
- задача Коши для обыкновенных дифференциальных уравнений
- сходимость разностной схемы
- метод Рунге-Кутта, неявные методы
- методы решения одномерной краевой задачи; метод стрельбы
- Уравнения в частных производных
- дискретизация
- метод матричной прогонки
- релаксационные методы
- сведение к задаче оптимизации; минимизация действия
- многосеточный метод (multigrid)
- Стохастические алгоритмы
- метод цепей Маркова (Markov chain Monte Carlo)
- алгоритм Метрополиса
- W.H. Press, S.A. Teukolsky, W.T. Vettering, B.P. Flannery, «Numerical recipes. The art of scientific computing» Cambridge university press, 2007.
- E.L. Lehmann, J.P. Romano, «Testing Statistical Hypotheses» Springer, 2005.