Rotación de Jacobi

En álgebra lineal numérica , una rotación de Jacobi es una rotación , Q _{k ℓ} , de un subespacio lineal bidimensional de un espacio de producto interno n- dimensional , elegido para poner a cero un par simétrico de entradas fuera de la diagonal de una matriz simétrica real n × n , A , cuando se aplica como una transformación de similitud :

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

Es la operación principal del algoritmo de valor propio de Jacobi , que es numéricamente estable y adecuado para su implementación en procesadores paralelos ^{[ cita requerida ]} .

Solo las filas k y ℓ y las columnas k y ℓ de A se verán afectadas, y A ′ permanecerá simétrico. Además, rara vez se calcula una matriz explícita para Q _{k ℓ ; en cambio, se calculan valores auxiliares y se actualiza} A de una manera eficiente y numéricamente estable. Sin embargo, como referencia, podemos escribir la matriz como

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

Es decir, Q _{k ℓ} es una matriz identidad excepto por cuatro entradas, dos en la diagonal ( q _kk y q _ℓℓ , ambas iguales a c ) y dos simétricamente ubicadas fuera de la diagonal ( q _{k ℓ} y q _{ℓ k} , iguales a s y − s , respectivamente). Aquí c  = cos θ y s  ​​= sen θ para algún ángulo θ; pero para aplicar la rotación, no se requiere el ángulo en sí. Usando la notación delta de Kronecker , las entradas de la matriz se pueden escribir:

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

Supongamos que h es un índice distinto de k o ℓ (que deben ser distintos). Entonces, la actualización de similitud produce, algebraicamente:

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

Computación numéricamente estable

Para determinar las cantidades necesarias para la actualización, debemos resolver la ecuación fuera de la diagonal para cero (Golub y Van Loan 1996, §8.4). Esto implica que:

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

Establezca β en la mitad de esta cantidad:

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

Si a _{k ​​ℓ} es cero podemos detenernos sin realizar una actualización, por lo que nunca dividimos por cero. Sea t tan θ. Luego, con algunas identidades trigonométricas, reducimos la ecuación a:

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

Para la estabilidad elegimos la solución:

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

De esto podemos obtener c y s como:

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

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

Aunque ahora podríamos utilizar las ecuaciones de actualización algebraicas dadas anteriormente, puede ser preferible reescribirlas. Sea:

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

De modo que ρ = tan(θ/2). Las ecuaciones de actualización revisadas son:

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

Como se señaló anteriormente, nunca necesitamos calcular explícitamente el ángulo de rotación θ. De hecho, podemos reproducir la actualización simétrica determinada por Q _{k ℓ} conservando solo los tres valores k , ℓ y t , con t establecido en cero para una rotación nula.

Ejemplo tridiagonal

Algunas aplicaciones pueden requerir múltiples entradas de cero en una matriz de similitud , posiblemente en forma de una matriz tridiagonal . ^[1] Dado que las rotaciones jacobianas pueden eliminar ceros de otras celdas que se pusieron a cero previamente, por lo general no es posible lograr la tridiagonalización simplemente poniendo a cero cada celda fuera de la tridiagonal individualmente en una matriz mediana a grande. Sin embargo, si las rotaciones jacobianas se realizan repetidamente en la celda tridiagonal anterior con el valor absoluto más alto utilizando una celda adyacente justo debajo o a la izquierda para rotar, entonces se espera que todas las celdas fuera de la tridiagonal converjan en cero después de varias iteraciones. En el siguiente ejemplo, es una matriz 5X5 que se va a tridiagonalizar en una matriz similar, . ${\displaystyle A}$ ${\displaystyle T}$

${\displaystyle {\begin{aligned}&A={\begin{bmatrix}2&5&9&11&7\\5&3&6&-2&5\\9&6&7&3&1\\11&-2&3&1&3\\7&5&1&3&4\\\end{bmatrix}}\\&{\text{eigenvalues of }}A={\begin{bmatrix}4.1714549&5.9308002&-5.3682585&24.054762&-11.788758\end{bmatrix}}\\&|A|=37662\end{aligned}}}$

Para tridiagonalizar la matriz en la matriz , las celdas fuera de la tridiagonalidad [1,3], [1,4], [1,5], [2,4], [2,5] y [3,5] deben continuar siendo puestas a cero iterativamente hasta que el valor absoluto máximo de esas celdas esté por debajo de un umbral de convergencia aceptable. Este ejemplo utilizará 1.e-14.. Las celdas debajo de la diagonal se pondrán a cero automáticamente, debido a la naturaleza simétrica de la matriz. La primera rotación jacobiana será en la celda fuera de la tridiagonal con el valor absoluto más alto, que por inspección es [1,4] con un valor de 11. Para hacer que esta entrada sea cero, la condición especificada en las ecuaciones anteriores debe cumplirse para que las coordenadas de la celda se pongan a cero ( ) y para las coordenadas de rotación seleccionadas de ( ), y se reproducen a continuación para la primera iteración. ${\displaystyle A}$ ${\displaystyle T}$ ${\displaystyle h=1,l=4}$ ${\displaystyle S}$ ${\displaystyle h=1,k=3}$

