imported>Dexxor: EoM-Link aktualisert

2021-02-27T11:38:11Z

EoM-Link aktualisert

Neue Seite

Die '''sturmsche Kette''', benannt nach [[Charles-François Sturm|Jacques Charles François Sturm]], ist – ähnlich wie die [[Vorzeichenregel von Descartes]] – ein [[Mathematik|mathematisches]] Hilfsmittel, mit dem sich die Anzahl der [[Nullstelle]]n eines [[Reelle Zahl|reellen]] [[Polynom]]s in einem gegebenen [[Intervall (Mathematik)|Intervall]] berechnen lässt.

== Sturmsche Kette eines Polynoms ohne mehrfache Nullstellen ==

Zur Erklärung des Verfahrens wird zunächst ein Spezialfall betrachtet. Sei <math>f(x)</math> ein reelles Polynom ohne mehrfache Nullstellen. Die sturmsche Kette von <math>f(x)</math> ist eine endliche Folge von Polynomen <math>P_0(x), P_1(x), \ldots, P_k(x)</math>, wobei der [[Polynom#Definition|Grad]] dieser Polynome [[Monotone Abbildung|streng monoton]] abnimmt. <math>P_0(x)</math> ist das gegebene Polynom, <math>P_1(x)</math> seine [[Differentialrechnung|Ableitung]].

: <math>P_0(x) := f(x)\,</math>
: <math>P_1(x) := f'(x)\,</math>

Die weiteren Polynome der sturmschen Kette werden [[Rekursion|rekursiv]] durch eine Variante des [[Euklidischer Algorithmus|euklidischen Algorithmus]] zur Bestimmung des [[Größter gemeinsamer Teiler|größten gemeinsamen Teilers]] definiert. Für <math>n \ge 0</math> ist das Polynom <math>P_{n+2}(x)</math> eindeutig definiert durch die Gleichung

: <math>P_n(x) = Q_n(x) P_{n+1}(x) - P_{n+2}(x),\,</math>

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

Die Folge <math>P_0(x), P_1(x), \ldots, P_k(x)</math> endet in dem betrachteten Spezialfall (keine mehrfachen Nullstellen) mit einem konstanten Polynom <math>P_k(x)</math>. Für jede reelle Zahl <math>a</math> sei nun <math>\sigma(a)</math> die Zahl der [[Vorzeichenwechsel]] in der endlichen Zahlenfolge <math>P_0(a), P_1(a), \ldots, P_k(a)</math>.

Die '''Regel von Sturm''' besagt nun, dass die Zahl der Nullstellen von <math>f(x)</math> im halboffenen Intervall <math>(a,b]</math> (mit <math>a<b</math>) gleich <math>\sigma(a)-\sigma(b)</math> ist.

== Beispiel ==

Für das Polynom

: <math>P_0(x) = f(x) = x^4-5x^3+7x^2-5x+6\,</math>

soll die Anzahl der Nullstellen im halboffenen Intervall <math>(1,4]</math> ermittelt werden. Dazu wird zunächst die Ableitung gebildet:

: <math>P_1(x) = f'(x) = 4x^3-15x^2+14x-5\,</math>

Durch [[Polynomdivision]] erhält man die Beziehung

: <math>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)</math>,

also

: <math>P_2(x) = \frac{1}{16} \left(19x^2-10x-71\right)</math>.

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.

: <math>\tilde{P}_2(x) = 19x^2-10x-71</math>

Erneute Polynomdivision führt zu

: <math>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)</math>

und

: <math>P_3(x) = \frac{1}{361} (-8000x+19200)</math>.

Multiplikation mit <math>\frac{361}{1600}</math> ergibt das einfachere Polynom

: <math>\tilde{P}_3(x) = -5x+12</math>.

Entsprechend verläuft der letzte Durchgang des Verfahrens:

: <math>19x^2-10x-71 = \left(-\frac{19}{5}x-\frac{178}{25}\right) (-5x+12) + \frac{361}{25}</math>

: <math>P_4(x) = -\frac{361}{25}</math>
: <math>\tilde{P}_4(x) = -1</math>

Einsetzen der Zahl 1 ergibt nun:

: <math>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</math>

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

Entsprechend für die Zahl 4:

: <math>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</math>

Hier gibt es nur einen Vorzeichenwechsel: <math>\sigma(4) = 1</math>. Die Anzahl der Nullstellen im Intervall <math>(1;4]</math> hat also den Wert <math>\sigma(1)-\sigma(4) = 3-1 = 2</math>. 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 <math>g(x)</math> von <math>f(x)</math> und seiner Ableitung <math>f\,'(x)</math> ermitteln. Dividiert man <math>f(x)</math> durch <math>g(x)</math>, so erhält man ein neues Polynom, das die gleichen Nullstellen wie <math>f(x)</math> besitzt, aber keine mehrfachen Nullstellen. Die Anzahl der verschiedenen Nullstellen von <math>f(x)</math> in einem Intervall erhält man nun dadurch, dass man die sturmsche Kette des Polynoms <math>f(x)/g(x)</math> bildet und wie oben die Anzahl der Nullstellen dieses Polynoms bestimmt.

== Siehe auch ==
* [[Liste numerischer Verfahren#Nichtlineare Gleichungssysteme|Liste numerischer Verfahren zur Nullstellenbestimmung]]
* [[Nullstelle]]

== Literatur ==
* J. Stoer: ''Numerische Mathematik I''. 5. Auflage. Springer 1989, ISBN 3-540-51481-3, S. 277.

== Weblinks ==
* {{MathWorld |id=SturmTheorem |title=Sturm Theorem}}
* [https://encyclopediaofmath.org/wiki/Sturm_theorem Eintrag zu Sturmschen Ketten] in der Encyclopedia of Mathematics (Springer)
* [http://arndt-bruenner.de/mathe/scripts/anzahlnullstellen.htm Interaktive Beispiele und Rechner]

[[Kategorie:Theorie der Polynome]]
[[Kategorie:Numerische Mathematik]]

Sturmsche Kette - Versionsgeschichte

imported>Dexxor: EoM-Link aktualisert