1. Работа с числами с плавающей точкой.

Числа с плавающей точкой (ЧПТ) - стандартный способ представления действительных чисел в компьютерах, аппроксимирующий их в форме: ±m * b^e, где:

Стандарт IEEE 754 определяет форматы (single precision float: 32 бита, double precision double: 64 бита), распределяя биты на знак, экспоненту и мантиссу. Ключевые особенности и проблемы:

Конечная точность и погрешность представления: Большинство действительных чисел не могут быть представлены точно из-за ограниченного числа бит мантиссы. Возникает погрешность округления. Величина машинного эпсилон (ε_mach) - это разница между 1.0 и следующим представимым числом >1.0 - характеризует относительную точность округления (ε_mach ≈ 1.1e^(-16) для double).

Диапазон представимых чисел: Ограничен количеством бит экспоненты. Возможны переполнение (overflow, |число| > max_представимое) и исчезновение порядка (underflow, |число| < min_представимое > 0).

Арифметические операции: Результат операции над ЧПТ часто требует округления до ближайшего представимого числа, внося погрешность.

Потеря значимости (Catastrophic Cancellation): Наиболее опасный эффект. Возникает при вычитании двух очень близких по величине чисел. Значимые разряды в мантиссе сокращаются, а погрешности, которые были в каждом из чисел, остаются и становятся относительно огромными в результате.

Пример:

a = 1.2345678901234

b = 1.2345678900000

a - b = 0.0000000001234 = 1.234e^(-10) (теряются многие значащие цифры).

Некоммутативность и неассоциативность: Из-за округления операции могут давать разные результаты при изменении порядка: (a + b) + c != a + (b + c), a + b != b + a в некоторых пограничных случаях (хотя коммутативность обычно сохраняется для + и *).

Особые значения: ±0, ±∞ (Inf), NaN (Not a Number - результат неопределенных операций типа 0/0, ∞ - ∞).

2. Архитектура памяти.

Современные компьютеры используют иерархию памяти для баланса между скоростью доступа, объёмом и стоимостью. Уровни иерархии (от быстрых к медленным):

Ключевые принципы:

Временная: Повторный доступ к одним данным → кэширование.

Пространственная: Доступ к соседним адресам (например, элементам массива) → загрузка блоков в кэш.

3. Переполнение (overflow), потеря точности (underflow).

Переполнение (overflow) возникает, когда результат вычислений превышает максимальное представимое число для типа данных.

Потеря точности (underflow) возникает, когда результат ближе к нулю, чем минимальное нормализованное число:

 Ключевые последствия:

4. Ошибка округления в арифметике с плавающей точкой, накопление ошибок округления, потеря значимости.

Ошибка округления возникает из-за конечной точности мантиссы (бит): число x представляется как fl(x)=x*(1+δ), где ∣δ∣ ≤ ε_mach ​ (машинное эпсилон, ≈ 10^(−16) для double). Например, 0.1 в двоичной системе хранится с погрешностью.

Накопление ошибок — кумулятивный эффект при последовательных операциях. Погрешность результата n операций может достигать ∼ sqrt(n) * ε_mach​ (случайное округление) или n * ε_mach ​ (худший случай).

Потеря значимости — вычитание близких чисел a ≈ b, усиливающее относительную погрешность:

fl(a−b) = (a * (1+δ_1) − b * (1+δ_2)) ≈ (a−b) + (a * δ_1− b * δ_2).

Относительная ошибка: ∣a * δ_1 − b * δ_2∣/∣a − b∣ ≫ ε_mach ​, если ∣a − b∣ ≪ ∣a∣ + ∣b∣.

Пример:

1.000001−1.000000 = 10^(−6), но при погрешностях δ_i ∼ 10^(−16) результат может иметь относительную ошибку до 10^(−10).

5. Суммирование по Кахану.

Алгоритм Кахана — метод компенсации ошибок округления при суммировании последовательности чисел с плавающей точкой. Он использует дополнительную переменную для отслеживания потерянных младших разрядов.

Алгоритм:

y = x - c (включаем предыдущую ошибку),

 t = sum + y (новая промежуточная сумма),

c = (t - sum) - y (вычисляем ошибку округления),

 sum = t.

Принцип работы:

6. Абсолютная и относительная погрешности.

Абсолютная погрешность (Δx) — разница между точным значением x∗ и его приближением x:

Δx=∣x−x∗∣.

