Вращение Якоби

В числовой линейной алгебре , A вращение Якоби представляет собой вращение , Q _{K л} , из 2-мерного линейного подпространства в качестве n - мерного внутреннего пространства продукта , выбранного нуль симметричного пара внебалансовых диагональных элементов матрицы с п × п вещественных симметричной матрица , , когда применяется в качестве преобразования подобия :

${\ displaystyle A \ mapsto Q_ {k \ ell} ^ {T} AQ_ {k \ ell} = A '. \, \!}$

${\displaystyle {\begin{bmatrix}{*}&&&\cdots &&&*\\&\ddots &&&&&\\&&a_{kk}&\cdots &a_{k\ell }&&\\\vdots &&\vdots &\ddots &\vdots &&\vdots \\&&a_{\ell k}&\cdots &a_{\ell \ell }&&\\&&&&&\ddots &\\{*}&&&\cdots &&&*\end{bmatrix}}\to {\begin{bmatrix}{*}&&&\cdots &&&*\\&\ddots &&&&&\\&&a'_{kk}&\cdots &0&&\\\vdots &&\vdots &\ddots &\vdots &&\vdots \\&&0&\cdots &a'_{\ell \ell }&&\\&&&&&\ddots &\\{*}&&&\cdots &&&*\end{bmatrix}}.}$

Это основная операция в алгоритме собственных значений Якоби , который численно стабилен и хорошо подходит для реализации на параллельных процессорах ^{[ необходима ссылка ]} .

Только строки k и ℓ и столбцы k и ℓ A будут затронуты, и этот A 'останется симметричным. Кроме того, явная матрица для Q _{k ℓ} вычисляется редко; вместо этого вычисляются вспомогательные значения, и A обновляется эффективным и численно стабильным способом. Однако для справки мы можем записать матрицу как

${\displaystyle Q_{k\ell }={\begin{bmatrix}1&&&&&&\\&\ddots &&&&0&\\&&c&\cdots &-s&&\\&&\vdots &\ddots &\vdots &&\\&&s&\cdots &c&&\\&0&&&&\ddots &\\&&&&&&1\end{bmatrix}}.}$

То есть Q _{k ℓ} является единичной матрицей, за исключением четырех элементов, двух на диагонали ( q _kk и q _ℓℓ , оба равны c ) и двух симметрично расположенных вне диагонали ( q _{k ℓ} и q _{ℓ k} , равных s и - s соответственно). Здесь c  = cos ϑ и s  = sin ϑ для некоторого угла; но чтобы применить поворот, сам угол не требуется. Используя дельта- нотацию Кронекера , элементы матрицы могут быть записаны

${\displaystyle q_{ij}=\delta _{ij}+(\delta _{ik}\delta _{jk}+\delta _{i\ell }\delta _{j\ell })(c-1)+(\delta _{ik}\delta _{j\ell }-\delta _{i\ell }\delta _{jk})s.\,\!}$

Предположим, что h - это индекс, отличный от k или ℓ (которые сами должны быть различными). Тогда обновление подобия дает алгебраически

${\displaystyle a'_{hk}=a'_{kh}=ca_{hk}-sa_{h\ell }\,\!}$

${\displaystyle a'_{h\ell }=a'_{\ell h}=ca_{h\ell }+sa_{hk}\,\!}$

${\displaystyle a'_{k\ell }=a'_{\ell k}=(c^{2}-s^{2})a_{k\ell }+sc(a_{kk}-a_{\ell \ell })=0\,\!}$

${\displaystyle a'_{kk}=c^{2}a_{kk}+s^{2}a_{\ell \ell }-2sca_{k\ell }\,\!}$

${\displaystyle a'_{\ell \ell }=s^{2}a_{kk}+c^{2}a_{\ell \ell }+2sca_{k\ell }.\,\!}$

Численно стабильные вычисления [ править ]

Чтобы определить количества, необходимые для обновления, мы должны решить недиагональное уравнение относительно нуля ( Голуб и Ван Лоан 1996 , §8.4). Это означает, что

${\displaystyle {\frac {c^{2}-s^{2}}{sc}}={\frac {a_{\ell \ell }-a_{kk}}{a_{k\ell }}}.}$

Установите β равным половине этого количества,

${\displaystyle \beta ={\frac {a_{\ell \ell }-a_{kk}}{2a_{k\ell }}}.}$

Если _{к ℓ} равен нулю , мы можем не выполнять обновление, таким образом , мы никогда не делить на ноль. Пусть t будет tan ϑ. Затем с помощью нескольких тригонометрических тождеств сводим уравнение к виду

${\displaystyle t^{2}+2\beta t-1=0.\,\!}$

Для устойчивости выбираем решение

${\displaystyle t={\frac {\operatorname {sgn}(\beta )}{|\beta |+{\sqrt {\beta ^{2}+1}}}}.}$

Отсюда мы можем получить c и s как

${\displaystyle c={\frac {1}{\sqrt {t^{2}+1}}}\,\!}$

${\displaystyle s=ct\,\!}$

Хотя теперь мы можем использовать приведенные ранее алгебраические уравнения обновления, может быть предпочтительнее их переписать. Позволять

${\displaystyle \rho ={\frac {s}{1+c}},}$

так что ρ = tan (ϑ / 2). Тогда пересмотренные уравнения обновления

${\displaystyle a'_{hk}=a'_{kh}=a_{hk}-s(a_{h\ell }+\rho a_{hk})\,\!}$

${\displaystyle a'_{h\ell }=a'_{\ell h}=a_{h\ell }+s(a_{hk}-\rho a_{h\ell })\,\!}$

${\displaystyle a'_{k\ell }=a'_{\ell k}=0\,\!}$

${\displaystyle a'_{kk}=a_{kk}-ta_{k\ell }\,\!}$

${\displaystyle a'_{\ell \ell }=a_{\ell \ell }+ta_{k\ell }\,\!}$

Как отмечалось ранее, нам никогда не нужно явно вычислять угол поворота ϑ. Фактически, мы можем воспроизвести симметричное обновление, определяемое Q _{k ℓ} , сохранив только три значения k , ℓ и t , при этом t установлено в ноль для нулевого поворота.

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

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

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

• Голуб, Джин Х .; Ван Лоан, Чарльз Ф. (1996), Матричные вычисления (3-е изд.), Балтимор: Johns Hopkins University Press, ISBN 978-0-8018-5414-9