Weierstraß-(Durand-Kerner)-Verfahren

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

Es sei $p(X)=X^{n}+p_{n-1}X^{n-1}+\cdots +p_{0}$ ein normiertes univariates Polynom mit komplexen Koeffizienten und mit führendem Koeffizienten 1. Dieses hat nach dem Fundamentalsatz der Algebra genau n Nullstellen $\xi _{1},\dots ,\xi _{n}\in \mathbb {C}$ und kann in Linearfaktoren zerlegt werden,

$p(X)=(X-\xi _{1})\cdots (X-\xi _{n}).\,$

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

$\xi _{k}=X-{\frac {p(X)}{\prod _{j=1,\dots ,n,\;j\neq k}(X-\xi _{j})}}.$

Diese Formel kann als triviale Fixpunktiteration verstanden werden, die Iteration

$z_{k}^{(i+1)}:=z_{k}^{(i)}-{\frac {p(z_{k}^{(i)})}{\prod _{j=1,\dots ,n,\;j\neq k}(z_{k}^{(i)}-\xi _{j})}}$

wird offensichtlich nach dem ersten Iterationsschritt in der Nullstelle $\xi _{k}$ stationär.

Ersetzt man nun in der Iterationsvorschrift die anderen Nullstellen durch gute Näherungen, so bleibt $\xi _{k}$ 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 $z_{1}^{(i)},\dots ,z_{n}^{(i)}\in \mathbb {C}$. Für den ersten Schritt können diese Zahlen $z_{1}^{(0)},\dots ,z_{n}^{(0)}\in \mathbb {C}$ 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 ${\vec {z}}^{(i)}=(z_{1}^{(i)},\dots ,z_{n}^{(i)})$ wird das Polynom $g(X):=(X-z_{1}^{(i)})\cdot \ldots \cdot (X-z_{n}^{(i)})$ zugeordnet, das diese komplexen Zahlen als Nullstellen hat. Von diesem Polynom wird die Ableitung $g'(X)$ nach der Unbestimmten X bestimmt. Es gelten

$g(z_{k}^{(i)})=0$ und $g'(z_{k}^{(i)})=\prod _{j\neq k}(z_{k}^{(i)}-z_{j}^{(i)}).$

Aus p(X) und der Ableitung $g_{{\vec {z}}^{(i)}}'(X)$ werden die Weierstraß-Korrekturen $w_{k}^{(i)}=-{\frac {p(z_{k}^{(i)})}{g'(z_{k}^{(i)})}}$, k = 1, ..., n bestimmt und das korrigierte Tupel ${\vec {z}}^{(i+1)}={\vec {z}}^{(i)}+{\vec {w}}^{(i)}=(z_{1}^{(i)}+w_{1}^{(i)},\dots ,z_{n}^{(i)}+w_{n}^{(i)})$ 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

Die oben angegebene 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

Zu lösen sei die kubische Gleichung $x^{3}-3x^{2}+3x-5=0$. Als Starttupel werde $(z_{1},z_{2},z_{3})=(a^{0},a^{1},a^{2})$ mit dem komplexen Parameter $a=0{,}4+0{,}9\cdot i$ 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 $(z_{1},z_{2},z_{3})$ 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 dem Satz 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

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

$g({\vec {z}})(X)=\prod _{j=1}^{n}(X-z_{j})=p(X).$

Da die Polynome auf beiden Seiten normiert sind (der höchstgradige Koeffizient ist 1), ist die Identität 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 ${\vec {w}}=(w_{1},\dots ,w_{n})$ in jedem Schritt der Newton-Iteration ergibt sich aus der Forderung, dass die Identität

$g({\vec {z}}+{\vec {w}})(X)=\prod _{j=1}^{n}(X-z_{j}-w_{j})=p(X)$

in erster Ordnung in ${\vec {w}}$ erfüllt sei. Aus der Taylor-Entwicklung erster Ordnung ergibt sich die in ${\vec {w}}$ lineare Gleichung

$g({\vec {z}})(X)-\sum _{k=1}^{n}w_{k}\,\prod _{j\neq k}(X-z_{j})=p(X).$

Jede einzelne Korrektur $w_{k}$ kann daraus durch Einsetzen von $X=z_{k}$ zu

$w_{k}=-{\frac {p(z_{k})-g({\vec {z}})(z_{k})}{\prod _{j\neq k}(z_{k}-z_{j})}}=-{\frac {p(z_{k})}{\partial _{X}g({\vec {z}})(z_{k})}}$

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

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 $D{\big (}z_{k}+w_{k},(n-1)\cdot |w_{k}|{\big )}$ 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 $D{\big (}z_{k}+n/2\cdot w_{k},n/2\cdot |w_{k}|{\big )}.$

Nicht-generelle Konvergenz

Das Weierstrass / Durand-Kerner-Verfahren ist nicht generell konvergent (d. h. für ein gegebenes Polynom ist die Menge der Startvektoren, die gegen die Nullstellen konvergieren, nicht offen und dicht). In der Tat gibt es eine offene Menge von Polynomen und eine offene Menge von Startvektoren, die gegen periodische Zyklen konvergieren, die nicht Nullstellen sind (siehe Reinke et al). Beispielsweise hat das Polynom $z^{3}+z+177$ eine offene Menge von Startvektoren, die gegen einen Zyklus der Länge 4 konvergieren.

Literatur

• 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. Korrigierte, aktuelle Links: digilab.bbaw.de, de.wikisource.de, www.biodiversitylibrary.org, zdb-katalog.de/title.xhtml, sämtlich abgerufen am 31. Mai 2021.
• 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. Jahrgang, 1966, S. 290–294 (springer.com). 
• 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). Jahrgang, 1980, S. 158–168. 
• M. S. Petkovic, C. Carstensen, M. Trajkovic: Weierstrass formula and zero-finding methods. In: Numerische Mathematik. 69. Jahrgang, 1995, S. 353–372 (springer.com). 
• 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. Jahrgang, 2003 (univie.ac.at). 
• Bernhard Reinke, Dierk Schleicher, und Michael Stoll, The Weierstrass root finder is not generally convergent, 2020

Weblinks

• Jan Verschelde, The method of Weierstrass (also known as the Durand-Kerner method), 2003.