Ротация Гивенса

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

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

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

$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 ненулевые элементы матрицы Гивенса определяются следующим образом:

${\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 ( i , j , θ ) x представляет вращение вектора x против часовой стрелки в ( i , j ) плоскости θ радиан, отсюда и название «Вращение Гивенса».

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

Стабильный расчет

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

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

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

${\begin{aligned}c&{}\leftarrow a/r\\s&{}\leftarrow -b/r.\end{aligned}}$

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

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

subroutine givens_rotation(a, b, c, s, r)

real a, b, c, s, r
real h, d

if (b.ne.0.0) then
    h = hypot(a, b)
    d = 1.0 / h
    c = abs(a) * d
    s = sign(d, a) * b
    r = sign(1.0, a) * h
else
    c = 1.0
    s = 0.0
    r = a
end if

return
end

Более того, как обнаружил Эдвард Андерсон при усовершенствовании LAPACK , ранее упускаемый из виду численный фактор — непрерывность. Чтобы добиться этого, мы требуем, чтобы r было положительным. Следующий код MATLAB / GNU Octave иллюстрирует алгоритм.

function [c, s, r] = givens_rotation(a, b)
    if b == 0;
        c = sign(a);
        if (c == 0);
            c = 1.0; % Unlike other languages, MatLab's sign function returns 0 on input 0.
        end;
        s = 0;
        r = abs(a);
    elseif a == 0;
        c = 0;
        s = -sign(b);
        r = abs(b);
    elseif abs(a) > abs(b);
        t = b / a;
        u = sign(a) * sqrt(1 + t * t);
        c = 1 / u;
        s = -c * t;
        r = a * u;
    else
        t = a / b;
        u = sign(b) * sqrt(1 + t * t);
        s = -1 / u;
        c = t / u;
        r = b * u;
    end
end

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

Триангуляризация

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

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

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

Для формирования искомой матрицы обнуление элементов (2, 1) и (3, 2) требуется ; элемент (2, 1) сначала обнуляется с использованием матрицы вращения:

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

Следующие результаты матричного умножения:

${\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}}$

где

${\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 ₂ :

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

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

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

После этого происходит следующее умножение матрицы:

${\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}}$

где

${\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 ₃ :

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

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

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

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

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

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

Комплексные матрицы

Другой метод может расширить вращения Гивенса на комплексные матрицы. Диагональная матрица, диагональные элементы которой имеют единичные величины, но произвольные фазы, является унитарной. Пусть A — матрица, для которой желательно сделать элемент ji равным нулю, используя строки и столбцы i и j>i. Пусть D — диагональная матрица, диагональные элементы которой равны единице, за исключением диагональных элементов ii и jj, которые также имеют единичную величину, но имеют фазы, которые необходимо определить. Фазы элементов ii и jj матрицы D могут быть выбраны так, чтобы элементы ii и ji матрицы произведения DA были вещественными. Тогда вращение G Гивенса может быть выбрано с использованием строк и столбцов i и j>i так, чтобы элемент ji матрицы произведений GDA был равен нулю. Поскольку произведение унитарных матриц унитарно, матрица произведения GD унитарна, как и любой продукт таких пар матриц.

В алгебре Клиффорда

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

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

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

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

где

$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 есть три вращения Гивенса:

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

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

${\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 .

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

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

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

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

Таблица составленных вращений

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

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

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

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

хзх	${\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}}$	хзи	${\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}}$
хукс	${\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	${\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}}$
укси	${\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	${\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}}$
отслеживать	${\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	${\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}}$
Зиз	${\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}}$	Зикс	${\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}}$
зхз	${\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	${\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}}$

См. также

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

Ссылки

• Биндель, Д.; Деммель, Дж.; Кахан, В.; Маркес, О. (2000), О надежном и эффективном вычислении вращений Гивенса . Рабочая заметка LAPACK 148, Университет Теннесси, UT-CS-00-449, 31 января 2001 г.
• Цыбенко, Джордж (март – апрель 2001 г.), «Сведение квантовых вычислений к элементарным унитарным операциям» (PDF) , Computing in Science and Engineering , 3 (2): 27–32, doi : 10.1109/5992.908999 , заархивировано из оригинала (PDF) ) 03 марта 2016 г. , получено 26 февраля 2009 г.
• Голуб, Джин Х .; Ван Лоан, Чарльз Ф. (1996), Матричные вычисления (3-е изд.), Джонс Хопкинс, ISBN  978-0-8018-5414-9 .
• Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007), «Раздел 11.3.1. Метод Гивенса» , Численные рецепты: искусство научных вычислений (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN  978-0-521-88068-8 , заархивировано из оригинала 11 августа 2011 г. , получено 13 августа 2011 г.