Sturms Satz - Sturm's theorem

In der Mathematik ist die Sturm-Folge eines univariaten Polynoms p eine Folge von Polynomen, die mit p und ihrer Ableitung durch eine Variante von Euklids Algorithmus für Polynome verbunden sind . Der Satz von Sturm drückt die Anzahl der verschiedenen reellen Wurzeln von p, die sich in einem Intervall befinden, als Anzahl der Vorzeichenwechsel der Werte der Sturm-Folge an den Grenzen des Intervalls aus. Auf das Intervall aller reellen Zahlen angewendet, ergibt sich die Gesamtzahl der reellen Wurzeln von p .

Während der Fundamentalsatz der Algebra ohne weiteres die Gesamtzahl der komplexen Wurzeln, mit Multiplizität gezählt , liefert, bietet er kein Verfahren zu deren Berechnung. Der Satz von Sturm zählt die Anzahl der verschiedenen reellen Nullstellen und ordnet sie in Intervallen. Durch Unterteilen der Intervalle, die einige Wurzeln enthalten, kann es die Wurzeln in beliebige kleine Intervalle isolieren, von denen jedes genau eine Wurzel enthält. Dies ergibt den ältesten Real-Wurzel-Isolationsalgorithmus und einen Wurzelsuchalgorithmus mit beliebiger Genauigkeit für univariate Polynome.

Für die Berechnung über die reellen Zahlen ist der Satz von Sturm weniger effizient als andere Methoden, die auf der Descartes-Vorzeichenregel basieren . Es funktioniert jedoch auf jedem reellen geschlossenen Körper und bleibt daher grundlegend für das theoretische Studium der rechnerischen Komplexität der Entscheidbarkeit und Quantoreneliminierung in der Theorie der reellen Zahlen erster Ordnung .

Die Sturm-Folge und das Sturm-Theorem sind nach Jacques Charles François Sturm benannt , der den Satz 1829 entdeckte.

Das Theorem

Die Sturm-Kette oder Sturm-Folge eines univariaten Polynoms P ( x ) mit reellen Koeffizienten ist die Folge von Polynomen mit ${\displaystyle P_{0},P_{1},\ldots ,}$

