Weierstraß-(Durand-Kerner)-Verfahren

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Das Weierstraß-(Durand-Kerner)-Verfahren (W-(D-K)-Verfahren) ist ein iteratives Verfahren zur simultanen Bestimmung aller Nullstellen eines univariaten Polynoms. Es ist benannt nach Karl Weierstraß, der es als Teil eines Beweises zum Fundamentalsatz der Algebra zwischen 1859 und 1891 entwickelte, sowie E. Durand und Immo Kerner, die es 1960 bzw. 1966 in einen Computeralgorithmus überführten.

Das Verfahren[Bearbeiten | Quelltext bearbeiten]

Es sei ein normiertes univariates Polynom mit komplexen Koeffizienten und mit führendem Koeffizienten 1. Dieses hat nach dem Fundamentalsatz der Algebra genau n Nullstellen und kann in Linearfaktoren zerlegt werden,

Aus dieser Formel kann jede der Nullstellen formal isoliert werden, es gilt

Diese Formel kann als triviale Fixpunktiteration verstanden werden, die Iteration

wird offensichtlich nach dem ersten Iterationsschritt in der Nullstelle stationär.

Ersetzt man nun in der Iterationsvorschrift die anderen Nullstellen durch gute Näherungen, so bleibt ein Fixpunkt und jede Iteration, die in der Nähe dieser Nullstelle startet, konvergiert auch gegen diese. Die Iteration des W-(D-K)-Verfahrens ergibt sich, wenn nun für alle Nullstellen gleichzeitig mittels dieser Iterationsvorschrift Näherungsfolgen bestimmt werden, und die jeweils bestimmte Näherung einer Nullstelle sofort in die Bestimmung der nächsten Näherungen der anderen Nullstellen eingeht.

Am Anfang eines jeden Iterationsschrittes stehen n paarweise verschiedene komplexe Zahlen . Für den ersten Schritt können diese Zahlen zufällig, aber paarweise verschieden gewählt werden, in späteren Schritten stehen diese Zahlen für Approximationen der Nullstellen von p(X).

Dem Tupel wird das Polynom zugeordnet, das diese komplexen Zahlen als Nullstellen hat. Von diesem Polynom wird die Ableitung nach der Unbestimmten X bestimmt. Es gelten

und

Aus p(X) und der Ableitung werden die Weierstraß-Korrekturen , k = 1, ..., n bestimmt und das korrigierte Tupel als Ergebnis und Eingabe des nächsten Iterationsschrittes erhalten.

Die Iteration kann z. B. abgebrochen werden, wenn die Korrektur eine zuvor festgelegte Rückgabegenauigkeit unterschreitet. (Die Rechengenauigkeit sollte etwas höher als diese Rückgabegenauigkeit sein.)

Varianten des Verfahrens[Bearbeiten | Quelltext bearbeiten]

Die oben angegeben Herleitung bestimmt die neuen Approximationen gleichzeitig, parallel, aus den alten Approximationen. In der einfachsten Implementierung der Methode werden aber die Aufdatierungen und damit die neuen Approximationen nacheinander, sequentiell, bestimmt. Daher bietet sich die Idee an, jede neue Approximation einer Nullstelle sofort anstelle der alten zu verwenden. Dieser Unterschied zwischen paralleler und sequentieller Aufdatierung entspricht dem analogen Vorgehen im Jacobi- und Gauß-Seidel-Verfahren zur iterativen Lösung linearer Gleichungssysteme.

Die sequentielle Variante konvergiert in vielen Fällen schneller, jedoch ist dieser Geschwindigkeitsvorteil schwer theoretisch zu fassen. Die parallele Variante erlaubt bei hohen Polynomgraden die Anwendung von Verfahren schneller Polynommultiplikation, wie Karatsuba oder Schönhage-Strassen in der Berechnung der Aufdatierung.

Beispiel[Bearbeiten | Quelltext bearbeiten]

Zu lösen sei die kubische Gleichung . Als Starttupel werde mit dem komplexen Parameter gewählt. Es ergeben sich die folgenden ersten Iterationsschritte für die parallele Variante der Iteration

It.-Nr. z1 z2 z3
0 +1.000000+0.000000i +0.400000+0.900000i −0.650000+0.720000i
1 +1.360773+2.022230i −1.398213−0.693566i +3.037440−1.328664i
2 +0.980963+1.347463i −0.335252−0.644069i +2.354289−0.703394i
3 +0.317181+0.936495i +0.490016−0.966141i +2.192804+0.029647i
4 +0.209016+1.572742i +0.041206−1.527519i +2.749778−0.045223i
5 +0.212971+1.394827i +0.184678−1.384565i +2.602351−0.010262i
6 +0.206531+1.374879i +0.206001−1.374653i +2.587468−0.000226i
7 +0.206300+1.374730i +0.206299−1.374730i +2.587401−0.000000i
8 +0.206299+1.374730i +0.206299−1.374730i +2.587401+0.000000i

und für die sequentielle Variante der Iteration

It.-Nr. z1 z2 z3
0 +1.000000+0.000000i +0.400000+0.900000i −0.650000+0.720000i
1 +1.360773+2.022230i −0.365804+2.483787i −2.385807−0.028361i
2 +2.659661+2.713714i +0.597676+0.822483i −0.631985−1.671566i
3 +2.270389+0.387972i +0.131179+1.312808i +0.282054−1.501550i
4 +2.542817−0.015337i +0.204444+1.371609i +0.205573−1.372072i
5 +2.587418−0.000012i +0.206300+1.374733i +0.206299−1.374730i
6 +2.587401−0.000000i +0.206299+1.374730i +0.206299−1.374730i
7 +2.587401−0.000000i +0.206299+1.374730i +0.206299−1.374730i

