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

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

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

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

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

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

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

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

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

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

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

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

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

                                                                        [math]\displaystyle{ j }[/math]                             [math]\displaystyle{ k }[/math]            

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

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

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

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