${\displaystyle {\begin{aligned}P_{0}&=P,\\P_{1}&=P',\\P_{i+1}&=-\operatorname {rem} (P_{i-1 },P_{i}),\end{ausgerichtet}}}$

für i ≥ 1 , wobei ‚P der IS - Derivat von P , und ist der Rest der euklidischen Division des durch die Länge der Sturm - Sequenz ist höchstens das Ausmaß der P . ${\displaystyle \operatorname {rem} (P_{i-1},P_{i})}$${\displaystyle P_{i-1}}$${\displaystyle P_{i}.}$

Die Anzahl der Vorzeichenvariationen bei ξ der Sturm-Folge von P ist die Anzahl der Vorzeichenwechsel – ohne Berücksichtigung von Nullen – in der Folge der reellen Zahlen

${\displaystyle P_{0}(\xi),P_{1}(\xi),P_{2}(\xi),\ldots.}$

Diese Anzahl von Vorzeichenvariationen wird hier mit V ( ξ ) bezeichnet .

Sturm-Theorem besagt , dass, wenn P ist ein Platz frei Polynom , die Anzahl der verschiedenen reeller Wurzeln von P in dem halboffenen Intervall ( a , b ] ist V ( a ) - V ( b ) (hier ein und b sind reelle Zahlen mit a < b ).

Der Satz erstreckt sich auf unbeschränkte Intervalle, indem das Vorzeichen bei +∞ eines Polynoms als das Vorzeichen seines führenden Koeffizienten (d. h. des Koeffizienten des Termes höchsten Grades) definiert wird. Bei –∞ ist das Vorzeichen eines Polynoms das Vorzeichen seines führenden Koeffizienten für ein Polynom geraden Grades und das entgegengesetzte Vorzeichen für ein Polynom ungeraden Grades.

Im Fall eines nicht quadratfreien Polynoms ist, wenn weder a noch b eine Mehrfachwurzel von p ist , V ( a ) − V ( b ) die Anzahl der verschiedenen reellen Wurzeln von P .

Der Beweis des Theorems ist wie folgt: Wenn der Wert von x von a auf b ansteigt , kann er eine Null von einigen ( i > 0 ) passieren ; wenn dies auftritt, ändert sich die Anzahl der Vorzeichenvariationen von nicht. Wenn x durch eine Wurzel geht, nimmt die Anzahl der Vorzeichenvariationen von 1 auf 0 ab. Dies sind die einzigen Werte von x, bei denen sich ein gewisses Vorzeichen ändern kann. ${\displaystyle P_{i}}$${\displaystyle (P_{i-1},P_{i},P_{i+1})}$${\displaystyle P_{0}=P,}$${\displaystyle (P_{0},P_{1})}$

Beispiel

Angenommen, wir möchten die Anzahl der Nullstellen in einem bestimmten Bereich für das Polynom finden . So ${\displaystyle p(x)=x^{4}+x^{3}-x-1}$

${\displaystyle {\begin{aligned}p_{0}(x)&=p(x)=x^{4}+x^{3}-x-1\\p_{1}(x)&=p '(x)=4x^{3}+3x^{2}-1\end{ausgerichtet}}}$

Der Rest der euklidischen Division von p ₀ durch p ₁ ist Multiplikation mit -1 erhalten wir ${\displaystyle -{\tfrac {3}{16}}x^{2}-{\tfrac {3}{4}}x-{\tfrac {15}{16}};}$

${\displaystyle p_{2}(x)={\tfrac {3}{16}}x^{2}+{\tfrac {3}{4}}x+{\tfrac {15}{16}}}$.

Als nächstes dividieren wir p ₁ durch p ₂ und multiplizieren den Rest mit −1 , wir erhalten

${\displaystyle p_{3}(x)=-32x-64}$.

Wenn wir nun p ₂ durch p ₃ teilen und den Rest mit −1 multiplizieren , erhalten wir

${\displaystyle p_{4}(x)=-{\tfrac {3}{16}}}$.

Da dies eine Konstante ist, ist die Berechnung der Sturm-Folge abgeschlossen.

Um die Anzahl der reellen Nullstellen von einem zu finden, muss man die Folgen der Vorzeichen dieser Polynome bei −∞ und ∞ auswerten , die jeweils (+, −, +, +, −) und (+, +, +, −, −) . Daher ${\displaystyle p_{0}}$

${\displaystyle V(-\infty)-V(+\infty)=3-1=2,}$

was zeigt, dass p zwei reelle Wurzeln hat.

Dies kann verifiziert werden, indem man feststellt, dass p ( x ) als ( x ² − 1) ( x ² + x + 1) faktorisiert werden kann , wobei der erste Faktor die Wurzeln –1 und 1 hat und der zweite Faktor keine reellen Wurzeln hat. Diese letzte Behauptung ergibt sich aus der quadratischen Formel und auch aus dem Satz von Sturm, der die Vorzeichenfolgen (+, –, –) bei −∞ und (+, +, –) bei +∞ angibt .

Verallgemeinerung

Sturm-Sequenzen wurden in zwei Richtungen verallgemeinert. Um jedes Polynom in der Folge zu definieren, verwendet Sturm das Negative des Rests der euklidischen Division der beiden vorhergehenden. Der Satz bleibt wahr, wenn man das Negative des Restes durch sein Produkt oder den Quotienten durch eine positive Konstante oder das Quadrat eines Polynoms ersetzt. Es ist auch nützlich (siehe unten), Folgen zu betrachten, bei denen das zweite Polynom nicht die Ableitung des ersten ist.

Eine verallgemeinerte Sturm-Folge ist eine endliche Folge von Polynomen mit reellen Koeffizienten

${\displaystyle P_{0},P_{1},\dots ,P_{m}}$

so dass

• die Grade nehmen nach dem ersten ab: für i = 2, ..., m ;${\displaystyle \deg P_{i}<\deg P_{i-1}}$
• ${\displaystyle P_{m}}$ hat keine wirkliche Wurzel oder ändert das Vorzeichen in der Nähe ihrer wirklichen Wurzeln nicht.
• wenn P _i ( ξ ) = 0 für 0 < i < m und ξ eine reelle Zahl ist, dann ist P _{i −1} ( ξ ) P _{i + 1} ( ξ ) < 0 .

Die letzte Bedingung impliziert, dass zwei aufeinanderfolgende Polynome keine gemeinsame reelle Wurzel haben. Insbesondere ist die ursprüngliche Sturm-Folge eine verallgemeinerte Sturm-Folge, wenn (und nur wenn) das Polynom keine mehrfache reelle Wurzel hat (sonst haben die ersten beiden Polynome ihrer Sturm-Folge eine gemeinsame Wurzel).

Bei der Berechnung der ursprünglichen Sturm-Folge durch euklidische Division kann es vorkommen, dass man auf ein Polynom trifft, das einen Faktor hat, der niemals negativ ist, wie oder . Setzt man in diesem Fall die Berechnung fort, wobei das Polynom durch seinen Quotienten durch den nichtnegativen Faktor ersetzt wird, erhält man eine verallgemeinerte Sturm-Folge, die auch zur Berechnung der Anzahl der reellen Nullstellen verwendet werden kann, da der Beweis des Sturmschen Satzes weiterhin gilt ( wegen der dritten Bedingung). Dies kann manchmal die Berechnung vereinfachen, obwohl es im Allgemeinen schwierig ist, solche nichtnegativen Faktoren zu finden, außer bei geraden Potenzen von x . ${\displaystyle x^{2}}$${\displaystyle x^{2}+1}$

Verwendung von Pseudo-Rest-Sequenzen

In der Computeralgebra haben die betrachteten Polynome ganzzahlige Koeffizienten oder können in ganzzahlige Koeffizienten transformiert werden. Die Sturm-Folge eines Polynoms mit ganzzahligen Koeffizienten enthält im Allgemeinen Polynome, deren Koeffizienten keine ganzen Zahlen sind (siehe Beispiel oben).

Um Berechnungen mit rationalen Zahlen zu vermeiden , besteht ein übliches Verfahren darin, die euklidische Division durch eine Pseudo-Division zu ersetzen, um polynomielle größte gemeinsame Teiler zu berechnen . Dies entspricht die Rest - Sequenz des zu ersetzen Euklidischen Algorithmus durch eine pseudo-Rest - Sequenz , Sequenz , eine Pseudo Rest eine Sequenz ist von Polynomen , so daß es Konstanten sind und derart , dass der Rest der euklidischen Division von ist durch (die verschiedenen Arten von pseudo -Restsequenzen werden durch die Wahl von definiert und werden typischerweise gewählt, um bei der euklidischen Division keine Nenner einzuführen, und sind ein gemeinsamer Teiler der Koeffizienten des resultierenden Rests; siehe Pseudo-Restsequenz für Details.) Zum Beispiel die Restsequenz des euklidischen Algorithmus ist eine Pseudo-Restfolge mit für jedes i , und die Sturm-Folge eines Polynoms ist eine Pseudo-Restfolge mit und für jedes i . ${\displaystyle p_{0},\ldots ,p_{k}}$${\displaystyle a_{i}}$${\displaystyle b_{i}}$${\displaystyle b_{i}p_{i+1}}$${\displaystyle a_{i}p_{i-1}}$${\displaystyle p_{i}.}$${\displaystyle a_{i}}$${\displaystyle b_{i};}$${\displaystyle a_{i}}$${\displaystyle b_{i}}$${\displaystyle a_{i}=b_{i}=1}$${\displaystyle a_{i}=1}$${\displaystyle b_{i}=-1}$

Zur Berechnung der größten gemeinsamen Teiler von Polynomen mit ganzzahligen Koeffizienten wurden verschiedene Pseudo-Restfolgen entwickelt, ohne Nenner einzuführen (siehe Pseudo-Restfolge ). Sie können alle zu verallgemeinerten Sturm-Folgen gemacht werden, indem man das Vorzeichen der dem Vorzeichen der entgegengesetzten wählt. Dies ermöglicht die Verwendung des Sturm-Theorems mit Pseudo-Rest-Folgen. ${\displaystyle b_{i}}$${\displaystyle a_{i}.}$

Wurzelisolierung

Für ein Polynom mit reellen Koeffizienten, Wurzel Isolierung besteht aus Feststellung für jede reale Wurzel, ein Intervall , das diese Wurzel enthält, und keine andere Wurzeln.

Dies ist nützlich für die Wurzelsuche , ermöglicht die Auswahl der zu findenden Wurzel und bietet einen guten Ausgangspunkt für schnelle numerische Algorithmen wie das Newton-Verfahren ; es ist auch nützlich, um das Ergebnis zu bestätigen, denn wenn die Newton-Methode außerhalb des Intervalls konvergiert, kann man sofort folgern, dass sie gegen die falsche Wurzel konvergiert.

Die Wurzelisolation ist auch für das Rechnen mit algebraischen Zahlen nützlich . Für die Berechnung mit algebraischen Zahlen besteht eine übliche Methode darin, sie als ein Paar aus einem Polynom, zu dem die algebraische Zahl eine Wurzel ist, und einem Isolationsintervall darzustellen. Kann zum Beispiel eindeutig repräsentiert werden durch${\displaystyle {\sqrt {2}}}$${\displaystyle (x^{2}-2,[0,2]).}$

Der Satz von Sturm bietet einen Weg zum Isolieren reeller Nullstellen, der weniger effizient ist (für Polynome mit ganzzahligen Koeffizienten) als andere Methoden, die die Descartes-Vorzeichenregel beinhalten . Es bleibt jedoch unter bestimmten Umständen nützlich, hauptsächlich für theoretische Zwecke, zum Beispiel für Algorithmen der reellen algebraischen Geometrie , die infinitesimale Zahlen beinhalten .

Um die reellen Nullstellen zu isolieren, geht man von einem Intervall aus, das alle reellen Nullstellen oder die interessierenden Nullstellen enthält (häufig sind in physikalischen Problemen nur positive Nullstellen interessant), und man berechnet und Zur Definition dieses Startintervalls kann man verwenden Grenzen an die Größe der Wurzeln (siehe Eigenschaften von Polynomwurzeln § Grenzen an (komplexen) Polynomwurzeln ). Dann teilt man dieses Intervall in zwei, indem man c in der Mitte von Die Berechnung von liefert die Anzahl der reellen Wurzeln in und und man kann dieselbe Operation in jedem Teilintervall wiederholen. Wenn man während dieses Prozesses auf ein Intervall trifft, das keine Wurzel enthält, kann es aus der Liste der zu berücksichtigenden Intervalle entfernt werden. Wenn man auf ein Intervall trifft, das genau eine Wurzel enthält, kann man aufhören, es zu teilen, da es sich um ein Isolationsintervall handelt. Der Prozess stoppt schließlich, wenn nur noch isolierende Intervalle übrig bleiben. ${\displaystyle (a,b]}$${\displaystyle V(a)}$${\displaystyle V(b).}$${\displaystyle (a,b].}$${\displaystyle V(c)}$${\displaystyle (a,c]}$${\displaystyle (c,b],}$

Dieser Isolationsprozess kann mit jedem Verfahren zum Berechnen der Anzahl von realen Wurzeln in einem Intervall verwendet werden. Theoretische Komplexitätsanalysen und praktische Erfahrungen zeigen, dass Methoden, die auf der Descartesschen Zeichenregel basieren, effizienter sind. Daraus folgt, dass Sturm-Sequenzen heutzutage nur noch selten zur Wurzelisolation verwendet werden.

Anwendung

Verallgemeinerte Sturm-Folgen ermöglichen das Zählen der Wurzeln eines Polynoms, wenn ein anderes Polynom positiv (oder negativ) ist, ohne diese Wurzeln explizit zu berechnen. Wenn man ein isolierendes Intervall für eine Wurzel des ersten Polynoms kennt, erlaubt dies auch, das Vorzeichen des zweiten Polynoms an dieser speziellen Wurzel des ersten Polynoms zu finden, ohne eine bessere Näherung der Wurzel zu berechnen.

Seien P ( x ) und Q ( x ) zwei Polynome mit reellen Koeffizienten, so dass P und Q keine gemeinsame Wurzel haben und P keine Mehrfachwurzeln hat. Mit anderen Worten, P und P'  Q sind teilerfremde Polynome . Diese Einschränkung beeinflusst die Allgemeingültigkeit des Folgenden nicht wirklich, da GCD- Berechnungen es ermöglichen, den allgemeinen Fall auf diesen Fall zu reduzieren, und die Kosten der Berechnung einer Sturm-Folge sind die gleichen wie die einer GCD.

Lassen W ( a ) bezeichnet die Anzahl der Vorzeichenänderungen an einem von einer Startsequenz Sturm generali von P und P‘  Q . Wenn a < b sind zwei reelle Zahlen, dann W ( a ) - W ( b ) ist die Anzahl der Wurzeln von P in dem Intervall , so dass Q ( a )> 0 minus der Anzahl der Wurzeln in der gleichen Intervall , so dass Q ( a ) < 0 . In Verbindung mit der Gesamtzahl der Wurzeln von P in dem gleichen Intervall von Sturm-Theorem gegeben, das gibt die Anzahl der Wurzeln von P , so dass Q ( a )> 0 und die Anzahl der Wurzeln von P , so dass Q ( a ) <0 . ${\displaystyle (a,b]}$

Siehe auch

Verweise

• Basu, Saugata; Pollack, Richard ; Roy, Marie-Françoise (2006). "Abschnitt 2.2.2". Algorithmen in der reellen algebraischen Geometrie (PDF) (2. Aufl.). Springer . S. 52–57. ISBN 978-3-540-33098-1.
• Sturm, Jacques Charles François (1829). "Mémoire sur la résolution des équations numériques". Bulletin des Sciences de Férussac . 11 : 419–425.
• Sylvester, JJ (1853). "Über eine Theorie der syzygetischen Beziehungen zweier rationaler Integralfunktionen, die eine Anwendung auf die Theorie der Sturm-Funktionen und die des größten algebraischen gemeinsamen Maßes umfasst" (PDF) . Phil. Übers. R. Soc. Lang . 143 : 407–548. doi : 10.1098/rstl.1853.0018 . JSTOR  108572 .
• Thomas, Joseph Miller (1941). „Der Satz von Sturm für mehrere Wurzeln“. Nationales Mathematik-Magazin . 15 (8): 391–394. doi : 10.2307/3028551 . JSTOR  3028551 . MR  0005945 .
• Heindel, Lee E. (1971), "Integer arithmetic algorithms for polynomial real zero choice", Proc. SYMSAC '71 : 415, doi : 10.1145/800204.806312 , MR  0300434
• Panton, Don B.; Verdini, William A. (1981). „Ein Fortran-Programm zur Anwendung des Sturm-Theorems beim Zählen der internen Renditen“. J. Finanz. Menge Anal . 16 (3): 381–388. doi : 10.2307/2330245 . JSTOR  2330245 .
• Akritas, Alkiviadis G. (1982). „Reflexionen über ein Paar Theoreme von Budan und Fourier“. Mathematik. Mag . . 55 (5): 292–298. doi : 10.2307/2690097 . JSTOR  2690097 . MR  0.678.195 .
• Petersen, Paul (1991). „Multivariate Sturm-Theorie“. Vorlesungsnotizen in Comp. Wissenschaft . Skript zur Vorlesung Informatik. 539 : 318–332. doi : 10.1007/3-540-54522-0_120 . ISBN 978-3-540-54522-4. MR  1.229.329 .
• Ja, Chee (2000). Grundlegende Probleme der algorithmischen Algebra . Oxford University Press . ISBN 0-19-512516-9.
• Rahman, QI; Schmeisser, G. (2002). Analytische Theorie der Polynome . Monographien der Londoner Mathematischen Gesellschaft. Neue Serien. 26 . Oxford: Oxford University Press . ISBN 0-19-853493-0. Zbl  1072.30006 .
• Baumol, William. Economic Dynamics , Kapitel 12, Abschnitt 3, "Qualitative Informationen zu realen Wurzeln"
• DG Hook und PR McAree, "Using Sturm Sequences To Bracket Real Roots of Polynomial Equations" in Graphic Gems I (A. Glassner Hrsg.), Academic Press, S. 416–422, 1990.