Сингулярное разложение (нахождение сингулярных значений и векторов)

Основные авторы описания: А.Ю.Чернявский

1 Общая постановка задачи

Дана произвольная матрица $A$ размера $m \times n$, необходимо построить её разложение в виде $A=U S V^*,$ где $U$ и $V$ — унитарные матрицы размера $m \times m$ и $n \times n$ соответственно, $S$ — диагональная матрица с вещественными положительными числами на диагонали. Диагональные элементы матрицы $S$ называются сингулярными числами матрицы $A$, а столбцы матриц $U$ и $V$ левыми и правыми сингулярными векторами соотвтественно.

1.1 Возможные вариации постановки задачи

• Поиск всех сингулярных чисел матрицы без поиска сингулярных векторов.
• Поиск сингулярных чисел матрицы из интервала $(a,b)$.
• Поиск сингулярных чисел матрицы из интервала $(a,b)$ и соответствующих сингулярных векторов.

2 Методы решения

2.2 Метод сведения к двухдиагональной матрице

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

1. Вычисление разложения матрицы на двухдиагональную и унитарные $A=U_1TV_1^*.$ (Если нет необходимости вычислять сингулярные вектора, можно ограничиться вычислением двухдиагональной матрицы .)
2. Вычисление SVD разложения матрицы $T=U_2SV_2^*.$
3. Вычисление (при необходимости) $U=U_1U_2, V=V_1V_2.$ (Умножение матриц.)

2.3 Методы вычисления сингулярного разложения двухдиагональных матриц

2.3.1 QR-итерация и её варианты

2.3.1.1 Особенности

• Быстрый метод для матриц порядка примерно 25 и меньше.
• Высокая относительная точность вычисления сингулярных чисел.

2.3.1.2 Алгоритмы

Алгоритм dqds нахождения сингулярных чисел двухдиагональной матрицы

Итерация алгоритма dqds

2.3.2 Метод "Разделяй-и-властвуй"

2.3.2.1 Особенности

• Быстрый метод для произвольных матриц размерности больше 25.
• Возможна низкая относительная точность вычисления сингулярных значений.