Zaehlt die Anzahl von Vorzeichenwechseln einer endlichen Liste von Zahlen eines geordneten Rings. Wechsel vonauf null zaehlen 2^(-1)/.

Berechnet zu einer rationalen Funktion R S^(-1), wobei R und S Polynome sind, ihre zugehoerige Sturmkette. Dabei soll der Grad von R kleinergleich dem von S sein, sonst wird eine Laufzeitausnahme geworfen.

Bestimmt zu einer rationalen Funktion R S^(-1) und Intervallgrenzen a und b ihren Cauchyindex.

Zwei Spezialfaelle des Index sind wichtig: Der Index von f' f^(-1), wobei f ein Polynom und f' seine Ableitung bezeichnet, ist die Anzahl der Nullstellen von f auf [a,b], wobei die Nullstellen ohne Vielfachheit gezaehlt werden und Nullstellen in den Randpunkten a und b 2^(-1) beitragen.

Der Index von Re gamma (Im gamma)^(-1) ist das doppelte der Windungszahl der Einschraenkung des polynomiellen Wegs gamma auf das Segment [a,b] der komplexen Zahlenebene, siehe windingNumber.

windingNumber z z' p berechnet die algebraische Windungszahl des Wegs  mit (t) = p(z + t (z' - z)) um den Ursprung. Dazu berechnen wir Sturmketten von Real- und Imaginaerteil von . Anders als bei analytischen Definitionen der Windungszahl sind Nullstellen von  zugelassen.

Siehe: Abschnitt 4.3 in [1].

rootsOnSegment z0 z1 p zaehlt die Anzahl der Nullstellen des Polynoms p im Segment [z0,z1] der komplexen Ebene. Dabei muss f keine bestimmten Voraussetzungen erfuellen.

Die Nullstellen werden ohne Vielfachheit gezaehlt, wobei Nullstelen auf den Ecken 2^(-1) beitragen.

Siehe: Korollar 3.8 von [1].

rootsOnRectangle z0 z1 p zaehlt die Anzahl der Nullstellen von p in dem Rechteck, dessen zwei gegenueberliegende Eckpunkte durch z0 und z1 gegeben sind. Das Polynom p darf dabei keine Nullstellen auf den vier Eckpunkten des Rechtecks besitzen, kann sonst aber beliebig sein.

Die Nullstellen im Inneren des Rechtecks zaehlen mit ihrer Vielfachheit, die auf den Kanten mit der Haelfte ihrer Vielfachheit. Mithilfe von rootsOnSegment kann man separat die Anzahl der Nullstellen auf den Kanten bestimmen und so auch ermitteln, wie viele Nullstellen im Inneren liegen.

Siehe: Theorem 5.1 von [1].

Datentyp fuer 0-Zellen (Punkte), 1-Zellen (Liniensegmente) und 2-Zellen (Rechtecke).

Liefert den Mittelpunkt einer Zelle.

Iterationsschritt des Unterteilungsverfahrens. Bestimmt zu einem gegebenen Polynom und einer Zelle diejenigen Unterzellen (also die beiden Haelften sowie dem Mittelpunkt einer 1-Zelle bzw. die vier Teilrechtecke und vier Teilkanten einer 2-Zelle), die Nullstellen des Polynoms enthalten.

Sollte schon eine Nullstelle gefunden worden sein, wird diese abdividiert, sodass zukuenftige Iterationen wegen des geringeren Grads effizienter ablaufen koennen.

Die genauen Voraussetzungen sind:

(A) Das Polynom besitzt keine Nullstellen auf den Eckpunkten der 1- und 2-Zellen.

(B) Das Polynom ist separabel.

Von divide wird dann eine Liste geliefert, die folgende Bedingungen erfuellt:

1. Die obigen beiden Voraussetzungen sind fuer die Teilzellen wieder erfuellt.
2. Jede Zelle enthaelt in ihrem Inneren mindestens eine Nullstelle des Inneren der Ausgangszelle.
3. Jede Nullstelle des Inneren der Ausgangszelle liegt in einem Inneren der Unterzellen.

Dabei ist das Innere einer 0-Zelle sie selbst, das einer 1- und 2-Zelle sie ohne ihren topologischen Rand.

Speziell werden daher fuer auf dem Rand einer 2-Zelle liegenden Nullstellen keine Unterzellen generiert. (Sonst koennte man mehrere Aufrufe von divide nicht gut zusammenfuehren, da dieselbe Nullstelle in mehreren Zellen liegen koennte.)

Bei sukzessiver Anwendung von divide erhaelt man irgendwann genau so viele Zellen, wie der Grad vom Polynom vorgibt. Sobald dieser Zustand erreicht ist, wird jede Zelle jeweils zu genau einer Unterzelle verfeinert: Denn wegen Bedingung (3) kann eine Zelle nicht verschwinden, und wegen Bedingung (2) kann eine Zeile nicht mehr als eine Nullstellen beinhaltende Unterzelle enthalten, da der Grad des Polynoms keine weiteren Nullstellen erlaubt.

Zu einem gegebenen separablen Polynom und einem Suchradius gibt subdivisions eine (unendliche) Folge von Iterierten zurueck, wobei jeder Iterationspunkt eine (endliche) Liste von Naeherungs-/Fehlerschrankenpaare an eine Nullstelle ist.

Bestimmt den Cauchyradius eines Polynoms, also eine Zahl R >= 0 derart, dass alle Nullstellen im offenen Ball mit Radius R um den Ursprung liegen.

Liefert zu einem gegebenen Polynom all seine Nullstellen. Das Polynom muss weder normiert noch separabel sein; allerdings werden die Nullstellen ohne Vielfachheiten zurueckgegeben.