Para forzar que las celdas [1,4] y [4,1] sean 0 rotando en la celda [1][3]:

${\displaystyle {\begin{aligned}&{\text{setting }}a'_{h\ell }=a'_{\ell h}=0{\text{ in above equation, }}a'_{h\ell }=a'_{\ell h}=ca_{h\ell }+sa_{hk}\,\!\\&9\sin(\theta )+11\cos(\theta )=0\\&\theta =\tan ^{-1}(-11/9)=-0.8850668\\&\sin(\theta )=-0.77395730\\&\cos(\theta )=0.66323890\\&\\&{\text{More conveniountly:}}\\&r={\sqrt {11^{2}+9^{2}}}=14.2126704\\&\sin(\theta )=-11/r=-0.77395730\\&\cos(\theta )=9/r=0.66323890\\&\\&S={\begin{bmatrix}&1&0&0&0&0\\&0&0.66323890&0&-0.77395730&0\\&0&0&1&0&0\\&0&0.77395730&0&0.66323890&0\\&0&0&0&0&1\\\end{bmatrix}}\\&\\&T_{1}=S^{T}AS={\begin{bmatrix}2&12.083046&9&0&7\\12.083046&-0.16438356&5.2139171&0.56164384&4.8001142\\9&5.2139171&7&-4.22079&1\\0&0.56164384&-4.22079&4.1643836&-3.3104236\\7&4.8001142&1&-3.3104236&4\\\end{bmatrix}}\\&{\text{eigenvalues of }}T_{1}={\begin{bmatrix}4.1714549&5.9308002&-5.3682585&24.054762&-11.788758\end{bmatrix}}\\&|T_{1}|=37662\end{aligned}}}$

La primera iteración de rotación, , produce una matriz con las celdas [1,4] y [4,1] puestas a cero, como se esperaba. Además, los valores propios y el determinante de son idénticos a los de y T1 también es simétrico, lo que confirma que la rotación jacobiana se realizó correctamente. La siguiente iteración para seleccionará la celda [2,5] que contiene el valor absoluto más alto, 4.8001142, de todas las celdas que se pondrán a cero. ${\displaystyle T_{1}}$ ${\displaystyle T_{1}}$ ${\displaystyle A}$ ${\displaystyle T_{2}}$

Después de 10 iteraciones de poner a cero la celda con el valor absoluto máximo utilizando rotaciones jacobianas en la celda justo debajo, el valor absoluto máximo de todas las celdas no tridiagonales es 2,6e-15. Suponiendo que este criterio de convergencia es aceptablemente bajo para la aplicación para la que se está realizando, la matriz triangularizada similar se muestra a continuación. ${\displaystyle T}$

${\displaystyle {\begin{aligned}&T={\begin{bmatrix}2&16.613248&0&0&0\\16.613248&10.184783&5.1109346&0&0\\0&5.1109346&4.0304188&4.5541372&0\\0&0&4.5541372&-3.3901672&0.43515335\\0&0&0&0.43515335&4.1749658\\\end{bmatrix}}\\&{\text{eigenvalues of }}T={\begin{bmatrix}4.1714549&5.9308002&-5.3682585&24.054762&-11.788758\end{bmatrix}}\\&|T|=37662\end{aligned}}}$

Dado que y tienen valores propios y determinantes idénticos y también son simétricos, y son matrices similares al estar tridiagonalizadas. ${\displaystyle A}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle A}$ ${\displaystyle T}$ ${\displaystyle T}$

Ejemplo de valores propios

La rotación jacobiana se puede utilizar para extraer los valores propios de una manera similar al ejemplo de triangulación anterior, pero poniendo a cero todas las celdas por encima de la diagonal, en lugar de la tridiagonal, y realizando la rotación jacobiana directamente en las celdas que se van a poner a cero, en lugar de en una celda adyacente.

Comenzando con la misma matriz que el ejemplo tridiagonal, ${\displaystyle A}$

${\displaystyle {\begin{aligned}&A={\begin{bmatrix}2&5&9&11&7\\5&3&6&-2&5\\9&6&7&3&1\\11&-2&3&1&3\\7&5&1&3&4\\\end{bmatrix}}\\&{\text{eigenvalues of }}A={\begin{bmatrix}4.1714549&5.9308002&-5.3682585&24.054762&-11.788758\end{bmatrix}}\\&|A|=37662\end{aligned}}}$

