Вращение Гивенса

В числовой линейной алгебры , A вращения Гивенс является вращение в плоскости , натянутой на двух осей координат. Вращения Гивенса названы в честь Уоллеса Гивенса , который представил их численным аналитикам в 1950-х годах, когда работал в Аргоннской национальной лаборатории .

Матричное представление [ править ]

Вращение Гивенса представлено матрицей вида

${\displaystyle G(i,j,\theta )={\begin{bmatrix}1&\cdots &0&\cdots &0&\cdots &0\\\vdots &\ddots &\vdots &&\vdots &&\vdots \\0&\cdots &c&\cdots &-s&\cdots &0\\\vdots &&\vdots &\ddots &\vdots &&\vdots \\0&\cdots &s&\cdots &c&\cdots &0\\\vdots &&\vdots &&\vdots &\ddots &\vdots \\0&\cdots &0&\cdots &0&\cdots &1\end{bmatrix}},}$

где c = cos  θ и s = sin  θ появляются на пересечении i- й и j- й строк и столбцов. То есть для фиксированного i > j ненулевые элементы матрицы Гивенса задаются следующим образом:

${\displaystyle {\begin{aligned}g_{kk}&{}=1\qquad {\text{for}}\ k\neq i,\,j\\g_{kk}&{}=c\qquad {\text{for}}\ k=i,\,j\\g_{ji}&{}=-g_{ij}=-s\\\end{aligned}}}$

Продукт G ( я ,  J ,  θ ) х представляет собой вращение против часовой стрелки от вектора х в ( я ,  J ) плоскости & thetas радианах, отсюда и название Гивенса вращение.

Основное использование вращений Гивенса в числовой линейной алгебре состоит в том, чтобы ввести нули ^{[ требуется пояснение ]} в векторы или матрицы. Этот эффект можно, например, использовать для вычисления QR-разложения матрицы. Одно преимущество перед преобразованиями Хаусхолдера состоит в том, что их можно легко распараллелить, а другое состоит в том, что часто для очень разреженных матриц они имеют меньшее количество операций.

Стабильный расчет [ править ]

Когда матрица Гивенс вращения, G ( я ,  J ,  θ ) , умножает другую матрицу, , с левой стороны , G A , только строки я и J из А страдают. Таким образом, мы ограничимся следующей задачей против часовой стрелки. Даны a и b , найти c = cos  θ и s = sin  θ такие, что

${\displaystyle {\begin{bmatrix}c&-s\\s&c\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}={\begin{bmatrix}r\\0\end{bmatrix}},}$

где - длина вектора . Явный расчет θ редко требуется или желателен. Вместо этого мы ищем напрямую c и s . Очевидным решением было бы${\displaystyle r={\sqrt {a^{2}+b^{2}}}}$${\displaystyle (a,b)}$

${\displaystyle {\begin{aligned}c&{}\leftarrow a/r\\s&{}\leftarrow -b/r.\end{aligned}}}$^[1]

Однако вычисление r может быть переполнено или опустошено. Альтернативная формулировка, позволяющая избежать этой проблемы ( Голуб и Ван Лоан, 1996 , §5.1.8), реализована как функция гипотез во многих языках программирования.

Следующий код на Фортране представляет собой минималистичную реализацию ротации Гивенса для действительных чисел. Если входные значения «a» или «b» часто равны нулю, код может быть оптимизирован для обработки этих случаев, как представлено здесь .

подпрограмма givens_rotation ( a ,  b ,  c ,  s ,  r )реальный a ,  b ,  c ,  s ,  r реальный h ,  dif  ( b . ne . 0.0 ),  то h = гипотеза ( a , b ) d = 1.0 / h c = abs ( a ) * d s = sign ( d , a ) * b r = sign ( 1.0 , a ) * h иначе c = 1.0 s = 0.0 r =                                   конец , есливозвратный конец

Кроме того, как обнаружил Эдвард Андерсон при улучшении LAPACK , ранее игнорировавшимся численным соображением является непрерывность. Для этого требуется, чтобы r было положительным. ^[2] Следующий код MATLAB / GNU Octave иллюстрирует алгоритм.

