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

Метод Якоби вычисления сингулярных чисел и векторов
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O(n^3) }[/math]

Авторы статьи: Почернина Елена (группа 601), Костюкова Светлана (группа 601)

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

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

Метод Якоби для вычисления сингулярных чисел и векторов является самым медленным из имеющихся алгоритмов поиска сингулярных чисел и векторов, но тем не менее, интерес к нему сохраняется. Для некоторых некоторых типов матриц [math]\displaystyle{ G }[/math] он способен вычислять сингулярные числа и векторы намного точнее, чем другие методы. В частности, метод Якоби вычисляет сингулярные числа матрицы [math]\displaystyle{ G }[/math] с высокой точностью, если G может быть представлена в виде [math]\displaystyle{ G = DX }[/math], где [math]\displaystyle{ D }[/math] – диагональная матрица, а [math]\displaystyle{ X }[/math] – хорошо обусловлена. В этом случае заданная матрица обрабатывается без предварительного приведения к двухдиагональному виду, в то время как другие алгоритмы включают в себя приведение матрицы к двухдиагональной форме, из-за чего и теряют все верные разряды во всех сингулярных числах, кроме старшего.

Математическое описание алгоритма

Исходные данные: матрица [math]\displaystyle{ G }[/math] (элементы [math]\displaystyle{ g_{ij}, i, j = 1, \ldots, n }[/math]).

Вычисляемые данные: матрица [math]\displaystyle{ \Sigma = diag(\sigma_{i}) }[/math], где [math]\displaystyle{ \sigma_{i} }[/math] - сингулярные числа, [math]\displaystyle{ U }[/math] - матрица левых сингулярных векторов, [math]\displaystyle{ V }[/math] - матрица правых сингулярных векторов.

Входные и выходные данные алгоритма

Входные данные: плотная матрица [math]\displaystyle{ G }[/math] (элементы [math]\displaystyle{ g_{ij} }[/math]). Дополнительные ограничения:

• [math]\displaystyle{ A= G^TG }[/math] – симметрическая матрица, т. е. [math]\displaystyle{ a_{ij}= a_{ji}, i, j = 1, \ldots, n }[/math].

Объём входных данных:

Выходные данные: матрица [math]\displaystyle{ \Sigma = diag(\sigma_{i}) }[/math], где [math]\displaystyle{ \sigma_{i} }[/math] - сингулярные числа, матрица [math]\displaystyle{ U }[/math] левых сингулярных векторов и матрица [math]\displaystyle{ V }[/math] правых сингулярных векторов.

Объём выходных данных:

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

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

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

Литература

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