Zählen der Anzahl der reellen Wurzeln eines Polynoms

Der beste Weg, dies zu lösen, ist die Verwendung des Satzes von Sturm . Dies ergibt einen Algorithmus zum Berechnen der Anzahl unterschiedlicher reeller Wurzeln eines beliebigen Polynoms. Die Wikipedia-Seite ist ziemlich gut, aber ich werde die Methode hier skizzieren.

Lassen$f(x)$ein Polynom sein. Wir definieren eine Sequenz wie folgt:

Angenommen, wir möchten wissen, wie viele Wurzeln$f(x)=x^3+2x+1$hat mit dieser Methode - natürlich wissen wir, dass die Antwort lautet$1$, aber wir sollten überprüfen. Wir erhalten folgende Kette:

Für jede reelle Zahl$a$, wir definieren$V(a)$die Anzahl der Vorzeichenwechsel in der Folge sein$P_0(a),P_1(a),P_2(a),P_3(a)$, wobei wir alle Nullen ignorieren. Angenommen beides nicht$a$oder$b$selbst Wurzeln sind, besagt Sturms Theorem$V(a)-V(b)$ist die Anzahl der reellen Wurzeln dazwischen$a$und$b$.

Beachten Sie, dass$V(-\infty)=\lim_{a\rightarrow-\infty}V(a)$oder$V(\infty)=\lim_{b\rightarrow\infty}V(b)$sind leicht zu berechnen, indem man sich die führenden Terme jedes Polynoms ansieht. Hier haben wir zum Beispiel das$V(-\infty)=2$seit, hin$-\infty$wir haben das$P_0$neigt dazu$-\infty$,$P_1$zu$\infty$,$P_2$zu$\infty$und$P_3$negativ ist - also zwei Vorzeichenwechsel. Dann$V(\infty)=1$da$P_0$und$P_1$sind positiv in der Nähe$\infty$und$P_2$und$P_3$sind negativ. Dieses Polynom hat$V(-\infty)-V(\infty)=1$Wurzeln, wie erwartet, da es sich um eine zunehmende Funktion handelt.

Dies kann von Hand etwas mühsam sein, aber es funktioniert immer für jedes Polynom.

Der einzige Trick, um dies zu beweisen, besteht zumindest im quadratfreien Fall darin, zu überlegen, was mit Vorzeichenänderungen in dieser Folge passiert, wenn man sich entlang der reellen Linie bewegt: Die Anzahl der Vorzeichenänderungen kann sich nur in der Nähe einer Wurzel von einer der ändern Polynome. Beachten Sie jedoch, dass für einige Polynome$c$, haben wir folgende Beziehung:

Ihr Polynom ist ein Faktor$X^7-1 = (X-1)(X^6+X^5+X^4+X^3+X^2+X+1)$und so sind die Nullen die 7. Wurzeln der Einheiten. Es gibt nur eine siebte Einheitswurzel, die real ist, und das ist$1$. Die anderen sind alle komplex.

Obwohl diese Methode nicht garantiert bei allen Polynomen funktioniert, ist sie manchmal überraschend effektiv: Beachten Sie das

Hinweis:$x=0$ist keine Lösung, damit wir schreiben können

Es gibt eine leichte Mehrdeutigkeit in Ihrer Problemstellung. "Die Anzahl der echten Wurzeln" kann mehrere Wurzeln mit Multiplizität zählen oder nicht. Zum Beispiel$x^2 = (x-0)^2$, hat zwei ununterscheidbare Wurzeln bei$0$, also müssen Sie entscheiden, wie Sie wiederholte Wurzeln berücksichtigen.

Sie könnten dies mit der Vorzeichen- und Halbierungsregel von Descartes fortsetzen, indem Sie Ihr Polynom horizontal verschieben. Aber Sturm-Sequenzen sind ein viel besserer Weg nach vorne.

Unabhängig von Ihrer Wahl sollten Sie dafür sorgen, dass alle Wurzeln des Polynoms einfache Wurzeln sind (dh alle haben Multiplizität$1$). Also erkennen und eliminieren wir zuerst wiederholte Wurzeln. Berechnen

Nun gibt es zwei Möglichkeiten weiter vorzugehen.

Methode 1:

Verschieben Sie Ihr Polynom nach links und rechts und verwenden Sie die Vorzeichenregel von Descarte, um herauszufinden, wie viele Wurzeln links und rechts von Null liegen. Zum Beispiel,

Nun schau zu$h'(x)$auf dem Intervall$(-1/2,0)$. Wir wollen wissen, ob$h'$irgendwelche Wurzeln in diesem Intervall hat, ihre Multiplizität und ihre Orte, so dass wir bestimmen können, ob der Graph von$h$sieht eher aus$\pm(x^2+1)$oder$\pm(x^2-1)$in diesem Intervall. (Ich habe keinen Versuch unternommen, diese zu skalieren und auf dieses Intervall zu verschieben. Stattdessen wollen wir wissen, ob$h$hat null oder zwei Wurzeln und wir werden es herausfinden$h$in diesem Intervall konkav nach oben oder unten konkav ist.) Wenn Sie dies tatsächlich tun, kann dies zu einem schrecklichen Baum von bedingten Fällen führen.

Methode 2:

Verwenden Sie den Satz von Sturm . Konstruieren Sie die (Sturm-) Restfolge, indem Sie den Euklidischen Divisionsalgorithmus anwenden$h$und$h'$. Lassen$V(\xi)$sei die Anzahl der Vorzeichenwechsel (ohne Nullen) in der Sturm-Folge, wenn ihre Mitglieder ausgewertet werden$x = \xi$. Dann$V(ab) - V(b)$ist die Anzahl der reellen Wurzeln im Intervall$(a,b]$.

Hinweis:

Also die Wurzeln von$f(x)=0$sind$e^{2m\pi i/7}$wo$m\equiv1,2,3,4,5,6\pmod7$

Nun der Imaginärteil von$e^{2m\pi i/7}$wird sein$0$wenn$2m\pi/7=n\pi$für eine ganze Zahl$n$

$\implies m=\dfrac{7n}2\implies n$muss eben sein$=2r$(sagen)$\implies7\mid m$

was einen Widerspruch ergibt.

Die Regel von Descarte gibt Ihnen nur eine Obergrenze. Die Methode, nach der Sie suchen, ist die der Sturm-Folgen (dh wenden Sie den euklidischen Algorithmus auf das Paar an$(f(x),f'(x))$und zähle die Vorzeichenwechsel über die Zwischenpolynome hinweg).

Wenn Sie die Anzahl der echten Wurzeln in möchten$(-\infty,\infty)$, genügt es, die Vorzeichen der führenden Terme zu beachten.