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

Метод Якоби вычисления сингулярных чисел и векторов
Последовательный алгоритм
Последовательная сложность
Объём входных данных
Объём выходных данных
Параллельный алгоритм
Высота ярусно-параллельной формы
Ширина ярусно-параллельной формы

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

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

Сингулярное разложение было первоначально разработано в дифференциальной геометрии при изучении свойств билинейных форм учеными Эудженио Бельтрами и Камилем Жорданом независимо в 1873 и 1874 годах соответственно. Первое доказательство сингулярного разложения для прямоугольных и комплексных матриц было осуществлено математиками Карлом Эскартом и Гэйлом Янгом в 1936 году.

Сингулярное разложение (Singular Values Decomposition, SVD) является удобным методом при работе с матрицами. Cингулярное разложение показывает геометрическую структуру матрицы и позволяет наглядно представить имеющиеся данные. Сингулярное разложение используется при решении самых разных задач — от приближения методом наименьших квадратов и решения систем уравнений до сжатия и распознавания изображений. Используются разные свойства сингулярного разложения, например, способность показывать ранг матрицы и приближать матрицы данного ранга. Так как вычисления ранга матрицы — задача, которая встречается очень часто, то сингулярное разложение является довольно популярным методом.

Сингулярным разложением матрицы $G (n \times n)$ называется разложение вида $G = U \Sigma V^T$ , где $U, V$ - унитарные матрицы $n \times n$, $\Sigma$ - диагональная матрица $n \times n$ с вещественными положительными числами на главной диагонали. Столбцы матриц $U, V$ называются соответственно левыми и правыми сингулярными векторами, а значения на диагонали матрицы $\Sigma$ - сингулярными значениями матрицы $G$.

Одним из методов нахождения сингулярного разложения матрицы является метод Якоби. Метод Якоби был предложен Карлом Густавом Якоби Якоби в 1846 году и представляет собой итерационный алгоритм вычисления собственных значений и собственных векторов симметричной матрицы. Для вычисления собственных значений необходимо неявно применить метод Якоби к симметричной матрице $A = G^T G$. На каждом шаге вычисляется вращение Якоби $J$, с помощью которого матрица $G^TG$ неявно пересчитывется в $J^TG^TGJ$; вращение выбрано так, чтобы пара внедиагональных элементов из $G^TG$ обратилась в нули в матрице $J^TG^TGJ$. При этом ни $G^TG$, ни $J^TG^TGJ$ не вычисляются в явном виде; вместо них вычисляется матрица $GJ$. Поэтому алгоритм называется методом односторонних вращений.

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

Исходные данные: Матрица $G$ размера $(n \times n)$ над полем вещественных или комплексных чисел.

Вычисляемые данные:

• $\sigma_i$ - сингулярные числа матрицы $G$,
• $U$ - матрица левых сингулярных векторов,
• $V$ - матрица правых сингулярных векторов.

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

Шаг 1 Вычисляем матрицу $G'$ применением одностороннего вращения Якоби к исходной матрице $G$.

Шаг 2 Повторяем Шаг 1 пока матрица $G'^TG$ не станет достаточно близка к диагональной.

Шаг 3 Вычисляем по полученной матрице $G'$ сингулярные числа $\sigma_i$ и сингулярные векторы $U, V$.

Основные формулы метода:

$\sigma_i = \parallel G'(:,i)\parallel_2$ (2-я норма $i$-го столбца в $G'$).

$U = [u_1, \dots, u_n]$, где $u_i = G'(:,i)/\sigma_i$.

$V = J$, где $J$ - накопленное произведение вращений Якоби.

Основные формулы процедуры одностороннего вращения Якоби:

Пусть $a_{ij}$ - элемент, расположенный в $i$-ой строке и $j$-ом столбце матрицы $G^TG$.

$\tau = (a_{jj} - a_{kk})/(2 \cdot a_{jk})$

$t = sign(\tau)/(|\tau|+\sqrt{1+\tau^2})$

$c = 1/\sqrt{1+t^2}$, где $c = cos\theta$

$s = c \cdot t$, где $s = sin\theta$

$J = J \cdot R(j,k,\theta)$

Здесь $R(j,k,\theta)$ - матрица вращений Якоби, которая имеет следующий вид:

                                                                                 $\begin{matrix} & & & & j & & k & & & \\ \end{matrix}$

$R(j,k,\theta) = \begin{matrix} \\ \\ \\ j \\ \\ k \\ \\ \\ \\ \end{matrix}$ $\begin{pmatrix} & 1 & & & & & & & & \\ & & 1 & & & & & & & \\ & & & \ddots & & & & & & \\ & & & & \cos(\theta) & & -\sin(\theta) & & & \\ & & & & & \ddots & & & & \\ & & & & \sin(\theta) & & \cos(\theta) & & & \\ & & & & & & & \ddots & & \\ & & & & & & & & 1 & \\ & & & & & & & & & 1 \\ \end{pmatrix}$

Одностороннее вращение Якоби в координатной плоскости $i, j$ вычисляется в том случае, если элемент $a_{ij}$ удовлетворяет условию: $|a_{ij}| \geq \epsilon \sqrt{a_{ii}a_{jj}}$, где $\epsilon$ -

Критерий останова:

Для проверки близости матрицы $G'^TG$ к диагональной используется следующее неравенство:

1.3 Вычислительное ядро алгоритма

Вычислительное ядро метода Якоби вычисления сингулярных чисел и векторов можно составить из множественных вызовов процедуры одностороннего вращения Якоби One-Sided-Jacobi-Rotation(G,j,k).

Основными операциями процедуры One-Sided-Jacobi-Rotation(G,j,k) являются:

• Вычисление элементов $a_{jj}, a_{jk}, a_{kk}$, где $a_{ij} = (G^TG)_{ij}$.
• Вычисление матрицы вращения Якоби $R(j,k,\theta)$.
• Применение вращения Якоби к матрицам $G$ и $J$.

1.4 Макроструктура алгоритма

Алгоритм вычисления сингулярных чисел и векторов Якоби состоит из множественных обращений к процедуре одностороннего вращения Якоби. На каждой итерации цикла происходит вызов процедуры One-Sided-Jacobi-Rotation(G, j, k) для всех $j \in [1, n-1]$ и $k \in [j+1, n]$. Таким образом, на каждой итерации цикла процедура One-Sided-Jacobi-Rotation(G, j, k) вызывается для всех наддиагональных элементом матрицы $G^TG$, то есть всего $\frac{n(n-1)}{2}$ раз. Количество итераций цикла непосредственно зависит от матрицы $G$, выход из цикла происходит по достижении критерия останова (описан в разделе "Математическое описание алгоритма".)

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

Схему реализации последовательного алгоритма можно описать следующиv псевдокодом:

repeat
  for  [math]j=1[/math] to [math]n-1[/math]
    for [math]k=j+1[/math] to [math]n[/math]
      One-Sided-Jacobi-Rotation(G, j, k)
    end for
  end for
пока [math]G^TG[/math] не станет достаточно близка к диагональной матрице.
Положить [math]\sigma_i = \parallel G'(:,i)\parallel_2[/math] (2-я норма [math]i[/math]-го столбца в [math]G'[/math]).
Положить [math]U = [u_1, \dots, u_n][/math], где [math] u_i = G'(:,i)/\sigma_i[/math].
Положить [math]V = J[/math], где [math]J[/math] - накопленное произведение вращений Якоби.

Процедура One-Sided-Jacobi-Rotation(G, j, k):

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

3 Литература

<references \>