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,[1] mas que só se tornou amplamente utilizado na década de 1950, com o advento dos computadores.[2]

Descrição

editar

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

 

é simétrica e semelhante a S.

Além disso, S′ tem entradas:

 

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 Sij = 0, no caso em que S′ tem a maior soma dos quadrados na diagonal:

 

Igualando-se isso a 0 e rearranjando, temos

 

se   (caso que a expressão acima não contempla), teremos

 

Com o objetivo de otimizar esse efeito, Sij 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.

Referências

  1. Jacobi, C.G.J. (1846). «Über ein leichtes Verfahren, die in der Theorie der Säkularstörungen vorkommenden Gleichungen numerisch aufzulösen». Crelle's Journal (em alemão). 30: 51–94 
  2. Golub, G.H.; van der Vorst, H.A. (2000). «Eigenvalue computation in the 20th century». Journal of Computational and Applied Mathematics. 123 (1-2): 35–65. doi:10.1016/S0377-0427(00)00413-1