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-оптимизаций.

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