Der Satz von Gerschgorin (nach dem Mathematiker Semjon Aronowitsch Gerschgorin) ist ein Lehrsatz aus der Algebra. Er besagt, dass die komplexen Nullstellen eines normierten komplexen Polynoms

in einem Kreis um den Nullpunkt mit dem Radius liegen, wobei die Abschätzungen

  • und

gelten.

Gerschgorin-Kreise

Bearbeiten

Dieser Satz ist eine Folgerung aus dem Satz über die Gerschgorin-Kreise in der komplexen Ebene, welche die Eigenwerte einer quadratischen Matrix enthalten. Für jede Matrix   gilt, dass die Eigenwerte von   in der Vereinigung der Kreisscheiben

 

um die Diagonalelemente   mit Radien   bzw. bei Betrachtung der transponierten Matrix mit Radien   liegen. Jede Zusammenhangskomponente der Vereinigung enthält genauso viele Eigenwerte wie Diagonalelemente der Matrix  .

Begleitmatrizen

Bearbeiten

Multipliziert man ein Polynom   mit Grad   mit der Variablen   und reduziert das Produkt modulo  , so entsteht ein neues Polynom   mit Grad kleiner  . Diese Zuordnung ist eine lineare Abbildung des Raums   der Polynome vom Grad   (oder kleiner) in sich selbst. Zu jeder Basis dieses  -dimensionalen Vektorraums (genauer des Quotientenrings  ) kann daher eine Koeffizientenmatrix dieses Multiplikationsoperators angegeben werden. Diese wird Begleitmatrix des Polynoms genannt.

Jede Begleitmatrix des Polynoms   hat die Nullstellen des Polynoms als Eigenwerte. Das Eigenpolynom zum Eigenwert   ist  , denn  .

Begleitmatrix zur Standardbasis

Bearbeiten

Die Standardbasis besteht aus den Monomen  . Die Produkte   sind schon die gradminimalen Repräsentanten modulo  , für das letzte Basiselement gilt

 .

Die Begleitmatrix (in Frobenius-Form) ist also

 .

Die Nullstellen des Polynoms   sind daher in der Vereinigung der Kreisscheiben   und   enthalten. Bei Verwendung der transponierten Begleitmatrix ergibt sich die Vereinigung der Kreisscheiben  ,   und  . Aus diesen beiden Fällen ergeben sich die einleitend angegebenen Abschätzungen.

Begleitmatrix zur Basis der Lagrange-Interpolation

Bearbeiten

(vgl. Börsch-Supan 1963): Seien   paarweise verschiedene komplexe Zahlen. Dann bilden die Polynome

 

eine Basis des Raums der Polynome vom Grad kleiner  . Der führende Koeffizient ist jeweils 1. Deshalb ist der minimale Repräsentant von   gerade das Polynom  . Nach der Formel der Lagrange-Interpolation kann dieses Polynom in der gewählten Basis ausgedrückt werden:

 .

Die Begleitmatrix ergibt sich somit zu

 .

Je näher die Stützstellen   an den wahren Nullstellen liegen, desto kleiner wird der zweite Summand, das heißt desto kleiner sind die Radien der Gerschgorin-Kreise.

Die Nullstellen von   sind danach in der Vereinigung der Kreisscheiben

 

bzw. bei Verwendung der transponierten Begleitmatrix in der Vereinigung der Kreisscheiben

 

enthalten. Sind die gewählten Stützstellen   gute Approximationen der Nullstellen von p(X), so zerfällt die Vereinigung der Kreisscheiben in Zusammenhangskomponenten, die jeweils einen Cluster von Nullstellen bzw. eine mehrfache Nullstelle enthalten. Sind die Nullstellen gut getrennt und die Approximation gut genug, so sind die Kreisscheiben paarweise disjunkt und jede enthält genau eine Nullstelle.

Eine weitere Beobachtung ist, dass die Zentren   der Kreisscheiben bessere Schätzungen der Nullstellen von   darstellen. Wiederholt man diese Verbesserung in einer Rekursion, so ergibt sich das Weierstraß-(Durand-Kerner)-Verfahren.

Verbesserung

Bearbeiten

A. Neumaier (2003) gibt die folgende Verbesserung der Kreisscheiben im letzten Beispiel: Die Nullstellen sind in den Kreisscheiben

 ,

enthalten. Diese Kreisscheiben sind Teilmengen der Kreisscheiben zur transponierten Matrix im letzten Beispiel. Der Radius reduziert sich gegenüber der dort abgeleiteten Formel um einen Faktor von etwa  .

Literatur

Bearbeiten
  • W. Börsch-Supan: A posteriori error bounds for the zeros of polynomials. In: Numerische Mathematik. Vol. 5, Nr. 1, 1963, ISSN 0029-599X, S. 380–398, doi:10.1007/BF01385904.
  • Howard E. Bell: Gershgorin’s Theorem and the Zeros of Polynomials. In: American Mathematical Monthly. Vol. 72, Nr. 3, März 1965, ISSN 0002-9890, S. 292–295.
  • Arnold Neumaier: A Gerschgorin type theorem for zeros of polynomials. (online), wahrscheinlich publiziert als Arnold Neumaier: Enclosing clusters of zeros of polynomials. In: Journal of Computational and Applied Mathematics. 156. Jahrgang, 2003 (sciencedirect.com).