Сингулярное разложение (нахождение сингулярных значений и векторов): различия между версиями
ASA (обсуждение | вклад) |
|||
(не показано 8 промежуточных версий 6 участников) | |||
Строка 1: | Строка 1: | ||
+ | {{level-p}} | ||
+ | |||
+ | Основные авторы описания: [[Участник:Chernyavskiy|А.Ю.Чернявский]] | ||
+ | |||
= Общая постановка задачи = | = Общая постановка задачи = | ||
− | Дана произвольная матрица <math>A</math> размера <math>m \times n</math>, необходимо построить её разложение в виде <math>A=U | + | Дана произвольная матрица <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> левыми и правыми сингулярными векторами соотвтественно. |
== Возможные вариации постановки задачи == | == Возможные вариации постановки задачи == | ||
* Поиск всех сингулярных чисел матрицы без поиска сингулярных векторов. | * Поиск всех сингулярных чисел матрицы без поиска сингулярных векторов. | ||
Строка 25: | Строка 29: | ||
* Высокая относительная точность вычисления сингулярных чисел. | * Высокая относительная точность вычисления сингулярных чисел. | ||
==== Алгоритмы ==== | ==== Алгоритмы ==== | ||
− | [[Алгоритм dqds | + | [[Алгоритм dqds нахождения сингулярных чисел двухдиагональной матрицы]] |
+ | |||
+ | :[[Итерация алгоритма dqds]] | ||
=== Метод "Разделяй-и-властвуй" === | === Метод "Разделяй-и-властвуй" === | ||
==== Особенности ==== | ==== Особенности ==== | ||
− | * Быстрый метод для произвольных матриц | + | * Быстрый метод для произвольных матриц размерности больше 25. |
* Возможна низкая относительная точность вычисления сингулярных значений. | * Возможна низкая относительная точность вычисления сингулярных значений. | ||
+ | |||
==== Алгоритмы ==== | ==== Алгоритмы ==== | ||
Строка 41: | Строка 48: | ||
==== Особенности ==== | ==== Особенности ==== | ||
==== Алгоритмы ==== | ==== Алгоритмы ==== | ||
+ | |||
+ | |||
+ | [[Категория:Начатые статьи]] | ||
+ | [[Категория:Разложения матриц]] | ||
+ | |||
+ | [[en:Singular value decomposition (finding singular values and singular vectors)]] |
Текущая версия на 15:17, 14 марта 2018
Основные авторы описания: А.Ю.Чернявский
Содержание
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 Метод сведения к двухдиагональной матрице
Наиболее популярным методом вычисления сингулярных чисел и сингулярного разложения матрицы общего вида является приведение матрицы к двухдиагональному виду с дальнейшим примененеим хорошо разработанных методов вычисления сингулярного разложения двухдиагональных матриц. Таким образом метод сводится к следующим шагам:
- Вычисление разложения матрицы на двухдиагональную и унитарные [math]A=U_1TV_1^*.[/math] (Если нет необходимости вычислять сингулярные вектора, можно ограничиться вычислением двухдиагональной матрицы [math][/math].)
- Вычисление SVD разложения матрицы [math]T=U_2SV_2^*.[/math]
- Вычисление (при необходимости) [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 нахождения сингулярных чисел двухдиагональной матрицы
2.3.2 Метод "Разделяй-и-властвуй"
2.3.2.1 Особенности
- Быстрый метод для произвольных матриц размерности больше 25.
- Возможна низкая относительная точность вычисления сингулярных значений.