In den ersten 4 Iterationen beider Varianten wird das Tripel scheinbar chaotisch bewegt, ab dem 5 Schritt bleiben zunehmend mehr Dezimalstellen konstant, Iteration 8 im parallelen bzw. 7 im sequentiellen Fall bestätigen die Korrektheit von Iteration 7 bzw. 6 im Rahmen der angegebenen Genauigkeit. Dieses allgemeine Verhalten ist charakteristisch für diese Methode.

Als Gleichung 3. Grades mit reellen Koeffizienten hat p(X) eine reelle Nullstelle und ein konjugiertes Paar komplexer Nullstellen. Die Näherungen erfüllen dieses Muster. Nach der Satzgruppe von Vieta muss z. B. die Summe aller Nullstellen dem Negativen des Koeffizienten zweithöchsten Grades entsprechen, also 3 sein. Auch dies bestätigt sich in den Näherungen.

Begründung als Newton-Verfahren[Bearbeiten | Quelltext bearbeiten]

Die – wenigstens lokale – Konvergenz der Weierstraß-Iteration ergibt sich aus ihrer Interpretation als mehrdimensionales Newton-Verfahren. Das Gleichungssystem dazu ergibt sich aus dem Vergleich der Koeffizienten gleichen Grades in der angestrebten Identität

Da die Polynome auf beiden Seiten normiert sind (der höchstgradige Koeffizient ist 1), ist die Identitat im Grad n trivial und es ergeben sich n Gleichungen für die n Unbekannten.

Im Allgemeinen ist diese Identität nicht erfüllt. Die Korrektur in jedem Schritt der Newton-Iteration ergibt sich aus der Forderung, dass die Identität

in erster Ordnung in erfüllt sei. Aus der Taylor-Entwicklung erster Ordnung ergibt sich die in lineare Gleichung

Jede einzelne Korrektur kann daraus durch Einsetzen von zu

gewonnen werden, was die oben angegebene Weierstraß-Korrektur ergibt.

Ein globaler Konvergenzbeweis für dieses Verfahren wurde schon in (K. Weierstraß 1891) als alternativer Beweis für den Fundamentalsatz der Algebra angegeben.

Fehlerschätzung mittels Gerschgorin-Kreisen[Bearbeiten | Quelltext bearbeiten]

Eine Fehlerabschätzung und eine alternative Herleitung des Verfahrens ist im Artikel zum Satz von Gerschgorin angegeben. Danach sind in jedem Iterationsschritt alle Nullstellen des Polynoms p(X) in der Vereinigung der Kreisscheiben enthalten. Sind die Kreisscheiben paarweise disjunkt, so enthält jede genau eine Nullstelle. (A. Neumaier 2003) zeigt die gleiche Aussage für die etwas kleineren Kreisscheiben

Literatur[Bearbeiten | Quelltext bearbeiten]

  • Karl Weierstraß: Neuer Beweis des Satzes, dass jede ganze rationale Function einer Veränderlichen dargestellt werden kann als ein Product aus linearen Functionen derselben Veränderlichen. In: Sitzungsberichte der königlich preussischen Akademie der Wissenschaften zu Berlin. 1891. online
  • E. Durand: Equations du type F(x)=0: Racines d'un polynome. In: Masson et al. (Hrsg.): Solutions numeriques des equations algebriques. Vol. 1. 1960,
  • Immo O. Kerner: Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen. In: Numerische Mathematik. 8, 1966, S. 290–294.
  • Marica Prešić: A convergence theorem for a method for simultaneous determination of all zeros of a polynomial. In: Publications de l'institut mathematique (Beograd) (N.S.). 28(42), 1980, S. 158–168.
  • M. S. Petkovic, C. Carstensen, M. Trajkovic: Weierstrass formula and zero-finding methods. In: Numerische Mathematik. 69, 1995, S. 353–372.
  • Bo Jacoby: Nulpunkter for polynomier. CAE-nyt (a periodical for Dansk CAE Gruppe [Danish CAE Group]), 1988.
  • Agnethe Knudsen: Numeriske Metoder. (lecture notes), Københavns Teknikum.
  • Bo Jacoby: Numerisk løsning af ligninger. Bygningsstatiske meddelelser (Published by Danish Society for Structural Science and Engineering) 63, no. 3–4, 1992, S. 83–105.
  • Xavier Gourdon: Combinatoire, Algorithmique et Geometrie des Polynomes. Ecole Polytechnique, Paris 1996 (Postscript [abgerufen am 15. Oktober 2006]).
  • Victor Pan: Univariate Polynomial Root-Finding with Lower Computational Precision and Higher Convergence Rates. Tech-Report, City University of New York, Mai 2002.
  • Bini, D. A.; Gemignani, L.; Pan, V. Y.: Inverse power and Durand-Kerner iterations for univariate polynomial root-finding. Comput. Math. Appl. 47 (2004), no. 2-3, 447–459
  • Arnold Neumaier: Enclosing clusters of zeros of polynomials. In: Journal of Computational and Applied Mathematics. 156, 2003.

Weblinks[Bearbeiten | Quelltext bearbeiten]