Satz von Gershgorin

Satz von Gershgorin

Der Satz von Gerschgorin (nach Semjon Aranowitsch Gerschgorin) besagt, dass die komplexen Nullstellen \xi_1, \dots, \xi_n eines normierten komplexen Polynoms

p= X^n + p_{n-1} X^{n-1} + \dots + p_0

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

  • r \le \max \{1, \sum^{n-1}_{j=0} | p_j | \} und
  • r \le \max \{ | p_0 |, 1 + | p_1 | , \dots , 1+| p_{n-1} | \}

gelten.

Inhaltsverzeichnis

Wiederholung Gerschgorin-Kreise

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 A\in\mathbb C^{n\times n} gilt, dass die Eigenwerte von A in der Vereinigung der Kreisscheiben

D\big(a_{k,k},r_k\big)=\big\{\,z\in\mathbb C:\,|z-a_{k,k}|\le r_k\,\big\}

um die Diagonalelemente ak,k mit Radien r_k=\sum_{j\ne k}|a_{k,j}| bzw. bei Betrachtung der transponierten Matrix mit Radien r_k=\sum_{j\ne k}|a_{j,k}| liegen. Jede Zusammenhangskomponente der Vereinigung enthält genauso viele Eigenwerte wie Diagonalelemente der Matrix A.

Begleitmatrizen

Multipliziert man ein Polynom q(X) mit Grad deg q<n mit der Variablen X und reduziert das Produkt modulo p(X), so entsteht ein neues Polynom \tilde q(X)=X\cdot q(X) \mod p(X) mit Grad kleiner n. Diese Zuordnung ist eine lineare Abbildung des Raums \mathbb C[X]_{n-1} der Polynome vom Grad n-1 (oder kleiner) in sich selbst. Zu jeder Basis dieses n-dimensionalen Vektorraums (genauer des Quotientenrings \mathbb C[X]/(p(X))) kann daher eine Koeffizientenmatrix dieses Multiplikationsoperators angegeben werden. Diese wird Begleitmatrix des Polynoms genannt.

Jede Begleitmatrix des Polynoms p(X) hat die Nullstellen des Polynoms als Eigenwerte. Das Eigenpolynom zum Eigenwert ξk ist q_k(X)=\prod_{j\ne k}(X-\xi_k), denn X\cdot q_k(X)=\xi_kq_k(X)+p(X).

Begleitmatrix zur Standardbasis

Die Standardbasis besteht aus den Monomen w_1=1,w_2=X,w_3=X^2,\dots,w_n=X^{n-1}. Die Produkte X\cdot w_1(X)=w_2(X),\dots,X\cdot w_{n-1}(X)=w_n(X) sind schon die gradminimalen Repräsentanten modulo p(X), für das letzte Basiselement gilt

X\cdot w_n(X)=X^n=p(X)-p_0w_0(X)-p_1-\dots-p_{n-1}w_n.

Die Begleitmatrix (in Frobenius-Form) ist also

A=\begin{pmatrix}
0&amp;amp;1&amp;amp;0&amp;amp;\dots\\
0&amp;amp;0&amp;amp;1&amp;amp;0&amp;amp;\dots\\
\vdots&amp;amp;&amp;amp;\ddots&amp;amp;\ddots\\
0&amp;amp;&amp;amp;&amp;amp;0&amp;amp;1\\
-p_0&amp;amp;-p_1&amp;amp;-p_2&amp;amp;\dots&amp;amp;-p_{n-1}
\end{pmatrix}
.

Die Nullstellen des Polynoms p sind daher in der Vereinigung der Kreisscheiben D(0,1) und D(-p_{n-1}, \min(|p_0|+\dots+|p_{n-2}|)) enthalten. Bei Verwendung der transponierten Begleitmatrix ergibt sich die Vereinigung der Kreisscheiben D(0, | p0 | ), D(0,1 + | pk | ), k=1,...,n-2 und D( − pn − 1,1). Aus diesen beiden Fällen ergeben sich die einleitend angegebenen Abschätzungen.

Begleitmatrix zur Basis der Lagrange-Interpolation

(vgl. Börsch-Supan 1963): Seien z_1,\dots,z_n\in\mathbb C paarweise verschiedene komplexe Zahlen. Dann bilden die Polynome

w_k(X)=\prod_{j\ne k}(X-z_j), k=1,...,n

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

X\cdot w_k(X)-p(X)
=\sum_{j=1}^n \big(z_jw_k(z_j)-p(z_j)\big)\,\frac{w_j(X)}{w_j(z_j)}
=z_k-\sum_{j=1}^n \frac{p(z_j)}{w_j(z_j)}\,w_j(X)
.

Die Begleitmatrix ergibt sich somit zu


A=\operatorname{diag}(z_1,\dots,z_n)
  -\begin{pmatrix}1\\\vdots\\1\end{pmatrix}\left(\frac{p(z_1)}{w_1(z_1)},\dots,\frac{p(z_n)}{w_n(z_n)}\right)
.

Je näher die Stützstellen z_1,\dots,z_n\in\mathbb C an den wahren Nullstellen liegen, desto kleiner wird der zweite Summand, d.h. desto kleiner sind die Radien der Gerschgorin-Kreise.

Die Nullstellen von p sind danach in der Vereinigung der Kreisscheiben

D\left(z_k-\frac{p(z_k)}{w_k(z_k)},\sum_{j\ne k}\left|\frac{p(z_j)}{w_j(z_j)}\right|\right)

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

D\left(z_k-\frac{p(z_k)}{w_k(z_k)},(n-1)\left|\frac{p(z_k)}{w_k(z_k)}\right|\right)

enthalten. Sind die gewählten Stützstellen z_1,\dots,z_n\in\mathbb C 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 z_k-\frac{p(z_k)}{w_k(z_k)} der Kreisscheiben bessere Schätzungen der Nullstellen von p darstellen. Wiederholt man diese Verbesserung in einer Rekursion, so ergibt sich das Weierstraß-(Durand-Kerner)-Verfahren.

Verbesserung

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

D\left(z_k-\frac{np(z_k)}{2w_k(z_k)},\left|\frac{np(z_k)}{2w_k(z_k)}\right|\right), k=1,...,n,

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 1/2.

Literatur

  • W. Börsch-Supan: A posteriori error bounds for the zeros of polynomials. In: Numerische Mathematik. 5, 1963
  • H.E. Bell: Gershgorin's theorem and the zeros of polynomials. In: American Mathematical Monthly. 72, 1965
  • Arnold Neumaier: A Gerschgorin type theorem for zeros of polynomials. , wahrscheinlich publiziert als Arnold Neumaier: Enclosing clusters of zeros of polynomials. In: Journal of Computational and Applied Mathematics. 156, 2003

Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Satz von Gerschgorin — Der Satz von Gerschgorin (nach dem Mathematiker Semjon Aranowitsch Gerschgorin) ist ein Lehrsatz aus der Algebra. Er besagt, dass die komplexen Nullstellen eines normierten komplexen Polynoms in einem Kreis K um den Nullpunkt mit dem Radius r… …   Deutsch Wikipedia

  • Liste mathematischer Sätze — Inhaltsverzeichnis A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A Satz von Abel Ruffini: eine allgemeine Polynomgleichung vom …   Deutsch Wikipedia

  • Liste de théorèmes — par ordre alphabétique. Pour l établissement de l ordre alphabétique, il a été convenu ce qui suit : Si le nom du théorème comprend des noms de mathématiciens ou de physiciens, on se base sur le premier nom propre cité. Si le nom du théorème …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”