Уровень задачи

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

Материал из Алговики
Перейти к: навигация, поиск


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

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

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

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

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

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

2.1 Общий метод сведения к спектральному разложению

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

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

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

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.
  • Возможна низкая относительная точность вычисления сингулярных значений.

2.3.2.2 Алгоритмы

2.3.3 Метод бисекции и обратной итерации

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

2.3.3.2 Алгоритмы

2.4 Метод Якоби

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

2.4.2 Алгоритмы