функция [c, s, r] = givens_rotation ( a, b )  если b == 0 ;    c = знак ( а );   если ( c == 0 );    c = 1,0 ; % В отличие от других языков, знаковая функция MatLab возвращает 0 на входе 0.    конец ; s = 0 ;   г = абс ( а );   elseif a == 0 ;    c = 0 ;   s = знак ( б );   г = абс ( б );   иначе абс ( а ) > абс ( б );    t = b / a ;     u = знак ( а ) * sqrt ( 1 + t * t );         c = 1 / u ;     s = c * t ;     г = а * и ;     еще t = a / b ;     u = знак ( b ) * sqrt ( 1 + t * t );         s = 1 / u ;     c = s * t ;     г = Ь * и ;     конецконец

Функция IEEE 754 copysign (x, y) обеспечивает безопасный и дешевый способ скопировать знак y в x . Если это недоступно, | x | ⋅sgn ( y ) , использующий функции abs и sgn , является альтернативой, как было сделано выше.

Треугольная форма [ править ]

Учитывая следующую матрицу 3 × 3 :

${\displaystyle A_{1}={\begin{bmatrix}6&5&0\\5&1&4\\0&4&3\\\end{bmatrix}},}$

выполнить две итерации вращения Гивенса (обратите внимание, что используемый здесь алгоритм вращения Гивенса немного отличается от приведенного выше), чтобы получить верхнюю треугольную матрицу для вычисления QR-разложения .

Чтобы сформировать желаемую матрицу, мы должны обнулить элементы (2, 1) и (3, 2) . Сначала мы обнуляем элемент (2, 1) . Используя матрицу вращения:

${\displaystyle G_{1}={\begin{bmatrix}c&-s&0\\s&c&0\\0&0&1\\\end{bmatrix}}.}$

У нас есть следующее матричное умножение:

${\displaystyle {\begin{aligned}G_{1}A_{1}&{}=A_{2}\\&{}={\begin{bmatrix}c&-s&0\\s&c&0\\0&0&1\\\end{bmatrix}}{\begin{bmatrix}6&5&0\\5&1&4\\0&4&3\\\end{bmatrix}},\end{aligned}}}$

где

${\displaystyle {\begin{aligned}r&{}={\sqrt {6^{2}+5^{2}}}\approx 7.8102\\c&{}=6/r\approx 0.7682\\s&{}=-5/r\approx -0.6402.\end{aligned}}}$

Подставляя эти значения для c и s и выполняя матричное умножение выше, получаем A ₂ :

${\displaystyle A_{2}\approx {\begin{bmatrix}7.8102&4.4813&2.5607\\0&-2.4327&3.0729\\0&4&3\\\end{bmatrix}}}$

Теперь нам нужно обнулить элемент (3, 2), чтобы завершить процесс. Используя ту же идею, что и раньше, у нас есть матрица вращения:

${\displaystyle G_{2}={\begin{bmatrix}1&0&0\\0&c&-s\\0&s&c\\\end{bmatrix}}}$

Нам представлено следующее умножение матриц:

${\displaystyle {\begin{aligned}G_{2}A_{2}&{}=A_{3}\\&{}\approx {\begin{bmatrix}1&0&0\\0&c&-s\\0&s&c\\\end{bmatrix}}{\begin{bmatrix}7.8102&4.4813&2.5607\\0&-2.4327&3.0729\\0&4&3\\\end{bmatrix}},\end{aligned}}}$

где

${\displaystyle {\begin{aligned}r&{}\approx {\sqrt {(-2.4327)^{2}+4^{2}}}\approx 4.6817\\c&{}\approx -2.4327/r\approx -0.5196\\s&{}\approx -4/r\approx -0.8544.\end{aligned}}}$

Подставляя эти значения для c и s и выполняя умножение, мы получаем A ₃ :

