Сингулярное разложение (нахождение сингулярных значений и векторов)
Общая постановка задачи
Дана произвольная матрица [math]\displaystyle{ A }[/math] размера [math]\displaystyle{ m \times n }[/math], необходимо построить её разложение в виде [math]\displaystyle{ A=U\cdot S \cdot V^*, }[/math] где [math]\displaystyle{ U }[/math] и [math]\displaystyle{ V }[/math] — унитарные матрицы размера [math]\displaystyle{ m \times m }[/math] и [math]\displaystyle{ n \times n }[/math] соответственно, [math]\displaystyle{ S }[/math] — диагональная матрица с вещественными положительными числами на диагонали. Диагональные элементы матрицы [math]\displaystyle{ S }[/math] называются сингулярными числами матрицы [math]\displaystyle{ A }[/math], а столбцы матриц [math]\displaystyle{ U }[/math] и [math]\displaystyle{ V }[/math] левыми и правыми сингулярными векторами соотвтественно.
Возможные вариации постановки задачи
- Поиск всех сингулярных чисел матрицы без поиска сингулярных векторов.
- Поиск сингулярных чисел матрицы из интервала [math]\displaystyle{ (a,b) }[/math].
- Поиск сингулярных чисел матрицы из интервала [math]\displaystyle{ (a,b) }[/math] и соответствующих сингулярных векторов.
Методы решения
Общий метод сведения к спектральному разложению
Метод сведения к двухдиагональной матрице
Наиболее популярным методом вычисления сингулярных чисел и сингулярного разложения матрицы общего вида является приведение матрицы к двухдиагональному виду с дальнейшим примененеим хорошо разработанных методов вычисления сингулярного разложения двухдиагональных матриц. Таким образом метод сводится к следующим шагам:
- Вычисление разложения матрицы на двухдиагональную и унитарные [math]\displaystyle{ A=U_1TV_1^*. }[/math] (Если нет необходимости вычислять сингулярные вектора, можно ограничиться вычислением двухдиагональной матрицы [math]\displaystyle{ }[/math].)
- Вычисление SVD разложения матрицы [math]\displaystyle{ T=U_2SV_2^*. }[/math]
- Вычисление (при необходимости) [math]\displaystyle{ U=U_1U_2, V=V_1V_2. }[/math] (Умножение матриц.)
Методы вычисления сингулярного разложения двухдиагональных матриц
QR-итерация и её варианты
Особенности
- Быстрый метод для матриц порядка примерно 25 и меньше
- Высокая точность вычисления сингулярных чисел