Algoritmo de autovalores de Jacobi

Em álgebra linear numérica, o algoritmo de autovalores de Jacobi é um método iterativo para o cálculo de autovalores e autovetores de uma matriz simétrica real (um processo conhecido como diagonalização). É nomeada após Carl Gustav Jakob Jacobi, quem primeiro propôs o método em 1846, mas que só se tornou amplamente utilizado na década de 1950, com o advento dos computadores.

Descrição

Dada S sendo uma matriz simétrica, e G = G(i,j,θ) sendo uma matriz de rotação de Givens. Então:

$S'=GSG^{\top }\,$

é simétrica e semelhante a S.

Além disso, S′ tem entradas:

${\begin{aligned}S'_{ii}&=c^{2}\,S_{ii}-2\,sc\,S_{ij}+s^{2}\,S_{jj}\\S'_{jj}&=s^{2}\,S_{ii}+2sc\,S_{ij}+c^{2}\,S_{jj}\\S'_{ij}&=S'_{ji}=(c^{2}-s^{2})\,S_{ij}+sc\,(S_{ii}-S_{jj})\\S'_{ik}&=S'_{ki}=c\,S_{ik}-s\,S_{jk}&k\neq i,j\\S'_{jk}&=S'_{kj}=s\,S_{ik}+c\,S_{jk}&k\neq i,j\\S'_{kl}&=S_{kl}&k,l\neq i,j\end{aligned}}$

onde s = sin(θ) e c = cos(θ).

Como G é ortogonal, S e S′ têm a mesma norma de Frobenius ||·||_F (a raiz quadrada da soma dos quadrados de todos os elementos), o que nos permite escolher θ que satisfaça S′_ij = 0, no caso em que S′ tem a maior soma dos quadrados na diagonal:

$S'_{ij}=\cos(2\theta )S_{ij}+{\tfrac {1}{2}}\sin(2\theta )(S_{ii}-S_{jj})$

Igualando-se isso a 0 e rearranjando, temos

$\tan(2\theta )={\frac {2S_{ij}}{S_{jj}-S_{ii}}}$

se $S_{jj}=S_{ii}$ (caso que a expressão acima não contempla), teremos

$\theta ={\frac {\pi }{4}}$

Com o objetivo de otimizar esse efeito, S_ij deve ser o elemento com maior valor absoluto fora da diagonal. Esse elemento recebe o nome de pivô.

O método de Jacobi para autovalores efetua repetidamente rotações até que a matriz se torne aproximadamente diagonal por meio do ataque ao pivô a cada iteração. Assim, os elementos finais na diagonal principal são aproximações dos autovalores reais de S.