Jacobi-Verfahren (Eigenwerte)

Das Jacobi-Verfahren (nach Carl Gustav Jacob Jacobi (1846))<ref> Jacobi, Über ein leichtes Verfahren, die in der Theorie der Säkularstörungen vorkommenden Gleichungen numerisch aufzulösen, Crelle's Journal, Band 30, 1846, S. 51–94</ref> ist ein iteratives Verfahren zur numerischen Berechnung aller Eigenwerte und -vektoren (kleiner) symmetrischer Matrizen.

Praktikabel wurde das Verfahren mit dem Aufkommen von Computern. Die verwendeten Drehmatrizen werden nach Wallace Givens, der sich damit Mitte der 1950er Jahre befasste, auch Givens-Rotation genannt.

Beschreibung

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

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

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

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

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

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

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

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

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

Da <math>a_{pq}^{(k + 1)} = 0</math> sein soll, ergibt sich aus <math>(\ast):\quad \Theta: = \frac{a_{qq}^{(k)} - a_{pp}^{(k)}}{2a_{pq}^{(k)}} = \cot2\varphi = \frac{1 - \tan^2\varphi}{2\tan\varphi}</math>

<math>\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</math>

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 <math>A^{(k)}</math> gegen eine Diagonalmatrix konvergiert. Diese muss aufgrund der Ähnlichkeit dieselben Eigenwerte besitzen.

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

Klassisches und zyklische Jacobi-Verfahren

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

Kaspar Nipp, Daniel Stoffer: Lineare Algebra: Eine Einführung für Ingenieure unter besonderer Berücksichtigung numerischer Aspekte. VDF Hochschulverlag AG 2002, ISBN 978-3-7281-2818-8. Abschnitt 10.2 (S. 222–228) (eingeschränkte Online-Version (Google Books))

Weblinks

Webseite der Fullerton Universität zum Jacobi-Verfahren (inklusive einer Linksammlung)

Einzelnachweise