Эта величина характеризует физический размер ошибки (например, погрешность измерения длины в метрах).

Относительная погрешность (δx) — отношение абсолютной погрешности к модулю точного значения x∗:

δx=Δx/∣x∗∣=∣x − x∗∣/∣x∗∣, (x∗ ≠ 0).

Она выражает качество приближения без привязки к масштабу величины (например, 0.01 при x∗=100 означает 1% ошибки).

7. Округление и значащие цифры в записи приближенного числа.

8. Верные в строгом (узком) смысле цифры числа, верные в широком смысле цифры числа.

9. Сложность алгоритмов и нотация big-O.

10. Профилирование кода в Python.

11. Представление чисел с плавающей точкой (стандарт IEEE 754), ошибки представления.

12. Способы изолирования корней нелинейных функций.

13. Сжимающие отображения.

14. Погрешность и критерии сходимости, константа Липшица.

15. Скорость сходимости итерационного алгоритма.

16. Стабильность и распространение ошибки в методах численного решения нелинейных уравнений.

17. Теория сжимающих отображений.

18. Интерполяция, экстраполяция, аппроксимация.

19. Глобальная и локальная интерполяция.

20. Ступенчатая и линейная интерполяция.

21. Глобальная и локальная интерполяция.

22. Интерполяционные полиномы.

23. Квадратичная интерполяция.

24. Интерполяция сплайнами.

25. Интерполяционный полином Лагранжа.

26. Метод кубической сплайн-интерполяции.

27. Основные операции в вычислительной линейной алгебре.

28. Эффективная реализация алгоритмов вычисления произведения матриц.

import numpy as np

29. Алгоритм Штрассена, сложность метода Штрассена.

Алгоритм Штрассена предназначен для быстрого умножения матриц, соответствует идее разделяй и властвуй.

В отличие от традиционного алгоритма умножения матриц (по формуле ), имеющего сложность , сложность алгоритм Штрассена: , что даёт выигрыш на больших плотных матрицах.

Если добавить к матрицам  и  одинаковые нулевые строки и столбцы, их произведение станет равно матрице  с теми же добавленными строками и столбцами. Поэтому можно рассматривать только матрицы размера , а другие случаи сводить к этому добавлением нулей, отчего  может увеличиться лишь вдвое.

Пусть A, B – матрицы размера . Их можно представить как блочные матрицы (матрицы из 4-х блоков) размера () из ()–матриц:

По принципу блочного умножения, матрица  выражается через их произведение:

где в правой части происходит восемь умножений матриц размера .

Для получения итоговой матрицы Штрассен предложил следующий вариант с 7 умножениями и 18 сложениями:

где:

Алгоритм Штрассена:

  1. Разбиваем матрицы  и   размера  на 4 блока размера .
  2. Вычисляем произведения по указанным выше формулам рекурсивно.

Несмотря на то, что алгоритм Штрассена является асимптотически не самым быстрым из существующих алгоритмов быстрого умножения матриц, он проще программируется и эффективнее при умножении матриц относительно малого размера, поэтому именно он чаще используется на практике. Метод Штрассена становится быстрее наивного алгоритма, если .

30. Вычисление SVD.

31. Собственные векторы, собственные значения.

Пусть A – действительная числовая квадратная матрица размером (). Ненулевой вектор  размером (), удовлетворяющий условию

 

называется собственным вектором матрицы . Число  в равенстве называется собственным значением. Говорят, что собственный вектор  соответствует (принадлежит) собственному значению .

Последнее равенство равносильно однородной относительно  системе:

Система имеет ненулевое решение для вектора  (при известном ) при условии . Это равенство есть характеристическое уравнение:

.

где  – характеристический многочлен -й степени.

Корни  характеристического уравнения являются собственными (характеристическими) значениями матрицы , а соответствующие каждому собственному значению , ненулевые векторы , удовлетворяющие системе , являются собственными векторами.

Задача линейной алгебры состоит в нахождении собственных значений и собственных векторов заданной матрицы.

32. Разложение по собственным векторам.

33. Задача Google PageRank.

34. Вычисление собственных значений с помощью характеристического многочлена.

35. Особенности степенного метода. Скорость сходимости.

36. Круги Гершгорина, теорема Гершгорина.

37. Теорема Шура.

38. Нормальные матрицы, унитарно диагонализуемые матрицы, унитарные матрицы, эрмитовы матрицы.

39. Верхне-гессенбергова форма матрицы.

