Вращение Якоби - Jacobi rotation

В числовая линейная алгебра, а Вращение Якоби это вращение, Q_kℓ, двумерного линейного подпространства н-размерный внутреннее пространство продукта, обнуляемую симметричную пару не-диагональ записи п×п настоящий симметричная матрица, А, когда применяется как преобразование подобия:

${\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 и ℓ из А будет затронуто, и это А′ Останется симметричным. Кроме того, явная матрица для Q_kℓ редко вычисляется; вместо этого вычисляются вспомогательные значения и А обновляется эффективным и численно стабильным способом. Однако для справки мы можем записать матрицу как

${\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_кк и 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.\,\!}$

Предполагать час это индекс, отличный от 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 }}}.}$

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

${\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, ℓ и т, с т установить на ноль для нулевого вращения.

Смотрите также

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

Рекомендации

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