${\displaystyle A_{3}\approx {\begin{bmatrix}7.8102&4.4813&2.5607\\0&4.6817&0.9664\\0&0&-4.1843\\\end{bmatrix}}.}$

Эта новая матрица A ₃ является верхней треугольной матрицей, необходимой для выполнения итерации QR-разложения . Q теперь формируется с использованием транспонирования матриц вращения следующим образом:

${\displaystyle Q=G_{1}^{T}\,G_{2}^{T}.}$

Выполнение этого матричного умножения дает:

${\displaystyle Q\approx {\begin{bmatrix}0.7682&0.3327&0.5470\\0.6402&-0.3992&-0.6564\\0&0.8544&-0.5196\\\end{bmatrix}}.}$

Это завершает две итерации вращения Гивенса, и теперь можно выполнить расчет QR-разложения .

Вращения Гивенса в алгебрах Клиффорда [ править ]

В алгебрах Клиффорда и ее дочерних структурах, таких как геометрическая алгебра, вращения представлены бивекторами . Повороты Гивенса представлены внешним произведением базисных векторов. Для любой пары базисных векторов бивекторами поворотов Гивенса являются:${\displaystyle \mathbf {e} _{i},\mathbf {e} _{j}}$

${\displaystyle B_{ij}=\mathbf {e} _{i}\wedge \mathbf {e} _{j}.}$

Их действие на любой вектор записывается:

${\displaystyle v=e^{-(\theta /2)(\mathbf {e} _{i}\wedge \mathbf {e} _{j})}ue^{(\theta /2)(\mathbf {e} _{i}\wedge \mathbf {e} _{j})},}$

где

${\displaystyle e^{(\theta /2)(\mathbf {e} _{i}\wedge \mathbf {e} _{j})}=\cos(\theta /2)+\sin(\theta /2)\mathbf {e} _{i}\wedge \mathbf {e} _{j}.}$

Измерение 3 [ править ]

В измерении 3 есть три вращения Гивенса:

${\displaystyle R_{X}(\theta )={\begin{bmatrix}1&0&0\\0&\cos \theta &-\sin \theta \\0&\sin \theta &\cos \theta \end{bmatrix}}.}$

${\displaystyle {\begin{aligned}\\R_{Y}(\theta )={\begin{bmatrix}\cos \theta &0&-\sin \theta \\0&1&0\\\sin \theta &0&\cos \theta \end{bmatrix}}\end{aligned}}}$^{[примечание 1]}

${\displaystyle {\begin{aligned}\\R_{Z}(\theta )={\begin{bmatrix}\cos \theta &-\sin \theta &0\\\sin \theta &\cos \theta &0\\0&0&1\end{bmatrix}}\end{aligned}}}$

Учитывая, что они являются эндоморфизмами, их можно составлять друг с другом сколько угодно раз, имея в виду, что g  ∘  f ≠ f  ∘  g .

Эти три составленных вращения Гивенса могут генерировать любую матрицу вращения в соответствии с теоремой Дэвенпорта о цепном вращении . Это означает , что они могут трансформировать в стандартном базис пространства для любого другого кадра в пространстве. ^{[ требуется разъяснение ]}

Когда повороты выполняются в правильном порядке, значения углов поворота конечного кадра будут равны углам Эйлера конечного кадра в соответствующем соглашении. Например, оператор преобразует основу пространства в кадр с углами крена, тангажа и рыскания в соответствии с соглашением Тейта-Брайана z - x - y (соглашение, согласно которому линия узлов перпендикулярна осям z и Y , также называемая Y - X ′ - Z ″ ).${\displaystyle R=R_{Y}(\theta _{3}).R_{X}(\theta _{2}).R_{Z}(\theta _{1})}$${\displaystyle YPR=(\theta _{3},\theta _{2},\theta _{1})}$

По той же причине любую матрицу вращения в 3D можно разложить на произведение трех из этих операторов вращения .

Смысл композиции двух поворотов  Гивена g ∘  f - это оператор, который преобразует векторы сначала на f, а затем на g , являющиеся вращениями f и g вокруг одной оси базиса пространства. Это похоже на эквивалентность внешнего вращения для углов Эйлера.

