Polynomial Root Isolation

by

Michael Arnold

Allgemeines zu Polynomen

• Ein Polynom vom Grad n hat die Form

• Es besitzt bei reellen Koeffizienten genau r reelle und 2s komplexe Nullstellen und es gilt: r + 2s = deg(P(x))

• Die Nullstellen eines Polynoms bezeichnet man auch als dessen “Wurzeln”

n

i

iixa0

naa ,..,0

Was wollen wir machen?

• Wir wollen alle reellen Nullstellen in getrennte Intervalle auf der x-Achse einschließen.

• Jedes Intervall darf also höchstens eine reelle Nullstelle enthalten.

Uspensky’s Algorithmus

• Benötigtes Theorem:– Descartes rule of sign (Definition, Beweis, Folgerungen)

• Algorithmus:– Nullstellenisolierung eines Polynoms für Nullstellen im Intervall (0,1)

– Terminierungsbeweis des Approximationsalgorithmus

– Verallgemeinerung des Algorithmus für alle reellen Nullstellen

Definition von V(P) und pos(P)

• Sei ein Polynom mit reellen Koeffizienten

• Eine Vorzeichenvariation von P ist ein Paar i, j mit so dass

und

• Mit V(P) bezeichnen wir die Anzahl der Vorzeichenvariationen von P

• Mit pos(P) bezeichnen wir die Anzahl der reellen Nullstellen von P. Dabei zählen wir mehrfache Nullstellen auch mehrfach.

n

i

iixaxP

