Jacobi-Verfahren (Eigenwerte)

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Das Jacobi-Verfahren (nach Carl Gustav Jacob Jacobi (1846))[1] 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.

Da die Ausgangsmatrix als symmetrisch vorausgesetzt wird, ist sie orthogonal ähnlich zu einer Diagonalmatrix

wobei die Diagonale von die Eigenwerte von enthält und spaltenweise die zugehörigen Eigenvektoren.

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

mit

wobei und jeweils in der -ten und -ten Zeile und Spalte stehen und das betragsgrößte Außerdiagonalelement von darstellt. Die Komponenten von ergeben sich nun aus folgender Überlegung:

Die Transformation bewirkt speziell in den Kreuzungselementen folgende Veränderungen:

Da sein soll, ergibt sich aus

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 gegen eine Diagonalmatrix konvergiert. Diese muss aufgrund der Ähnlichkeit dieselben Eigenwerte besitzen.

Klassisches und zyklische Jacobi-Verfahren

[Bearbeiten | Quelltext bearbeiten]

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.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  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