Таблица составленных поворотов [ править ]

В следующей таблице показаны три поворота Гивенса, эквивалентные различным соглашениям об углах Эйлера, с использованием внешней композиции (композиции вращений вокруг базисных осей) активных вращений и правила правой руки для положительного знака углов.

Обозначения были упрощены таким образом, что c ₁ означает cos  θ _1, а s ₂ означает sin  θ ₂ ) . Субиндексы углов - это порядок, в котором они применяются с использованием внешнего состава (1 для собственного вращения, 2 для нутации, 3 для прецессии).

Поскольку повороты применяются только в порядке, обратном порядку поворотов в таблице углов Эйлера , эта таблица такая же, но поменять местами индексы 1 и 3 в углах, связанных с соответствующей записью. Запись типа zxy означает применение сначала поворота по оси y , затем по оси x и, наконец , по оси z по базовым осям.

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

xzx	${\displaystyle {\begin{bmatrix}c_{2}&-c_{1}s_{2}&s_{1}s_{2}\\c_{3}s_{2}&c_{3}c_{2}c_{1}-s_{3}s_{1}&-c_{2}c_{3}s_{1}-c_{1}s_{3}\\s_{2}s_{3}&c_{3}s_{1}+c_{1}c_{2}s_{3}&c_{3}c_{1}-c_{2}s_{3}s_{1}\end{bmatrix}}}$	xzy	${\displaystyle {\begin{bmatrix}c_{2}c_{3}&-c_{3}s_{2}c_{1}+s_{3}s_{1}&c_{3}s_{2}s_{1}+s_{3}c_{1}\\s_{2}&c_{1}c_{2}&-c_{2}s_{1}\\-s_{3}c_{2}&s_{3}s_{2}c_{1}+c_{3}s_{1}&-s_{3}s_{2}s_{1}+c_{3}c_{1}\end{bmatrix}}}$
xyx	${\displaystyle {\begin{bmatrix}c_{2}&s_{1}s_{2}&c_{1}s_{2}\\s_{2}s_{3}&c_{3}c_{1}-c_{2}s_{3}s_{1}&-c_{3}s_{1}-c_{1}c_{2}s_{3}\\-c_{3}s_{2}&c_{3}c_{2}s_{1}+c_{1}s_{3}&c_{3}c_{2}c_{1}-s_{3}s_{1}\end{bmatrix}}}$	xyz	${\displaystyle {\begin{bmatrix}c_{3}c_{2}&-s_{3}c_{1}+c_{3}s_{2}s_{1}&s_{3}s_{1}+c_{3}s_{2}c_{1}\\s_{3}c_{2}&c_{3}c_{1}+s_{3}s_{2}s_{1}&-c_{3}s_{1}+s_{3}s_{2}c_{1}\\-s_{2}&c_{2}s_{1}&c_{2}c_{1}\end{bmatrix}}}$
yxy	${\displaystyle {\begin{bmatrix}c_{3}c_{1}-c_{2}s_{3}s_{1}&s_{2}s_{3}&c_{3}s_{1}+s_{3}c_{2}c_{1}\\s_{1}s_{2}&c_{2}&-c_{1}s_{2}\\-c_{2}c_{3}s_{1}-c_{1}s_{3}&c_{3}s_{2}&c_{3}c_{2}c_{1}-s_{3}s_{1}\end{bmatrix}}}$	yxz	${\displaystyle {\begin{bmatrix}c_{3}c_{1}-s_{3}s_{2}s_{1}&-s_{3}c_{2}&c_{3}s_{1}+s_{3}s_{2}c_{1}\\s_{3}c_{1}+c_{3}s_{2}s_{1}&c_{3}c_{2}&s_{3}s_{1}-c_{3}s_{2}c_{1}\\-c_{2}s_{1}&s_{2}&c_{2}c_{1}\end{bmatrix}}}$
yzy	${\displaystyle {\begin{bmatrix}c_{3}c_{2}c_{1}-s_{3}s_{1}&-c_{3}s_{2}&c_{2}c_{3}s_{1}+c_{1}s_{3}\\c_{1}s_{2}&c_{2}&s_{1}s_{2}\\-c_{3}s_{1}-c_{1}c_{2}s_{3}&s_{2}s_{3}&c_{3}c_{1}-c_{2}s_{3}s_{1}\end{bmatrix}}}$	yzx	${\displaystyle {\begin{bmatrix}c_{2}c_{1}&-s_{2}&c_{2}s_{1}\\c_{3}s_{2}c_{1}+s_{3}s_{1}&c_{3}c_{2}&c_{3}s_{2}s_{1}-s_{3}c_{1}\\s_{3}s_{2}c_{1}-c_{3}s_{1}&s_{3}c_{2}&s_{3}s_{2}s_{1}+c_{3}c_{1}\end{bmatrix}}}$
зыз	${\displaystyle {\begin{bmatrix}c_{3}c_{2}c_{1}-s_{3}s_{1}&-c_{2}s_{1}c_{3}-c_{1}s_{3}&c_{3}s_{2}\\c_{3}s_{1}+c_{1}c_{2}s_{3}&c_{3}c_{1}-c_{2}s_{3}s_{1}&s_{2}s_{3}\\-c_{1}s_{2}&s_{1}s_{2}&c_{2}\end{bmatrix}}}$	Zyx	${\displaystyle {\begin{bmatrix}c_{2}c_{1}&-c_{2}s_{1}&s_{2}\\s_{3}s_{2}c_{1}+c_{3}s_{1}&-s_{3}s_{2}s_{1}+c_{3}c_{1}&-s_{3}c_{2}\\-c_{3}s_{2}c_{1}+s_{3}s_{1}&c_{3}s_{2}s_{1}+s_{3}c_{1}&c_{3}c_{2}\end{bmatrix}}}$
zxz	${\displaystyle {\begin{bmatrix}c_{3}c_{1}-c_{2}s_{1}s_{3}&-c_{3}s_{1}-c_{1}c_{2}s_{3}&s_{2}s_{3}\\c_{2}c_{3}s_{1}+c_{1}s_{3}&c_{3}c_{2}c_{1}-s_{3}s_{1}&-c_{3}s_{2}\\s_{1}s_{2}&c_{1}s_{2}&c_{2}\end{bmatrix}}}$	zxy	${\displaystyle {\begin{bmatrix}c_{3}c_{1}+s_{3}s_{2}s_{1}&-c_{3}s_{1}+s_{3}s_{2}c_{1}&s_{3}c_{2}\\c_{2}s_{1}&c_{2}c_{1}&-s_{2}\\-s_{3}c_{1}+c_{3}s_{2}s_{1}&s_{3}s_{1}+c_{3}s_{2}c_{1}&c_{3}c_{2}\end{bmatrix}}}$

См. Также [ править ]

• Вращение Якоби
• Плоскость вращения
• Преобразование домохозяина
• Давенпорт вращения

Заметки [ править ]

Ссылки [ править ]

• Bindel, D .; Demmel, J .; Kahan, W .; Маркес, О. (2000), О надежном и эффективном вычислении вращений Гивенса. Рабочая записка LAPACK 148, Университет Теннесси, UT-CS-00-449, 31 января 2001 г.
• Cybenko, Джордж (март-апрель 2001), "Снижение квантовых вычислений к элементарным унитарным операций" (PDF) , Вычислительный в области науки и техники , 3 (2): 27-32, DOI : 10,1109 / 5992.908999
• Голуб, Джин Х .; Ван Лоан, Чарльз Ф. (1996), Matrix Computations (3-е изд.), Johns Hopkins, ISBN 978-0-8018-5414-9.
• Нажмите, WH; Теукольский, С.А. Феттерлинг, Вашингтон; Фланнери, Б.П. (2007), «Раздел 11.3.1. Метод Гивенса» , Численные рецепты: Искусство научных вычислений (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN 978-0-521-88068-8