Jacobi-Verfahren (Eigenwerte)

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

Beschreibung

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 = 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 φ 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]{}\,diag(\lambda_1, \ldots, \lambda_n)$

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)