|
|
| (не показано 7 промежуточных версии этого же участника) |
| Строка 1: |
Строка 1: |
| − | == О курсе ==
| |
| − |
| |
| − | Курс по выбору для студентов для студентов 3 и 4 курса в 1-2 модулях.
| |
| − |
| |
| − | '''Лектор:''' Рахуба Максим Владимирович
| |
| − |
| |
| − | Лекции проходят на Покровке по вторникам в ауд. D510 (09:30 - 10:50)
| |
| − |
| |
| − | '''Семинарист:''' Высоцкий Лев Игоревич
| |
| − |
| |
| − | Семинары проходят онлайн по пятницам (13:00 - 14:20)
| |
| − | Ссылка на регулярную Zoom-конференцию: https://zoom.us/j/91934043735
| |
| − |
| |
| − | '''Ассистент курса:''' Фёдоров Андрей Александрович
| |
| − |
| |
| − | Домашние задания необходимо присылать на почту aafedorov_2@edu.hse.ru
| |
| − |
| |
| − | === Полезные ссылки ===
| |
| − |
| |
| − | Телеграм-канал курса: https://t.me/joinchat/AAAAAFkvC-gUnDmoK-YY2w
| |
| − |
| |
| − | Телеграм-чат курса: https://t.me/joinchat/AiDEvBgUTMjcfkWpD8NMWA
| |
| − |
| |
| − | Anytask курса: https://anytask.org/course/706
| |
| − |
| |
| − | == План курса ==
| |
| − |
| |
| − | === Еженедельные тесты ===
| |
| − |
| |
| − | На каждом семинаре (начиная с первого) будет проходить короткий тест по теме последней лекции.
| |
| − |
| |
| − | === Лекции ===
| |
| − |
| |
| − | '''1. Основы матричного анализа''' [https://yadi.sk/i/iTZgqpcy1EDATg Записи с лекции]
| |
| − |
| |
| − | Матричные нормы. Сохранение длин и унитарные матрицы. Разложение Шура. Нормальные матрицы.
| |
| − |
| |
| − | '''2. Малоранговая аппроксимация матриц''' [https://yadi.sk/i/06phQHGsdvmTjQ Записи с лекции]
| |
| − |
| |
| − | Разделение переменных и скелетное разложение. Сингулярное разложение матриц. Теорема Эккарта-Янга-Мирского.
| |
| − | Ортопроекторы. Простейший рандомизированный алгоритм поиска малорангового приближения матриц.
| |
| − |
| |
| − | '''3. Малоранговая аппроксимация матриц 2''' [https://yadi.sk/i/r3J39_a6KexeNA Записи с лекции], [https://yadi.sk/i/D0jYHzi64B5EZg Слайды (метод крестовой аппроксимации)]
| |
| − |
| |
| − | CUR разложение матриц. Метод крестовой аппроксимации матриц. ALS (Alternating Least Square) алгоритм для матричной факторизации.
| |
| − |
| |
| − | '''4. Малоранговая аппроксимация тензоров ''' [https://yadi.sk/i/OYKwAVfh3ozEqA Записи с лекции]
| |
| − |
| |
| − | Кронекерово и внешнее (тензорное) произведения. Каноническое разложение и разложение Таккера. Теорема о мультилинейном ранге тензора. HOSVD алгоритм.
| |
| − |
| |
| − | '''5. QR разложение и метод наименьших квадратов ''' [https://yadi.sk/i/zn3IGmSXXDWk2w Записи с лекции]
| |
| − |
| |
| − | QR разложением матриц с помощью отражений Хаусхолдера и вращений Гивенса. Метод наименьших квадратов. Решение системы нормальных уравнений с помощью QR и SVD разложений. Псевдообратная матрица Мура-Пенроуза.
| |
| − |
| |
| − | '''6. Быстрое преобразование Фурье и структурированные матрицы ''' [https://yadi.sk/i/lT15uA_QTmC_oA Записи с лекции]
| |
| − |
| |
| − | Матрица Фурье и быстрое преобразование Фурье. Циркулянты и дискретная теорема свертки. Теплицевы матрицы.
| |
| − |
| |
| − | ''' 7. Умножение матриц. Вычислительная устойчивость. ''' [https://yadi.sk/i/nv0MK0no3BOWSg Записи с лекции]
| |
| − |
| |
| − | Сложность умножения матриц. Метод Штрассена и его связь с каноническим разложением тензоров. BLAS и связанные с ним пакеты программ. Представление чисел в памяти компьютера. Вычислительная устойчивость алгоритмов. Основные аксимомы машинной арифметики. Обусловленность задач.
| |
| − |
| |
| − | ''' 8. Прямые методы решения систем линейных уравнений с плотными матрицами. ''' [https://yadi.sk/i/FtU6lowC6-81Hw Записи с лекции]
| |
| − |
| |
| − | LU разложения, его существование и единственность. Стратегии выбора ведущего элемента: частичный и полный выборы. Разложение Холецкого.
| |
| − |
| |
| − | ''' 9. Прямые методы решения систем линейных уравнений с большими разреженными матрицами. ''' [https://yadi.sk/i/q1ce9xApMfIZJg Записи с лекции]
| |
| − |
| |
| − | Формула Шермана-Моррисона. Форматы хранения разреженных матриц. Заполнение, ленточные матрицы. Алгоритмы поиска перестановки, минимизирующей заполнение: Катхилл-Макки, minimal degree ordering, вложенное рассечение (начало следующей лекции).
| |
| − |
| |
| − | ''' 10. Итерационные методы решения систем линейных уравений 1. ''' [https://yadi.sk/i/GSNI0EjilcZ2_g Записи с лекции]
| |
| − |
| |
| − | Метод простой итерации и его сходимость. Методы Якоби и Гаусса-Зейделя. Метод Ричардсона, выбор оптимального параметра. Метод наискорейшего спуска для функционала энергии, оценка сходимости.
| |
| − |
| |
| − | ''' 11. Итерационные методы решения систем линейных уравений 2. ''' [https://yadi.sk/i/To-SsNZvBlOY-A Записи с лекции]
| |
| − |
| |
| − | Итерационный метод Чебышева. Оптимизация на подпространствах и подпространства Крылова. Соотношение Арнольди. Вывод метода сопряженных градиентов.
| |
| − |
| |
| − | === Домашние задания ===
| |
| − |
| |
| − | '''Домашнее задание 1''' [https://yadi.sk/d/e0-v9kUjJ2uZDQ Папка с заданием]
| |
| − |
| |
| − | Задание состоит из [https://yadi.sk/i/yL3BZPCZw1mKSA теоретических задач] в pdf файле и [https://yadi.sk/d/csFrVusKGyLnJw практической задачи] в Jupyter Notebook (не забудьте дополнительно скачать файл с видео из папки).
| |
| − |
| |
| − | Выдается: 02.09.20
| |
| − |
| |
| − | Дедлайн (строгий): 17.09.20 в 21:59
| |
| − |
| |
| − | '''Домашнее задание 2''' [https://yadi.sk/d/NOdnMcvIS6--OA Папка с заданием]
| |
| − |
| |
| − | Задание состоит из [https://yadi.sk/i/MF854Jx16pjZEA теоретических задач] в pdf файле и [https://yadi.sk/d/l8WlrYCW_UQiYw практических задач] в Jupyter Notebook.
| |
| − |
| |
| − | Выдается: 18.09.20
| |
| − |
| |
| − | Дедлайн (строгий): 01.10.20 в 21:59
| |
| − |
| |
| − | '''Домашнее задание 3''' [https://yadi.sk/d/iPcQ9bCgelHMlQ Папка с заданием]
| |
| − |
| |
| − | Задание состоит из [https://yadi.sk/i/90SDdHWo_JiZBw теоретических задач] в pdf файле и [https://yadi.sk/d/KB0p4LhUgtlvUw практических задач] в Jupyter Notebook.
| |
| − |
| |
| − | Выдается: 02.10.20
| |
| − |
| |
| − | Дедлайн (строгий): 15.10.20 в 21:59
| |
| − |
| |
| − | '''Домашнее задание 4''' [https://yadi.sk/d/ESEDQP6hcaSjlQ Папка с заданием]
| |
| − |
| |
| − | Задание состоит из [https://yadi.sk/i/CUEvhVuQ_JMgCQ теоретических задач] в pdf файле и [https://yadi.sk/d/bf1T91xoV_AEcA практической задачи] в Jupyter Notebook.
| |
| − |
| |
| − | Выдается: 05.11.20
| |
| − |
| |
| − | Дедлайн (строгий): 19.11.20 в 21:59
| |
| − |
| |
| − | '''Домашнее задание 5''' [https://yadi.sk/d/8RdsWtJ4kyPVHw Папка с заданием]
| |
| − |
| |
| − | Задание состоит из [https://yadi.sk/i/RJINdY--taiR6g теоретических задач] в pdf файле и [https://yadi.sk/d/Jey58f7eHqsqpQ практических задач] в Jupyter Notebook.
| |
| − |
| |
| − | Выдается: 20.11.20
| |
| − |
| |
| − | Дедлайн (строгий): 03.12.20 в 21:59
| |
| − |
| |
| − | === Контрольная работа ===
| |
| − |
| |
| − | Полусеместровая контрольная работа пройдет 02 ноября (понедельник) с 13:00 до 15:00 через Zoom.
| |
| − |
| |
| − | [https://yadi.sk/i/6UIMia-ERoRxCw Задачи для подготовки].
| |
| − |
| |
| − | Контрольная работа будет состоять из задач и нескольких теоретических вопросов на знание основных концепций и теорем из курса. Например:
| |
| − |
| |
| − | 1) Сформулируете дискретную теорему свертки и объясните, как умножать циркулянт на вектор со сложностью O(n log n);
| |
| − |
| |
| − | 2) Сформулируйте ALS алгоритм с ортогонализацией в применении к поиску наилучшего малорангового приближения матрицы A во фробениусовой норме.
| |
| − |
| |
| − | === Экзамен ===
| |
| − |
| |
| − | '''Письменный''' экзамен в аудитории.
| |
| − |
| |
| − | === Итоговая оценка за курс ===
| |
| − |
| |
| − | Итог = Округление(min(10, 0.4 * ДЗ + 0.1 * Б + 0.1 * ПР + 0.2 * КР + 0.3 * Э))
| |
| − |
| |
| − | ДЗ –– средняя оценка за домашние задания
| |
| − | Б –– средняя оценка за бонусные задачи в ДЗ
| |
| − | ПР — средняя оценка за самостоятельные работы на семинарах
| |
| − | КР –– оценка за контрольную работу (проводится в первой половине 2-го модуля)
| |
| − | Э –– устный экзамен
| |
| − |
| |
| − | Округление арифметическое
| |
| − |
| |
| − | Автоматы не предусмотрены
| |
| − |
| |
| | == Литература == | | == Литература == |
| | | | |
| Строка 156: |
Строка 6: |
| | | | |
| | 3) Trefethen, L. N., & Bau III, D. (1997). Numerical linear algebra. (Vol. 50). Siam. Philadelphia. | | 3) Trefethen, L. N., & Bau III, D. (1997). Numerical linear algebra. (Vol. 50). Siam. Philadelphia. |
| | + | |
| | + | 4) Demmel, James W. Applied numerical linear algebra. Society for Industrial and Applied Mathematics, 1997. |
1) Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations 4th Edition. The Johns Hopkins University Press. Baltimore.
2) Тыртышников, Е. Е. (2007). Методы численного анализа. Академия, Москва.
3) Trefethen, L. N., & Bau III, D. (1997). Numerical linear algebra. (Vol. 50). Siam. Philadelphia.
4) Demmel, James W. Applied numerical linear algebra. Society for Industrial and Applied Mathematics, 1997.
