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

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

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

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

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

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

[math]\tau = (a_{jj} - a_{kk})/(2 \cdot a_{jk})[/math]

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

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

[math]s = c \cdot t[/math], где [math]s = sin\theta[/math]

[math]G = G \cdot R(j,k,\theta)[/math]

[math]J = J \cdot R(j,k,\theta)[/math]

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

                                                                        [math]j[/math]                             [math]k[/math]            

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

Одностороннее вращение Якоби в координатной плоскости [math]i, j[/math] вычисляется в том случае, если элемент [math]a_{ij}[/math] удовлетворяет условию: [math]|a_{ij}| \geq \varepsilon \sqrt{a_{ii}a_{jj}}[/math].

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

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