Lexikon der Mathematik: Jacobi-Verfahren zur Lösung des Eigenwertproblems
eines der ältesten Verfahren zur Lösung des vollständigen Eigenwert problems bei symmetrischen Matrizen \(A\in {{\mathbb{R}}}^{n\times n}\).
Das Jacobi-Verfahren transformiert A mittels einfacher orthogonaler Ähnlichkeitstranformationen auf Diagonalgestalt. Auf der Diagonalen stehen dann die Eigenwerte, das Produkt der Ähnlichkeitstransformationen liefert die Information über die zugehörigen Eigenvektoren.
Das Jacobi-Verfahren berechnet eine orthogonale Matrix U, für die UTAU Diagonalgestalt hat, als unendliches Produkt von Jacobi-RotationsmatrizenGij(a).
Man setzt A0 = A und iteriert für k = 0, 1,…:
- Wähle ein Pivotpaar (ik, jk), 1 ≤ ik< jk ≤ n.
- Bestimme ak so, daß in
\begin{eqnarray}{G}_{{i}_{k},{j}_{k}}({\alpha }_{k}){A}_{k}{G}_{{i}_{k},{j}_{k}}{({\alpha }_{k})}^{T}\end{eqnarray} das Element in der Position (ik, jk) verschwindet. - Setze \({A}_{k+1}={G}_{{i}_{k},{j}_{k}}({\alpha }_{k}){A}_{k}{G}_{{i}_{k},{j}_{k}}{({\alpha }_{k})}^{T}\).
Wegen der Symmetrie verschwindet in \({A}_{k+1}\) auch das Element in Position (jk, ik). Diese Nullen bleiben in der weiteren Iteration nicht erhalten.
Verschiedene Varianten des Jacobi-Verfahrens unterscheiden sich hinsichtlich der Vorschrift zur Bestimmung der Pivotpaare:
- Beim klassichen Jacobi-Verfahren wird in jedem Schritt das betragsmäßig größte Nebendiagonal-element von Ak eliminiert, man spricht hier auch von der Maximum-Strategie. Die Suche nach dem jeweils maximalen Element ist recht aufwendig.
- Bei den zyklischen Jacobi-Verfahren werden z. B. zeilenweise nacheinander alle Elemente unterhalb der Diagonalen zur Elimination gewählt, also z. B.
Ebenso ist jede Permutation dieser Reihenfolge möglich.
Im Intervall \((\frac{\pi }{4},\frac{\pi }{4}]\) gibt es genau einen Winkel αk, welcher in \({G}_{{i}_{k},{j}_{k}}({\alpha }_{k}){A}_{k}{G}_{{i}_{k},{j}_{k}}{({\alpha }_{k})}^{T}\) das Element in der Position (ik, jk) annulliert. Wählt man stets diesen Winkel, so läßt sich für alle erwähnten Varianten des Jacobi-Verfahrens zeigen, daß die Matrixfolge \({({A}_{k})}_{k\in {\mathbb{N}}}\) gegen eine Diagonalmatrix konvergiert. Die Folge der orthogonalen Matrizen \({({U}_{k})}_{k\in {\mathbb{N}}}\),
Es existieren zahlreiche Vorschläge, das Jacobi- Verfahren für das nichtsymmetrsiche Eigenwertproblem zu verallgemeinern.
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.