40. Приведение произвольной матрицы к верхне-гессенберговой форме.

41. Отношение Релея.

42. Зазор между собственными значениями в матрице, алгоритмы со сдвигами.

43. Отражения Хаусхолдера.

Верхнегессенберговая форма:

Аналогично нижняя матрица Хессенберга:

Симметричная матрица:

Единичная матрица I ⇔ Identity Matrix ⇔ матрица с 1 по главной диагонали и нулями в остальных клетках

Эрмитово сопряженная матрица U* ⇔ Транспонированная U с элементами замененными на комплексно сопряженные им (мнимая часть с i умножается на -1)

Унитарная матрица U ⇔

Ортогональная матрица Q ⇔

Общий смысл:

Существует преобразование векторов матрицы, когда зануляются элементы под поддиагональю и собственные значения матрицы не меняются.

Зануление происходит отражением вектора (Hx). Преобразование Хаусхолдера устроено так, что, преобразуя очередной вектор (столбец) матрицы, предыдущие преобразования не портятся. Зануление под диагональю происходит в других алгоритмах (i.e. QR). Почему не занулять сразу под диагональю - QR вычислительно сложный, и эффективнее сначала получить верхнегессенберговую матрицу, потом уже получить треугольную.

При использовании отражения Хаусхолдера на симметричной матрице получается трехдиагональная (на главной диагонали, под и над ней числа, остальное нули).

Отражение Хаусхолдера - матрица H, осуществляющая отражение вектора через гиперплоскость (Hx - отраженный вектор x через гиперплоскость)

 - вектор нормали к гиперплоскости

, - подвектор,  - первый элемент подвектора, ||x|| - евклидова норма вектора без квадрата,  - базисный вектор (единица первый элемент, все остальное нули)

Отражение Хаусхолдера (H) ⇔

Свойства H:

44. Сходимость и сложность QR алгоритма.

Виды сходимости:

         - последовательность, сходящаяся к x*;

Линейная:

Квадратичная:         

Кубическая:

Сходимость алгоритма:

Линейная для исходного алгоритм

Квадратная со сдвигами с несимметричной матрицей

Кубическая со сдвигами с симметричной матрицей

Сложность алгоритма:

QR разложение плотной матрицы NxN (итерация): , итоговая сложность , k - количество итераций

QR разложение трёхдиагональной матрицы NxN (итерация): , со сдвигами число итераций O(n), итоговая сложность

Почему:

Трехдиагональная:

При QR разложении для плотной матрицы обнуляются все элементы для столбца под диагональю, для трехдиагональной это всего 1 элемент.

Сдвиги:

Сдвиги увеличивают относительную разницу между собственными значениями

QR алгоритм чувствителен к отношению собственных чисел. Чем ближе  к нулю тем быстрее сходимость.

Примеры сдвигов:

Рэлея: вычитаем последний элемент

Уилкинсона: вычисляем собственные значения матрицы 2x2 внизу справа через дискриминант, выбираем значение ближайшее к

45. Метод главных компонент и поиск сингулярных значений, прикладные аспекты.

Метод главных компонент ⇔ PCA ⇔ Principal Component Analysis - метод понижения размерности данных и удаления линейных зависимостей путем перевода данных в декартову систему координат, где базисные вектора - собственные вектора.

Реализация для собственных чисел:

1. Стандартизируем данные

2. Вычисляем ков. матрицу

3. Находим собственные значения и вектора ков. матрицы

4. Сортируем по невозростанию собственных значений. Собственные значения показывают какая у компоненты (пара собственное значение/вектор) дисперсия. Чем больше дисперсия компоненты, тем она важнее.

5. Выбираем k первых компонент, они называются главными.

6. Проецируем исходные данные в систему, где базисные вектора - главные компоненты  - собственные вектора, T - спроецированные данные

Реализация через SVD:

1. Центрируем данные

2. Вычисляем SVD

3. Находим собственные значения ков. матрицы  - сингулярное значение,  - собственное значение ковариационной матрицы; Вектора для компонент - V из разложения SVD

4. Сортируем по невозростанию собственных значений. Собственные значения показывают какая у компоненты (пара собственное значение/вектор) дисперсия. Чем больше дисперсия компоненты, тем она важнее.

5. Выбираем k первых компонент, они называются главными.

6. Проецируем исходные данные в систему, где базисные вектора - главные компоненты  - собственные вектора, T - спроецированные данные

