Das Trennkreisverfahren (englisch splitting circle method) ist eine Methode zum numerischen Faktorisieren von Polynomen in einer Variablen mit komplexen Koeffizienten. Dieses Verfahren wurde 1982 von Arnold Schönhage in dem Artikel The fundamental theorem of algebra in terms of computational complexity (bisher nur im Netz veröffentlicht) vorgeschlagen und 1996 von Xavier Gourdon im Computeralgebrasystem PARI/GP und nachfolgend Magma implementiert. Seit der Mitte der 1990er Jahre wurden u. a. von V. Pan und G. Malajovich Verbesserungen des Algorithmus vorgeschlagen, die jedoch bisher nirgends implementiert wurden.

Durch fortgesetztes Zerlegen eines Polynoms in zwei nichttriviale Faktoren kann letztendlich eine Faktorisierung in Linearfaktoren erreicht werden. Dies ist gleichbedeutend zum Auffinden aller komplexen Nullstellen des Polynoms einschließlich der Angabe ihrer Vielfachheit.

Beim numerischen Rechnen mit einer fixierten endlichen Genauigkeit (s. Gleitkommazahl und Festkommazahl) ist es nicht möglich, zwischen einer mehrfach auftretenden Nullstelle und einer gleichmächtigen Gruppe nahe beieinander liegender Nullstellen zu unterscheiden. In diesem Fall ist das Ergebnis des Verfahrens eine Faktorisierung in

  • Linearfaktoren für ausreichend isolierte Nullstelle und
  • Faktoren höheren Grades für Gruppen von Nullstellen, die in der gewählten Genauigkeit nicht unterscheidbar sind.

Faktorisierung mit Hilfe des Residuenkalküls Bearbeiten

Nach dem verallgemeinerten Satz von Vieta sind die Koeffizienten eines normieren Polynoms

 

bis auf ein Vorzeichen die elementarsymmetrischen Polynome in den Nullstellen   des Polynoms. Es soll eine Zerlegung von   in ein Produkt zweier Faktoren   gefunden werden, wobei   die ersten   Nullstellen von   als Nullstellen habe, d. h.

 ,
  und
 .

Die Koeffizienten von   und   sind zu bestimmen, ohne als Zwischenschritt die Nullstellen bestimmen zu müssen. Dies ist mittels des Residuenkalküls und einer geeigneten Zerlegung der komplexen Ebene möglich. Eine Art der Zerlegung ist die in das Innere und Äußere eines beliebigen Kreises, der dann Trennkreis genannt wird.

Sei   eine beschränkte Teilmenge der komplexen Zahlenebene   mit (stückweise) glatter Randkurve  . Dann gilt nach dem Residuensatz für jede in   holomorphe Funktion  

 .

Liegen die Nullstellen   von   im Inneren von   und alle anderen Nullstellen außerhalb von  , liegt insbesondere keine Nullstelle auf der Randkurve  , so gilt also

 .

Die in den Koeffizienten von   auftretenden Koeffizienten sind Summen in gemischten Produkten der Nullstellen. Die eben angegebene Residuenformel ist daher nicht direkt anwendbar. Es ist aber möglich, die elementarsymmetrischen Polynome durch "ungemischte" Ausdrücke in den Nullstellen darzustellen. Jedes symmetrische Polynom in   komplexen Zahlen   kann durch einen polynomialen Ausdruck in den elementarsymmetrischen Polynomen dieser   Zahlen dargestellt werden. Dies gilt insbesondere für die Potenzsummen  . Umgekehrt können die elementarsymmetrischen Polynome und damit die Koeffizienten des Polynoms   aus den ersten   Potenzsummen gewonnen werden, die Umrechnungsformeln dafür sind die Newtonidentitäten. Die Potenzsummen selbst können mittels der Residuenformel zu   durch ein Konturintegral gewonnen werden.

Der theoretische Faktorisierungsalgorithmus lautet also:

  1. Finde eine glatt berandete beschränkte Teilmenge  , die einige, aber nicht alle Nullstellen von   enthält.
  2. Bestimme die Konturintegrale, welche die Potenzsummen der Nullstellen ergeben. Mit dem konstanten Polynom   kann auch die Anzahl der enthaltenen Nullstellen bestimmt werden.
  3. Bestimme mittels der Newton-Identitäten die Koeffizienten von  , mittels Polynomdivision die Koeffizienten von  .

Approximative Faktorisierung und deren Verbesserung Bearbeiten

In der numerischen Anwendung können die Konturintegrale nicht exakt bestimmt werden. Jedoch kann die numerische Integration mit beliebiger Genauigkeit vorgenommen werden, indem eine genügend kleine Schrittweite gewählt wird. Die mittels der Newton-Identitäten bestimmten genäherten Faktoren seien mit   und   bezeichnet. Für eine schnelle Ausführung der numerischen Integration bietet es sich an, sich auf Kreise in der komplexen Ebene zu beschränken, da dann die numerische Integration, d. h. die Bestimmung der Werte der Polynome an den Stützstellen sowie die Bestimmung der Integrale aus den Werten der Quotienten, mit Hilfe der schnellen Fourier-Transformation ausgeführt werden kann.

