Jacobi-Verfahren (Eigenwerte)

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})}$ 

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.

• 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))

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

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