Trennkreisverfahren

Das Trennkreisverfahren (engl. 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

Nach der verallgemeinerten Satzgruppe von Vieta sind die Koeffizienten eines normieren Polynoms

$p(x)=x^n+p_{n-1}x^{n-1}+\dots+p_1x+p_0$

bis auf ein Vorzeichen die elementarsymmetrischen Polynome in den Nullstellen $z_1,\dots,z_n$ des Polynoms. Es soll eine Zerlegung von p(x) in ein Produkt zweier Faktoren p(x)=f(x)g(x) gefunden werden, wobei f(x) die ersten k Nullstellen von p(x) als Nullstellen habe, d.h.

$p(x)=(x-z_1)(x-z_2)\cdots(x-z_n)$,

$f(x)=(x-z_1)(x-z_2)\cdots(x-z_k)$ und

$g(x)=(x-z_{k+1})\cdots(x-z_n)$.

Die Koeffizienten von f(x) und g(x) 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 K eine beschränkte Teilmenge der komplexen Zahlenebene $\mathbb C$ mit (stückweise) glatter Randkurve C. Dann gilt nach dem Residuensatz für jede in K holomorphe Funktion h

$\oint_C h(z)\frac{p'(z)}{p(z)}\,dz =2\pi i\sum_{\zeta\in K\,:\,p(\zeta)=0} \mathrm{Res}\left({\textstyle \frac{h(z)p'(z)}{p(z)}},\zeta\right) =2\pi i\sum_{\zeta\in K\,:\,p(\zeta)=0} h(\zeta)$.

Liegen die Nullstellen $z_1,\dots,z_k$ von p(x) im Inneren von K und alle anderen Nullstellen außerhalb von K, liegt insbesondere keine Nullstelle auf der Randkurve C, so gilt also

$\sum_{j=1}^kh(z_j)=\frac{1}{2\pi i}\oint_C h(z)\frac{p'(z)}{p(z)}\,dz$.

Die in den Koeffizienten von f(x) 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 k komplexen Zahlen $z_1,\dots,z_k$ kann durch einen polynomialen Ausdruck in den elementarsymmetrischen Polynomen dieser k Zahlen dargestellt werden. Dies gilt insbesondere für die Potenzsummen $s_m=z_1^m+z_2^m+\dots+z_k^m$. Umgekehrt können die elementarsymmetrischen Polynome und damit die Koeffizienten des Polynoms $f(x)=(x-z_1)(x-z_2)\cdot(x-z_k)$ aus den ersten k Potenzsummen gewonnen werden, die Umrechnungsformeln dafür sind die Newton-Identitäten. Die Potenzsummen selbst können mittels der Residuenformel zu h(z) = z^m, m=1,...,k durch ein Konturintegral gewonnen werden.

Der theoretische Faktorisierungsalgorithmus lautet also:

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

Approximative Faktorisierung und deren Verbesserung

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 F₀(x) und G₀(x) 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" $\textstyle p(x)-F_0(x)\,G_0(x)$ beliebig klein sein. Ist dieser Fehler von der Größenordnung ε > 0, so hat der Abstand der Nullstellen von p(x) zu den entsprechenden Nullstellen der Faktoren im ungünstigsten Fall die Größenordnung $\textstyle \sqrt[n]\varepsilon$. Die numerische Integration muss so ausgeführt werden, dass mit den Nullstellen von p(x) auch die entsprechenden Nullstellen von $\textstyle F_0(x)$ innerhalb von K und die von $\textstyle G_0(x)$ außerhalb von K liegen.

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

• $\textstyle F_1=F_0+\Delta F$ mit $\textstyle \Delta F=A_0(p-F_0G_0)\;\mod\;F_0$;
• $\textstyle G_1=G_0+\Delta G$ mit $\textstyle \Delta G=B_0(p-F_0G_0)\;\mod\;G_0$;
• $\textstyle A_1=A_0+\Delta A$ mit $\textstyle \Delta A=A_0(1-A_0F_1-B_0G_1)\;\mod\;F_0$
• $\textstyle B_1=B_0+\Delta B$ mit $\textstyle \Delta B=B_0(1-A_0F_1-B_0G_1)\;\mod\;G_0$

bestimmt werden, für welche die Koeffizienten der Fehlerausdrücke $p(x)-F_1(x)\,G_1(x)$ und $\textstyle 1-(A_1F_1+B_1G_1)$ die Größenordnung ε² besitzen.

Auffinden geeigneter Trennkreise

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 eine 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

Das Produkt p(x)p( − x) enthält nur gerade Potenzen von x. Ersetzt man darin x² durch x, so hat das entstehende Polynom $p_1(x)=(-1)^n p(\sqrt x)p(-\sqrt x)$ 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 p₁(x) mit einer wesentlich geringeren Genauigkeit der numerischen Integration als der für p₀(x) = p(x) notwendigen durchzuführen. Im Extremfall ist keine numerische Integration erforderlich (Malajovich). Mittels der angegebenen Variante des Newton-Verfahrens wird die Anfangsfaktorisierung von p₁(x) zu einer Faktorisierung mit kleinem Fehler p₁(x) − f₁(x)g₁(x) verbessert. Für die Faktoren von p(x) gilt $f_1(x^2)\approx(-1)^kf(x)f(-x)$ und $g_1(x^2)\approx(-1)^{n-k}g(x)g(-x)$, daher gilt

$\frac{f_1(x^2)}{p(-x)}\approx (-1)^k\frac{f(x)}{g(-x)}$.

Mit der Methode der Padé-Approximation für die aus der linken Seite entstehende (formale) Potenzreihe kann der gemeinsame Faktor f( − x) 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

• Schönhage, Arnold (1982): The fundamental theorem of algebra in terms of computational complexity. Preliminary Report, Math. Inst. Univ. Tübingen (1982), 49 pages. (ps.gz)
• Xavier Gourdon: Combinatoire, Algorithmique et Geometrie des Polynomes. Ecole Polytechnique, Paris 1996 (HTML).
• Pan, Victor Y. (1996). Optimal and nearly optimal algorithms for approximating polynomial zeros. Comput. Math. Appl., 31, 97–138.
• Malajovich, Gregorio; Zubelli, Jorge P. (1997): A fast and stable algorithm for splitting polynomials. Comput. Math Appl., 33, 1–23.
• Pan, Victor (1998). Algorithm for Approximating Complex Polynomial Zeros, Notizen eines Einführungsvortrags
• Pan, Victor (2002). Univariate Polynomials: Nearly Optimal Algorithms for Numerical Factorization and Root-finding

Weblinks

• Magma documentation. Real and Complex Fields: Element Operations.