Gerschgorin-Kreis

Gerschgorin-Kreise dienen in der numerischen linearen Algebra, einem Teilgebiet der Mathematik, zur Abschätzung von Eigenwerten. Mit ihrer Hilfe können einfach Gebiete angegeben werden, in welchen sich die Eigenwerte einer Matrix befinden und unter besonderen Bedingungen sogar wie viele Eigenwerte in diesen enthalten sind.

Sie sind benannt nach dem Mathematiker Semjon Aronowitsch Gerschgorin.

Definition

Sei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} eine quadratische Matrix mit Einträgen aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathbb{C}} (also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A \in \mathbb{C}^{n \times n}} ), dann ist der zum Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} -ten Diagonalelement Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_{ii}} gehörende Gerschgorin-Kreis folgendermaßen definiert:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \bar S_i := \bar S\left(a_{ii}, \sum_{j=1, j \neq i}^n \left| a_{ij} \right|\right)} für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i=1,\ldots,n}

wobei ${\bar {S}}(x,r)$ die abgeschlossene Kreisscheibe mit Radius $r=\sum _{j=1,j\neq i}^{n}\left|a_{ij}\right|$ um den Punkt $x\in \mathbb {C}$ bezeichnet.

Da die Menge der Eigenwerte (das Spektrum) von $A$ identisch mit der von $A^{T}$ ist, kann eine weitere Familie von Kreisen mit denselben Eigenschaften auch spaltenweise bestimmt werden:

${\bar {S}}_{j}:={\bar {S}}\left(a_{jj},\sum _{i=1,i\neq j}^{n}\left|a_{ij}\right|\right)$ für $j=1,\ldots ,n$

Abschätzung von Eigenwerten

Es gilt:

• Das Spektrum von $A$ ist eine Teilmenge von $\textstyle \bigcup _{i=1}^{n}{\bar {S}}_{i}$
• Falls es eine Teilmenge $I$ von $\{1,\ldots ,n\}$ gibt, sodass:

$\bigcup _{i\in I}{\bar {S}}_{i}\cap \bigcup _{i\notin I}{\bar {S}}_{i}=\emptyset$

dann beinhaltet $\textstyle \bigcup _{i\in I}{\bar {S}}_{i}$ genau Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left|I\right|} Eigenwerte (samt Vielfachheiten) der Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} .

Oder einprägsamer: Jede Zusammenhangskomponente der Vereinigung aller Gerschgorin-Kreisscheiben enthält genauso viele Eigenwerte wie Diagonalelemente der Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} .

Durch die Möglichkeit, die Kreise sowohl zeilen- als auch spaltenweise zu berechnen (die Eigenwerte der transponierten Matrix sind dieselben), können bei nichtsymmetrischen Matrizen zwei Abschätzungen pro Diagonalelement gefunden werden.

Beispiele

Datei:Gerschgorin A.png

Gerschgorin-Kreise zu Matrix A

Zu der Matrix

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A= \begin{pmatrix} 2 & 1 & 0.5 \\ 0.2 & 5 & 0.7 \\ 1 & 0 & 6 \end{pmatrix} }

gibt es folgende Gerschgorin-Kreise (spalten- und zeilenweise):

• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \bar S(2, 1.2)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \bar S(2, 1.5)} zum Diagonalelement Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_{11}}
• ${\bar {S}}(5,1)$ und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \bar S(5, 0.9)} zum Diagonalelement Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_{22}}
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \bar S(6, 1.2)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \bar S(6, 1)} zum Diagonalelement Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_{33}}

Da der Mengendurchschnitt ${\bar {S}}(2,1.2)\cap {\bigl (}{\bar {S}}(5,1)\cup {\bar {S}}(6,1.2){\bigr )}=\emptyset$ leer ist, befindet sich in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \bar S(2, 1.2)} genau ein Eigenwert und in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \bar S(5, 0.9) \cup \bar S(6, 1)} befinden sich genau zwei.

Die tatsächlichen Eigenwerte der Matrix Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A} sind gerundet 1,8692, 4,8730 und 6,2578 und tatsächlich in den oben angegebenen Gebieten enthalten.

Die Matrix

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B= \begin{pmatrix} 8 & 0 & 1 \\ 0 & 7 & 0 \\ 1 & 0 & 5 \\ \end{pmatrix} }

ist symmetrisch und reell, somit sind alle Eigenwerte reell und es gibt folgende reelle Intervalle (Gerschgorin-Kreise):

• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lbrack 7, 9 \rbrack = \bar S(8, 1)} zum Diagonalelement Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_{11}}
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lbrack 7, 7 \rbrack = \bar S(7, 0)} zum Diagonalelement Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle b_{22}}
• Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lbrack 4, 6 \rbrack = \bar S(5, 1)} zum Diagonalelement Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_{33}}

Da in der zweiten Spalte und Zeile dieser Matrix nur das Diagonalelement Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_{22}} verschieden von Null ist, kann ein Eigenwert mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b_{22}=7} leicht bestimmt werden, die beiden anderen liegen in den Intervallen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lbrack 7, 9 \rbrack} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lbrack 4, 6 \rbrack} , somit kann Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B} direkt als positiv definit identifiziert werden. Die tatsächlichen Eigenwerte der Matrix $B$ sind $\{7,\,{\tfrac {13\pm {\sqrt {13}}}{2}}\}$, also ungefähr 4,6972, 7 und 8,3028.

Verwendung

Die Gerschgorin-Kreise bieten in der Numerik eine einfache Möglichkeit, Eigenschaften von Matrizen zu bestimmen. Enthält z. B. kein Gerschgorin-Kreis den Nullpunkt, so ist die Matrix invertierbar. Diese Eigenschaft wird im Begriff der strikt diagonaldominanten Matrix zusammengefasst. Genauso lässt sich bei symmetrischen bzw. hermiteschen Matrizen die Definitheit oftmals mithilfe der Gerschgorin-Kreise grob abschätzen.

Siehe auch

• Satz von Gerschgorin: Anwendung auf Polynomnullstellen
• Satz von Courant-Fischer: alternative Charakterisierung der Eigenwerte symmetrischer oder hermitescher Matrizen

Literatur

• Gerschgorin, S. Über die Abgrenzung der Eigenwerte einer Matrix. Izv. Akad. Nauk. UdSSR Otd. Fiz.-Mat. Nauk 6, Seite 749–754, 1931 [1]
• Varga, R. S. Geršgorin and His Circles. Springer, Berlin 2004. ISBN 3540211004. Errata (PDF; 37 kB).