Участник:Davletshuna Alexandra/Метод Якоби вычисления сингулярных чисел и векторов

Метод Якоби вычисления сингулярных чисел и векторов
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O(n^3) }[/math]
Объём входных данных	[math]\displaystyle{ \frac{n (n + 1)}{2} }[/math]
Объём выходных данных	[math]\displaystyle{ \frac{n (n + 1)}{2} }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ }[/math]
Ширина ярусно-параллельной формы	[math]\displaystyle{ }[/math]

Авторы статьи: Давлетшина Александра (группа 619), Зайцева Александра (группа 601)

Свойства и структура алгоритма

Общее описание алгоритма

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

• левые сингулярные векторы матрицы А — это собственные векторы матрицы [math]\displaystyle{ AA^* }[/math];

• правые сингулярные векторы матрицы A — это собственные векторы матрицы [math]\displaystyle{ A^*A }[/math].

Геометрическая интерпретация сингулярного разложения заключается в следующем факте из геометрии: Образом любого линейного преобразования, заданного с помощью матрицы [math]\displaystyle{ m }[/math]x[math]\displaystyle{ n }[/math], примененного к единичной сфере является гиперэллипсоид.

Из многочисленных разложений матриц, наиболее удобным является сингулярное разложение матрицы в виде: [math]\displaystyle{ A=U\Sigma V^* }[/math], где [math]\displaystyle{ U, V }[/math] – унитарные матрицы, а [math]\displaystyle{ \Sigma }[/math] – диагональная матрица с вещественными положительными числами на диагонали .

Диагональные элементы матрицы [math]\displaystyle{ \Sigma }[/math] называются сингулярными числами матрицы [math]\displaystyle{ A }[/math], а столбцы матриц [math]\displaystyle{ U,V }[/math] левыми и правыми сингулярными векторами соответственно.

Алгоритм Якоби сингулярного разложения матрицы был предложен одним из первых в 1846 году. Он приводит прямоугольную матрицу к диагональной матрице с помощью последовательности элементарных вращений. Метод может найти все сингулярные значения с очень высокой точностью. Однако его производительность является довольно низкой, в сравнении с конкурирующими методами.

Неявный метод Якоби математически эквивалентен применению метода Якоби вычисления собственных значений к матрице [math]\displaystyle{ A = G^TG }[/math]. Это значит, что на каждом шаге вычисляется вращение Якоби [math]\displaystyle{ J }[/math], с помощью которого матрица [math]\displaystyle{ G^TG }[/math] неявно пересчитывется в [math]\displaystyle{ J^TG^TGJ }[/math]; вращение выбрано так, чтобы пара внедиагональных элементов из [math]\displaystyle{ G^TG }[/math] обратилась в нули в матрице [math]\displaystyle{ J^TG^TGJ }[/math]. При этом ни [math]\displaystyle{ G^TG }[/math], ни [math]\displaystyle{ J^TG^TGJ }[/math] не вычисляются в явном виде; вместо них вычисляется матрица [math]\displaystyle{ GJ }[/math]. Поэтому алгоритм называется методом односторонних вращений.

Программная реализация алгоритма

Существующие реализации алгоритма

Метод Якоби нахождения сингулярных значений и векторов реализован в пакете LAPACK. В связи с тем, что алгоритм считается медленным, он не включен во многие известные пакеты.

Литература

1. Дж. Деммель Вычислительная линейная алгебра. Изд. Мир, 2001.