Direkt zum Inhalt

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,…:

  1. Wähle ein Pivotpaar (ik, jk), 1 ≤ ik< jkn.
  2. 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.
  3. 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.
\begin{eqnarray}(2,1),(3,1),(3,2),(4,1)(4,2)(4,3),(5,1),\mathrm{\ldots },(n,1),\mathrm{\ldots },(n,n-1).\end{eqnarray}

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}}}\), \begin{eqnarray}{U}_{k}={G}_{{i}_{k},{j}_{k}}({\alpha }_{k}){G}_{{i}_{k-1},{j}_{k-1}}({\alpha }_{k-1})\cdots {G}_{{i}_{0},{j}_{0}}({\alpha }_{0}),\end{eqnarray} welche man durch Aufmultiplizieren der Ähnlichkeitstransformationen erhält, konvergiert gegen eine orthogonale Matrix von Eigenvektoren. Die Konvergenz ist asymptotisch quadratisch. Das Verfahren ist heute insbesondere aufgrund seiner leichten Adaption für Parallelrechner beliebt.

Es existieren zahlreiche Vorschläge, das Jacobi- Verfahren für das nichtsymmetrsiche Eigenwertproblem zu verallgemeinern.

  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

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.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.