Через SVD устойчивее, потому что не вычисляется  - если X имеет малый ранг или содержит маленькие числа значения будут сравнимы с ошибками округления

Выбор k количества компонент:

Обычно выбирают n так, чтобы во включенных компонентах было не меньше 95% дисперсии:

46. Сингулярное разложение (SVD).

 ⇔ левые сингулярные векторы

 ⇔ диагональная матрица сингулярных значений

 ⇔ правые сингулярные значения

 - ортогональные матрицы

Разложение SVD обобщает понятие собственных значений на прямоугольные матрицы, где напрямую собственные значения не найти.

Применения: Поиск информации; веб-поиск; обработка сигналов; анализ больших данных; аппроксимация матриц низкого ранга; минимизация методом наименьших квадратов; псевдообратная матрица и т.д.

Численными методами:

1. Находим

2. Находим собственные значения и вектора у   (QR-алг)

3. Находим сингулярные значения , составляем

4. Вычисляем сингулярные векторы:

V = собственные вектора

U =

Пример разложения в презентации слайд 340

47. Плотные и разреженные матрицы, способы хранения разреженных матриц.

Плотные матрицы - матрицы, где бо́льшая часть элементов ненулевая

Разреженные матрицы - матрицы, где бо́льшая часть элементов нулевая

* Нет четкого количества ненулевых элементов, что делает матрицу разрежённой

Т.к. бо́льшая часть разрежённой матрицы - нули, их можно игнорировать, тем самым сэкономив место и ускорив их последующую обработку.

Форматы хранения:

* Coordinate Format (COO)

Хранит ненулевые элементы в виде трёх массивов:

values — значения ненулевых элементов,

row_indices — номера строк,

col_indices — номера столбцов.

Плюсы: Простота добавления элементов.

Минусы: Неэффективен для арифметических операций.

* Compressed Sparse Row (CSR)

Оптимизирован для строк.

Использует три массива:

values — ненулевые элементы,

col_indices — индексы столбцов,

row_ptr — указатели на начало строк в values и col_indices.

Плюсы: Эффективен для умножения матрицы на вектор.

Минусы: Долго добавлять элементы. (Если добавить новый элемент в строку i, то все indptr[j] для j > i нужно увеличить на 1. Это O(N) операция (где N — число строк).)

* Compressed Sparse Column (CSC)

Аналог CSR, но для столбцов.

Три массива:

values — ненулевые элементы,

row_indices — индексы строк,

col_ptr — указатели на начало столбцов.

Плюсы: Эффективен для операций по столбцам.

Минусы: Долго добавлять элементы (аналогично CSR)

* Diagonal Storage (DIA)

Используется для матриц с диагональной структурой.

Хранит ненулевые элементы вдоль диагоналей.

Плюсы: Эффективен для СЛАУ с диагональным преобладанием.

Минусы: Не подходит для произвольных разреженных матриц.

* ELLPACK (ELL) (LIL в scipy)

Хранит ненулевые элементы в двумерном массиве, дополняя короткие строки.

Плюсы: Хорош для GPU-оптимизаций.

Минусы: Неэффективен при сильном разбросе длины строк.

47. Плотные и разреженные матрицы, способы хранения разреженных матриц.

48. Обыкновенные дифференциальные уравнения, численное дифференцирование. Типы ОДУ.

49. Метод прямой разности, метод обратной разности, метод центральной разности.

50. Локальная и глобальная ошибки, правило Симпсона, ошибка сокращения и ошибка округления, накопление ошибок.

51. Сетка дифференцирования.

52. Фазовые портреты, особые точки.

53. Неявные и явные методы численного дифференцирования.

54. Многошаговые методы решения обыкновенных дифференциальных уравнений.

55. Использование адаптивного шага.

56. Понятия согласованности, устойчивости, сходимости алгоритмов.

57. Строгая и нестрогая (слабая) устойчивость.

58. Детерминированный хаос, бифуркация, странные аттракторы.

Детерминированный хаос:

Примечание: Детерминированность (или определенность) - подразумевается, что в алгоритме определен каждый шаг, то есть сколько бы раз мы его не повторили, получим один и тот же результат.

Детерминированный хаос - это явление, когда динамическая система, несмотря на определенность начальных условий и детерминированных законов, является сложной, из-за чего кажется хаотичной и проблемной в предсказании поведения.

Характеристики таких систем:

        Бифуркация:

