rotación 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 producto interno de n dimensiones , elegido para poner a cero un par simétrico de entradas fuera de la diagonal de un real simétrico de n × n. matriz , 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 central del algoritmo de valores propios de Jacobi , que es numéricamente estable y adecuado para su implementación en procesadores paralelos ^{[ cita requerida ]} .

Sólo las filas k y ℓ y las columnas k y ℓ de A se verán afectadas, y A ′ permanecerá simétrica. Además, rara vez se calcula una matriz explícita para Q _{k ℓ} ; en cambio, se calculan los valores auxiliares y A se actualiza de forma 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 colocadas simétricamente fuera de la diagonal ( q _{k ℓ} y q _{ℓ k} , igual 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 }.\,\!}$

Cálculo numéricamente estable

Para determinar las cantidades necesarias para la actualización, debemos resolver la ecuación fuera de la diagonal para obtener 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 parar sin realizar una actualización, así 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 usar las ecuaciones de actualización algebraicas dadas anteriormente, puede ser preferible reescribirlas. Dejar:

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

de modo que ρ = tan(θ/2). Entonces 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 ceros en una matriz de similitud , posiblemente en forma de matriz tridiagonal . ^[1] Dado que las rotaciones jacobianas pueden eliminar ceros de otras celdas que previamente fueron puestas a cero, generalmente no es posible lograr la tridiagonalización simplemente poniendo a cero cada celda fuera de la tridiagonal individualmente en una matriz de tamaño mediano a grande. Sin embargo, si se realizan rotaciones jacobianas repetidamente en la celda tridiagonal superior con el valor absoluto más alto usando una celda adyacente justo debajo o hacia la izquierda para rotar, entonces se espera que todas las celdas no triangulares converjan en cero después de varios iteraciones. En el siguiente ejemplo, hay una matriz de 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 una matriz en una matriz , las celdas fuera de la tridiagonal [1,3], [1,4], [1,5], [2,4], [2,5] y [3,5] deben continuar se pondrá a cero de forma iterativa 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 estará 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 que esta entrada sea cero, se debe cumplir la condición especificada en las ecuaciones anteriores para las coordenadas de celda que se van a poner 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}$

${\displaystyle {\begin{aligned}\\&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 seleccionará la celda [2,5] que contiene el valor absoluto más alto, 4.8001142, de todas las celdas que se van a poner 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 usando rotaciones jacobianas en la celda justo debajo, el valor absoluto máximo de todas las celdas fuera de la tridiagonal es 2,6e-15. Suponiendo que este criterio de convergencia sea aceptablemente bajo para la aplicación para la que se realiza, a continuación se muestra una matriz triangular similar. ${\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 con tridiagonalización. ${\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 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 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 estará 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 la ecuaciones anteriores. El ángulo de rotación es el resultado de una solución cuadrática, pero en la ecuación se puede ver que si la matriz es simétrica, entonces se asegura una solución real. ${\displaystyle l=4,k=1}$

${\displaystyle {\begin{aligned}\\&11(cos^{2}(\theta )-sin^{2}(\theta ))+(2-1)cos(\theta )sin(\theta )=0\\&{\text{dividing by }}cos^{2}(\theta )\\&tan^{2}(\theta )-tan(\theta )/11-1=0\\&tan(\theta )=[1/11+{\sqrt {1/11^{2}+4}}]/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 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 usando 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 sea aceptablemente bajo para la aplicación para la que se realiza, a continuación se muestra una matriz diagonalizada similar. ${\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 se pueden extraer directamente para usarlos en otros lugares.

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

Ver también

• Rotación de dados
• Transformación del jefe de familia
• Similitud de matriz

Referencias

1. Kinayman, Noyan; Aksun, Michigan (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, gen H .; Van Loan, Charles F. (1996), Computaciones matriciales (3.ª ed.), Baltimore: Johns Hopkins University Press, ISBN 978-0-8018-5414-9