Jacobi-Verfahren (Eigenwerte)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Das Jacobi-Verfahren (nach Carl Gustav Jacob Jacobi (1846)) ist ein iteratives Verfahren zur numerischen Berechnung aller Eigenwerte und -vektoren (kleiner) symmetrischer Matrizen.

Beschreibung[Bearbeiten]

Da die Ausgangsmatrix A\in\mathbb{R}^{n \times n} als symmetrisch vorausgesetzt wird, ist sie orthogonal ähnlich zu einer Diagonalmatrix D \in \mathbb{R}^{n \times n}.

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

wobei die Diagonale von D die Eigenwerte \lambda_1, \ldots, \lambda_n von A enthält und S spaltenweise die zugehörigen Eigenvektoren.

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


Die Idee des Jacobi-Verfahrens besteht darin, das jeweils betragsgrößte Außerdiagonalelement mit Hilfe einer Givens-Rotation auf 0 zu bringen, und sich auf diese Art mehr und mehr einer Diagonalmatrix anzunähern. Es ergibt sich die Iterationsvorschrift

\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}

mit 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},

wobei \cos\varphi und \sin\varphi jeweils in der p-ten und q-ten (p < q) Zeile und Spalte stehen und |a_{pq}^{(k)}| \geq |a_{ij}^{(k)}|\quad\forall 1 \leq i,j \leq n, i \not= j das betragsgrößte Außerdiagonalelement von A^{(k)} darstellt. Die Komponenten von R_k ergeben sich nun aus folgender Überlegung:

Die Transformation R_k^TA^{(k)}R_k bewirkt speziell in den Kreuzungselementen folgende Veränderungen:

\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}
Da a_{pq}^{(k + 1)} = 0 sein soll, ergibt sich aus (\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

Da die Rotationsmatrizen orthogonal sind und Produkte orthogonaler Matrizen wieder orthogonal sind, wird auf diese Art eine orthogonale Ähnlichkeitstransformation beschrieben. Es lässt sich zeigen, dass die Folge der Matrizen A^{(k)} gegen eine Diagonalmatrix konvergiert. Diese muss aufgrund der Ähnlichkeit dieselben Eigenwerte besitzen.

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

Klassisches und zyklische Jacobi-Verfahren[Bearbeiten]

Beim klassischen Jacobi-Verfahren wird in jedem Iterationsschritt das betragsmäßig größte Element zu Null gesetzt. Da die Suche nach diesem der Hauptaufwand des Algorithmus ist, wendet das zyklische Jacobi-Verfahren in jedem Iterationsschritt je eine Givensrotation auf jedes Element des strikten oberen Dreiecks an.

Literatur[Bearbeiten]

Weblinks[Bearbeiten]