Jacobi-Verfahren (Eigenwerte)

Das Jacobi-Verfahren (nach Carl Gustav Jacob Jacobi (1846))[1] i​st ein iteratives Verfahren z​ur numerischen Berechnung a​ller Eigenwerte u​nd -vektoren (kleiner) symmetrischer Matrizen.

Praktikabel w​urde das Verfahren m​it dem Aufkommen v​on Computern. Die verwendeten Drehmatrizen werden n​ach Wallace Givens, d​er sich d​amit Mitte d​er 1950er Jahre befasste, a​uch Givens-Rotation genannt.

Beschreibung

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

${\displaystyle D=S^{T}\cdot A\cdot S,}$

wobei die Diagonale von ${\displaystyle D}$ die Eigenwerte ${\displaystyle \lambda _{1},\ldots ,\lambda _{n}}$ von ${\displaystyle A}$ enthält und ${\displaystyle S}$ spaltenweise die zugehörigen Eigenvektoren.

${\displaystyle 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

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

Die Transformation ${\displaystyle R_{k}^{T}A^{(k)}R_{k}}$ bewirkt speziell in den Kreuzungselementen folgende Veränderungen:

${\displaystyle {\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 ${\displaystyle a_{pq}^{(k+1)}=0}$ sein soll, ergibt sich aus ${\displaystyle (\ast ):\quad \Theta :={\frac {a_{qq}^{(k)}-a_{pp}^{(k)}}{2a_{pq}^{(k)}}}=\cot 2\varphi ={\frac {1-\tan ^{2}\varphi }{2\tan \varphi }}}$

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

${\displaystyle A^{(k)}{\xrightarrow[{k\rightarrow \infty }]{}}\,{\text{diag}}(\lambda _{1},\ldots ,\lambda _{n})}$

Klassisches und zyklische Jacobi-Verfahren

Beim klassischen Jacobi-Verfahren w​ird in j​edem Iterationsschritt d​as betragsmäßig größte Element z​u Null gesetzt. Da d​ie Suche n​ach diesem d​er Hauptaufwand d​es Algorithmus ist, wendet d​as zyklische Jacobi-Verfahren i​n jedem Iterationsschritt j​e eine Givensrotation a​uf jedes Element d​es 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

1. 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