La primera rotación jacobiana se realizará en la celda fuera de la diagonal con el valor absoluto más alto, que por inspección es [1,4] con un valor de 11, y la celda de rotación también será [1,4], en las ecuaciones anteriores. El ángulo de rotación es el resultado de una solución cuadrática, pero se puede ver en la ecuación que si la matriz es simétrica, entonces se asegura una solución real. ${\displaystyle l=4,k=1}$

Para forzar que las celdas [1,4] y [4,1] sean 0 rotando en la celda [1][4]:

${\displaystyle {\begin{aligned}&{\text{setting }}a'_{k\ell }=a'_{\ell k}=0{\text{ in above equation: }}a'_{k\ell }=a'_{\ell k}=(c^{2}-s^{2})a_{k\ell }+sc(a_{kk}-a_{\ell \ell })\,\!\\&11(cos^{2}(\theta )-sin^{2}(\theta ))+(2-1)cos(\theta )sin(\theta )=0\\&{\text{dividing by -}}cos^{2}(\theta ){\text{:}}\\&tan^{2}(\theta )-tan(\theta )/11-1=0\\&tan(\theta )={\bigg [}1/11+{\sqrt {1/11^{2}+4}}{\bigg ]}/2=1.0464871\\&\theta =tan^{-1}(1.0464871)=-0.80810980\\&sin(\theta )=0.72298259\\&cos(\theta )=0.69086625\\&\\&{\text{More conveniountly:}}\\&r={\sqrt {1.0464871^{2}+1}}=1.4474582\\&sin(\theta )=1.0464871/r=0.72298259\\&cos(\theta )=1/r=0.69086625\\&\\&S={\begin{bmatrix}&0.69086625&0&0&0.72298259&0\\&0&1&0&0&0\\&0&0&1&0&0\\&-0.72298259&0&0&0.69086625&0\\&0&0&0&0&1\\\end{bmatrix}}\\&\\&T_{1}=S^{T}AS={\begin{bmatrix}-9.5113578&4.9002964&4.0488484&0&2.6671159\\4.9002964&3&6&2.2331805&5\\4.0488484&6&7&8.5794421&1\\0&2.2331805&8.5794421&12.511358&7.1334769\\2.6671159&5&1&7.1334769&4\\\end{bmatrix}}\\&{\text{eigenvalues of }}T_{1}={\begin{bmatrix}4.1714549&5.9308002&-5.3682585&24.054762&-11.788758\end{bmatrix}}\\&|T_{1}|=37662\end{aligned}}}$

La primera iteración de rotación, , produce una matriz con las celdas [1,4] y [4,1] puestas a cero, como se esperaba. Además, los valores propios y el determinante de son idénticos a los de y T1 también es simétrico, lo que confirma que la rotación jacobiana se realizó correctamente. La siguiente iteración para seleccionará la celda [3,4] que contiene el valor absoluto más alto, 8,5794421, de todas las celdas que se pondrán a cero. ${\displaystyle T_{1}}$ ${\displaystyle T_{1}}$ ${\displaystyle A}$ ${\displaystyle T_{2}}$

Después de 25 iteraciones de poner a cero la celda con el valor absoluto máximo utilizando rotaciones jacobianas en la celda justo debajo, el valor absoluto máximo de todas las celdas fuera de la diagonal es 9.0233029E-11. Suponiendo que este criterio de convergencia es aceptablemente bajo para la aplicación para la que se está realizando, la matriz diagonalizada similar se muestra a continuación. ${\displaystyle T}$

${\displaystyle {\begin{aligned}&T={\begin{bmatrix}24.054762&0&0&0&0\\0&5.9308002&0&0&0\\0&0&-11.788758&0&0\\0&0&0&4.1714549&0\\0&0&0&0&-5.3682585\\\end{bmatrix}}\\&{\text{eigenvalues of }}T={\begin{bmatrix}4.1714549&5.9308002&-5.3682585&24.054762&-11.788758\end{bmatrix}}\\&|T|=37662\end{aligned}}}$

Los valores propios ahora se muestran en diagonal y pueden extraerse directamente para su uso en otro lugar.

Dado que y tienen valores propios y determinantes idénticos y también son simétricos, y son matrices similares con que se diagonalizan con éxito. ${\displaystyle A}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle A}$ ${\displaystyle T}$ ${\displaystyle T}$

Véase también

• Rotación de Givens
• Transformación del jefe de familia
• Similitud de matrices

Referencias

1. Kinayman, Noyan; Aksun, MI (2005). Circuitos de microondas modernos. 685 Canton Street, Norwood, MA, EE. UU.: Artech House, Inc., págs. 506, 507, 511. ISBN 1-58053-725-1.{{cite book}}: CS1 maint: date and year (link) CS1 maint: location (link)

• Golub, Gene H. ; Van Loan, Charles F. (1996), Cálculos matriciales (3.ª ed.), Baltimore: Johns Hopkins University Press, ISBN 978-0-8018-5414-9