Bei genügend hoher Genauigkeit der numerischen Integration werden die Koeffizienten des "Fehlerpolynoms"   beliebig klein sein. Ist dieser Fehler von der Größenordnung  , so hat der Abstand der Nullstellen von p(x) zu den entsprechenden Nullstellen der Faktoren im ungünstigsten Fall die Größenordnung  . Die numerische Integration muss so ausgeführt werden, dass mit den Nullstellen von p(x) auch die entsprechenden Nullstellen von   innerhalb von K und die von   außerhalb von K liegen.

Ist die letzte Forderung erfüllt, so kann die Faktorisierung mittels einer Variante des Newtonverfahrens verbessert werden. Es folgt aus der letztgenannten Forderung, dass sowohl f(x) und g(x) als auch   und   teilerfremd sind. Es gibt nach dem erweiterten euklidischen Algorithmus Polynome a(x) und b(x) mit 1=af+bg. Seien   Polynome, für welche die Koeffizienten des Fehlerausdrucks   ebenfalls die Größenordnung   haben. Dann können verbesserte Polynome

  •   mit  ;
  •   mit  ;
  •   mit  
  •   mit  

bestimmt werden, für welche die Koeffizienten der Fehlerausdrücke   und   die Größenordnung   besitzen.

Auffinden geeigneter Trennkreise Bearbeiten

Der Kernpunkt des numerischen Verfahrens besteht im Auffinden geeigneter Trennkreise. Schönhage (1982) schlägt vor, den Betrag der größten Nullstelle zu schätzen und auf einen Kreis doppelten Radius drei gleichverteilte Punkte zu wählen. zusammen mit dem Koordinatenursprung werden diese dann als Mittelpunkt des Trennkreises getestet. Zu jedem dieser Testpunkte werden Schätzungen für die Abstände der Nullstellen des Polynoms bestimmt. Ergibt sich aus diesen Schätzungen ein Kreisring um den Testpunkt ohne enthaltene Nullstellen, so ist dies ein Kandidat für einen Trennkreis. Die relative Breite, d. h. das Verhältnis aus äußerem und inneren Radius, bestimmt die minimal notwendige Genauigkeit bei der numerischen Integration. Man wählt den besten Kandidaten nach den Kriterien der größten relativen Breite des Kreisrings und der gleichmäßigsten Aufteilung der Nullstellen auf das Innere und Äußere des Kreisrings.

Eine verbesserte Konstruktion der Menge der Testpunkte, die eine gleichmäßige Aufteilung der Nullstellen garantiert, wurde in Pan (1996,2002) vorgeschlagen. Eine weitere Variante, Gruppen trennbarer Nullstellen aufzufinden, sind Bisektions-Exklusionsverfahren (Weyl, Yakoubsohn).

Bessere Trennkreise mittels Gräffe-Iteration Bearbeiten

Das Produkt   enthält nur gerade Potenzen von x. Ersetzt man darin durch x, so hat das entstehende Polynom   Nullstellen in den Quadraten der Nullstellen von p. Dies ist die Grundlage des Dandelin-Gräffe-Verfahrens zur Nullstellenbestimmung. Hier wird es jedoch nur zur Schätzung der Beträge der Nullstellen verwendet. Gleichzeitig mit den Nullstellen werden auch die relativen Breiten nullstellenfreier Kreisringe quadriert. Wiederholt man dieses Quadrieren oft genug, so werden diese Kreisringe auch in den Schätzungen sichtbar.

Es ist möglich, die durch die Gräffe-Iteration verbreiterten Kreisringe zu benutzen, um die Anfangsfaktorisierung von   mit einer wesentlich geringeren Genauigkeit der numerischen Integration als der für   notwendigen durchzuführen. Im Extremfall ist keine numerische Integration erforderlich (Malajovich). Mittels der angegebenen Variante des Newton-Verfahrens wird die Anfangsfaktorisierung von   zu einer Faktorisierung mit kleinem Fehler   verbessert. Für die Faktoren von p(x) gilt   und  , daher gilt

 .

Mit der Methode der Padé-Approximation für die aus der linken Seite entstehende (formale) Potenzreihe kann der gemeinsame Faktor   auf der linken Seite numerisch gekürzt werden und damit (Approximationen für) Zähler und Nenner der rechten Seite bestimmt werden.

Entsprechend muss, wenn die Gräffe-Iteration mehrfach angewandt wird, die Hebung der Faktorisierung mehrfach ausgeführt werden.

Literatur Bearbeiten

Weblinks Bearbeiten