Sturmsche Kette

Die sturmsche Kette, benannt nach Jacques Charles François Sturm, ist – ähnlich wie die Vorzeichenregel von Descartes – ein mathematisches Hilfsmittel, mit dem sich die Anzahl der Nullstellen eines reellen Polynoms in einem gegebenen Intervall berechnen lässt.

Sturmsche Kette eines Polynoms ohne mehrfache Nullstellen

Zur Erklärung des Verfahrens wird zunächst ein Spezialfall betrachtet. Sei $f(x)$ ein reelles Polynom ohne mehrfache Nullstellen. Die sturmsche Kette von $f(x)$ ist eine endliche Folge von Polynomen Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle P_{0}(x),P_{1}(x),\ldots ,P_{k}(x)} , wobei der Grad dieser Polynome streng monoton abnimmt. $P_{0}(x)$ ist das gegebene Polynom, $P_{1}(x)$ seine Ableitung.

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle P_{0}(x):=f(x)\,}

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle P_{1}(x):=f'(x)\,}

Die weiteren Polynome der sturmschen Kette werden rekursiv durch eine Variante des euklidischen Algorithmus zur Bestimmung des größten gemeinsamen Teilers definiert. Für $n\geq 0$ ist das Polynom $P_{n+2}(x)$ eindeutig definiert durch die Gleichung

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 P_n(x) = Q_n(x) P_{n+1}(x) - P_{n+2}(x),\,}

wenn man fordert, dass der Grad von 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 P_{n+2}(x)} kleiner sein soll als der von 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 P_{n+1}(x)} . (Diese Definition unterscheidet sich vom euklidischen Algorithmus nur durch das Minuszeichen anstelle eines Pluszeichens.)

Die Folge 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 P_0(x), P_1(x), \ldots, P_k(x)} endet in dem betrachteten Spezialfall (keine mehrfachen Nullstellen) mit einem konstanten Polynom 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 P_k(x)} . Für jede reelle Zahl 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} sei nun Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \sigma (a)} die Zahl der Vorzeichenwechsel in der endlichen Zahlenfolge 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 P_0(a), P_1(a), \ldots, P_k(a)} .

Die Regel von Sturm besagt nun, dass die Zahl der Nullstellen von 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 f(x)} im halboffenen Intervall 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,b]} (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 a<b} ) gleich 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 \sigma(a)-\sigma(b)} ist.

Beispiel

Für das Polynom

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 P_0(x) = f(x) = x^4-5x^3+7x^2-5x+6\,}

soll die Anzahl der Nullstellen im halboffenen Intervall 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 (1,4]} ermittelt werden. Dazu wird zunächst die Ableitung gebildet:

$P_{1}(x)=f'(x)=4x^{3}-15x^{2}+14x-5\,$

Durch Polynomdivision erhält man die Beziehung

$x^{4}-5x^{3}+7x^{2}-5x+6=\left({\frac {1}{4}}x-{\frac {5}{16}}\right)\left(4x^{3}-15x^{2}+14x-5\right)-{\frac {1}{16}}\left(19x^{2}-10x-71\right)$,

also

$P_{2}(x)={\frac {1}{16}}\left(19x^{2}-10x-71\right)$.

Hier und in den folgenden Rechenschritten ist es zweckmäßig, das Verfahren etwas abzuwandeln. Man multipliziert das erhaltene Polynom mit einer geeigneten positiven Zahl (in diesem Fall mit 16), um unangenehme Brüche zu vermeiden. Das Endergebnis wird dadurch nicht beeinflusst.

${\tilde {P}}_{2}(x)=19x^{2}-10x-71$

Erneute Polynomdivision führt zu

$4x^{3}-15x^{2}+14x-5=\left({\frac {4}{19}}x-{\frac {245}{361}}\right)\left(19x^{2}-10x-71\right)+{\frac {1}{361}}(8000x-19200)$

und

$P_{3}(x)={\frac {1}{361}}(-8000x+19200)$.

Multiplikation mit ${\frac {361}{1600}}$ ergibt das einfachere Polynom

${\tilde {P}}_{3}(x)=-5x+12$.

Entsprechend verläuft der letzte Durchgang des Verfahrens:

$19x^{2}-10x-71=\left(-{\frac {19}{5}}x-{\frac {178}{25}}\right)(-5x+12)+{\frac {361}{25}}$

$P_{4}(x)=-{\frac {361}{25}}$

${\tilde {P}}_{4}(x)=-1$

Einsetzen der Zahl 1 ergibt nun:

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle P_{0}(1)=4;\quad P_{1}(1)=-2;\quad {\tilde {P}}_{2}(1)=-62;\quad {\tilde {P}}_{3}(1)=7;\quad {\tilde {P}}_{4}(1)=-1}

Hier kommen genau drei Vorzeichenwechsel vor, nämlich zwischen 4 und −2, zwischen −62 und 7 sowie zwischen 7 und −1. Demzufolge gilt $\sigma (1)=3$.

Entsprechend für die Zahl 4:

$P_{0}(4)=34;\quad P_{1}(4)=67;\quad {\tilde {P}}_{2}(4)=193;\quad {\tilde {P}}_{3}(4)=-8;\quad {\tilde {P}}_{4}(4)=-1$

Hier gibt es nur einen Vorzeichenwechsel: $\sigma (4)=1$. Die Anzahl der Nullstellen im Intervall $(1;4]$ hat also den Wert $\sigma (1)-\sigma (4)=3-1=2$. In diesem Intervall existieren genau zwei Nullstellen (nämlich 2 und 3).

Sturmsche Kette eines beliebigen Polynoms

Den allgemeinen Fall, in dem das gegebene Polynom mehrfache Nullstellen haben darf, kann man auf den schon betrachteten Spezialfall zurückführen. Durch Anwendung des euklidischen Algorithmus lässt sich der größte gemeinsame Teiler $g(x)$ von $f(x)$ und seiner Ableitung $f\,'(x)$ ermitteln. Dividiert man $f(x)$ durch $g(x)$, so erhält man ein neues Polynom, das die gleichen Nullstellen wie $f(x)$ besitzt, aber keine mehrfachen Nullstellen. Die Anzahl der verschiedenen Nullstellen von $f(x)$ in einem Intervall erhält man nun dadurch, dass man die sturmsche Kette des Polynoms $f(x)/g(x)$ bildet und wie oben die Anzahl der Nullstellen dieses Polynoms bestimmt.

Siehe auch

• Liste numerischer Verfahren zur Nullstellenbestimmung
• Nullstelle

Literatur

• J. Stoer: Numerische Mathematik I. 5. Auflage. Springer 1989, ISBN 3-540-51481-3, S. 277.

Weblinks

• Eric W. Weisstein: Sturm Theorem. In: MathWorld (englisch).
• Eintrag zu Sturmschen Ketten in der Encyclopedia of Mathematics (Springer)
• Interaktive Beispiele und Rechner