В широком смысле: Бифуркация — это качественное изменение поведения динамической системы при бесконечно малом изменении её параметров, когда ее параметры проходят через некоторые бифуркационные (критические) значения. Эти значения еще называют точками бифуркации.

В узком смысле: Бифуркация - это раздвоение.

Простыми словами, бифуркация - это моменты, когда поведение системы резко меняется. Двойной маятник неплохо это отображает: сначала вся тысяча маятников (видео со слайда 566) двигается одинаково, а потом происходит абсолютно разное движение.

Бифуркационная диаграмма - представление любого характеристического свойства решения как функции критического параметра.

Пример:

Бифуркация подразделяется на:

        Сценарий - последовательность бифуркаций, качественно меняющих свойства системы.

Странные аттракторы:

Аттрактор (или точка притяжения) - точка бифуркации, из которой все исходящие решения устойчивы (по сути - рисунок выше).

Странный аттрактор — это притягивающее множество целых неустойчивых траекторий в фазовом пространстве динамической системы. Данные аттракторы выглядят как сложные фрактальные узоры. Примеры: аттрактор Лоренца (слайды 580-581), аттрактор Рёсслера (слайд 582).

59. Амплитуда, период, частота, длин волны, дискретизация, частота дискретизации, герц, угловая частота, фаза сигнала.

Амплитуда - разница между максимальным значением и базовой линией.

Период волны - время, за которое волна проходит полный цикл.

Частота - количество волн, проходящих через фиксированное место за определенное время. Измеряется в количестве циклов за 1 секунду. Единицей является Герц.

Период = 1 / Частота

Длина волны - расстояние между двумя последовательными гребнями.

Дискретизация - как часто мы измеряем значения волны во времени.

Частота дискретизации - скорость дискретизации, измеряется в Гц.

Герц - частота колебаний за одну секунду (например если мы дискретизируем волну с частотой 2 Гц, значит, каждую секунду мы фиксируем два значения).

Угловая частота - количество циклов за секунду. Измеряется в радианах в секунду.

Фаза сигнала - это положение волны во времени относительно точки отсчета, отвечает за сдвиги волн вправо-лево. Измеряется в градусах или радианах.

60. Амплитудный спектр и частотный спектр.

Амплитудный спектр - совокупность амплитуд гармоник ряда Фурье.

Частотный спектр - совокупность частот амплитуд гармоник ряда Фурье.

61. Фильтрация сигналов.

Большинство фильтров работают не с самим сигналом, а с его спектром. Если вычислить спектр сигнала, удалить из него (или существенно уменьшить) определенные частоты, а затем выполнить обратное преобразование Фурье, то результатом будет фильтрованный сигнал. Эта процедура производится в тех случаях, когда частотный спектр помехи или шума занимают на оси частот интервал, отличный или лишь частично перекрывающийся с частотным диапазоном сигнала.

Математическая абстракция и преобразование Фурье не применимы к реальным сигналам в силу их ограниченности по времени и, следовательно, непериодичности, однако их можно рассматривать как периодические с периодом T → ∞. Тогда ω0=2π/T → 0, а спектры амплитуд и фаз становятся непрерывными (сплошными), сумма в разложении Фурье превращается в интеграл и в результате переходим к интегралу Фурье.

Разложению в ряд Фурье могут подвергаться периодические сигналы. При этом они представляются в виде суммы гармонических функций либо комплексных экспонент (e^(2πνt)) с частотами, арифметическую прогрессию. образующими. Чтобы такое разложение существовало, фрагмент сигнала длительностью в один период должен удовлетворять условиям Дирихле, а также сигнал должен быть абсолютно интегрируемым, т.е. интеграл его модуля должен быть конечной величиной.

Условия Дирихле - во фрагменте сигнала длительностью в один период:

В итоге для работы применяются дискретное или быстрое преобразование Фурье.

Прямое преобразование Фурье – это разложение сигнала на гармонические функции (в спектр).

 Обратное преобразование Фурье – это синтез сигнала по гармоникам.

Преобразование Фурье ставит в соответствие сигналу, заданному во времени, его спектральную функцию, т.е. осуществляется переход из временной области в частотную. Преобразование Фурье является взаимно-однозначным, поэтому представление сигнала в частотной области (т.е. спектральная функция) содержит столько же информации, сколько и исходный сигнал, заданный во временной области.

62. Применение преобразований Фурье с целью анализа сезонности во временных рядах.

Примечание: про само преобразование в вопросе выше.