Het jacobi-eigenwaardealgoritme is een iteratief algoritme uit de numerieke wiskunde, dat gebruikt wordt om alle eigenwaarden en eigenvectoren van kleine symmetrische matrices te berekenen. Het algoritme werd in het midden van de 19e eeuw door de Duitse wiskundig Carl Jacobi ontwikkeld.
Voor een reële, symmetrische
-matrix
geldt:
,
waarin
de diagonaalmatrix van eigenwaarden van
is en
kolomsgewijs de bijbehorende eigenvectoren van
bevat.
Het achterliggende idee bij het jacobi-eigenwaardealgoritme bestaat eruit om steeds het grootste element buiten de diagonaal van
met behulp van een Givens-rotatie naar 0 te brengen, om op die manier meer en meer de diagonaalmatrix te benaderen.
Er geldt het volgende iteratievoorschrift
![{\displaystyle {\begin{array}{lll}A^{(0)}&=&A\\A^{(k+1)}&=&R_{k}^{T}A^{(k)}R_{k}=\underbrace {R_{k}^{T}R_{k-1}^{T}\ldots R_{0}^{T}} _{S_{k}^{T}}A^{(0)}\underbrace {R_{0}\ldots R_{k-1}R_{k}} _{S_{k}}\end{array}}}](https://cdn.statically.io/img/wikimedia.org/api/rest_v1/media/math/render/svg/a6fafb47f87bfe5f4d444b0b68532d58dda1e5aa)
met
waarbij
en
steeds in de
-de en
-de
rij en kolom staan en
het absoluut grootste buitendiagonaalelement van
voorstelt, dus is voor alle
![{\displaystyle |a_{pq}^{(k)}|\geq |a_{ij}^{(k)}|}](https://cdn.statically.io/img/wikimedia.org/api/rest_v1/media/math/render/svg/9684c2c5d8bdaefe81b032db745a433aa6aed4de)
De elementen van
volgen dan uit de volgende overweging:
De transformatie
zorgt speciaal voor de elementen op de kruising van de
-de en
-de rij en kolom voor de volgende veranderingen:
![{\displaystyle {\begin{array}{lll}a_{pp}^{(k+1)}&=&a_{pp}^{(k)}\cos ^{2}\varphi -2a_{pq}^{(k)}\cos \varphi \sin \varphi +a_{qq}^{(k)}\sin ^{2}\varphi \\a_{qq}^{(k+1)}&=&a_{pp}^{(k)}\sin ^{2}\varphi +2a_{pq}^{(k)}\cos \varphi \sin \varphi +a_{qq}^{(k)}\cos ^{2}\varphi \\a_{pq}^{(k+1)}&=&a_{qp}^{(k+1)}=(a_{pp}^{(k)}-a_{qq}^{(k)})\cos \varphi \sin \varphi +a_{pq}^{(k)}(\cos ^{2}\varphi -\sin ^{2}\varphi )\end{array}}}](https://cdn.statically.io/img/wikimedia.org/api/rest_v1/media/math/render/svg/9c20a3d05722fd5ff4b5ba058ed54a67baef14a6)
Aangezien
moet zijn, volgt hieruit voor
![{\displaystyle \Theta ={\frac {a_{qq}^{(k)}-a_{pp}^{(k)}}{2a_{pq}^{(k)}}}=\cot 2\varphi ={\frac {1-\tan ^{2}\varphi }{2\tan \varphi }}}](https://cdn.statically.io/img/wikimedia.org/api/rest_v1/media/math/render/svg/b4086d41f85e28772613c9540fdf8960352edb40)
dat
![{\displaystyle \tan \varphi ={\begin{cases}{\frac {1}{\Theta +\operatorname {sgn} \Theta {\sqrt {1+\Theta ^{2}}}}}&\Theta \not =0\\1&\Theta =0\end{cases}}}](https://cdn.statically.io/img/wikimedia.org/api/rest_v1/media/math/render/svg/2c6f3c5214510e98dc2ce4e48a5ed9676800e70a)
en dus
![{\displaystyle \cos \varphi ={\frac {1}{\sqrt {1+\tan ^{2}\varphi }}},\quad \sin \varphi =\tan \varphi \cos \varphi }](https://cdn.statically.io/img/wikimedia.org/api/rest_v1/media/math/render/svg/f6eb2ccffcbd9c75de4c6182440db008383e2773)
Aangezien de rotatiematrices orthogonaal zijn en producten van orthogonale matrices ook weer orthogonaal zijn, wordt op deze wijze een orthogonale gelijksoortigheidstransformatie beschreven. Men kan aantonen dat de rij van matrices
naar een diagonaalmatrix convergeert. Deze matrix moet op grond van de gelijksoortigheid dezelfde eigenwaarden bezitten.
![{\displaystyle A^{(k)}\ {\xrightarrow[{k\rightarrow \infty }]{}}\,\mathrm {diag} (\lambda _{1},\ldots ,\lambda _{n})}](https://cdn.statically.io/img/wikimedia.org/api/rest_v1/media/math/render/svg/574de6982c9969fde8827240b2ee67ac38f3ec4f)
Over het algemeen volstaan
bewerkingen voor een
-matrix.
Bij het klassieke jacobi-eigenwaardealgoritme wordt bij elke iteratie het op dat moment grootste element op nul gezet. Aangezien het cyclische jacobi-eigenwaardealgoritme daarentegen juist naar dit grootste element zoekt, wordt daar bij iedere iteratie steeds een Givens-rotatie op elk element binnen de strikte bovendriehoek uitgevoerd.