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.

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 $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}^{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}}$

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}^{T}A^{(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)}}}=\cot 2\varphi ={\frac {1-\tan ^{2}\varphi }{2\tan \varphi }}$

$\Rightarrow \tan \varphi ={\begin{cases}{\frac {1}{\Theta +\operatorname {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

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)