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 {ℝ}^{n\times n}$ als symmetrisch vorausgesetzt wird, ist sie orthogonal ähnlich zu einer Diagonalmatrix $D\in {ℝ}^{n\times n}.$

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

wobei die Diagonale von $D$ die Eigenwerte ${\lambda }_1,\dots ,{\lambda }_n$ von $A$ enthält und $S$ spaltenweise die zugehörigen Eigenvektoren.

$D=\text{diag}({\lambda }_1,\dots ,{\lambda }_n),S=\{E({\lambda }_1),\dots ,E({\lambda }_n)\}$

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}{ccc}{A}^{(0)}& =& A\\ A^{(k+1)}& =& R_k^T{A}^{(k)}{R}_k=\underset{S_k^T}{\underbrace{R_k^T{R}_{k-1}^T\dots R_0^T}}{A}^{(0)}\underset{S_k}{\underbrace{R_0\dots R_{k-1}{R}_k}}\end{array}$

mit $R_k=\left[\begin{array}{ccccccc}1& \cdots & 0& \cdots & 0& \cdots & 0\\ ⋮& \ddots & ⋮& & ⋮& & ⋮\\ 0& \cdots & \cos \phi & \cdots & \sin \phi & \cdots & 0\\ ⋮& & ⋮& \ddots & ⋮& & ⋮\\ 0& \cdots & -\sin \phi & \cdots & \cos \phi & \cdots & 0\\ ⋮& & ⋮& & ⋮& \ddots & ⋮\\ 0& \cdots & 0& \cdots & 0& \cdots & 1\end{array}\right],$

wobei $\cos \phi$ und $\sin \phi$ jeweils in der $p$-ten und $q$-ten $(p<q)$ Zeile und Spalte stehen und $|a_{pq}^{(k)}|\ge |a_{ij}^{(k)}|\mathrm{\forall }1\le i,j\le n,i=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}{ccc}{a}_{pp}^{(k+1)}& =& a_{pp}^{(k)}{\cos }^2\phi -2a_{pq}^{(k)}\cos \phi \sin \phi +a_{qq}^{(k)}{\sin }^2\phi \\ a_{qq}^{(k+1)}& =& a_{pp}^{(k)}{\sin }^2\phi +2a_{pq}^{(k)}\cos \phi \sin \phi +a_{qq}^{(k)}{\cos }^2\phi \\ a_{pq}^{(k+1)}& =& a_{qp}^{(k+1)}=(a_{pp}^{(k)}-a_{qq}^{(k)})\cos \phi \sin \phi +a_{pq}^{(k)}({\cos }^2\phi -{\sin }^2\phi )(\ast )\end{array}$

Da $a_{pq}^{(k+1)}=0$ sein soll, ergibt sich aus $(\ast ):\mathrm{\Theta }:=\frac{a_{qq}^{(k)}-a_{pp}^{(k)}}{2a_{pq}^{(k)}}=\cot 2\phi =\frac{1-{\tan }^2\phi }{2\tan \phi }$

$\Rightarrow \tan \phi =\{\begin{array}{cc}\frac{1}{\mathrm{\Theta }+\mathrm{sgn}\mathrm{\Theta }\sqrt{1+{\mathrm{\Theta }}^2}}& \mathrm{\Theta }=0\\ 1& \mathrm{\Theta }=0\end{array}\Rightarrow \cos \phi =\frac{1}{\sqrt{1+{\tan }^2\phi }},\sin \phi =\tan \phi \cos \phi$

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)}\underset{k\to \mathrm{\infty }}{\overset{}{\to }}\text{diag}({\lambda }_1,\dots ,{\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)