Jacobi-eigenwaarde algoritme

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Het Jacobi-eigenwaarde algoritme 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.

Algoritme[bewerken]

Aangezien het uitgangspunt is dat de matrix A\in\mathbb{R}^{n \times n} symmetrisch is, is deze matrix orthogonaal gelijksoortig aan een diagonaalmatrix D \in \mathbb{R}^{n \times n}.

D = S^T \cdot A \cdot S,

waarbij de diagonalen van D de eigenwaarden \lambda_1, \ldots, \lambda_n van A bevat en S kolomsgewijs de bijbehorende eigenvectoren

D = diag(\lambda_1, \ldots, \lambda_n),\qquad S = \lbrace E(\lambda_1), \ldots, E(\lambda_n)\rbrace

Het achterliggende idee bij het Jacobi-eigenwaarde algoritme bestaat eruit om steeds het grootste element buiten de diagonaal 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

\begin{array}{lll}A^{(0)} & = & A \\ A^{(k + 1)} & =  &R_k^T A^{(k)} R_k = \underbrace{R_k^TR_{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}

met R_k = \begin{bmatrix}   1   & \cdots &    0   & \cdots &    0   & \cdots &    0   \\
                      \vdots & \ddots & \vdots &        & \vdots &        & \vdots \\
                         0   & \cdots & \cos\varphi & \cdots &   \sin\varphi   & \cdots &    0   \\
                      \vdots &        & \vdots & \ddots & \vdots &        & \vdots \\
                         0   & \cdots &   -\sin\varphi   & \cdots &    \cos\varphi   & \cdots &    0   \\
                      \vdots &        & \vdots &        & \vdots & \ddots & \vdots \\
                         0   & \cdots &    0   & \cdots &    0   & \cdots &    1
       \end{bmatrix},

waarbij \cos\varphi en \sin\varphi steeds voor de p-de en q-de (p < q) rij en kolom staan en |a_{pq}^{(k)}| \geq |a_{ij}^{(k)}|\quad\forall 1 \leq i,j \leq n, i \not= j het grootste buitendiagonaalelement van A^{(k)} voorstelt. De componenten van R_k lenen zich nu tot de volgende overweging:

De transformatie R_k^TA^{(k)}R_k zorgt speciaal in de kruislementen voor de volgende veranderingen:

\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)\qquad(\ast)\end{array}
Aangezien a_{pq}^{(k + 1)} = 0 moet zijn, volgt uit (\ast):\quad \Theta: = \frac{a_{qq}^{(k)} - a_{pp}^{(k)}}{2a_{pq}^{(k)}} = \cot2\varphi = \frac{1 - \tan^2\varphi}{2\tan\varphi}
\Rightarrow \tan\varphi = \begin{cases}\frac{1}{\Theta + \sgn\Theta\sqrt{1 + \Theta^2}} & \Theta \not= 0 \\ 1 & \Theta = 0 \end{cases} \Rightarrow \cos\varphi = \frac{1}{\sqrt{1 + \tan^2\varphi}},~\sin\varphi = \tan\varphi\cos\varphi

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 A^{(k)} naar een diagonaalmatrix convergeert. Deze matrix moet op grond van de gelijksoortigheid dezelfde eigenwaarden bezitten.

A^{(k)}\ \xrightarrow[k\rightarrow\infty]{}\,diag(\lambda_1, \ldots, \lambda_n)

Over het algemeen volstaan 5n bewerkingen voor een n x n matrix

Klassiek en cyclisch Jacobi-eigenwaarde algoritme[bewerken]

Bij het klassieke Jacobi-eigenwaarde algoritme wordt bij elke iteratie het op dat moment grootste element op nul gezet. Aangezien het cyclische Jacobi-eigenwaarde algoritme daarentegen juist naar dit grootste element zoekt, wordt daar bij iedere iteratie steeds een Givens-rotatie op elk element binnen de strikte bovendriehoek uitgevoerd.

Referenties[bewerken]

  • (de) Kaspar Nipp, Daniel Stoffer: Lineare Algebra: Eine Einführung für Ingenieure unter besonderer Berücksichtigung numerischer Aspekte (Lineaire algebra: een introductie voor ingenieurs met bijzondere inachteming van de numerieke aspecten) VDF Hochschulverlag AG 2002, ISBN 978-3-7281-2818-8. Abschnitt 10.2 (S. 222-228) ((de) beperkte online-version (Google Books))

Externe link[bewerken]