0

)( Qai nji 0

0jiaa

0... 11 ji aa

Descartes rule of sign

• Sei P ein Polynom mit reellen Koeffizienten. Dann ist V(P) - pos(P) ein gerade natürliche Zahl.

• Folgerungen:

» Wenn V(P)=0 => pos(P)=0

» Wenn V(P)=1 => pos(P)=1

Nullstellenisolierung im Intervall (0,1)

• Sei P(x) ein Polynom mit reellen Koeffizienten und Grad n.

• Wir betrachten nun folgendes Polynom:

• Für x betrachten wir nun die Werte (0, ).

• 1/(1+x) bildet für x aus auf (0,1) ab.

• Mit (1+x)^n wird dafür gesorgt, dass Q(x) auch ein Polynom ist.

• =>Zu allen reellen positiven Nullstellen von Q(x) gehört eine reelle Nullstelle von P(x) im Intervall (0,1)

xPxxQ n

1

1)1()(

),0(

Beispiele

• V(Q)=0 => Die Funktion hat keine Nullstellen im Intervall (0,1)

123)( 23 xxxxP

xPxxQ

1

1)1()( 3

Beispiele

• V(Q)=1 =>Die Funktion hat genau eine Nullstelle im Intervall (0,1)

)3)(5.0()( xxxP

xPxxQ

1

1)1()( 2

Nullstellenisolierung im Intervall (0,1)

• Wenn V(Q)=1 oder V(Q)=0 ist, sind wir also fertig, weil wir wissen ob es genau eine oder keine reelle Nullstelle im von uns untersuchten Intervall existiert.

• Was passiert aber wenn V(Q)>1 ist?

• Angenommen V(Q)=2, dann könnte nach Descartes rule of sign pos(Q) = 0 oder 2 sein !

• Wenn V(Q)=3, dann könnte pos(Q)= 1 oder 3 sein!

• Usw....

Nullstellenisolierung im Intervall (0,1)

• Wenn V(Q)>1 ist prüfen wir zuerst ob P(1/2)=0 ist.

• Ist das der Fall, haben wir ein isoliertes Intervall gefunden, in dem eine reelle Nullstelle ist (nämlich [1/2,1/2]).

• Als nächstes berechnen wir P1(x) und P2(x) wie folgt:

• Die reellen Wurzeln von P1(x) in (0,1) haben eine zugehörige Wurzel bei P(x) in (0,1/2).

• Die reellen Wurzeln von P2(x) in (0,1) haben eine zugehörige Wurzel bei P(x) in (1/2,1).

• => Wir wenden diese Methode nun rekursiv auf P1(x) und P2(x) an und können somit unsere gewünschten Intervalle berechnen.

2)(1

xPxP

2

1)(2

xPxP

Terminiert der Algorithmus?

• Der Algorithmus terminiert, wenn das Polynom P(x) keine mehrfachen Nullstellen aufweist, es sei denn diese Wurzeln sind von der Form

• Mit i,k und

• In diesem Fall werden die Nullstellen vom Algorithmus direkt gefunden.

k

i

2

ki 21

Lemmata

• Wir suchen Schritt für Schritt die Wurzeln von P(x) im Intervall

• Es gilt: i,k und

• Wir bilden (0,1) auf I ab, indem wir x auf abbilden.

• Sei A(x)= und Q(x)=

• Lemma 1: Falls Q(x) keine Wurzeln innerhalb des Radius von 1/2 zentriert um den Punkt (1/2, 0) besitzt, so gilt V(Q(x))=0.

• Lemma 2: Falls Q(x) genau eine reelle Wurzel in (0,1) und keine komplexe Wurzeln in den offenen Scheiben um die Punkte besitz und durch den Ursprung gehen, (also Radius haben,) dann ist V(Q(x))=1.

kk

iiI

2

1,

2 ki 20

k

xi

2

k

xiP

2

xx n

1

1)1(

322

1 i

3

1

Terminierungsbeweis

• Wenn Lemma 1 oder Lemma 2 erfüllt sind, folgt aus Descartes rule of sign die Terminierung des Algorithmus.

• Wir müssen also zeigen, dass wenn das Intervall I klein genug ist, die

Bedingungen für eines der Lemmata auf jeden Fall erfüllt sind.

Terminierungsbeweis

• Sei

• Falls gilt für unser Polynom Q(x):

• Somit haben die Wurzeln von Q(x) mindestens Abstand 2.

},0)(,|:min{| 2121 ii PC

22

k

},2)(2

0)(,|:min{| 2121

iPi

PQC ik

iiki

ii

},0)(,|:22min{| 2121 iikk PCii

22 k

Terminierungsbeweis

• Falls Q(x) keine Wurzeln mit Radius 1/2 um den Punkt (1/2,0) besitzt, ist die Bedingung für Lemma 1 erfüllt.

• Falls Q(x) genau eine Nullstelle in diesem Bereich besitzt, muss es eine reelle Wurzel sein. Wären in diesem Bereich komplexe Wurzeln, würden sie in konjugierten Paaren auftreten und müssten beide in dem Bereich liegen. Somit sind die Bedingungen für Lemma 2 erfüllt.

• Der Fall das mehrere Nullstellen in dem Bereich auftreten ist nicht möglich, da sonst der Abstand zwischen den Nullstellen zu klein wäre. Dieser Fall kann also nicht eintreten.

• Wenn aber mehrfache Nullstellen auftreten, können die Bedingungen der Lemmata nicht mehr erfüllt werden.

• => Terminierung des Algorithmus für Polynome ohne mehrfache Nullstellen mit Außnahme mehrfacher Nullstellen die direkt gefunden werden können (, also der Form i/(2^k)).

Verallgemeinerung des Algorithmus

• Wir wollen zuerst ein B finden für das alle reellen Nullstellen des zu untersuchenden Polynoms P vom Grad n im Intervall [-B,B] liegen müssen.

• Wie bestimmen wir nun ein geeignetes B?

• Wir testen einfach für k=1,2,3,... Bis folgende Gleichung erfüllt ist:

• Unser gesuchtes B hat hier folgende Form: B=2^k

• Die Gleichung ist genau dann erfüllt, wenn die höchste x-Potenz alle anderen x-Potenzen dominiert und deshalb keine Nullstellen mehr auftreten können für x-Einsetzungen kleiner -B oder größer B.

1

0

0)2(||)2(||n

i

iki

nkn aa

123)( 23 xxxxP

Verallgemeinerung des Algorithmus

• Nun sei das Polynom

• Alle Wurzeln von Pa(x) liegen jetzt also im Intervall [-1/4,1/4]

• Eine reelleWurzel w von Pa(x) gehört also zu der reellen Wurzel 4Bw von P(x)

)4()( BxPxPa

1327684096)44()( 23 xxxxPxPa

Verallgemeinerung des Algorithmus

• Nun sei das Polynom

• Alle Wurzeln von Pb(x) liegen jetzt also im Intervall [1/4, 3/4]

• Die reelle Wurzel w von Pb(x) gehört also zu der reellen Wurzel w-1/2 von Pa(x)

2

1)( xPxP ab

6873808691240962

1)( 23

xxxxPxP ab

Verallgemeinerung des Algorithmus

• Wir können nun unseren Algorithmus auf Pb(x) anwenden und erhalten nach der Korrektur unserer Intervallgrenzen die gewünschten Intervalle für unser Polynom P(x).

Rekursionsübersicht für Intervallgrenzen

... ... ... ...