Метод Якоби (вращений) для нахождения сингулярных значений неособенных матриц: различия между версиями
[досмотренная версия] | [досмотренная версия] |
Frolov (обсуждение | вклад) м |
Frolov (обсуждение | вклад) м |
||
Строка 56: | Строка 56: | ||
<math>|a_{ij}| \geq \varepsilon \sqrt{a_{ii}a_{jj}}</math>. | <math>|a_{ij}| \geq \varepsilon \sqrt{a_{ii}a_{jj}}</math>. | ||
− | В зависимости от способов перебора пар индексов матрицы вращения можно получать разные алгоритмы, реализующие метод Якоби. | + | == Варианты метода == |
+ | |||
+ | В зависимости от способов перебора пар индексов матрицы вращения можно получать разные алгоритмы, реализующие метод Якоби. Скажем, одним из них является [[Метод Якоби (вращений) для нахождения сингулярных значений с циклическим перебором|метод с циклическим перебором]] пар<ref name = "Dem"> Деммель Д. Вычислительная линейная алгебра. – 2001.</ref>, но если нужно распараллелить метод максимально, то выбор "последовательностей" пар может быть и [[Метод Якоби для нахождения сингулярных значений со специальным подбором вращений|другим]]. |
Версия 12:49, 28 декабря 2017
Авторы статьи: Ивкина Е.И., Колганова В.В.
Одним из методов нахождения сингулярного разложения матрицы является метод Якоби. Метод Якоби был предложен Карлом Густавом Якоби в 1846 году и представляет собой итерационный алгоритм вычисления собственных значений и собственных векторов симметричной матрицы. Для вычисления собственных значений необходимо неявно применить метод Якоби к симметричной матрице [math]A = G^T G[/math]. На каждом шаге вычисляется вращение Якоби [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].
Варианты метода
В зависимости от способов перебора пар индексов матрицы вращения можно получать разные алгоритмы, реализующие метод Якоби. Скажем, одним из них является метод с циклическим перебором пар[1], но если нужно распараллелить метод максимально, то выбор "последовательностей" пар может быть и другим.
- ↑ Деммель Д. Вычислительная линейная алгебра. – 2001.