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

Метод Якоби вычисления сингулярных чисел и векторов
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O(n^3) }[/math]
Объём входных данных	[math]\displaystyle{ }[/math]
Объём выходных данных	[math]\displaystyle{ }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ }[/math]
Ширина ярусно-параллельной формы	[math]\displaystyle{ }[/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] - матрица правых сингулярных векторов.

Схема реализации последовательного алгоритма

Метод можно описать следующим образом:

repeat
    for [math]\displaystyle{ j=1 }[/math] to [math]\displaystyle{ n-1 }[/math]
        for [math]\displaystyle{ k=j+1 }[/math] to [math]\displaystyle{ n }[/math]
            обратиться к процедуре One-Sided-Jacobi-Rotation[math]\displaystyle{ (G,j,k) }[/math]
        end for
    end for
пока [math]\displaystyle{ G^TG }[/math] не станет достаточно близка к диагональной матрице
Положить [math]\displaystyle{ \sigma_{i} = ||G(:,i)||_2  }[/math] (норма [math]\displaystyle{ i }[/math]-го столбца в [math]\displaystyle{ G }[/math])
Положить [math]\displaystyle{ U = [u_{1},\dots, u_{n}] }[/math], где [math]\displaystyle{ u_{i} = G(:,i)/\sigma_{i} }[/math]
Положить [math]\displaystyle{ V = J }[/math], где [math]\displaystyle{ J }[/math] - накопленное произведение вращений Якоби.

Метод Якоби для нахождения сингулярных чисел и векторов матрицы [math]\displaystyle{ G }[/math] также использует метод односторонних вращений (процедура One-Sided-Jacobi-Rotation). Алгоритм выглядит следующим образом:

proc One-Sided-Jacobi-Rotation[math]\displaystyle{ (G,j,k) }[/math]
    вычислить [math]\displaystyle{ a_{jj} = (G^TG)_{jj}, a_{jk} = (G^TG)_{jk} }[/math] и [math]\displaystyle{ a_{kk} = (G^TG)_{kk} }[/math]
    if [math]\displaystyle{ |a_{jk}| }[/math] не слишком мал
        [math]\displaystyle{ 
         \begin{align}
         \tau &= {a_{jj} - a_{kk}}/{2a_{jk}} \\
         t &= {sign(\tau)}/(|\tau| + \sqrt{1 + \tau^2}) \\
         c &= 1/(\sqrt{1 + t^2}) \\
         s &= ct \\
         G &= GR(j,k,\theta)\end{align} }[/math]
        if нужны правые сингулярные векторы 
            [math]\displaystyle{ J = JR(j,k,\theta) }[/math]
        end if
    end if

Последовательная сложность алгоритма

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

Информационный граф

Опишем граф алгоритма как аналитически, так и в виде рисунка.

Первая группа вершин расположена в двумерной области, соответствующая ей операция - вычисление [math]\displaystyle{ a_{jj}, a_{jk}, a_{kk} }[/math]. Естественно введённые координаты области таковы:

• [math]\displaystyle{ j }[/math] — меняется в диапазоне от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ n-1 }[/math], принимая все целочисленные значения;
• [math]\displaystyle{ k }[/math] — меняется в диапазоне от [math]\displaystyle{ j+1 }[/math] до [math]\displaystyle{ n }[/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] правых сингулярных векторов.

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

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

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

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

Литература

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