Метод Якоби (вращений) для нахождения сингулярных значений неособенных матриц

Авторы статьи: Ивкина Е.И., Колганова В.В., общая редакция и правка страницы - А.В.Фролов.

Одним из методов нахождения сингулярного разложения матрицы является метод Якоби. Метод Якоби был предложен Карлом Густавом Якоби в 1846 году и представляет собой итерационный алгоритм вычисления собственных значений и собственных векторов симметричной матрицы. Для вычисления собственных значений необходимо неявно применить метод Якоби к симметричной матрице $A = G^T G$.

1 Основные формулы

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

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

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

$t = sign(\tau)/(|\tau|+\sqrt{1+\tau^2})$. При $\tau = 0$ считаем $sign(\tau) = 1$, то есть $\theta = \frac{\pi}{4}.$

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

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

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

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

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

                                                                        $j$                             $k$            

$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 \varepsilon \sqrt{a_{ii}a_{jj}}$.

2 Варианты метода

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