Метод Якоби (вращений) для нахождения сингулярных значений неособенных матриц: различия между версиями
[досмотренная версия] | [досмотренная версия] |
Frolov (обсуждение | вклад) (Новая страница: «{{level-m}}») |
Frolov (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
{{level-m}} | {{level-m}} | ||
+ | |||
+ | Авторы статьи: [[Участник: Ekaterina.ivkina| Ивкина Е.И.]], [[Участник: Victoria| Колганова В.В.]] | ||
+ | |||
+ | Одним из методов нахождения [[Сингулярное разложение (нахождение сингулярных значений и векторов)|сингулярного разложения матрицы]] является '''метод Якоби'''. Метод Якоби был предложен Карлом Густавом Якоби в 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>. |
Версия 12:39, 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].