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.
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 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)=xn+pn−1xn−1+⋯+p1x+p0p(x)=x^n+p_{n-1}x^{n-1}+\dots+p_1x+p_0
bis auf ein Vorzeichen die elementarsymmetrischen Polynome in den Nullstellen z1,…,znz_1,\dots,z_n des Polynoms. Es soll eine Zerlegung von p(x)p(x) in ein Produkt zweier Faktoren p(x)=f(x)g(x)p(x)=f(x)g(x) gefunden werden, wobei f(x)f(x) die ersten kk Nullstellen von p(x)p(x) als Nullstellen habe, d.h.
p(x)=(x−z1)(x−z2)⋯(x−zn)p(x)=(x-z_1)(x-z_2)\cdots(x-z_n),
f(x)=(x−z1)(x−z2)⋯(x−zk)f(x)=(x-z_1)(x-z_2)\cdots(x-z_k) und
g(x)=(x−zk+1)⋯(x−zn)g(x)=(x-z_{k+1})\cdots(x-z_n).
Die Koeffizienten von f(x)f(x) und g(x)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 KK eine beschränkte Teilmenge der komplexen Zahlenebene C\mathbb C mit (stückweise) glatter Randkurve CC. Dann gilt nach dem Residuensatz für jede in KK holomorphe Funktion hh
∮Ch(z)p′(z)p(z) dz=2πi \oint_C h(z)\dfrac{p'(z)}{p(z)}\,dz =2\pi i ∑ζ∈K : p(ζ)=0Res(h(z)p′(z)p(z),ζ)=2πi∑ζ∈K : p(ζ)=0h(ζ) \sum\limits_{\zeta\in K\,:\,p(\zeta)=0} \mathrm{Res}\left({\dfrac{h(z)p'(z)}{p(z)}},\zeta\right) =2\pi i\sum\limits_{\zeta\in K\,:\,p(\zeta)=0} h(\zeta) .
Liegen die Nullstellen z1,…,zkz_1,\dots,z_k von p(x)p(x) im Inneren von KK und alle anderen Nullstellen außerhalb von KK, liegt insbesondere keine Nullstelle auf der Randkurve CC, so gilt also
∑j=1kh(zj)=12πi∮Ch(z)p′(z)p(z) dz\sum\limits_{j=1}^kh(z_j)=\dfrac{1}{2\pi i}\oint_C h(z)\dfrac{p'(z)}{p(z)}\,dz.
Die in den Koeffizienten von f(x)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 kk komplexen Zahlen z1,…,zkz_1,\dots,z_k kann durch einen polynomialen Ausdruck in den elementarsymmetrischen Polynomen dieser kk Zahlen dargestellt werden. Dies gilt insbesondere für die Potenzsummen sm=z1m+z2m+⋯+zkms_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−z1)(x−z2)⋅(x−zk)f(x)=(x-z_1)(x-z_2)\cdot(x-z_k) aus den ersten kk Potenzsummen gewonnen werden, die Umrechnungsformeln dafür sind die Newton-Identitäten. Die Potenzsummen selbst können mittels der Residuenformel zu h(z)=zm h(z)=z^m , m=1,…,km=1,\dots ,k durch ein Konturintegral gewonnen werden.
Der theoretische Faktorisierungsalgorithmus lautet also:
  1. Finde eine glatt berandete beschränkte Teilmenge KK, die einige, aber nicht alle Nullstellen von p(x)p(x) enthält.
  2. Bestimme die Konturintegrale, welche die Potenzsummen der Nullstellen ergeben. Mit dem konstanten Polynom h(z)=1h(z)=1 kann auch die Anzahl der enthaltenen Nullstellen bestimmt werden.
  3. Bestimme mittels der Newton-Identitäten die Koeffizienten von f(x)f(x), mittels Polynomdivision die Koeffizienten von g(x)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 F0(x)F_0(x) und G0(x)G_0(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" p(x)−F0(x) G0(x)p(x)-F_0(x)\,G_0(x) beliebig klein sein. Ist dieser Fehler von der Größenordnung ε>0\varepsilon>0, so hat der Abstand der Nullstellen von p(x)p(x) zu den entsprechenden Nullstellen der Faktoren im ungünstigsten Fall die Größenordnung εn\sqrtN{n}\varepsilon. Die numerische Integration muss so ausgeführt werden, dass mit den Nullstellen von p(x)p(x) auch die entsprechenden Nullstellen von F0(x)F_0(x) innerhalb von KK und die von G0(x)\textstyle G_0(x) außerhalb von KK 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)f(x) und g(x)g(x) als auch F0(x)F_0(x) und G0(x)G_0(x) teilerfremd sind. Es gibt nach dem erweiterten euklidischen Algorithmus Polynome a(x)a(x) und b(x)b(x) mit 1=af+bg1=af+bg. Seien A0(x),B0(x)A_0(x),B_0(x) Polynome, für welche die Koeffizienten des Fehlerausdrucks 1−(A0F0+B0G0)1-(A_0F_0+B_0G_0) ebenfalls die Größenordnung ε>0\varepsilon>0 haben. Dann können verbesserte Polynome
  • F1=F0+ΔF\textstyle F_1=F_0+\Delta F mit ΔF=A0(p−F0G0)  mod    F0\textstyle \Delta F=A_0(p-F_0G_0)\;\mod\;F_0;
  • G1=G0+ΔG\textstyle G_1=G_0+\Delta G mit ΔG=B0(p−F0G0)  mod    G0\textstyle \Delta G=B_0(p-F_0G_0)\;\mod\;G_0;
  • A1=A0+ΔA\textstyle A_1=A_0+\Delta A mit ΔA=A0(1−A0F1−B0G1)  mod    F0\textstyle \Delta A=A_0(1-A_0F_1-B_0G_1)\;\mod\;F_0
  • B1=B0+ΔB\textstyle B_1=B_0+\Delta B mit ΔB=B0(1−A0F1−B0G1)  mod    G0\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)−F1(x) G1(x)p(x)-F_1(x)\,G_1(x) und 1−(A1F1+B1G1)\textstyle 1-(A_1F_1+B_1G_1) die Größenordnung ε2\varepsilon^2 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)p(x)p(-x) enthält nur gerade Potenzen von xx. Ersetzt man darin x2x^2 durch xx, so hat das entstehende Polynom p1(x)=(−1)np(x)p(−x)p_1(x)=(-1)^n p(\sqrt x)p(-\sqrt x) Nullstellen in den Quadraten der Nullstellen von pp. 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 p1(x)p_1(x) mit einer wesentlich geringeren Genauigkeit der numerischen Integration als der für p0(x)=p(x)p_0(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 p1(x)p_1(x) zu einer Faktorisierung mit kleinem Fehler p1(x)−f1(x)g1(x)p_1(x)-f_1(x)g_1(x) verbessert. Für die Faktoren von p(x) gilt f1(x2)≈(−1)kf(x)f(−x)f_1(x^2)\approx(-1)^kf(x)f(-x) und g1(x2)≈(−1)n−kg(x)g(−x)g_1(x^2)\approx(-1)^{n-k}g(x)g(-x), daher gilt
f1(x2)p(−x)≈(−1)kf(x)g(−x)\dfrac{f_1(x^2)}{p(-x)}\approx (-1)^k\dfrac{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)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.
  • Xavier Gourdon: Combinatoire, Algorithmique et Geometrie des Polynomes. Ecole Polytechnique, 1996
  • Pan, Victor Y. (1996). 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 (2002). Univariate Polynomials: Nearly Optimal Algorithms for Numerical Factorization and Root-finding
 
 

Die Logik ist die Hygiene, deren sich der Mathematiker bedient, um seine Gedanken gesund und kräftig zu erhalten.

Hermann Weyl

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Trennkreisverfahren aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
Datenschutzerklärung

 

Numerische Verfahren